Явный и неявный параллелизм программ. Методы автоматического распараллеливания программ. Мультипроцессорные ОС.
Многопроцессорные системы.
Производительность вычислительных систем.
1) время реакции системы (случайная величина, от внешнего воздействия до начала кванта времени, которому система предназначается). 2) время отклика системы (случайная величина, время до реакции системы). 3) оборотное время (случайная величина, время от поступления задания до выдачи результатов). 4) дисперсия этих случайных параметров отражает степень предсказуемости системы, очень важна для интерактивных систем. 5) пропускная способность вычислительной системы. 6) степень загрузки вычислительной системы. Существуют разновидности тестов: 1) контрольные задачи или BenchMark – типовая рабочая программа, для оценки производительности системы. 2) синтетические тесты (задачи) – специальные задачи для тестирования отдельных компонентов системы. При оценке производительности нужно выделять узкие места (BottleNeck) – те ресурсы, которые либо ограничивают суммарную производительность системы, либо вводит в состояние насыщения, например: Общая производительность системы зависит не только от частоты процесса, но и от прочих ресурсов, но, тем не менее, наиболее важное устройство, определяющее производительность – процессор.Производительность процессора и пути повышения производительности
1) выбор оптимальной системы команд: а) CISC, б) RISC. а) CISC (со сложным набором команд). Удобно для программирования, чтобы команда имела законченное действие (состоящее из множества простых). Малое количество регистров общего назначения приводит к потенциальному сокращению производительности. б) RISC (с сокращенным набором команд). Предложил и начал широко использовать Саймур Крэй (Cray), создал в 60-х годах многопроцессорную систему (суперкомпьютер). Команд мало и они элементарные, быстро выполняются, занимают мало места (одна команда), очень большие объемы внутренних регистров. Недостаток: сложность программирования (место, занимаемое программой в памяти, несколько больше). 2) суперскалярная архитектура вычислительного процессора (на одном кристалле несколько вычислительных блоков), например ОДКС или VLIW (очень длинное командное слово). 3) динамическое изменение последовательности команд: Цель: что бы процессор меньше ждал. Применяется предсказание ветвления, использование сопроцессоров: а) математического, б) векторного (одновременная обработка массива данных), в) матричный (одновременная обработка матрицы данных). 4) конвейерная обработка команд. 5) использование иерархии памяти.Мультипроцессорные вычислительные системы.
1) по архитектуре (сколько потоков команд, сколько потоков данных): а) ОКОД – одна команда одно данное (SISD – Single Instruction Stream Single Data Stream) Обычная фон Неймановская вычислительная машина.
Поток данный, поток команд и результат.
Процессор, запоминающее устройство.
б) Конвейерные и векторные процессоры.
Конвейерные и векторные процессоры – используются для векторных команд, когда одна и та же операция применяется ко всем элементам вектора (операции над массивами). При работе данных видов процессора требуется дополнительное время для начальной инициализации работы, а затем данные с высокой скоростью поступают в процессор и обрабатываются в своем операционном устройстве.
Данный тип процессоров увеличивает производительность процессоров при работе с векторами.
в) Матричные процессоры, SIMD, Single Instruction Stream Multiple Data Stream
Матричные процессоры состоят из большого количества идентичных процессорных элементов (ПЭ), которые имеют свою память. Все процессорные элементы выполняют одну и ту же программу. Данная модель схожа с моделью конвейерного и векторного процессора, но здесь уже в качестве вычислительного блока используется отдельные процессорные элементы. Данные процессоры так же используются на векторных операциях, а так же используются при выполнении нескольких итераций цикла. То есть на всех процессорных элементах выполняется одна и та же команда.
г) Многопроцессорные системы класса, MIMD или МКМД.
В данном случае в качестве процессоров типа MIMD используются процессоры типа SISD, и требуется обеспечить их взаимодействие. В отличие от матричного, здесь требуется обеспечить взаимодействие процессоров.
д) Вычислительные системы типа MSIMD – многопроцессорные системы с матричными процессорами. Данный класс многопроцессорных систем используется в суперкомпьютерах, то есть здесь одновременно выполняется декомпозиция команд на одном из процессоров и одновременно несколько задач распределяется на несколько матричных процессорах. Данная организация дает возможность использовать одновременно мелкозернистый и крупнозернистый параллелизм одновременно.
2) по степени связи между вычислительными блоками (процессорами)
а) тесно связанные – общие ресурсы.
б) слабо связанные – нет общих ресурсов, но есть канал связи. Если канал связи мал, то это транспьютер, если большой, то – многомашинная система.
MPP – многомашинная система, в отличие от предыдущего класса MSIMD в том, что в качестве элемента системы выступает один компьютер, данные многомашинные системы строятся как многопроцессорные системы с обменом посредством сообщений. Используются данный класс параллельных вычислительных систем, например, в АСУТП или в АСУП.
Многопроцессорные системы с общей памятью, в системе имеется общая память, которая доступна всем процессорным элементам, так называемая сильно связанная система.
Многопроцессорные системы с обменом посредством сообщений. В данных многопроцессорных системах отсутствует общая память, а синхронизация и передача сообщений осуществляется по высокоскоростной сети. Эти системы называют слабо связанными системами.
Транспьютер состоит из 2-х слов – транзит и компьютер. Транспьютер – сверхбольшая интегральная схема, включающая в себе ЦП, блок операций с плавающей точкой, статическое ОЗУ, чипсет (интерфейс) с внешней памятью и несколько каналов связи (Link).
3) по схеме соединения процессоров:
а) общая шина
Достоинства: простота наращивания устройств.
Недостатки: Шина – разделяемый объект, тормозит всю систему (если отказывает шина, то отказывает вся система). Данная система оправдана для небольшого числа процессоров.
б) переключающая матрица.
Достоинства: одновременная работа множества процессоров с множеством блоков памяти; повышена надежность.
Недостатки: сложность устройства.
4) сетевые многопроцессорные структуры (слабо связанные системы).
1) 4-х связная (4-х линковая) 2-х мерная сеть:
Узел: процессор + память = транспьютер. à Транспьютерная сеть.
Достоинства: достаточная живучесть; низкая стоимость; высокая производительность. Недостаток: если например нужно передать информацию от 1У к 9У, то нужно искать путь для передачи (затраты времени). 2) гиперкуб (n-Cube, n - размерность): структура из узлов, каждый из которых имеет - линков.
Достоинства: сокращение размеров путей.
Недостатки: сложность изготовления.
3) многоуровневая сеть:
Достоинства: каждый с каждым без посредников, нет ретранслирующих узлов; коммутаторы (например по 4 линка) простые.
Недостатки: промежуточные коммутации, задерживающие сигнал (данные все равно не на прямую, а через К).
Многопроцессорные ОС.
Проблемы: 1) защита ядра ОС от повторного вхождения. 2) защита разделяемых данных. Методы защиты, которые использовались в однопроцессорных системах (блокировка диспетчера, запрет всех прерываний), не работают. Пути решения: 1) полная реентерабельность ядра. В противном случае можно использовать систему master-slave на одном ядре ОС. 2) при обращении к разделяемым данным необходимо использовать специальные семафоры. Классы мультипроцессорных ОС, по организации: 1) ОС по типу master-slave. ОС только на одном процессоре исполняется, остальные процессы на подчиненных. За системными вызовами подчиненные (slave) обращаются к процессору master, который в каждый момент времени может выполнять только один запрос. Надежность – недостаточная. Достоинство: простота. Недостаток: большая загруженность мастер – процесса. 2) МОС с разделенными ядрами (Separate Kernel). Разделение ОС по ядрам. Большинство локальных вызовов независимы, при обращении к глобальным вызовам необходимо использовать семафоры и другие методы синхронизации. Достоинства – высокая надежность. Недостатки – нет коопераций между процессорами. Пример ОС: Tandem в областях критически важных приложений. 3) симметричная МОС. Самые мощные, сложные и эффективные. Одна общая ОС, выполняется одновременно на всех процессорах, наиболее широко используются специальные семафоры. Для таких систем характерна миграция процессов, полная реентерабельность, отсутствие однозначной привязки процессов. Системы: HP-UX, Solaris, Sun.- Пример: система, 256 процессоров, ОС – симметричная.
Параллельное программирование.
Параллельное программирование сложно. Для повышения производительности (распараллеливание). Причины: 1) особенности человеческого мышления. 2) некоторые языки не приспособлены, примеры языков параллельного программирования: ADA, Modula, параллельный Pascal. 3) трудности отладки. Критерий распараллеливания: 1) независимость операций. 2) перестановка операций.- Ручное;
- Автоматическое (на уровне компилятора).
