On the Inpact of Communication Latencies on Distributed Sparse LU Factorization.

Please always quote using this URN: urn:nbn:de:0297-zib-1245
  • Sparse LU factorization offers some potential for parallelism, but at a level of very fine granularity. However, most current distributed memory MIMD architectures have too high communication latencies for exploiting all parallelism available. To cope with this, latencies must be avoided by coarsening the granularity and by message fusion. However, both techniques limit the concurrency, thereby reducing the scalability. In this paper, an implementation of a parallel LU decomposition algorithm for linear programming bases is presented for distributed memory parallel computers with noticable communication latencies. Several design decisions due to latencies, including data distribution and load balancing techniques, are discussed. An approximate performance model is set up for the algorithm, which allows to quantify the impact of latencies on its performance. Finally, experimental results for an Intel iPSC/860 parallel computer are reported and discussed.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Martin Grammel, Hans-Christian Hege, Roland Wunderling
Document Type:ZIB-Report
Date of first Publication:1993/11/30
Series (Serial Number):ZIB-Report (SC-93-28)