Szerokość pasma bisekcji
W sieciach komputerowych, jeśli sieć jest podzielona na dwie partycje o równej wielkości, przepustowość topologii sieci to przepustowość dostępna między dwiema partycjami. Bisekcję należy wykonać w taki sposób, aby przepustowość między dwiema partycjami była minimalna. Bisekcja przepustowości daje rzeczywistą przepustowość dostępną w całym systemie. Bisekcja przepustowości odpowiada za wąskie gardło całej sieci. Dlatego przepustowość dzielona na pół lepiej odzwierciedla charakterystykę przepustowości sieci niż jakakolwiek inna metryka.
Obliczenia szerokości pasma bisekcji
Dla macierzy liniowej z n węzłami przepustowość w połowie odpowiada szerokości pasma jednego łącza. W przypadku macierzy liniowej wystarczy przerwać tylko jedno łącze, aby podzielić sieć na dwie części.
Dla topologii pierścienia z n węzłami dwa łącza powinny zostać przerwane, aby przepołowić sieć, więc przepustowość przekrojowa staje się przepustowością dwóch łączy.
W przypadku topologii drzewa z n węzłami można podzielić na pół w korzeniu przez zerwanie jednego łącza, więc przepustowość przecięcia to jedna przepustowość łącza.
W przypadku topologii siatki z n łącza powinny zostać przerwane, aby przepołowić sieć, więc przepustowość w połowie .
W przypadku topologii hipersześcianu z n węzłami, n/2 łączy powinno zostać przerwanych w celu podzielenia sieci na pół, więc przepustowość przekrojowa to przepustowość n/2 łączy.
Znaczenie szerokości pasma bisekcji
Teoretyczne wsparcie dla znaczenia tej miary wydajności sieci zostało opracowane w badaniach doktoranckich Clarka Thomborsona (dawniej Clark Thompson) . Thomborson udowodnił, że ważne algorytmy sortowania, szybkiej transformacji Fouriera i mnożenia macierz-macierz stają się ograniczone pod względem komunikacji — w przeciwieństwie do ograniczeń procesora lub pamięci — na komputerach z niewystarczającą szerokością podziału. Badania doktoranckie F. Thomsona Leightona zacieśniły luźną granicę Thomborsona co do szerokości bisekcji ważnego obliczeniowo wariantu grafu De Bruijna, znanego jako sieć wymiany losowej . Na podstawie przeprowadzonej przez Billa Dally'ego analizy opóźnień, średniej przepustowości przypadku i przepustowości punktów aktywnych m-ary sieci n-kostek dla różnych m, można zaobserwować, że sieci niskowymiarowe, w porównaniu z sieciami wielowymiarowymi (np. n-sześcianów) o tej samej szerokości przecięcia (np. tori ), mają zmniejszone opóźnienia i wyższą przepustowość punktów aktywnych.