Untuk Diimplementasikan pada Kasus Perhitungan Jumlah Triple pada Graph Tak Berarah

Komputasi Paralel: Graph Tak Berarah Menggunakan Adjacency Matrix Untuk Diimplementasikan pada Kasus Perhitungan Jumlah Triple pada Graph Tak Berarah Achmad Fauzan [email protected]

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.

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 Komunitas eLearning IlmuKomputer.Com Copyright © 2003-2014 IlmuKomputer.Com

1

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

Komunitas eLearning IlmuKomputer.Com Copyright © 2003-2014 IlmuKomputer.Com

2

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 Komunitas eLearning IlmuKomputer.Com Copyright © 2003-2014 IlmuKomputer.Com

3

Pseudocode perhitungan triple tanpa paralelisme adalah sebagai berikut. //Count triples for(i=0;i
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(), Komunitas eLearning IlmuKomputer.Com Copyright © 2003-2014 IlmuKomputer.Com

4

nth=omp_get_num_threads(); for(i=me;i
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 double start = omp_get_wtime(); //Count triples for(i=0;i
Dengan Paralelisme double start = omp_get_wtime(); //Count triples #pragma omp parallel { int i,j,k,temp=0, me=omp_get_thread_num(), nth=omp_get_num_threads(); for(i=me;i
5

double end = omp_get_wtime(); double time = end-start; printf("find triple on %f sec\n",time); triple=triple/3; printf("triple=%d\n",triple);

temp++; } } } } #pragma omp critical { triple+=temp; } } double end = omp_get_wtime(); double time = end-start; printf("find triple on %f sec\n",time); triple=triple/3; printf("triple=%d\n",triple);

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 5 10 20 40 80 160 320 640 1280

Tanpa Paralelisme Rata-rata waktu Jumlah (sec) triple 0.000003 2 0.000014 18 0.000088 145 0.000582 1105 0.004309 9344 0.016460 81018 0.080972 663333 0.603690 5392748 4.949615 43549936

Dengan Paralelisme Rata-rata waktu Jumlah (sec) triple 0.002185 2 0.002530 18 0.003158 145 0.004668 1105 0.005492 9344 0.009734 81018 0.035921 663333 0.238395 5392748 1.793848 43549936

Selisih waktu 0.002182 0.002516 0.003070 0.004087 0.001183 -0.006726 -0.045051 -0.365295 -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.


6

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.


7

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
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 #pragma omp parallel { int i,j,k,temp=0, #pragma omp for schedule(static) for(i=0;i

8

2. Dynamic Pseudocode yang digunakan adalah sebagai berikut. //Count triples #pragma omp parallel { int i,j,k,temp=0, #pragma omp for schedule(dynamic) for(i=0;i
3. Guided Pseudocode yang digunakan adalah sebagai berikut. //Count triples #pragma omp parallel { int i,j,k,temp=0, #pragma omp for schedule(guided) for(i=0;i

9

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 100 200 400 800 1600 3200

Tanpa schedule Rata-rata Jumlah waktu triple (sec) 0.001853 19697 0.012113 157878 0.064627 1310551 0.511904 10563048 4.611130 84984586 57.135814 682032863

Schedule static Rata-rata Jumlah waktu triple (sec) 0.001334 19697 0.007954 157878 0.064610 1310551 0.534730 10563048 5.321333 84984586 52.599362 682032863

Schedule dynamic Rata-rata Jumlah waktu triple (sec) 0.000947 19697 0.010231 157878 0.062197 1310551 0.555397 10563048 5.693085 84984586 53.490192 682032863

Schedule guided Rata-rata Jumlah waktu triple (sec) 0.000773 19697 0.009787 157878 0.043057 1310551 0.394683 10563048 4.198684 84984586 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.


10

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 Komunitas eLearning IlmuKomputer.Com Copyright © 2003-2014 IlmuKomputer.Com

11

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.


12

Lampiran I. Tabel pengamatan pada pengujian perhitungan triple tanpa paralelisme dan dengan paralelisme. Tabel pengujian menggunakan 5 buah vertex Pengujian ke1 2 3 4 5 6 7 8 9 10 Rata-rata

Tanpa Paralelisme Waktu perhitungan (sec) 0.000004 0.000004 0.000004 0.000004 0.000003 0.000002 0.000004 0.000003 0.000003 0.000003 0.000003

Jumlah triple 2 2 2 2 2 2 2 2 2 2

Dengan Paralelisme Waktu perhitungan Jumlah (sec) triple 0.003718 2 0.003028 2 0.001792 2 0.002454 2 0.002039 2 0.001230 2 0.001783 2 0.001458 2 0.003072 2 0.001280 2 0.002185

Jumlah triple 18 18 18 18 18 18 18 18 18 18


Tabel pengujian menggunakan 10 buah vertex Pengujian ke1 2 3 4 5 6 7 8 9 10 Rata-rata


