Tampilkan postingan dengan label algoritma. Tampilkan semua postingan
Tampilkan postingan dengan label algoritma. Tampilkan semua postingan

PROGRAM VERIFIKASI ALGORITMA, METODE DIAGONAL, PARALLELISM, PENGURUTAN PARALLELISM

Program Verifikasi Algoritma, Metode Diagonal

Dalam program verifikasi algoritma kita dihadapkan bahwa apakah komputer dapat memverifikasi algoritma yang telah kita buat, apakah input yang kita berikan sesuai dan dapat memecahkan masalah yang dihadapkan.


Metode diagonal yang dipublikasikan oleh Georg Cantor yang merupakan pembuktian matematis bahwa ada himpunan terbatas yang tidak dapat dimasukan dalam korespondensi satu-ke-satu dengan himpunan tak terhingga dari bilangan asli. Himpunan-himpunan terebut dikenal sebagai himpunan yang tidak bisa dihitung.

Metode Diagonal
Metode Diagonal

 

Pembuktian program dengan metode diagonal dapat divisualisasikan dengan membayangkan sebuah tabel terbatas, yang sudah diberikan program yang sudah dibuat terhadap semua input yang mungkin (secara sederhana, input dalam bilangan integer).


Daftar program tercantum secara vertikal disebelah kiri dan input tercantum secara horizontal di bagian bawah. Pada pertemuan antara baris ke I dan kolom ke J kita dapat memastikan apakah program I menghentikan kolom J atau tidak.


Sekarang kita membangun sebuah program imajiner baru yang akan menjadi versi samaran dari program yang dibangun sebelumnya. 

 

Prilaku penghentian  adalah “negatif” pada garis diagonal tabel. Dengan kata lain program ini terbentuk dan berjalan pada semua masukan (input), ia berhenti hanya apabila program ke-J tidak akan dihentikan pada J dan tidak berhenti jika program ke-J an dihentikan pada J.


Pembuktian seperti ini secara singkat dapat dijelaskan dengan mengatakan bahwa kita telak mendiagonalkan semua program dan semua masukan, membangun S menjadi negatif atau sebaliknya dari diagonal tersebut. Kontradiksi kemudian mengikuti semua ketidakmungkinan S menjadi salah satu program pada daftar.


Baca Juga:


Paralellism dan Pengurutan Paralelism

Algoritma parallel merupakan algoritma yang dapat dieksekusi dalam satu waktu pada banyak perangkat processing yang berbeda, dan pada akhirnya akan digabungkan kembali untuk mendapatkan hasil yang benar.  


Analisis algoritma paralel biasanya dilakukan dengan asumsi bahwa jumlah tak terbatas dari prosesor yang tersedia. Teknik algoritma parallel, sekalipun didukung oleh teknologi prosesor yang berkembang sangat pesat, komputer sekuensial tetap akan mengalami keterbatasan dalam hal kecepatan pemrosesannya. 

 

Hal ini menyebabkan lahirnya konsep keparalelan (parallelism) untuk menangani masalah dan aplikasi yang membutuhkan kecepatan pemrosesan yang sangat tinggi, seperti misalnya prakiraan cuaca, simulasi pada reaksi kimia, perhitungan aerodinamika dan lain-lain.

Parallelism menurut Michael J. Quin adalah konsep komputer parallel yang diberikan oleh Michael J. Quin yang membedakan komputer parallel berdasarkan data parallelism dan control parallelism.

  • Data parallelism merupakan penerapan operasi yang sama secara simultan terhadap elemen-elemen dari kumpulan data.
  • Control parallelism merupakan penerapan operasi-operasi yang berbeda terhadap elemen-elemen data yang berbeda secara bersamaan.


Teknik Pembangunan Algoritma Paralel

Paralelisme Data

Teknik paralelisme data merupakan teknik yang paling banyak digunakan dalam program paralel. Teknik ini lahir dari penelitian bahwa aplikasi utama komputasi paralel adalah dalam bidang sain dan engineer, yang umumnya melibatkan array multi-dimensi yang sangat besar. 

 

