Name
Title | ||
|---|---|---|
Optimizing the parallel computation of linear recurrences using compact matrix representations |
Abstract | ||
|---|---|---|
This paper presents a novel method for optimizing the parallel computation of linear recurrences. Our method can help reduce the resource requirements for both memory and computation. A unique feature of our technique is its formulation of linear recurrences as matrix computations, before exploiting their mathematical properties for more compact representations. Based on a general notion of closure for matrix multiplication, we present two classes of matrices that have compact representations. These classes are permutation matrices and matrices whose elements are linearly related to each other. To validate the proposed method, we experiment with solving recurrences whose matrices have compact representations using CUDA on nVidia GeForce 8800 GTX GPU. The advantages of our technique are that it enables the computation of larger recurrences in parallel and it provides good speedups of up to eleven times over the un-optimized parallel computations. Also, the memory usage can be as much as nine times lower than that of the un-optimized parallel computations. Our result confirms a promising approach for the adoption of more advanced parallelization techniques. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.jpdc.2009.01.004 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
matrix multiplication,memory usage,linear recurrence,compact representation,parallel computation,matrix computation,recursion,novel method,compact matrix representation,programmable graphics hardware,advanced parallelization technique,memory optimization,un-optimized parallel computation,parallel computer,matrix representation | Matrix calculus,CUDA,Matrix (mathematics),Parallel algorithm,Computer science,Parallel computing,Permutation,Permutation matrix,Matrix multiplication,Computation | Journal |
Volume | Issue | ISSN |
69 | 4 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
2 | 0.42 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adrian Nistor | 1 | 174 | 5.85 |
| Wei-Ngan Chin | 2 | 868 | 63.37 |
| Tiow-Seng Tan | 3 | 398 | 27.99 |
| Nicolae Tapus | 4 | 84 | 34.55 |