Compiler address transformation for conflict-free access of memories and networks

A method for mapping arrays into parallel memories so that to minimize serialization and network conflicts for lock-step systems will be presented. Each array is associated an arbitrary number of data access patterns that can be identified following compiler data-dependence analysis. Conditions for conflict-free access of parallel memories and network are derived for arbitrary power-of-2 data patterns and arbitrary multistage networks. We propose an efficient heuristic to synthesize combined address transformation (NP-complete) which applies to arbitrary linear patterns, arbitrary multistage networks, and arbitrary number of power-of-2 memories. Our method can be implemented as part of the address transformation (Xor and And) or through compiler emulation. Performance of optimized storage schemes is presented for FFT, arbitrary sets of data patterns, non power-of-2 stride access in vector processors, interleaving, and static row-column storages. Our approach is profitable in all the above cases and provides a systematic method for coverting array-memory mapping and network aspects of algorithms from one network topology to another.