Algorytm równoległy - wprowadzenie

Na algorithmto sekwencja kroków, które pobierają dane wejściowe od użytkownika i po wykonaniu pewnych obliczeń generują dane wyjściowe. ZAparallel algorithm to algorytm, który może wykonywać kilka instrukcji jednocześnie na różnych urządzeniach przetwarzających, a następnie łączyć wszystkie poszczególne wyjścia w celu uzyskania końcowego wyniku.

Przetwarzanie współbieżne

Łatwa dostępność komputerów wraz z rozwojem Internetu zmieniła sposób, w jaki przechowujemy i przetwarzamy dane. Żyjemy w czasach, w których danych jest pod dostatkiem. Każdego dnia mamy do czynienia z ogromnymi ilościami danych, które wymagają skomplikowanych obliczeń i to również w krótkim czasie. Czasami musimy pobrać dane z podobnych lub powiązanych ze sobą zdarzeń, które występują jednocześnie. Właśnie tego potrzebujemyconcurrent processing które mogą podzielić złożone zadanie i przetworzyć je w wielu systemach, aby szybko uzyskać wynik.

Jednoczesne przetwarzanie jest niezbędne, gdy zadanie obejmuje przetwarzanie ogromnej ilości złożonych danych. Przykłady obejmują - dostęp do dużych baz danych, testowanie samolotów, obliczenia astronomiczne, fizykę atomową i jądrową, analizę biomedyczną, planowanie gospodarcze, przetwarzanie obrazu, robotykę, prognozowanie pogody, usługi internetowe itp.

Co to jest równoległość?

Parallelismto proces jednoczesnego przetwarzania kilku zestawów instrukcji. Zmniejsza całkowity czas obliczeniowy. Równoległość można zaimplementować za pomocąparallel computers,tj. komputer z wieloma procesorami. Komputery równoległe wymagają równoległego algorytmu, języków programowania, kompilatorów i systemu operacyjnego obsługującego wielozadaniowość.

W tym samouczku omówimy tylko parallel algorithms. Zanim przejdziemy dalej, omówmy najpierw algorytmy i ich typy.

Co to jest algorytm?

Na algorithmto sekwencja instrukcji zastosowanych w celu rozwiązania problemu. Projektując algorytm należy wziąć pod uwagę architekturę komputera, na którym algorytm będzie wykonywany. Jeśli chodzi o architekturę, istnieją dwa typy komputerów -

• Komputer sekwencyjny
• Komputer równoległy

W zależności od architektury komputerów mamy dwa rodzaje algorytmów -

• Sequential Algorithm - Algorytm, w którym niektóre kolejne kroki instrukcji są wykonywane w porządku chronologicznym w celu rozwiązania problemu.

• Parallel Algorithm- Problem jest podzielony na podproblemy i są wykonywane równolegle, aby uzyskać indywidualne wyniki. Później te poszczególne wyjścia są łączone razem, aby uzyskać ostateczną pożądaną moc.

Nie jest łatwo podzielić duży problem sub-problems. Podproblemy mogą być zależne od danych. Dlatego procesory muszą się ze sobą komunikować, aby rozwiązać problem.

Stwierdzono, że czas potrzebny procesorom na komunikowanie się ze sobą jest dłuższy niż rzeczywisty czas przetwarzania. Dlatego projektując algorytm równoległy, należy wziąć pod uwagę właściwe wykorzystanie procesora, aby uzyskać wydajny algorytm.

Aby prawidłowo zaprojektować algorytm, musimy mieć jasne pojęcie o podstawach model of computation w komputerze równoległym.

Model obliczeniowy

Zarówno komputery sekwencyjne, jak i równoległe działają na zestawie (strumieniu) instrukcji zwanych algorytmami. Ten zestaw instrukcji (algorytm) instruuje komputer, co ma zrobić na każdym kroku.

W zależności od strumienia instrukcji i strumienia danych, komputery można podzielić na cztery kategorie -

• Pojedynczy strumień instrukcji, komputery z pojedynczym strumieniem danych (SISD)
• Pojedynczy strumień instrukcji, komputery z wieloma strumieniami danych (SIMD)
• Wiele strumieni instrukcji, komputery z pojedynczym strumieniem danych (MISD)
• Wiele strumieni instrukcji, komputery z wieloma strumieniami danych (MIMD)

Komputery SISD

Komputery SISD zawierają one control unit, one processing unit, i one memory unit.

W tego typu komputerach procesor otrzymuje pojedynczy strumień instrukcji z jednostki sterującej i działa na pojedynczym strumieniu danych z jednostki pamięci. Podczas obliczeń na każdym kroku procesor otrzymuje jedną instrukcję z jednostki sterującej i operuje na pojedynczych danych odebranych z jednostki pamięci.

Komputery SIMD

Komputery SIMD zawierają one control unit, multiple processing units, i shared memory or interconnection network.

Tutaj jedna jednostka sterująca wysyła instrukcje do wszystkich jednostek przetwarzania. Podczas obliczeń na każdym etapie wszystkie procesory otrzymują pojedynczy zestaw instrukcji z jednostki sterującej i działają na innym zestawie danych z jednostki pamięci.

Każda z jednostek przetwarzania ma własną lokalną jednostkę pamięci do przechowywania zarówno danych, jak i instrukcji. W komputerach SIMD procesory muszą komunikować się między sobą. Odbywa się to przezshared memory lub przez interconnection network.

Podczas gdy niektóre procesory wykonują zestaw instrukcji, pozostałe procesory czekają na następny zestaw instrukcji. Instrukcje z jednostki sterującej decydują, który procesor będzieactive (wykonaj instrukcje) lub inactive (poczekaj na kolejną instrukcję).

Komputery MISD

Jak sama nazwa wskazuje, komputery MISD zawierają multiple control units, multiple processing units, i one common memory unit.

Tutaj każdy procesor ma własną jednostkę sterującą i mają wspólną jednostkę pamięci. Wszystkie procesory otrzymują instrukcje indywidualnie z własnej jednostki sterującej i działają na jednym strumieniu danych, zgodnie z instrukcjami otrzymanymi od odpowiednich jednostek sterujących. Ten procesor działa jednocześnie.

Komputery MIMD

Komputery MIMD mają multiple control units, multiple processing units, i a shared memory lub interconnection network.

Tutaj każdy procesor ma swoją własną jednostkę sterującą, lokalną jednostkę pamięci oraz jednostkę arytmetyczno-logiczną. Otrzymują różne zestawy instrukcji od odpowiednich jednostek sterujących i operują na różnych zestawach danych.

Uwaga

• Komputer MIMD, który współużytkuje wspólną pamięć, jest znany jako multiprocessors, podczas gdy te, które korzystają z sieci połączeń, są znane jako multicomputers.

• W oparciu o fizyczną odległość procesorów, multikomputery są dwojakiego rodzaju -

  • Multicomputer - Gdy wszystkie procesory są bardzo blisko siebie (np. W tym samym pomieszczeniu).

  • Distributed system - Gdy wszystkie procesory są daleko od siebie (np. - w różnych miastach)