Synthesis of custom interleaved memory systems

This paper presents a novel approach to the synthesis of interleaved memory systems that is especially suited for application-specific processors. Our synthesis system generates the optimized interleaved memories for a specif ic algorithm and finds the best mapping of arrays in that algorithm onto th e memory system to achieve high performance. The design space is four-dimen sional (4-D) and comprises the number of memory banks, the type of memory c omponents, the storage scheme, and the range of clock period in the system. Optimal designs are found among the Pareto points (a set of nondominated p oints in the design space) computed for our memory model under the performa nce and cost criteria set by the designer. The memory model includes all th e components of an interleaved memory system and covers a lookup table-base d address generation with data alignment. The synthesis is based on a gener al periodic storage scheme, which enables efficient handling of irregular a nd overlapped access patterns. The synthesis process is the exhaustive sear ch of the heavily pruned design space. and the pruning is based on mathemat ically proven properties of periodic storage schemes. This paper presents t he theorems, the synthesis algorithm, and the methods of effective word and bank address generation. Examples are given to illustrate the effectivenes s of our method.