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

  IFFT ifft = new IFFT();

Int logN = 0;

int m    = N;

while ( m > 1 )

  {

   m = m / 2;

logN++;

  }

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

   A [ ifft.bit_reverse ( k, logN ) ] = a [ k ];

int N2 = N / 2;

ifft.Iterative_FFT( a, A, N2, logN, 0,  ifft.sendStop );

ifft.Iterative_FFT( a, A, N2, logN, N2, ifft.sendStop );

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

ifft.getStop();

//   Final iteration

Double wn_Re, wn_Im, w_Re, w_Im;

Double arg, t_Re, t_Im;

Double u_Re, u_Im, tmp;

int    jN2;

arg = 2.0 * Math.PI / N;

wn_Re = Math.Cos( arg );

wn_Im = Math.Sin( arg );

w_Re  = 1.0;

w_Im  = 0.0;

for ( int j = 0; j < N2; j++ )

  {

jN2  = j + N2;

t_Re = w_Re * A [ jN2 ].Re - w_Im * A [ jN2 ].Im;

t_Im = w_Re * A [ jN2 ].Im + w_Im * A [ jN2 ].Re;

u_Re = A [ j ].Re;

u_Im = A [ j ].Im;

   A [ j ].Re = u_Re + t_Re;

   A [ j ].Im = u_Im + t_Im;

   A [ jN2 ].Re = u_Re - t_Re;

   A [ jN2 ].Im = u_Im - t_Im;

tmp  =w_Re * wn_Re - w_Im * wn_Im;

w_Im = w_Re * wn_Im + w_Im * wn_Re;

w_Re = tmp;

  }

DateTime dt2 = DateTime.Now;

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

}

Handler getStop void()   &channel sendStop()  {

return;

}

Public int bit_reverse ( int k, int size )   {

Int right_unit = 1;

Int left_unit  = 1 << ( size - 1 );

int   result     = 0;

int   bit;

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

  {

bit = k &right_unit;

if ( bit != 0 )

result = result | left_unit;

right_unit = right_unit<< 1;

left_unit  =left_unit>> 1;

  }

return ( result );

 

}

Public async Iterative_FFT ( Complex[] a, Complex[] A, int N2,     int log N, int shift, channel() sendStop                         )

{

int    j, k, m, m2, km2, s;

double wn_Re, wn_Im, w_Re, w_Im;

double arg, t_Re, t_Im;

double u_Re, u_Im, tmp;

for ( s = 1; s <logN; s++ )

  {

   m = 1 << s;

arg = 2.0 * Math.PI / m;

wn_Re = Math.Cos( arg );

wn_Im = Math.Sin( arg );

w_Re  = 1.0;

w_Im  = 0.0;

   m2    = m >> 1;

for( j = 0; j < m2; j++ )

for ( k = j + shift; k < N2; k += m )

    {

km2  = k + m2;

t_Re = w_Re * A [ km2 ].Re - w_Im * A [ km2 ].Im;

t_Im = w_Re * A [ km2 ].Im + w_Im * A [ km2 ].Re;

u_Re = A [ k ].Re;

u_Im = A [ k ].Im;

     A [ k ].Re = u_Re + t_Re;

     A [ k ].Im = u_Im + t_Im;

     A [ km2 ].Re = u_Re - t_Re;

     A [ km2 ].Im = u_Im - t_Im;

tmp  =w_Re * wn_Re - w_Im * wn_Im;

w_Im = w_Re * wn_Im + w_Im * wn_Re;

     w_Re = tmp;

    }

  }

sendStop ();

}

}

Ниже представлены графики  времени исполнения последовательного  и итеративного параллельного (на 2 процессора) алгоритмов БПФ, реализованных  на языке MC#.

Тестовые замеры проводились  на машине с двухъядерным процессором Intel Core 2 Duo 2.4 GHz  и оперативной памятью 1 Гб.

 

Рис. 12. Время исполнения последовательного и параллельного  алгоритмов БПФ.

 

3.5.3 Построения списка простых чисел методом “решета Эратосфена”

1. Наивный алгоритм

По условию задачи, по заданному натуральному числу N ³ 2, необходимо найти все простые числа в интервале от 2 до N.

Метод просеивания состоит  из следующих шагов:

1) из исходного списка  l₀ всех натуральных чисел от 2 до N

l₀ = [2, … , N]

выбирается первое число  этого списка, а именно 2, и выдается в качестве первого выходного  значения;

2)  затем  строится  новый список l₁ , который получается из списка l₀ вычеркиванием из него всех чисел, кратных  очередному выбранному простому числу – на первом шаге, числу 2:

