ВКР: Распараллеливание многоблочных задач для SMP-кластера

Московский государственный университет им. М. В. Ломоносова

Факультет вычислительной математики и кибернетики

Кафедра системного программирования

ДИПЛОМНАЯ РАБОТА

Распараллеливание многоблочных задач для SMP-кластера

Аннотация
Оптимизация распределения данных и вычислений между процессорами является важным шагом при распараллеливании многоблочных задач. В первом разделе описаны параллельные системы и актуальность многоблочного метода. Во втором и третьем разделе определены цели и задачи данной работы. В четвертом и пятом разделе приводится обзор существующих алгоритмов и предлагается эффективный метод отображения подзадач, допускающих распараллеливание. В шестом разделе описана практическая реализация. Полученный результат в будущем может быть усовершенствован путём ввода в рассмотрение неоднородных вычислительных систем, а также учёта затрат на коммуникации.
Оглавление
1 Введение
1.1 Параллельная ЭВМ и распределенные системы.
1.2 Многоблочный метод решения сложных задач.6
1.3 Программирование параллельных ЭВМ.7
2 Цель работы
3 Постановка задачи
4 Обзор существующих решений
4.1 Алгоритм сокращения критического пути (CPR).
4.2 Упаковка в контейнеры
4.3 Алгоритмы EVAH.
5 Исследование и построение решения задачи
5.1 Первоначальные предложения по отображению..
5.2 Эволюция предложений по отображению..
6 Описание практической части
6.1 Обоснование выбранного инструментария……
6.2 Общая архитектура разработанного средства…
6.3 Схема работы средства…
6.4 Характеристики функционировани
7 Заключение
8 Список цитируемой литературы
Введение

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

1.1 Параллельная ЭВМ и распределенные системы

В настоящее время идет развитие параллельной высокопроизводительной вычислительной техники по следующим направлениям [6]:

• Векторно-конвейерные компьютеры. Конвейерные функциональные устройства и набор векторных команд - это две особенности таких машин. В отличие от традиционного подхода, векторные команды оперируют целыми массивами независимых данных, что позволяет эффективно загружать доступные конвейеры, т.е. команда вида A=B+C может означать сложение двух массивов, а не двух чисел. Характерным представителем данного направления является семейство векторно-конвейерных компьютеров CRAY куда входят, например, CRAY EL, CRAY J90, CRAY T90, новые CRAY X1/X1E.

• Параллельные компьютеры с общей памятью. Вся оперативная память таких компьютеров разделяется несколькими одинаковыми процессорами. Это снимает проблемы предыдущего класса, связанные с необходимостью явного выделения векторных операций в программе, а также позволяет распределить неоднородную работу (например, пока один процессор складывает, одновременно с ним другой может умножать), но добавляет новые - число процессоров, имеющих доступ к общей памяти, по чисто техническим причинам нельзя сделать большим. В данное направление входят многие современные многопроцессорные SMP-компьютеры или, например, отдельные узлы компьютеров HP Exemplar, HP Superdome и Sun StarFire.

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

Однако есть и решающий "минус", сводящий многие "плюсы" на нет. Дело в том, что межпроцессорное взаимодействие в компьютерах этого класса идет намного медленнее, чем происходит локальная обработка данных самими процессорами. Именно поэтому написать эффективную программу для таких компьютеров очень сложно, а для некоторых алгоритмов иногда просто невозможно. К данному классу можно отнести компьютеры Intel Paragon, IBM SP1, Parsytec, в какой-то степени IBM SP2 и CRAY T3D/T3E/X1/XMT, хотя в этих компьютерах влияние указанного минуса значительно ослаблено. К этому же классу можно отнести и сети компьютеров, которые все чаще рассматривают как дешевую альтернативу крайне дорогим суперкомпьютерам.

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

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

1.2 Многоблочный метод решения сложных задач

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

• Физическая область может быть разбита на несколько зон или блоков. Границы блоков могут не соответствовать границам физической области.
• Для каждого блока отдельно строится сетка в соответствии с граничными условиями.