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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 Цель работы

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

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

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

3 Постановка задачи

Дана многоблочная программа на языке Fortran-DVM, использующая механизм подзадач DVM.

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