1. Введение........................................................................................... 3

1.1. Параллельные вычислительные системы.......................................................... 3

1.2. Язык C-DVM............................................................................................................... 4

1.3. Задача оптимизации производительности и ее значение............................... 5

1.4. Обзор существующих решений............................................................................. 8

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

1.6. Особенности реализации...................................................................................... 12

2. Описание алгоритма............................................................. 13

2.1. Исходные данные и результаты работы............................................................ 13

2.2. Моделирование....................................................................................................... 14

2.2.1. Вычисляемые характеристики и их компоненты............................................. 14

2.2.2. Общие принципы моделирования......................................................................... 17

2.2.3. Обычные функции.................................................................................................. 18

2.2.4. Функции начала/конца интервала....................................................................... 19

2.2.5. Функции ввода/вывода данных............................................................................. 20

2.2.6. Функции, связанные с передачей сообщений....................................................... 21

2.2.7. Функции создания/уничтожения объектов........................................................ 22

2.2.8. функции распределения ресурсов и данных......................................................... 26

2.2.9. Функции инициализации коллективных операций.............................................. 29

2.2.10. Функции выполнения коллективных операций................................................. 30

2.2.11. Функции параллельного цикла............................................................................ 34

2.2.12. Неизвестные функции......................................................................................... 35

3. Заключение.................................................................................. 36

3.1. Текущая реализация.............................................................................................. 36

3.2. Возможные направления развития.................................................................... 36

4. Список литературы................................................................. 37

5. Приложения................................................................................. 38

5.1. Приложение 1. Исходные тексты классов для моделирования распределения витков параллельного цикла....................................................................................................... 38

5.1.1. Классы LoopLS и LoopBlock.................................................................................. 38

5.1.2. Класс ParLoop........................................................................................................ 42

5.2. Приложение 2. Сравнение прогноза и реальных характеристик на МПС размера 2x2 (кластер рабочих станций SGI)...................................................................................... 45

5.2.1. Результат прогнозирования................................................................................. 45

5.2.2. Реальные характеристики выполнения.............................................................. 52

1. Введение

   1. Параллельные вычислительные системы.

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

• SIMD (Single Instruction, Multiple Data) – системы с параллелизмом по данным при отсутствии функционального параллелизма;
• MIMD (Multiple Instructions, Multiple Data) – системы с комбинированным параллелизмом;
• MISD (Multiple Instructions, Single Data) – системы с функциональным параллелизмом при отсутствии параллелизма по данным (нет ни одной реализации).

По организации памяти параллельные вычислительные системы разделяют на системы с общей памятью и системы с распределенной памятью.

Вычислительные программы для параллельных вычислительных систем с распределенной памятью (транспьютерные системы, Intel Paragon, IBM SP2, МВС-100) и сетей в настоящее время, как правило, создаются на языках Фортран 77 и Си, расширенных библиотеками передачи сообщений (PVM, MPI). Разработка таких параллельных программ требует от прикладного программиста значительно больших усилий, чем разработка последовательных программ, поскольку ему требуется не только распределить данные и вычисления между разными процессорами, но и организовать взаимодействие процессоров посредством обмена сообщениями. Фактически, параллельная программа представляет собой систему взаимодействующих программ, каждая из которых выполняется на своем процессоре. Программы на разных процессорах могут быть совершенно различными, могут различаться лишь незначительно, а могут являться одной программой, поведение которой зависит от номера процессора. Но даже в этом последнем случае, программист обычно вынужден разрабатывать и сопровождать два различных варианта своей программы - последовательный и параллельный.

Учитывая данные факторы, вполне закономерным представляется появление языков для разработки мобильных параллельных программ. Одним из таких языков является язык C-DVM.

1. Язык C-DVM.

Язык C-DVM предназначен для разработки мобильных и эффективных параллельных программ вычислительного характера. Он представляет собой расширение языка Си в соответствии с моделью DVM (Distributed Virtual Machine, Distributed Virtual Memory), разработанной в ИПМ им М.В. Келдыша РАН.

При использовании языка C-DVM программист имеет только один вариант программы и для последовательного и для параллельного выполнения. Эта программа, помимо описания алгоритма обычными средствами языка Си, содержит правила параллельного выполнения этого алгоритма. Эти правила оформляются синтаксически таким образом, что они являются «невидимыми» для стандартных компиляторов с языка Си для последовательных ЭВМ и не препятствуют выполнению и отладке CDVM-программы на рабочих станциях как обычной последовательной программы.

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

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

Текущая версия языка поддерживает только параллелизм по данным (параллельно выполняются витки одного цикла).