Algorytm równoległy - struktura
Aby poprawnie zastosować dowolny algorytm, bardzo ważne jest wybranie odpowiedniej struktury danych. Dzieje się tak, ponieważ określona operacja wykonywana na strukturze danych może zająć więcej czasu w porównaniu z tą samą operacją wykonywaną na innej strukturze danych.
Example- Aby uzyskać dostęp do i- tego elementu zestawu przy użyciu tablicy, może to zająć stały czas, ale przy użyciu połączonej listy czas wymagany do wykonania tej samej operacji może stać się wielomianem.
Dlatego wybór struktury danych musi być dokonany z uwzględnieniem architektury i rodzaju operacji do wykonania.
Następujące struktury danych są powszechnie używane w programowaniu równoległym -
- Połączona lista
- Arrays
- Sieć Hypercube
Połączona lista
Lista połączona to struktura danych zawierająca zero lub więcej węzłów połączonych wskaźnikami. Węzły mogą, ale nie muszą, zajmować kolejne lokalizacje pamięci. Każdy węzeł ma dwie lub trzy części - jednądata part który przechowuje dane, a pozostałe dwa są link fieldsktóre przechowują adres poprzedniego lub następnego węzła. Adres pierwszego węzła jest przechowywany w zewnętrznym wskaźniku o nazwiehead. Ostatni węzeł, znany jakotail, generalnie nie zawiera żadnego adresu.
Istnieją trzy typy połączonych list -
- Lista pojedynczo połączona
- Lista podwójnie połączona
- Lista połączona cyklicznie
Lista pojedynczo połączona
Węzeł pojedynczo połączonej listy zawiera dane i adres następnego węzła. Zewnętrzny wskaźnik o nazwiehead przechowuje adres pierwszego węzła.
Lista podwójnie połączona
Węzeł podwójnie połączonej listy zawiera dane i adres zarówno poprzedniego, jak i następnego węzła. Zewnętrzny wskaźnik o nazwiehead przechowuje adres pierwszego węzła i wywoływany wskaźnik zewnętrzny tail przechowuje adres ostatniego węzła.
Lista połączona cyklicznie
Lista połączona cyklicznie jest bardzo podobna do listy pojedynczo połączonej, z wyjątkiem faktu, że ostatni węzeł zapisał adres pierwszego węzła.
Tablice
Tablica to struktura danych, w której możemy przechowywać podobne typy danych. Może być jednowymiarowy lub wielowymiarowy. Tablice można tworzyć statycznie lub dynamicznie.
W statically declared arrays, wymiary i rozmiar tablic są znane w momencie kompilacji.
W dynamically declared arrays, wymiary i rozmiar tablicy są znane w czasie wykonywania.
Do programowania w pamięci współdzielonej tablice mogą być używane jako pamięć wspólna, a do programowania równoległego danych można ich używać poprzez partycjonowanie na pod-tablice.
Sieć Hypercube
Architektura Hypercube jest pomocna w przypadku tych równoległych algorytmów, w których każde zadanie musi komunikować się z innymi zadaniami. Topologia Hypercube może z łatwością osadzać inne topologie, takie jak pierścień i siatka. Znany jest również jako n-kostki, gdziento liczba wymiarów. Hipersześcian można skonstruować rekurencyjnie.
