kommppuuttasii apparraalleell:: bggr raapphh...

Komunitas eLearning IlmuKomputer.Com

Copyright © 2003-2014 IlmuKomputer.Com

1

KKoommppuuttaassii PPaarraalleell:: GGrraapphh TTaakk BBeerraarraahh

MMeenngggguunnaakkaann AAddjjaacceennccyy MMaattrriixx Untuk Diimplementasikan pada Kasus Perhitungan

Jumlah Triple pada Graph Tak Berarah

Achmad Fauzan [email protected]

Penerapan paralelisme pada komputasi dapat mempercepat waktu pemrosesan dibandingkan

tanpa paralelisme atau sekuensial. Perhitungan triple, yang merupakan himpunan dari tiga buah

vertex yang masing-masing saling terhubung dengan kedua vertex lainnya, pada graph tak

berarah dilakukan dengan cara menelusuri sepasang edge tiap vertex dan memastikan vertex

pada kedua ujung edge tersebut saling terhubung. Pada implementasi kasus tersebut dengan

tanpa menggunakan paralelisme, pada percobaan didapatkan waktu rata-rata 4.95 detik untuk

menghitung 43.549.936 buah triple pada graph dengan jumlah vertex 1280 buah. Waktu yang

didapatkan tersebut lebih lama 3.15 detik dibandingkan dengan menggunakan paralelisme yang

hanya membutuhkan waktu rata-rata 1.80 detik.

A. Graph tak berarah dalam bentuk adjacency matrix

Graph tak berarah merupakan graph yang sisinya tidak mempunyai orientasi. Pada graph tak

berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan.

Gambar 1. Graph tak berarah dengan 7 buah vertex

Lisensi Dokumen: Copyright © 2003-2014 IlmuKomputer.Com

Seluruh dokumen di IlmuKomputer.Com dapat digunakan, dimodifikasi dan

disebarkan secara bebas untuk tujuan bukan komersial (nonprofit), dengan syarat

tidak menghapus atau merubah atribut penulis dan pernyataan copyright yang

disertakan dalam setiap dokumen. Tidak diperbolehkan melakukan penulisan ulang,

kecuali mendapatkan ijin terlebih dahulu dari IlmuKomputer.Com.



2

Adjacency matrix merupakan representasi matriks nxn (n kali n) yang menyatakan

hubungan antar simpul dalam suatu graph. Kolom dan baris dari matriks ini

merepresentasikan simpul-simpul, dan nilai dalam matriks ini menyatakan hubungan antar

simpul, apakah terdapat sisi yang menghubungkan kedua simpul tersebut.

Pada gambar 1, hubungan antar simpul dapat direpresentasikan dalam adjacency matrix

berikut.

Gambar 2. Adjancency matrix dengan 7 buah vertex

Gambar 2 merupakan adjacency matrix yang berkorelasi dengan graph tak berarah pada

gambar 1. Baris dan kolom pada matriks merupakan simpul-simpul (vertex) yang berlabel

1-7.

Kelebihan dari adjancency matrix ini adalah elemen matriksnya dapat diakses langsung

melalui indeks, sehingga hubungan ketetanggaan antara kedua vertex dapat ditentukan

dengan langsung. Sedangkan kekurangannya adalah bila graph memiliki jumlah sisi yang

relatif sedikit, karena matriksnya bersifat jarang yaitu hanya mengandung elemen bukan nol

yang sedikit. Kasus seperti ini merugikan karena kebutuhan ruang memori untuk matriks

menjadi boros dan tidak efisien karena komputer menyimpan elemen 0 (nol) yang tidak

perlu.

B. Triple pada adjacency matrix

Triple merupakan sebuah himpunan dari 3 vertex berbeda dimana masing-masing vertex

memiliki edge ke kedua vertex lain.

Gambar 3. Graph tak berarah dengan 3 buah triple



3

Cara mengetahui suatu himpunan 3 buah vertex adalah triple atau bukan, dapat dilakukan

dengan cara berikut.

1. Menelusuri dua edge yang ada pada suatu vertex.

2. Mengecek apakah masing-masing vertex di kedua edge tersebut terhubung/memiliki

edge sendiri. Jika ya, maka ketiga vertex tersebut adalah triple.

