The PolyViz Viewer displaying three polyhedra.

“PolyViz is a tool for visualizing n-dimensional polyhedra. Motivated by the difficulty of reasoning about the iteration spaces of nested loops with many levels, PolyViz allows users to visualize polyhedral representations of those iteration spaces.”

- PolyViz Sourceforge project description

I started writing PolyViz for an advanced high performance computing (HPC) course last spring (early 2010). The course focused on the polyhedral model, a way of thinking about tightly nested loops in computer programs as geometric shapes. In the polyhedral model, each loop has an index variable, like in a standard for loop, such as i, j or k. Each index variable iterates over a range of values, this set of values is called its domain. Each index variable is interpreted as a dimension of the polyhedron. Values that are included in the domain are within the polyhedron, all other values are not.

PolyViz on Sourceforge – See the files section to download source packages or the manual, which is very good and covers background materials and the mathematics involved, along with instructions on how to use the software.

For simple loops this usually results in some manner of rectangular shape (though it may be 3, 4 or higher dimensional depending on how deep the loop nest goes). However, for loops with more complex domains, the polyhedrons become more complex themselves.

The polyhedral model shows its worth when one tries to optimise a loop nest. There are many program transformations that may improve the performance of a loop nest, such as shifting the order of loops or skewing the loop in some way. These transformations are especially important when trying to parallelize a loop nest. Traditionally, these transformations are applied manually to the loop code by skilled programmers. In the polyhedral model, many of these transformations can be expressed as functions that can be applied to the polyhedral domain to arrive at the modified program. Of course, the program must be translated into and out of the polyhedral model in order to leverage this mathematical elegance.

This is where PolyViz can help. It can be very difficult, even for experts, to look at loop bounds in a nest of for loops and imagine the shape of the implied polyhedral iteration space. However, it is necessary to do this in order to reason about the effects of program transformations on important program attributes like data dependencies.

PolyViz allows programmers to type in the bounds of a polyhedron, in the form of a series of inequalities, and instantly view a model of the polyhedron. If the polyhedron is high dimensional (more than 3 dimensions), the user chooses which dimensions he or she would like to view directly and which will be parameterized. Parameterized dimensions are fixed at a given value. The result is essentially a rendering of a 3 dimensional slice of a higher dimensional object. See the manual for a great analogy (involving a koosh ball) that explains this concept.

Jon Roelofs and I co-wrote the PolyViz library software as part of the HPC course. I wrote the PolyViz Viewer GUI application last summer for Prof. Sanjay Rajopadhye with the support of the National Science Foundation.

PolyViz uses Ogre, an exceptional open source real-time 3D graphics engine, to provide visualizations. The PolyViz Viewer uses wxWidgets to provide a native GUI experience on OS X, Windows and Linux (GTK).

Tags: 3D Graphics, HPC, Ogre, Polyhedral Model, PolyViz, Visualization, wxWidgets

This entry was posted on Monday, January 24th, 2011 at 4:19 pm and is filed under Research. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.