Транскрипт

1 Часть 3. Методы параллельных вычислений 6. Принципы разработки параллельных методов 6. Принципы разработки параллельных методов Моделирование параллельных программ Этапы разработки параллельных алгоритмов Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование набора подзадач Распределение подзадач между процессорами Параллельное решение гравитационной задачи N тел Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности параллельных вычислений Краткий обзор раздела Обзор литературы Контрольные вопросы Задачи и упражнения Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную проблему. Для снижения сложности рассматриваемой темы оставим в стороне математические аспекты разработки и доказательства сходимости алгоритмов эти вопросы в той или иной степени изучаются в ряде "классических" математических учебных курсов. Здесь же мы будем полагать, что вычислительные схемы решения задач, рассматриваемых далее в качестве примеров, уже известны 1). С учетом высказанных предположений последующие действия для определения эффективных способов организации параллельных вычислений могут состоять в следующем: Выполнить анализ имеющихся вычислительных схем и осуществить их разделение (декомпозицию) на части (подзадачи), которые могут быть реализованы в значительной степени независимо друг от друга, Выделить для сформированного набора подзадач информационные взаимодействия, которые должны осуществляться в ходе решения исходной поставленной задачи, Определить необходимую (или доступную) для решения задачи вычислительную систему и выполнить распределение имеющего набора подзадач между процессорами системы. При самом общем рассмотрении понятно, что объем вычислений для каждого используемого процессора должен быть примерно одинаков это позволит обеспечить равномерную вычислительную загрузку (балансировку) процессоров. Кроме того, также понятно, что распределение подзадач между процессорами должно быть выполнено таким образом, чтобы наличие информационных связей (коммуникационных взаимодействий) между подзадачами было минимальным. 1) Несмотря на то, что для многих научно-технических задач на самом деле известны не только последовательные, но и параллельные методы решения, данное предположение является, конечно, очень сильным, поскольку для новых возникающих задач, требующих для своего решения большого объема вычислений, процесс разработки алгоритмов составляет существенную часть всех выполняемых работ.

2 Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование подзадач Распределение подзадач между процессорами Рис Общая схема разработки параллельных алгоритмов После выполнения всех перечисленных этапов проектирования можно оценить эффективность разрабатываемых параллельных методов для этого обычно определяются значения показателей качества порождаемых параллельных вычислений (ускорение, эффективность, масштабируемость). По результатам проведенного анализа может оказаться необходимым повторение отдельных (в предельном случае всех) этапов разработки следует отметить, что возврат к предшествующим шагам разработки может происходить на любой стадии проектирования параллельных вычислительных схем. В этом отношении часто выполняемым дополнительным действием в приведенной выше схеме проектирования является корректировка состава сформированного множества задач после определения имеющегося количества процессоров подзадачи могу быть укрупнены (агрегированы) при наличии малого числа процессоров или, наоборот, детализированы в противном случае. В целом, данные действия могут быть определены как масштабирование разрабатываемого алгоритма и выделены в качестве отдельного этапа проектирования параллельных вычислений. Для применения получаемого в конечном итоге параллельного метода необходимо выполнить разработку программ для решения сформированного набора подзадач и разместить разработанные программы по процессорам в соответствии с выбранной схемой распределения подзадач. Для проведения вычислений программы запускаются на выполнение (программы на стадии выполнения обычно именуются процессами), для реализации информационных взаимодействий программы должны иметь в своем распоряжении средства обмена данными (каналы передачи сообщений). Следует отметить, что каждый процессор обычно выделяется для решения одной единственной подзадачи, однако при наличии большого количества подзадач или использовании ограниченного числа процессоров это правило может не соблюдаться и, в результате, на процессорах может выполняться одновременно несколько программ (процессов). В частности, при разработке и начальной проверке параллельной программы для выполнения всех процессов может использоваться один процессор (при расположении на одном процессоре процессы выполняются в режиме распределения времени). Рассмотрев внимательно разработанную схему проектирования и реализации параллельных вычислений, можно отметить, что данный подход в значительной степени ориентирован на вычислительные системы с распределенной памятью, когда необходимые информационные взаимодействия реализуются при помощи передачи сообщений по каналам связи между процессорами. Тем не менее, данная схема может быть использована без потери какой-либо эффективности параллельных вычислений и для разработки параллельных методов для систем с общей памятью в этом случае механизмы передачи сообщений для обеспечения информационных взаимодействий должны быть заменены операциями доступа к общим (разделяемым) переменным Моделирование параллельных программ Рассмотренная схема проектирования и реализации параллельных вычислений дает способ понимания параллельных алгоритмов и программ. На стадии проектирования параллельный метод может быть представлен в виде графа "подзадачи сообщения", который представляет собой не что иное, как укрупненное (агрегированное) представление графа информационных зависимостей (графа "операции-операнды" см. раздел 2). Аналогично на стадии выполнения для описания параллельной программы может быть использована модель в виде графа "процессы каналы", в которой вместо подзадач используется понятие процессов, а информационные зависимости заменяются каналами 2

3 передачи сообщений. В дополнение, на этой модели может быть показано распределение процессов по процессорам вычислительной системы, если количество подзадач превышает число процессоров см. рис процесс - канал - операции приема (передачи) - входные (выходные) каналы для взаимодействия процессов Рис Модель параллельной программы в виде графа "процессы-каналы" Использование двух моделей параллельных вычислений 2) позволяет лучше разделить проблемы, которые проявляются при разработке параллельных методов. Первая модель граф "подзадачи - сообщения" позволяет сосредоточиться на вопросах выделения подзадач одинаковой вычислительной сложности, обеспечивая при этом низкий уровень информационной зависимости между подзадачами. Вторая модель граф "процессы каналы" концентрирует внимание на вопросах распределения подзадач по процессорам, обеспечивая еще одну возможность снижения трудоемкости информационных взаимодействий между подзадачами за счет размещения на одних и тех же процессорах интенсивно взаимодействующих процессов. Кроме того, эта модель позволяет лучше анализировать эффективность разработанного параллельного метода и обеспечивает возможность более адекватного описания процесса выполнения параллельных вычислений. Дадим дополнительные пояснения для используемых понятий в модели "процессы-каналы": Под процессом в рамках данного учебного материала будем понимать выполняемую на процессоре программу, которая использует для свой работы часть локальной памяти процессора и которая содержит ряд операций приема/передачи данных для организации информационного взаимодействия между выполняемыми процессами параллельной программы, Канал передачи данных с логической точки зрения может рассматриваться как очередь сообщений, в которую один или несколько процессов могут отправлять пересылаемые данные и из которой процесс-адресат может извлекать сообщения, отправляемые другими процессами. В общем случае, можно считать, что каналы возникают динамически в момент выполнения первой операции приема/передачи с каналом. По степени общности, канал может соответствовать одной или нескольким командам приема данных процесса-получателя; аналогично при передаче сообщений канал может использоваться одной или несколькими командами передачи данных одного или нескольких процессов. Для снижения сложности моделирования и анализа параллельных методов будем предполагать, что емкость каналов является неограниченной и, как результат, операции передачи данных выполняются практически без задержек простым копированием сообщений в канал. С другой стороны, операции приема сообщений могут приводить к задержкам (блокировкам), если запрашиваемые из канала данные еще не были отправлены процессами-источниками сообщений. Следует отметить важное достоинство рассмотренной модели "процессы-каналы" в этой модели проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и 2) В Foster (1995) рассматривается только одна модель модель "задача-канал" для описания параллельных вычислений, которая занимает некоторое промежуточное положение по сравнению с изложенными здесь моделями. Так, в модели "задачаканал" не учитывается возможность использования одного процессора для решения нескольких подзадач одновременно. 3

4 действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ Этапы разработки параллельных алгоритмов Рассмотрим более подробно изложенную выше методику разработки параллельных алгоритмов. В значительной степени данная методика опирается на подход, впервые рассмотренный в Foster (1995), и, как отмечалось ранее, включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы (см. рис. 6.1). Для демонстрации приводимых рекомендаций далее будет использоваться учебная задача поиска максимального значения среди элементов матрицы A (такая задача возникает, например, при численном решении систем линейных уравнений для определения ведущего элемента метода Гаусса): y = max a. 1 i, j N i j Такая задача носит полностью иллюстративный характер, и после рассмотрения этапов разработки в оставшейся части раздела будет приведен более полный пример использования данной методики для разработки параллельных алгоритмов. Кроме того, данная схема разработки будет применена и при изложении всех далее рассматриваемых методов параллельных вычислений Разделение вычислений на независимые части Выбор способа разделения вычислений на независимые части основывается на анализе вычислительной схемы решения исходной задачи. Требования, которым должен удовлетворять выбираемый подход, обычно состоят в обеспечении равного объема вычислений в выделяемых подзадачах и минимума информационных зависимостей между этими подзадачами (при прочих равных условиях нужно отдавать предпочтение редким операциям передачи большего размера сообщений по сравнению с частыми пересылками данных небольшого объема). В общем случае, проведение анализа и выделение задач представляет собой достаточно сложную проблему ситуацию помогает разрешить существование двух часто встречающихся типов вычислительных схем: а) б) Рис Разделение данных для матрицы A: а) ленточная схема, б) блочная схема Для большого класса задач вычисления сводятся к выполнению однотипной обработки элемент элементов большого набора данных к такому виду задач относятся, например, матричные вычисления, численные методы решения уравнений в частных производных и др. В этом случае говорят, что существует параллелизм по данным, и выделение подзадач сводится к разделению имеющихся данных. Так, например, для нашей учебной задачи поиска максимального значения при формировании подзадач исходная матрица A может быть разделена на отдельные строки (или последовательные группы строк) ленточная схема разделения данных (см. рис. 6.3) или на прямоугольные наборы элементов блочная схема разделения данных. Для большого количества решаемых задач разделение вычислений по данным приводит к порождению одно-, двух- и трех- мерных наборов подзадач, для которых информационные связи существуют только между ближайшими соседями (такие схемы обычно именуются сетками или решетками), 4

