Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors

Y. R. Leu; I. Y. Chen; S. Y. Kuo

doi:10.1109/ASAP.1993.397139

Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors

Y. R. Leu, I. Y. Chen, S. Y. Kuo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Several new algorithms for matrix-matrix multiplications on hypercube multiprocessors are presented and evaluated based on the number of multiplications, additions, and transfers. The matrices to be multiplied are uniformly distributed to all processors of a hypercube system. Each processor owns some submatrices which are derived by dividing the source matrices. Each submatrix multiplication can now be performed independently within a processor. All the partial results are then summed up and transferred to a single processor. An orthogonal tree is used for efficient communication. The time complexity is O(log₂p) if p × p processors are used. In addition, the UDD (Uniform Data Distribution) approach is employed when some processors do not work properly and the faulty effects have been detected. Two classes of fault patterns are considered and evaluated.

Original language	English
Title of host publication	Proceedings of International Conference on Application Specific Array Processors, ASAP 1993
Editors	Benjamin Wah, Luigi Dadda
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	176-179
Number of pages	4
ISBN (Electronic)	0818634928
DOIs	https://doi.org/10.1109/ASAP.1993.397139
State	Published - 1993
Externally published	Yes
Event	1993 International Conference on Application Specific Array Processors, ASAP 1993 - Venice, Italy Duration: 25 10 1993 → 27 10 1993

Publication series

Name	Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors
ISSN (Print)	1063-6862

Conference

Conference	1993 International Conference on Application Specific Array Processors, ASAP 1993
Country/Territory	Italy
City	Venice
Period	25/10/93 → 27/10/93

Bibliographical note

Publisher Copyright:
© 1993 IEEE.

Access to Document

10.1109/ASAP.1993.397139

Cite this

Leu, Y. R., Chen, I. Y., & Kuo, S. Y. (1993). Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors. In B. Wah, & L. Dadda (Eds.), Proceedings of International Conference on Application Specific Array Processors, ASAP 1993 (pp. 176-179). Article 397139 (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASAP.1993.397139

Leu, Y. R. ; Chen, I. Y. ; Kuo, S. Y. / Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors. Proceedings of International Conference on Application Specific Array Processors, ASAP 1993. editor / Benjamin Wah ; Luigi Dadda. Institute of Electrical and Electronics Engineers Inc., 1993. pp. 176-179 (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors).

@inproceedings{74e4951f585841a093a2a8b0b4118668,

title = "Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors",

abstract = "Several new algorithms for matrix-matrix multiplications on hypercube multiprocessors are presented and evaluated based on the number of multiplications, additions, and transfers. The matrices to be multiplied are uniformly distributed to all processors of a hypercube system. Each processor owns some submatrices which are derived by dividing the source matrices. Each submatrix multiplication can now be performed independently within a processor. All the partial results are then summed up and transferred to a single processor. An orthogonal tree is used for efficient communication. The time complexity is O(log2p) if p × p processors are used. In addition, the UDD (Uniform Data Distribution) approach is employed when some processors do not work properly and the faulty effects have been detected. Two classes of fault patterns are considered and evaluated.",

author = "Leu, {Y. R.} and Chen, {I. Y.} and Kuo, {S. Y.}",

note = "Publisher Copyright: {\textcopyright} 1993 IEEE.; 1993 International Conference on Application Specific Array Processors, ASAP 1993 ; Conference date: 25-10-1993 Through 27-10-1993",

year = "1993",

doi = "10.1109/ASAP.1993.397139",

language = "英语",

series = "Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors",

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

pages = "176--179",

editor = "Benjamin Wah and Luigi Dadda",

booktitle = "Proceedings of International Conference on Application Specific Array Processors, ASAP 1993",

address = "美国",

}

Leu, YR, Chen, IY & Kuo, SY 1993, Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors. in B Wah & L Dadda (eds), Proceedings of International Conference on Application Specific Array Processors, ASAP 1993., 397139, Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors, Institute of Electrical and Electronics Engineers Inc., pp. 176-179, 1993 International Conference on Application Specific Array Processors, ASAP 1993, Venice, Italy, 25/10/93. https://doi.org/10.1109/ASAP.1993.397139

Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors. / Leu, Y. R.; Chen, I. Y.; Kuo, S. Y.
Proceedings of International Conference on Application Specific Array Processors, ASAP 1993. ed. / Benjamin Wah; Luigi Dadda. Institute of Electrical and Electronics Engineers Inc., 1993. p. 176-179 397139 (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors

AU - Leu, Y. R.

AU - Chen, I. Y.

AU - Kuo, S. Y.

PY - 1993

Y1 - 1993

N2 - Several new algorithms for matrix-matrix multiplications on hypercube multiprocessors are presented and evaluated based on the number of multiplications, additions, and transfers. The matrices to be multiplied are uniformly distributed to all processors of a hypercube system. Each processor owns some submatrices which are derived by dividing the source matrices. Each submatrix multiplication can now be performed independently within a processor. All the partial results are then summed up and transferred to a single processor. An orthogonal tree is used for efficient communication. The time complexity is O(log2p) if p × p processors are used. In addition, the UDD (Uniform Data Distribution) approach is employed when some processors do not work properly and the faulty effects have been detected. Two classes of fault patterns are considered and evaluated.

AB - Several new algorithms for matrix-matrix multiplications on hypercube multiprocessors are presented and evaluated based on the number of multiplications, additions, and transfers. The matrices to be multiplied are uniformly distributed to all processors of a hypercube system. Each processor owns some submatrices which are derived by dividing the source matrices. Each submatrix multiplication can now be performed independently within a processor. All the partial results are then summed up and transferred to a single processor. An orthogonal tree is used for efficient communication. The time complexity is O(log2p) if p × p processors are used. In addition, the UDD (Uniform Data Distribution) approach is employed when some processors do not work properly and the faulty effects have been detected. Two classes of fault patterns are considered and evaluated.

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

U2 - 10.1109/ASAP.1993.397139

DO - 10.1109/ASAP.1993.397139

M3 - 会议稿件

AN - SCOPUS:85064708198

T3 - Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors

SP - 176

EP - 179

BT - Proceedings of International Conference on Application Specific Array Processors, ASAP 1993

A2 - Wah, Benjamin

A2 - Dadda, Luigi

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 1993 International Conference on Application Specific Array Processors, ASAP 1993

Y2 - 25 October 1993 through 27 October 1993

ER -

Leu YR, Chen IY, Kuo SY. Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors. In Wah B, Dadda L, editors, Proceedings of International Conference on Application Specific Array Processors, ASAP 1993. Institute of Electrical and Electronics Engineers Inc. 1993. p. 176-179. 397139. (Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors). doi: 10.1109/ASAP.1993.397139

Matrix-matrix multiplications and fault tolerance on hypercube multiprocessors

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this