Adam Mazur


Bottleneck Analysis of a Gigabit Network Interface Card

  1. Co weryfikujemy

    NIC (network interface card) to popularnie zwana sieciówka.
    To co rozróżnia karty sieciowe to rodzaj sieci jaki potrafia obsługiwac, jak Ethernet, Token Ring, czy własnie Gigabit którym my sie zajmiemy.

    Myrinet - gigabitowy system sieci, o bardzo małym narzucie danych kontorlnych, przez co jest dużo wydajniejszy od popularnych standardów jak Ethernet, ma wiekszą przepustowość, mniej kolizji na kablu i mniej angażuje procesor host'a. Pierwsza generacja Myrinet'ów zapewniała przepustowość rzędu 512 MBit/s w obie strony, w tej chwili ta wartość wzrosła do 2 GBit/s. Co ważne rzeczywiście osiągana przepustowość jest bardzo bliska teoretycznej maksymalnej przepustowości sieci.

    Berkeley-VIA to implementacja Virtual Interface Architecture, swego rodzaju nakładki na Myrinet.
    Udostępnia bezpośredni dostęp do NIC omijając nawet jądro (w którym identyczne operacje przechodzą przez szereg filtrów, testów i tym podobnych nakładek)
    - stąd zakłada się że Berkeley-VIA udostępnia niemal fizyczną przepustowość łączy.

    testy jakie przeprowadzono, wykazały że:

    Pytanie brzmi: dlaczego mimo że Berkley-VIA ma taki mały koszt ogólny komunikacji, nadal nie jest w stanie zapewnić najlepszej z możliwych przepustowości?

    Zdecydowano sie zweryfikować Myrinet w celu znalezienia wąskiego gardła. Myrinet NIC posiada trzy kanały DMA oraz własną pamięc i procesor, a dodatkowo interakcja Myrinet'u z host'em jest bardzo złożona - więc weryfikacja do prostych nie należy. Po kolei przedstawię jak:

    1. najpierw zbudowano diagramy przejść stanów aby wymodelować Myrinet
    2. potem przetłumaczono je na specyfikacje w Promeli
    3. na koniec wyprowadzono formuły weryfikacji, i zweryfikujemy je w SPIN'nie
  2. budowa Myrinet NIC


    Myrinet NIC zawiera:

  3. modelowanie

    Analizowano dwa oprogramowania sprzętowe:

    1. LCP - Lanai Control Program

      składa sie z czterech modułów: hostDma, lcpTx, lcpRx i main.
      Poszczególne diagramy przejść stanów wyglądają tak:

      [ hostDma ]

      odpowiedzialny jest za transfer danych po EBUS-LBUS DMA

      1. moduły lpcTx i lpcRx wywolując metody modułu hostDma, ustawiają go w stan HostDmaBusy
      2. kiedy zaś operacja zostanie zakończona moduł ten przechodzi w stan HostDmaIdle

      [ lcpTx ]odpowiedzialny jest za wysyłanie danych z SRAM do sieci

      1. gdy są jakieś dane do wysłania moduł ten przechodzi w stan LpcTxGotASend
      2. dalej, w celu sprowadzenia danych do pamięci podręcznej - woła metodę modułu hostDma przechodząc do stanu LpcTxHostDma
      3. po powrocie z metody stan zmienia się na LcpTxSendDma
        w tym stanie moduł inicializuje operacje send-DMA i czeka na jej zakończenie
      4. jeśli podczas tej operacji przyjdą jakieś dane z sieci - moduł lcpTx przechodzi w stan LcpTxInvokeRx z którego wróci do LcpTxSendDma dopiero po odebraniu wszystkich danych z sieci
      5. lcpTx wraca do stanu LcpTxIdle dopiero po zakończeniu operacji send-DMA

      [ lcpRx ]odpowiedzialny jest za odbieranie danych z sieci do SRAM
      1. początkowy stan to LcpRxReady: inicjuje on operacje receive-DMA z wyprzedzeniem, ponieważ ciężko powiedzieć kiedy przyjdą jakieś dane
      2. gdy Myrinet NIC otrzyma dane z sieci, stan modułu lcpRx zostaje zmieniony na LcpRxGotAReceive, po czym moduł ten uruchamia metode modułu hostDma zmieniając stan na LcpRxHostDma
      3. po zakończeniu metody modułu hostDma stan powraca do LcpRxReady i reinicjuje operacje receive-DMA

      [ main ]odpowiada za wołanie metod modułów lcpTx i lcpRx jeśli są dane odpowiednio do wysłania lub odebrania

      Moduły zostały wyspecyfikowane w Promeli jako osobne procesy.

      Wszystkie interakcje pomiedzy modułami sa wykonywane synchronicznie, przy czym te interakcje zaimplementowano jako po dwa kanały dla każdego procesu: jeden do przesyłania argumentu, a drugi dla zwracanej wartości.
      Zdarzenia sa również przesyłane jako argumenty lub wartości zwracane.

      Przykład:

      [ specyfikacja lcpTx w Promeli ]
      
      active proctype lcpTx()
      { int event;
      
      do
      :: (lt_state == LcpTxIdle) ->
      	Tolt?event;
      	if
      	:: (event == GotASend) ->
      		lt_statg = LcpTxGotASend;
      		Tohd!HostDmaRequest;
      		lt_state = LcpTxHostDma;
      		ret2txrx?event;
      		if
      		:: (event == HostDmaDone) ->
      			lt_state = LcpTxSendDma;
      			do
      			:: if
      				:: (send_int == 1) ->
      					lt_state = LcpTxIdle;
      					send_int = O;
      					goto endoflt
      				:: (recv_int == 1) ->
      					lt_state = lcpTxInvokeRx;
      					Tolr!ReceiveDone;
      					ret2tx?event;
      					if
      					:: (event == LcpRxDone) ->
      						lt_state = lcpTxSendDma
      					:: else -> skip
      					fi
      				:: else -> skip
      				fi
      			od
      		:: else -> skip
      		fi
      	:: else -> skip
      	fi;
      endoflt:
      	ret2lcp!0
      od }
      					

    2. MCP - Myrinet Control Program

      MCP wchodzi w skład Myrinet'u i oblsługuje komunikacje tradycyjnymi protokołami jak TCP czy UDP.

      Składa się z pięciu modułów:

      • hostSend - odpowiedzialny za transfer danych z pamięci głównej do SRAM'u
      • netSend - odpowiedzialny za transfer danych z SRAM'u do sieci
      • hostReceive - odpowiedzialny za transfer przysłanych danych z SRAM'u do pamięci głównej
      • netReceive - odpowiedzialny za odbiór danych z sieci do SRAM'u
      • main - odpowiedzialny za wołanie metod pozostałych modułów, w zależności od zdarzeń

      [ hostSend ]odpowiedzialny za transfer danych z pamięci głównej do SRAM'u

      1. stan początkowy to HostSendIdle
      2. po przyjściu danych do wysłania zmienia się modułowi stan na HostSendGotASend
        - wtedy też moduł sprawdza warunki:
        1. jeśli nie ma juz miejsca w SRAM'ie - stan przechodzi na HostSendFull i wraca do modułu main.
        2. jeśli EBUS-LBUS DMA jest zajęte przez moduł hostReceive - stan zmienia sie na HostSendDmaBusy i wraca do modułu main
        3. w pozostałych przypadkach moduł wchodzi w stan HostSendDma rozpoczynając operacje EBUS-LBUS DMA, i powracając do modułu main bez czekanie na zakończenie tej operacji
      3. w przypadu znalezienia się w stanie HostSendFull - dalsze przechodzenie pomiędzy stanami jest wznawiane kiedy moduł netSend wyśle wszystkie dane z SRAM'u
      4. w przypadku znalezienia się w stanie HostSendDmaBusy - dalsze przechodzienie pomiędzy stanami będzie kontynuowane po zakończeniu operacji EBUS-LBUS DMA wołanej przez moduł hostReceive
      5. moduł powraca ze stanu HostSendDma do stanu początkowego gdy zakończy się operacja EBUS-LBUS DMA

      [ netSend ]odpowiedzialny za transfer danych z SRAM'u do sieci

      1. stan początkowy to NetSendIdle
      2. jeśli moduł hostSend wprowadzi jakieś dane z pamięci głównej do SRAM'u, stan modułu netSend zostaje ustawiony jako NetSendBusy. W tym stanie inicjuje on operacje send-DMA i czeka na jej zakończenie, po czym wraca do stanu początkowego

      [ hostReceive ]odpowiedzialny za transfer przysłanych danych z SRAM'u do pamięci głównej

      1. stan początkowy to HostReceiveIdle
      2. jeśli istnieją dane w SRAM'ie które moduł netReceive sprowadził z sieci, stan modułu hostReceive zmienia się na HostReceiveGotAReceive
      3. potem, podobnie jak moduł hostSend, trzeba sprawdzic warunki: jeśli EBUS-LBUS DMA jest używane przez moduł hostSend, to stan zmienia sie na HostReceiveDmaBusy i moduł czeka aż EBUS-LBUS DMA nie zostanie zwolnione (a właściwie to zwraca sterowanie modułowi main)
      4. jeśli EBUS-LBUS DMA nie jest używane, to stan przechodzi na HostReceiveDma, moduł inicjuje operacje EBUS-LBUS DMA, po czym powraca do modułu main.
      5. stan powróci do stanu początkowego po wykonaniu operacji przez EBUS-LBUS DMA

      [ netReceive ]odpowiedzialny za odbiór danych z sieci do SRAM'u

      1. stan początkowy to NetReceiveDma
        (z analogicznych powodów jak w LCP stan LcpRxReady)
      2. gdy operacja receive-DMA sie zakończy, moduł ten przechodzi do stanu NetReceiveDmaDone, w którym sprawdza czy bufor w SRAM'ie jest dostępny dla ewentualnych kolejnych danych, i jeśli nie jest on jeszcze pełny to wraca to stanu początkowego
      3. jeśli bufor w stanie NetReceiveDmaDone był pełny, przechodzi do stanu NetReceiveFull i czeka aż moduł hostReceive wyśle dane będące w SRAM'ie

      Porównując LCP do MCP: podstawowa różnica to że w tym drugim każdy moduł ma wiele punktów wejścia. Oznacza to tylko tyle że podczas gdy w LCP wychodząc z stanu początkowego metoda kończyła działanie dopiero po dotarciu z powrotem do stanu początkowego, bez czekania na jakiekolwiek zdarzenia, o tyle w MCP sterowanie może zostać przerwane w niemal dowolnym stanie, oraz wznowione później w punkcie w którym ostatnio przerwało.

      Podobnie jak w LCP komunikacja pomiędzy modułami odbywa się za pomocą dwóch kanałów komunikacyjnych w Promeli. Zdarzenia są składowane w kanale nazwanym Events, a powołując się na jego zawartość moduł główny woła odpowiednie metody.

      Przykład:

      [ specyfikacja hostSend w Promeli ]
      
      active proctype hostSend()
      { int event;
      
      do
      :: (hs_state == HostSendIdle) ->
      	Tohs?event;
      	if
      	:: (event == GotASend) ->
      		if
      		:: (nempty(hs_buffer)) ->
      			hs_buffer?hs_data;
      			hs_state = HostSendGotASend;
      			if
      			:: (full(ns_buffer)) ->
      				hs_state = HostSendFull
      			:: (nfull(ns_buffer)) ->
      				if
      				:: (DmaInUse==1) ->
      					hs_state = HostSendDmaBusy
      				:: else ->
      					DmaInUse = 1;
      					hs_state = HostSendDma
      				fi
      			fi
      		:: (empty(hs_buffer)) -> skip
      		fi
      	:: else -> skip
      	fi;
      	Return!0
      
      :: (hs_state == HostSendFull) ->
      	Tohs?event;
      	if
      	:: (event == NetSendQueueNotFull) ->
      		hs_state = HostSendNotFull;
      		if
      		:: (DmaInUse == 1) ->
      			hs_state = HostSendDmaBusy
      		:: else ->
      			DmaInUse = 1;
      			hs_state = HostSendDma
      		fi
      	:: else -> skip
      	fi;
      	Return!0
      	
      :: (hs_state == HostSendDmaBusy) ->
      	Tohs?event;
      	if
      	:: (event == SendDmaFree) ->
      		hs_state = HostSendDma
      	:: else -> skip
      	fi;
      	Return!0
      
      :: (hs_state == HostSendDma) ->
      	Tohs?event;
      	if
      	:: (event == SendDmaDone) ->
      		DmaInUse = 0;
      		if
      		:: (hr_state == HostReceiveDmaBusy) ->
      			Return!ReceiveDmaFree;
      			DmaInUse = 1
      		:: else -> skip
      		fi
      		ns_buffer!hs_data;
      		Return!NetSendQueueNotEmpty;
      		if
      		:: (nempty(hs_buffer)) ->
      			Return!GotASend
      		:: (empty(hs_buffer)) -> skip
      		fi;
      		hs_state = HostSendIdle;
      		dma_int = 0
      	:: else ->skip
      	fi;
      	Return!0
      od }
      					
  4. porównanie oprogramowań pod kątem przepustowości

    Największy wpływ na szybkość przesyłania danych w NIC ma stopień wykorzystania kanałów DMa.
    Maksymalne przepustowości są osiągane gdy EBUS-LBUS DMA działa równolegle z kanałami send-DMA i receive-DMA.

    PrzykładNiech:
    - DMAEBUS-LBUSto przepustowość EBUS-LBUS DMA
    - DMAsendto przepustowość send-DMA

    DMAEBUS-LBUSjest zależna od szerokości szyny wejścia/wyjścia (np. PCI) która łączy pamięć główną z pamięcią SRAM w karcie sieciowej.
    Z drugiej jednak strony DMAsendzależy od fizycznego nośnika danych w sieci (np. od kabla)

    Jeśli kanały DMA działają równolegle, przepustowość wyraża się jako:
      przepustowość = MIN(DMAEBUS-LBUS, DMAsend)

    Jeśli jednak kanały DMA działają sekwencyjnie, przepustowość jest ograniczona do:
      przepustowość = DMAEBUS-LBUS

    1 + DMAEBUS-LBUS

    DMAsend

    zatem, jeśli nawet DMAEBUS-LBUSi DMAsendsą takie same, to wynikowa szybkość przesyłania danych (synchronicznie) ograniczy się do 1/2 DMAEBUS-LBUS!

    Wyprowadzono więc formuły LTL do weryfikacji wykorzystania kanałów DMA:

    1. LCP
      1. <> (LcpTxInvokeRx && HostDmaBusy && !LcpTxHostDma)
        czyli: czy moduł lcpTx może inicjować send-DMA, podczas gdy moduł hostDma używa EBUS-LBUS DMA kopiując dane z pamięci głównej do SRAM?
      2. <> (LcpRxReady && HostDmaBusy && !LcpRxHostDma)
        czyli: czy moduł lcpRx może inicjować receive-DMA, podczas gdy moduł hostDma używa EBUS-LBUS DMA kopiując dane z pamięci SRAM do głównej?
    2. MCP
      1. <> (HostSendDma && NetSendBusy)
        czyli: czy moduł netSend może inicjować operacje send-DMA podczas gdy moduł hostSend korzysta z szyny EBUS-LBUS DMA?
      2. <> (HostReceiveDma && NetReceiveBusy)
        czyli: czy moduł netReceive może inicjować operacje receive-DMA podczas gdy moduł hostReceive korzysta z szyny EBUS-LBUS DMA?

    Jeśli szyny DMA miałyby działać równolegle, weryfikacja każdej z powyższych formuł powinna dać odpowiedź "prawda".
    I o ile SPIN dla MCP dał takie właśnie odpowiedzi, to dla LCP odpowiedzią na obie formuły był "fałsz"! - te wyniki wyjaśniają dlaczego osiągi Berkeley-VIA są tak ograniczone.

    Symulacja dowiodła również, że LCP wykorzystuje DMA sekwencyjnie (szeregowo), podczas gdy MCP wykorzystuje je równolegle. Identyczne wyniki osiągnięto przy symulacjach "interaktywnych" i losowych.

     

    Wykonano dodatkowo jeszcze jeden test, na to czy szyna EBUS-LBUS DMA jest w jednym czasie wykorzystywana przez maksymalnie jeden moduł (ta szyna prowadzi dane zarowno z pamięci głównej do SRAM, jak i w druga strone - stąd moduły powinny czekać aż DMA przestanie być obciążone jeśli inne moduły z niego korzystają)

    Formuły wyglądały jak niżej:

    1. LCP
      [] ! (LcpTxHostDma && LcpRxHostDma)
      czyli: lcpTx nie może używać z EBUS-LBUS DMA w czasie gdy korzysta z niej moduł lcpRx
    2. MCP
      [] ! (HostSendDma && HostReceiveDma)
      czyli: moduł hostSend nie może używać EBUS-LBUS DMA w czasie gdy korzysta z niej moduł hostReceive

    Ta weryfikacja dowiodła, że zarówno LCP jak i MCP spełniają postawione im wymogi

  5. Podsumowując

    Powyżej prześledzono wąskie gardło oprogramowanie Myrinet'u.
    Wyniki pokazały ze: