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

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;

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