Многоблочный метод решения сложных задач. Программирование параллельных ЭВМ. Алгоритм сокращения критического пути (CPR). Упаковка в контейнеры. Алгоритмы EVAH. Общая архитектура разработанного средства. Первоначальные предложения по отображению.
Пусть имеется n подзадач и m процессоров, тогда алгоритмическая сложность разработанного программного средства при использовании алгоритма «Транспонированное Отображение» асимптотически не превосходит C * (n * log(n) n * m). Время работы на тесте из 10000 блоков, 2048 процессоров на процессоре Intel Core 2 Duo 2.33 ГГЦ составило 100 секунд. Алгоритм был протестирован на данных о блоках реальной задачи из 810 подзадач по моделированию аэродинамики самолета при отображении на 29, 57, 128, 256, 384 процессоров. Запусков счета этой задачи с различными отображения не производилось, все расчеты времени в условных единицах и являются теоретическими на основании знаний о размерах блоков. Получаемые отображения сравнивались с результатами работы алгоритма отображения без учета параллелизма подзадач («Жадное Отображение»), а также с одним из вариантов используемого в DVM отображения, работающему по алгоритму: Пусть есть M процессоровПредложен эффективный алгоритм отображения подзадач, использующий возможность распараллеливания подзадач.
План
Оглавление
1 Введение
1.1 Параллельная ЭВМ и распределенные системы
1.2 Многоблочный метод решения сложных задач
1.3 Программирование параллельных ЭВМ
2 Цель работы
3 Постановка задачи
4 Обзор существующих решений
4.1 Алгоритм сокращения критического пути (CPR)
4.2 Упаковка в контейнеры
4.3 Алгоритмы EVAH
5 Исследование и построение решения задачи
5.1 Первоначальные предложения по отображению
5.2 Эволюция предложений по отображению
6 Описание практической части
6.1 Обоснование выбранного инструментария
6.2 Общая архитектура разработанного средства
6.3 Схема работы средства
Вывод
В рамках этой работы рассмотрены разные алгоритмы для отображения многоблочных задач. Предложен эффективный алгоритм отображения подзадач, использующий возможность распараллеливания подзадач. Он реализован в составе статической библиотеки, подключаемой во время компиляции совместно с системой поддержки времени исполнения LIBDVM, а также в виде интерактивного приложения для генерации отображений.
В дальнейшем стоит задача автоматического определения границ блоков (сейчас блоки определяются ручным образом) для сетки сложной структуры, а также задача усовершенствования предлагаемого алгоритма отображения вводом в рассмотрение неоднородных вычислительных систем, а также учетом затрат на коммуникации.
Список литературы
1 Введение
В истории развитии микропроцессоров и больших интегральных схем известен закон Мура. В 1965 году в процессе подготовки выступления, Гордон Мур сделал такое наблюдение: новые модели микросхем разрабатывались спустя более-менее одинаковые периоды - 18-24 месяца - после появления их предшественников, а емкость их при этом возрастала каждый раз примерно вдвое. Но даже при такой скорости развития мощность отдельных вычислительных машин не может удовлетворять современные потребности физиков-математиков. Появились суперкомпьютеры и кластеры, разработаны параллельные алгоритмы, распределенные методы и системы. Для работы на таких системах нужно распараллеливать программы, а также в таких распределенных системах важную роль играет балансировка вычислений.1. Н.А. Коновалов, В.А. Крюков, А.А. Погребцов, Н.В. Поддерюгина, Ю.Л. Сазанов. Параллельное программирование в системе DVM. Языки Fortran DVM и C-DVM. Труды Международной конференции "Параллельные вычисления и задачи управления" (PACO’2001) Москва, 2-4 октября 2001 г., 140-154 с.
2. M. Jahed Djomehri, Rupak Biswas, Noe Lopez-Benitez. Load balancing strategies for multi-block overset grid applications [PDF] ()
3. Oliver Sinnen. Task Scheduling for Parallel Systems // John Wiley And Sons, Inc. 2007.
4. Nir Menakerman, Raphael Rom. Bin Packing with Item Fragmentation // Algortihms and Data Structures. Springer Berlin / Heidelberg, 2001. Volume 2125/2001. P. 313-324
5. Andrei Radulescu, Arjan J.C. van Gemund. A Low-Cost Approach towards Mixed Task and Data Parallel Scheduling // ICPP. 2001. P. 69-76
6. Buyya, Rajkumar. High Performance Cluster Computing : Architectures and Systems, Volume 1 // Prentice Hall. 1999.
7. GCC, the GNU Compiler Collection [PDF] (http://gcc.gnu.org/onlinedocs/gcc-4.5.0/gcc.pdf )
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
