The Z-polyhedral model
The Z-polyhedral model
复制标题
Z 多面体模型
DOI：
10.1145/1229428.1229478
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Rajopadhye
中科院分区：
文献类型：
--
作者：
Gautam Gupta;S. Rajopadhye
多面体模型是一种发达的格式化，在各种环境中已广泛使用转换依赖于某些封闭属性，但是，模型的表达性有限，对程序的需求是广泛的。 ⁰-Polyhedra是多面体和晶格的相交，我们使用新的表示和解释了⁰-Polyhedra的闭合性能。因此，规定的LBL工会被广泛认为是富裕的集合，等于⁰-Polyhedra的工会。 ⁰-Polyhedraand Presburger集合我们的表示和闭合性质构成了⁰-Polyhedral模型的基础，我们提出了自动降低⁰-多层模型的复杂性的转换。
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.