Parallel Gaussian elimination on an MIMD computer

doi:10.1016/0167-8191(88)90070-1

Parallel Computing

Volume 6, Issue 3, March 1988, Pages 275-296

https://doi.org/10.1016/0167-8191(88)90070-1 Get rights and content

Abstract

This paper introduces a graph-theoretic approach to analyse the performances of several parallel Gaussian-like triangularization algorithms on an MIMD computer. We show that the SAXPY, GAXPY and DOT algorithms of Dongarra, Gustavson and Karp, as well as parallel versions of the LDM^t, LDL^t, Doolittle and Cholesky algorithms, can be classified into four task graph models. We derive new complexity results and compare the asymptotic performances of these parallel versions.

References (17)

M. Cosnard et al.
Résolution parallèle de systèmes linéaires denses par diagonalisation
Bulletin EDF C
(1986)
M. Cosnard et al.
Comparison des méthodes parallèles de diagonalisation pour la résolution de systèmes linéaires denses
C.R. Acad. Sci. Paris Ser. I
(1985)
J.J. Dongarra et al.
Implementing linear algebra algorithms for dense matrices on a vector pipeline machine
SIAM Rev.
(1984)
M.J. Flynn
Very high-speed computing systems
D.D. Gajski et al.
Essential issues in multiprocessors systems
IEEE Comput.
(June 1985)
G.H. Golub et al.
Matrix Computation
(1983)
D. Heller
A survey of parallel algorithms in numerical linear algebra
SIAM Rev.
(1978)

There are more references available in the full text version of this article.

Cited by (86)

An evolutionary fuzzy scheduler for multi-objective resource allocation in fog computing
2021, Future Generation Computer Systems
With rapid development of the Internet of Things (IoT), a vast amount of raw data produced by IoT devices needs to be processed promptly. Compared to cloud computing, fog computing nodes are closer to data resource for decreasing the end-to-end transmission latency. Considering the limited resource of IoT devices, offloading computationally-intensive tasks to the servers with high computing capability is essential in the IoT–fog–cloud system to complete those tasks on time. In this work, we propose a fuzzy logical offloading strategy for IoT applications characterized by uncertain parameters to optimize both agreement index and robustness. A multi-objective Estimation of Distribution Algorithm (EDA) is designed to learn and optimize the fuzzy offloading strategy from a diversity of the applications. The algorithm partitions applications into independent clusters, so that each cluster can be allocated to the corresponding tier for further processing. Thus, system resources are saved by making scheduling decisions in a reduced search space. Simulation studies on benchmark problems and real-world cases are carried out to verify the efficiency of our proposed algorithm. Pareto sets produced by our algorithm outperformed classic heuristic solutions for 88.3% benchmark cases and dominated Pareto sets of two state-of-art multi-objective algorithms for 92.7% and 94.4% cases correspondingly.
Adaptive workflow scheduling in grid computing based on dynamic resource availability
2015, Engineering Science and Technology, an International Journal
Citation Excerpt :
Overall, the results clearly specifies that our proposed algorithm outperforms the other algorithms in all the cases and is the suitable algorithm for workflow scheduling in dynamic grid environment, where the number of resources and load on them are changing dynamically. In this test suit, we generated the task graphs corresponding to real life problems such as Gaussian Elimination (GE) [13] and Fast Fourier Transform (FFT) [12]. The structure of these task graphs is fixed.
Grid computing enables large-scale resource sharing and collaboration for solving advanced science and engineering applications. Central to the grid computing is the scheduling of application tasks to the resources. Various strategies have been proposed, including static and dynamic strategies. The former schedules the tasks to resources before the actual execution time and later schedules them at the time of execution. Static scheduling performs better but it is not suitable for dynamic grid environment. The lack of dedicated resources and variations in their availability at run time has made this scheduling a great challenge. In this study, we proposed the adaptive approach to schedule workflow tasks (dependent tasks) to the dynamic grid resources based on rescheduling method. It deals with the heterogeneous dynamic grid environment, where the availability of computing nodes and links bandwidth fluctuations are inevitable due to existence of local load or load by other users. The proposed adaptive workflow scheduling (AWS) approach involves initial static scheduling, resource monitoring and rescheduling with the aim to achieve the minimum execution time for workflow application. The approach differs from other techniques in literature as it considers the changes in resources (hosts and links) availability and considers the impact of existing load over the grid resources. The simulation results using randomly generated task graphs and task graphs corresponding to real world problems (GE and FFT) demonstrates that the proposed algorithm is able to deal with fluctuations of resource availability and provides overall optimal performance.
A complex structure-preserving algorithm for the full rank decomposition of quaternion matrices and its applications
2022, Numerical Algorithms
A complex structure-preserving algorithm for split quaternion matrix LDU decomposition in split quaternion mechanics
2021, Calcolo
A hybrid list-based task scheduling scheme for heterogeneous computing
2021, Journal of Supercomputing
A makespan lower bound for the tiled cholesky factorization based on ALAP schedule
2020, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

View all citing articles on Scopus

^☆: This work has been supported by the Centre National de la Recherche Scientifique through the GRECO C3.

View full text

Parallel Gaussian elimination on an MIMD computer☆

Abstract

Résolution parallèle de systèmes linéaires denses par diagonalisation

Bulletin EDF C

Comparison des méthodes parallèles de diagonalisation pour la résolution de systèmes linéaires denses

C.R. Acad. Sci. Paris Ser. I

Implementing linear algebra algorithms for dense matrices on a vector pipeline machine

SIAM Rev.

Very high-speed computing systems

Essential issues in multiprocessors systems

IEEE Comput.

Matrix Computation

A survey of parallel algorithms in numerical linear algebra

SIAM Rev.