Е.С.Борисов
четверг, 9 сентября 2004 г.
Существуют задачи, не решаемые на серийных персональных компьютерах за приемлемое время, к примеру прогнозирование погоды, моделирование процессов разрушения в механике (crash-тесты)[ 1 ]. Для решения таких задач используют многопроцессорные (параллельные) вычислители. Множество архитектур параллельных вычислителей весьма обширно. Основной характеристикой при классификации [ 2 ] параллельных вычислительных систем является способ организации памяти :
Для параллельных вычислительных систем необходимо создавать специальные программы. В тексте такой программы определяются части (ветки), которые могут выполнятся параллельно, а также алгоритм их взаимодействия.
Основным параметром оценки работы параллельной системы является коэффициент ускорения [ 4 ] :
(1) |
где - время выполнения программы на процессорах.
Эффективность выполнения программы на параллельном вычислителе, в первую очередь, зависит от меры распараллеливания самой задачи, описываемой программой. Параллельные программы, вообще говоря, являются архитектурно зависимыми.
Оценить максимально возможное ускорение для данной программы можно, используя закон Амдала [ 3 ] :
где - доля последовательных операций в параллельной программе, - количество процессоров.
Приведем краткое описание технологий параллельных вычислений. Средства параллельных вычислений можно разделить на три уровня :
Выделяют следующие классы параллельных систем.
При написании параллельных программ можно пользоваться коммуникационными библиотеками. Такие библиотеки реализуют методы запуска и управления параллельными процессами, обычно они содержат функции обмена данными между ветвями параллельной программы, функции синхронизации процессов.
Соответственно типу организации памяти, существует два основных типа коммуникационных библиотек [ 5 ] и интерфейсов параллельного программирования :
Надо отметить, что одно может быть сымитировано через другое :
Существует множество библиотек и интерфейсов параллельного программирования. Отметим наиболее популярные из них.
Параллельные программы можно писать ''вручную'', непосредственно вставляя в нужные места вызовы коммуникационной библиотеки. Этот путь требует от программиста специальной подготовки. Альтернативой является использование систем автоматического и полуавтоматического распараллеливания последовательных программ.
Дискретная динамическая система (ДДС, transition systems) представляет собой тройку :
где
Алгебра алгоритмов Глушкова [ 7 ] определяется следующим образом. Введем три множества :
Алгеброй алгоритмов назовем пару :
где
В алгебре алгоритмов ( 3 ) определены следующие операции :
где - операторы, - состояние памяти, - условие
где - оператор, - состояние памяти, - условие
В алгебре операторов выделяется множество базовых операторов, а в алгебре условий выделяется множество базовых условий. Таким образом, порождается алгебра алгоритмов .
Регулярное выражение в назовём регулярной программой .
Сформулируем постановку задачи: построить полуавтоматическую систему распараллеливания последовательных программ для параллельных вычислителей с распределенной памятью.
Система полуавтоматического распараллеливания описывается тремя алгебродинамическими моделями :
В основе, представленной ниже, системы полуавтоматического распараллеливания лежат асинхронный вызов подпрограммы и принцип неготового значения[ 8 ]. При асинхронном вызове подпрограммы из процесса , выполняющего подпрограмму происходят такие события (рис. 2 ) :
Определим последовательную многокомпонентную программу как упорядоченное множество пар . Каждая такая пара определяет подпрограмму в :
где - i-тая подпрограмма
Введем операторы вызова подпрограммы и возврата из подпрограммы .
Процесс выполнения последовательной многокомпонентной программы описывается дискретной динамической системой :
Здесь
Введем понятие параллельной программы и определим его как упорядоченое множество пар . Каждая такая пара определяет параллельный процесс :
где
Определим два типа операторов обмена данными между компонентами параллельной программы :
Назовем элементарными операторами все операторы, не являющиеся операторами обмена данными между компонентами параллельной программы.
Процесс выполнения последовательной многокомпонентной программы описывается дискретной динамической системой :
где
Полуавтоматическая система распараллеливания последовательных программ описывается следующей дискретной динамической системой :
Здесь
где
введём обозначения :
где
где
где
Опишем реализацию транслятора-распараллеливателя для языка C.
Вычислительные системы сверхвысокой производительности стоят дорого. Цена таких систем недоступна для большинства образовательных и научно-исследовательских организаций, но часто существует приемлемая альтернатива - кластер. При достаточном числе узлов, такие системы способны обеспечить требуемую производительность.
Можно использовать уже существующую сеть рабочих станций (системы такого типа иногда называют COW - Cluster Of Workstations). При этом узлы могут иметь различную архитектуру, производительность, работать под управлением разных OC (MS Windows, Linux, FreeBSD).
Если узлы планируется использовать только в составе кластера, то их можно существенно облегчить (отказаться от жёстких дисков, видеокарт, мониторов и т.п.). В облегчённом варианте узлы будут загружаться и управляться через сеть. Количество узлов и требуемая пропускная способность сети определяется задачами, которые планируется запускать на кластере.
Message Passing Interface (MPI) - популярный стандарт для построения параллельных программ по модели обмена сообщениями. Этот стандарт обычно используют в параллельных системах с распределённой памятью (кластера и т.п.).
MPI содержит в себе разнообразные функции обмена данными, функции синхронизации параллельных процессов, механизм запуска и завершения параллельной программы. Стандарт MPI-1 описывает статическое распараллеливание, т.е. количество параллельных процессов фиксировано, это ограничение устранено в новом стандарте MPI-2, позволяющем порождать процессы динамически. MPI-2 в настоящее время находится в стадии разработки.
Разными коллективами разработчиков написано несколько программных пакетов, удовлетворяющих спецификации MPI (MPICH, LAM, HPVM etc.). Существуют стандартные ''привязки'' MPI к языкам С, С++, Fortran 77/90, а также реализации почти для всех суперкомпьютерных платформ и сетей рабочих станций.
В данной работе для прогона контрольных примеров был использован кластер на основе сети персональных компьютеров и библиотека MPICH (http://www-unix.mcs.anl.gov/mpi/mpich), созданная авторами спецификации MPI. Этот пакет можно получить и использовать бесплатно. В состав MPICH входит библиотека программирования, загрузчик приложений, утилиты. Существуют реализации этой коммуникационной библиотеки для многих UNIX-платформ, MS Windows.
Для запуска MPI-программ на гомогенном (состоящего из одинаковых узлов, работающих под одной OS) кластере необходимо выполнить следующие шаги.
Для обеспечения более высокого уровня сетевой безопасности можно использовать ssh - OpenSSH remote login client.
Вместо процедуры копирования программы на узлы можно использовать NFS (Network File System) :
После команды mpirun , MPICH, используя rsh , запускает n -раз программу myprog на машинах из machines . При запуске каждому процессу присваивается уникальный номер, и далее программа работает исходя из этого номера.
Используя MPI, можно писать эффективные параллельные программы, но непосредственное программирование в MPI имеет ряд недостатков. MPI можно назвать ассемблером виртуальной многопроцессорной машины. Написание MPI-программ требует от программиста специальной подготовки. Кроме того, MPI-программы, как средство низкого уровня, являются, в значительной мере, архитектурно зависимыми, что затрудняет их переносимость. Описанная система полуавтоматического распараллеливания позволяет решить эти проблемы.
Реализация транслирует программу на расширенном языке C в параллельную MPI-программу на C.
Для того что бы воспользоваться системой полуавтоматического распараллеливания , необходимо выполнить следующие шаги.
asyncron int my_big_func() { /* just do it :) */ return 0; }Вызов такой функций порождает новый параллельный процесс. Таким образом - количество компонент параллельной программы определяется количеством вызовов асинхронных функций.
$ delta myprog.c > myprog_mpi.c components : 4 $ mpicc myprog_mpi.c -o myprog_mpi $ mpirun -machinefile machines -np 4 myprog_mpi
Важной особенностью данной системы является ''гладкий синтаксис''. Введение ключевого слова asyncron является единственным отличием языка C от стандартного C. Программа для распараллеливателя может, без каких либо изменений, собираться обычным (последовательным) транслятором языка C, достаточно добавить в заголовок программы #define asyncron , в этом случае получается обычная (последовательная) программа.
Распараллеливатель можно получить [ здесь ]
Рассмотрим классический пример параллельного программирования - вычисление . Число будем вычислять как определенный интеграл :
Согласно правилу прямоугольников интеграл можно заменить суммой:
$ cc pi.c -o pi $ ./pi pi = 3.1415926535899708
$ delta pi.c > pi_mpi.c components : 3 $ mpicc pi_mpi.c -o pi_mpi $ mpirun -machinefile machines -np 3 pi_mpi pi = 3.1415926535899708
Параллельная MPI-программа вычисления , результат работы распараллеливателя -- [ pi_mpi.c ]