[APPS] Threads - Me

// ***********************************************************************
//
// Demo program pro vyuku predmetu APPS (09/2011)
// Petr Olivka, katedra informatiky, FEI, VSB-TU Ostrava
// email:petr.olivka@vsb.cz
//
// Priklad pouzit vlaken v OS Windows
// Pro overeni paralelismu je nutno mit alespon dvoujadrovy procesor
//
// ***********************************************************************

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

#define TYP int

// funkce rand() je pouze 16 bitova
// rand32 vraci 32 bitove nahodne cislo
int rand32()
{
	return rand() * RAND_MAX + rand();
}

// funkce pro nalezeni nejvetsiho cisla v useku pole
// od leveho (vcetne) az k pravemu prvku
TYP hledej_max(int levy, int pravy, TYP *pole)
{
	TYP nejvetsi = pole[levy];
	for (int i = levy + 1; i < pravy; i++)
	if (nejvetsi < pole[i])
		nejvetsi = pole[i];
	return nejvetsi;
}

void bubble_sort(int levy, int pravy, TYP *pole)
{
	for (int i = levy; i < pravy - 1; i++)
	{
		for (int j = levy; j < pravy - i - 1; j++)
		{
			if (pole[j + 1] < pole[j])
			{
				TYP tmp = pole[j + 1];
				pole[j + 1] = pole[j];
				pole[j] = tmp;
			}
		}
	}
}

void vypis_pole(int levy, int pravy, TYP *pole)
{
	for (int i = levy; i < pravy; i++)
		printf("%d ", pole[i]);
	printf("\n");
}

// Pouziti globalnich promennych zjednodusuje ukazku pouziti vlaken.
// Neni ovsem programatorsky spravne!
// Globalni promenne: DELKA - pocet prvku na ktere odkazuje POLE
int DELKA;
TYP *POLE, *POLE1, *POLE2;
TYP MAX1 = 0, MAX2 = 0, MAX3 = 0;

// vlakno A bude hledat maximalni prvek pole mezi prvkem 0 a DELKA/2
// vysledek ulozi do globalni promenne MAX1
DWORD WINAPI vlaknoA(LPVOID)
{
	printf("Startuje vlakno A\n");
	MAX1 = hledej_max(0, DELKA / 3, POLE);
	return 0;
}

// vlakno B bude hledat maximalni prvek pole mezi prvkem DELKA/2 a DELKA
// vysledek ulozi do globalni promenne MAX2
DWORD WINAPI vlaknoB(LPVOID)
{
	printf("Startuje vlakno B\n");
	MAX2 = hledej_max(DELKA / 3, (DELKA / 3) * 2, POLE);
	return 0;
}

DWORD WINAPI vlaknoC(LPVOID)
{
	printf("Startuje vlakno C\n");
	MAX2 = hledej_max((DELKA / 3) * 2, DELKA, POLE);
	return 0;
}

DWORD WINAPI vlaknoA2(LPVOID)
{
	printf("Startuje vlakno C\n");
	MAX2 = hledej_max(0, DELKA / 2, POLE);
	return 0;
}

DWORD WINAPI vlaknoB2(LPVOID)
{
	printf("Startuje vlakno C\n");
	MAX2 = hledej_max(DELKA / 2, DELKA, POLE);
	return 0;
}

void napln_pole(int pravy, int levy, TYP *pole)
{
	for (int i = pravy; i < levy; i++)
	{
		pole[i] = rand() % DELKA;
		if (!(i % 10000000))
			printf(".");
	}
	printf("\n");
}

DWORD WINAPI vlakno4(LPVOID x)
{
	if (x == (LPVOID)0)
		napln_pole(0, DELKA / 4, POLE);
	else if (x == (LPVOID)1)
		napln_pole(DELKA / 4, (DELKA / 2), POLE);
	else if (x == (LPVOID)2)
		napln_pole((DELKA / 2), (DELKA * 3) / 4, POLE);
	else
		napln_pole((DELKA * 3) / 4, DELKA, POLE);
	return 0;
}

DWORD WINAPI vlakno2(LPVOID x)
{
	if (x == (LPVOID)0)
		bubble_sort(0, DELKA / 2, POLE1);
	else if (x == (LPVOID)1)
		bubble_sort(0, DELKA - (DELKA / 2), POLE2);
	return 0;
}

// vypocet casoveho intervalu v milisekundach
int kolik_ms(LPFILETIME pred, LPFILETIME po)
{
	hyper pred64b = pred->dwHighDateTime;
	pred64b = (pred64b << 32) | pred->dwLowDateTime;
	hyper po64b = po->dwHighDateTime;
	po64b = (po64b << 32) | po->dwLowDateTime;
	// konverze 100ns -> 1ms
	return (int)((po64b - pred64b) / 10000);
}

void splitArrays(int *l, int *r, int *pole) {
	
	for (int i = 0; i < DELKA / 2; i++) {
		l[i] = pole[i];
	}
	int pom = 0;
	for (int i = DELKA / 2; i < DELKA; i++) {
		r[pom++] = pole[i];
	}
}

