Loading...
Please wait, while we are loading the content...
Similar Documents
Data traffic reduction schemes for cholesky factorization on asynchronous multiprocessor systems
| Content Provider | NASA Technical Reports Server (NTRS) |
|---|---|
| Author | Naik, Vijay K. Patrick, Merrell L. |
| Copyright Year | 1989 |
| Description | Communication requirements of Cholesky factorization of dense and sparse symmetric, positive definite matrices are analyzed. The communication requirement is characterized by the data traffic generated on multiprocessor systems with local and shared memory. Lower bound proofs are given to show that when the load is uniformly distributed the data traffic associated with factoring an n x n dense matrix using n to the alpha power (alpha less than or equal 2) processors is omega(n to the 2 + alpha/2 power). For n x n sparse matrices representing a square root of n x square root of n regular grid graph the data traffic is shown to be omega(n to the 1 + alpha/2 power), alpha less than or equal 1. Partitioning schemes that are variations of block assignment scheme are described and it is shown that the data traffic generated by these schemes are asymptotically optimal. The schemes allow efficient use of up to O(n to the 2nd power) processors in the dense case and up to O(n) processors in the sparse case before the total data traffic reaches the maximum value of O(n to the 3rd power) and O(n to the 3/2 power), respectively. It is shown that the block based partitioning schemes allow a better utilization of the data accessed from shared memory and thus reduce the data traffic than those based on column-wise wrap around assignment schemes. |
| File Size | 1653781 |
| Page Count | 31 |
| File Format | |
| Alternate Webpage(s) | http://archive.org/details/NASA_NTRS_Archive_19890017978 |
| Archival Resource Key | ark:/13960/t4rj9bv4x |
| Language | English |
| Publisher Date | 1989-06-01 |
| Access Restriction | Open |
| Subject Keyword | Mathematical And Computer Sciences (general) Partitions Mathematics Computational Grids Multiprocessing Computers Data Reduction Memory Computers Parallel Processing Computers Cholesky Factorization Matrices Mathematics Ntrs Nasa Technical Reports Server (ntrs) Nasa Technical Reports Server Aerodynamics Aircraft Aerospace Engineering Aerospace Aeronautic Space Science |
| Content Type | Text |
| Resource Type | Technical Report |
