Modeling multidimensional data and control flow

Abstract

Multidimensional (M-D) signal processing is a key component of most real-time signal and data processing VLSI systems in industry. Handling the M-D nature of data in an efficient way is crucial to arrive at acceptable system implementations. This aspect of design has often been ignored up to now in high-level synthesis. In this paper, a polyhedral based model is presented for the linear, piecewise linear and data dependent signal indexing as occurring in practical M-D signal processing applications. The model features a mathematical description of dependencies between individual operations and signal instances of M-D signals for all algorithms that contain signal indexing specified by a mixture of indexing by iterators and M-D signals embedded in the data flow. The exact modeling of M-D signal indexing is especially essential for deriving alternative control flow structures for a given data flow specification. Exploration of various control flow structures allows one to arrive at an efficient large-scale memory organization during high level synthesis of architectures, both in terms of storage locations and access order.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>