5 Рис Регулярные одно-, двух- и трех- мерные структуры базовых подзадач после декомпозиции данных Для другой части задач вычисления могут состоять в выполнении разных операций над одним и тем же набором данных в этом случае говорят о существовании функционального параллелизма (в качестве примеров можно привести задачи обработки последовательности запросов к информационным базам данных, вычисления с одновременным применением разных алгоритмов расчета и т.п.). Очень часто функциональная декомпозиция может быть использована для организации конвейерной обработки данных (так, например, при выполнении каких-либо преобразований данных вычисления могут быть сведены к функциональной последовательности ввода, обработки и сохранения данных). Важный вопрос при выделении подзадач состоит в выборе нужного уровня декомпозиции вычислений. Формирование максимально возможного количества подзадач обеспечивает использование предельно достижимого уровня параллелизма решаемой задачи, однако затрудняет анализ параллельных вычислений. Использование при декомпозиции вычислений только достаточно "крупных" подзадач приводит к ясной схеме параллельных вычислений, однако может затруднить эффективное использование достаточно большого количества процессоров. Возможное разумное сочетание этих двух подходов может состоять в использовании в качестве конструктивных элементов декомпозиции только тех подзадач, для которых методы параллельных вычислений являются известными. Так, например, при анализе задачи матричного умножения в качестве подзадач можно использовать методы скалярного произведения векторов или алгоритмы матрично-векторного произведения. Подобный промежуточный способ декомпозиции вычислений позволит обеспечить и простоту представления вычислительных схем, и эффективность параллельных расчетов. Выбираемые подзадачи при таком подходе будем именовать далее базовыми, которые могут быть элементарными (неделимыми), если не допускают дальнейшего разделения, или составными в противном случае. Для рассматриваемой учебной задачи достаточный уровень декомпозиции может состоять, например, в разделении матрицы A на множество отдельных строк и получении на этой основе набора подзадач поиска максимальных значений в отдельных строках; порождаемая при этом структура информационных связей соответствует линейному графу см. рис Для оценки корректности этапа разделения вычислений на независимые части можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Выполненная декомпозиция не увеличивает объем вычислений и необходимый объем памяти? Возможна ли при выбранном способе декомпозиции равномерная загрузка всех имеющихся процессоров? Достаточно ли выделенных частей процесса вычислений для эффективной загрузки имеющихся процессоров (с учетом возможности увеличения их количества)? Выделение информационных зависимостей При наличии вычислительной схемы решения задачи после выделения базовых подзадач определение информационных зависимостей между подзадачами обычно не вызывает больших затруднений. При этом, однако, следует отметить, что на самом деле этапы выделения подзадач и информационных зависимостей достаточно сложно поддаются разделению. Выделение подзадач должно происходить с учетом возникающих информационных связей; после анализа объема и частоты необходимых информационных обменов между подзадачами может потребоваться повторение этапа разделения вычислений. При проведении анализа информационных зависимостей между подзадачами следует различать (предпочтительные формы информационного взаимодействия выделены подчеркиванием): Локальные и глобальные схемы передачи данных для локальных схем передачи данных в каждый момент времени выполняются только между небольшим числом подзадач (располагаемых, как 5

6 правило, на соседних процессорах), для глобальных операций передачи данных в процессе коммуникации принимают участие все подзадачи, Структурные и произвольные способы взаимодействия для структурных способов организация взаимодействий приводит к формированию некоторых стандартных схем коммуникации (например, в виде кольца, прямоугольной решетки и т.д.), для произвольных структур взаимодействия схема выполняемых операций передач данных не носит характер однородности, Статические или динамические схемы передачи данных для статических схем моменты и участники информационного взаимодействия фиксируются на этапах проектирования и разработки параллельных программ, для динамического варианта взаимодействия структура операции передачи данных определяется в ходе выполняемых вычислений, Синхронные и асинхронные способы взаимодействия для синхронных способов операции передачи данных выполняются только при готовности всех участников взаимодействия и завершаются только после полного окончания всех коммуникационных действий, при асинхронном выполнении операций участники взаимодействия могут не дожидаться полного завершения действий по передаче данных. Для представленных способов взаимодействия достаточно сложно выделить предпочтительные формы организации передачи данных: синхронный вариант, как правило, более прост для использования, в то время как асинхронный способ часто позволяет существенно снизить временные задержки, вызванные операциями информационного взаимодействия. Как уже отмечалось в предыдущем пункте, для учебной задачи поиска максимального значения при использовании в качестве базовых элементов подзадач поиска максимальных значений в отдельных строках исходной матрицы A структура информационных связей имеет вид, представленный на рис Рис Структура информационных связей учебной задачи Как и ранее, для оценки правильности этапа выделения информационных зависимостей можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Соответствует ли вычислительная сложность подзадач интенсивности их информационных взаимодействий? Является ли одинаковой интенсивность информационных взаимодействий для разных подзадач? Является ли схема информационного взаимодействия локальной? Не препятствует ли выявленная информационная зависимость параллельному решению подзадач? Масштабирование набора подзадач Масштабирование разработанной вычислительной схемы параллельных вычислений проводится в случае, если количество имеющихся подзадач отличается от числа планируемых к использованию процессоров. Для сокращения количества подзадач необходимо выполнить укрупнение (агрегацию) вычислений. Применяемые здесь правила совпадают с рекомендациями начального этапа выделения подзадач определяемые подзадачи, как и ранее, должны иметь одинаковую вычислительную сложность, а объем и интенсивность информационных взаимодействий между подзадачами должны оставаться на минимально-возможном уровне. Как результат, первыми претендентами на объединение являются подзадачи с высокой степенью информационной взаимозависимости. При недостаточном количестве имеющегося набора подзадач для загрузки всех доступных к использованию процессоров необходимо выполнить детализацию (декомпозицию) вычислений. Как 6

7 правило, проведение подобной декомпозиции не вызывает каких-либо затруднений, если для базовых задач методы параллельных вычислений являются известными. Выполнение этапа масштабирования вычислений должно свестись, в конечном итоге, к разработке правил агрегации и декомпозиции подзадач, которые должны параметрически зависеть от числа процессоров, применяемых для вычислений. Для рассматриваемой учебной задачи поиска максимального значения агрегация вычислений может состоять в объединении отдельных строк в группы (ленточная схема разделения матрицы см. рис. 6.3а), при декомпозиции подзадач строки исходной матрицы A могут разбиваться на несколько частей (блоков). Список контрольных вопросов, предложенный в Foster (1995) для оценки правильности этапа масштабирования, выглядит следующим образом: Не ухудшится ли локальность вычислений после масштабирования имеющегося набора подзадач? Имеют ли подзадачи после масштабирования одинаковую вычислительную и коммуникационную сложность? Соответствует ли количество задач числу имеющихся процессоров? Зависят ли параметрически правила масштабирования от количества процессоров? Распределение подзадач между процессорами Распределение подзадач между процессорами является завершающим этапом разработки параллельного метода. Надо отметить, что управление распределением нагрузки для процессоров возможно только для вычислительных систем с распределенной памятью, для мультипроцессоров (систем с общей памятью) распределение нагрузки обычно выполняется операционной системой автоматически. Кроме того, данный этап распределения подзадач между процессорами является избыточным, если количество подзадач совпадает с числом имеющихся процессоров, а топология сети передачи данных вычислительной системы представляет собой полный граф (т.е., все процессоры связаны между собой прямыми линиями связи). Основной показатель успешности выполнения данного этапа эффективность использования процессоров, определяемая как относительная доля времени, в течение которого процессоры использовались для вычислений, связанных с решением исходной задачи. Пути достижения хороших результатов в этом направлении остаются прежними как и ранее, необходимо обеспечить равномерное распределение вычислительной нагрузки между процессорами и минимизировать количество сообщений, передаваемых между процессорами. Точно так же, как и на предшествующих этапах проектирования, оптимальное решение проблемы распределения подзадач между процессорами основывается на анализе информационной связности графа "подзадачи - сообщения". Так, в частности, подзадачи, между которыми имеются информационные взаимодействия, целесообразно размещать на процессорах, между которыми существуют прямые линии передачи данных. Следует отметить, что требование минимизации информационных обменов между процессорами может противоречить условию равномерной загрузки процессов. Так, мы можем разместить все подзадачи на одном процессоре и полностью устранить межпроцессорную передачу сообщений, однако, понятно, загрузка большинства процессоров в этом случае будет минимальной. Для нашей учебной задачи поиска максимального значения распределение подзадач между процессорами не вызывает каких-либо затруднений достаточно лишь обеспечить размещение подзадач, между которыми имеются информационные связи, на процессорах, для которых существуют прямые каналы передачи данных. Поскольку структура информационной связей учебной задачи имеет вид линейного графа, выполнение данного требования может быть обеспечено практически при любой топологии сети вычислительной системы. Решение вопросов балансировки вычислительной нагрузки значительно усложняется, если схема вычислений может изменяться в ходе решения задачи. Причиной этого могут быть, например, неоднородные сетки при решении уравнений в частных производных, разреженность матриц и т.п. 3). Кроме того, используемые на этапах проектирования оценки вычислительной сложности решения подзадач могут иметь приближенный характер и, наконец, количество подзадач может изменяться в ходе вычислений. В таких ситуациях может потребоваться перераспределение базовых подзадач между 3) Можно отметить, что даже для нашей простой учебной задачи может наблюдаться различная вычислительная сложность сформированных базовых задач. Так, например, количество операций при поиске максимального значения для строки, в которой максимальное значение имеет первый элемент, и строки, в которой значения являются упорядоченными по возрастанию, будет различаться в два раза. 7

