Minimizing communication overhead for matrix inversion algorithms on hypercubes

I
IPPS
1995
9th International Parallel Processing Symposium
Abstract - Minimizing communication overhead for matrix inversion algorithms on hypercubes

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Xiaodong Wang Articles by V.P. Roychowdhury

9th International Parallel Processing Symposium

Santa Barbara, CA

April 25-April 28

ISBN: 0-8186-7074-6

	ASCII Text	x
	Xiaodong Wang, V.P. Roychowdhury, "Minimizing communication overhead for matrix inversion algorithms on hypercubes," Parallel Processing Symposium, International, pp. 446, 9th International Parallel Processing Symposium, 1995.

	BibTex	x
	@article{ 10.1109/IPPS.1995.395969, author = {Xiaodong Wang and V.P. Roychowdhury}, title = {Minimizing communication overhead for matrix inversion algorithms on hypercubes}, journal ={Parallel Processing Symposium, International}, volume = {0}, year = {1995}, issn = {1063-7133}, pages = {446}, doi = {http://doi.ieeecomputersociety.org/10.1109/IPPS.1995.395969}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Processing Symposium, International TI - Minimizing communication overhead for matrix inversion algorithms on hypercubes SN - 1063-7133 SP EP A1 - Xiaodong Wang, A1 - V.P. Roychowdhury, PY - 1995 KW - hypercube networks; matrix inversion; parallel algorithms; communication complexity; minimisation; communication overhead; matrix inversion algorithms; hypercubes; Gauss-Jordan inversion algorithms; parallel inversion algorithms; data partitioning; MIMD hypercube; asynchronous message passing; interrupt handling; performance analysis VL - 0 JA - Parallel Processing Symposium, International ER -

Xiaodong Wang, Sch. of Electr. Eng., Purdue Univ., West Lafayette, IN, USA

V.P. Roychowdhury, Sch. of Electr. Eng., Purdue Univ., West Lafayette, IN, USA

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPPS.1995.395969

We propose novel parallel Gauss-Jordan inversion algorithms (with or without partial pivoting) under different data partitioning strategies. The machine model we assume is a MIMD hypercube, using asynchronous message passing, with the software supporting user specified interrupt handling. These algorithms achieve almost optimal overlapping of communication delays by computation, leading to a minimization of communication overhead. Furthermore, it is shown that the optimal data layout for our algorithms is different from that for hypercubes that do not overlap communication and computation. Rigorous analytical and numerical performance analysis of our parallel algorithms are presented as well.

Index Terms:

hypercube networks; matrix inversion; parallel algorithms; communication complexity; minimisation; communication overhead; matrix inversion algorithms; hypercubes; Gauss-Jordan inversion algorithms; parallel inversion algorithms; data partitioning; MIMD hypercube; asynchronous message passing; interrupt handling; performance analysis

Citation:

Xiaodong Wang, V.P. Roychowdhury, "Minimizing communication overhead for matrix inversion algorithms on hypercubes," ipps, pp.446, 9th International Parallel Processing Symposium, 1995

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.