Šířka pásma půlení - Bisection bandwidth

V počítačové síti, pokud je síť půlený do dvou oddílů, šířka pásma půlení a topologie sítě je šířka pásma dostupná mezi dvěma oddíly.[1] Bisection by mělo být provedeno tak, aby šířka pásma mezi dvěma oddíly je minimum.[2] Šířka pásma půlení poskytuje skutečnou šířku pásma dostupnou v celém systému. Šířka pásma Bisection odpovídá úzké šířce pásma celé sítě. Šířka pásma půlení proto představuje charakteristiky šířky pásma sítě lépe než jakákoli jiná metrika.

Výpočty šířky pásma půlení[2]

Pro lineární pole s n uzly šířka pásma půlení je jedna šířka pásma. U lineárního pole musí být rozděleno pouze jedno spojení, aby se síť rozdělila na dva oddíly.

Rozdělení sítě lineárního pole

Pro prsten topologie s n uzly by měla být přerušena dvě spojení, aby se rozdělila síť, takže šířka pásma půlení se změní na šířku pásma dvou odkazů.

Rozdělení kruhové sítě

Pro strom topologii s n uzly lze rozdělit na kořen rozbitím jednoho odkazu, takže šířka pásma půlení je jedna šířka pásma.

Rozdělení sítě stromů

Pro Pletivo topologie s n uzly, odkazy by měly být přerušeny, aby rozdělily síť, takže šířka pásma půlení je šířka pásma Odkazy.

Rozdělení 2D sítě

Pro Hyper kostka topologie s n uzly, n / 2 odkazy by měly být přerušeny, aby rozdělily síť, takže šířka pásma půlení je šířka pásma n / 2 odkazů.

Rozdělení sítě hyper-krychlí

Význam šířky pásma půlení

Teoretická podpora důležitosti tohoto měřítka výkonu sítě byla vyvinuta v doktorském výzkumu v Clark Thomborson (dříve Clark Thompson).[3] Thomborson dokázal, že důležité algoritmy pro třídění, Rychlá Fourierova transformace a multiplikace matice-matice se u počítačů s nedostatečnou šířkou půlení stanou omezenou komunikací - na rozdíl od CPU-omezenou nebo omezenou pamětí. F. Thomson Leighton PhD výzkum[4] zpřísnil Thomborsonovu volnou vazbu [5] na půlové šířce výpočetně důležité varianty De Bruijnův graf známý jako Síťová směnárna. Na základě Bill Dally je analýza latence, průměrné propustnosti případů a propustnosti hot-spot sítí m-ary n-cube[2] pro různé m lze pozorovat, že nízkodimenzionální sítě ve srovnání s vysokodimenzionálními sítěmi (např. binární n-kostky) se stejnou šířkou půlení (např. Tori ), mají sníženou latenci a vyšší propustnost hot-spot.[6]

Reference

  1. ^ John L. Hennessy a David A. Patterson (2003). Počítačová architektura: kvantitativní přístup (Třetí vydání.). Morgan Kaufmann Publishers, Inc. str.789. ISBN  978-1-55860-596-1.
  2. ^ A b C Solihin, Yan (2016). Základy paralelní vícejádrové architektury. CRC Press. 371–381. ISBN  9781482211191.
  3. ^ C. D. Thompson (1980). Teorie složitosti pro VLSI (PDF) (Teze). Carnegie-Mellon University.
  4. ^ F. Thomson Leighton (1983). Problémy se složitostí ve VLSI: Optimální rozvržení pro graf zamíchané směny a další sítě (Teze). MIT Stiskněte. ISBN  0-262-12104-2.
  5. ^ Clark Thompson (1979). Časoprostorová složitost pro VLSI. Proc. Caltech Conf. o systémech a výpočtech VLSI. 81–88.
  6. ^ Bill Dally (1990). "Analýza výkonu propojovacích sítí k-ary n-cube". Transakce IEEE na počítačích. 39 (6): 775–785. CiteSeerX  10.1.1.473.5096. doi:10.1109/12.53599.