Laporan Akhir Pemrosesan Paralel

OLEH: SUGENG/10210800

S1/UNIKOM

Pendahuluan

Pemrosesan paralel bertujuan untuk mempercepat komputasi data yang berukuran sangat besar, bila data tersebut dikerjakan dengan menggunakan satu komputer saja maka akan butuh waktu sangat lama untuk menyelesaikannya. Namun dalam pemrosesan paralel tidak lantas semakin banyak komputer yang digunakan maka komputasi otomatis menjadi lebih cepat, ada beberapa hal yang harus diperkhitungkan. Dalam kasus ini terdapat dua buah perhitungan yang akan dianalisis yaitu banyaknya komputasi perbandingan untuk mengurutkan data secara ascending serta komunikasi data pada pemrosesan paralel. Pada tugas ini digunakan sebuah algoritma insertion pada sekuensial komputer serta algoritma merge untuk menggabungkan kembali data yang telah disorting pada masing-masing  komputer. Adapun perangkat komputer untuk melakukan pemrosesan paralel digunakan sebanyak 4 buah komputer yang terkoneksi pada jaringan lokal berbentuk star.

1.      Algoritma pengurutan

Pengertian  algoritma secara umum adalah langkah-langkah  penyelesain suatu masalah dengan urutan dan metode tertentu yang dipengaruhi oleh pola pikir terhadap suatu masalah. Algoritma pengurutan (sorting) pada dasarnya adalah membandingkan antar data atau elemen berdasarkan kriteria dan kondisi tertentu.  Pada pengurutan (sorting)  integer (bilangan bulat positif atau negatif, termasuk nol), kriteria yang umum digunakan adalah lebih besar (>)  atau lebih kecil (<) terhadap elemen  integer yang lain.

1.1  Insertion Sort

Algoritma  insertion sort dapat dirangkum sebagai berikut:

  1. Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
  2. Bandingkan nilainya dengan elemen sebelumnya.
  3. Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut.  Decrement  i (kurangi nilainya dengan 1).
  4. Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
  5. Jika Ti-1  ≤ Ti  terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
  6. Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).

1.1.1 Kompleksitas Algoritma Insertion Sort

Kompleksitas algoritma insertion dihitung dari banyaknya jumlah perbandingan data yang dilakukan. Pada algoritma insertion tidak memiliki jumlah iterasi yang tetap sehingga akan terdapat kasus terbaik dan kasus terburuk dari setiap penyelesaian komputasi.

For  i= 1 up to n-1 

tukar = a[i] 

  for  j= i down to 0 

   if tukar < a[j-1]   then 

a[j]=a[j-1] 

else 

stop for 

endif

Endfor

  a[j]=tukar

Endfor

 

Gambar 1.Simulasi algoritma insertion.

Algoritma insertion terdiri dari 2 kalang bersarang.Dimana terjadi N-1 perulangan (dengan N adalah banyak elemen struktur data), dengan masing-masing perulangan terjadi i kali operasi perbandingan.i tersebut bernilai 1 untuk proses pertama, bernilai 2 untuk proses kedua, begitu seterusnya hingga proses ke N-1.

  1. Kasus terbaik:

Jika list data sudah dalam bentuk terurut dari kecil ke besar (ascending). Pada kasus ini maka efisiensi menjadi sebesar n-1.

Gambar 2.Simulasi algoritma insertion.

  1. Kasus terburuk:

Jika list data  dalam bentuk terurut yang terbalik (descending) sehingga perbandingan data (efisiensi) akan menjadi sebesar (n2-n)/2.

Gambar 3.Simulasi algoritma insertion.

            Setelah data terurut secara skuensial dalam satu komputer maka dalam pemrosesan paralel data tersebut dapat digabungkan menggunakan algoritma merge.

1.2 Algoritma Merge Sort

Algoritma merge sort digunakan untuk menggabungkan kembali dua data yang terdapat pada pemrosesan paralel setelah data itu diurutkan sebelumnya. Cara kerja algoritma merge adalah dengan membadingkan indeks awal pada variable data satu dengan indeks awal pada variable data kedua, jika salah satu dari data tersebut lebih kecil atau sama maka akan dipindah pada variabel data lain sebagai tempat penyimpanan sementara, kemudian indeks berikutnya pada variabel data yang memiliki data lebih kecil tadi dibandingan dengan data pada indeks divariabel data satunya, begitu seterusnya sampai semua data telah habis dibandingkan dan terurut pada variable yang telah disediakan.

1.2.1 Kopleksitas perbandingan merge sort