Tabel pengujian menggunakan 20 buah vertex Tanpa Paralelisme Waktu perhitungan (sec) 1 0.000088 2 0.000088 3 0.000088 4 0.000088 5 0.000087 6 0.000088 7 0.000088 8 0.000089 Komunitas eLearning IlmuKomputer.Com Copyright © 2003-2014 IlmuKomputer.Com Pengujian ke-

Jumlah triple 145 145 145 145 145 145 145 145

Dengan Paralelisme Waktu perhitungan Jumlah (sec) triple 0.001756 145 0.003433 145 0.003765 145 0.003930 145 0.003586 145 0.004580 145 0.002576 145 0.003193 145

13

9 10 Rata-rata

0.000089 0.000087 0.000088

145 145

0.001602 0.003162 0.003158

145 145



Jumlah triple 1105 1105 1105 1105 1105 1105 1105 1105 1105 1105


Jumlah triple 9344 9344 9344 9344 9344 9344 9344 9344 9344 9344




Tabel pengujian menggunakan 160 buah vertex Pengujian ke1 2 3 4 5 6 7

Tanpa Paralelisme Waktu perhitungan (sec) 0.026298 0.011498 0.020957 0.016425 0.015704 0.015008 0.015432


Jumlah triple 81018 81018 81018 81018 81018 81018 81018

Dengan Paralelisme Waktu perhitungan Jumlah (sec) triple 0.016600 81018 0.009798 81018 0.012643 81018 0.008698 81018 0.005519 81018 0.009355 81018 0.008520 81018

14

8 9 10 Rata-rata

0.011608 0.010059 0.021607 0.016460

81018 81018 81018

0.011545 0.008502 0.006160 0.009734

81018 81018 81018



Jumlah triple 663333 663333 663333 663333 663333 663333 663333 663333 663333 663333

Dengan Paralelisme Waktu perhitungan (sec) 0.036960 0.033988 0.036638 0.040505 0.036380 0.034577 0.038381 0.035003 0.034436 0.032338 0.035921

Jumlah triple 663333 663333 663333 663333 663333 663333 663333 663333 663333 663333

Dengan Paralelisme Waktu perhitungan (sec) 0.239225 0.238045 0.233274 0.234727 0.235242 0.234364 0.231468 0.243389 0.232529 0.261682 0.238395

Jumlah triple 5392748 5392748 5392748 5392748 5392748 5392748 5392748 5392748 5392748 5392748



Jumlah triple 5392748 5392748 5392748 5392748 5392748 5392748 5392748 5392748 5392748 5392748

Tabel pengujian menggunakan 1280 buah vertex Pengujian ke1 2 3 4 5 6

Tanpa Paralelisme Waktu perhitungan Jumlah (sec) triple 4.961537 43549936 4.947825 43549936 4.944057 43549936 4.976400 43549936 4.936359 43549936 4.963781 43549936


Dengan Paralelisme Waktu perhitungan Jumlah (sec) triple 1.795396 43549936 1.797618 43549936 1.791860 43549936 1.789855 43549936 1.807901 43549936 1.787250 43549936

15

7 8 9 10 Rata-rata

4.934203 4.953855 4.944076 4.934055 4.949615

43549936 43549936 43549936 43549936

1.791889 1.779464 1.802016 1.795233 1.793848

43549936 43549936 43549936 43549936

Lampiran II. Tabel pengamatan pada pengujian perhitungan triple dengan paralelisme tanpa schedule dan dengan schedule static, dynamic, maupun guided. Tabel pengujian menggunakan 100 buah vertex Uji ke1 2 3 4 5 6 7 8 9 10 Rata-rata

Tanpa schedule Waktu Jumlah (sec) Triple 0.005418 19697 0.001678 19697 0.001371 19697 0.002954 19697 0.002256 19697 0.000971 19697 0.000948 19697 0.000949 19697 0.001040 19697 0.000948 19697 0.001853

Schedule static Waktu Jumlah (sec) Triple 0.001001 19697 0.000993 19697 0.001132 19697 0.000994 19697 0.000992 19697 0.000990 19697 0.003018 19697 0.002206 19697 0.001012 19697 0.001002 19697 0.001334

Schedule dynamic Waktu Jumlah (sec) Triple 0.000981 19697 0.000965 19697 0.000943 19697 0.000938 19697 0.000936 19697 0.000946 19697 0.000944 19697 0.000943 19697 0.000937 19697 0.000940 19697 0.000947

Schedule guided Waktu Jumlah (sec) Triple 0.000773 19697 0.000775 19697 0.000768 19697 0.000771 19697 0.000775 19697 0.000771 19697 0.000774 19697 0.000770 19697 0.000774 19697 0.000778 19697 0.000773



Schedule dynamic Waktu Jumlah (sec) Triple 0.062991 1310551 0.064124 1310551 0.061717 1310551 0.062605 1310551

Schedule guided Waktu Jumlah (sec) Triple 0.043404 1310551 0.043313 1310551 0.042720 1310551 0.042929 1310551

Tabel pengujian menggunakan 200 buah vertex Uji ke1 2 3 4 5 6 7 8 9 10 Rata-rata



