Fault-tolerant sorting in SIMD hypercubes

Amitabh Mishra; Y. Chang; L. Bhuyan; F. Lombardi

Fault-tolerant sorting in SIMD hypercubes

Amitabh Mishra, Y. Chang, L. Bhuyan, F. Lombardi

Department of Computer Science and Information Engineering

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

2 Citations (Scopus)

Abstract

This paper considers sorting in SIMD hypercube multiprocessors in the presence of node failures. The proposed algorithm correctly sorts up to 2ⁿ = N keys in a faulty SIMD hypercube of dimension n containing up to n - 1 faulty nodes. The proposed fault-tolerant algorithm employs radix sort. We use a pair of flood dimensions which helps to route data around the faulty processors during the movement of data. If all the key values to be sorted belong to the range 0 to M - 1, sorting can be accomplished efficiently in O(log M·log N) + O(log²N) time.

Original language	English
Pages (from-to)	312-318
Number of pages	7
Journal	IEEE Symposium on Parallel and Distributed Processing - Proceedings
Publication status	Published - 1995
Event	Proceedings of the IEEE 9th International Parallel Processing Symposium - Santa Barbara, CA, USA Duration: 1995 Apr 25 → 1995 Apr 28

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@article{c8d35d7bba5348368c677e9ea43f020e,

title = "Fault-tolerant sorting in SIMD hypercubes",

abstract = "This paper considers sorting in SIMD hypercube multiprocessors in the presence of node failures. The proposed algorithm correctly sorts up to 2n = N keys in a faulty SIMD hypercube of dimension n containing up to n - 1 faulty nodes. The proposed fault-tolerant algorithm employs radix sort. We use a pair of flood dimensions which helps to route data around the faulty processors during the movement of data. If all the key values to be sorted belong to the range 0 to M - 1, sorting can be accomplished efficiently in O(log M·log N) + O(log2N) time.",

author = "Amitabh Mishra and Y. Chang and L. Bhuyan and F. Lombardi",

year = "1995",

language = "English",

pages = "312--318",

journal = "IEEE Symposium on Parallel and Distributed Processing - Proceedings",

issn = "1063-6374",

note = "Proceedings of the IEEE 9th International Parallel Processing Symposium ; Conference date: 25-04-1995 Through 28-04-1995",

}

TY - JOUR

T1 - Fault-tolerant sorting in SIMD hypercubes

AU - Mishra, Amitabh

AU - Chang, Y.

AU - Bhuyan, L.

AU - Lombardi, F.

PY - 1995

Y1 - 1995

N2 - This paper considers sorting in SIMD hypercube multiprocessors in the presence of node failures. The proposed algorithm correctly sorts up to 2n = N keys in a faulty SIMD hypercube of dimension n containing up to n - 1 faulty nodes. The proposed fault-tolerant algorithm employs radix sort. We use a pair of flood dimensions which helps to route data around the faulty processors during the movement of data. If all the key values to be sorted belong to the range 0 to M - 1, sorting can be accomplished efficiently in O(log M·log N) + O(log2N) time.

AB - This paper considers sorting in SIMD hypercube multiprocessors in the presence of node failures. The proposed algorithm correctly sorts up to 2n = N keys in a faulty SIMD hypercube of dimension n containing up to n - 1 faulty nodes. The proposed fault-tolerant algorithm employs radix sort. We use a pair of flood dimensions which helps to route data around the faulty processors during the movement of data. If all the key values to be sorted belong to the range 0 to M - 1, sorting can be accomplished efficiently in O(log M·log N) + O(log2N) time.

UR - http://www.scopus.com/inward/record.url?scp=0029239489&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029239489&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0029239489

SN - 1063-6374

SP - 312

EP - 318

JO - IEEE Symposium on Parallel and Distributed Processing - Proceedings

JF - IEEE Symposium on Parallel and Distributed Processing - Proceedings

T2 - Proceedings of the IEEE 9th International Parallel Processing Symposium

Y2 - 25 April 1995 through 28 April 1995

ER -

Fault-tolerant sorting in SIMD hypercubes

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this