Algoritma penggabungan dapat dituliskan sebagai berikut :

  1. a.      i, j, J3 ← 0
  2. b.      Kerjakan baris 5 sampai dengan 7 selama  (i < J1) atau (j < J2)
  3. c.       J3 ← J3 + 1
  4. d.      Jika (T1[i] < T2[j])  maka T3[J3] ← T1[i], i ← i + 1
  5. e.       Jika (T1[i] >= T2[j]) maka T3[J3] ← T2[j], j ← j + 1
  6. f.        Jika (i > J1) maka kerjakan baris 9, jika tidak kerjakan baris 15
  7. g.      i ← j
  8. h.      Selama (i < J2) kerjakan baris 11 sampai dengan 13
  9. i.        J3 ← J3 + 1
  10. j.         T3[J3] ← T2[i]
  11. k.       13.i ← i + 1
  12. l.        Selesai
  13. m.    j ← i
  14. n.      Selama (j < J1) kerjakan baris 17 sampai dengan 19
  15. o.      J3 ← J3 + 1
  16. p.      T3[J3] ← T1[j]
  17. q.      j ← j + 1

 

Gambar 4. Proses pengurutan merge sort

Dari proses yang terjadi terlihat bahwa algoritma tersebut melakukan n-1 kali perbandingan utuk dapat mengurutkan data pada algoritma merge sort.

2. Kompleksitas dalam pemrosesan paralel

Pada pemrosesan paralel terjadi beberapa proses sorting yaitu, skuensial proses pada masing-masing komputer secara bersamaan menggunakan algoritma insertion sorting kemudian dilanjutkan proses penggabungan data dari dua komputer menggunakan algoritma merge, jika terdapat banyak komputer maka akan terjadi beberapa kali proses merge sorting sampai keseluruhan data menjadi satu kembali.

2.1 Kompleksitas 2 komputer

Dalam perhitungan ini terdapat dua algoritma yaitu:

pertama : insertion sort dengan rumus

kedua merge sort dengan rumus (n-1)

jika dijumlahkan menjadi

=

+ (n-1)

=  + (n-1)

=  (n2-2n +8n-8)

=  (n2+6n – 8)

2.2 Kompleksitas 3 komputer

Rumus kompleksitanya adalah penjumlahan dari skuensial komputer + penggabungan tahap1 + penggabungan tahap2 atau  insertion + merge1 + merge2:

=

=

=

=  (n2– 3n + 12n – 18 + 18n – 18)

=  (n2+27n – 36)

2.3 kompleksitas 4 komputer

=

=

=

=  (n2– 4n + 18n – 32 + 32n – 32)

=  (n2+46n – 64)

2.4 Kompleksitas sebanyak (P) Komputer

Kompleksitas dalam pemrosesan paralel diperoleh dengan cara melihat jumlah komputer yang digunakan, dalam hal ini pemrosesan pada banyak komputer menggunakan metode binery tree, dimana penggabungan data maksimal dilakukan antara dua komputer sampai semua data yang diinginkan tergabung kembali dalam satu komputer. Berikut ilustrasi pemrosesan paralel dalam banyak komputer

  1. 4 komputer

Terdapat log4  tahap untuk menyatukan data kedalam satu komputer

  1. 7 komputer

Terdapat log8 tahap untuk menyatukan data kedalam satu komputer

  1. 8 komputer

Terdapat log8 tahap untuk menyatukan data kedalam satu computer

  1. 9 komputer

Terdapat log16 tahap untuk menyatukan data kedalam satu komputer

  1. 16 komputer

Terdapat log16 tahap untuk menyatukan data kedalam satu komputer.

Dari ilustrasi diatas diketahui bahwa untuk meggabungkan data kedalam satu komputer dibutuhkan 2LogP tahap, dimana sisanya dibulatkan ke atas.

f. Rumus untuk P komputer adalah

a)      Jumlah komputer genap

b)      Jumlah  komputer ganjil

3. Perangkat Software Dan Hardware

Untuk dapat melakuakan komputasi secara paralel dibutuhkan beberapa software dan hardware pendukung.

3.1 Software

Perangkat Lunak yang digunakan berbasis sistem operasi windows yaitu windows 7 serta windows XP, selain itu juga digunakan beberapa aplikasi untuk mendukung pemrograman serta eksekusi program yaitu:

a. Microsoft Visual Studio 2010

b. MPICH2

3.2 Hardware

Dibutuhkan beberapa komputer untuk dapat mengeksekusi pemrosesan paralel, untuk itu digunakan beberapa komputer yang mana masing-masing komputer memiliki perangkat yang  berbeda yaitu:

a. Komputer 1 (OS windowsXP part3, CPU 2,7GHz, RAM 2G)

b. Komputer 2 (OS Windows7, CPU 1,3GHz, RAM 2G)

c. Komputer 3 (OS Windows7, CPU 1,86GHz, RAM 3G)

d. Komputer 4 (OS Windows7, CPU 1,6GHz, RAM 2G)

4. Perhitungan Waktu Eksekusi Algoritma Insertion dan Merge

Dalam pemrosesan paralel terjadi pembagian proses eksekusi pada masing-masing computer, dimana sertiap computer mengeksekusi dengan waktu yang berbeda-beda namun saling berkaitan.

4.1 Perhitungan waktu eksekusi pada 2 prosesor

Tabel Waktu eksekusi 2 prosesor

T

P (1)

P(2)

T P(1)

T P(2)

T1 Random data
T2 Kirim ke Kom 2 Terimadari kom 1 1/2 n 1/2 n
T3 Insertion Insertion (1/2n2-n)/2 (n2-n)/2
T4 Terima dari kom2 Kirim 1/2n 1/2n
T5 Merge Selesai n-1 n-1
T6 Selesai

4.2 Perhitungan waktu eksekusi pada 3 prosesor

Tabel Waktu eksekusi 3 prosesor

T

P 1

P 2

P 3

T P(1)

T P(2)

T P(3)

T1 Random data
T2 Kirim ke kom 2 Terima dari kom 1 1/3n 1/3n
T3 Kirim ke kom 3 Insertion Terima dari kom 1 1/3 n (1/3 n2-n)/2 1/3 n
T4 Insertion Insertion ((1/3 n)2-n)/2 ((1/3 n)2-n)/2
T5 Terima dari kom 3 Kirim ke kom 2 1/3n 1/3n
T6 Merge Selesai (2/3n)-1
T7 Terima dari kom 2 Kirim ke kom 1 (2/3n) (2/3n)
T8 merge selesai n-1
T9 selesai

4.3 Perhitungan waktu eksekusi pada 4 prosesor

Tabel Waktu eksekusi 2 prosesor

T

P 1

P 2

P 3

P 4

T P1

T P2

T P3

T P4

T1 Random data
T2 Kirim ke kom 2 Terima dari kom 1 1/2n 1/2n
T3 Kirim ke kom 3 Kirim ke kom 4 Terima dari kom 1 Terima dari kom 2 1/4n 1/4n 1/4n 1/4n
T4 insertion Insertion Insertion insertion ((1/4 n)2-n)/2 ((1/4 n)2-n)/2 ((1/4 n)2-n)/2 ((1/4 n)2-n)/2
T5 Terima dari kom 4 Terima dari kom 3 Kirim ke kom 1 Kirim ke kom 2 1/4n 1/4n 1/4n 1/4n
T6 Merge Merge Selesai Selesai 1/2n-1 1/2n-1
T7 Terima dari kom 2 Kirim ke kom 1 1/2n 1/2n
T8 Merge Selsesai n-1 n-1
T9 Selesai

4.4 Flowchart  pemrosesan paralel 2 prosesor

Gambar Flowchart Eksekusi 2 Komputer

4.5 Flowchart pemrosesan paralel 3 prosesor

Gambar Flowchart Eksekusi 3 Komputer


4.6 Flowchart pada pemrosesan 4 prosesor

Gambar Flowchart Eksekusi 4 Komputer

4.7  Flowchar prosedur insertion dan merge

Gambar Flowchart Eksekusi Insertion dan Merge Komputer

5. Pengujian dan Analisa

Pemrosesan paralel memungkinkan komputasi data yang lebih cepat, dalam penyelesaian komputustasi data pada kasus ini terdapat dua buah proses yang diperhitungkan yaitu proses perbandingan data untuk mengurutkan data yang menggunakan algoritma insertion serta yang kedua adalah transimisi data. Untuk merubah data jumlah proses eksekusi menjadi data dalam satuan waktu (s) perlu banyak sekali hal yang harus diperhitungkan, seperti besarnya clock prosesor, besarnya beban alokasi prosesor pada saat eksekusi program, jumlah cycle clock tiap interuksi, jumlah interuksi dalam program, beban prosesor oleh program lain yang sedang berjalan, banyak sekali hal yang mempengaruhi lamanya eksekusi penyelesaian suatu interuksi atau sebuah program. Sehingga dalam laporan ini hanya dibuat sebuah perbandingan lamanya proses yang terjadi antara penyelesaian dengan sekuensial komputer dengan paralel komputer.

5.1 Data Hasil Pengujian

