Algoritma Paralel - Analisis

Analisis suatu algoritma membantu kita menentukan apakah algoritma tersebut berguna atau tidak. Umumnya, suatu algoritma dianalisis berdasarkan waktu pelaksanaannya(Time Complexity) dan jumlah ruang (Space Complexity) itu membutuhkan.

Karena kami memiliki perangkat memori canggih yang tersedia dengan biaya yang wajar, ruang penyimpanan tidak lagi menjadi masalah. Karenanya, kompleksitas ruang tidak terlalu dianggap penting.

Algoritma paralel dirancang untuk meningkatkan kecepatan komputasi komputer. Untuk menganalisis Algoritma Paralel, kami biasanya mempertimbangkan parameter berikut -

Kompleksitas waktu (Waktu Eksekusi),
Jumlah total prosesor yang digunakan, dan
Total biaya.

Kompleksitas Waktu

Alasan utama di balik pengembangan algoritma paralel adalah untuk mengurangi waktu komputasi suatu algoritma. Dengan demikian, mengevaluasi waktu eksekusi suatu algoritma sangat penting dalam menganalisis efisiensinya.

Waktu eksekusi diukur berdasarkan waktu yang dibutuhkan oleh algoritma untuk menyelesaikan suatu masalah. Total waktu eksekusi dihitung dari saat algoritme mulai mengeksekusi hingga saat berhenti. Jika semua prosesor tidak memulai atau mengakhiri eksekusi pada saat yang bersamaan, maka total waktu eksekusi dari algoritme adalah saat prosesor pertama memulai eksekusinya hingga saat prosesor terakhir menghentikan eksekusinya.

Kompleksitas waktu dari suatu algoritma dapat diklasifikasikan menjadi tiga kategori-

Worst-case complexity - Jika jumlah waktu yang dibutuhkan oleh algoritme untuk input tertentu adalah maximum.
Average-case complexity - Jika jumlah waktu yang dibutuhkan oleh algoritme untuk input tertentu adalah average.
Best-case complexity - Jika jumlah waktu yang dibutuhkan oleh algoritme untuk input tertentu adalah minimum.

Analisis Asymptotic

Kompleksitas atau efisiensi suatu algoritma adalah banyaknya langkah yang dijalankan oleh algoritma tersebut untuk mendapatkan keluaran yang diinginkan. Analisis asimtotik dilakukan untuk menghitung kompleksitas suatu algoritma dalam analisis teoritisnya. Dalam analisis asimtotik, panjang input yang besar digunakan untuk menghitung fungsi kompleksitas algoritme.

Note - Asymptoticadalah kondisi di mana garis cenderung bertemu dengan kurva, tetapi tidak berpotongan. Di sini garis dan kurva tidak menunjukkan gejala satu sama lain.

Notasi asimtotik adalah cara termudah untuk mendeskripsikan waktu eksekusi tercepat dan paling lambat untuk suatu algoritme menggunakan batas kecepatan tinggi dan batas rendah kecepatan. Untuk ini, kami menggunakan notasi berikut -

Notasi O besar
Notasi omega
Notasi theta

Notasi O besar

Dalam matematika, notasi Big O digunakan untuk merepresentasikan karakteristik asimtotik fungsi. Ini mewakili perilaku suatu fungsi untuk input besar dalam metode yang sederhana dan akurat. Ini adalah metode untuk mewakili batas atas waktu eksekusi algoritme. Ini mewakili jumlah waktu terlama yang diperlukan algoritme untuk menyelesaikan eksekusinya. Fungsi -

f (n) = O (g (n))

jika ada konstanta positif c dan n₀ seperti yang f(n) ≤ c * g(n) untuk semua n dimana n ≥ n₀.

Notasi omega

Notasi omega adalah metode untuk merepresentasikan batas bawah waktu eksekusi suatu algoritma. Fungsi -

f (n) = Ω (g (n))

jika ada konstanta positif c dan n₀ seperti yang f(n) ≥ c * g(n) untuk semua n dimana n ≥ n₀.

Notasi Theta

Notasi teta adalah metode yang merepresentasikan batas bawah dan batas atas dari waktu eksekusi suatu algoritma. Fungsi -

f (n) = θ (g (n))

jika ada konstanta positif c₁, c₂, dan n₀ sedemikian rupa sehingga c1 * g (n) ≤ f (n) ≤ c2 * g (n) untuk semua n dimana n ≥ n₀.

Mempercepat Algoritma

Kinerja algoritma paralel ditentukan dengan menghitungnya speedup. Speedup didefinisikan sebagai rasio waktu eksekusi kasus terburuk dari algoritma sekuensial tercepat yang diketahui untuk masalah tertentu dengan waktu eksekusi kasus terburuk dari algoritma paralel.

speedup =

Waktu eksekusi kasus terburuk dari sekuensial tercepat yang diketahui untuk masalah tertentu / Waktu eksekusi kasus terburuk dari algoritma paralel

Jumlah Prosesor yang Digunakan

Jumlah prosesor yang digunakan merupakan faktor penting dalam menganalisis efisiensi algoritma paralel. Biaya untuk membeli, memelihara, dan menjalankan komputer dihitung. Semakin besar jumlah prosesor yang digunakan oleh algoritme untuk memecahkan masalah, semakin mahal hasil yang diperoleh.