Abstract
Algorithms specified for parametrically sized problems are more general purpose and more reusable than algorithms for fixed sized problems. For this reason, there is a need for representing and symbolically analyzing linearly parameterized algorithms. An important class of parallel algorithms can be described as systems of parameterized affine recurrence equations (PARE). In this representation, linearly parameterized polyhedra are used to describe the domains of variables. This paper describes an algorithm which computes the set of parameterized vertices of a polyhedron, given its representation as a system of parameterized inequalities. This provides an important tool for the symbolic analysis of the parameterized domains used to define variables and computation domains in PAREs. A library of operations on parameterized polyhedra based on the Polyhedral Library has been written in C and is freely distributed.
Similar content being viewed by others
REFERENCES
C. Mongenet, Ph. Clauss, and G. R. A. Perrin, Geometrical Coding to Compile Affine Recurrence Equations on Regular Arrays, Fifth Parallel Processing Symp., IPPS'91, Anaheim, California (1991).
S. Rajopadhye, Synthesizing Systolic Arrays with Control Signals from Recurrence Equations, Distributed Computing, 3:88–105 (1989).
V. Van Dongen and P. Quinton, The Mapping of Linear Recurrence Equations on Regular Arrays, Journal of VLSI Signal Processing, 1:95–113 (1989).
V. Loechner and Ph. Clauss, Parametric Analysis of Polyhedral Iteration Spaces, International Conference ASAP'96, Chicago, Illinois, pp. 415–424 (August 1996).
V. Loechner and C. Mongenet, OPERA: A Toolbox for Loop Parallelization, First Int. Workshop on Software Engineering for Parallel and Distributed Systems, PDSE'96, Berlin (March 1996).
Günter Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, No. 152, Springer-Verlag, New York (1995).
A. Schrijver, Theory of Linear and Integer Programming, John Wiley and Sons, New York (1986).
D. Avis and D. Bremner, How Good are Convex Hull Algorithms? 11th Ann. ACM Symp. on Computational Geometry, Vancouver, B. C., pp. 20–26 (June 1995).
D. K. Wilde, A Library for Doing Polyhedral Operations, Master's Thesis, Oregon State University, Corvallis, Oregon (December 1993). Also published in IRISA Technical Report PI 785, Rennes, France (1993).
T. S. Motzkin, H. L. Raiffa, G. Thompson, and R. M. Thrall, The Double Description Method (1953). Republished in Theodore S. Motzkin: Selected Papers, Birkhauser, Boston (1983).
F. Fernández and P. Quinton, Extension of Chernikova's Algorithm for Solving General Mixed Linear Programming Problems, Technical Report 437, IRISA, Rennes (1988).
H. Le Verge, A Note on Chernikova's Algorithm, Technical Report 635, IRISA, Rennes (1992).
A. J. Goldman, Resolution and Separation Theorems for Polyhedral Convex Sets. In H. W. Kuhn and A. W. Tucker (Eds.), Linear Inequalities and Related Systems, Princeton University, New Jersey (1956).
K. Fukuda and V. Rosta, Combinatorial Face Enumeration in Convex Polytopes, Computational Geometry, 4:191–198 (1994).
Paul Feautrier, Some Efficient Solutions to the Affine Scheduling Problem. Part I. One-dimensional time, IJPP 21(5):313–348 (1992).
Paul Feautrier, Some Efficient Solutions to the Affine Scheduling Problem. Part II. Multidimensional Time, IJPP 21(6):389–420 (1992).
P. Feautrier, Parametric Integer Programming, RAIRO Recherche Opérationelle, 22(3): 243–268 (1988).
V. Loechner and C. Mongenet, Solutions to the Communication Minimization Problem for Affine Recurrence Equations, Euro-Par'97, Passau (August 1997).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Loechner, V., Wilde, D.K. Parameterized Polyhedra and Their Vertices. International Journal of Parallel Programming 25, 525–549 (1997). https://doi.org/10.1023/A:1025117523902
Issue Date:
DOI: https://doi.org/10.1023/A:1025117523902