8 процессорами уже непосредственно в процессе выполнения параллельной программы (или, как обычно говорят, придется выполнить динамическую балансировку вычислительной нагрузки). Данные вопросы являются одними из наиболее сложных (и наиболее интересных) в области параллельных вычислений к сожалению, рассмотрение данных вопросов выходит за рамки данного учебного материала (дополнительная информация может быть получена, например, в Buyya (1999) и Wilkinson and Allen (1999)). В качестве примера дадим краткую характеристику широко используемого способа динамического управления распределением вычислительной нагрузки, обычно именуемого схемой "менеджер - исполнитель" (manager-worker scheme). При использовании данного подхода предполагается, что подзадачи могут возникать и завершаться в ходе вычислений, при этом информационные взаимодействия между подзадачами либо полностью отсутствует, либо минимальны. В соответствии с рассматриваемой схемой для управления распределением нагрузки в системе выделяется отдельный процессор-менеджер, которому доступна информация обо всех имеющихся подзадачах. Остальные процессоры системы являются исполнителями, которые для получения вычислительной нагрузки обращаются к процессору-менеджеру. Порождаемые в ходе вычислений новые подзадачи передаются обратно процессору-менеджеру и могут быть получены для решения при последующих обращениях процессоров-исполнителей. Завершение вычислений происходит в момент, когда процессорыисполнители завершили решение всех переданных им подзадач, а процессор-менеджер не имеет какихлибо вычислительных работ для выполнения. Предложенный в Foster (1995) перечень контрольных вопросов для проверки этапа распределения подзадач состоит в следующем: Не приводит ли распределение нескольких задач на один процессор к росту дополнительных вычислительных затрат? Существует ли необходимость динамической балансировки вычислений? Не является ли процессор-менеджер "узким" местом при использовании схемы "менеджерисполнитель"? 6.3. Параллельное решение гравитационной задачи N тел Многие вычислительные задачи в области физики сводятся к операциям обработки данных для каждой пары объектов имеющейся физической системы. Такой задачей является, в частности, проблема, широко известная в литературе как гравитационная задача N тел (или просто задача N тел) см., например, Andrews (2000) В самом общем виде, задача может быть описана следующим образом. Пусть дано большое количество тел (планет, звезд и т.д.), для каждого из которых известна масса, начальное положение и скорость. Под действием гравитации положение тел меняется, и требуемое решение задачи состоит в моделировании динамики изменения системы N тел на протяжении некоторого задаваемого интервала времени. Для проведения такого моделирования заданный интервал времени обычно разбивается на временные отрезки небольшой длительности и далее на каждом шаге моделирования вычисляются силы, действующие на каждое тело, а затем обновляются скорости и положения тел. Очевидный алгоритм решения задачи N тел состоит в рассмотрении на каждом шаге моделирования всех пар объектов физической системы и выполнении для каждой получаемой пары всех необходимых расчетов. Как результат, при таком подходе время выполнения одной итерации моделирования будет составлять 4) T = τ N(N 1) / 2, 1 где τ есть время перевычисления параметров одной пары тел. Как следует из приведенного описания, вычислительная схема рассмотренного алгоритма является сравнительно простой, что позволяет использовать задачу N тел в качестве еще одной наглядной демонстрации применения методики разработки параллельных алгоритмов. 4) Следует отметить, что для решения задачи N тел существует и более эффективные последовательные алгоритмы, однако их изучение может потребовать достаточно больших усилий. С учетом данного обстоятельства для дальнейшего рассмотрения выбирается именно данный "очевидный" (но не самый быстрый) метод, хотя, в общем случае, безусловно, для распараллеливания следует выбирать наилучшие схемы выполнения расчетов. 8

9 Разделение вычислений на независимые части Выбор способа разделения вычислений не вызывает каких-либо затруднений - очевидный подход состоит в выборе в качестве базовой подзадачи всего набора вычислений, связанных с обработкой данных одного какого-либо тела физической системы Выделение информационных зависимостей Выполнение вычислений, связанных с каждой подзадачей, становится возможным только в случае, когда в подзадачах имеются данные (положение и скорости передвижения) обо всех телах имеющейся физической системы. Как результат, перед началом каждой итерации моделирования каждая подзадача должна получить все необходимые сведения от всех других подзадач системы. Такая процедура передачи данных, как отмечалось в разделе 3, именуется операцией сбора данных (single-node gather). В рассматриваемом алгоритме данная операция должна быть выполнена для каждой подзадачи такой вариант передачи данных обычно именуется как операция обобщенного сбора данных (multi-node gather or all gather). Определение требований к необходимым результатам информационного обмена не приводит к однозначному установлению нужного информационного обмена между подзадачами достижение требуемых результатов может быть обеспечено при помощи разных алгоритмов выполнения операции обобщенного сбора данных. Наиболее простой способ выполнения необходимого информационного обмена состоит в реализации последовательности шагов, на каждом из которых все имеющиеся подзадачи разбиваются попарно и обмен данными осуществляется между подзадачами образовавшихся пар. При надлежащей организации попарного разделения подзадач (N-1)-кратное повторение описанных действий приведет к полной реализации требуемой операции сбора данных. Рассмотренный выше метод организации информационного обмена является достаточно трудоемким для сбора всех необходимых данных требуется (N-1) итераций, на каждой из которых выполняется одновременно (N/2) операций передачи данных. Для сокращения требуемого количества итераций можно обратить внимание на факт, что после выполнения первого шага операции сбора данных подзадачи будут уже содержать не только свои данные, но и данные подзадач, с которыми они образовывали пары. Как результат, на второй итерации сбора данных можно будет образовывать пары подзадач для обмена данными сразу о двух телах физической системы тем самым, после завершения второй итерации каждая подзадача будет содержать сведения о четырех телах системы и т.д. Как можно заметить, данный способ реализации обменов позволяет завершить необходимую процедуру за log 2 N итераций. Следует отметить, что при этом объем пересылаемых данных в каждой операции обмена удваивается от итерации к итерации на первой итерации между подзадачами пересылаются данные об одном теле системы, на второй итерации о двух телах и т.д. Использование рассмотренного способа реализации операции обобщенного сбора данных приводит к определению структуры информационных связей между подзадачами в виде N-мерного гиперкуба Масштабирование и распределение подзадач по процессорам Как правило, число тел физической системы N значительно превышает количество процессоров p. Как результат, рассмотренные ранее подзадачи следует укрупнить, объединив в рамках одной подзадачи вычисления для группы (N/p) тел. После проведения подобной агрегации число подзадач и количество процессоров будет совпадать, и при распределении подзадач между процессорами останется лишь обеспечить наличие прямых коммуникационных линий между процессорами с подзадачами, между которыми имеются информационные обмены при выполнении операции сбора данных Анализ эффективности параллельных вычислений Оценим эффективность разработанных способов параллельных вычислений для решения задачи N тел. Поскольку предложенные варианты отличаются только методами выполнения информационных обменов, для сравнения подходов достаточно определить длительность операции обобщенного сбора данных. Используем для оценки времени передачи сообщений модель, предложенную Хокни (см. раздел 3), тогда длительность выполнения операции сбора данных для первого варианта параллельных вычислений может быть выражена как 1 T p (comm) = (p 1)(α + m (N / p) / β), где α, β есть параметры модели Хокни (латентность и пропускная способность сети передачи данных), а m задает объем пересылаемых данных для одного тела физической системы. 9

10 Для второго способа информационного обмена, как уже отмечалось ранее, объем пересылаемых данных на разных итерациях операции сбора данных различается. На первой итерации объем пересылаемых сообщений составляет (mn/p), на второй итерации этот объем увеличивается вдвое и оказывается равным 2(mN/p) и т.д. В общем случае, для итерации с номером i объем сообщений оценивается как 2 i-1 (mn/p). Как результат, длительность выполнения операции сбора данных в этом случае может быть определена при помощи следующего выражения T 2 p log p i= 1 i 1 (comm) = (α + 2 m(N / p) / β) = α log p + m (N / p)(p 1) / β. Сравнение полученных выражений показывает, что второй разработанный способ параллельных вычислений имеет существенно более высокую эффективность, несет меньшие коммуникационные затраты и допускает лучшую масштабируемость при увеличении количества используемых процессоров Краткий обзор раздела В разделе была рассмотрена методика разработки параллельных алгоритмов, предложенная в Foster (1995). Данная методика включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы. При применении методики предполагается, что вычислительная схема решения рассматриваемой задачи уже является известной. Основные требования, которые должны быть обеспечены при разработке параллельных алгоритмов, состоят в обеспечении равномерной загрузки процессоров при низком информационном взаимодействии сформированного множества подзадач. Для описания получаемых в ходе разработки вычислительных параллельных схем рассмотрены две модели. Первая из них модель "подзадачи-сообщения" может быть использована на стадии проектирования параллельных алгоритмов, вторая модель "процессы-каналы" может быть применена на стадии реализации методов в виде параллельных программ. В завершение раздела показывается применение рассмотренной методики разработки параллельных алгоритмов на примере решения гравитационной задачи N тел Обзор литературы Рассмотренная в разделе методика разработки параллельных алгоритмов впервые была предложена в Foster (1995). В этой работе изложение методики проводится более детально; кроме того, в работе содержится несколько примеров использования методики для разработки параллельных методов для решения ряда вычислительных задач. Полезной при рассмотрении вопросов проектирования и разработки параллельных алгоритмов может оказаться также работа Quinn (2004). Гравитационная задача N тел более подробно рассматривается в Andrews (2000) Контрольные вопросы 1. В чем состоят исходные предположения для возможности применения рассмотренной в разделе методики разработки параллельных алгоритмов? 2. Каковы основные этапы проектирования и разработки методов параллельных вычислений? 3. Как определяется модель "подзадачи-сообщения"? 4. Как определяется модель "процессы-каналы"? 5. Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов? 6. В чем состоят основные действия на этапе выделения подзадач? 7. Каковы основные действия на этапе определения информационных зависимостей? 8. В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач? 9. В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы? 10. Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер - исполнитель"? 11. Какой метод параллельных вычислений был разработан для решения гравитационной задачи N тел? 10

11 12. Какой способ выполнения операции обобщенного сбора данных является более эффективным? 6.7. Задачи и упражнения 1. Выполните реализацию каскадной схемы вычисления суммы последовательности числовых значений (см. раздел 2) и сравните время выполнения выполненной реализации и функции MPI_Bcast библиотеки MPI. 2. Выполните реализацию рассмотренных способов выполнения обобщенной операции сбора данных и сравните время их выполнения. Сопоставьте получаемые временные характеристики с имеющими теоретическими оценками. Выполните сравнение со временем выполнения функции MPI_Allgather библиотеки MPI. 3. Разработайте схему параллельных вычислений, используя рассмотренную в разделе методику проектирования и разработки параллельных методов: для задачи поиска максимального значения среди минимальных элементов строк матрицы (такая задача имеет место для решения матричных игр) y = max min a, 1 i N 1 j N ij (обратите особое внимание на ситуацию, когда число процессоров превышает порядок матрицы, т.е. p>n), для задачи вычисления определенного интеграла с использованием метода прямоугольников b N 1 y = f (x) dx h fi, a i= 0 f i = f (x), x = i h, h = (b a) / N. i i (описание методов интегрирования дано, например, в Kahaner, Moler and Nash (1988)) 4. Выполните реализацию разработанных параллельных методов для задач п Разработайте схему параллельных вычислений для задачи умножения матрицы на вектор, используя рассмотренную в разделе методику проектирования и разработки параллельных методов. Литература Andrews, G. R. (2000). Foundations of Multithreaded, Parallel, and Distributed Programming.. Reading, MA: Addison-Wesley (русский перевод Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом "Вильямс", 2003) Bertsekas, D.P., Tsitsiklis, J.N. (1989) Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Ed.) (1999). High Performance Cluster Computing. Volume1: Architectures and Systems. Volume 2: Programming and Applications. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Numerical Methods and Software. Prentice Hall (русский перевод Каханер Д., Моулер Л., Нэш С. Численные методы и программное обеспечение. М.: Мир, 2001) Foster, I. (1995). Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. New York, NY: McGraw-Hill. Wilkinson, B., Allen, M. (1999). Parallel programming. Prenrice Hall. 11

