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

В любом традиционном языке  объектно-ориентированного программирования, таком, как например, 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 )

{

return x;

}

}

 

2) “Линейный алгоритм”

class Fib {

public static int threshold = 30;

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

if ( n < threshold )

sendResult(cfib( n ) );

else {

newFib().Compute( n – 1, c );

sendResult(cfib( n – 2 ) + Get() );

   }

}

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

{

return ( x );

   }

Private int cfib( int n ) {

if ( n <= 1 )

return ( 1 );

else

return ( cfib( n – 1 ) + cfib( n – 2 ) );

  }

}

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 )

 {

return x;

}

}

Ниже приведены графики  времени выполнения последовательной программы и распределенного, “линейного”  варианта программы Fibс threshold = 36. Причем количество используемых процессоров в распределенном варианте определялось как n – 34 (для n>= 35 ). Тестовые замеры проводились на кластере с процессорами AMD Athlon(TM) MP 1800+.

Рис. 11. Время вычисления N-го числа Фибоначчи “линейным” алгоритмом.

 

3.5.2 Быстрое преображение Фурье

Комплексное число 

ω_n= e^{2πi / n}

называется главным значением корня степени nиз единицы.

Вектор y=(y₀, y₁, … , y_n-1) называется дискретным преобразованием Фурье вектора a=(a₀, a₁, … , a_n-1), где a_i и y_j( 0 ≤ i, j ≤ n )есть комплексные числа, если

y_k = Σ_0≤j≤n-1a_jω_n^kj

для k = 0, 1, … , n – 1.

Быстрое преобразование Фурье (БПФ) представляет собой метод быстрого вычисления дискретного преобразования Фурье, использующий свойства комплексных  корней из единицы и требующий  времени O(nlogn), в отличие от времени O(n²) при прямом вычислении по формуле.

В случае, когда nесть степень двойки, имеется следующий алгоритм быстрого преобразования Фурье вектора a=(a₀, a₁, … , a_n-1):

 

1) Рекурсивный алгоритм

using System;

public class Complex {

 

public double Re = 0.0;

public doubleIm = 0.0;

public Complex () {}

public Complex ( double re, doubleim )  {

  Re = re;

Im = im;

}

}

public class FFT   {

public static void Main ( String[] args )   {

int     i;

int N = System.Convert.ToInt32 ( args [0] ); //  N is power of 2

  Random r = new Random();

Complex[]  a = new Complex [ N ];

Complex[]  y = new Complex [ N ];

for ( i = 0; i < N; i++ )   {

a [ i ] = new Complex ( r.NextDouble(), r.NextDouble() );

y [ i ] = new Complex ();

  }

FFT  fft = new FFT();

DateTime dt1 = DateTime.Now;

int   N2 = N / 2;

Complex[] a0 = new Complex [ N2 ];

Complex[] a1 = new Complex [ N2 ];

Complex[] y0 = new Complex [ N2 ];

Complex[] y1 = new Complex [ N2 ];

for ( i = 0; i < N; i += 2 )   {

   a0 [ i / 2 ] = a [ i ];

   a1 [ i / 2 ] = a [ i + 1 ];

   y0 [ i / 2 ] = new Complex();

   y1 [ i / 2 ] = new Complex();

  }

fft.FFT_Async( N2, a0, y0, fft.sendStop );

fft.FFT_Async( N2, a1, y1, fft.sendStop );

for ( i = 0; i < 2; i++ )

fft.getStop();

fft.merge( N, y0, y1, y );

DateTime dt2 = DateTime.Now;

Console.WriteLine( " N = " + N + "   Elapsed time is " + (dt2-dt1).TotalSeconds );

}

Handler getStop void()   &channel sendStop()  {

return;

}

Public async FFT_Async ( int N, Complex[] a, Complex[] y, сhannel () sendStop )   {

Recursive_FFT( N, a, y );

sendStop();

}

public void Recursive_FFT ( int N, Complex[] a, Complex[] y )   {

int   i;

if ( N == 1 )   {

y [ 0 ] = a [ 0 ];

return;

  }

int   N2 = N / 2;

Complex[] a0 = new Complex [ N2 ];

Complex[] a1 = new Complex [ N2 ];

Complex[] y0 = new Complex [ N2 ];

Complex[] y1 = new Complex [ N2 ];

for ( i = 0; i < N; i += 2 )   {

   a0 [ i / 2 ] = a [ i ];

   a1 [ i / 2 ] = a [ i + 1 ];

   y0 [ i / 2 ] = new Complex();

   y1 [ i / 2 ] = new Complex();

  }

Recursive_FFT( N2, a0, y0 );

Recursive_FFT( N2, a1, y1 );

merge ( N, y0, y1, y );

}

public void merge (int N, Complex[]y0, Complex[] y1, Complex[] y )     {

double wy_Re, wy_Im, tmp;

double w_Re, w_Im, wn_Re, wn_Im;

int      i;

wn_Re    = Math.Cos( 2.0 * Math.PI / N );

wn_Im    = Math.Sin( 2.0 * Math.PI / N );

w_Re     = 1.0;

w_Im     = 0.0;

int      N2 = N / 2;

for ( i = 0; i < N2; i++ )   {

wy_Re = w_Re * y1 [ i ].Re - w_Im * y1 [ i ].Im;

wy_Im = w_Re * y1 [ i ].Im + w_Im * y1 [ i ].Re;

y [ i ].Re = y0 [ i ].Re + wy_Re;

y [ i ].Im = y0 [ i ].Im + wy_Im;

y [ i + N2 ].Re = y0 [ i ].Re - wy_Re;

y [ i + N2 ].Im = y0 [ i ].Im - wy_Im;

tmp  =w_Re * wn_Re - w_Im * wn_Im;

w_Im = w_Re * wn_Im + w_Im * wn_Re;

w_Re = tmp;

  }

}

 

 

2) Итеративный алгоритм

 

using System;

public class Complex {

public double Re = 0.0;

public doubleIm = 0.0;

public Complex () {}

public Complex ( double re, double im )  {

  Re = re;

Im = im;

}

}

public class IFFT   {

public static void Main ( String[] args )   {

int N = System.Convert.ToInt32 ( args [ 0 ] ); //  N is power of 2

  Random r = new Random();

Complex[]  a = new Complex [ N ];

Complex[]  A = new Complex [ N ];

for ( int i = 0; i < N; i++ )

a [ i ] = new Complex ( r.NextDouble(), r.NextDouble() );

DateTime dt1 = DateTime.Now;