Assignment and scheduling in parallel matrix factorization

TitleAssignment and scheduling in parallel matrix factorization
Publication TypeJournal Articles
Year of Publication1986
AuthorsO'Leary DP, Stewart G.W
JournalLinear Algebra and its Applications
Pagination275 - 299
Date Published1986/05//
ISBN Number0024-3795

We consider the problem of factoring a dense n×n matrix on a network consisting of P MIMD processors, with no shared memory, when the network is smaller than the number of elements in the matrix (P<n2). The specific example analyzed is a computational network that arises in computing the LU, QR, or Cholesky factorizations. We prove that if the nodes of the network are evenly distributed among processors and if computations are scheduled by a round-robin or a least-recently-executed scheduling algorithm, then optimal order of speedup is achieved. However, such speedup is not necessarily achieved for other scheduling algorithms or if the computation for the nodes is inappropriately split across processors, and we give examples of these phenomena. Lower bounds on execution time for the algorithm are established for two important node-assignment strategies.