Złożoność asynchronicznych sieci logicznych

Wstęp

Synchroniczna bramka logiczna generuje wartość wynikową w chwili, gdy otrzyma wszystkie wartości wejściowe. Dlatego czas działania sieci zbudowanych z takich bramek nie zależy od aktualnych wartości danych wejściowych lecz jest stały, równy długości najdłuższej ścieżki obliczeń, czyli głębokości. Stąd starania, aby sieci synchroniczne miały jak najmniejszą głębokość.

W sieciach asynchronicznych bramki generują rezultat w momencie, gdy na podstawie już poznanych wartości wejściowych mogą jednoznacznie taki rezultat określić. Dla takich sieci wskazana jest więc analiza oczekiwanego czasu działania sieci, przeprowadzona dla określonej klasy rozkładów prawdopodobieństwa danych wejściowych. W pracy zajmujemy się taką analizą. Wprowadzamy również podział rozkładów prawdopodobieństwa na odpowiednie klasy, które wykorzystujemy w rozważaniach na temat złożoności czasowej sieci asynchronicznych.

W pracy prezentujemy rezultaty dotyczące złożoności sieci asynchronicznych uzyskane wcześniej przez innych autorów. Przedstawiamy podstawowe funkcje logiczne takie jak OR, AND, PARITY, MAJORITY, THRESHOLD i omawiamy ich złożoność w średnim przypadku. Oprócz tego zamieszczamy wyniki dla równoległego problemu sum prefiksowych i pokazujemy ich zastosowanie do obliczania sumy dwóch liczb.

Na koniec prowadzimy rozważania na temat czasu oczekiwanego dla sieci sortujących zbudowanych z asynchronicznych komparatorów. Koncentrujemy się tutaj na danych wejściowych o rozkładzie jednorodnym. Szczególną uwagę poświęcamy przy tym sieciom scalającym Odd-Even i bitonicznym.

Pełny tekst pracy.