Sebagai contoh pada vertex 1 memiliki edge dengan vertex 2 dan 3. Maka akan dilakukan

penelusuran apakah vertex 2 memiliki edge dengan vertex 3, dan ternyata terdapat edge

antara vertex 2 dan 3 sehingga himpunan vertex 1, 2, dan 3 merupakan sebuah triple.

C. Perhitungan triple pada adjacency matrix secara sekuensial (tanpa paralelisme)

Perhitungan triple dilakukan dengan cara sebagai berikut:

1. Membuat tiga buah variabel i, j, dan k yang masing-masing akan mewakili sebuah

vertex, dan variabel triple untuk menghitung bayaknya triple.

2. Mencari edge yang terdapat pada vertex i dimulai dari i = 0 yang berhubungan dengan

vertex j dengan cara menelusuri matrix pada baris ke i dan kolom ke j.

3. Apabila nilai yang didapatkan adalah 0 maka tidak terdapat edge dan penelusuran

dilanjutkan ke j berikutnya, dan apabila nilai yang didapatkan adalah 1 maka terdapat

edge dan mencari kembali edge dari vertex i yang berhubungan dengan vertex k dengan

cara menelusuri matrix pada baris ke i dan kolom ke k.

4. Apabila nilai yang didapatkan adalah 0 maka tidak terdapat edge dan penelusuran

dilanjutkan ke k berikutnya, dan apabila nilai yang didapatkan adalah 1 maka terdapat

edge dan mengecek edge antara vertex j dengan vertex k.

5. Apabila nilai yang didapatkan adalah 0 maka tidak terdapat edge dan ketiga vertex i, j,

dan k bukanlah triple, namun apabila nilai yang didapatkan adalah 1 maka terdapat edge

dan ketiga vertex i, j, dan k saat itu adalah triple, kemudian menambahkan nilai variabel

triple dengan angka 1.

Langkah-langkah tersebut dapat digambarkan sebagai berikut.

Gambar 4. Perhitungan triple tanpa paralelisme



4

Pseudocode perhitungan triple tanpa paralelisme adalah sebagai berikut. //Count triples

for(i=0;i<n;i++){

for(j=0;j<n;j++){

if(matrix[i][j]==1 && i!=j){

for(k=j+1;k<n;k++){

if(matrix[i][k]==1 && matrix[j][k]==1 && i!=k)

triple++;

}

}

}

}

triple=triple/3;

printf("triple=%d\n",triple);

D. Perhitungan triple pada adjacency matrix secara paralel skenario 1

Pada skenario 1 ini, paralelisme akan diterapkan pada perhitungan triple dengan cara

membagi tugas pencarian edge pada vertex i ke thread yang berbeda. Misalkan terdapat 4

buah thread maka thread 1 akan menghitung triple pada vertex 1, 5, 9, dan seterusnya.

Skenario ini dapat digambarkan seperti gambar berikut.

Gambar 5. Perhitungan triple dengan paralelisme menggunakan 4 buah thread

Pseudocode perhitungan triple dengan paralelisme adalah sebagai berikut. //Count triples

#pragma omp parallel

{

int i,j,k,temp=0,

me=omp_get_thread_num(),



5

nth=omp_get_num_threads();

for(i=me;i<n;i+=nth){

for(j=0;j<n;j++){


for(k=j+1;k<n;k++){


temp++;

}

}

}

}

#pragma omp critical

{

triple+=temp;

}

}

triple=triple/3;


E. Pengujian efektifitas waktu perhitungan triple tanpa paralel dan dengan paralel

Pengujian dilakukan dengan cara mencatat waktu lamanya proses perhitungan triple pada

matrix adjacency, yaitu dengan memasang pencatat waktu awal sesaat sebelum proses

perhitungan dimulai dan mencatat waktu akhir sesaat setelah proses perhitungan selesai.

Banyaknya vertex yang digunakan yaitu secara acak berjumlah belasan hingga ratusan dan

ribuan vertex. Adjancency matrix yang digunakan dalam percobaan ini adalah sama, antara

matrix pada percobaan perhitungan triple tanpa paralel dan dengan paralel. Tujuannya

adalah melihat efektifitas waktu pada perhitungan triple tanpa paralel dan dengan paralel.

