Аннотация

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

Оглавление

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 Схема работы средства

6.4 Характеристики функционирования

7 Заключение

8 Список цитируемой литературы

1       Введение

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

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

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

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

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