l₁ = [3, 5, 7, … , N]   (в предположении, что N нечетно)

затем данная процедура повторяется  рекурсивно для вновь построенного списка.

Алгоритм заканчивает  свою работу, когда очередной список оказывается пустым.

 

Class Eratosthenes   {

public static void Main(String[] args) {

intN = System.Convert.ToInt32 (args[0] );

  Eratosthenes E = new Eratosthenes();

New CSieve().Sieve ( E.getNat, E.sendPrime );

for ( int n=2; n <= N; n++ )

E.Nats( n );

E.Nats( -1 );

while (  ( intp = E.getPrime() ) != -1 )

Console.WriteLine( p );

}

Handler getNat int()  &channel Nats ( int n ) {             

return( n );

}

Handler getPrime int()&channel sendPrime( int p ) {     

return( n );

}

} 

Class CSieve  {

async Sieve ( handlerint() getList, channel (int) sendPrime ) {

int  p = getList();

sendPrime ( p );

if  ( p != -1 )   {

new CSieve().Sieve ( hin, sendPrime );

filter ( p, getList, cout );

  }

}

Handler hin int()  &channel cout ( int x ) {

return ( x );

}

Void filter (int p, handlerint() getList,

channel(int) cfiltered )   {

while( ( int n = getList() ) != -1 )

if( n % p != 0 ) cfiltered ( n );

cfiltered ( -1 );

}

}

 

2. Пакетный алгоритм

В данном разделе описывается  модификация наивного алгоритма  “решето Эратосфена”, существенно  улучшающая эффективность параллельной (распределенной) программы, и которая  дает существенное ускорение при  поиске простых чисел в длинных  интервалах (например, для N ≥ 10⁶).

Основная  идея предлагаемого  алгоритма заключается  в переходе от использования потоков одиночных  данных (потоков отдельных натуральных  чисел) к потокам пакетов натуральных  чисел.

Пакет – это массив натуральных чисел фиксированного размера (задаваемого в программе значением PACKAGE_SIZE), пустые хвостовые элементы которого заполняются нулями.

При этом, функции наивного алгоритма обобщаются в данном варианте естественным образом:

Async Sieve(handlerint[]() getNatPack, channel (int[]) sendPrimesPack) — с помощью обработчика getNatPack получает первый пакет из потока, обрабатывает его функцией SynchronousSieve, получая пакет простых чмселhead, и отправляя его по каналу sendPrimesPack; остальные пакеты из входного потока фильтруются с помощью функции filter по модулю пакета head и направляются на вход следующей в цепочке рекурсивной функции Sieve;

Void filter(int[] head, handlerint[] () getNatPack, channel(int[]) cfiltered) — функция, которая фильтрует пакеты из входного потока, получаемые с помощью обработчика getNatPack, по модулю пакета простых чисел head, отправляя результирующие пакеты в канал cfiltered; при этом, все результирующие пакеты (кроме, может быть, последнего) имеют длину PACKAGE_SIZE (строго говоря, и последний пакет имеет длину PACKAGE_SIZE, но его хвостовая часть может быть заполнена нулями).

 

Using System;

Using System.Text;

public class Config {

public static int N = 1000000;

public static int MAX_LEN = 50000;

public static void print(int[] a) {

StringBuildersb = new StringBuilder();

sb.Append("---------------------------------------------\n");

for(int i = 0; i<a.Length&& a[i]!=0; i++) sb.Append(a[i]+" ");

Console.WriteLine(sb.ToString());

}

}

Public class CSieve