ГЛАВА 3 ПРИНЦИПЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ МЕТОДОВ Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную

Методы и алгоритмы параллельных вычислений Проектирование параллельных алгоритмов Кулаков Кирилл Александрович 2016 Петрозаводск Цели проектирования Балансировка нагрузки Масштабируемость Эффективность

Высокопроизводительные вычисления Лекция 2. Оценка максимально возможного параллелизма Обеспечение наилучших наилучшего ускорения S T = эффективности E = 1 возможно не для всех вычислительно T трудоемких

Лекции Лекция 1. Принципы построения параллельных вычислительных систем.............................. 23 Лекция 2. Моделирование и анализ параллельных вычислений...... 49 Лекция 3. Оценка коммуникационной

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 9. Параллельные

Проект комиссии Президента по модернизации и технологическому развитию экономики России «Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного

Тема: Распараллеливание выражений на примере арифметических Основные характеристики сложности и параллельности Что подлежит распараллеливанию? Задача (декомпозиция на подзадачи меньшей размерности) 2Метод

ВОПРОСЫ К ТЕСТУ ПО КУРСУ «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ» 1. Принципы построения параллельных вычислительных систем (15) 1. Схемы многопроцессорных систем с однородным и неоднородным доступом. 2.

Проектирование параллельных алгоритмов Лекция 3.1 29.03.2012 Т.Ю.Лымарь 1 3.1 Методология проектирования Разделение Установление связей Агрегирование Привязка к конкретной ЭВМ 29.03.2012 Т.Ю.Лымарь 2 3.1.1

Московский государственный университет им. М.В. Ломоносова История и методология параллельного программирования 9. Проектирование параллельных алгоритмов Разработчики: Л.Б. Соколинский, д.ф.-м.н., профессор

Федеральное агентство по образованию Нижегородский государственный университет им. Н.И. Лобачевского Национальный проект «Образование» Инновационная образовательная программа ННГУ. Образовательно-научный

Нижегородский государственный университет им. Н.И.Лобачевского Факультет вычислительной математики и кибернетики Кафедра математического обеспечения ЭВМ Лаборатория «Информационные технологии» ItLab Практический

Нижегородский государственный университет им. Н.И. Лобачевского - Национальный исследовательский университет - Лекция. Моделирование параллельных вычислений Гергель В.П., декан ВМК ННГУ Суперкомпьютерные

Алгоритмы для параллельных вычислительных систем 1. Типы параллелизма и методы синтеза параллельных алгоритмов. 2. Оценка эффективности параллельных алгоритмов. 1. Типы параллелизма и методы синтеза параллельных

СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Проект Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения

Оценка эффективности параллельных алгоритмов Лекция 4. 29.03.2012 Т.Ю. Лымарь 1 Введение Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:

Оценка эффективности параллельных алгоритмов Лекция 7 Т.Ю. Лымарь Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма: Оценка максимально возможного

ОСНОВНЫЕ ПОНЯТИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Параллельные вычисления (параллельная обработка) это использование нескольких или многих вычислительных устройств для одновременного выполнения разных частей одной

Математические модели и методы эффективного использования распределенных Цифровая вычислительных 3D-медицина систем Заголовок Результаты Подзаголовок в области компьютерной презентации графики и геометрического

УДК 681.5 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ЧИСЛЕННОГО РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ СОДУ Назарова И.А. Донецкий национальный технический университет Запропоновано паралельні чисельні алгоритми однокрокових методів для

ГЛАВА МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ При разработке параллельных алгоритмов решения сложных научнотехнических задач принципиальным моментом является анализ эффективности использования параллелизма,

1. Цели и задачи дисциплины: Суперкомпьютерные технологии и высокопроизводительные вычисления с использованием многопроцессорных вычислительных систем (МВС) становятся важным фактором научно-технического

Построение статистических моделей эффективности параллельных программ В.Н.Белецкий, С.А.Резникова, А.А.Чемерис Институт проблем моделирования в энергетике им. Г.Е.Пухова НАН Украины В статье рассмотрен

Информатика, управление, экономика ТРУДЫ МФТИ 2 Том 2, (5) УДК 59687+475 АС Хританков Московский физико-технический институт (государственный университет) Математическая модель характеристик производительности

АЛГОРИТМЫ БАЛАНСИРОВКИ ЗАГРУЗКИ ПРОЦЕССОРОВ ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ Бельков Д.В. Донецкий национальный технический университет, г. Донецк кафедра вычислительной математики и программирования

Вычислительные машины и программное обеспечение УДК 681.3.06 П.А. Павлов ЭФФЕКТИВНОСТЬ РАСПРЕДЁЛЕННЫХ ВЫЧИСЛЕНИЙ В МАСШТАБИРУЕМЫХ СИСТЕМАХ Масштабируемость (scalability) является одним из важнейших требований

Метод Ритца Выделяют два основных типа методов решения вариационных задач. К первому типу относятся методы, сводящие исходную задачу к решению дифференциальных уравнений. Эти методы очень хорошо развиты

ДИАГОНАЛЬНЫЙ МЕТОД УМНОЖЕНИЯ ПЛОТНЫХ МАТРИЦ Князькова Т.В., к.т.н., доцент, ВятГУ, г. Киров Сегодня с ростом мощностей вычислительных систем и современных суперкомпьютеров в широком спектре отраслей экономики

Введение 1 Глава 1 Задания 1.1 Разминка Первое задание на написание программы, использующей библиотеку MPI, одно на всех. 1.1.1 Вычисление числа π Вычислить число π по следующей формуле: 1 1 dx 4 1 + x

Лабораторная работа 4 Параллельная реализация метода Якоби в трехмерной области Цель работы: практическое освоение методов распараллеливания численных алгоритмов на регулярных сетках на примере реализации

Р. И. Идрисов ВРЕМЕННАЯ РАЗВЁРТКА ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ IR2 ЯЗЫКА SISAL 3.1 * На сегодняшний день увеличение вычислительных мощностей связано уже не с ускорением отдельного, а с добавлением дополнительных

Стратегия оптимизационного исследования и методы решения задач статической и динамической оптимизации технологических объектов Задачи статической оптимизации технологических объектов традиционно формулируются

ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ЗЕРНИСТЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ (Получение параллельных последовательностей зернистых вычислений) Приведем примеры получения параллельных алгоритмов, множества операций которых

ПАРАЛЛЕЛЬНЫЕ СВОЙСТВА АЛГОРИТМА Параллельные компьютеры (суперкомпьютеры) предназначены для быстрого решения больших задач. Чем мощнее компьютер, тем потенциально быстрее можно решить на нем задачу. Помимо

Каляев А.В. ПРОГРАММИРОВАНИЕ ВИРТУАЛЬНЫХ АРХИТЕКТУР И ОРГАНИЗАЦИЯ СТРУКТУРНО- ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ 1 Аннотация НИИ многопроцессорных вычислительных

Алгоритмы параллельного умножения матриц 1 Ленточные алгоритмы умножения матриц В данных алгоритмах матрицы разбиваются на непрерывные последовательности строк или столбцов (полосы). В простейшем случае

Распределение памяти Распределение памяти - это процесс, в результате которого отдельным элементам исходной программы ставятся в соответствие адрес, размер и атрибуты области памяти, необходимой для размещения

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ вида Численное решение нелинейных алгебраических или трансцендентных уравнений. заключается в нахождении значений

«Алгебра и геометрия» 13. Системы линейных алгебраических уравнений (СЛАУ). Теорема Кронекера-Капелли. Общее и частное решения СЛАУ. 14. Кривые второго порядка: эллипс, гипербола, парабола, и их свойства.

УДК 681.32 ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ КЛАСТЕРОВ РАБОЧИХ СТАНЦИЙ С ИСПОЛЬЗОВАНИЕМ ВЕЕРНОГО РАСПРЕДЕЛЕНИЯ ДОПОЛНИТЕЛЬНЫХ ЗАДАНИЙ НА ПРОСТАИВАЮЩЕЕ ОБОРУДОВАНИЕ 2012 В. М. Довгаль 1, С. Г. Спирин 2 1 профессор

Граф алгоритма и параллельные вычисления. Внутренний параллелизм программ. Лекция 3 12.04.2012 (С) Л.Б.Соколинский 1 3.1 Внутренний параллелизм Программа содержит параллелизм, если некоторые ее части (операторы)

МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П.КОРОЛЕВА

Лекция 5 5 Теорема существования и единственности решения задачи Коши для нормальной системы ОДУ Постановка задачи Задача Коши для нормальной системы ОДУ x = f (, x), () состоит в отыскании решения x =

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 2. Моделирование

Глава 5. МЕТОДЫ НЕЯВНОГО ПЕРЕБОРА Рассмотрим общую постановку задачи дискретной оптимизации mi f (x), (5.) x D в которой -мерный искомый вектор x принадлежит конечному множеству допустимых решений D.

ОГЛАВЛЕНИЕ Введение.... 12 Ч а с т ь I. Основы распараллеливания Лекция 1. О постановке задачи распараллеливания... 17 1.1. Введение.... 17 1.2. О некоторых вычислительных задачах.... 19 1.3. Численный

УДК 68.3.06 ОПРЕДЕЛЕНИЕ ЧИСЛА И ТОПОЛОГИИ РАЗМЕЩЕНИЯ СТАНЦИЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ А.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected] Рассмотрены задачи

