Parceling the Butterfly and the Batcher Sorting Network
- 684 Downloads
This paper proposes a new metric that aims to express the cost of manufacturing large-scale, communication-intensive digital systems. These systems are modeled by networks with internal and external edges, where the latter are input/output edges connecting the system with the external world. A k–parceling of such a network is a partition of the network into components each having at most k non-internal edges. (Such a partition is of interest when the number of the external edges is much larger than k.) The k–parceling number of a network is the minimal number of components in a k–parceling.
We argue that the parceling number of a large-scale, communication-intensive network expresses the cost of such a system better than the contemporary prevalent metrics and therefore it can guide the designers of such systems better than these metrics.
The paper studies the parceling of two important networks, the Butterfly and the Batcher Bitonic sorting network. It establishes explicit (rather than asymptotic) lower and upper bounds on the parceling number of both networks.
KeywordsDirected Graph Parallel Edge External Edge Graph Embedding Sorting Network
Unable to display preview. Download preview PDF.
- [B90]Bakoglo, H.B.: Circuits, interconnections and packaging for VLSI. Addison-Wesley, Reading (1990)Google Scholar
- [B68]Batcher, K.E.: Sorting networks and their application. In: Proc. AFIPS Spring Joint Computer Conf, vol. 32, pp. 307–314 (1968)Google Scholar
- [BMM78]Bell, C.G., Mudge, J.C., McNamara, J.E.: Computer Engineering. Digital Press (1978)Google Scholar
- [GL04]Golbandi, N., Litman, A.: Characterizations of generalized butterfly networks, T.R. no. CS-2004-10, Dept. of Computer Science, Technion, Israel (2004), http://www.cs.technion.ac.il/users/wwwb/cgibin/tr-info.cgi?2004/CS/CS-2004-10
- [LGGL73]Goke, L.R., Lipovski, G.J.: Banyan Networks For Partitioning Multiprocessing Systems. In: Proceedings of the 1st Annual Symposium on Computer Architecture, pp. 21–28 (1973)Google Scholar
- [HK84]Huang, A., Knauer, S.: Starlite: a wideband digital switch. In: Proceedings of GLOBECOME 1984, pp. 121–125 (1984)Google Scholar
- [L85]Leiserson, C.E.: Fat-trees: universal networks for hardwareefficient supercomputing. IEEE Trans. Comp. C 34, 892–901 (1985)Google Scholar
- [T79]Thompson, C.D.: Area-time complexity for VLSI. In: Proceeding of the 11th Annual ACM Symposium on Theory of Computing, pp. 81–88 (1979)Google Scholar
- [T80]Thompson, C.D.:: A complexity theory for VLSI. Ph.D. Thesis, CMU (1980)Google Scholar
- [WE85]Weste, N.H.E., Eshraghian, K.: Principles of CMOS VLSI design, 1st edn. Addison-Wesley, Reading (1985)Google Scholar