Paralel Algoritma - Yapı
Herhangi bir algoritmayı doğru bir şekilde uygulamak için, uygun bir veri yapısı seçmeniz çok önemlidir. Bunun nedeni, bir veri yapısı üzerinde gerçekleştirilen belirli bir işlemin, başka bir veri yapısı üzerinde gerçekleştirilen aynı işleme kıyasla daha fazla zaman alabilmesidir.
Example- Bir dizi kullanarak bir kümedeki i'nci öğeye erişmek sabit bir süre alabilir, ancak bağlantılı bir liste kullanarak aynı işlemi gerçekleştirmek için gereken süre bir polinom olabilir.
Bu nedenle, bir veri yapısının seçimi, yapılacak işlemlerin mimarisi ve türü dikkate alınarak yapılmalıdır.
Aşağıdaki veri yapıları genellikle paralel programlamada kullanılır -
- Bağlantılı liste
- Arrays
- Hypercube Ağı
Bağlantılı liste
Bağlantılı bir liste, işaretçilerle bağlanan sıfır veya daha fazla düğüme sahip bir veri yapısıdır. Düğümler ardışık bellek konumlarını işgal edebilir veya işgal etmeyebilir. Her düğümün iki veya üç bölümü vardır - birdata part verileri depolayan ve diğer ikisi link fieldsönceki veya sonraki düğümün adresini saklayan. İlk düğümün adresi adı verilen harici bir işaretçide saklanırhead. Olarak bilinen son düğümtail, genellikle herhangi bir adres içermez.
Üç tür bağlantılı liste vardır -
- Tek Bağlantılı Liste
- Çift Bağlantılı Liste
- Dairesel Bağlantılı Liste
Tek Bağlantılı Liste
Tekil bağlantılı bir listenin bir düğümü, verileri ve sonraki düğümün adresini içerir. Adlı harici bir işaretçihead ilk düğümün adresini depolar.
Çift Bağlantılı Liste
Çift bağlantılı listenin bir düğümü, verileri ve hem önceki hem de sonraki düğümün adresini içerir. Adlı harici bir işaretçihead ilk düğümün adresini ve çağrılan harici işaretçiyi depolar tail son düğümün adresini depolar.
Dairesel Bağlantılı Liste
Döngüsel bağlantılı bir liste, son düğümün ilk düğümün adresini kaydetmesi dışında tek bağlı listeye çok benzer.
Diziler
Dizi, benzer veri türlerini depolayabileceğimiz bir veri yapısıdır. Tek boyutlu veya çok boyutlu olabilir. Diziler statik veya dinamik olarak oluşturulabilir.
İçinde statically declared arrays, Dizilerin boyutu ve boyutu derleme sırasında bilinmektedir.
İçinde dynamically declared arrays, Dizinin boyutu ve boyutu çalışma zamanında bilinir.
Paylaşılan bellek programlaması için diziler ortak bir bellek olarak kullanılabilir ve paralel veri programlama için alt dizilere bölümlenerek kullanılabilirler.
Hypercube Ağı
Hypercube mimarisi, her görevin diğer görevlerle iletişim kurması gereken paralel algoritmalar için yararlıdır. Hypercube topolojisi, halka ve ağ gibi diğer topolojileri kolayca yerleştirebilir. Aynı zamanda n-küp olarak da bilinir.nboyutların sayısıdır. Bir hiperküp, özyinelemeli olarak inşa edilebilir.