void mergeArrays(int *l, int *r, int *pole, int sizel, int sizer) {
		
	int lx = 0, rx = 0, px = 0;
	while (px < DELKA) {
		if (lx >= sizel || rx >= sizer)
			break;
		if (l[lx] < r[rx]) {
			pole[px++] = l[lx++];
		} else if (l[lx] > r[rx]) {
			pole[px++] = r[rx++];
		} else {
			pole[px++] = l[lx++];
			pole[px++] = r[rx++];
		}
	}
	while (lx < sizel)
		pole[px++] = l[lx++];
	while (rx < sizer)
		pole[px++] = r[rx++];
}

int main(int na, char **arg)
{
	/*if (na != 2)
	{
		printf("Zadej pocet prvku, minimalne 1000000\n");
		system("PAUSE");
		return 0;
	}*/
	DELKA = atoi(arg[1]);
	/*if (DELKA < 1000000)
	{
	printf("Pocet prvku musi byt minimalne 1000000\n");
	system("PAUSE");
	return 0;
	}*/
	POLE = new TYP[DELKA];
	if (!POLE)
	{
		printf("Nelze alokovat pamet!\n");
		return 1;
	}
	srand((int)time(NULL));



	//Generovani nahodnych cisel do pole
	FILETIME cas_pred, cas_po;
	printf("Generuji nahodna cisla\n");

	GetSystemTimeAsFileTime(&cas_pred);

	napln_pole(0, DELKA, POLE);
	vypis_pole(0, 25, POLE);

	GetSystemTimeAsFileTime(&cas_po);
	printf("Cas generovani bez vlaken %d [ms]\n", kolik_ms(&cas_pred, &cas_po));



	/*
	//Hledani nejvetsiho prvku 3 vlakny
	printf("\nHledani nejvetsiho prvku pomoci 3 vlaken...\n");
	HANDLE p1, p2, p3;

	GetSystemTimeAsFileTime(&cas_pred);

	p1 = CreateThread(0, 0, vlaknoA, 0, 0, 0);
	p2 = CreateThread(0, 0, vlaknoB, 0, 0, 0);
	p3 = CreateThread(0, 0, vlaknoC, 0, 0, 0);

	WaitForSingleObject( p1, INFINITE );
	WaitForSingleObject( p2, INFINITE );
	WaitForSingleObject( p3, INFINITE);

	GetSystemTimeAsFileTime( &cas_po );

	printf( "Nalezene maximum je %d\n", max( MAX1, MAX2, MAX3) );
	printf( "Cas hledani byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );
	*/
	


	/*
	//hledani nejvetsiho prvku pomoci 2 vlaken
	GetSystemTimeAsFileTime(&cas_pred);

	p1 = CreateThread(0, 0, vlaknoA2, 0, 0, 0);
	p2 = CreateThread(0, 0, vlaknoB2, 0, 0, 0);

	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);

	printf("Nalezene maximum je %d\n", max(MAX1, MAX2));
	printf("Cas hledani byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));

	printf("Hledani nejvetsiho prvku pomoci 2\ vlakna...\n");
	GetSystemTimeAsFileTime(&cas_pred);
	*/



	/*
	// hledani jednim vlaknem
	TYP M = hledej_max( 0, DELKA, POLE );

	GetSystemTimeAsFileTime( &cas_po );

	printf( "Nalezene maximum je %d\n", M );
	printf( "Cas hledani byl %d [ms]\n", kolik_ms( &cas_pred, &cas_po ) );
	*/


	
	/*
	//Bubble sort bez vlaken
	GetSystemTimeAsFileTime(&cas_pred);

	bubble_sort(0, DELKA, POLE);

	GetSystemTimeAsFileTime(&cas_po);
	vypis_pole(0, 50, POLE);
	printf("Cas trideni byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));
	*/


	
	/*
	//Generovani pomoci 4 vlaken
	HANDLE p1, p2, p3, p4;

	GetSystemTimeAsFileTime(&cas_pred);

	p1 = CreateThread(0, 0, vlakno4, (LPVOID)0, 0, 0);
	p2 = CreateThread(0, 0, vlakno4, (LPVOID)1, 0, 0);
	p3 = CreateThread(0, 0, vlakno4, (LPVOID)2, 0, 0);
	p4 = CreateThread(0, 0, vlakno4, (LPVOID)3, 0, 0);

	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);
	WaitForSingleObject(p3, INFINITE);
	WaitForSingleObject(p4, INFINITE);

	GetSystemTimeAsFileTime(&cas_po);
	vypis_pole(0, 25, POLE);
	printf("Cas generovani s 4 vlakny %d [ms]\n", kolik_ms(&cas_pred, &cas_po));
	*/



	/*
	//Bubble sort pomoci dvou vlaken
	HANDLE p1, p2;

	POLE1 = new TYP[DELKA / 2];
	POLE2 = new TYP[DELKA - DELKA / 2];

	GetSystemTimeAsFileTime(&cas_pred);

	splitArrays(POLE1, POLE2, POLE);
	p1 = CreateThread(0, 0, vlakno2, (LPVOID)0, 0, 0);
	p2 = CreateThread(0, 0, vlakno2, (LPVOID)1, 0, 0);

	WaitForSingleObject(p1, INFINITE);
	WaitForSingleObject(p2, INFINITE);
	mergeArrays(POLE1, POLE2, POLE, DELKA / 2, DELKA - DELKA / 2);

	GetSystemTimeAsFileTime(&cas_po);
	vypis_pole(0, 25, POLE);
	printf("Cas trideni byl %d [ms]\n", kolik_ms(&cas_pred, &cas_po));
	*/


	system("PAUSE");
}