Optimized codes for multi-dimensional problems such as image processing and fluid dynamics often require the problem space to be traversed in a direction not parallel to any of the basis vectors of the space. Affine transformations of the iteration indices are needed for these oblique traversals. This project is implementing affine transformations for loop retiming in code generators, with consideration of the effect of conditional branches. Architectural support for anticipating conditional branches is also being investigated. With extensive undergraduate participation, research is proceeding toward several goals: identification of new high-level language constructs for describing loop retiming; development of supporting hardware features; new techniques for accomodating conditional branches; and development of simulators and other tools for investigating loop transformations.
