The Cube-Connected Cycles: A Versatile Network for Parallel Computation

The Cube-Connected Cycles: A Versatile Network for Parallel Computation

May 1981 | Franco P. Preparata, Jean Vuillemin
The paper introduces the cube-connected cycles (CCC), a versatile network for parallel computation. The CCC is designed to be a general-purpose parallel processor and is suitable for VLSI implementation. It combines pipelining and parallelism to emulate the cube-connected machine and shuffle-exchange network with minimal performance degradation and a more compact structure. The CCC is efficient for solving a wide range of problems, including Fast Fourier Transform, sorting, and permutations. The CCC has three interconnection ports per module, allowing bidirectional data transmission. It supports both synchronous and self-timed execution, and its layout complies with VLSI requirements such as modularity and simplicity of communication. The CCC can be programmed systematically from global algorithms, and it offers optimal area-time complexity for several problems. The paper describes algorithms in the DESCEND and ASCEND classes, which are used for various parallel tasks. The CCC can emulate these algorithms efficiently, with the DESCEND algorithm running in O(log n) steps. The CCC's layout is more compact and regular than previous networks, and it achieves optimal performance in terms of area-time complexity. The paper also discusses the implementation of the CCC for VLSI, showing that it can be used for various applications, including matrix multiplication, sorting, and convolution. The CCC's layout is compared to other networks like the shuffle-exchange, demonstrating its efficiency and versatility. The CCC is expected to be practically feasible and capable of efficiently executing a wide variety of algorithms, making it a promising architecture for parallel computing.The paper introduces the cube-connected cycles (CCC), a versatile network for parallel computation. The CCC is designed to be a general-purpose parallel processor and is suitable for VLSI implementation. It combines pipelining and parallelism to emulate the cube-connected machine and shuffle-exchange network with minimal performance degradation and a more compact structure. The CCC is efficient for solving a wide range of problems, including Fast Fourier Transform, sorting, and permutations. The CCC has three interconnection ports per module, allowing bidirectional data transmission. It supports both synchronous and self-timed execution, and its layout complies with VLSI requirements such as modularity and simplicity of communication. The CCC can be programmed systematically from global algorithms, and it offers optimal area-time complexity for several problems. The paper describes algorithms in the DESCEND and ASCEND classes, which are used for various parallel tasks. The CCC can emulate these algorithms efficiently, with the DESCEND algorithm running in O(log n) steps. The CCC's layout is more compact and regular than previous networks, and it achieves optimal performance in terms of area-time complexity. The paper also discusses the implementation of the CCC for VLSI, showing that it can be used for various applications, including matrix multiplication, sorting, and convolution. The CCC's layout is compared to other networks like the shuffle-exchange, demonstrating its efficiency and versatility. The CCC is expected to be practically feasible and capable of efficiently executing a wide variety of algorithms, making it a promising architecture for parallel computing.
Reach us at info@study.space
[slides] The cube-connected-cycles%3A A versatile network for parallel computation | StudySpace