| Successful program optimization requires analysis of profitability. From this analysis, a compiler or runtime system can decide where and how to apply an assortment of program transformations. This two-faced problem is called transformation guidance [110, 100, 11, 63, 108]. We consider the desired goal of robust guidance of performance optimizations for hierarchical systems.; A guidance system is robust if it unifies disparate sources of knowledge, and makes reasonable decisions hold up, despite a lack of definitive information. In particular, we seek to address concerns presented by aspects of syntax, architecture, and data set. Syntax may not be statically analyzable; for example, the data dependences due to A(B(i)) (an indirect memory reference) cannot be determined until runtime. Architecture poses a problem in the complexity of the relationship between its properties and performance. Data set shares both problems: on the one hand, we cannot analyze properties of unavailable data; and yet, once available, we cannot easily predict how its properties, combined with architectural properties, influence execution time.; This thesis solves aspects of this robust guidance problem. First, we present bucket tiling, a program transformation for locality which handles non-affine array references (such as the indirect which reference mentioned above). Bucket tiling improves the performance of codes such as conjugate gradient and integer sort by 1.5 to 2.8 times. We have developed a tool which automatically applies bucket tiling to C or Fortran codes.; To guide locality optimizations such as bucket tiling in a robust manner models. A modal model recognizes, and leverages off the following observation: many aspects of a program's behavior can be assigned to a small, finite number of distinguishable categories. We develop a modal model for guiding locality transformations which uses three parameterized modes to represent three different access patterns. We show how to experimentally determine parameterized formulas for execution time of these modes on any given target platform. Further, we use these modes as the basis for a calculus of performance modeling for our guidance system. Given any program, represented as a tree of modes, we show how to determine an execution time formula for the program. For bucket tiling, we determine execution time formulas for the original and transformed programs, and use these to guide the decision on performing the transformation.; We also contrast a modal modeling approach to a static- combinatoric approach. Such an approach models by counting some observable property of behavior, such as cache misses. This contrast highlights the principle advantage of modal modeling: robustness to syntax, architecture, and data set properties. |