ЭКСТРАПОЛЯЦИОННЫЕ БЛОЧНЫЕ ОДНОШАГОВЫЕ МЕТОДЫ ЧИСЛЕННОГО ВЫСОКОТОЧНОГО РЕШЕНИЯ ЗАДАЧИ КОШИ Кулаков В.В. Назарова И. А.Фельдман Л.П. Донецкий национальный технический университет Рассматриваются параллельные

Труды ИСА РАН, 2008. Т. 32 О понятии производительности в распределенных вычислительных системах М. А. Посыпкин, А. С. Хританков Институт системного анализа Российской академии наук (ИСА РАН) В данной

2007 НАУЧНЫЙ ВЕСТНИК МГТУ ГА 26 серия Радиофизика и радиотехника УДК 6236:6239 ОЦЕНКА ЦЕЛЕСООБРАЗНОСТИ РАСПАРАЛЛЕЛИВАНИЯ ИНФОРМАЦИОННО-ЗАВИСИМЫХ ЗАДАЧ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РН АКИНШИН Статья представлена

Максимальное распараллеливание алгоритмов на основе концепции Q-детерминанта Валентина Николаевна Алеева Южно-Уральский государственный университет (НИУ) Новосибирcк, 2015 ВВЕДЕНИЕ В докладе рассматривается

Министерство образования и науки Российской Федерации Нижегородский государственный университет им. Н.И. Лобачевского В.П. Гергель ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОПРОЦЕССОР- НЫХ МНОГОЯДЕРНЫХ

ЛК 1. Моделирование. 1. Основные понятия. 2 Принципы моделирования. 3 Свойства моделей 4 Классификация методов моделирования. 5. Математическое моделирование 1. ОСНОВНЫЕ ПОНЯТИЯ. Моделирование замещение

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Новосибирский государственный университет» (НГУ) Факультет информационных технологий

Нижегородский государственный университет им. Н.И. Лобачевского Научно исследовательский университет Создание учебной библиотеки параллельных методов Parlib Выполнили: Козинов Е.А. Кутлаев М.В. Осокин

УДК 681.3.06 ПРОЕКТИРОВАНИЕ СТРУКТУРЫ ЛОКАЛЬНОЙ СЕТИ ДЛЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ А.В. Погребной, Д.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected]

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА ЦИКЛИЧЕСКОЙ ПРОГОНКИ Головашкин Д.Л., Филатов М. В. Институт систем обработки изображений РАН Самарский государственный аэрокосмический университет Аннотация Работа посвящена

УДК 519.856; 519.854; 519.85 СТАТИСТИЧЕСКИЙ ПОИСК СТРУКТУР ИНФОРМАЦИОННО- ВЫЧИСЛИТЕЛЬНОЙ СЕТИ В.В. Малыгин Исследованы свойства сходимости функции оценки структуры информационно вычислительной сети. На

Построение рекурсивно-параллельных алгоритмов решения задач вычислительной геометрии на основе стратегии «распределяй и властвуй» В.Н. Терещенко В работе рассматривается один из подходов построения эффективных

12.1. Ввод-вывод по опросу готовности устройства Готовность или неготовность внешнего устройства к вводу-выводу проверяется в регистре состояния внешнего устройства Для программно-управляемого ввода/вывода

ТАКСОНОМИЯ ФЛИННА Кириллова Юлия 6057/2 22.11.11 Таксономия Флинна общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. предложена в 1972 г. Майклом Флинном.

Лабораторная работа 4 Решение задачи Пуассона методом Якоби в трехмерной области Цель - практическое освоение методов распараллеливание алгоритмов задач, решаемых сеточными методами на примере решения

Текущая версия страницы пока не проверялась

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от, проверенной 5 октября 2014; проверки требуют.

Параллельные вычисления - способ организации компьютерных вычислений , при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно (одновременно). Термин охватывает совокупность вопросов параллелизма в программировании , а также создание эффективно действующих аппаратных реализаций . Теория параллельных вычислений составляет раздел прикладной теории алгоритмов .

Существуют различные способы реализации параллельных вычислений. Например, каждый вычислительный процесс может быть реализован в виде процесса операционной системы , либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса ОС. Параллельные программы могут физически исполняться либо последовательно на единственном процессоре - перемежая по очереди шаги выполнения каждого вычислительного процесса, либо параллельно - выделяя каждому вычислительному процессу один или несколько процессоров (находящихся рядом или распределённых в компьютерную сеть).

Основная сложность при проектировании параллельных программ - обеспечить правильную последовательность взаимодействий между различными вычислительными процессами, а также координацию ресурсов, разделяемых между процессами.

В некоторых параллельных системах программирования передача данных между компонентами скрыта от программиста (например, с помощью механизма обещаний), тогда как в других она должна указываться явно. Явные взаимодействия могут быть разделены на два типа:

Параллельные системы, основанные на обмене сообщениями, зачастую более просты для понимания, чем системы с разделяемой памятью, и обычно рассматриваются как более совершенный метод параллельного программирования. Существует большой выбор математических теорий для изучения и анализа систем с передачей сообщений, включая модель акторов и различные виды исчислений процессов . Обмен сообщениями может быть эффективно реализован на симметричных мультипроцессорах как с разделяемой когерентной памятью, так и без неё.

У параллелизма с распределенной памятью и с передачей сообщений разные характеристики производительности. Обычно (но не всегда), накладные расходы памяти на процесс и времени на переключение задач у систем с передачей сообщений ниже, однако передача самих сообщений более накладна, чем вызовы процедур. Эти различия часто перекрываются другими факторами, влияющими на производительность.

Параллельные вычислительные процессы и системы (Лекция 13)

Виды параллелизма

Параллельная обработка данных имеет две разновидности: конвейерность и собственно параллельность.

Параллельная обработка. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени.

Конвейерная обработка. Что необходимо для сложения двух вещественных чисел, представленных в форме с плавающей запятой? Целое множество мелких операций таких, как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п. Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой пары аргументов последовательно одна за одной до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получается очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят– ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5 + 99 = 104 единицы времени – ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы, конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. Но, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость.

Реализация параллельных систем

Производительность компьютеров росла экспоненциально, начиная с 1945 года и до настоящего момента (если брать средний показатель за каждые 10 лет). Компьютерная архитектура претерпела значительные изменения, пройдя путь от последовательной до параллельной.

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

Несложно сделать вывод, что нельзя ограничиваться увеличением скорости лишь за счет тактовой частоты процессоров. Зависимость от процессоров в конечном итоге заводит в тупик. Другая стратегия в этой области – использование внутреннего параллелизма в чипе процессора. Но такая технология очень дорога. Современные суперкомпьютеры основываются в большей степени на идее использование большого количества относительно не дорогих уже имеющихся процессоров.

Это подразумевает и такие системы, как: суперкомпьютеры, оборудованные тысячами процессоров; сети рабочих станций; мультипроцессорные рабочие станции и т.д.

Мультикомпьютер – это некоторое количество машин фон Неймана (узлов) связанных между собой сетью. Каждый компьютер выполняет свою программу. Эти программы могут иметь доступ к локальной памяти и умеют посылать и получать сообщения через сеть. Сообщения, используемые для связи между компьютерами, эквивалентны операциям чтения или записи с удаленной памятью. В идеализированной сети время доставки сообщения между машинами не зависит от расстояния между узлами или сетевого трафика, но зависит от длины отправляемого письма.

Определяющий параметр модели мультикомпьютера – это то, что доступ к локальной (в том же узле) памяти менее дорог, чем доступы к удаленной (находящейся в другом узле) памяти. Т.е. операции чтения и записи менее дороги, чем отправление или получение сообщений. Следовательно, желательно, чтобы обращение к локальным данным было гораздо более частым, чем к удаленным данным. Это фундаментальное свойство программного обеспечения называется локальностью. Значение локальности зависит от отношения стоимости дистанционного доступа к локальному.

Другие модели машин. Рассмотрим важнейшие компьютерные архитектуры. Мультикомпьютер очень похож на то, что часто называют компьютером с распределенной памятью MIMD (Multiple Instruction Multiple Data ). MIMD означает, что каждый процессор может обрабатывать отдельный поток инструкций над его собственными локальными данными. Распределенная память означает, что память распределена между процессорами. Принципиальным отличием MIMD компьютера от мультикомпьютера – это то, что стоимость доставки сообщения между двумя узлами не зависит от местоположения узла и сетевого трафика. Основные представители этого класса: IBM SP, Intel Paragon , Thinking Machines CM 5, Cray T 3D , Meiko CS -2, и CUBE .

Другой класс суперкомпьютеров – мультипроцессор или MIMD компьютер с разделяемой памятью. В мультипроцессоре все процессоры делят доступ к общей памяти, обычно через шину или через иерархию шин. В идеализированной модели параллельной машины с произвольным доступом (PRAM) часто используют теоретически изучаемые параллельные алгоритмы, любой процессор может получить доступ к любому элементу памяти в одно и то же время. Такая архитектура обычно подразумевает некоторые специальные формы устройства памяти. Количество обращений к разделяемой памяти уменьшается за счет хранения копий часто используемых данных в кэше, связанном с каждым процессором.

Доступ к этому кэшу намного быстрее, чем доступ к разделяемой памяти, следовательно, локальность очень важна. Программы, разработанные для мультикомпьютеров, могут так же эффективно работать на мультипроцессорах, потому что разделяемая память позволяет эффективную реализацию передачи сообщений. Представители этого класса – Silicon Graphics Challenge, Sequent Symmetry и многие мультипроцессорные рабочие станции.

Более специализированный класс параллельных компьютеров – это SIMD (Single Instruction Miltiple Data) компьютеры. В SIMD машинах все процессоры оперируют с одним и тем же потоком инструкций над различными порциями данных. Этот подход может уменьшить сложность программного и аппаратного обеспечения, но это имеет смысл только для специализированных проблем, характеризуемых высокой степенью закономерности, например обработка изображений и определенные виды цифрового моделирования. Алгоритмы, применимые на мультикомпьютерах, не могут в общих чертах эффективно выполняться в SIMD компьютерах.

Нейровычислительные системы.

Нейровычислительное устройство – это система, функционирование которой в максимальной степени ориентировано на реализацию нейросетевых алгоритмов. Основное отличие нейрокомпьютеров от других вычислительных систем – это обеспечение высокого параллелизма вычислений за счет применения специализированного нейросетевого логического базиса или конкретных архитектурных решений. Использование возможности представления нейросетевых алгоритмов для реализации на нейросетевом логическом базисе является основной предпосылкой резкого увеличения производительности нейрокомпьютеров.

