Quicksort, Java'dan C/C++'ye

[Phoenixlin]

Paralel programming dersim için hocanın geçmiş ödevlerde verdiği Java'da yazılmış quicksort kodunu(download şeysi) önce C/C++ dillerinden birine çevirmem gerekiyor. Gel gör ki compiler bazında o kadar sorun yaşadım ki en son yazdığım iki satır kodu Visual Studio'da çalıştıramayınca onu da sildim buraya geldim(Visual Studio kullanma sebebim OpenMP library dosyalarını içinde barındırıp, windows'da iş gören compiler olarak OpenMP'nin sitesinde önerilmesinden dolayı).

Tek istediğim C/C++'da yetkili bir abimin yukardaki java kodunu bu dillerden birine çevirmesi. Karşılığında bol acılı dürüm ısmarlarım(yemeksepeti bu günler için var =)). Kodun kendisi sequential quicksort kodu bu arada. İçinde parallelliğe dair bir şey yok, ödevimin tamamının yapılmasını istemiyorum kısaca. Ki zaten asıl olay kodun çevirisi yapıldıktan sonra onu paralel hale getirme kısmısı.

Edit: Java kodunda olayı AnyType arrayi üstünden yapıyoduk da C/C++ kodunda direk integer array'i kullanılsa da olur(önceki ödevlerde en azından tüm AnyTypeları integer yaptım diye notum düşmedi =d)

(Daha çevirisini yapamazken nasıl paralel hale getircen diyenler olabilir tabi. OpenMP denilen naneyle çevirmek kolay gibin gözüküyor. Hatta başarılı bir şekilde çevirebilirsem buraya da atarım kodu)

[senko]

OpenMP'yi gcc ile kullanamiyormusun?

[Phoenixlin]

gcc'de problem olmuyor da windows'a visual studio kurmak daha kolay gözüktü en başta. Sonra 2,5gb download+45 dakika install süresinin ardından en basitinden bir kodu bile compile ettikten sonra çalıştıramayınca hüzünle sildim her şeyi =d Bir de bu hafta sonunu başka bir kod için heba edince, Quicksort'un çevirisi için yardım isteyeyim dedim =)

[Phoenixlin]

