Adam Mazur

Bottleneck Analysis of a Gigabit Network Interface Card

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:
- Berkeley-VIA ma większą przepustowość niż UDP na Myrinet'cie, ale już dużo mniejszą niż tzw. Asynchroniczne UDP jeśli brac pod uwagę pakiety większe niz 4Kb
- Berkeley-VIA podczas transmisji ma mniejszy czas oczekiwania niż UDP i Asynchroniczne UDP.
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
budowa Myrinet NIC

Myrinet NIC zawiera:
- procesor RISC nazwany LanAI
- pamięć SRAM (Static Random Access Memory) - przetrzymuje odebrane dane lub dane do wysłania
- trzy szyny DMA:
  - EBUS-LBUS DMA - odpowiedzialna za transfer danych pomiedzy SRAM'em a pamiecią główną
  - send-DMA - odpowiedzialne za transfer danych z SRAM'u do wlaściwej sieci
  - receive-DMA - odpowiedzialne za transfer danych z sieci do SRAM'u
modelowanie

Analizowano dwa oprogramowania sprzętowe:
- Lanai Control Program (LCP) - obsługującym stronę Berkeley-VIA
- Myrinet Control Program (MCP) - oblsługującym stronę tradycyjnych protokołów jak TCP czy UDP
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 }
					
```

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:
- DMA_EBUS-LBUSto przepustowość EBUS-LBUS DMA
- DMA_sendto przepustowość send-DMA

DMA_EBUS-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 DMA_sendzależ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(DMA_EBUS-LBUS, DMA_send)

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

`przepustowość =`	`DMA_EBUS-LBUS`

	`1 +`	`DMA_EBUS-LBUS`

		`DMA_send`

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

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

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?
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:

LCP
[] ! (LcpTxHostDma && LcpRxHostDma)
czyli: lcpTx nie może używać z EBUS-LBUS DMA w czasie gdy korzysta z niej moduł lcpRx
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

Podsumowując

Powyżej prześledzono wąskie gardło oprogramowanie Myrinet'u.
Wyniki pokazały ze:
- LCP wykorzystuje DMA szeregowo, co prowadzi do zmniejszenia szybkości przesyłania danych w Berkeley-VIA.
- MCP w pełni wykorzystuje wszystkie trzy kanały DMA:
  jego wewnętrzna struktura jest bardziej wyszukana niż LCP, moduły maja wiele punktów wejscia (w porównaniu z pojedynczymi punktami wejscia w LCP) a takie rozwiązanie pozwala działać kanałom DMA równolegle.

Adam Mazur

Bottleneck Analysis of a Gigabit Network Interface Card

Co weryfikujemy

budowa Myrinet NIC

modelowanie

porównanie oprogramowań pod kątem przepustowości

Podsumowując