1.Анализ архитектур параллельных вычислительных систем
1.1.Параллелизм в работе ЭВМ
Параллелизм – основа высокопроизводительной работы всех подсистем вычислительных машин. Организация памяти любого уровня иерархии, организация системного ввода/вывода, организация мультиплексирования шин и т.д. базируются на принципах параллельной обработки запросов. Современные операционные системы являются многозадачными и многопользовательскими, имитируя параллельное исполнение программ посредством механизма прерываний.
Развитие производства процессоров также ориентировано на распараллеливание операций, т.е. на выполнение процессором большего числа операций за такт. Ключевыми ступенями развития архитектуры процессоров стали гиперконвейеризация, суперскалярность, неупорядоченная модель обработки, векторное процессирование (технология SIMD – single instruction, multiple data – одиночный поток команд, множественный поток данных), архитектура VLIW (Very long instruction word – очень длинная машинная команда). Все ступени были ориентированы на повышение степени параллелизма исполнения.
В настоящее время мощные сервера представляют собой мультипроцессорные системы, а в процессорах активно используется параллелизм уровня потоков.
1.2.Уровни параллелизма
Параллелизм – это возможность одновременного выполнения более одной арифметико-логической операции. Возможность параллельного выполнения этих операций определяется правилом Рассела, которое состоит в следующем:
Программные объекты A и B (команды, операторы, программы) являются независимыми и могут выполняться параллельно, если выполняется следующее условие:
(InB И OutA) ИЛИ (InA И OutB) И (OutA И OutB) = ∅,
где In(A) – набор входных, а Out(A) – набор выходных переменных объекта A. Если условие не выполняется, то между A и B существует зависимость и они не могут выполняться параллельно.
Если условие нарушается в первом терме, то такая зависимость называется прямой. Приведем пример:
A: R = R1 + R2
B: Z = R + C
Здесь операторы A и B не могут выполняться одновременно, так как результат A является операндом B.
Если условие нарушено во втором терме, то такая зависимость называется обратной:
A: R = R1 + R2
B: R1 = C1 + C2
Здесь операторы A и B не могут выполняться одновременно, так как выполнение B вызывает изменение операнда в A.
Наконец, если условие не выполняется в третьем терме, то такая зависимость называется конкуренционной:
A: R = R1 + R2
B: R = C1 + C2
Здесь одновременное выполнение операторов дает неопределенный результат.
Увеличение параллелизма любой программы заключается в поиске и устранении указанных зависимостей.
Наиболее общей формой представления этих зависимостей является информационный граф задачи (ИГ). Пример ИГ, описывающего логику конкретной задачи, дан на рис. 1.1. В своей первоначальной форме ИГ, тем не менее, не используется ни математиком, ни программистом, ни ЭВМ.
Более определенной формой представления параллелизма является ярусно-параллельная форма (ЯПФ): алгоритм вычислений представляется в виде ярусов, причем в нулевой ярус входят операторы (ветви), не зависящие друг от друга, в первый ярус – операторы, зависящие только от нулевого яруса, во второй – от первого яруса и т. д.
Для ЯПФ характерны параметры, в той или иной мере отражающие степень параллелизма метода вычислений: bi – ширина i-го яруса; B – ширина графа ЯПФ (максимальная ширина яруса, т. е. максимум из bi, i = 1, 2, ...); li – длина яруса (время операций) и L длина графа; ε – коэффициент заполнения ярусов; θ – коэффициент разброса указанных параметров и т. д.
Рис. 1.. Информационный граф математического выражения и порядок выполнения операций в выражении
Распараллеливание операций – перспективный путь повышения производительности вычислений. Согласно закону Мура число транзисторов, размещаемых на интегральной схеме, экспоненциально растёт, что позволяет в настоящее время включать в состав CPU большое количество исполнительных устройств самого разного назначения.
В 70-е годы стал активно применяться принцип конвейеризации вычислений. Конвейер Intel Pentium 4 (на ядрах Willamette и Northwood) состоит из 20 ступеней, а в процессорах на ядрах Prescott и Cedar Mill – из 31 ступени. Такое распараллеливание на микроуровне – первый шаг на пути эволюции процессоров. На принципах конвейеризации базируются и внешние устройства. Например, динамическая память (организация чередования банков) или внешняя память (организация RAID).
Использование микроуровневого параллелизма позволяло лишь уменьшать количество тактов на инструкцию (Cycles Per Instruction – CPI), в то время как миллионы транзисторов при выполнении одиночной инструкции простаивали. На следующем этапе эволюции в 80-е годы стали использовать параллелизм уровня команд посредством размещения в CPU сразу нескольких конвейеров. Такие CPU позволяли достигать CPI<1. Параллелизм уровня инструкций (Instruction Level Parallelism – ILP) породил неупорядоченную модель обработки, динамическое планирование, станции резервации и т.д. Поэтому от CPI перешли к количеству инструкций за такт (Instructions Per Cycle – IPC). Но ILP ограничен алгоритмом исполняемой программы. Кроме того, при увеличении количества ALU сложность оборудования экспоненциально растёт, увеличивается количество горизонтальных и вертикальных потерь в слотах выдачи. Параллелизм уровня инструкций исчерпал свои резервы, а закон Мура позволил производителям процессоров осваивать более высокие уровни параллелизма. Современные методики повышения ILP основаны на использовании процессоров класса SIMD. Это векторное процессирование, матричные процессоры, архитектура VLIW.
Параллелизм уровня потоков и уровня заданий применяется в процессорах класса MIMD. Многопоточные процессоры позволяют снижать вертикальные потери в слотах выдачи, а Simultaneous Multithreading (SMT) процессоры – как вертикальные, так и горизонтальные потери. Трудность применения следствий закона Мура на одном ядре из-за сложности такого ядра предопределила выпуск многоядерных процессоров (CMP).
Параллелизм всех уровней свойственен не только процессорам общего назначения (GPP), но и специальным процессором (ASP (Application-Specific Processor), DSP (Digital Signal Processor)).
Иногда классифицируют параллелизм по степени гранулярности как отношение объёма вычислений к объёму коммуникаций. Различают мелкозернистый, среднезернистый и крупнозернистый параллелизм (рис. 1.2.). Мелкозернистый параллелизм обеспечивает сам CPU, но компилятор может и должен ему помочь для обеспечения большего IPC. Среднезернистый параллелизм – прерогатива программиста, которому необходимо разрабатывать многопоточные алгоритмы. Здесь роль компилятора заключается в выборе оптимальной последовательности инструкций (с большим IPC) посредством различных методик (например, символическое разворачивание циклов). Крупнозернистый параллелизм обеспечивает ОС.
Уровень параллелизма
|
Степерь гранулярности (отношение объема вычислений к объему коммуникаций)
|
Микроуровневый параллелизм
|
Мелкозернистый (fine grained), обеспечивается:
|
Параллелизм уровня команд
|
Среднезернистый (medium grained), обеспечивается:
|
Параллелизм уровня потоков
|
Крупнозернистый (coarse grained), обеспечивается:
|
Параллелизм уровня заданий
|
Рис. 1.2. Уровни параллелизма
|