Tabel 1. Perbandingan pseudocode perhitungan triple tanpa paralelisme

dan dengan paralelisme

Tanpa Paralelisme Dengan Paralelisme

double start = omp_get_wtime();

//Count triples

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if(matrix[i][j]==1 && i!=j)

{

for(k=j+1;k<n;k++){

if(matrix[i][k]==1 &&

matrix[j][k]==1 && i!=k)

triple++;

}

}

}

}


//Count triples


{

int i,j,k,temp=0,



for(i=me;i<n;i+=nth)

{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){

if(matrix[i][k]==1 &&

matrix[j][k]==1 && i!=k)



6

double end = omp_get_wtime();

double time = end-start;

printf("find triple on %f

sec\n",time);

triple=triple/3;


temp++;

}

}

}

}


{

triple+=temp;

}

}



printf("find triple on %f

sec\n",time);

triple=triple/3;


Pengambilan data secara lengkap dapat dilihat pada lampiran I. Rata-rata waktu yang

dibutuhkan dapat dilihat pada tabel berikut.

Tabel 2. Rata-rata waktu yang dibutuhkan pada perhitungan triple tanpa paralelisme

dan dengan paralelisme

Jumlah vertex

Tanpa Paralelisme Dengan Paralelisme Selisih waktu

Rata-rata waktu (sec)

Jumlah triple


Jumlah triple

5 0.000003 2 0.002185 2 0.002182

10 0.000014 18 0.002530 18 0.002516

20 0.000088 145 0.003158 145 0.003070

40 0.000582 1105 0.004668 1105 0.004087

80 0.004309 9344 0.005492 9344 0.001183

160 0.016460 81018 0.009734 81018 -0.006726

320 0.080972 663333 0.035921 663333 -0.045051

640 0.603690 5392748 0.238395 5392748 -0.365295

1280 4.949615 43549936 1.793848 43549936 -3.155767

Pada graph dengan banyaknya vertex 5 sampai dengan 80 buah, proses perhitungan triple

lebih cepat selesai tanpa menggunakan paralelisme. Namun pada graph dengan banyaknya

vertex lebih dari 80 buah, proses perhitungan triple lebih cepat selesai dengan menggunakan

paralelisme. Pada graph dengan 160 vertex, selisih waktu mencapai 0.006726 detik, namun

pada graph dengan 1280 vertex selisih waktu dapat mencapai 3.155767 detik. Perbedaan

waktu ini akan semakin besar apabila vertex pada suatu graph semakin banyak. Hal ini

membuktikan bahwa dengan menggunakan paralelisme, kecepatan proses dapat

ditingkatkan.



7

Gambar 6. Diagram perbandingan waktu yang dibutuhkan pada perhitungan triple

tanpa paralelisme dan dengan paralelisme

Berdasarkan hasil pengujian tersebut dapat disimpulkan bahwa penggunaan paralelisme

pada perhitungan triple akan benar-benar efektif bila diterapkan pada graph dengan jumlah

vertex lebih dari 80 buah. Efektifitas waktu yang didapatkan akan semakin besar berbanding

lurus dengan semakin banyaknya vertex pada graph tersebut.

Untuk memaksimalkan kecepatan proses maka dapat diterapkan dengan cara menggunakan

paralelisme hanya ketika jumlah vertex melebihi 80 buah. Sehingga hasil yang dicapai dapat

lebih dinamis menyesuaikan kebutuhan komputasi.



8

F. Perhitungan triple pada adjacency matrix secara paralel skenario 2

Salah satu kelemahan komputasi pada skenario 1 adalah penggunaan array untuk

mendefinisikan matrix nxn, yaitu keterbatasan jumlah vertex yang dapat disimpan dalam

bentuk variabel array, sehingga tidak dapat digunakan untuk graph dengan jumlah vertex

banyak (pada percobaan sebelumnya hanya dapat menyimpan sampai dengan 1280 vertex,

dan jika jumlah vertex melebihi 2000 maka tidak dapat disimpan pada variabel array

tersebut). Solusi untuk mengatasi permasalahan tersebut digunakan pointer untuk

menyimpan matrix nxn. Pointer bersifat dinamis karena menyimpan alamat memori suatu

nilai sehingga tidak dibatasi tipe data yang digunakan.

int **matrix;//matrix[n][n];

int x,y;

matrix=(int **)malloc(10*n);

for(x=0;x<n;x++){

matrix[x]=(int *)malloc(10*n);

}

Perhitungan triple pada adjacency matrix secara paralel skenario 2 menitik beratkan pada

pembagian tugas perhitungan berdasarkan bobot kerjanya. Adapun jenis paralel yang

digunakan adalah #pragma omp for schedule. Ada beberapa teknik yang digunakan yaitu

secara static, dynamic, dan guided.

1. Static

Pseudocode yang digunakan adalah sebagai berikut. //Count triples


{

int i,j,k,temp=0,

#pragma omp for schedule(static)

for(i=0;i<n;i++){

for(j=0;j<n;j++){


for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}



9

2. Dynamic



{

int i,j,k,temp=0,

#pragma omp for schedule(dynamic)

for(i=0;i<n;i++){

for(j=0;j<n;j++){


for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}

3. Guided



{

int i,j,k,temp=0,

#pragma omp for schedule(guided)

for(i=0;i<n;i++){

for(j=0;j<n;j++){


for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}



10

G. Pengujian efektifitas waktu perhitungan triple tanpa schedule, schedule static,

schedule dynamic, dan schedule guided

Teknik pengujian masih sama dengan pengujian sebelumnya yaitu dengan cara mencatat

waktu lamanya proses perhitungan triple pada matrix adjacency untuk masing-masing

teknik perhitungan. Namun jumlah vertex yang akan digunakan dalam pengujian ini harus

mencapai ribuan untuk melihat perbedaan waktu yang signifikan.

Pengambilan data secara lengkap dapat dilihat pada lampiran II. Rata-rata waktu yang

dibutuhkan dapat dilihat pada tabel berikut.

Tabel 3. Rata-rata waktu yang dibutuhkan pada perhitungan triple tanpa schedule,

schedule static, schedule dynamic, dan schedule guided

Jumlah vertex

Tanpa schedule Schedule static Schedule dynamic Schedule guided


Jumlah triple


Jumlah triple


Jumlah triple


Jumlah triple

100 0.001853 19697 0.001334 19697 0.000947 19697 0.000773 19697

200 0.012113 157878 0.007954 157878 0.010231 157878 0.009787 157878

400 0.064627 1310551 0.064610 1310551 0.062197 1310551 0.043057 1310551

800 0.511904 10563048 0.534730 10563048 0.555397 10563048 0.394683 10563048

1600 4.611130 84984586 5.321333 84984586 5.693085 84984586 4.198684 84984586

3200 57.135814 682032863 52.599362 682032863 53.490192 682032863 44.908770 682032863

Pada pengujian menggunakan jumlah vertex 100 hingga 1600, tidak terlihat perbedaan

waktu yang terlalu signifikan. Bahkan dengan jumlah triple yang mencapai 84.984.586 pada

graph dengan 1600 vertex, selisih waktu yang ada hanya 1.494401 detik antara yang

tercepat yaitu menggunakan schedule guide (4.198684 detik) dengan yang terlama

menggunakan schedule dynamic (5.693085 detik). Selisih waktu yang signifikan baru

terjadi pada pengujian dengan 3200 vertex yang mencapai 12.227044 detik dengan

banyaknya triple 682.032.863.

Hal ini menunjukkan bahwa penggunaan schedule static, dynamic, ataupun guided pada

perhitungan triple adjacency matrix akan benar-benar efektif bila vertex yang terdapat pada

graph lebih dari 3200 buah dan triple yang ada lebih dari 600 juta triple. Karena yang paling

mempengaruhi lamanya proses perhitungan triple yaitu banyaknya triple itu sendiri.



11

Gambar 7. Diagram perbandingan waktu yang dibutuhkan pada perhitungan triple

tanpa schedule, schedule static, schedule dynamic, dan schedule guided

H. Kesimpulan

Kesimpulan yang dapat diambil adalah sebagai berikut.

1. Penggunaan paralelisme pada komputasi dapat mempercepat pemrosesan karena

penugasan secara keseluruhan dapat dibagi dengan banyaknya thread yang

terdapat pada perangkat komputer.

2. Semakin banyak thread yang digunakan maka kecepatan pemrosesan pun

semakin tinggi.

3. Pada penugasan yang relatif kecil ada kalanya akan lebih efektif menggunakan

komputasi tanpa paralel karena resource yang digunakan dalam membagi tugas



12

ke masing-masing thread lebih besar dari pada proses utama komputasi itu

sendiri.

4. Pada komputasi yang menggunakan perulangan, baik secara perulangan tunggal

maupun bertingkat, akan lebih baik menggunakan paralel for schedule dari pada

membagi tugas paralel secara manual.

Referensi Matloff, N. 2014. Programming on Parallel Machines. University of California. California.

Biografi Penulis Achmad Fauzan. Menyelesaikan S1 di Universitas Muhammadiyah

Purwokerto. Sekarang sedang melanjutkan studi di S2 Ilmu Komputer

Universitas Gadjah Mada. Saat ini sedang mempelajari bidang komputasi

paralel dan pemrosesan bahasa alami. Selain kegiatan akademik juga sedang

membangun usaha di bidang IT, khususnya pengembangan perangkat lunak.



13

Lampiran I. Tabel pengamatan pada pengujian perhitungan triple tanpa paralelisme

dan dengan paralelisme.

Tabel pengujian menggunakan 5 buah vertex

Pengujian ke-


Waktu perhitungan (sec)

Jumlah triple


Jumlah triple

1 0.000004 2 0.003718 2

2 0.000004 2 0.003028 2

3 0.000004 2 0.001792 2

4 0.000004 2 0.002454 2

5 0.000003 2 0.002039 2

6 0.000002 2 0.001230 2

7 0.000004 2 0.001783 2

8 0.000003 2 0.001458 2

9 0.000003 2 0.003072 2

10 0.000003 2 0.001280 2

Rata-rata 0.000003

0.002185


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.000015 18 0.003972 18

2 0.000017 18 0.002527 18

3 0.000010 18 0.001794 18

4 0.000014 18 0.002209 18

5 0.000015 18 0.003211 18

6 0.000015 18 0.002281 18

7 0.000015 18 0.001906 18

8 0.000014 18 0.003090 18

9 0.000015 18 0.001967 18

10 0.000014 18 0.002342 18

Rata-rata 0.000014

0.002530


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.000088 145 0.001756 145

2 0.000088 145 0.003433 145

3 0.000088 145 0.003765 145

4 0.000088 145 0.003930 145

5 0.000087 145 0.003586 145

6 0.000088 145 0.004580 145

7 0.000088 145 0.002576 145

8 0.000089 145 0.003193 145



14

9 0.000089 145 0.001602 145

10 0.000087 145 0.003162 145

Rata-rata 0.000088

0.003158


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.000577 1105 0.007128 1105

2 0.000606 1105 0.010276 1105

3 0.000576 1105 0.003853 1105

4 0.000576 1105 0.002366 1105

5 0.000582 1105 0.003376 1105

6 0.000580 1105 0.004208 1105

7 0.000575 1105 0.001756 1105

8 0.000581 1105 0.001255 1105

9 0.000582 1105 0.009089 1105

10 0.000581 1105 0.003377 1105

Rata-rata 0.000582

0.004668


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.004313 9344 0.004296 9344

2 0.004288 9344 0.002509 9344

3 0.004333 9344 0.003605 9344

4 0.004315 9344 0.005199 9344

5 0.004295 9344 0.005571 9344

6 0.004313 9344 0.008564 9344

7 0.004331 9344 0.008808 9344

8 0.004309 9344 0.004386 9344

9 0.004311 9344 0.009380 9344

10 0.004285 9344 0.002604 9344

Rata-rata 0.004309

0.005492


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.026298 81018 0.016600 81018

2 0.011498 81018 0.009798 81018

3 0.020957 81018 0.012643 81018

4 0.016425 81018 0.008698 81018

5 0.015704 81018 0.005519 81018

6 0.015008 81018 0.009355 81018

7 0.015432 81018 0.008520 81018



15

8 0.011608 81018 0.011545 81018

9 0.010059 81018 0.008502 81018

10 0.021607 81018 0.006160 81018

Rata-rata 0.016460

0.009734


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.079254 663333 0.036960 663333

2 0.079712 663333 0.033988 663333

3 0.079525 663333 0.036638 663333

4 0.080123 663333 0.040505 663333

5 0.090178 663333 0.036380 663333

6 0.076570 663333 0.034577 663333

7 0.080658 663333 0.038381 663333

8 0.082119 663333 0.035003 663333

9 0.082856 663333 0.034436 663333

10 0.078725 663333 0.032338 663333

Rata-rata 0.080972

0.035921


Pengujian ke-



Jumlah triple


Jumlah triple

1 0.601529 5392748 0.239225 5392748

2 0.603163 5392748 0.238045 5392748

3 0.600636 5392748 0.233274 5392748

4 0.605600 5392748 0.234727 5392748

5 0.603198 5392748 0.235242 5392748

6 0.609186 5392748 0.234364 5392748

7 0.607648 5392748 0.231468 5392748

8 0.607516 5392748 0.243389 5392748

9 0.601186 5392748 0.232529 5392748

10 0.597233 5392748 0.261682 5392748

Rata-rata 0.603690

0.238395


Pengujian ke-



Jumlah triple


Jumlah triple

1 4.961537 43549936 1.795396 43549936

2 4.947825 43549936 1.797618 43549936

3 4.944057 43549936 1.791860 43549936

4 4.976400 43549936 1.789855 43549936

5 4.936359 43549936 1.807901 43549936

6 4.963781 43549936 1.787250 43549936



16

7 4.934203 43549936 1.791889 43549936

8 4.953855 43549936 1.779464 43549936

9 4.944076 43549936 1.802016 43549936

10 4.934055 43549936 1.795233 43549936

Rata-rata 4.949615

1.793848 Lampiran II. Tabel pengamatan pada pengujian perhitungan triple dengan paralelisme

tanpa schedule dan dengan schedule static, dynamic, maupun guided.


Uji ke- Tanpa schedule Schedule static Schedule dynamic Schedule guided

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

1 0.005418 19697 0.001001 19697 0.000981 19697 0.000773 19697

2 0.001678 19697 0.000993 19697 0.000965 19697 0.000775 19697

3 0.001371 19697 0.001132 19697 0.000943 19697 0.000768 19697

4 0.002954 19697 0.000994 19697 0.000938 19697 0.000771 19697

5 0.002256 19697 0.000992 19697 0.000936 19697 0.000775 19697

6 0.000971 19697 0.000990 19697 0.000946 19697 0.000771 19697

7 0.000948 19697 0.003018 19697 0.000944 19697 0.000774 19697

8 0.000949 19697 0.002206 19697 0.000943 19697 0.000770 19697

9 0.001040 19697 0.001012 19697 0.000937 19697 0.000774 19697

10 0.000948 19697 0.001002 19697 0.000940 19697 0.000778 19697

Rata-rata 0.001853

0.001334

0.000947

0.000773



Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

1 0.020619 157878 0.007457 157878 0.011884 157878 0.009387 157878

2 0.011915 157878 0.007446 157878 0.009801 157878 0.009380 157878

3 0.010594 157878 0.007462 157878 0.009788 157878 0.010117 157878

4 0.010781 157878 0.009940 157878 0.010820 157878 0.009746 157878

5 0.012005 157878 0.007475 157878 0.009753 157878 0.009335 157878

6 0.010576 157878 0.007451 157878 0.009782 157878 0.010868 157878

7 0.010964 157878 0.007440 157878 0.010340 157878 0.009743 157878

8 0.011139 157878 0.009900 157878 0.009792 157878 0.009380 157878

9 0.010575 157878 0.007511 157878 0.009749 157878 0.010213 157878

10 0.011965 157878 0.007454 157878 0.010598 157878 0.009703 157878

Rata-rata 0.012113

0.007954

0.010231

0.009787



Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

1 0.071436 1310551 0.064791 1310551 0.062991 1310551 0.043404 1310551

2 0.062590 1310551 0.064795 1310551 0.064124 1310551 0.043313 1310551

3 0.062531 1310551 0.064748 1310551 0.061717 1310551 0.042720 1310551

4 0.062591 1310551 0.064592 1310551 0.062605 1310551 0.042929 1310551



17

5 0.062538 1310551 0.064679 1310551 0.061781 1310551 0.042837 1310551

6 0.062532 1310551 0.065446 1310551 0.061814 1310551 0.042737 1310551

7 0.062566 1310551 0.064606 1310551 0.061774 1310551 0.042939 1310551

8 0.062556 1310551 0.064582 1310551 0.061794 1310551 0.042882 1310551

9 0.073920 1310551 0.064846 1310551 0.061615 1310551 0.043071 1310551

10 0.063008 1310551 0.063017 1310551 0.061752 1310551 0.043740 1310551

Rata-rata 0.064627

0.064610

0.062197

0.043057



Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

1 0.511951 10563048 0.525326 10563048 0.546511 10563048 0.387635 10563048

2 0.509285 10563048 0.526795 10563048 0.548624 10563048 0.389000 10563048

3 0.507065 10563048 0.528836 10563048 0.549008 10563048 0.389580 10563048

4 0.507037 10563048 0.536740 10563048 0.551580 10563048 0.391520 10563048

5 0.508004 10563048 0.533302 10563048 0.553735 10563048 0.390984 10563048

6 0.507160 10563048 0.535607 10563048 0.558006 10563048 0.389883 10563048

7 0.510422 10563048 0.537254 10563048 0.561344 10563048 0.391040 10563048

8 0.518023 10563048 0.539520 10563048 0.561344 10563048 0.394642 10563048

9 0.522875 10563048 0.542058 10563048 0.562131 10563048 0.393235 10563048

10 0.517218 10563048 0.541857 10563048 0.561688 10563048 0.429307 10563048

Rata-rata 0.511904

0.534730

0.555397

0.394683



Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

1 4.060474 84984586 5.115586 84984586 5.574764 84984586 4.160144 84984586

2 4.198144 84984586 5.165908 84984586 5.619026 84984586 4.156325 84984586

3 4.344107 84984586 5.211490 84984586 5.653879 84984586 4.189345 84984586

4 4.479217 84984586 5.265666 84984586 5.656285 84984586 4.169900 84984586

5 4.598968 84984586 5.305254 84984586 5.682287 84984586 4.193594 84984586

6 4.714631 84984586 5.346070 84984586 5.724851 84984586 4.205695 84984586

7 4.911577 84984586 5.387553 84984586 5.740063 84984586 4.193306 84984586

8 4.956928 84984586 5.419079 84984586 5.738955 84984586 4.240962 84984586

9 4.813576 84984586 5.468172 84984586 5.766592 84984586 4.229627 84984586

10 5.033673 84984586 5.528556 84984586 5.774151 84984586 4.247946 84984586

Rata-rata 4.611130

5.321333

5.693085

4.198684



Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

Waktu (sec)

Jumlah Triple

1 51.617737 682032863 51.800432 682032863 53.192155 682032863 44.592707 682032863

2 55.513753 682032863 52.216148 682032863 53.301533 682032863 44.866254 682032863

3 56.917487 682032863 52.371644 682032863 53.352951 682032863 44.864587 682032863

4 56.753033 682032863 52.688662 682032863 53.592512 682032863 44.676666 682032863



18

5 57.596418 682032863 52.646071 682032863 53.724255 682032863 44.755065 682032863

6 57.901871 682032863 52.759391 682032863 53.525457 682032863 45.000306 682032863

7 58.176224 682032863 52.570906 682032863 53.553776 682032863 45.079034 682032863

8 58.634588 682032863 52.838995 682032863 53.680751 682032863 44.906529 682032863

9 58.981025 682032863 53.003361 682032863 53.685781 682032863 45.100222 682032863

10 59.266003 682032863 53.098005 682032863 53.292748 682032863 45.246331 682032863

Rata-rata 57.135814

52.599362

53.490192

44.908770



19

Lampiran III. Pseudocode program perhitungan triple tanpa paralelisme

// triple_seq.c

#include <stdio.h>

#include <stdlib.h>

int main()

{

int n;//banyaknya vertex

printf("How many vertex?");

scanf("%d",&n);

int matrix[n][n];

int i,j,k,triple=0;

//Create a undirected graph adjacency matrix random

for(i=0;i<n;i++)

{

for(j=i;j<n;j++)

{

matrix[i][j]=rand()%2;

matrix[j][i]=matrix[i][j];

}

}

//show adjacency matrix

printf("size of matrix is %dx%d¥n",n,n);

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

printf("%d ",matrix[i][j]);

}

printf("¥n");

}

//Count triples

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){


triple++;

}

}

}

}

printf("find triple on %f sec¥n",time);

triple=triple/3;

printf("triple=%d¥n",triple);

}



20

Lampiran IV. Pseudocode program perhitungan triple dengan paralelisme

// triple_par.c

#include <stdio.h>

#include <stdlib.h>

#include <omp.h>

int main()

{



scanf("%d",&n);

int matrix[n][n];

int x,y,triple=0;


for(x=0;x<n;x++)

{

for(y=x;y<n;y++)

{

matrix[x][y]=rand()%2;

matrix[y][x]=matrix[x][y];

}

}


printf("size of matrix is %dx%d¥n",n,n);

for(x=0;x<n;x++)

{

for(y=0;y<n;y++)

{

printf("%d ",matrix[x][y]);

}

printf("¥n");

}


//Count triples


{

int i,j,k,temp=0,




{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){


temp++;

}



21

}

}

}


