Parceling the Butterfly and the Batcher Sorting Network

  • Ami Litman
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3895)


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.


Directed Graph Parallel Edge External Edge Graph Embedding Sorting Network 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [AKS83]
    Ajtai, M., Komlós, J., Szemerédi, E.: Sorting in c log n parallel steps. Combinatorica 3, 1–19 (1983)zbMATHCrossRefMathSciNetGoogle Scholar
  2. [B90]
    Bakoglo, H.B.: Circuits, interconnections and packaging for VLSI. Addison-Wesley, Reading (1990)Google Scholar
  3. [B68]
    Batcher, K.E.: Sorting networks and their application. In: Proc. AFIPS Spring Joint Computer Conf, vol. 32, pp. 307–314 (1968)Google Scholar
  4. [BMM78]
    Bell, C.G., Mudge, J.C., McNamara, J.E.: Computer Engineering. Digital Press (1978)Google Scholar
  5. [BFJM87]
    Bermond, J.C., Fourneau, J.M., Jean-Marie, A.: Equivalence of multistage interconnection networks. Information Processing Letters 26, 45–50 (1987/88)CrossRefGoogle Scholar
  6. [BCR91]
    Bhatt, S.N., Chung, F.R.K., Rosenberg, A.L.: Partitioning circuits for improved testability. Algorithmica 6, 37–48 (1991)zbMATHCrossRefMathSciNetGoogle Scholar
  7. [EL97]
    Even, S., Litman, A.: Layered Cross Product - a technique to construct interconnection networks. Networks 29, 219–223 (1997)zbMATHCrossRefMathSciNetGoogle Scholar
  8. [GHMSL91]
    Giacopelli, J.N., Hickey, J.J., Marcus, W.S., Sincoskie, W.D., Littlewood, M.: Sunshine: a high-performance self-routing broadband packet switch architecture. IEEE Journal on Selected Areas in Communications 9, 1289–1298 (1991)CrossRefGoogle Scholar
  9. [GL04]
    Golbandi, N., Litman, A.: Characterizations of generalized butterfly networks, T.R. no. CS-2004-10, Dept. of Computer Science, Technion, Israel (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
  11. [HK84]
    Huang, A., Knauer, S.: Starlite: a wideband digital switch. In: Proceedings of GLOBECOME 1984, pp. 121–125 (1984)Google Scholar
  12. [LR86]
    Leighton, F.T., Rosenberg, A.L.: Three-dimensional circuit layouts. SIAM J. Comput. 15, 793–813 (1986)zbMATHCrossRefMathSciNetGoogle Scholar
  13. [L92]
    Leighton, F.T.: Introduction to parallel algorithms and architectures. Morgan Kaufmann, San Francisco (1992)zbMATHGoogle Scholar
  14. [L85]
    Leiserson, C.E.: Fat-trees: universal networks for hardwareefficient supercomputing. IEEE Trans. Comp. C 34, 892–901 (1985)Google Scholar
  15. [LS83]
    Leiserson, C.E., Saxe, J.B.: Optimizing synchronous systems. Journal of VLSI and Computer Systems 1, 41–67 (1983)zbMATHGoogle Scholar
  16. [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
  17. [T80]
    Thompson, C.D.:: A complexity theory for VLSI. Ph.D. Thesis, CMU (1980)Google Scholar
  18. [WE85]
    Weste, N.H.E., Eshraghian, K.: Principles of CMOS VLSI design, 1st edn. Addison-Wesley, Reading (1985)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Ami Litman
    • 1
  1. 1.Computer Science DepartmentTechnionHaifaIsrael

Personalised recommendations