А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 187
Текст из файла (страница 187)
11.2. Таким образом, удаленная память образует очередной уровень иерархии; ее обьем больше, но больше и время обращения к ней. Аналогично принципу проектирования иерархии памяти, который гласит, что быстрой памяти всегда меньше, чем медленной, можно сформулировать правило, что машины с быстрым межпроцессорным взаимодействием всегда имеют меньшее количество процессоров. Процессор Кош первого уровня Шине ияи иное внутреннее соеяинение Рнс.
11.2. Машины с распределенной памятью Существуег два варианта машин с распределенной памятью: машины с неравномерным доступом к памяти (попцп1Топп шешогу ассезз — МБМА) и машины с передачей сообщений. Архитектура ЬП)МА предоставляет программному обеспечению общее адресное пространство, позволяя процессорам взаимодействоватгн записывая и считывая общие ячейки памяти. В машинах с передачей сообщений адресные пространства процессоров различны, и процессоры взаимодействуют путем передачи сообщений друг другу.
Заметим, что хотя для машин 917 11.1. Фундаментальные концепции с общей памятью написание кода оказывается более простой задачей„ программное обеспечение в любом случае должно обеспечивать высокую локальность для эффективной работы машины. 11.1.2 Параллелизм в приложениях Для оценки работоспособности параллельного приложения мы будем использовать две метрики: степень параллелизми (рага11е!)яп сочегаяе), представляющую собой процент вычислений, которые могут выполняться параллельно, и зернистость параллелизма (йгапп!ап1у о( рага!!е11ап), представляющую собой количество вычислений, которые каждый процессор может выполнить без синхронизации или взаимодействия с другими процессорами. Одним из наиболее привлекательных приложений параллелизма являются циклы: цикл может состоять из многих итераций, и если они независимы одна от другой, то мы получаем неиссякаемый источник параллелизма.
Закон Амдалн Важность степени параллелизма кратко выражается законом Амдаля (Апи(аЫ), который гласит, что если Г" — доля распараллеленного кода и если распараллеленная версия выполняется на машине с р процессорами без накладных расходов на взаимодействие процессоров и организацию параллельных вычислений, то ускорение работы программы составляет (1 — () + (И ) Например, если половина вычислений остается последовательной, то скорость программы нельзя повысить больше чем в два раза, независимо от количества имеющихся процессоров. При наличии четырех процессоров программа ускорится в 1,6 раза. Даже если степень параллелизма — 90',4, то на четырех процессорах мы получим ускорение только в три раза, а при неограниченном количестве процессоров скорость работы программы возрастет в десять раз.
Зернистость параллелизма В идеале все вычисления приложения могут быть разделены на много независимых крупных задач, поскольку в таком случае их можно просто назначить разным процессорам. Одним из таких примеров является проект ВЕТ! (Яеагсп Гог Ехпа-Тепез!па1 1п!е!11яепсе — поиск внеземных цивилизаций), представляющий собой проект с использованием подключенных к Интернету домашних компьютеров для параллельного анализа различных частей данных, полученных с радиотелескопа. Каждое задание требует только небольшого количества входных данных и генерирует небольшие выходные данные, и может выполняться независимо от 918 Глава (1. Оптимизация параллелизма н локальности всех остальных.
В результате такие вычисления хорошо работают на множестве машин в Интернете, характеризующемся высокими задержками в линиях связи и низкой пропускной способностью. Большинство приложений требуют большего взаимодействия между процессорами, даже если они и допускают разделение на крупные подзадачи. Рассмотрим, например, %еЬ-сервер, ответственный за обслуживание большого количества, в основном, независимых запросов к базе данных. Такое приложение может быть запущено в многопроцессорной среде, в которой один поток реализует базу данных, а множество других обслуживает пользовательские запросы.
Другими примерами могут служить разработка лекарств и аэродинамическое моделирование, в которых результаты для множества различных параметров могут вычисляться независимо. Иногда вычисления даже для одного множества параметров моделирования могут выполняться так долго, что их желательно ускорить при по- моши распараллеливания. Если зернистость параллелизма снижается, требуются более мощная поддержка межпроцессорного взаимодействия и большие усилия при программировании таких приложений. Многие длительные научные и инженерные приложения с простыми управляющими структурами и большими множествами данных могут быть распараллелены более легко, чем упоминавшиеся ранее приложения.
В этой главе мы, в первую очередь, сосредоточимся на методах, применимых к численным приложениям, в частности к программам, затрачивающим ббльшую часть времени на работу с данными в многомерных массивах. 11.1.3 Параллелизм на уровне циклов Основным объектом распараллеливания служат циклы, в особенности в приложениях, использующих массивы. Долго работающие приложения, как правило, тяготеют к большим массивам данных, приводящим к циклам с множеством итераций, по одной для каждого элемента массива.
При этом не такая уж редкость массивы, в которых итерации не зависят одна от другой. Можно разделить большое количество итераций в таких циклах между процессорами. Если количество вычислений, выполняемых в каждой итерации, примерно одинаковое, простое равномерное разделение итераций по процессорам обеспечит максимальную степень параллелизма. Исключительно простой пример 11.1 демонстрирует возможность использования преимуществ параллелизма на уровне цикла. Пример 11.1. Цикл аког(з = 0; ъ < и; ъ++) ( 2[з.1 = Х[х( — У[э.]з Е[з( = Е[л] * Е[з(з 919 !1.!.
Фундаментальные концепции Параллелизм на уровне задач Можно найти параллельность и вне итераций цикла. Например, можно назначить двум процессорам вызовы двух разных функций или выполнения двух независимых циклов. Такой параллелизм известен как параллелизм ни уровне задач.
Уровень задач не такой привлекательный источник парачлелизма, как уровень цикла. Причина этого в том, что количество независимых задач в каждой программе постоянно и не изменяется с изменением размера данных, как в случае итераций в типичном цикле. Кроме того, в общем случае задачи имеют разные размеры, так что очень трудно все время загружать все процессоры системы.
вычисляет квадраты разностей между элементами векторов Х и 1' и сохраняет их в векторе Я. Цикл распараллеливаем, поскольку каждая его итерация обращается к различным множествам данных. Можно выполнить цикл на компьютере с М процессорами, присваивая каждому процессору уникальный идентификатор р = = О, 1,..., М вЂ” 1 и выполняя на каждом процессоре один и тот же код Ь = сех).(п/М)! Гол(з = Ь*р; з < а!зп(п,Ь*(Р+).))' з++) Е[з] = Х[з] — у[з]; Е[з] = Е[з] * Е[з1; Мы равномерно разделяем итерации цикла между процессорами; р-й процессор получает для выполнения р-ю "полосу" итераций. Заметим, что количество итераций может не быть кратно М, так что мы не можем гарантировать, что последний процессор не достигнет конца исходного цикла за минимальное количество операций. и Параллельный код, приведенный в примере 11.1, представляет собой КРМ[З- программу (йпя!е Ргоагапз Мн!йр!е [Уа!а — одна программа, много данных).
Один и тот же код выполняется всеми процессорами, но для каждого процессора этот код параметризован уникальным идентификатором процессора, так что различные процессоры могут выполнять различные действия. Обычно один процессор, известный как ведущий (таз(ег), выполняет все последовательные части вычислений. При достижении параллелизованной части кода ведущий процессор активирует все ведомые (з!аче) процессоры. Все вместе процессоры выполняют параллелизованную часть кода, после чего участвуют в барьерной синхронизапии (Ьагпег зупс)поп(ха!(оп).
Все операции, выполняемые процессором до входа 920 Глава 11. Оптимизация параллелизма и локальности в барьер синхронизации, гарантированно завершаются до того, как любому другому процессору будет позволено покинуть этот барьер и выполнить операцию, находящуюся за ним. Если параллелизуются только небольшие циклы наподобие приведенного в примере 11.1, то получающийся в результате код имеет невысокую степень параллелизма и относительно малую его зернистость. Предпочтительно параллелизовать внешние циклы программы, поскольку это существенно повышает зернистость параллелизма. Рассмотрим, например, приложение двумерного быстрого преобразования Фурье (БПФ), работающего с массивом данных размером п х и. Такая программа выполняет п БПФ каждой строки данных, затем — и БПФ столбцов.
Предпочтительнее назначить каждому из и независимых БПФ свой процессор, чем использовать несколько процессоров для выполнения одного БПФ. Такой код легче написать, степень параллельности алгоритма окажется равной !00',м и код будет иметь хорошую локальность, поскольку во время вычисления БПФ взаимодействие процессоров не потребуется. Во многих приложениях нет параллелизуемых больших внутренних циклов. Однако зачастую во времени выполнения таких приложений доминирует время, затраченное на работу ядер (кегпе1а), которые могут состоять из сотен строк кода с циклами разной степени вложенности. Иногда оказывается возможным реорганизовать вычисления в ядре и разбить его на мазозависимые модули, сосредоточиваясь, в первую очередь, на локальности. 11.1.4 Локальность данных Существует два несколько отличающихся понятия локальности данных, которые необходимы при рассмотрении параллелизма программ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