Tabel pengujian menggunakan 400 buah vertex Uji ke1 2 3 4

Tanpa schedule Waktu Jumlah (sec) Triple 0.071436 1310551 0.062590 1310551 0.062531 1310551 0.062591 1310551

Schedule static Waktu Jumlah (sec) Triple 0.064791 1310551 0.064795 1310551 0.064748 1310551 0.064592 1310551


16

5 6 7 8 9 10 Rata-rata

0.062538 0.062532 0.062566 0.062556 0.073920 0.063008 0.064627

1310551 1310551 1310551 1310551 1310551 1310551

0.064679 0.065446 0.064606 0.064582 0.064846 0.063017 0.064610

1310551 1310551 1310551 1310551 1310551 1310551

0.061781 0.061814 0.061774 0.061794 0.061615 0.061752 0.062197

1310551 1310551 1310551 1310551 1310551 1310551

0.042837 0.042737 0.042939 0.042882 0.043071 0.043740 0.043057

1310551 1310551 1310551 1310551 1310551 1310551











Schedule dynamic Waktu Jumlah (sec) Triple 53.192155 682032863 53.301533 682032863 53.352951 682032863 53.592512 682032863

Schedule guided Waktu Jumlah (sec) Triple 44.592707 682032863 44.866254 682032863 44.864587 682032863 44.676666 682032863

Tabel pengujian menggunakan 3200 buah vertex Uji ke1 2 3 4

Tanpa schedule Waktu Jumlah (sec) Triple 51.617737 682032863 55.513753 682032863 56.917487 682032863 56.753033 682032863

Schedule static Waktu Jumlah (sec) Triple 51.800432 682032863 52.216148 682032863 52.371644 682032863 52.688662 682032863


17

5 6 7 8 9 10 Rata-rata

57.596418 57.901871 58.176224 58.634588 58.981025 59.266003 57.135814

682032863 682032863 682032863 682032863 682032863 682032863

52.646071 52.759391 52.570906 52.838995 53.003361 53.098005 52.599362


682032863 682032863 682032863 682032863 682032863 682032863

53.724255 53.525457 53.553776 53.680751 53.685781 53.292748 53.490192

682032863 682032863 682032863 682032863 682032863 682032863

44.755065 45.000306 45.079034 44.906529 45.100222 45.246331 44.908770

18

682032863 682032863 682032863 682032863 682032863 682032863

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
19

Lampiran IV. Pseudocode program perhitungan triple dengan paralelisme // triple_par.c #include <stdio.h> #include <stdlib.h> #include int main() { int n;//banyaknya vertex printf("How many vertex?"); scanf("%d",&n); int matrix[n][n]; int x,y,triple=0; //Create a undirected graph adjacency matrix random for(x=0;x
20

} } } #pragma omp critical { triple+=temp; } } double end = omp_get_wtime(); double time = end-start; printf("find triple on %f sec¥n",time); triple=triple/3; printf("triple=%d¥n",triple); }


21

Lampiran V. Pseudocode program perhitungan triple dengan paralelisme tanpa schedule // triple_parallel1.c #include <stdio.h> #include <stdlib.h> #include int main() { int n;//banyaknya vertex printf("How many vertex?"); scanf("%d",&n); int **matrix;//matrix[n][n]; int x,y,triple=0; matrix=(int **)malloc(10*n); for(x=0;x
22

{ int i,j,k,temp=0, me=omp_get_thread_num(), nth=omp_get_num_threads(); for(i=me;i

23

Lampiran VI. Pseudocode program perhitungan triple dengan paralelisme schedule static //triple_for_static1.c #include <stdio.h> #include <stdlib.h> #include int main() { int n;//banyaknya vertex printf("How many vertex?"); scanf("%d",&n); int **matrix;//matrix[n][n]; int x,y,triple=0; matrix=(int **)malloc(10*n); for(x=0;x
24

{ int i,j,k,temp=0; #pragma omp for schedule(static) for(i=0;i

25

Lampiran VII. Pseudocode program perhitungan triple dengan paralelisme schedule dynamic // triple_for_dynamic1.c #include <stdio.h> #include <stdlib.h> #include int main() { int n;//banyaknya vertex printf("How many vertex?"); scanf("%d",&n); int **matrix;//matrix[n][n]; int x,y,triple=0; matrix=(int **)malloc(10*n); for(x=0;x
26

{ int i,j,k,temp=0; #pragma omp for schedule(dynamic) for(i=0;i

27

Lampiran VIII. Pseudocode program perhitungan triple dengan paralelisme schedule guided // triple_for_guided1.c #include <stdio.h> #include <stdlib.h> #include int main() { int n;//banyaknya vertex printf("How many vertex?"); scanf("%d",&n); int **matrix;//matrix[n][n]; int x,y,triple=0; matrix=(int **)malloc(10*n); for(x=0;x
28

{ int i,j,k,temp=0; #pragma omp for schedule(guided) for(i=0;i

29

Untuk Diimplementasikan pada Kasus Perhitungan Jumlah Triple pada Graph Tak Berarah

Recommend Documents