Konrad Kukulski, 163930 Wrocław, 15.06.2010

Elżbieta Tchorowska, 171067

Architektura komputerów 2

Projekt

Prowadzący: dr Piotr Patronik

Temat: Sieci sortujące niskiej złożoności O(nlogn)

Wstęp

Celem projektu było zrozumienie działania, zbadanie i implementacja w języku wyższego rzędu, sieci sortującej złożoności O(n*logn) autorstwa Ajtai'a, Komlósa i Szemerédi'ego. Głównym materiałem był artykuł napisany przez nich, udostępniony przez prowadzącego zajęcia.

Artykuł

Ponieważ nie wszyscy członkowie grupy biegle czytają w języku angielskim, a tak właśnie był napisany owy artykuł, pierwszym krokiem było przetłumaczenie go na język polski. Przy okazji była szansa lepszego zrozumienia problemu. W końcu, żeby coś przetłumaczyć z sensem, trzeba to zrozumieć. W załączeniu przedstawiono przetłumaczony artykuł na język polski. Niestety, ze zrozumieniem, co autorzy mieli na myśli było ciężej. Opierając się jeszcze na innych materiałach, ze stron WWW, zaczęliśmy próbować rysować odwzorowanie na ekspanderach, o których była mowa w artykule.

Ekspandery

Odwzorowanie sortowania na ekspanderach okazało się wcale nie takie banalne, jak się wydawało. Cała koncepcja była niby prosta, jednakże nie potrafiliśmy poradzić sobie z problemem zamiany kluczy węzłów między sobą, w poszczególnych rozgałęzieniach drzewa. Autorzy wyraźnie mówili o podziale ciągu na trójki, co próbowaliśmy zrobić. Niestety, nie zwróciliśmy uwagi o notce dotyczącej błędów. Uznaliśmy, że za błąd autorzy przyjmują złe ustawienie liczb po przeprowadzonym sortowaniu. Okazało się w praktyce, że jednak przyjmują za błąd złe ustawienie przed sortowaniem. Inaczej, sortowanie nie działa na dla każdej permutacji zbioru, tylko dla poszczególnych, wybranych. A przynajmniej nie przy złożoności n*logn.

Podział

Próbowaliśmy również ugryźć to ze strony tak zwanego „połówkowania” o którym mówili autorzy. Chociaż połówkowanie jest bardzo podobne do znanego quicksorta, dalej niestety nie wychodziły żadne ciekawe rezultaty, a liczby jak nie chciały być sortowane, tak nie chciały. Cały algorytm w teorii wydawał się bardzo prosty i czytelny, w praktyce miał tyle wyjątków, stanów błędów, odgałęzień i niedopracowań, że aż strach było myśleć o nim więcej. Nie poddając się, zabraliśmy się za rysowanie sieci na liniach i komparatorach, próbując odtworzyć tok rozumowania autorów artykułu.

Sieć sortująca

Z początku, błądząc po omacku, próbowaliśmy stworzyć sieć, która przypominałaby chociaż cokolwiek zawierającego podział, o którym mówią autorzy. Po wielu godzinach bezowocnej pracy, dużej ilości napojów procentowych, o trzeciej w nocy, udało się stworzyć coś, co mogło nosić miano ZIGZAG'a. Mianowicie - sortowało, był podział na trójki, jak mówił algorytm, i cała sieć składała się z dwóch powtarzających się kroków, w sekwencji ZIG ZAG ZIG… Pozostało jedynie sprawdzić, jaka jest złożoność owej sieci, ilość komparatorów i inne tego typu rzeczy, które mogły by całkowicie upewnić nas, że albo wymyśliliśmy coś genialnego, albo brniemy dalej w nieznane.

Autorzy w artykule opisują jeden krok jako ZIG ZAG, bądź ZIG ZAG ZIG. Co wychodzi w sumie na to samo, jakoże ostatni ZIG jest niepotrzebny i nie robi nic w większości przypadków. Istnieje jednak kilka z nich, gdzie przy ostatnim kroku, ostatni ZIG jest potrzebny, by dokończyć sortowanie. To jednak wyszło dopiero po implementacji algorytmu w C++.

Cały wygląd sieci był zaskakująco prosty. Przedstawia sortowanie trójkami, gdzie krok ZIG zaczyna sortowanie od linii 1, 4, 7…, a krok ZAG zaczyna od 2, 5, 8… Podział na trójki istnieje. Nawet tłumaczenie ekspanderów i poziomów parzystych i nieparzystych ma sens, gdy przedstawioną sieć rozrysuje się w odpowiedni sposób. Faktycznie, patrząc przez palce, można zauważyć tam sortowanie trójek węzłów w ekspanderze.

