A HEURISTIC STORAGE FOR MINIMIZING ACCESS TIME OF ARBITRARY DATA PATTERNS

The serialization of memory accesses is a major limiting factor in hig h performance SIMD computers. The data patterns or templates that are accessed by a program can be perceived by the compiler, and, therefore , the design of dynamic storage schemes that minimize conflicts may dr amatically improve performance. The problem of finding storage schemes that minimize the access time of arbitrary sets of power-of-two data patterns is proved to be NP-complete. We propose linear address transf ormations that can be dynamically applied by each processing element f or mapping array references onto memories. An efficient approach for c ombining the constraints of different access patterns into one single linear address transformation is presented. We prove that finding the transformation that minimizes the access time is reducible to N-colori ng, where N is the number of parallel memories. Using coloring heurist ics, storage schemes are investigated with respect to minimizing the i mplementation cost (perfect storage) and overall access conflicts (sem iperfect storage). Results show that the perfect-storage may deviate o n the average by 20% from the optimum access time in the case of 10 ar bitrary data patterns and 16 memories. However, semiperfect schemes le ad to dramatic reduction of the degree of conflict compared to perfect -schemes. The proposed heuristic storage largely outperforms interleav ing and row-column-diagonals storages. The method can be implemented a s compiler procedure for synthesizing storage schemes that promote par allel access to arbitrary sets of data patterns.