RCC-Full: An Effective Network for Parallel Computations |
| |
Authors: | Mounir Hamdi Richard W Hall |
| |
Affiliation: | aDepartment of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong;bDepartment of Electrical Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania, 15261 |
| |
Abstract: | A new interconnection network is proposed for the construction of a massively parallel computer system. The systematic construction of this interconnection network, denoted RCC-FULL, is performed by methodically connecting together a number of basic atoms where a basic atom is a set of fully interconnected nodes. Key communication characteristics are derived and evaluated for RCC-FULL and efficient routing algorithms, which need only local information to route messages between any two nodes, are also derived. AnO(log (N)) sorting algorithm is shown for RCC-FULL and RCC-FULL is shown to emulate deterministically the CRCW PRAM model, with onlyO(log (N)) degradation in time performance. Finally, the hardware cost for the RCC-FULL is estimated as a function of its pin requirements and compared to that of the binary hypercube and most instances of RCC-FULL have substantially lower cost. Hence, RCC-FULL appears to be a particularly effective network for PRAM emulation, and might be considered as a universal network for future supercomputing systems. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|