Dalam program sekuensial biasa, array ini dimanipulasi dengan mempergunakan perulangan bersarang untuk mendapatkan hasil. Kebanyakan program paralel dibentuk dengan mengatur ulang algoritma sekuensial agar perulangan bersarang tersebut dapat dilaksanakan secara paralel.

 

Partisi Data

Merupakan teknik khusus dari Paralelisme Data, dimana data disebar ke dalam memori-memori lokal multikomputer. Sebuah proses paralel dimana ditugaskan untuk mengoperasikan masing-masing bagian data. Proses tersebut harus terdapat dalam lokal memori yang sama dengan bagian data, karena itu proses dapat mengakses data tersebut secara lokal. 

 

Untuk memperoleh kinerja yang baik, setiap proses harus memperhatikan variabel-variabel dan data-data lokalnya masing-masing. Jika suatu proses membutuhkan akses data yang terdapat dalam remote memori, maka hal ini dapat dilakukan melalui jaringan message passing yang menghubungkan prosesor-prosesor.

 

Algoritma Relaksasi

Pada algoritma ini, setiap proses tidak membutuhkan sinkronisasi dan komunikasi antar proses. Meskipun prosesor mengakses data yang sama, setiap prosesor dapat melakukan komputasi sendiri tanpa tergantung pada data antara yang dihasilkan oleh proses lain. Contoh algoritma relaksasi adalah algoritma perkalian matrik, pengurutan dengan mengunakan metode ranksort dan lain sebagainya.

 

Paralelisme Sinkron

Aplikasi praktis dari komputasi paralel adalah untuk problem yang melibatkan array multi-dimensi yang sangat besar. Problem tersebut mempunyai peluang yang baik untuk paralelisme data karena elemen yang berbeda dalam array dapat diproses secara paralel. 

 

Teknik komputasi numerik pada array ini biasanya iteratif, dan setiap iterasi akan mempengaruhi iterasi berikutnya untuk menuju solusi akhir. Misalnya saja untuk solusi persamaan numerik pada sistem yang besar. Umumnya, setiap iterasi mempergunakan data yang dihasilkan oleh iterasi sebelumnya dan program akhirnya menuju suatu solusi dengan akurasi yang dibutuhkan. Algoritma iterasi ini mempunyai peluang paralelisme pada setiap iterasinya.


Komputasi Pipeline

Pada komputasi pipeline, data dialirkan melalui seluruh struktur proses, dimana masing-masing proses membentuk tahap-tahap tertentu dari keseluruhan komputasi . Algoritma ini dapat berjalan dengan baik pada multikomputer, karena adanya aliran data dan tidak banyak memerlukan akses ke data bersama.


Synchronization Delay

Ketika proses paralel disinkronkan, berarti bahwa suatu proses harus menunggu proses lainnya. Dalam beberapa program paralel, jumlah waktu tunda ini dapat menyebabkan bottleneck dan mengurangi speedup keseluruhan. 

 

Load Imbalance Dalam beberapa program paralel, tugas komputasi dibangun secara dinamis dan tidak dapat diperkirakan sebelumnya. Karena itu harus selalu ditugaskan ke prosesor-prosesor sejalan dengan pembangunan tugas tersebut. Hal ini dapat menyebabkan suatu prosesor tidak bekerja (idle), sementara prosesor lainnya tidak dapat mengerjakan task yang ditugaskannya.


Untuk melakukan operasi pengurutan (sorting) secara paralel terdapat dua cara:

Range-Partitioning Sort 

  • Pilihlah prosesor P0, ..., Pm, di mana m [] n -1 untuk melakukan sorting.
  • Buatlah range-partition-vector dengan m anggota, pada atribut sorting 
  • Distribusi ulang relasi menggunakan range-partitioning 
  • Semua tuple yang berada di antara range ke-i dikirim ke prosesor Pi
  • Pi  menyimpan tuple yang diterimanya sementara di disk Di. 
  • Masing-masing prosesor Pi mengurutkan partisi relasi secara lokal. 
  • Masing-masing prosesor melakukan operasi (sorting) yang sama secara paralel dengan prosesor yang lain, tanpa adanya interaksi satu sama lain (data parallelism).
  • Pada akhirnya operasi penggabungan hasil pengurutan tadi dilakukan dengan mudah: operasi range-partitioning menjamin bahwa, untuk 1<=i<=j<= m, nilai key dalam prosesor Pi  semuanya lebih kecil dari nilai key pada Pj.

 