Сейчас разработки цифровых нейрокомпьютеров наиболее активно ведутся по следующим направлениям:

· программная эмуляция нейросетевых алгоритмов на основе использования обычных вычислительных средств и ППО по моделированию нейросетей;

· программно-аппаратная эмуляция нейросетей на основе стандартных вычислительных средств с подключаемым виртуальным нейросетевым блоком, выполняющим основные нейрооперации, и ППО, осуществляющим функции общего управления;

· аппаратная реализация нейронных сетей.

Несмотря на то, что наибольшего эффекта при реализации нейросетевых алгоритмов удается добиться лишь с использованием нейрокомпьютеров третьего направления, их широкое применение ограничивается высокой. Например, нейрокомпьютер Synaps1 – один из представителей нейрокомпьютеров третьего направления, имеет мультипроцессорную архитектуру, оригинальное построение подсистемы памяти, а для выполнения вычислительных операций использует сигнальные процессоры и специальные сигнальные матричные процессоры МА16. За счет этого производительность нейрокомпьютера составила порядка несколько миллиардов умножений и сложений в секунду. Программное обеспечение данной системы включает в себя ОС Synaps1 с библиотекой нейроалгоритмов, а также ППО: базовую библиотеку НС, компилятор языка программирования нейроалгоритмов (nAPL) (набор библиотечных функций для С++) и т.п. Прикладные исследования показали, что использование нейрокомпьютеров третьего направления позволяет повысить производительность обычных вычислительных систем как минимум на три порядка и моделировать НС с миллионами соединений. Так, например, Synaps1 позволяет моделировать нейросеть с 64 миллионами синапсов с использованием различных активационных функций.

Два класса компьютерных систем, которые иногда используют как параллельные компьютеры – это локальная сеть (LAN), в которой компьютеры, находящиеся в физической близости (например, то же строение), связываются быстрой сетью, и глобальная сеть (WAN), в которой соединены географически удаленные компьютеры. Хотя системы такого типа доставляют дополнительные проблемы, такие как безопасность, надежность, они могут быть рассмотрены для различных целей как мультикомпьютеры, хотя и с высокой стоимостью удаленного доступа.

Сложности использования параллельных систем

Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования.

У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

Закон Амдала. Предположим, что в программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f <=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из "p" процессоров при данном значении f, можно воспользоваться законом Амдала: если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (10 получается только в том случае, когда время исполнения параллельной части равно 0).

Следствие закона Амдала. Для того, чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q ) -ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем для 99.99% кода!

Таким образом, заставить параллельную вычислительную систему работать с максимальной эффективностью на конкретной программе это задача не из простых, поскольку необходимо тщательное согласование структуры программ и алгоритмов с особенностями архитектуры параллельных вычислительных систем.

Программирование параллельных систем

Модель машины фон Неймана предполагает, что процессор выполняет последовательность инструкций. Инструкции могут определять в дополнение к различным арифметическим операциям адреса данных, которые надо прочитать/записать в памяти, и/или адрес следующей инструкции, которую надо выполнить. Пока возможно только программировать компьютер с точки зрения этой основной модели, этот метод для большинства целей недопустимо сложен из-за того, что мы должны следить за миллионами позиций памяти и организовать выполнение тысяч машинных инструкций. Следовательно, прикладывается модульная техника разработки, посредством которой сложные программы создаются из простых компонент, и компоненты структуры с точки зрения абстракций более высокого уровня (такие, как структуры данных, итерационные циклы и процедуры). Абстракции (например, процедуры) делают эксплуатацию модульности легче, допуская объекты, которыми должны управлять без беспокойства для их внутренней структуры. Так сделаны высокоуровневые языки, как, например, Fortran, C, Ada и Java , которые допускают разработку, выраженную с точки зрения этих абстракций, которые переводятся автоматически в выполняемый код. Параллельное программирование вводит дополнительные источники сложности: если мы должны запрограммировать на самом низком уровне, нам нужно не только увеличить количество выполняемых инструкций, но также управлять выполнением тысяч процессоров и координированием миллионов межпроцессорных взаимодействий. Следовательно, абстракция и модульность по крайней мере так же важны, как и в последовательном программировании. Фактически, мы выделим модульность как четвертое фундаментальное требование для параллельного программного обеспечения, дополнительно к параллелизму, масштабируемости, и локальности.

Основные абстракции, используемые в параллельном программиро-вании, сводятся к задачам и каналам:

1.Параллельное вычисление состоит из одной или более задач. Задачи выполняются параллельно. Количество задач может меняться во время выполнения программы.

2.Задача изолирует последовательную программу и локальную память. Вдобавок набор вводов и выводов определяет свой интерфейс в своей среде.

3.Задача может выполнять четыре основных действия дополнительно к чтению и записи в локальной памяти: послать сообщение на свои порты вывода, получить сообщение со своих портов ввода, создать новые задачи и уничтожить (завершить) задачу.

4.Операция отправления сообщения – асинхронная, она завершается немедленно. Операция получения – синхронная, она вызывает выполнение задачи, блокируя процесс, пока сообщение не будет получено.

5.Пары ввода/вывода могут связываться сообщениями в очереди, называемыми каналами. Каналы могут создаваться и удаляться, и ссылки на каналы (порты) способны включаться в сообщения, так что связность изменяется динамически.

6.Задания могут отображаться в физических процессорах различными способами; отображающее применение не влияет на семантику программы. Конкретно многочисленные задания могут отображаться в единственном процессоре (можно также представить, что единичная задача может быть отображенной в множестве процессоров, но эта возможность здесь не учитывается.)

Абстракция задач требует свойство локальности: данные, содержащиеся в локальной памяти задачи – «закрытые»; другие данные – «удаленные». Канальная абстракция обеспечивает механизм для указания, вычисление каких данных из одной задачи требуется для начала работы другой задачи. (Это охарактеризовано зависимостью данных). Модель задач и каналов обладает и некоторыми другими свойствами:

Производительность . Последовательные абстракции программирования, такие как, например, процедуры и структуры данных, эффективны из-за того, что они могут быть отображены просто и эффективно в компьютере фон Неймана. Задачи и каналы имеют аналогично прямое распределение в мультикомпьютере. Задача представляет часть кода, который может быть выполнен последовательно в единственном процессоре. Если две задачи, которые делят канал, отображаются в других процессорах, канальное соединение осуществлено как межпроцессорное соединение; если они отображаются в том же процессоре, могут быть использованы некоторые более эффективные механизмы.

Независимость распределения . Поскольку задания взаимодействуют, используя тот же механизм (каналы) независимо от положения задачи, результат вычисленный программой не зависит от того, где задача выполняется. Следовательно, алгоритмы могут разрабатываться и осуществляться без беспокойства о количестве процессоров, на которых они будут выполняться; фактически, алгоритмы часто разрабатываются так, что создают гораздо больше задач, чем процессоров. Это простой путь достижения масштабности: когда количество процессоров увеличивается, количество задач на процессор уменьшается, но сам алгоритм не должен быть модифицирован. Когда имеется большее число задач, чем процессоры смогли бы обслуживать, чтобы замаскировать задержки связи, обеспечиваются другие вычисления, которые могут выполняться, пока выполняется связь для доступа к удаленным данным.

Модульность . В модульном составлении программы различные компоненты программ разрабатываются отдельно как независимые модули и затем объединяются, чтобы получить полную программу. Взаимодействие между модулями ограничивается отчетливо выраженными интерфейсами. Следовательно, модульные реализации могут быть изменены без модификации других компонент, и свойства программы могут определяться из спецификации ее модулей и кода, который соединяет эти модули вместе. Когда успешно приложена модульная разработка, уменьшается программная сложность и облегчается многократное использование кода.

Детерминизм . Алгоритм или программа детерминированы, если при выполнении с конкретным вводом всегда получается один и тот же вывод. Он недетерминирован, если многочисленные выполнения с тем же вводом могут дать другой вывод. Хотя недетерминизм иногда полезен и должен поддерживаться, параллельная модель программирования, которая облегчает написание детерминированных программ, очень желательна. Детерминированные программы имеют тенденцию быть более понятными. Также при проверке на правильность должна вычисляться только одна последовательность выполнения параллельной программы, а не все возможные для выполнения.

Понятие параллельных вычислений

ОСНОВЫ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Лекция №6

Под параллельными вычислениями (parallel or concurrent computations) можно понимать процессы решения задач, в которых в один и тот же момент времени могут выполняться одновременно несколько вычислительных операций

Параллельные вычисления составляют основу суперкомпьютерных технологий и высокопроизводительных расчетов

· Параллельная обработка

Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени.

Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут - принцип параллельности в действии!

Пионером в параллельной обработке потоков данных был академик А.А.Самарский, выполнявший в начале 50-х годов расчеты, необходимые для моделирования ядерных взрывов. Самарский решил эту задачу, посадив несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была расчитана эволюция взрывной волны.

Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал. Это, можно сказать, и была первая параллельная система. Хотя расчеты водородной бомбы были мастерски проведены, точность их была очень низкая, потому что узлов в используемой сетке было мало, а время счета получалось слишком большим.

· Конвейерная обработка

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций.

Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Модели параллельных компьютеров (классификация Флинна)

· «Один поток команд - один поток данных» (SISD - "Single Instruction Single Data")

Относится к фон-Неймановской архитектуре. SISD компьютеры это обычные, "традиционные" последовательные компьютеры, в которых в каждый момент времени выполняется лишь одна операция над одним элементом данных (числовым или каким-либо другим значением). Большинство современных персональных ЭВМ попадает именно в эту категорию.

· «Один поток команд - много потоков данных» (SIMD - "Single Instruction - Multiplе Data")

SIMD (англ. Single Instruction, Multiple Data) - принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных. SIMD компьютеры состоят из одного командного процессора (управляющего модуля), называемого контроллером, и нескольких модулей обработки данных, называемых процессорными элементами. Управляющий модуль принимает, анализирует и выполняет команды.

