Komputery i sieci - podstawy

Równoległy system przetwarzania danych (ang. parallel processing) pokazany jest na rys. 1. Pomysł, by w tym samym czasie realizować poszczególne fragmenty algorytmu, jest naturalną drogą pozwalającą przyśpieszyć system cyfrowy. Nie każdy jednak algorytm daje się rozbić na takie niezależne części, by mógł być realizowany równolegle. Z drugiej strony, jeśli mamy n procesorów, nie musimy na wszystkich realizować tego samego zadania.

Rys. 1. Przetwarzanie równoległe danych; P# k oznacza procesor o numerze k

Innym sposobem przyśpieszenia przetwarzania jest tzw. przetwarzania potokowe (ang. pipelining). W przetwarzaniu potokowym n procesorów realizuje fragmenty algorytmu, tak jak dzieje się to na taśmie produkcyjnej, przekazując „półprodukt” do następnego procesora po ustalonym czasie T. Schemat blokowy układu przetwarzania potokowego pokazany jest na rys.2.

Rys. 2. Przetwarzanie potokowe

Układy systoliczne lub - jak czasem mówimy - sieci systoliczne lub tablice systoliczne (ang. systolic array) łączą dwie wyżej opisane koncepcje przyśpieszania realizacji algorytmu: przetwarzanie równoległe i przetwarzanie potokowe i mają następujące cechy:

• regularność struktury
• modularność
• lokalność połączeń
• przetwarzanie równoległe i potokowe

Sieci systoliczne służą do realizacji różnych ważnych algorytmów np.:

• sortowania
• obliczania iloczynu skalarnego wektorów,
• mnożenia wektora przez macierz
• mnożenia macierzy
• obliczania DFT (w gruncie rzeczy jest to też mnożenie wektora przez macierz)
• realizacji metody najmniejszych kwadratów

 

a)

b)

Rys. 3. Typowe struktury sieci systolicznych a) struktura jednowymiarowa b) struktura dwuwymiarowa

Omówimy dokładniej sieci systoliczne sortujące lub - jak mówimy krócej - układy sortujące. Układy sortujące są ważnym z praktycznego punktu widzenia układem służą np. do realizacji filtrów medianowych i kwantylowych w cyfrowym przetwarzaniu sygnałów.

Warto w tym miejscu przypomnieć, co to jest sortowanie. Sortowanie ciągu liczbowego a₁, a₂, ...a_n to jego porządkowanie. Formalnie rzecz biorąc sortowanie ciągu sprowadza się do znalezienia takiej permutacji π:<1, n>→<1, n>, by spełnione były nierówności a_π(1) ≤ a_π(2) ≤ ... ≤ a_π(n).

Algorytmów sortowania jest dużo, nie wszystkie jednak dobrze nadają się do - jak mówimy w żargonie - „systolizacji”. W sieciach systolicznych znajdują zastosowanie trzy algorytmy sortowania:

• algorytm bubblesort – sortowanie bąbelkowe
• algorytm modified bubblesort – zmodyfikowane sortowanie bąbelkowe
• algorytm insertion sort – sortowanie przez wstawianie

Na rys. 4. pokazana jest komórka podstawowa PC (ang. processing cell) sortującej sieci systolicznej, a na rys. 5. pokazana jest systoliczna sieć sortująca oparta na wykorzystaniu algorytmu modified bublesort.

Rys. 4. Układ komórki podstawowej PC oraz jej uproszczony symbol (po prawej)

 

Rys. 5. Sieć systoliczna sortująca (pięcioelementowy ciąg skończony liczb w kodzie NKB) oparta na algorytmie modified bubblesort; na wejście podawane są słowa o długości w

Rys. 6. Sieć systoliczna sortująca (ciąg skończony o długości n) oparta na algorytmie insertion sort; na wejście podawane są słowa o długości w; liczby zapisywane są w kodzie NKB