{

// Функция, реализующая  стандартный алгоритм "Решето //Эратосфена"

Private int[] SynchronousSieve(int[] ar)

    {

if (ar == null || ar.Length == 0) return new int [ 0 ];

int[] primes = (int[]) Array.CreateInstance(typeof(int), Config.MAX_LEN);

int ind = 0;

primes[0] = ar[0];

for(int i = 1; i <ar.Length; i++)

        {

if(isPrime(ar[i],primes)) primes[++ind] = ar[i];

}

Return primes;

    }

// Функция,проверяющаячислонапростоту

Private bool isPrime(int n, int[]primes)

    {

Bool isPrime = true;

for(int j = 0; isPrime&& j <primes.Length&&                    primes[j]!=0 && primes[j]*primes[j] <= n; j++)

isPrime = (n % primes[j] != 0);

return isPrime;

    }

Async Sieve(handlerint[]() getNatPack, channel (int[]) sendPrimesPack)

{

// Получаем первый  пакет из входного потока и

        // извлекаем из него подпакет  простых чисел

int[] head = SynchronousSieve((int[])getNatPack());

// Посылаем пакет  простых чисел в выходной поток

sendPrimesPack(head );

// Фильтруем оставшиеся  пакеты входного потока

        // относительно пакета head

if ( head.Length != 0 )

{

New CSieve().Sieve( inter,sendPrimesPack);

filter ( head, getNatPack, cout );

        }

    }

Handler inter int[]()  &channel cout ( int[] p) {

return ( x );

    }

// Фильтрацияпотоков

void filter(int[] head, handler int[] () getNatPack, channel (int[]) cfiltered)

    {

int[] al =   (int[])Array.CreateInstance(typeof(int),Config.MAX_LEN);

int ind = 0;

// Для каждого  пакета из входного потока

for( int[] p; (p = (int[])getNatPack() ).Length != 0;)

        {

// Выбираем простые  числа, формируя новый пакет

for(int i = 0; i <p.Length&& p[i]!=0; i++)

            {

if(isPrime(p[i],head))

{

al[ind++] = p[i];

 

// Если пакет  заполнен, то посылаем его

                    // в поток отфильтрованных пакетов

if(ind == Config.MAX_LEN)

{

ind = 0;

cfiltered (al);

al = (int[])Array.CreateInstance(typeof(int),Config.MAX_LEN);

}

                }

            }

        }

// Посылаем последний  пакет в поток

        // отфильтрованных пакетов

if(al[0] != 0) cfiltered (al);

// Посылаем маркер  конца потока пакетов      

cfiltered(new int [ 0 ] );

    }

Class Eratosthenes2   {

public static void Main(String[] args) {

   Eratosthenes2 er2 = new Eratosthenes2();

CSievecsieve = new CSieve();

// Запускаемметод Sieve

csieve.Sieve( er2.getNatPack, er2.sendPrimePack);

int[] al =   (int[])Array.CreateInstance(typeof(int),Config.MAX_LEN);

// Создаем поток  пакетов натуральных чисел

for (inti = 2; i<= Config.N; i++)

{

intind = (i-2)%Config.MAX_LEN;

al[ind] = i;

if(ind == Config.MAX_LEN - 1)

            {

                er2.Nats ( al );

al = (int[])Array.CreateInstance(typeof(int),Config.MAX_LEN);

            }

        }

if(al[0] != 0)

er2.Nats(al);

        er2.Nats ( newint [ 0 ] );

int[] p;

// Распечатываем  результирующие пакеты простых  чисел

while (( p = (int[])er2.getPrimePack()).Length != 0)

Config.print(p);

}

Handler getNatPackint[]()  &channel Nats ( int[]p ) {             

return( p );

}

Handler getPrimePackint[]() &channel sendPrimePack( int[]p ) {     

return( p );

 }

}

 

3.5.4 Обход бинарного дерева

Если структура данных задачи организована в виде дерева, то его обработку легко распараллелить путем обработки каждого поддерева  отдельном async- (movable-) методом.

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

 

Class BinTree {

Public BinTree left;

Public BinTree right;

Public int value; 

public BinTree( int depth ) {

value = 1;

if ( depth <= 1 ) {

left = null;

right = null;

    }

else {

left = new BinTree( depth – 1 );

right = new BinTree( depth – 1 );

    }

  }

}

public class SumBinTree {

public static void Main( String[] args ) {

int depth = System.Convert.ToInt32( args [0] );

SumBinTreesbt = new SumBinTree();

BinTreebtree = newBinTree( depth );

sbt.Sum(btree, sbt.c );

Console.WriteLine( “Sum = “ + sbt.Get() );

}

  // Определениеканалаиобработчика

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

  {

return ( x );

  }

// Определениеasync-метода

Public async Sum( BinTreebtree, channel (int) c ) {

if ( btree.left == null )  // Деревоестьлист

c ( btree.value );

else {

new SumBinTree().Sum( btree.left,  c1 );

new SumBinTree().Sum( btree.right, c2 );

c(Get2() );

    }

  }

// Определение связки  из двух каналов и обработчика

handler Get2 int() &channel с1( int x )

&channel с2(int y )

  {

return ( x + y );

}

}

 

3.6 Пример работающей программы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

Задачи параллельного  программирования, то есть оптимального планирования загрузки исполнительных устройств, составляют особый класс  задач исследования операций. Это  задачи высокой сложности, и методы их точного решения не могут быть положены в основу специального программного обеспечения вычислительной системы, требующего сверхвысокой оперативности. Однако при расчете, обосновании  и сопровождении сложных проектов, при мониторинге строительства, эти задачи решаются, составляя основу оперативного планирования, допускающего, ради точности результатов, повышенную трудоемкость.