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

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++)