/*
	Example program that shows how to create a multithreaded program in which each thread will treat a part of an array.
*/

#include <thread>
#include <vector>
#include <time.h>
#include <chrono>
#include <iostream> // cout, ...

using namespace std;
using namespace std::chrono;

const int MAX_NBR_THREADS = 20;
#define N (1024*1024) 


void multiplication_function(int t, float* arr, float* arr2, float* result, int n);

_int64 sequential_version(int n, float* arr, float* arr2, float* result);

_int64 version_multithreaded(const int n, float* arr, float* arr2, float* result, const int NBR_THREADS);
_int64 version_parallel_hint(const int n, float* arr, float* arr2, float* result);

void checkIfResultsAreTheSame(string name, float* arr3, float* arr4, int n, bool PRINT_DATA);


int main()
{
	cout << "Considering arrays of size " << N << endl;

	// allocation and initialization
	srand(time(NULL)); // random initial seed
	float* arr = new float[N], * arr2 = new float[N], * result_seq = new float[N], * result_par = new float[N], * arr4 = new float[N], * arr5 = new float[N], * arr6 = new float[N];
	for (int i = 0; i < N; i++) {
		arr[i] = rand();
		arr2[i] = rand();
		result_seq[i] = 0; // actually, initialization is not necessary
		result_par[i] = 0;
		arr4[i] = rand();
		arr5[i] = rand();
		arr6[i] = 0;
	}

	// flush caches
	_int64 run_time_seq = sequential_version(N, arr4, arr5, arr6);
	cout << "Runtime for sequential version: " << run_time_seq << "us " << (run_time_seq * 1000 / N) << "ns/op" << endl;

	run_time_seq = sequential_version(N, arr, arr2, result_seq);
	cout << "Runtime for sequential version: " << run_time_seq << "us " << (run_time_seq * 1000 / N) << "ns/op" << endl;

	_int64 run_time = version_parallel_hint(N, arr, arr2, result_par);
	checkIfResultsAreTheSame("Parallel hint version", result_seq, result_par, N, false);
	cout << "Runtime for version with parallel hint: " << run_time << "us " << (run_time * 1000 / N) << "ns/op - Speedup = " << ((double)run_time_seq / run_time) << endl;


	// warm up
	version_multithreaded(N, arr4, arr5, arr6, MAX_NBR_THREADS);

	for (int nbr_threads = 1; nbr_threads <= MAX_NBR_THREADS; nbr_threads++) {
		version_multithreaded(N, arr4, arr5, arr6, MAX_NBR_THREADS); // clear the caches

		_int64 run_time = version_multithreaded(N, arr, arr2, result_par, nbr_threads);
		checkIfResultsAreTheSame("Multithreaded version", result_seq, result_par, N, false);
		cout << "Runtime for " << nbr_threads << " threads: " << run_time << "us " << (run_time * 1000 / N) << "ns/op - Speedup = " << ((double)run_time_seq / run_time) << endl;
	}


	// clean up memory
	delete arr, arr2, result_seq, result_par, arr4, arr5, arr6;

	cout << endl << "Press ENTER to close window...";
	char c = cin.get();
	return 0;
}

void multiplication_function(int t, float* arr, float* arr2, float* result, int n)
{

	for (int i = 0; i < n; ++i) {
		//	arr[i] = rand();
		//	arr2[i] = rand();

			//result[i] = arr[i] * arr2[i];

			//	result[i] = 7 * arr[i] * arr2[i] - 9.5 *  arr[i] * arr[i] + arr[i] / 8.943 - arr[i]/ arr2[i] + (arr[i] - arr2[i]) * (arr[i] - arr2[i]) + 8.97 * (arr[i] - arr2[i]) / (arr[i] - arr2[i]);
			// a lot of work, to make sure it is compute-bound
			//for (int j = 1; j < 100; j+=2) {
			//	
			//	result[i] += arr[i] * arr2[i] / j;
			//	result[i] -= arr[i] * arr2[i] / (j+1);
			//}

		const int A = 23, B = 4203, C = 4748;
		int random = (int)arr[i]; // start value (seed)
		for (int j = 0; j < 100; j++) {
			random = (A * random + B) % C;
		}
		result[i] = random;

	}

}



_int64 sequential_version(int n, float* arr, float* arr2, float* result) {
	time_point<system_clock> start = system_clock::now();

	multiplication_function(0, arr, arr2, result, n);

	time_point<system_clock> end = system_clock::now();
	microseconds us = duration_cast<microseconds>(end - start);

	return us.count();
}


_int64 version_multithreaded(const int n, float* arr, float* arr2, float* result, const int NBR_THREADS) {

	time_point<system_clock> start = system_clock::now();

	const int ELEMENTS_PER_THREAD = n / NBR_THREADS;

	vector<thread*> threads; // vector of pointers to threads

	// *** STARTING THE THREADS
	for (int t = 0; t < NBR_THREADS; t++)
		threads.push_back(new thread(multiplication_function, t, arr + t * ELEMENTS_PER_THREAD, arr2 + t * ELEMENTS_PER_THREAD, result + t * ELEMENTS_PER_THREAD, ELEMENTS_PER_THREAD)); // pass the function to be executed and all the necessary parameters

	// do the remainder of the array in the main thread																																													 // do the remainder of the array
	int last_idx = NBR_THREADS * ELEMENTS_PER_THREAD;
	if (last_idx < n)
		multiplication_function(0, arr + last_idx, arr2 + last_idx, result + last_idx, n - last_idx);

	// *** waiting for all threads to finish
	for (int t = 0; t < threads.size(); t++) {
		threads[t]->join();
		delete threads[t];
	}

	time_point<system_clock> end = system_clock::now();
	microseconds us = duration_cast<microseconds>(end - start);
	return us.count();
}

_int64 version_parallel_hint(const int n, float* arr, float* arr2, float* result) {
	time_point<system_clock> now = system_clock::now();

#pragma loop(ivdep)  // indicates that the iterations of the loop are independent. This statement seems to be necessary...
#pragma loop(hint_parallel(14))
	for (int i = 0; i < n; ++i) {
		const int A = 23, B = 4203, C = 4748;
		int random = (int)arr[i]; // start value (seed)
		for (int j = 0; j < 100; j++) {
			random = (A * random + B) % C;
		}
		result[i] = random;

	}
	time_point<system_clock> epoch = system_clock::now();
	microseconds us = duration_cast<microseconds>(epoch - now);
	return us.count();
}
void checkIfResultsAreTheSame(string name, float* arr3, float* arr4, int n, bool PRINT_DATA) {
	int nbr_diff = 0;
	for (int i = 0; i < n; i++) {
		float rel_diff = arr3[i] == arr4[i] ? 0 : (arr3[i] - arr4[i]) / (arr3[i] == 0 ? arr4[i] : arr3[i]);
		if (rel_diff > 0.0001) {
			nbr_diff++;
			if (PRINT_DATA && i < 10) cout << arr3[i] << "<>" << arr4[i] << " (" << rel_diff << "), ";
		}
		else {
			if (PRINT_DATA && i < 10) cout << arr3[i] << "==" << arr4[i] << " (" << rel_diff << "), ";
		}
		arr4[i] = 0; // we reset arr4 for further usage
	}
	if (PRINT_DATA) cout << endl;
	if (nbr_diff > 0)
		cout << "Problem with algorithm : " << nbr_diff << " differences with Original Algorithm." << endl;
} // " << name << "