Лекция по компьютерным системам

 

5. Метрики  параллельных  вычислений

 

В силу особенностей параллельных вычислений для оценки их эффек-тивности используется специфическая система метрик.

 

Профиль параллелизма программы

Степень параллелизма D(t) (DOP, Degree Of Parallelism) – это число процес-соров многопроцессорной системы, параллельно участвующих в выполнении программы в каждый момент времени t. Графическое представление параметра D(t) как функции времени называется профилем параллелизма программы. Изменения в уровне загрузки процессоров за время наблюдения зависят от многих факторов (алгоритма, доступных ресурсов, степени оптимизации, обес-печиваемой компилятором и т.д.). Типичный профиль параллелизма для алго-ритма декомпозиции (divide-and-conquer algorithm) показан на рис. 1.1.

 

Рис. 1.1. Профиль параллелизма

 

В дальнейшем предполагается, что система состоит из n гомогенных про-цессоров, максимальный параллелизм в профиле равен m и n >> m. Производи-тельность Δ одиночного процессора системы выражается в единицах скорости вычислений (количество операций в единицу времени) и не учитывает издержек, связанных с обращением к памяти и пересылкой данных. Если за наблюдаемый период загружены i процессоров, то D= i.

Общий объем вычислительной работы W (команд или вычислений), вы-полненной начиная со стартового момента ts до момента завершения te, пропор-ционален площади под кривой параллелизма:

.

Интеграл часто заменяют дискретным эквивалентом:

,

где ti – общее время, в течение которого D = i, a  – общее затраченное время.

Средний параллелизм А определяется как

.

В дискретной форме это можно записать так:

 

.

 

Профиль параллелизма на рис. 1.1 за время наблюдения (ts, te) возрастает от 1 до пикового значения m=8, а затем спадает до 0. Средний параллелизм A = (1×5 +    + 2×3 + 3×4 + 4×6 + 5×2 + 6×2 + 8×3) / (5 + 3 + 4 + 6 + 2 + 2 + 3) = 93/25 = 3,72. Фактически общая рабочая нагрузка и A представляют собой нижнюю границу асимптотического ускорения.

Параллельная программа выполняется в режиме i, если для ее исполнения задействованы i процессоров. Время, в течение которого система работает в режиме i, обозначим через ti, а объем работы, выполненной в режиме i, как          Wi = i×Δ×ti. Тогда при наличии n процессоров время исполнения T(n) для двух экстремальных случаев: n = 1 (T(1)) и n = (T( )) можно записать в виде:

 

.

 

Асимптотическое повышение быстродействия S определяется как отно-шение T(1)  к T( ):

.

Сравнивая это выражение и предыдущие уравнения, можно констатировать, что в идеальном варианте S = A. В общем случае нужно учитывать комму-никационные задержки и системные издержки. Как S , так и A были опреде-  лены в предположении, что n >> m.

 

6. Классификация  параллельных  вычислительных  систем

 

Наибольшее признание получила классификация ВС, предложенная в 1966 году М. Флинном. В ее основу положено понятие потока, под которым пони-мается последовательность элементов, команд или данных, обрабатываемая про-цессором. В зависимости от количества потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, SIMD, MIMD.

 

SISD

SISD (Single Instruction Stream/Single Data Stream) – одиночный поток ко-манд и одиночный поток данных (рис. 1.2, а). Представителями этого класса являются классические фон-неймановские ВМ, где имеется только один поток команд, команды обрабатываются последовательно и каждая команда инициирует одну операцию с одним потоком данных. То, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка, не имеет значения, поэтому в класс SISD одновременно попадают как ВМ СDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными.

 

Рис. 1.2. Архитектура вычислительных систем по Флинну: а – SISD; б – MISD;

в – SIMD; г – MIMD

 

MISD

MISD (Multiple Instruction Stream/Single Data Stream) – множественный  поток команд и одиночный поток данных (рис. 1.2, б). Из определения следует, что в архитектуре ВС присутствует множество процессоров, обрабатывающих один и тот же поток данных. Примером могла бы служить ВС, на процессоры которой подается искаженный сигнал, а каждый из процессоров обрабатывает этот сигнал с помощью своего алгоритма фильтрации. Тем не менее ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не сумели представить убедительный пример реально существующей вычислительной сис-темы, построенной на данном принципе. Ряд исследователей относят к данному классу конвейерные системы, однако это не нашло окончательного признания. Отсюда принято считать, что пока данный класс пуст. Наличие пустого класса не следует считать недостатком классификации Флинна. Такие классы могут стать чрезвычайно полезными для разработки принципиально новых концепций в теории и практике построения вычислительных систем.

 

 

SIMD

SIMD (Single Instruction Stream/Multiple Data Stream) – одиночный поток команд и множественный поток данных (рис. 1.2, в). ВМ данной архитектуры позволяют выполнять одну арифметическую операцию сразу над многими дан-ными – элементами вектора. Представителями класса SIMD считаются матрицы процессоров, где единое управляющее устройство контролирует множество про-цессорных элементов. Все процессорные элементы получают от устройства уп-равления одинаковую команду и выполняют ее над своими локальными данными. В принципе в этот класс можно включить и векторно-конвейерные ВС, если каждый элемент вектора рассматривать как отдельный элемент потока данных.

 

MIMD

MIMD (Multiple Instruction Stream/Multiple Data Stream) – множественный поток команд и множественный поток данных (рис. 1.2, г). Класс предполагает наличие в вычислительной системе множества устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком ко-манд и данных. Класс MIMD чрезвычайно широк, поскольку включает в себя всевозможные  мультипроцессорные системы. Кроме того, приобщение к классу MIMD зависит от трактовки. Так, векторно-конвейерные ВС можно отнести и к классу MIMD, если конвейерную обработку рассматривать как выполнение множества команд (операций ступеней конвейера) над множественным скаляр-ным потоком.

Схема классификации Флинна вплоть до настоящего времени является наиболее распространенной при первоначальной оценке той или иной ВС, поскольку позволяет сразу оценить базовый принцип работы системы. Однако у классификации Флинна имеются и очевидные недостатки, например, неспособ-ность однозначно отнести некоторые архитектуры к тому или иному классу. Другая слабость – это чрезмерная насыщенность класса MIMD. Все это породило попытки либо модифицировать классификацию Флинна, либо предложить иную систему классификации.

 

Контрольные вопросы

 

1. По каким признакам можно разграничить понятия «вычислительная машина» и «вычислительная система»?
2. По каким признакам выделяют поколения вычислительных машин?
3. Пояснить определяющие идеи для каждого из этапов эволюции вычисли-тельной техники.
4. Сравните схемы классификации параллелизма по уровню и гранулярности. Каковы достоинства, недостатки и области применения этих схем клас-сификации?
5. Для заданной программы и конфигурации параллельной вычислительной системы рассчитать значения метрик параллельных вычислений.
6. Укажите достоинства и недостатки схемы классификации Флинна.