| In this thesis, we consider the parallelization problem. Given a sequential algorithm and a target architecture, how can the sequential algorithm be converted into a parallel algorithm suitable for the target architecture? The parallel algorithm must be correct and produce the same results as the sequential one. It must also utilize the resources of the target architecture efficiently.;The parallelization problem can be divided into three main stages: identification of parallelism which includes dependency analysis, partitioning the statements into atomic tasks of granularity suitable to the target architecture and scheduling these tasks into the processors.;The identification of parallelism is independent of the target architecture while the partitioning and scheduling stages are very dependent on it. For example, the partitioning for a machine with many small processors is very different than the partitioning for a machine with a few large ones. It is well known that the problems arising in the partitioning and scheduling stages are NP-complete.;The thesis shows that for some algorithms arising in linear algebra, simple heuristics are sufficient to produce good solutions to the partitioning and scheduling problems. We consider the Gaussian elimination and Gauss-Jordan algorithms for general dense matrices and the Cholesky decomposition algorithms for symmetric positive definite matrices. In addition we study algorithms for the solution of simultaneous triangular systems with the same coefficient matrix and different right hand sides and for the solution of the triangular Sylvester equation.;Most of the results in this thesis are related to the more difficult problems of partitioning and scheduling for message passing architectures. We analyze existing, well- known schedulings, introduce a methodology to estimate their parallel times, study their strengths and weaknesses and propose N-cp/misf, a new class of scheduling methods which are faster and more general than those previously used.;It is shown that for the problem of matrix inversion, GJ is a faster algorithm than GE both for message passing and vectorized architectures. The parallel programs have been implemented on an NCUBE hypercube and they are correct and efficient. Further, the experimental parallel run times agree with the theory. |