Kimse mi yardım etmez yau :( Neyse googleda arama yapacak genç dimaalara bir faydam dokunsun(Bitirince paralelini de atarım):

Quicksort - Sequential Algorithm

	#include <stdio.h>

	#include <stdlib.h>

	#include <sys/timeb.h>

	

	static const int CUTOFF = 8;

	static const int NUM_ITEMS = 1000000;

	static const long MIN_TIME = 10000;

	

	void quickSortNormal(int* a,int low,int high);

	

	void insertionSort(int* a,int low,int high){

	    for( int p = low + 1; p <= high; p++ )

	    {

	        int tmp = a[ p ];

	        int j;

	        

	        for( j = p; j > low && tmp< a[ j - 1 ]; j-- )

	            a[ j ] = a[ j - 1 ];

	        a[ j ] = tmp;

	    }

	}

	

	

	void swapReferences(int* a,int index1,int index2){

	    int tmp = a[index1];

	    a[index1] = a[index2];

	    a[index2] = tmp;

	}

	void quickSortNormal(int a[], int low, int high){

	    if( low + CUTOFF > high )

	        insertionSort( a, low, high );

	    else

	    {

	        // Sort low, middle, high

	        int middle = ( low + high ) / 2;

	        if( a[ middle ]<a[ low ])

	            swapReferences( a, low, middle );

	        if( a[ high ]<a[ low ])

	            swapReferences( a, low, high );

	        if( a[ high ]<a[ middle ])

	            swapReferences( a, middle, high );

	        

	        // Place pivot at position high - 1

	        swapReferences( a, middle, high - 1 );

	        int pivot = a[ high - 1 ];

	        

	        // Begin partitioning

	        int i, j;

	        for( i = low, j = high - 1; ; )

	        {

	            while( a[ ++i ]<pivot)

	                ;

	            while( pivot<a[ --j ])

	                ;

	            if( i >= j )

	                break;

	            swapReferences( a, i, j );

	        }

	        

	        // Restore pivot

	        swapReferences( a, i, high - 1 );

	        

	        quickSortNormal( a, low, i - 1 );    // Sort small elements

	        quickSortNormal( a, i + 1, high );   // Sort large elements

	    }

	}

	

	//Test Sort methods

	void permute(int* a){

	    for( int j = 1; j < sizeof(a)/sizeof(int); j++ )

	        swapReferences( a, j, rand()%j );

	}

	void checkSort(int* a){

	    for( int i = 0; i < sizeof(a)/sizeof(int); i++ )

	        if( a[ i ] != i )

	            printf( "Error at %d", i );

	    //printf( "Finished checksortn" );

	}

	long getMilliCount(){

	    struct timeb tb;

	    ftime(&tb);

	    long nCount = tb.millitm + (tb.time & 0xfffff) * 1000;

		return nCount;

	}

	

	long getMilliSpan(long nTimeStart){

	    long nSpan = getMilliCount() - nTimeStart;

		if(nSpan < 0)

			nSpan += 0x100000 * 1000;

		return nSpan;

	}

	

	int main(int argc, const char * argv[])

	{

	    int a[NUM_ITEMS];

	    for(int i =0; i<sizeof(a)/sizeof(int); i++){

	        a[i] = i;

	    }

	    long allTime = getMilliCount();

	    long startTime =  0;

	    long sortTime = 0;

	    int count = 0;

	    while( sortTime < MIN_TIME) {

	        permute( a );

	        startTime  = getMilliCount();

			quickSortNormal(a,0,sizeof(a)/sizeof(int)-1);

	        sortTime += getMilliSpan(startTime);

	        checkSort( a );

	        count++;

	    }

	    allTime = getMilliSpan(allTime);

	    float elapsedSortTime = (float) sortTime / count;

	    printf("elapsed time= %f --- %d  %lun",elapsedSortTime,count,allTime);

	    return 0;

	}

	

[Phoenixlin]

Quicksort'un paralel kodunu da bitirmiş bulunmaktayım; ama bana göre komik bir sorunum var.

Yukarda yazdığım sequential code, 10^5lik bir arrayi yaklaşık 2 saniyede sort ediyor. Aşağıdaki paralel kod aynı size'da array'i, tek bir thread ile başlayıp 0.46 saniye gibi büyük bir hızlanmayla bitiriyor. Böyle bir şey olması doğal mı? Yoksa ben kodun bir yerlerine kontrol mekanizması eklemedim diye arka planda yüzlerce thread mi yaratıyorum?

Test case'im şu bu arada:

Array size = 10^5
Grain size = 1000(eğer sort edilecek array parçalarının size'ı bunun altına düşerse, paralel yapmayı bırakıp sequential kodla yola devam ediyor)
# of Threads = Paralel kod için 1-2-4-8. Sequential zaten havada karada 1 thread yaratacak maksimum.

Quicksort - Paralel

	//

	//  main.c

	//

	

	#include <stdio.h>

	#include <stdlib.h>

	#include <sys/timeb.h>

	#include <omp.h>

	

	static const int CUTOFF = 8;

	static const int NUM_ITEMS = 100000;

	static const int GRAIN_SIZE = 1000;

	static const long MIN_TIME = 10000;

	

	void quickSortSequential(int* a,int low,int high);

	

	void insertionSort(int* a,int low,int high){

		int p;

	    for( p = low+1; p <= high; p++ )

	    {

	        int tmp = a[ p ];

	        int j;

	        

	        for( j = p; j > low && tmp< a[ j - 1 ]; j-- )

	            a[ j ] = a[ j - 1 ];

	        a[ j ] = tmp;

	    }

	}

	

	

	void swapReferences(int* a,int index1,int index2){

	    int tmp = a[index1];

	    a[index1] = a[index2];

	    a[index2] = tmp;

	}

	void quickSortSequential(int a[], int low, int high){

	    if( low + CUTOFF > high )

	        insertionSort( a, low, high );

	    else

	    {

	        // Sort low, middle, high

	        int middle = ( low + high ) / 2;

	        if( a[ middle ]<a[ low ])

	            swapReferences( a, low, middle );

	        if( a[ high ]<a[ low ])

	            swapReferences( a, low, high );

	        if( a[ high ]<a[ middle ])

	            swapReferences( a, middle, high );

	        

	        // Place pivot at position high - 1

	        swapReferences( a, middle, high - 1 );

	        int pivot = a[ high - 1 ];

	        

	        // Begin partitioning

	        int i, j;

	        for( i = low, j = high - 1; ; )

	        {

	            while( a[ ++i ]<pivot)

	                ;

	            while( pivot<a[ --j ])

	                ;

	            if( i >= j )

	                break;

	            swapReferences( a, i, j );

	        }

	        

	        // Restore pivot

	        swapReferences( a, i, high - 1 );

	        

	        quickSortSequential( a, low, i - 1 );    // Sort small elements

	        quickSortSequential( a, i + 1, high );   // Sort large elements

	    }

	}

	

	void quickSortParallel(int* a,int low,int high){

	    if( low + CUTOFF > high )

	        insertionSort( a, low, high );

	    else

	    {

	        // Sort low, middle, high

	        int middle = ( low + high ) / 2;

	        if( a[ middle ]<a[ low ])

	            swapReferences( a, low, middle );

	        if( a[ high ]<a[ low ])

	            swapReferences( a, low, high );

	        if( a[ high ]<a[ middle ])

	            swapReferences( a, middle, high );

	        

	        // Place pivot at position high - 1

	        swapReferences( a, middle, high - 1 );

	        int pivot = a[ high - 1 ];

	        

	        // Begin partitioning

	        int i, j;

	        for( i = low, j = high - 1; ; )

	        {

	            while( a[ ++i ]<pivot)

	                ;

	            while( pivot<a[ --j ])

	                ;

	            if( i >= j )

	                break;

	            swapReferences( a, i, j );

	        }

	        

	        // Restore pivot

	        swapReferences( a, i, high - 1 );

		    if(GRAIN_SIZE <= i-1-low || GRAIN_SIZE <= high-i-1){

				//printf("Here %dn", i-1-low );

				//printf("Here %dn", high-i-1 );

	#			pragma omp task firstprivate(a)

				quickSortParallel( a, low, i - 1 );    // Sort small elements

	#			pragma omp task firstprivate(a)

				quickSortParallel( a, i + 1, high );   // Sort large elements	

			}

			else{

				quickSortSequential( a, low, i - 1 );

				quickSortSequential( a, i + 1, high );

			}

		}

	}

	void QuickSortOmp(int a[], int size){

	#	pragma omp parallel shared(a)

	    {

	#		pragma omp single

	        {

	            quickSortParallel(a,0,size/sizeof(int)-1);

	        }

	    }

	

	}

	

	//Test Sort methods

	void permute(int* a){

		int j;

	    for( j=1; j < sizeof(a)/sizeof(int); j++ )

	        swapReferences( a, j, rand()%j );

	}

	void checkSort(int* a){

		int i ;

	    for( i= 0; i < sizeof(a)/sizeof(int); i++ ){

			if( a[ i ] != i )

				printf( "Error at %d", i );

	    }

		//printf( "Finished checksortn" );

	}

	

	long getMilliCount(){

	    struct timeb tb;

	    ftime(&tb);

	    long nCount = tb.millitm + (tb.time & 0xfffff) * 1000;

		return nCount;

	}

	

	long getMilliSpan(long nTimeStart){

	    long nSpan = getMilliCount() - nTimeStart;

		if(nSpan < 0)

			nSpan += 0x100000 * 1000;

		return nSpan;

	}

	

	int main(int argc, const char * argv[])

	{

	    int a[NUM_ITEMS];

		int i ;

	    for(i= 0; i<sizeof(a)/sizeof(int); i++){

	        a[i] = i;

	    }

	    long allTime = getMilliCount();

	    long startTime =  0;

	    long sortTime = 0;

	    int count = 0;

		omp_set_dynamic(0);

		int numThreads = 1;

		//for(numThreads = 1 ; numThreads <= 8 ; numThreads *= 2){

		//	printf("%d threads...n", numThreads);

			omp_set_num_threads(numThreads);

			

			while( sortTime < MIN_TIME) {

				permute( a );

				startTime  = getMilliCount();

				QuickSortOmp(a, NUM_ITEMS);

				//quickSortParallel(a,0,sizeof(a)/sizeof(int)-1, numThreads, numBusyThreads);

				sortTime += getMilliSpan(startTime);

				checkSort( a );

				count++;

			}

		//}

	    allTime = getMilliSpan(allTime);

	    float elapsedSortTime = (float) sortTime / count;

	    printf("elapsed time= %f --- %d  %lun",elapsedSortTime,count,allTime);

	    return 0;

	}

	

	

[riglous]

veri boyutunu artırınca ikisi de linear mı artıyor?

[Phoenixlin]

10^6lık boyutta, ilk kod 21 saniyede biterken diğeri 5 saniye tutuyor. Speedup aşağı yukarı aynı değerde evet.

[riglous]

Kerpeten gibi hissettim kendimi.
10^7 ve 10^4'ü de verebilir misin?

[Deacon]

Anlamadim ben tam olarak. Quicksort'un paralelken daha hizli calismasi niye komik ki?

[Phoenixlin]

riglous said:

Kerpeten gibi hissettim kendimi.
10^7 ve 10^4'ü de verebilir misin?

Seq 10^4 = 0.170068
Par 10^4 = 0.003590

10^7 için segmentation fault yedim -_-

10^5 için sırasıyla paralel program thread sayısına göre şöyle veriyor zamanları:

1 - 0.46...
2 - 0.29...
4 - 0.20...
8 - 0.15...

Neyse öğlene raporunu yazacam bunun en kötü değerler üstünde oynarım. Kodda düzgün sort ettiği zaman asistan umursamıyo asdf :d

Ya 1'den fazla thread kullandığımda hızlanması gerekiyor iyi optimize edersen de sonuçta 1 threadli paralel programla, 1 threadli sequential program arasında nerdeyse fark yok. Hatta paralelin çok hafif yavaş çalışması bile mümkün; ama ben 4 kat hızlanma yaşıyorum :D

[Gladmir]

Cok okumadim yukarilari, ilgimi ceken bir nokta var;

Tek thread paralel flow nedir?

[mulgear6]

abi sayılar değişiyo o sebeple hız değişiyo olmasın? fgdg

[nameless]

multiple cpu ile deneyerek gülebilirsiniz. mesajlaşma baya zaman kaybettirir gibi geliyor.

[Deacon]

Phoenixlin said:

1 threadli paralel programla,

what?

[Phoenixlin]

Nesi komik yau paralel çalışsın diye yazdığınız kod için tek bi thread oluşturursanız tek threadli paralel kod oluyo :D

Kodun olayı performans karşılaştırması yapmak. "Sequential kod hali hazırda 10^5lik bir arrayde ve grain size'ı 1000 olan bir durumda ne kadar hızla çalışır? Aynı problem ve grain size'da paralel kod 1-2-4-8 core kullanarak ne kadar hızlı çalışır?" idi olay. Akıl ve mantığın yolu sequential kod hızı = 1 thread ile çalışan paralel kod. Aradaki paralel overhead yüzünden hatta paralel kodun az biraz yavaş bile çalışması gerekirken; 4 kat hızlanması sıkıntıydı da geçti bitti aralara bir yere taks waith komutu atınca insani değerler vermeye başladı kod =)

[Eralpb]

Bikac onerim var ama;

MIN_TIMESi cok arttirsana bu hiz farkini gercekten yasayabilcek misin kendin saniyelerle olcerek?

Belki de kullandigin timer sadece su anki processin saatini veriyordur veya thread baska core'a kayiyordur processinin suanki coreu kullanma zamanini veriyordur?
omp_get_wtime() deneyebilirsin.

Veya openmpnin yarattigi threadlerin prioritysi default olarak daha yuksek de oluyor olabilir, yani main processten yuksek.

Openmpli bi environmentim olsa da denesem keske merak ettim.

[Gladmir]

Belki farkli bir ifade bicimidir diye sordum, amacim oyle sey mi olur veya sarcasm degil;

Ama;

Tek thread paralel flow, ifade olarak yanlis. Tabii ki, kasit ettigin farkli birseydir eminim ama burayi goren okuyan bu ise yeni baslayan gencler kamasir.

Paralel programing mevcut multi thread env. larda bile mevcut degil. Deneysel DNA computing de kullaniliyor, tek fiziksel sayisal varlik olarak(turkce si enterasan oldu.)

Gercek paralel programing de multiple CPU BUS a ihtiyacin var, multiple thread den ziyade. Fiziksel olarak farkli, mevcut network lerle birbirine bagli adamlarla yapiliyor ozetle. Ornek; bosta kalan ps3 lerin dunya saglik orgutunun network une baglanip remote paralel computing icin kullanilmasi.

[fizban]

kast ettiği şey, muhtemelen paralel programlamadan kaynaklanan overhead'lerin olduğu, yazılan omp kodunun tek thread ile çalıştığı zaman hızlanma değil yavaşlama sağlaması gerektiği. ki haklı gibi.

koda bakmadım, aldım direk compile ettim ikisini de g++ ile. hiçbir hız farkı görmedim. işin komik yanı thread sayısını arttırdığım zaman da hız değişmiyor. ikisinde de 10 saniye.

bi dakka şimdi baktım da min_time ne ya ? neler oluyoooeoe

[Phoenixlin]

Quicksort kimi problemleri çok hızlı çözdüğü için program zamanı ölçemiyor; o yüzden birden fazla kez quicksort işlemi yaptırıp bir sorting time buluyorsun. O sorting time MIN_TIME'a eşit ya da büyük olduğunda da looptan çıkıp bulduğun sorting time'ı, yaptığın quicksort işlemi sayısına bölüyorsun.