Po implementacji w C++ (załączony program na płycie) odkryliśmy, że aby przesortować n elementów, faktycznie potrzebne jest logn kroków, jeśli za krok przyjmujemy ZIG ZAG ZIG. Przy rozroście sieci w dół w zależności od liczby n, faktycznie złożoność sieci wynosi n*logn. Choć osobiście uważamy to, za bardzo naciąganą teorię.

Cały algorytm miał pracować w czasie równoległym, czyli tam, gdzie jest to możliwe, niezależne porównania, miały wykonywać się w tym samym czasie. Zakładając tak, sieć potrzebuje n/2 porównań, co również zgadza się z założeniami sieci z artykułu. I tu niestety kończy się piękno owej sieci.

Liczba komparatorów jest niesamowicie duża, niewiele mniejsza od bąbelkowego dla małej ilości n. Potrzebuje około 3*n*logn. Około, gdyż wartość ta jest różna w zależności od wyniku modulo 3 liczby n.

Przeprowadziliśmy teoretyczne sortowania na kartce dla elementów do 32.

Bardziej czytelny wygląd sieci przedstawia ostatni szkic. Pozostałe przedstawiają teoretyczne sortowania, obliczenia i szkice sieci dla mniejszej ilości elementów.

Sieć sortująca stworzona przypadkiem 1

Pracując nad siecią ZIG ZAG, próbując ją jak najbardziej ulepszyć i zrozumieć, przypadkiem wpadliśmy na pomysł innej sieci, która również będzie wykorzystywała sortowanie trójek. Cały algorytm polegał na podziale elementów po trzy i porównanie ze sobą. Linie 1,2,3 - 4,5,6 - 7,8,9 itd. W efekcie otrzymujemy ileś zbiorów posortowanych trójek. Wiemy na pewno, że wśród pierwszych elementów tych zbiorów, znajduje się liczba największa, a wśród trzecich - najmniejsza.

Żeby ją znaleźć - znowu przeprowadzamy sortowanie trójkami - tym razem elementów największych z poprzedniego sortowania - oraz elementów najmniejszych. Powtarzając krok do skutku, aż nie będzie już czego porównywać - otrzymamy największy element na dole, a najmniejszy na górze.

Całość ma podobne założenia do sieci bąbelkowej. Złożoność jest identyczna. Czas przeznaczony na wykonanie porównań, tylko dwa razy mniejszy. Niestety, sieć, mimo iż stabilna, jest bardzo rozbudowana i bardzo rozrasta się w prawo.

W przeciwieństwie do ZIG ZAG'a sortuje zawsze. Potrzebne jej dopracowanie i może dało by radę ograniczyć złożoność do czegoś mniejszego. Na to niestety chwilowo nie było czasu.

W załączeniu ogólnikowy wygląd sieci, obliczenia oraz plakat ścienny z siecią, przedstawieniem ekspanderów, wykresów.

Sieć sortująca stworzona przypadkiem 2

Na drugą sieć sortującą wpadliśmy, gdy zwiedzając google, wikipedie i inne takie natknęliśmy się na artykuł dotyczący sieci o optymalnej ilości komparatorów. Nie było niestety żadnego mądrego wzorku, ale pisało, że dla 8 elementów zawiera 19 komparatorów. Natchnieni siecią Batchera i tą informacją postanowiliśmy ją stworzyć.

Obecnie sieć jest dopracowana tylko dla ilości elementów, które są potęgą liczby 2. Obecne pomiary i doświadczenia są bardzo obiecujące. Cała sieć składa się z dwóch etapów. W pierwszym porównujemy ze sobą elementy na wejściach parzystych i elementy na wejściach nieparzystych, według algorytmu wymyślonego przez nas. W tym momencie otrzymujemy dwa podzbiory, które są posortowane między sobą i naprzemiennie. Pozostaje jedynie przesortować je między sobą i powinniśmy otrzymać posortowany ciąg liczb.

Tak jak pierwszy etap zawiera złożoność O(logn), tak drugi niestety jest bardziej zbliżony do kwadratu, co próbujemy do chwili obecnej zmienić. Nie interesuje nas sortowanie czasu równoległego, tylko sieć, dla której każde porównanie wykonuje się w jednej jednostce czasu.

Planujemy dopracować obie sieci.

W załączeniu poglądowy schemat sieci i obliczenia.

Płyta CD z ZIG ZAG'iem

---