Simplifying Polynomial Constraints Over Integers to Make Dependence Analysis More Precise
| dc.contributor.author | Maslov, Vadim | en_US |
| dc.contributor.author | Pugh, William | en_US |
| dc.date.accessioned | 2004-05-31T22:23:32Z | |
| dc.date.available | 2004-05-31T22:23:32Z | |
| dc.date.created | 1994-02 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | Why do existing parallelizing compilers and environments fail to parallelize many realistic FORTRAN programs? One of the reasons is that these programs contain a number of linearized array references, such as {\tt A(M*N*i+N*j+k)} or {\tt A(i*(i+1)/2+j)}. Performing exact dependence analysis for these references requires testing polynomial constraints for integer solutions. Most existing dependence analysis systems, however, restrict themselves to solving affine constraints only, so they have to make worst-case assumptions whenever they encounter a polynomial constraint. In this paper we introduce an algorithm which exactly and efficiently solves a class of polynomial constraints which arise in dependence testing. Another important application of our algorithm is to generate code for loop transformation known as symbolic blocking (tiling). (Also cross-referenced as UMIACS-TR-93-68.1) | en_US |
| dc.format.extent | 226809 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/589 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3109.1 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-93-68.1 | en_US |
| dc.title | Simplifying Polynomial Constraints Over Integers to Make Dependence Analysis More Precise | en_US |
| dc.type | Technical Report | en_US |