Title :
Alphabets: An Extended Polyhedral Equational Language
Author :
Rajopadhye, S. ; Gupta, G. ; Kim, D-G
Author_Institution :
Comput. Sci. Dept., Colorado State Univ., Fort Collins, CO, USA
Abstract :
The polyhedral model is a formalism for reasoning about an important class of compute- and data-intensive kernels in many programs. We extend the model to include (i) while loops, and (ii) nonaffine dependence functions, together with additional reduction-like operators like argmin and k-argmin. We propose a equational language Alphabets, that extends an earlier language Alpha. We prove its closure properties under program transformations, discuss its denotational semantics, and provide operational semantics in the form of a demand-driven code generator. Our work focuses on expressibility, and complements most previous efforts to extend the polyhedral model that address legality of transformations, techniques to choose them to optimize particular criteria, and the dependence analysis needed to bring a program into an extended model.
Keywords :
formal verification; operating system kernels; program compilers; programming language semantics; reasoning about programs; Alpha language; Alphabets language; argmin operator; compute-intensive kernels; data-intensive kernels; demand-driven code generator; denotational semantics; k-argmin operator; language closure property; operational semantics; polyhedral equational language; polyhedral model; program transformation; Computational modeling; Context; Equations; Indexes; Mathematical model; Semantics; Solid modeling;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.206