Паралельні та розпод ...

Автокореляція або автокореляційна функція — це кореляція функції з самою собою зміщеною на певну величину незалежної змінної. Автокореляція використовується для знаходження закономірностей в ряді даних, таких як періодичність. Часто застосовується у статистиці та обробці сигналів для аналізу функцій або серій даних.
Що це значить? Це значить, що, наприклад, є сигнал з шумом, то б то масив довжини Size
з випадково обраними у часі значеннями. Далі сума квадратів елементів масиву:

Sums[0] = A[0]*A[0] + A[1]*A[1] + ... + A[Size-1]*A[Size-1]

Така сума буде досить великим значенням. Але ми також можемо знайти суми попарних добутків:

Sums[1] = A[0]*A[1] + A[1]*A[2] + ... + A[Size-1]*A[0]

Sums[2] = A[0]*A[2] + A[1]*A[3] + ... + A[Size-2]*A[0] + A[Size-1]*A[1]

і так далі.

Графік функції дозволяє оцінити загальний вигляд вихідного сигналу.

1. З використанням кодів послідовної програми main_serial.cpp побудувати графік автокореляції сигналу.

2. Розробити паралельну версію програми для знаходження автокореляції з використанням paralell for OpenMP для циклу знаходження сум:

    for( int shift = 0; shift < size; shift++ )
    {
        float sum = 0.0;
        for (int i = 0; i < size; i++)
        {
            sum += A[i] * A[i + shift];
        }
        Sums[shift] = sum;
    }

3. Реалізувати програму з використанням CPU SIMD інструкції (див файл main_simd.cpp як зразок).

4. Розробити GPU {OpenCL або CUDA} версію програми. У цьому випадку ядро OpenCL для обчислення сум може мати такий вигляд:

__kernel void AutoCorrelate(__global const float *dA, __global float *dSums )
{
	int Size = get_global_size( 0 ); // the dA size is actually twice this big
	int gid = get_global_id( 0 );
	int shift = gid;
	float sum = 0.;
	for( int i = 0; i < Size; i++ )
	{
		sum += dA[i] * dA[i + shift];
	}
	dSums[shift] = sum;
}

5. Написати звіт, що буде включати коди всіх програм, графік автокореляції, відповідь на питання "який період функції сигналу?", діаграму для порівняння часу роботи послідовної версії, openMP 1 потік, openMP 2 потоки, openMP 4 потоки, CPU SIMD, GPU, аналіз результатів.