Архитектура параллельных вычислений

         В случае языка MC#, программист может предусмотреть исполнение автономных асинхронных методов либо локально, либо удаленно. В последнем случае, метод может быть спланирован для исполнения на другой машине, выбираемой двумя способами: либо согласно явному указанию программиста (что не является типичным случаем), либо автоматически (обычно, на наименее загруженном узле кластера или машине Grid-сети). Взаимодействие асинхронных методов, в рамках языка MC#, реализуется посредством передачи сообщений с использованием каналов и обработчиков канальных сообщений. Эти каналы и обработчики определяются в MC#-программах с помощью связок в стиле языка Polyphonic C#.

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

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

         Разделение всех методов в программе на обычные (синхронные) и асинхронные производится программистом с использованием специальных ключевых слов async и movable. (В языке MC#, семантика и использование ключевого слова async полностью совпадает с использованием этого слова в языке Polyphonic C# за тем исключением, что в MC# async-методы не могут встречаться в связках – см. об этом ниже). 

async- и movable-методы, каналы, обработчики связки 

         Async- и movable- методы являются единственным средством создания параллельных процессов (потоков) в языке MC#.

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

         Общий синтаксис  определения async- и movable-методов в языке MC# следующий:

   модификаторы {async | movable} имя_метода (аргументы)

   {

               <тело метода>

   }

         Ключевые слова  async и movable располагаются на месте типа возвращаемого значения, поэтому синтаксическое правило его задания при объявлении метода в языке MC# имеет вид:

         return-type::= type | void | async | movable

         Задание ключевого  слова async означает, что при вызове данного метода он будет запущен в виде отдельного потока локально, т.е., на данной машине, но без перемещения на другую машину. Ключевое слово movable означает, что данный метод при его вызове может быть спланирован для исполнения на другой машине. Как обычно, для любого параллельного языка программирования, реализация MC# состоит из компилятора и рантайм-системы. Главными функциональными частями рантайм-системы являются:

1. ResiurceManager – процесс, исполняющийся на центральном узле и распределяющий по узлам movable-методы.
2. WorkNode – процесс, исполняющийся на каждом из рабочих узлов и контролирующий выполнение movable-методов.
3. Communicator – процесс, исполняющийся на каждом из узлов и ответственный за принятие сообщений для объектов, расположенных на данном узле.

      Компилятор  переводит программу из MC# в C#, его  главной целью является создание кода, реализующего: 1) выполнение movable-методов  на других процессорах, 2) пересылку  канальных сообщений и 3) синхронизацию  методов, объединённых связкой. Эти  функции предоставляются соответствующими методами классов рантайм-системы. Среди них:

1. класс Session – реализует вычислительную сессию.
2. класс TCP – предоставляет возможность доставки запросов на исполнение movable-методов и канальных сообщений.
3. класс Serialization – предоставляет сериализацию/десериализацию объектов, перемещаемых на другие рабочие узлы.
4. класс Channel – содержит информацию о канале.
5. класс Handler– содержит информацию об обработчике.

Главные функции  компилятора MC#:

1. Добавление вызовов функций Init() и Finalize() класса Session в главном методе программы. Функция Init() доставляет исполняемый модуль программы на другие узлы, запускает процесс Manager, создаёт объекты LocalNode и другие. Функция Finalize() останавливает запущенные потоки и завершает вычислительную сессию.
2. Добавление выражений, создающих объекты типа сhannel и handler для каждого из каналов и обработчиков, описанных в программе.
3. Замена вызовов async-методов на порождение соответствующих локальных потоков.
4. Замена вызовов movable-методов на запросы менеджеру распределения ресурсов.
5. Замена канальных вызовов на пересылку соответствующих сообщений по TCP-соединению. Трансляция связок, содержащих определения каналов, производится так же, как и в языке Polyphonic C#.

 

3.3 Параллельные библиотеки

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

ATLAS

ATLAS (Automatically Tuned Linear Algebra Software) - библиотека, позволяющая  автоматически генерировать и  оптимизировать численное программное  обеспечение для процессоров  с многоуровневой организацией  памяти и конвейерными функциональными  устройствами. ATLAS требует некоторого  времени для изучения основных  параметров архитектуры целевого  компьютера, а затем на основе  этих параметров получает "оптимальный"  код. 

Aztec

Aztec - параллельная  библиотека итерационных методов  для решения систем линейных  уравнений. Позволяет описывать  части распределенной матрицы  с использованием глобальной  адресации. 

DOUG

DOUG (Domain decomposition On Unstructured Grids) - параллельный  решатель для finite element - систем, возникающих  из дифференциальных уравнений  с частными производными эллиптического  типа.

GALOPPS

GALOPPS (Genetic ALgorithm Optimized for Portability and Parallelism System) - библиотека "обобщенных" генетических алгоритмов. Доступна многопоточная версия.

JOSTLE

JOSTLE - библиотека для распределения расчетов на сетках (mesh partitioning software). Реализована на С с помощью MPI.

NAMD

NAMD - параллельная  объектно-ориентированная библиотека  для расчетов в области молекулярной  динамики. Реализована на С++ с использованием шаблонов, а также Charm++ и Converse.

ParMETIS

PARMETIS - параллельная версия библиотеки METIS, включающей ряд алгоритмов над графами (parallel graph partitioning). Реализована с помощью MPI.

PETSc

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

ScaLAPACK

Библиотека ScaLAPACK включает подмножество процедур LAPACK, переработанных для использования  на MPP-компьютерах, включая: решение  систем линейных уравнений, обращение  матриц, ортогональные преобразования, поиск собственных значений и  др. Может быть портирована на любую  платформу, где поддерживается PVM или MPI. 

3.4 Классы задач, решаемые с помощью параллелизма 

3.5 Примеры решения задач

      3.5.1 Вычисление чисел Фибоначчи

   Последовательность  чисел Фибоначчи есть бесконечный  ряд из натуральных чисел

      a₀, a₁, a₂, a₃, . . .

таких, что

      a₀ = 1,

      a₁ = 1, и

      a_i = a_i-1 + a_i-2,  для  i ³ 2.

         Построим параллельную программу, находящую -ое ( ³ ) число в ряду Фибоначчи, т.е., элемент a_nпоследовательности.

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

1. Базовый алгоритм

 

   class Fib {

   public async Compute( int x, channel (int)sendResult ) {

   if ( n <= 1 )

   sendResult ( 1 );

   else {

   new Fib().Compute( n – 1, ic1 );

   new Fib().Compute( n – 2, ic2 );

   sendResult ( Get() );

      }

    }

   Handler Get int() &channel ic1( int x )

   &channel ic2(int y )

    {

   return x + y;

    }

}

   public class MainFib {

   public static void Main( String[] args ) {

   int n = System.Convert.ToInt32( args [0] ); // n естьномер

   // искомого числа Фибоначчи ( n>= 1 )

   MainFibmfib = new MainFib(); // Создание объекта

   // необходимо для создания его  каналов 

   // и обработчиков

   Fib fib = new Fib();

   fib.Compute( n, mfib.senResult );

   Console.WriteLine( “For n = “ + n + “ value is “ +

   mfib.Get() );

    }

   handler Get int() &channel sendResult( int x )