Efficient CRCW PRAM emulation on practical networks

M. Hamdi

doi:10.1109/ICPP.1994.100

Efficient CRCW PRAM emulation on practical networks

M. Hamdi^*

^*Corresponding author for this work

Hong Kong University of Science and Technology

Research output: Contribution to journal › Conference article › peer-review

Abstract

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.

Original language	English
Article number	5727848
Pages (from-to)	III147-III150
Journal	Proceedings of the International Conference on Parallel Processing
Volume	3
DOIs	https://doi.org/10.1109/ICPP.1994.100
Publication status	Published - 1994
Externally published	Yes
Event	23rd International Conference on Parallel Processing, ICPP 1994 - Raleigh, NC, United States Duration: 15 Aug 1994 → 19 Aug 1994

Access to Document

10.1109/ICPP.1994.100

Cite this

@article{6a1a5c910d294970b8d13d92a3b8e804,

title = "Efficient CRCW PRAM emulation on practical networks",

abstract = "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.",

author = "M. Hamdi",

year = "1994",

doi = "10.1109/ICPP.1994.100",

language = "English",

volume = "3",

pages = "III147--III150",

journal = "Proceedings of the International Conference on Parallel Processing",

issn = "0190-3918",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "23rd International Conference on Parallel Processing, ICPP 1994 ; Conference date: 15-08-1994 Through 19-08-1994",

}

TY - JOUR

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 - http://www.scopus.com/inward/record.url?scp=84904310950&partnerID=8YFLogxK

U2 - 10.1109/ICPP.1994.100

DO - 10.1109/ICPP.1994.100

M3 - Conference article

AN - SCOPUS:84904310950

SN - 0190-3918

VL - 3

SP - III147-III150

JO - Proceedings of the International Conference on Parallel Processing

JF - Proceedings of the International Conference on Parallel Processing

M1 - 5727848

T2 - 23rd International Conference on Parallel Processing, ICPP 1994

Y2 - 15 August 1994 through 19 August 1994

ER -

Efficient CRCW PRAM emulation on practical networks

Abstract

Access to Document

Other files and links

Fingerprint

Cite this