Thumbnail
Access Restriction
Open

Author Gautam ♦ Rajopadhye, S.
Source CiteSeerX
Content type Text
Publisher ACM
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Dependence Function ♦ Novel Representation ♦ Polyhedraand Presburger ♦ Hardware Generationand ♦ Context Viz ♦ Closure Property ♦ Automatic Reduction ♦ Required Closure Property ♦ Certain Closure Property ♦ Developed Formalism ♦ Polyhedral Model ♦ Program Verification ♦ Automatic Parallelization ♦ Loop Program ♦ General Class ♦ Z-polyhedral Model ♦ Asymptotic Program Complexity
Description The polyhedral model is a well developed formalism and has been extensively used in a variety of contexts viz. the automatic parallelization of loop programs, program verification, locality, hardware generationand more recently, in the automatic reduction of asymptotic program complexity. Such analyses and transformations rely on certain closure properties. However, the model is limited in expressivity and the need for a more general class of programs is widely known. We provide the extension to ⁰-polyhedra which are the intersection of polyhedra and lattices. We prove the required closure properties using a novel representation and interpretation of ⁰-polyhedra. In addition, we also prove closure in the ⁰-polyhedral model under images by dependence functions---thereby proving that unions of LBLs, widely assumedto be a richer class of sets, is equal to unions of ⁰-polyhedra. Another corollary of this result is the equivalence of the unions of ⁰-polyhedraand Presburger sets. Our representation and closure properties constitute the foundations of the ⁰-polyhedral model. As an example, we presentthe transformation for automatic reduction of complexity in the ⁰-polyhedral model.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2007-01-01
Publisher Institution PRINCIPLES AND PRACTICE OF PARALLEL PROGRAMMING