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 |
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
