Тема : “Автоматическое распараллеливание программ для распределенных систем. Планирование распределения данных и вычислений”.

Научный руководитель — д. ф.-м. н. В.А. Крюков.

Введение

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

Рассмотрим основные этапы развития параллелизма с момента изобретения компьютеров :

• введено арифметическое устройство для плавающей арифметики (IBM 704, 1955 г.)
• разработаны контролеры ввода-вывода, освобождающие процессор от необходимости обработки этих операций (IBM 709, 1958 г.)
• память разбита на несколько блоков (их часто называют “банками” памяти), так, что идущие подряд команды попадают в разные блоки, что позволяет намного ускорить их выборку. Реализован опережающий просмотр команд вперед (STRETCH, 1961 г.)
• независимые функциональные устройства. Конвейерная обработка команд. Режим зацепления функциональных устройств. (CDC 7600, 1969 г. CRAY1, 1976 г.)
• появляются компьютеры, обьединяющие в себе несколько процессорных элементов (ILLIAC4, 1975 г, матрица 8*8 процессоров.)

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

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

Нашей задачей является разработка системы, цель

которой - автоматический перевод программ с FORTRAN-77 на параллельный DVM Fortran. Целью дипломной работы является этап, когда, на основании информации о циклах, массивах и зависимостях, принимается решение о распределении данных и вычислений по процессорам. Вычисления распараллеливаются путем распределения итераций циклов по процессорным элементам. При этом используются вычислительные оценки времени перераспределения данных и выполнения цикла при заданном распределении массивов. Особенность распределенной системы состоит в необходимости согласованного распределения вычислений и данных.