The cube-connected cycles: a versatile network for parallel computation

ABSTRACT

An interconnection pattern of processing elements, the cube-connected cycles (CCC), is introduced which can be used as a general purpose parallel processor. Because its design complies with present technological constraints, the CCC can also be used in the layout of many specialized large scale integrated circuits (VLSI). By combining the principles of parallelism and pipelining, the CCC can emulate the cube-connected machine and the shuffle-exchange network with no significant degradation of performance but with a more compact structure. We describe in detail how to program the CCC for efficiently solving a large class of problems that include Fast Fourier transform, sorting, permutations, and derived algorithms.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Barnes, G.H., Brown, R.M., Kato, M., Kuck, D.J,, Slotnick, DL, and Stokes, R.A. The ILLIAC IV computer. IEEE Trans. Comput. C-17, 8, (Aug. 1968), 746-757.
• 3: Batcher, K.E., Sorting networks and their applications. Proc. AF1PS Spring Joint Computer Conf. 32, Atlantic City, N J, April 1968, 307-314.
• 4: R. P. Brent , H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.190-200, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804666]
• 5: W. Morven Gentleman, Some Complexity Results for Matrix Computations on Parallel Processors, Journal of the ACM (JACM), v.25 n.1, p.112-115, Jan. 1978 [doi>10.1145/322047.322057]
• 6: Guibas, L.J., Kung, H.T., and Thompson, C.D., Direct VSLI implementation of combinatorial algorithms. Res. Rept., Dept. Comp. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, March 1979.
• 7: Heller, D., A survey of parallel algorithms in numerical linear algebra. Dept. Comp. Sci., Carnegie-Mellon Univ., Pittsburgh, PA, Feb. 1976.
• 8: D. S. Hirschberg, Fast parallel sorting algorithms, Communications of the ACM, v.21 n.8, p.657-661, Aug. 1978 [doi>10.1145/359576.359582]
• 9: Hoey, D., and Leiserson, C.L., A layout for the shuffle-exchange network. Proc. 1980 Int'l Conf. on Parallel Processing, Boyne, MI, Aug. 1980, 327-336.
• 10: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 11: Kung, H.T., and Leiserson, C.E., Algorithms for VSLI processor arrays. Symp. on Sparse Matrix Computations, Knoxville, TN, Nov. 1978.
• 12: K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
• 13: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 14: Nassimi, D., and Sahni, S., Bitonic sort on a mesh-connected parallel computer. IEEE Trans. Comput. C-28, 1, (Jan. 1979) 2-7.
• 15: Pease, M.C., The indirect binary n-cube microprocessor array. 1EEE Trans. Comput. C-26, 5, (May 1977) 458-473.
• 16: Marshall C. Pease, An Adaptation of the Fast Fourier Transform for Parallel Processing, Journal of the ACM (JACM), v.15 n.2, p.252-264, April 1968 [doi>10.1145/321450.321457]
• 17: Preparata, F.P., and Vuillemin, J., Area time optimal VLSI networks based in the cube-connected cycles. Tech. Rept. INRIA n.13, Rocquencourt, France and ACT-.21, Coord. Sci. Lab., Univ. Illinois, Urbana, IL, 1980.
• 18: Preparata, F.P., New parallel sorting schemes. 1EEE Trans. Comput. C-27, 7, (July 1978) 669-673.
• 19: Steinberg, D., and Rodeh, M., A layout for the shuffle-exchange network with O(A T/log3/2N) area. (Submitted for publication).
• 20: Stone, H.S,, Parallel processing with the perfect shuffle. IEEE Trans. Comput. C-20, 2, (Feb. 1971) 153-161.
• 21: Clark David Thompson, A complexity theory for vlsi, 1980
• 22: C. D. Thompson, Area-time complexity for VLSI, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.81-88, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804401]
• 23: C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Proceedings of the eighth annual ACM symposium on Theory of computing, p.58-64, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803632]
• 24: Valiant, L.G., Parallelism in comparison problems. SlAM J. Comput., 4, 3, (Sept. 1975) 348-355.
• 25: Vuillemin, J., A combinatorial limit to the computing power of VSLI circuits. Proc. 21st Symp. on Foundations of Computer Science. Syracuse, NY, Oct. 1980, 294-300
• 26: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Management, Performance, Theory

Keywords:
Fourier transform, VLSI design, parallel processing, sorting