Автор: Пользователь скрыл имя, 13 Ноября 2011 в 18:59, курсовая работа
Идея параллельной обработки данных не нова. Можно считать, что она возникла еще на заре человеческой цивилизации, когда оказалось, что племя может успешно бороться за выживание, если каждый его член выполняет свою часть общей работы.
В ближайшее время под эффективным использованием аппаратных средств компьютера будут пониматься применение параллельных алгоритмов. Это связано с замедлением темпов роста тактовой частоты микропроцессоров и быстрым распространением многоядерных микропроцессоров.
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 ();
}
}
Ниже
представлены графики времени исполнения
последовательного и
Тестовые
замеры проводились на машине с двухъядерным
процессором Intel Core 2 Duo 2.4 GHz и оперативной
памятью 1 Гб.
Рис. 12.
Время исполнения последовательного
и параллельного алгоритмов БПФ.
3.5.3 Построения списка простых чисел методом “решета Эратосфена”
1. Наивный алгоритм
По условию задачи, по заданному натуральному числу N ³ 2, необходимо найти все простые числа в интервале от 2 до N.
Метод просеивания состоит из следующих шагов:
1) из исходного списка l0 всех натуральных чисел от 2 до N
l0 = [2, … , N]
выбирается первое число этого списка, а именно 2, и выдается в качестве первого выходного значения;
2) затем строится новый список l1 , который получается из списка l0 вычеркиванием из него всех чисел, кратных очередному выбранному простому числу – на первом шаге, числу 2:
l1 = [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. Пакетный алгоритм
В данном разделе
описывается модификация
Основная идея предлагаемого
алгоритма заключается в переходе
от использования потоков
Пакет – это массив натуральных чисел фиксированного размера (задаваемого в программе значением 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("----------------