{

triple+=temp;

}

}



printf("find triple on %f sec¥n",time);

triple=triple/3;

printf("triple=%d¥n",triple);

}



22

Lampiran V. Pseudocode program perhitungan triple dengan paralelisme tanpa

schedule

// triple_parallel1.c

#include <stdio.h>

#include <stdlib.h>

#include <omp.h>

int main()

{



scanf("%d",&n);


int x,y,triple=0;


for(x=0;x<n;x++)

{


}


for(x=0;x<n;x++)

{

for(y=x;y<n;y++)

{



}

}


printf("size of matrix is %dx%d\n",n,n);

for(x=0;x<n;x++)

{

for(y=0;y<n;y++)

{


}

printf("\n");

}


//Count triples




23

{

int i,j,k,temp=0,




{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}



printf("find triple on %f sec\n",time);

triple=triple/3;


}



24

Lampiran VI. Pseudocode program perhitungan triple dengan paralelisme schedule

static

//triple_for_static1.c

#include <stdio.h>

#include <stdlib.h>

#include <omp.h>

int main()

{



scanf("%d",&n);


int x,y,triple=0;


for(x=0;x<n;x++)

{


}


for(x=0;x<n;x++)

{

for(y=x;y<n;y++)

{



}

}



for(x=0;x<n;x++)

{

for(y=0;y<n;y++)

{


}

printf("\n");

}


//Count triples




25

{

int i,j,k,temp=0;

#pragma omp for schedule(static)

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}




triple=triple/3;


}



26

Lampiran VII. Pseudocode program perhitungan triple dengan paralelisme schedule

dynamic

// triple_for_dynamic1.c

#include <stdio.h>

#include <stdlib.h>

#include <omp.h>

int main()

{



scanf("%d",&n);


int x,y,triple=0;


for(x=0;x<n;x++)

{


}


for(x=0;x<n;x++)

{

for(y=x;y<n;y++)

{



}

}



for(x=0;x<n;x++)

{

for(y=0;y<n;y++)

{


}

printf("\n");

}


//Count triples




27

{

int i,j,k,temp=0;

#pragma omp for schedule(dynamic)

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}




triple=triple/3;


}



28

Lampiran VIII. Pseudocode program perhitungan triple dengan paralelisme schedule

guided

// triple_for_guided1.c

#include <stdio.h>

#include <stdlib.h>

#include <omp.h>

int main()

{



scanf("%d",&n);


int x,y,triple=0;


for(x=0;x<n;x++)

{


}


for(x=0;x<n;x++)

{

for(y=x;y<n;y++)

{



}

}



for(x=0;x<n;x++)

{

for(y=0;y<n;y++)

{


}

printf("\n");

}


//Count triples




29

{

int i,j,k,temp=0;

#pragma omp for schedule(guided)

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{


{

for(k=j+1;k<n;k++){


temp++;

}

}

}

}


{

triple+=temp;

}

}




triple=triple/3;


}

kommppuuttasii apparraalleell:: bggr raapphh...

Documents