Summary form only given. In this paper we extend the method to deal with coarse-grain operations in static scheduled VLIW processors as is introduced by Busa (2000). We allow functional units with a controller that does not traverse its states in a predefined way. This makes it possible to execute a function that contains a conditional construct like an if-statement as a single operation on a functional unit. In this way the performance penalty otherwise caused by branch instructions is reduced. By adding valid input and output signals, the problem is circumvented that during compilation it is, for this type of functional unit, not known when and how many samples will be consumed or produced. We refer to these units as Conditional Input/output Units (CIUs). The operations that are executed on CIUs are called Conditional Input/output Operations (CIOs). The difference with guarded operations is that the production of a result of a CIO depends on the state of the CIU.

Turbo decoding offers outstanding error correcting capabilities, that will be used in wireless applications like the Universal Mobile Telecom Standard (UMTS). However the algorithm is very computational intensive, and therefore an implementation on a general purpose programmable DSP results in a power consumption which reduces the applicability of turbo decoding in hand-held applications. In this paper we present a solution based on a layered processing architecture. This architecture includes an application specific Very Long Instruction Word (VLIW) processor, a data flow processor, and hard-wired execution units in a hierarchical way. The power consumption of this solution is an order of magnitude better than the implementation on a current state of the art, power efficient general purpose DSP.

We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time.

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.>