Skip to main content
SpringerLink
Log in

Optimal three-dimensional VLSI layouts

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

In this note we propose VLSI layouts for the cube-connectedcycles (CCC) in a three-dimensional medium. The first type of layout is for the all-active-volume mode, where computing modules are placed anywhere within the solid chip; the second type is for the one-active-layer mode, where computing modules are placed on an external face of the solid chip. In both cases we present volume × time optimal realizations. In addition, by opening the cycles of the CCC, one obtains the well-known FFT network. Both realizations use minimum volume; an all-active-volume realization with the same volume performance was earlier proposed by Rosenberg, while the present one-active-layer realization is the only optimal one that is known.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. L. Rosenberg. “Three-dimensional VLSI: A case study,”J. ACM, to appear

  2. V. E. Benes. “Optimal rearrangeable multistage connecting networks,”Bell Syst. Tech. Jour., vol. 43, pp. 1641–1656 (1964).

    Google Scholar 

  3. F. P. Preparata and J. Vuillemin. “The Cube-Connected-Cycles: a versatile network for parallel computation,”Comm. of the ACM. vol. 24, no. 5, pp. 300–309, May 1981.

    Google Scholar 

  4. C. D. Thompson. “Area-time complexity for VLSI,”Proc. of the 11th Annual ACM Symposium on the Theory of Computing (SIGACT). pp. 81–88, (May 1979).

  5. H. S. Stone. “Parallel processing with the perfect shuffle,”IEEE Transactions on Computers. vol. C-20, pp. 153–161 (1971).

    Google Scholar 

  6. F. P. Preparata and J. Vuillemin. “Area-time optimal VLSI networks for computing integer multiplication and Discrete Fourier Transform,”Proceedings of I.C.A.L.P., Haifa, Israel., pp. 29–40, (July 1981).

  7. D. S. Wise. “Compact layouts of Banyan/FFT networks,”Proc. of the CMU Conference on VLSI Systems and Computations, Pittsburgh, Penn., October 1981; pp. 186–195.

Download references

Author information

Authors and Affiliations

  1. Coordinated Science Laboratory, University of Illinois, Urbana, Illinois, USA

    Franco P. Preparata

  2. Departments of Electrical Engineering and of Computer Science, University of Illinois, Urbana, Illinois, USA

    Franco P. Preparata

Authors
  1. Franco P. Preparata
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported in part by National Science Foundation Grants MCS-81-05552 and ECS-81-06939.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Preparata, F.P. Optimal three-dimensional VLSI layouts. Math. Systems Theory 16, 1–8 (1983). https://doi.org/10.1007/BF01744565

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01744565

Keywords

Search

Navigation