Если в команде встречаются данные, контроллер рассылает на все процессорные элементы команду, и эта команда выполняется на нескольких или на всех процессорных элементах. Каждый процессорный элемент имеет свою собственную память для хранения данных. Одним из преимуществ данной архитектуры считается то, что в этом случае более эффективно реализована логика вычислений. SIMD процессоры называются также векторными.

· «Много потоков команд - один поток данных» (MISD - "Multiple Instruction - Single Data")

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

Массивы ПЭ с непосредственными соединениями между близлежащими ПЭ называются систолическими . Такие массивы исключительно эффективны, но каждый из них ориентирован на решение весьма узкого класса задач. Рассмотрим, как можно построить систолический массив для решения некоторой задачи. Пусть, например, требуется создать устройство для вычисления матрицы D=C+AB , где

Здесь все матрицы - ленточные, порядка n . Матрица A имеет одну диагональ выше и две диагонали ниже главной; матрица B - одну диагональ ниже и две диагонали выше главной; матрица C по три диагонали выше и ниже главной. Пусть каждый ПЭ может выполнять скалярную операцию c+ab и одновременно осуществлять передачу данных. Каждый ПЭ, следовательно, должен иметь три входа: a, b, c и три выхода: a, b, c . Входные (in ) и выходные (out ) данные связаны соотношениями

a out = a in , b out = b in , c out = c in + a in *b in ;

Если в момент выполнения операции какие-то данные не поступили, то будем считать, что они доопределяются нулями. Предположим далее, что все ПЭ расположены на плоскости и каждый из них соединен с шестью соседними. Если расположить данные, как показано на рисунке, то схема будет вычислять матрицу D .

Массив работает по тактам. За каждый такт все данные перемещаются в соседние узлы по направлениям, указанным стрелками.

На рисунке показано состояние систолического массива в некоторый момент времени. В следующий такт все данные переместятся на один узел и элементы a11, b11, c11 окажутся в одном ПЭ, находящемся на пересечении штриховых линий. Следовательно, будет вычислено выражение c11+a11b11 .В этот же такт данные a12 и b21 вплотную приблизятся в ПЭ, находящемся в вершине систолического массива.

В следующий такт все данные снова переместятся на один узел в направлении стрелок и в верхнем ПЭ окажутся a12 и b21 и результат предыдущего срабатывания ПЭ, находящегося снизу, т.е. c11+a11b11 . Следовательно, будет вычислено выражение c11+a11b11+a12b21 . Это есть элемент d11 матрицы D .

Продолжая потактное рассмотрение процесса, можно убедиться, что на выходах ПЭ, соответствующих верхней границе систолического массива, периодически через три такта выдаются элементы матрицы D , при этом на каждом выходе появляются элементы одной и той же диагонали. Примерно через 3n тактов будет закончено вычисление всей матрицы D . При этом загруженность каждой систолической ячейки асимптотически равна 1/3 .

· «Много потоков команд - много потоков данных» (MIMD - "Multiple Instruction - Multiple Data")

Эта категория архитектур вычислительных машин наиболее богата, если иметь в виду примеры ее успешных реализаций. В нее попадают симметричные параллельные вычислительные системы, рабочие станции с несколькими процессорами, кластеры рабочих станций и т.д.

Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования. Начнем с самых простых вещей. У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Южно-Российский государственный технический университет

(Новочеркасский политехнический институт)

Шахтинский институт (филиал) ЮРГТУ (НПИ)

ЛЕКЦИИ ПО ДИСЦИПЛИНЕ

«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ»

Шахты- 2010

Введение

Основные понятия

1. Общие вопросы решения ";больших задач";

1.1 Современные задачи науки и техники, требующие для решения суперкомпьютеры

1.2.2 Абстрактные модели параллельных вычислений

1.2.3 Способы параллельной обработки данных, погрешность вычислений

1.3 Понятие параллельного процесса и гранулы распараллеливания

1.4 Взаимодействие параллельных процессов, синхронизация процессов

1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля)

2. Принципы построения многопроцессорных вычислительных систем

2.1 Архитектура многопроцессорных вычислительных систем

2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью

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

2.4 Многопроцессорные вычислительные системы c распределенной памятью

2.4.1 Массивно-параллельные суперкомпьютеры серии Cry T3

2.4.2 Кластерные системы класса BEOWULF

Заключение

Список литературы

Введение

Еще на заре компьютерной эры, примерно в середине прошлого века, конструкторы электронно-вычислительных машин задумались над возможностью применения параллельных вычислений в компьютерах. Ведь увеличение быстродействия только за счет совершенствования электронных компонентов компьютера – достаточно дорогой способ, который, к тому же, сталкивается с ограничениями, налагаемыми физическими законами. Так параллельная обработка данных и параллелизм команд были введены в конструкцию компьютеров и сейчас любой пользователь ";персоналки";, возможно, сам того не зная, работает на параллельном компьютере.

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

С некоторых пор повышение быстродействия компьютеров традиционной (именуемой ";фон Неймановской";) архитектуры стало чрезмерно дорого вследствие технологических ограничений при производстве процессоров, поэтому разработчики обратили внимание на иной путь повышения производительности – объединение электронно-вычислительных машин в многопроцессорные вычислительные системы. При этом отдельные фрагменты программы параллельно (и одновременно) выполняются на различных процессорах, обмениваясь информацией посредством внутренней компьютерной сети.

Идея объединения электронно-вычислительных машин с целью повышения, как производительности, так и надежности известны с конца пятидесятых годов.

Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных комплексов; известны системы такого рода, объединяющие вычислительные мощности тысяч отдельных процессоров. Следующим этапом являются попытки объединить миллионы разнородных компьютеров планеты в единый вычислительный комплекс с огромной производительностью посредством сети Internet. На сегодняшний день применение параллельных вычислительных систем является стратегическим направлением развития вычислительной техники. Развитие ";железа"; с необходимостью подкрепляются совершенствованием алгоритмической и программной компонент – технологий параллельного программирования.

Метод распараллеливания вычислений существует уже давно, организация совместного функционирования множества независимых процессоров требует проведения серьезных теоретико-практических исследований, без которых сложная и относительно дорогостоящая многопроцессорная установка часто не только не превосходит, а уступает по производительности традиционному компьютеру.

Потенциальная возможность распараллеливания неодинакова для вычислительных задач различного типа – она значительна для научных программ, содержащих много циклов и длительных вычислений и существенно меньше для инженерных задач, для которых характерен расчет по эмпирическим формулам.

Рассмотрим два основных вопроса:

1. Многопроцессорные вычислительные системы – (массивно-параллельные суперкомпьютеры) Cray T3D(E) с количеством процессоров от 40 до 2176. Это суперкомпьютеры с распределенной памятью на RISC-процессорах типа Alpha21164A, с топологией коммуникационной сети – трехмерный тор, операционной системой UNIX с микроядром и трансляторами для языков FORTRAN, HPF, C/C++. Поддерживаемые модели программирования: MPI, PVM, HPF.

2. Беовульф-кластеры рабочих станций. Кластеры рабочих станций – совокупность рабочих станций, соединенных в локальную сеть. Кластер – вычислительная система с распределенной памятью и распределенным управлением. Кластерная система может обладать производительностью, сравнимой с производительностью суперкомпьютеров. Кластеры рабочих станций обычно называют Беовульф-кластерами (Beowulf cluster – по одноименному проекту), связанны локальной сетью Ethernet и используют операционную систему Linux.

Основные понятия

Наиболее распространенной технологией программирования для кластерных систем и параллельных компьютеров с распределенной памятью в настоящее время является технология MPI. Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии – Message Passing Interface (интерфейс передачи сообщений). Стандарт MPI фиксирует интерфейс, который должен соблюдаться как системой программирования на каждой вычислительной платформе, так и пользователем при создании своих программ. MPI поддерживает работу с языками Фортран и Си. Полная версия интерфейса содержит описание более 125 процедур и функций.

Интерфейс MPI поддерживает создание параллельных программ в стиле MIMD (Multiple Instruction Multiple Data), что подразумевает объединение процессов с различными исходными текстами. Однако писать и отлаживать такие программы очень сложно, поэтому на практике программисты, гораздо чаще используют SPMD-моделъ (Single Program Multiple Data) параллельного программирования, в рамках которой для всех параллельных процессов используется один и тот же код. В настоящее время все больше и больше реализаций MPI поддерживают работу с так называемыми ";нитями";.

Поскольку MPI является библиотекой, то при компиляции программы необходимо прилинковать соответствующие библиотечные модули.

После получения выполнимого файла необходимо запустить его на требуемом количестве процессоров. После запуска одна и та же программа будет выполняться всеми запущенными процессами, результат выполнения в зависимости от системы будет выдаваться на терминал или записываться в файл.

MPI программа – это множество параллельных взаимодействующих процессов. Все процессы порождаются один раз, образуя параллельную часть программы. В ходе выполнения MPI-программы порождение дополнительных процессов или уничтожение существующих не допускается (в дальнейших версиях MPI такая возможность появилась). Каждый процесс работает в своем адресном пространстве, никаких общих переменных или данных в MPI нет. Основным способом взаимодействия между процессами является явная посылка сообщений.

Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения – коммуникатор. Состав образуемых групп произволен. Группы могут полностью совпадать, входить одна в другую, не пересекаться или пересекаться частично. Процессы могут взаимодействовать только внутри некоторого коммуникатора, сообщения, отправленные в разных коммуникаторах, не пересекаются и не мешают друг другу. Коммуникаторы имеют в языке Фортран тип integer (в языке Си – предопределенный тип MPI Comm).

При старте программы всегда считается, что все порожденные процессы работают в рамках всеобъемлющего коммуникатора. Этот коммуникатор существует всегда и служит для взаимодействия всех запущенных процессов MPI-программы. Все взаимодействия процессов протекают в рамках определенного коммуникатора, сообщения, переданные в разных коммуникаторах, никак не мешают друг другу.

Процессоры с сокращенным набором команд (RISC). В основе RISC-архитектуры (RISC – Reduced Instruction Set Computer) процессора лежит идея увеличения скорости его работы за счет упрощения набора команд.

Исследования показали, что 33% команд типичной программы составляют пересылки данных, 20% – условные ветвления и еще 16% – арифметические и логические операции. В подавляющем большинстве команд вычисление адреса может быть выполнено быстро, за один цикл. Более сложные режимы адресации используются примерно в 18% случаев. Около 75% операндов являются скалярными, то есть переменными целого, вещественного, символьного типа и т. д., а остальные являются массивами и структурами. 80% скалярных переменных – локальные, а 90% структурных являются глобальными. Таким образом, большинство операндов – это локальные операнды скалярных типов. Они могут храниться в регистрах.

