Параллельные вычисления
 Скачать 1.75 Mb.
|
|
овыми средствами. Синхронизация может поддерживаться и аппаратно (например, барьерная синхронизация в суперкомпьютере Cray T3, с помощью которой осуществля- ется ожидание всеми процессами определенной точки в программе, после достижения которой возможна дальнейшая работа, см. подраздел 2.4.1). 1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля) Представляет интерес оценка величины возможного повышения произво- дительности с учетом качественных характеристик самой исходно последо- вательной программы. Закон Амдаля (Gene Amdahl, 1967) связывает потенциальное ускорение вычислений при распараллеливании с долей операций, выполняемых априори последовательно. Пусть f (0<f<1) – часть операций алгоритма, которую рас- параллелить не представляется возможным; тогда распараллеливаемая часть равна (1-f); при этом затраты времени на передачу сообщений не учитывают- ся, t s - время выполнения алгоритма на одном процессоре (последователь- ный вариант), n – число процессоров параллельной машины. При переносе алгоритма на параллельную машину время расчета распре- делится так: • t s f × - время выполнения части алгоритма, которую распараллелить не- возможно, • n f t s × − ) 1 ( - время, затраченное на выполнение распараллеленной части алгоритма. Время t p , необходимое для расчета на параллельной машине с n процес- сорами, равно (см. рис.4) n f f t t t s s p / ) 1 ( × − + × = , а ускорение времени расчета - 31 - ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − + = × − + × = ≤ n f f n / ) f ( f S t t t t t s s s p s 1 1 1 . (4) Анализ выражения (4) показывает (т.к. f ) n f ( S n lim 1 , = ∞ → ), что только при малой доли последовательной операций (f<<1) возможно достичь значитель- ного (естественно, не более чем в n раз) ускорения вычислений (рис.5). В случае f=0,5 ни при каком (даже бесконечно большом) количестве процессо- ров невозможно достичь S>2! Заметим, что эти ограничения носят фун- даментальный харак- тер (их нельзя обойти для заданного алгорит- ма), однако практиче- ская оценка доли f по- следовательных опера- ций априори обычно не- возможна. Таким образом каче- ственные характеристи- ки самого алгоритма на- кладывают ограничения на возможное ускорение при распараллеливании. Например, характерные для инженерных расчетов алгоритмы счета по последовательным формулам рас- параллеливаются плохо (часть f значима), в то же время сводимые к задачам линейного программирования (ЛП – операции с матрицами – умножение, об- ращение, нахождение собственных значений, решение СЛАУ – систем ли- нейных алгебраических уравнений и т.п.) алгоритмы распараллеливаются удовлетворительно. Априорно оценить долю последовательных операций f непросто (само по- нятие ‘последовательных’ и ‘параллельных’ операций трудноформализируе- мо и допускает неоднозначные толкования). Однако можно попробовать формально использовать формулу Амдаля для решения обратной задачи – определения f по экспериментальным данным производительности; это дает возможность количественно судить о достигнутой эффективности распа- раллеливания. Рисунок 4 — Схема к выводу закона Амдаля - 32 - На рис.6 приведены резуль- таты эксперимента на кластере SCI-MAIN НИВЦ МГУ на зада- че умножения матриц по лен- точной схеме (размерность 10 3 × 10 3 вещественных чисел двойной точности, серия опы- тов марта 2005 г.), эксперимен- тальные данные наилучшим об- разом (использован метод наи- меньших квадратов) соответст- вуют формуле Амдаля при f=0,051 (вывод: данный алго- ритм распараллелен эффектив- но, т.к. доля параллельных опе- раций составляет ≅ 95%, что вполне удовлетворительно для алгоритма со сложностью уровня O(n 3 ) операций). Формальный вывод – ждать более чем 20-ти кратного увеличения производительности такого ал- горитма не следует! Закон Амдаля удобен для качест- венного анализа проблемы распарал- леливания, недос- татком выражения (4) является неучет потерь времени на межпроцессорный обмен сообщениями (что как раз и выра- жено знаком ‘мень- ше или равно’ в (4)); эти потери могут не только снизить уско- рение вычислений в параллельном варианте, но и замедлить вычисления по сравнению с последо- вательным. Более общим является выражение (сетевой закон Амдаля): с n f f S + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ − + = 1 1 , Рисунок 6 — Производительность вычислительной кластер- ной системы на процедуре умножения матриц (экспери- мент и расчет по формуле Амдаля) Рисунок 5 — Трехмерный график, количественно отражающий зависимость Амдаля согласно выражения (4) - 33 - где c – коэффициент сетевой деградации вычислений, t W с t W с с с с t w × × = × = , W с - количество передач данных, W – общее число вычислений в за- даче, t с - время одной передачи данных, t – время выполнения одной операции. Сомножитель W W с с w = (повышение коего снижает S) определяет состав- ляющую коэффициента деградации, вызванную свойствами алгоритма рас- параллеливания: t t с с t = - зависящую от соотношения производительности процессора и аппаратуры сети (‘техническую’) составляющую; значения с w и с t могут быть оценены заранее. Т.о. полученные (при неучете сетевой де- градации вычислений) из выражения (4) значения f являются пессимистиче- скими. Было бы странно, если бы даже при идеальном параллелизме (f=0) сетевое ускорение вычислений могло быть выше n с f lim с = ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ + ⎟ ⎠ ⎞ ⎜ ⎝ ⎛ + → n f - 1 1 0 Удивительно (для столь ограниченной модели!), что в некоторых случаях ускорение времени вычислений на n-процессорной МВС количественно пре- вышает величину числа процессоров (т.н. 'парадокс параллелизма’)! Объяс- нения лежат в чисто технической области - напр., обработка однопроцессор- ной (или SMP, см. подраздел 2.1) системой матриц значительного размера с большой вероятностью приведет к необходимости сброса части элементов матриц на внешнюю (обычно дисковую) память (своппинг, swapping), а дли- тельность этой процедуры на многие порядки превышает время обращения к ОП. При разумном программировании для МВС эти матрицы будут распре- делены между ОП процессоров, причем каждая часть матриц полностью по- мещается в ОП и своппинга не будет – в этом и объяснение ‘чудесного’ по- вышения быстродействия. Контрольные вопросы 1. Что такое суперкомпьютер? Чем он (количественно и качественно) отли- чается от персональной ЭВМ? В каких областях человеческой деятельно- сти необходимо применение суперкомпьютеров? - 34 - 2. В каких единицах выражается производительность супер-ЭВМ? Каким об- разом сравниваются производительности различных суперкомпьютеров? Какие из этих характеристик (хотя бы качественно) наиболее объективны? 3. Какие причины тормозят дальнейшее увеличение вычислительных мощно- стей однопроцессорных компьютеров? Каковы аргументы против приме- нения параллельных вычислений? Есть ли альтернативы параллельным вычислительным технологиям? 4. Доказать возможность полностью параллельного вычисления любого за- данного алгоритма. Какова его практическая ценность? 5. В чем суть теоремы Брента? Каким путем можно уменьшить число шагов при моделировании (построении) схемы из функциональных элементов? 6. Дать определение процесса (параллельного процесса) и зерна (гранулы) распараллеливания. В каких единицах можно определить величину грану- лы (привести несколько вариантов ответа)? 7. Для чего нужна синхронизация выполнения параллельных процессов? Ка- ким образом синхронизация может помочь в решении проблемы возникно- вения дедлоков? 8. Чем ограничивается возможность распараллеливания реальных алгорит- мов? В чем суть закона Амдаля? Предложите методику ‘обхода’ закона Амдаля? 9. Какую (количественно!) долю последовательных операций можно считать допустимой для различных вычислительных алгоритмов? - 35 - 2 Принципы построения многопроцессорных вычислительных систем 2.1 Архитектура многопроцессорных вычислительных систем Архитектура параллельных компьютеров развивалась практически с само- го начала их создания и применения, причем в самых различных направлени- ях. Наиболее общие положения приводят к двум классам – компьютеры с общей памятью и компьютеры с распределенной памятью. Компьютеры с общей памятью (мультипроцессоры, компьютеры с разде- ляемой памятью) состоят из нескольких (одинаковых, возможно) процессо- ров, имеющих равноприоритетный доступ к общей памяти с единым адрес- ным пространством (рис.7a). Типичный пример такой архи- тектуры – компьютеры класса SMP (Symmetric Multi Proces- sors), включающие несколько процессоров, но одну память, комплект устройств вво- да/вывода и операционную систему (‘symmetric’ означает возможность каждого процес- сора выполнять то же, что и любой другой; 2 ÷4- процессорные серверы SMP- архитектуры легко приобрести почти в любом компьютерном магазине). Достоинством ком- пьютеров с общей памятью является (относительная) про- стота программирования параллельных задач (нет необходимости занимать- ся организацией пересылок сообщений между процессорами с целью обмена данными), минусом – недостаточная масштабируемость (при увеличении числа процессоров возрастает конкуренция за доступ к общим ресурсам – в первую очередь памяти, что ограничивает суммарную производительность системы). Реальные SMP-системы содержат обычно не более 32 процессоров, для дальнейшего наращивания вычислительных мощностей подобных систем используется NUMA-технология (см. ниже). Отечественной SMP- разработкой является ЭВМ ‘Эльбрус-1’ (В.С.Бурцев, 1980) с быстродействи- ем до 15 млн. оп./с. (125 млн. оп./с. для ‘Эльбрус-2’); компьютеры этой моде- ли до сих пор обеспечивают функционирование систем противоракетной обороны и космических войск России. Рисунок 7 — Параллельные компьютеры: с общей памятью - а) и с распределенной памятью – б) - 36 - В компьютерах с распределенной памятью (мультикомпьютерные систе- мы) каждый вычислительный узел (ВУ) является полноценным компьютером и включает процессор, память, устройства ввода/вывода, операционную сис- тему и др. (рис.7б). Типичный пример такой архитектуры – компьютерные системы класса MPP (Massively Parallel Processing), в которых с помощью некоторой коммуникационной среды объединяются однородные вычисли- тельные узлы. Достоинством компьютеров с распределенной памятью явля- ется (почти неограниченная) масштабируемость, недостатками – необходи- мость применения специализированных программных средств (библиотек обмена сообщениями) для осуществления обменов информацией между вы- числительными узлами. Для МВС с общей и распределенной памятью ис- пользуются термины сильно- и слабосвязанные машины соответственно. Как было показано, производительность каналов обмена сильно влияет на возможность эффективного распараллеливания, причем это важно для обоих рассмотренных архитектур. Простейшей системой коммуникации является общая шина (рис.8a), которая связывает все процессоры и память, однако да- же при числе устройств на шине больше нескольких десятков производи- тельность шины катастрофически падает вследствие взаимного влияния и конкуренции устройств за монопольное владение шиной при обменах дан- ными. Рисунок 8 — Многопроцессорные системы с общей шиной - а), с матричным коммута- тором – б) и c каскадированием коммутаторов (Омега-сеть) – в) При построении более мощных систем (коммутация десятков/сотен уст- ройств) используются более изощренные подходы. Эффективной (но дорогой вследствие значительного объема оборудования) является схема матричной коммутации (рис.8б), при которой устройства связываются между собой двунаправленными переключателями, разрешающими или запрещающими передачу информации между соответствующими модулями. Альтернативой является каскадирование переключателей; например, по схеме Омега-сети, - 37 - рис.8в. При этом каждый переключатель может соединять любой из двух своих входов с любым из двух выходов, для соединения n процессоров с n блоками памяти в этом случае требуется 2 2 / n n log × переключателей (вместо n 2 по схеме рис.8б). Недостаток схем с каскадированием коммутаторов – за- держки срабатывания переключателей (на схеме рис.8в при произвольном соединении сигнал вынужденно проходит последовательно через n log 2 пе- реключателей вместо единственного по схеме рис.8б). Для систем с распределенной памятью используются практически все мыслимые варианты соединений (см. рис.9), при этом параметром качества с точки зрения скорости передачи сообщений служит величина средней длины пути, соединяющего произвольные процессоры; при этом имеется в виду именно физический путь, т.к. реализовать логическую топологию (про- граммными средствами) не представляет трудностей. Рисунок 9 — Варианты топологий связи процессоров в многопроцессорных вычисли- тельных системах Простейшая линейная топология (рис.9a) удовлетворительно соответству- ет многим алгоритмам, для которых характерна связь лишь соседних процес- сов между собой (одномерные задачи математической физики и многомер- ные, сводимые к одномерным); недостаток – невозможность передачи сооб- щений при разрыве в любом месте. Уменьшение вдвое средней длины пути и повышение надежности связи (при нарушении связи сообщения могут быть переданы в противоположном направлении, хотя и с меньшей скоростью) достигается соединение первого узла с последним – получается топология ‘кольцо’ (рис.9б). Топология ‘звезда’ (рис.9в) максимально отвечает распре- делению нагрузки между процессами, характерной для систем 'клиент/сервер' - 38 - (главный узел ‘раздает’ задания и ‘собирает’ результаты расчетов, при этом подчиненные узлы друг с другом взаимодействуют минимально). Топология ‘решетка’ (рис.9г) использовалась еще в начале 90-х г.г. при построении суперкомпьютера Intel Paragon на основе процессоров i860 [1,4]; нахождение минимального пути передачи данных между процессорами A и B (координаты [1,1,3] и [2,2,3] соответ- ственно ) для топологии ‘трехмерная решетка’ иллюстрировано рис.10. То- пология ‘двумерный тор’ (рис.9д) расширяет ‘двумерную решетку’ до- полнительными связями, снижающи- ми длину среднего пути (само собой, возможен и ‘трехмерный тор’) и ха- рактерна для сетевой технологии SCI (Scalable Coherent Interface), предла- гаемой фирмой Dolphin Interconnect Sol. ( http://www.dolphinics.com ). Приме- няется (рис.9e) характеризующаяся наличием связи каждого процессора с каждым трехмерная топология ‘кли- ка’ (Clique). На рис.9з) приведен об- щий вид топологии полной связи всех процессоров между собой; такая то- пология характеризуется наименьшей (тождественно единичной) длиной среднего пути между процессорами, однако аппаратно практически нереа- лизуема при значительном числе процессоров вследствие катастрофического роста числа связей (однако часто применяется в качестве виртуальной топо- логии, реализуемый на логическом уровне программными средствами). Для топологии ‘гиперкуб’ (рис.9и) характерна сокращенная длина средне- го пути и близость к структурам многих алгоритмов численных расчетов, что обеспечивает высокую производительность. N-мерный гиперкуб содержит 2 N процессоров. Двухмерный гиперкуб - это квадрат, трехмерный гиперкуб образует обычный куб, а четырехмерный гиперкуб представляет собой куб в кубе. Для семейства суперкомпьютеров nCube 2 (известная тесным сотруд- ничеством в области параллельных баз данных с ORACLE фирма nCUBE Corp., сейчас подразделение C-COR, http://www.c-cor.com ) гиперкуб макси- мальной размерности 13 содержит 8192 процессора, в системе nCube 3 число процессоров может достигать 65536 (16-мерный гиперкуб). В качестве основных характеристик топологии сети передачи данных час- то используются следующие показатели: Рисунок 10 — Нахождение минимального пути для передачи сообщений между процессорами в топологии 'трехмерная решетка' - 39 - • Диаметр определяется как максимальное расстояние (обычно кратчай- ших путь между процессорами) между двумя процессорами в сети, эта величина характеризует максимально необходимое время для передачи данных между процессорами (время передачи в первом приближении прямо пропорционально длине пути). • Св |