a. Data Hasil Pengujian 1 Komputer

Tabel Hasil Pengujian 1 Komputer

Jumlah Data

Insertion

1000

241548

10000

25064077

100000

2465999636

200000

9895523458

300000

22298125629

400000

39622488684

500000

61855844967

1000000

247470921511

b. Data Hasil Pengujian

Tabel Hasil Pengujian 2 Komputer

Jumlah Data

Juml ah kompleksitas

Jumlah merge

Jumlah komunikasi

Total Proses Eksekusi

1000

64128

996

1000

66124

10000

6141642

9943

10000

6161585

100000

617869784

99498

100000

618069282

200000

2471702612

198919

200000

2472101531

300000

5570336325

298255

300000

5570934580

400000

9849909081

398030

400000

9850707111

500000

15427239500

497520

500000

15428237020

600000

22288576230

597042

600000

22289773272

700000

30333930838

696388

700000

30335327226

800000

39583781486

796062

800000

39585377548

900000

50222602416

895635

900000

50224398051

1000000

61949982128

994903

1000000

61951977031

1100000

74984282481

1094581

1100000

74986477062

1300000

104628415531

1293558

1300000

104631009089

1500000

139253769242

1492587

1500000

139256761829

2000000

247513351332

1990043

2000000

247517341375

c. Data Hasil Pengujian 3 Komputer

Tabel Lama Eksekusi 3 Komputer

Jumlah Data

Insertion

Merge

Lama Komunikasi

Total Eksekusi

1000

28229

997

1340

30566

10000

2725774

9928

13400

2749102

100000

274148409

99353

134000

274381762

200000

1095328795

198678

268000

1095795473

300000

2488871001

298011

402000

2489571012

400000

4414128221

397254

536000

4415061475

500000

6862497121

496647

670000

6863663768

1000000

27445459872

993421

1340000

27447793293

1100000

33227962746

1092555

1474000

33230529301

1300000

46381982824

1291329

1742000

46385016153

1500000

61849679835

1490006

2010000

61853179841

2000000

110036682935

1986448

2680000

110041349383

Tabel Lama Eksekusi 4 Komputer

Jumlah Data

Insertion

Merge

Komunikasi

Total Proses eksekusi

1000

15561

1489

1500

18550

10000

1535556

14940

15000

1565496

100000

155675759

149213

150000

155974972

200000

619469595

298522

300000

620068117

300000

1390662690

447736

450000

1391560426

400000

2477481217

596981

600000

2478678198

500000

3865146075

746194

750000

3866642269

1000000

15474197514

1492400

1500000

15477189914

1100000

18699693787

1641731

1650000

18702985518

1300000

26153990254

1940099

1950000

26157880353

1500000

34845710579

2238629

2250000

34850199208

2000000

61823843893

2984942

3000000

61829828835

e. Data Kompleksitas Masing-Masing Komputer

Tabel Perbandingan Waktu Proses Pada Beberapa Komputer

Jumlah Data

Total Proses 1 Kom

Total Proses 2 Kom

Total Proses 3 Kom

Total Proses 4 Kom

1000

241548

66124

30566

18550

10000

25064077

6161585

2749102

1565496

100000

2465999636

618069282

274381762

155974972

200000

9895523458

2472101531

1095795473

620068117

300000

22298125629

5570934580

2489571012

1391560426

400000

39622488684

9850707111

4415061475

2478678198

500000

61855844967

15428237020

6863663768

3866642269

1000000

247470921511

61951977031

27447793293

15477189914

1100000

74986477062

33230529301

18702985518

1300000

104631009089

46385016153

26157880353

1500000

139256761829

61853179841

34850199208

2000000

247517341375

110041349383

61829828835

f. Grafik Perbandingan waktu Proses Beberapa Komputer

Gambar Grafik Lama Waktu Proses Beberapa Komputer

6.  Kesimpulan

a.   Dengan menggunakan algoritma insertion, semakin banyak data (>500.000) yang dieksekusi maka waktu komputasi menjadi naik derastis bila dikerjakan hanya menggunakan satu komputer.

b. Semakin banyak komputer yang digunakan maka akan mempercepat proses eksekusi meskipun besarnya komunikasi data juga semakin bertambah namun tidak terlalu berpengaruh pada kompleksitas proses eksekusi, jika menggunakan 2 komputer maka jumlah data yang dieksekusi akan 2 kali lipat lebih banyak dari satu komputer, jika menggunakan 3 komputer maka jumlah data yang dieksekusi akan 3 kali lebih banyak dari 1 komputer dengan jumlah proses yang kurang lebih sama.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s