Title | ||
---|---|---|
Scalable techniques for computing band linear recurrences on massively parallel and vector supercomputers |
Abstract | ||
---|---|---|
Presents a new scalable algorithm, called the `regular schedule', for parallel evaluation of band linear recurrences (BLRs), i.e. mth-order linear recurrences for m>1. Its scalability and simplicity make it well suited for vector supercomputers and massively parallel computers. We describe our implementation of the regular schedule on two types of machines: the Convex C240 and the MasPar MP-2. The scalability of our scheduling techniques is demonstrated on the two machines. Significant improvements in CPU performance for a range of programs containing BLRs implemented using the regular schedule in C over the same programs implemented using the highly-optimized coded-in-assembly BLAS routines are demonstrated on the Convex C240. We also demonstrate the scalability of this schedule on the MasPar MP-2 with up to 2000 processors. Our approach can be used both at the user level, in parallel programming code containing BLRs, and in compiler parallelization of such programs combined with recurrence recognition techniques for massively parallel and vector supercomputers |
Year | DOI | Venue |
---|---|---|
1994 | 10.1109/IPPS.1994.288256 | IPPS |
Keywords | Field | DocType |
scalable algorithm,parallel evaluation,maspar mp-2,scheduling,parallel programming,user level,basic linear algebra subroutines,cpu performance,massively parallel computers,computing band linear recurrences,linear algebra,c implementation,vector processor systems,recurrence recognition techniques,mathematics computing,scalability,parallel algorithms,compiler parallelization,band linear recurrences,scheduling techniques,convex c240,regular schedule,performance evaluation,scalable techniques,parallel programming code,vector supercomputers,parallel machines,subroutines,highly-optimized coded-in-assembly blas routines,concurrent computing,vectors,linear systems | Linear algebra,Computer performance,Subroutine,Parallel algorithm,Massively parallel,Scheduling (computing),Computer science,Parallel computing,Compiler,Scalability | Conference |
Citations | PageRank | References |
2 | 0.40 | 12 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Haigeng Wang | 1 | 68 | 7.39 |
Alexandru Nicolau | 2 | 2265 | 307.74 |
Stephen Keung | 3 | 29 | 2.29 |
Kai-Yeung Sunny Siu | 4 | 996 | 110.51 |