Analisa Kompleksitas Algoritma Paralel
[Ke Urutan Pembelajaran Paralel]
Pada saat sebuah algoritma digunakan untuk memecahkan sebuah persoalan, maka performance dari algoritma tersebut akan dinilai. Hal ini berlaku untuk algoritma, baik algoritma sekuensial maupun algoritma paralel. Penampilan sebuah algoritma pengolahan peralel dapat dinilai dari beberapa kriteria, seperti running time dan banyaknya prosesor yang digunakan.
Running Time
- Running time adalah waktu yang digunakan oleh sebuah algoritma untuk menyelesaikan masalah pada sebuah komputer paralel dihitung mulai dari saat algoritma mulai hingga saat algoritma berhenti. Jika prosesor-prosesornya tidak mulai dan selesai pada saat yang bersamaan, maka running time dihitung mulai saat komputasi pada prosesor pertama dimulai hingga pada saat komputasi pada prosesor terakhir selesai.
Counting Steps
- Untuk menentukan running time, secara teoritis dilakukan analisa untuk menentukan waktu yang dibutuhkan sebuah algoritma dalam mencari solusi dari sebuah masalah. Hal ini dilakukan dengan cara menghitung banyaknya operasi dasar, atau step (langkah), yang dilakukan oleh algoritma untuk keadaan terburuknya (worst case).
Langkah-langkah yang diambil oleh sebuah algoritma dibedakan ke dalam dua jenis yaitu :
- Computational step
Sebuah computational step adalah sebuah operasi aritmetika atau operasi logika yang dilakukan terhadap sebuah data dalam sebuah prosesor.
- Routing step.
Pada routing step, sebuah data akan melakukan perjalanan dari satu prosesor ke prosesor lain melalui shared memory atau melalui jaringan komunikasi.
Speedup
- Pengukuran speedup sebuah algoritma paralel adalah salah satu cara untuk mengevaluasi kinerja algoritma tersebut.
- Speedup adalah perbandingan antara waktu yang diperlukan algoritma sekuensial yang paling efisien untuk melakukan komputasi dengan waktu yang dibutuhkan untuk melakukan komputasi yang sama pada sebuah mesin pipeline atau paralel.
