next up previous contents
Next: Obliczenia równoległe Up: calosc Previous: Spis rzeczy   Spis rzeczy

Wstęp

Większość algorytmów będących przedmiotem badań oraz używanych w obecnych programach to algorytmy sekwencyjne. Można to wytłumaczyć tym, że ogromna część komputerów będących obecnie w użyciu to maszyny jednoprocesorowe. Chociaż nowoczesne procesory stają się coraz szybsze, to jednak faktycznie potrafią one wykonywać w danej chwili kod tylko jednego programu. Pomimo tego, że dysponujemy systemami operacyjnymi umożliwiającymi wykonywanie jednocześnie wielu zadań, pracują one na zasadzie podzielenia czasu pracy procesora pomiędzy te programy. Faktyczna wieloprogramowość pozostaje ciągle w wielu przypadkach trudna do osiągnięcia. Problemem stają się także kwestie techniczne. O ile osiągalne jest obecnie zbudowanie komputera złożonego nawet z kilkudziesięciu czy większej liczby procesorów, o tyle uczynienie tego tak, aby łatwe było wykorzystanie całej mocy tak powstałej maszyny jest już trudne. Najczęściej projektanci posiłkują się wtedy odpowiednim językiem programowania oraz zrzucają na ramiona programisty ciężar realizacji synchronizacji procesorów i optymalizacji komunikacji między nimi.

Zwiększanie liczby procesorów staje się powoli koniecznością. Potrzeba wykonywania obliczeń z większą prędkością czy dokładnością towarzyszy komputerom od zawsze. Wydaje się, że przy obecnym poziomie techniki procesory zaczynają zbliżać się do granicy możliwości fizycznych rozwiązań stosowanych do ich produkcji. Ta sama technika spowodowała jednak, że koszty zbudowania komputerów wieloprocesorowych spadły znacząco oraz nadal spadają. Nie należy się więc dziwić, że już od dawna były rozwijane algorytmy do równoległych obliczeń.

Celem niniejszej pracy było stworzenie emulatora, który pozwalałby w prosty sposób zapisywać algorytmy równoległe oraz wykonywać je używając do tego celu standardowych komputerów osobistych połączonych siecią. W tym celu konieczne stało się również opracowanie odpowiedniego języka programowania oraz jego kompilatora.

Jednym z najprostszych jak i najczęściej używanych modeli do konstrukcji i analizy algorytmów równoległych jest maszyna typu PRAM. W rozdziale 2.1 przedstawiam opis budowy takiej maszyny wraz z przykładem realizacji sprzętowej jej pewnej wersji. Dodatkowo omawiam tam także dwa przykłady języków programowania dla takich maszyn.

W rozdziale 2.2 przedstawiam przykład innego podejścia do budowy komputerów równoległych -- system klastrowy zbudowany na Uniwersytecie w Berkeley. Różni się on w zasadniczy sposób od maszyny typu PRAM, jednak na jego podstawie można zbudować system analogiczny do PRAM, ponieważ udostępnia on większość potrzebnych do tego celu mechanizmów.

W dalszej części pracy przedstawiam przyjęty przeze mnie do realizacji język programowania. W rozdziale 3 opisuję składnię oraz poszczególne konstrukcje języka, jak również kilka zapisanych w nim algorytmów (dwa bardziej skomplikowane programy są zamieszczone w dodatkach B i C). Gramatyka bezkontekstowa języka jest podana w dodatku A.

W rozdziale 4 przedstawiam projekt implementacji maszyny PRAM w sieci lokalnej, a w dodatkach D i E -- sposób korzystania ze stworzonego systemu.

Rozdział 5 zawiera wyniki testów systemu. Przeprowadziłem je używając do tego celu różnych algorytmów. Testy miały na celu ukazanie zalet i słabości skonstruowanego przeze mnie systemu oraz wskazanie elementów, na które należy zwrócić uwagę przy zapisie programów, które miałyby z niego korzystać.

Rozdział 6 zawiera podsumowanie pracy.


next up previous contents
Next: Obliczenia równoległe Up: calosc Previous: Spis rzeczy   Spis rzeczy
Łukasz Maśko
2000-04-17