In a study of the Perfect benchmark programs, Rudolf Eigenmann [Eig92] found that current compilers performed poorly (the harmonic mean of the speed-ups on a Ceder multiprocessor was 1.4). Speed-ups with a harmonic mean of 14.2 were obtained by performing manual transformations that required no knowledge of the application domain and that Eigenmann speculates can be automated. This suggests that there is substantial room for improvement in compiler technology for high-performance computers. We will aggressively pursue collaborations involving the use of our techniques in complete systems constructed by other researchers that will be used by scientific programmers. Through this collaboration, we hope to get feedback on how our techniques address the needs of scientific programmers and inspirations for research topics to fulfill unmet needs.
We are currently implementing a general Presburger arithmetic interface to the Omega test. Once this is constructed we will compare our algorithm with Cooper's [Coo72] algorithm and Bledsoe`s Sup-Inf method [Sho77][Ble75], and explore applications of the Omega test in other areas (constraint logic programming, program verification, verification of timing constraints in real-time systems, etc.). We are continuing to explore methods to improve the efficiency of the Omega test and increase its capabilities. One feature we plan to add is the ability to sum a polynomial over a polytope. This can be used to compute the integer volume of a polytope, which can be used to analyze communication costs and parallelism. For example,
We are examining techniques to handling arbitrary control flow and procedure calls within our analysis and transformation framework. Value-based flow dependences are an accurate, minimal description of the communication required in a program. We will examine the use of this information in optimizing communications in distributed memory multicomputers [AL93].
Our unified transformation framework simply reasons about and generates code for transformations. It does not try to determine an ``optimal'' transformation. Since our framework is so flexible, many transformations are possible. We are starting work [KP93a] on techniques to determine which transformations are desirable.
We are exploring issues involved in the implementation of sparse arrays as a high-level abstract data type (ADT). This would make it easier for a compiler (and perhaps other humans) to understand programs and give the compiler a wide range of choices in how to implement the ADT and reorder the program so as to make sparse array operations efficient.