Согласно статистике, большая часть времени тратится на обработку операторов ";вызов подпрограммы"; и ";возврат из подпрограммы";. При компиляции эти операторы порождают длинные последовательности машинных команд с большим числом обращений к памяти, поэтому даже если доля этих операторов составляет всего 15%, они потребляют основную часть процессорного времени. Только около 1% подпрограмм имеют более шести параметров, а около 7% подпрограмм содержат более шести локальных переменных.

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

В основу RISC-архитектуры положены следующие принципы и идеи. Набор команд должен быть ограниченным и включать только простые команды, время выполнения которых после выборки и декодирования один такт или чуть больше. Используется конвейерная обработка. Простые RISC-команды допускают эффективную аппаратную реализацию, в то время как сложные команды могут быть реализованы только средствами микропрограммирования. Конструкция устройства управления в случае RISC-архитектуры упрощается, и это дает возможность процессору работать на больших тактовых частотах. Использование простых команд позволяет эффективно реализовать и конвейерную обработку данных, и выполнение команд.

Сложные команды RISC-процессором выполняются дольше, но их количество относительно невелико. В RISC-процессорах небольшое число команд адресуется к памяти. Выборка данных из оперативной памяти требует более одного такта. Большая часть команд работает с операндами, находящимися в регистрах. Все команды имеют унифицированный формат и фиксированную длину. Это упрощает и ускоряет загрузку и декодирование команд, поскольку, например, код операции и поле адреса всегда находятся в одной и той же позиции. Переменные и промежуточные результаты вычислений могут храниться в регистрах. С учетом статистики использования переменных, большую часть локальных переменных и параметров процедур можно разместить в регистрах. При вызове новой процедуры содержимое регистров обычно перемещается в оперативную память, однако, если количество регистров достаточно велико, удается избежать значительной части длительных операций обмена с памятью, заменив их операциями с регистрами. Благодаря упрощенной архитектуре RISC-процессора, на микросхеме появляется место для размещения дополнительного набора регистров.

В настоящее время вычислительные системы с RISC-архитектурой занимают лидирующие позиции на мировом компьютерном рынке рабочих станций и серверов. Развитие RISC-архитектуры связано с развитием компиляторов, которые должны эффективно использовать преимущества большого регистрового файла, конвейеризации и т. д.

1. Общие вопросы решения ";больших задач";

Под термином ";большие задачи"; обычно понимают проблемы, решение которых требует не только построения сложных математических моделей, но и проведения огромного, на многие порядки превышающие характерные для программируемых электронно-вычислительных машин, количества вычислений. Здесь применяют с соответствующими ресурсами электронно-вычислительные машины – размерами оперативной и внешней памяти, быстродействием линий передачи информации и др.

Верхний предел количества вычислений для ";больших задач"; определяется лишь производительностью существующих на данный момент вычислительных систем. При ";прогонке"; вычислительных задач в реальных условиях ставится не вопрос ";решить задачу вообще";, а ";решить за приемлемое время"; (часы/десятки часов).

1.1. Современные задачи науки и техники, требующие

для решения суперкомпьютеры

Достаточно часто приходится сталкиваться с такими задачами, которые, представляя немалую ценность для общества, не могут быть решены с помощью относительно медленных компьютеров офисного или домашнего класса. Единственная надежда в этом случае возлагается на компьютеры с большим быстродействием, которые принято называть суперкомпьютерами. Только машины такого класса могут справиться с обработкой больших объемов информации. Это могут быть, например, статистические данные или результаты метеорологических наблюдений, финансовая информация. Иногда скорость обработки имеет решающее значение. В качестве примера можно привести составление прогноза погоды и моделирование климатических изменений. Чем раньше предсказано стихийное бедствие, тем больше возможностей подготовиться к нему. Важной задачей является моделирование лекарственных средств, расшифровка генома человека, томография, в том числе и медицинская, разведка месторождений нефти и газа. Примеров можно привести много.

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

Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных комплексов; известны системы такого рода, объединяющие вычислительные мощности тысяч отдельных процессоров.

Ниже перечислены некоторые области человеческой деятельности, требующие для своего решения суперкомпьютерных мощностей использующих параллельные вычисления:

Предсказания погоды, климата и глобальных изменений в атмосфере

Науки о материалах

Построение полупроводниковых приборов

Сверхпроводимость

Разработка фармацевтических препаратов

Генетика человека

Астрономия

Транспортные задачи большой размерности

Гидро и газодинамика

Управляемый термоядерный синтез

Разведка нефти и газа

Вычислительные задачи наук о мировом океане

Распознавание и синтез речи, распознавание изображений

Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,6×106 (сетка с шагом 10 по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,6×107 числами. При шаге дискретизации по времени 10 минут за моделируемый промежуток времени необходимо определить 5×104 ансамблей (то есть 1014 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 102÷103 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 1016÷1017.

Суперкомпьютер с производительностью 1012 оп/сек при идеальном случае (полная загруженность и эффективная алгоритмизация) будет выполнять такой эксперимент в течение нескольких часов; для проведения полного процесса моделирования необходима многократная (десятки/сотни раз) прогонка программы.

Проблема супервычислений столь важна, что многие государства курируют работы в области суперкомпьютерных технологий.

Государственная поддержка прямо связана с тем, что независимость в области производства и использования вычислительной техники отвечает интересам национальной безопасности, а научный потенциал страны непосредственно связан и в большой мере определяется уровнем развития вычислительной техники и математического обеспечения.

С целью объективности при сравнении производительность супер-электронно-вычислительных машин рассчитывается на основе выполнения заранее известной тестовой задачи (";бенчмарка";, от англ. benchmark). Пиковая производительность определяется максимальным числом операций, которое может быть выполнено за единичное время при отсутствии связей между функциональными устройствами, характеризует потенциальные возможности аппаратуры и не зависит от выполняемой программы.

Недостатком метода оценки пиковой производительности как числа выполняемых компьютером команд в единицу времени (MIPS, Million Instruction Per Second) дает только самое общее представление о быстродействии, так как не учитывает специфику конкретных программ (трудно предсказуемо, в какое число и каких именно инструкций процессора отобразится пользовательская программа).

Необходимо отметить, что существуют аргументы против широкого практического применения параллельных вычислений:

Параллельные вычислительные системы чрезмерно дороги. По подтверждаемому практикой закону Гроша, производительность компьютера растет пропорционально квадрату его стоимости; в результате гораздо выгоднее получить требуемую вычислительную мощность приобретением одного производительного процессора, чем использование нескольких менее быстродействующих процессоров.

Контраргумент. Рост быстродействия последовательных электронно-вычислительных машин не может продолжаться бесконечно, компьютеры подвержены быстрому моральному старению и необходимы частые финансовые затраты на покупку новых моделей. Практика создания параллельных вычислительных систем класса Beowulf ясно показала экономичность именно этого пути.

При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского (Marvin Minsky) достигаемое при использовании параллельной системы ускорение вычислений пропорционально двоичному логарифму от числа процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10).

Контраргумент. Приведенная оценка ускорения верна для распараллеливания определенных алгоритмов. Однако существует большое количество задач, при параллельном решении которых достигается близкое к 100% использованию всех имеющихся процессоров параллельной вычислительной системы.

Последовательные компьютеры постоянно совершенствуются. По широко известному закону Мура сложность последовательных микропроцессоров возрастает вдвое каждые 18 месяцев, поэтому необходимая производительность может быть достигнута и на ";обычных"; последовательных компьютерах.

Контраргумент. Аналогичное развитие свойственно и параллельным системам.

Однако применение параллелизма позволяет получать необходимое ускорение вычислений без ожидания разработки новых более быстродействующих процессоров. Эффективность параллелизма сильно зависит от характерных свойств параллельных систем. Все современные последовательные электронно-вычислительные машины работают в соответствие с классической схемой фон-Неймана; параллельные системы отличаются существенным разнообразием архитектуры и максимальный эффект от использования параллелизма может быть получен при полном использовании всех особенностей аппаратуры (следствие – перенос параллельных алгоритмов и программ между разными типами систем затруднителен, а иногда и невозможен).

Контраргумент. При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные ";устоявшиеся"; способы обеспечения параллелизма. Инвариантность создаваемого программного обеспечения обеспечивается при помощи использования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.). PVM и MPI используются в суперкомпьютерах Cray-T3.

За десятилетия эксплуатации последовательных электронно-вычислительных машинах накоплено огромное программное обеспечение, ориентировано на последовательные электронно-вычислительные машины; переработка его для параллельных компьютеров практически нереальна.

Контраргумент. Если эти программы обеспечивают решение поставленных задач, то их переработка вообще не нужна. Однако если последовательные программы не позволяют получать решение задач за приемлемое время или же возникает необходимость решения новых задач, то необходима разработка нового программного обеспечения и оно изначально может реализовываться в параллельном исполнении.

Существует ограничение на ускорение вычисление при параллельной реализации алгоритма по сравнению с последовательной.

Контраргумент. В самом деле, алгоритмов вообще без (определенной) доли последовательных вычислений не существует. Однако это суть свойство алгоритма и не имеет отношения к возможности параллельного решения задачи вообще. Необходимо научиться применять новые алгоритмы, более подходящие для решения задач на параллельных системах.

Таким образом, на каждое критическое соображение против использования параллельных вычислительных технологий находится более или менее существенный контраргумент.

1.2 Параллельная обработка данных

1.2.1 Принципиальная возможность параллельной обработки

Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.

Можно построить m процессоров, которые при одновременной работе выдают нужный результат за один-единственный такт работы вычислителя.

Такие ";многопроцессорные"; машины теоретически можно построить для каждого конкретного алгоритма и, казалось бы, ";обойти"; последовательный характер алгоритмов. Однако не все так просто – конкретных алгоритмов бесконечно много, поэтому развитые выше абстрактные рассуждения имеют не столь прямое отношение к практической значимости. Их развитие убедило в самой возможности распараллеливания, явилось основой концепции неограниченного параллелизма, дало возможность рассматривать с общих позиций реализацию так называемых вычислительных сред – многопроцессорных систем, динамически настраиваемых под конкретный алгоритм.

---