Parallel External Sort-Merge 

  • Asumsi bahwa relasi telah dipartisi di antara disk-disk D0, ..., Dn-1 (dengan cara apapun).
  • Masing-masing prosesor Pi secara lokal mengurutkan data pada disk Di.
  • Hasil operasi pengurutan yang dilakukan di masing-masing prosesor kemudian digabungkan untuk mendapat hasil pengurutan akhir. 
  • Untuk menggabungkan hasil pengurutan masing-masing prosesor tadi secara paralel dilakukan sebagai berikut: 
    • Partisi-partisi yang sudah diurutkan di masing-masing prosesor Pi  kemudian di-rangepartitioning ke seluruh prosesor P0, ..., Pm-1.
    • Masing-masing prosesor Pi melakukan pengabungan dengan serangkaian data   yang sudah terurut tadi pada saat mereka diterima, untuk memperoleh satu rangkaian penuh yang terurut.
    • Rangkaian yang sudah terurut pada prosesor-prosesor P0,..., Pm-1 kemudian digabungkan untuk memperoleh hasil akhir.


Contoh

Algoritma Pencarian Nilai Terbesar Secara Parallel

Contoh :

A memiliki nilai = 1, 9, 2, 8, 3, 7, 4, 6, 5, 0

1.      i←0

2.      besar←false

3.      Selama (tidak  besar) dan (i<=N) kerjakan baris 4

4.      Jika (Data[i] > i+1) maka besar←true, jika tidak i←i+1

5.      Jika (besar) maka i adalah indeks dari data yang besar dan tampilkan.

Maka :

1.      i←0

2.      Besar←False

3.      Selama (tidak besar) dan (i<=N) kerjakan baris 4

4.      Jika (Data[1] > 9) maka besar←true, jika tidak i←9

5.      Jika (Besar) maka i adalah indeks dari data yang besar dan tampilkan.

6.      Maka akan memperoleh hasil 9

 

Algoritma Penghitungan Rerata Secara Parallel.

Contoh : A = 6, 3, 2, 9, 7

1.      i = 0

2.      for i=0 to i<=N do

3.      Data[i] +

 

Kondisi awal : daftar dari n >= 1 adalah element dari A[0 …(n-1)]

Kondisi akhir : Penjumlahan dari element di bagi jumlah element A dan simpan di A[0]

Variable global : n, A[0, …(n-1)],j

Begin

   Spawn(P0, P1, P2, …, P[n/2 j-1])

   For all Pi where 0 <= i <= [n/2]-1 do

               For j = o to [log n] -1 do

                           If i modulo 2j = 0 and 2i + 2j < n then

                                       A[2i]=A[2i]+A[2i+2J]

                           End if

               End For

            End For

            A[0]/max[j]

End


Algoritma Pengurutan Secara Sekuensial akan Mengurutkan Data dengan Nilai Terkecil akan dinaikan ke Atas dan Sebaliknya Data dengan Nilai Terbesar akan Berada di Posisi Bawah

Contoh : A = {25, 22, 18, 20, 15}, dimana A adalah sebuah variable array

1.      i = 0

2.      Selama (i=0; i<n-1; i++), kerjakan baris 3

3.      Jika (A[i] >= A[i+1] maka

§  Temp = A[i]

§  A[i] = A[i+1]

§  A[i+1] = temp

4.      Tampilkan A[i]

5.      Kembali i

Maka

1.      i = 0

2.      Selama (i=0; i<n-1; i++), kerjakan baris 3

3.      Jika (A[25] >= A[22] maka

§  Temp = A[25]

§  A[25] = A[22]

§  A[22] = temp

4.      Tampilkan A[25]

5.      Kembali 25

Maka hasil sorting dengan sekuensial :

15

18

20

22 

25

 

Ladangtekno