Paralel Algoritma - Analiz

Bir algoritmanın analizi, algoritmanın yararlı olup olmadığını belirlememize yardımcı olur. Genel olarak, bir algoritma yürütme süresine göre analiz edilir(Time Complexity) ve alan miktarı (Space Complexity) gerektirir.

Makul bir maliyetle sunulan gelişmiş bellek cihazlarımız olduğundan, depolama alanı artık sorun olmaktan çıkıyor. Bu nedenle, uzay karmaşıklığına çok fazla önem verilmiyor.

Paralel algoritmalar, bir bilgisayarın hesaplama hızını artırmak için tasarlanmıştır. Bir Paralel Algoritmayı analiz etmek için normalde aşağıdaki parametreleri dikkate alırız -

Zaman karmaşıklığı (Yürütme Zamanı),
Kullanılan toplam işlemci sayısı ve
Toplam tutar.

Zaman Karmaşıklığı

Paralel algoritmalar geliştirmenin arkasındaki ana sebep, bir algoritmanın hesaplama süresini azaltmaktı. Bu nedenle, bir algoritmanın yürütme süresinin değerlendirilmesi, verimliliğini analiz etmede son derece önemlidir.

Yürütme süresi, algoritmanın bir problemi çözmek için harcadığı süre esas alınarak ölçülür. Toplam yürütme süresi, algoritmanın çalışmaya başladığı andan durduğu ana kadar hesaplanır. Tüm işlemciler aynı anda yürütmeyi başlatmaz veya bitirmezlerse, algoritmanın toplam yürütme süresi, ilk işlemcinin yürütmeye başladığı ve son işlemcinin yürütmeyi durdurduğu ana kadar olan andır.

Bir algoritmanın zaman karmaşıklığı üç kategoriye ayrılabilir−

Worst-case complexity - Belirli bir girdi için bir algoritmanın gerektirdiği zaman miktarı maximum.
Average-case complexity - Belirli bir girdi için bir algoritmanın gerektirdiği zaman miktarı average.
Best-case complexity - Belirli bir girdi için bir algoritmanın gerektirdiği zaman miktarı minimum.

Asimptotik Analiz

Bir algoritmanın karmaşıklığı veya verimliliği, istenen çıktıyı elde etmek için algoritma tarafından yürütülen adımların sayısıdır. Asimptotik analiz, teorik analizinde bir algoritmanın karmaşıklığını hesaplamak için yapılır. Asimptotik analizde, algoritmanın karmaşıklık fonksiyonunu hesaplamak için büyük uzunlukta girdi kullanılır.

Note - Asymptoticbir çizginin bir eğriyi karşılama eğiliminde olduğu, ancak kesişmediği bir durumdur. Burada çizgi ve eğri birbirine asimptotiktir.

Asimptotik gösterim, hızda yüksek sınırlar ve düşük sınırlar kullanan bir algoritma için mümkün olan en hızlı ve en yavaş yürütme süresini tanımlamanın en kolay yoludur. Bunun için aşağıdaki gösterimleri kullanıyoruz -

Büyük O gösterimi
Omega notasyonu
Teta gösterimi

Büyük O gösterimi

Matematikte, Big O notasyonu, fonksiyonların asimptotik özelliklerini temsil etmek için kullanılır. Basit ve doğru bir yöntemde büyük girdiler için bir işlevin davranışını temsil eder. Bir algoritmanın yürütme süresinin üst sınırını temsil eden bir yöntemdir. Algoritmanın yürütülmesini tamamlaması için alabileceği en uzun süreyi temsil eder. Fonksiyon -

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

pozitif sabitler varsa c ve n₀ öyle ki f(n) ≤ c * g(n) hepsi için n nerede n ≥ n₀.

Omega notasyonu

Omega gösterimi, bir algoritmanın yürütme süresinin alt sınırını temsil eden bir yöntemdir. Fonksiyon -

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

pozitif sabitler varsa c ve n₀ öyle ki f(n) ≥ c * g(n) hepsi için n nerede n ≥ n₀.

Theta Notasyonu

Teta gösterimi, bir algoritmanın yürütme süresinin hem alt sınırını hem de üst sınırını temsil eden bir yöntemdir. Fonksiyon -

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

pozitif sabitler varsa c₁, c₂, ve n₀ öyle ki c1 * g (n) ≤ f (n) ≤ c2 * g (n) hepsi için n nerede n ≥ n₀.

Bir Algoritmanın Hızlandırılması

Paralel bir algoritmanın performansı, hesaplanarak belirlenir. speedup. Hızlandırma, belirli bir problem için bilinen en hızlı sıralı algoritmanın en kötü durum yürütme süresinin paralel algoritmanın en kötü durum yürütme süresine oranı olarak tanımlanır.

speedup =

Özel bir problem için bilinen en hızlı sıralı en kötü durumda uygulama süresi / paralel algoritma En kötü durum yürütülmesi sırasında

Kullanılan İşlemci Sayısı

Paralel bir algoritmanın verimliliğini analiz etmede kullanılan işlemci sayısı önemli bir faktördür. Bilgisayarları satın alma, bakım ve çalıştırma maliyetleri hesaplanır. Bir problemi çözmek için bir algoritma tarafından kullanılan işlemci sayısı ne kadar fazlaysa, elde edilen sonuç o kadar maliyetli olur.