Bounds on minimax edge length for complete binary trees

ABSTRACT

Information is not transferred instantaneously; there is always a propagation delay before an output is available as an input to the next computational step. Propagation delay is a function of wire length, so we study the length of edges in planar graphs. We prove matching (to within a constant factor) upper and lower bounds on minimax edge length for four planar embedding problems for complete binary trees. (The results are summarized in Table 1.) Because trees are often subcircuits of larger circuits, these results imply general performance limits due to propagation delay. The results give important information for the popular technique of pipelining.

REFERENCES

• 1: Bentley, J.L. and Kung, H.T., A Tree Machine for Searching Problems, Proceedings of the International Conference on Parallel Processing (1979), 257-266.
• 2: Brent, R.P. and Kung, H.T., On the Area of Binary Tree Layouts, Carnegie-Mellon University, 1979.
• 3: Brent, R.P. and Kung, H.T., A Regular Layout for Parallel Adders, Technical Report CMU-CS-79-131, Carnegie-Mellon University, 1979.
• 4: Gannon, D.B., On Pipelining a Mesh Connected Multiprocessor for Finite Element Problems by Nested Disection, Proceedings of the Internatiuonal Conference on Parallel Processing (1980), 197-204.
• 5: Ladner, R.E. and Fischer, M.J., Parallel Prefix Computation, 1977 International Conference on Parallel Processing (1977). Also available as Technical Report 77-02-02, University of Washington, Department of Computer Science.
• 6: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 7: Rosenberg, A.L. and Snyder, L., Bounds on the Cost of Data Encodings, Mathematical Systems Theory 12 (1978), 9-39.
• 8: Stone, H.S., Parallel Processing with the Perfect Shuffle, IEEE Transactions on Computers C-20 (1971), 153-161.
• 9: Thompson, C.D., Private Communication
• 10: Valiant, L.G., Universality Considerations in VLSI Circuits, Edinburgh University, December, 1979.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Theory