Beyond shared memory loop parallelism in the polyhedral model
| dc.contributor.author | Yuki, Tomofumi, author | |
| dc.contributor.author | Rajopadhye, Sanjay, advisor | |
| dc.contributor.author | Böhm, Wim, committee member | |
| dc.contributor.author | Strout, Michelle M., committee member | |
| dc.contributor.author | Chong, Edwin, committee member | |
| dc.date.accessioned | 2007-01-03T04:54:56Z | |
| dc.date.available | 2007-01-03T04:54:56Z | |
| dc.date.issued | 2013 | |
| dc.description.abstract | With the introduction of multi-core processors, motivated by power and energy concerns, parallel processing has become main-stream. Parallel programming is much more difficult due to its non-deterministic nature, and because of parallel programming bugs that arise from non-determinacy. One solution is automatic parallelization, where it is entirely up to the compiler to efficiently parallelize sequential programs. However, automatic parallelization is very difficult, and only a handful of successful techniques are available, even after decades of research. Automatic parallelization for distributed memory architectures is even more problematic in that it requires explicit handling of data partitioning and communication. Since data must be partitioned among multiple nodes that do not share memory, the original memory allocation of sequential programs cannot be directly used. One of the main contributions of this dissertation is the development of techniques for generating distributed memory parallel code with parametric tiling. Our approach builds on important contributions to the polyhedral model, a mathematical framework for reasoning about program transformations. We show that many affine control programs can be uniformized only with simple techniques. Being able to assume uniform dependences significantly simplifies distributed memory code generation, and also enables parametric tiling. Our approach implemented in the AlphaZ system, a system for prototyping analyses, transformations, and code generators in the polyhedral model. The key features of AlphaZ are memory re-allocation, and explicit representation of reductions. We evaluate our approach on a collection of polyhedral kernels from the PolyBench suite, and show that our approach scales as well as PLuTo, a state-of-the-art shared memory automatic parallelizer using the polyhedral model. Automatic parallelization is only one approach to dealing with the non-deterministic nature of parallel programming that leaves the difficulty entirely to the compiler. Another approach is to develop novel parallel programming languages. These languages, such as X10, aim to provide highly productive parallel programming environment by including parallelism into the language design. However, even in these languages, parallel bugs remain to be an important issue that hinders programmer productivity. Another contribution of this dissertation is to extend the array dataflow analysis to handle a subset of X10 programs. We apply the result of dataflow analysis to statically guarantee determinism. Providing static guarantees can significantly increase programmer productivity by catching questionable implementations at compile-time, or even while programming. | |
| dc.format.medium | born digital | |
| dc.format.medium | doctoral dissertations | |
| dc.identifier | Yuki_colostate_0053A_11552.pdf | |
| dc.identifier.uri | http://hdl.handle.net/10217/78875 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2000-2019 | |
| dc.rights | Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright. | |
| dc.subject | determinism | |
| dc.subject | distributed memory | |
| dc.subject | polyhedral model | |
| dc.subject | tiling | |
| dc.subject | uniformization | |
| dc.subject | X10 | |
| dc.title | Beyond shared memory loop parallelism in the polyhedral model | |
| dc.type | Text | |
| dcterms.rights.dpla | This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Colorado State University | |
| thesis.degree.level | Doctoral | |
| thesis.degree.name | Doctor of Philosophy (Ph.D.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Yuki_colostate_0053A_11552.pdf
- Size:
- 990.38 KB
- Format:
- Adobe Portable Document Format
- Description: