Refine
Year of publication
Document Type
- In Proceedings (151)
- Article (123)
- ZIB-Report (30)
- Book chapter (15)
- Other (14)
- In Collection (9)
- Book (3)
- Poster (3)
Keywords
- DVR (2)
- 3D neural network (1)
- Cultural Heritage (1)
- DNA (1)
- Dense connectome (1)
- GPU acceleration (1)
- Gaussian Process (1)
- HCI (1)
- Interaction Techniques (1)
- Kendall (1)
Institute
- Visual Data Analysis (348) (remove)
Efficient implementations of irregular problems on vector and parallel architectures are generally hard to realize. An important class of problems are Gauß-Seidel iteration schemes applied to irregular data sets. The unstructured data dependences arising there prevent restructuring compilers from generating efficient code for vector or parallel machines. It is shown, how to structure the data dependences by decomposing the underlying data set using graph coloring techniques and by specifying a particular execution order already on the algorithm level. Methods to master the irregularities originating from different types of tasks are proposed. An application is given and some open issues and future developments are discussed.
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.