Show simple item record

Simplifying Polynomial Constraints Over Integers to Make Dependence Analysis More Precise

dc.contributor.authorMaslov, Vadimen_US
dc.contributor.authorPugh, Williamen_US
dc.description.abstractWhy 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.extent226809 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3109.1en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-93-68.1en_US
dc.titleSimplifying Polynomial Constraints Over Integers to Make Dependence Analysis More Preciseen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record