TY - GEN
T1 - Efficient CRCW PRAM emulation on practical networks
AU - Hamdi, M.
PY - 1994
Y1 - 1994
N2 - A new interconnection network is proposed for the construction of massively parallel computers. The systematic construction of this network, denoted RCNFULL, is performed by methodically connecting together a number of basic atoms where a basic atom is a set of fully connected nodes. Key communication characteristics and efficient routing algorithms are derivedfor RCN-FULL. An 0(log(N)) sorting algorithm is shown for RCN-FULL and RCN-FULL is proven to deterministically emulate the CRCW PRAM model, with only O(log{N)) degradation in time performance. Finally, the hardware cost for the RCNFULL is estimated as a function of its pin limitations and compared favorably to that of the hypercube.
AB - A new interconnection network is proposed for the construction of massively parallel computers. The systematic construction of this network, denoted RCNFULL, is performed by methodically connecting together a number of basic atoms where a basic atom is a set of fully connected nodes. Key communication characteristics and efficient routing algorithms are derivedfor RCN-FULL. An 0(log(N)) sorting algorithm is shown for RCN-FULL and RCN-FULL is proven to deterministically emulate the CRCW PRAM model, with only O(log{N)) degradation in time performance. Finally, the hardware cost for the RCNFULL is estimated as a function of its pin limitations and compared favorably to that of the hypercube.
UR - https://www.scopus.com/pages/publications/84904310950
U2 - 10.1109/ICPP.1994.100
DO - 10.1109/ICPP.1994.100
M3 - Conference contribution
AN - SCOPUS:84904310950
SN - 0849324955
T3 - Proceedings of the International Conference on Parallel Processing
SP - III147-III150
BT - Proceedings of the 1994 International Conference on Parallel Processing, ICPP 1994
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 23rd International Conference on Parallel Processing, ICPP 1994
Y2 - 15 August 1994 through 19 August 1994
ER -