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

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

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

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

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

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

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

· Для каждого блока отдельно строится сетка в соответствии с граничными условиями.

Рисунок 1. Примеры сеток в многоблочном методе

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

1.3 Программирование параллельных ЭВМ

Чтобы считать задачу на параллельном вычислителе, она должна быть распараллелена. Распараллеливать может:

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

Для научно-инженерных расчетов применяются следующие модели программирования:

· Модель передачи сообщений

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

· Модель с общей памятью

Все процессы разделяют единое адресное пространство. Доступ к общим данным регулируется с помощью примитивов синхронизации. Стандартом для моделей с общей памятью стал OpenMP.

· Модель параллелизма по данным

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

· пользователь вместе со специальной программой-распараллеливателем в автоматизированном режиме - указывая свойства последовательной программы

· автоматический распараллеливатель – он извлекает параллелизм самостоятельно из последовательной программы и распараллеливает ее в автоматическом режиме без участия пользователя

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

Подавляющее большинство программ для систем с распределенной памятью в настоящее время разрабатываются в модели передачи сообщений (MPI). Языки, поддерживающие модель параллелизма по данным (HPF, Fortran-DVM, C-DVM), значительно упрощают разработку программ, но их использование очень ограничено. Кардинальные изменения архитектуры ЭВМ (многоядерность, использование в качестве ускорителей графических процессоров) требуют появления новых языков высокого уровня, обеспечивающих более высокий уровень автоматизации программирования, в том числе и при создании многоблочных программ.

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

2 Цель работы

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

· обеспечить автоматическое (а не только ручное) отображения подзадач на процессоры

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