We present a two-stage solution approach to the multidimensional periodic scheduling (MPS) problem. This problem originates from the design of high-throughput digital-signal-processor systems, where highly parallel execution of loops is of utmost importance. We introduce the concept of multidimensional periodic operations in order to cope with problems originating from loop hierarchies and explicit timing requirements. In the first stage of the approach, we assign periods to the multidimensional periodic operations such that storage costs are minimized. This is done by means of branch-and-bound, based on a linear programming and constraint-generation technique. In the second stage, we assign start times to the operations and determine on which processing units (PUs) they are executed. This is done by means of an iterative approach. The two major subproblems of MPS concerning checking data dependency constraints and PU constraints are solved by means of an all-integer integer-linear-programming technique. This technique is used as a subroutine in the above two stages. The effectiveness and efficiency of the approach are good, which is illustrated by means of some practical examples.

This tutorial surveys the present and future of multimedia computing systems and outlines new challenges for CAD presented by these systems. Multimedia computing is a challenging domain for several reasons: it requires both high computation rates and memory bandwidth; it is a multirate computing problem; and requires low-cost implementations for high-volume markets. As a result, the design of multimedia computing systems introduces new challenges for CAD at all levels of abstraction, ranging from layout to system design. After surveying the nature of the multimedia computing problem, we examine two experiences in multimedia computer design from a CAD perspective: the design of VLSI systems-on-chips for multimedia: and the successive refinement of an application from software to a high-volume chip using advanced CAD synthesis tools.

This paper discusses improved force-directed scheduling and its application in the design of high-throughput DSP systems, such as real-time video VLSL circuits. We present a mathematical justification of the technique of force-directed scheduling, introduced by Paulin and Knight (1989), and we show how the algorithm can be used to find cost-effective time assignments and resource allocations, allowing trade-offs between processing units and memories. Furthermore, we present modifications that improve the effectiveness and the efficiency of the algorithm. The significance of the improvements is illustrated by an empirical performance analysis based on a number of problem instances.>

A multiport memory allocation problem for hierarchical, i.e. multi-dimensional, data streams is described. Memory allocation techniques are used in high level synthesis for foreground and background memory allocation, the design of data format converters, and the design of synchronous inter-processor communication hardware. The techniques presented in this paper differ from other approaches in the sense that data streams are considered to be design entities and are not expanded to individual samples. A formal model for hierarchical data streams is given and a memory allocation algorithm is presented. The algorithm comprises two steps: data routing and assignment of signal delays to memories. A number of sub-problems are formulated as ILP programs. In the presented form, the allocation algorithm only considers interconnect costs, but memory size and other cost factors can be taken into account. The presented work is implemented in the memory allocation tool MEDEA which is part of the PHIDEO synthesis system.

Force-directed scheduling is a technique which schedules operations under time constraints in order to achieve schedules with a minimum number of resources. The worst case time complexity of the algorithm is cubic in the number of operations. This is due to the computation of the changes in the distribution functions needed for the force calculations. An incremental way to compute the changes in the distribution functions, based on gradual time-frame reduction, is presented. This reduces the time complexity of the algorithm to quadratic in the number of operations, without any loss in effectiveness or generality of the algorithm. Implementations show a substantial CPU-time reduction of force-directed scheduling, which is illustrated by means of some industrially relevant examples.>

Functions executed by a multifunctional processing unit (PU) correspond to clusters of operations in the specification, which are represented as signal flow graphs (SFGs). Because of high-throughput demands, the operations of each SFG are executed in parallel. Since operations for only one of the SFGs are executed at a given time, operations belonging to different SFGs can be executed on the same operator. Here, the most important part of the mapping of several SFGs onto one PU, which is the assignment of the SFGs operations to the PU's operators, given a number of allocated operators, is considered. The problem is to find an operator assignment that minimizes the silicon area that is occupied by the PU's interconnection consisting of multiplexers and wires. An approach based on local search algorithms such as iterative improvement and simulated annealing is presented. Although these algorithms are known to be generally applicable, it is shown that detailed knowledge of the operator assignment problem is required to obtain good results within acceptable CPU time limits for large problem instances.>