Embedded processors in electronic systems typically are tuned to a few applications. Development of processor-specific compilers is prohibitively expensive and, as a result, such compilers, if existing, yield code of an unacceptable quality. To improve this code quality, we developed a processor model that captures the connectivity, the parallelism, and all architectural peculiarities of an embedded processor. We also implemented a retargetable and optimizing compiler working on this model. We present the graph-based processor model, and formally define the code generation task as binding the intermediate representation of an application to this model. We also present a new method for code selection, based on this processor model, that is capable of handling directed acyclic graphs instead of trees.

The increasing use of embedded software, often implemented on a core processor in a single-chip system, is a clear trend in the telecommunications, multimedia, and consumer electronics industries. A companion paper (Paulin et al., 1997) presents a survey of application and architecture trends for embedded systems in these growth markets. However, the lack of suitable design technology remains a significant obstacle in the development of such systems. One of the key requirements is more efficient software compilation technology. Especially in the case of fixed-point digital signal processor (DSP) cores, it is often cited that commercially available compilers are unable to take full advantage of the architectural features of the processor. Moreover, due to the shorter lifetimes and the architectural specialization of many processor cores, processor designers are often compelled to neglect the issue of compiler support. This situation has resulted in an increased research activity in the area of design tool support for embedded processors. This paper discusses design technology issues for embedded systems using processor cores, with a focus on software compilation tools. Architectural characteristics of contemporary processor cores are reviewed and tool requirements are formulated. This is followed by a comprehensive survey of both existing and new software compilation techniques that are considered important in the context of embedded processors.

We present an extensive survey of trends in embedded processor use with an emphasis on emerging applications in wireless communication, multimedia, and general telecommunications. We demonstrate the importance of application-specific instruction-set processors (ASIPs) in high-volume, low cost applications. We also examine some of the underlying trends of the applications in which embedded processors are used. This is followed by a description of embedded software development tool requirements. High-performance software compilation emerges as a key requirement. Finally, specific industrial case studies of products in MPEG, videophone, and low-cost digital signal processor (DSP) applications are used to illustrate the architecture design tradeoffs, and highlight specific tool requirements. A companion paper (Goosens et al., 1997) presents a comprehensive survey of embedded software development tools, focusing mostly on retargetable software compilation.

Real-time DSP applications require a bit-true synthesis system to generate correct and efficient ASICs. This requires concise simulation and synthesis models, which are presented in this paper and exemplified for a non-restoring division operation. Such models are used in the synthesis library of bit-true Cathedral-II compiler, by which industrial size applications have been synthesised.>

A constraint satisfaction framework is proposed that can guarantee necessary and sufficient conditions for a state graph assignment to result in a transformed state graph that is race-free. Performing transformations at the state graph level has the advantage that the requirements imposed on the initial signal transition graph (STG) are very weak. Unlike previous methods, the initial STG need not be a live, safe, free choice net. The only requirement is that the corresponding initial state graph should be finite and connected, and have a consistent state assignment. Hence, a very broad range of STGs can be synthesized. The transformation achievable using the proposed framework correspond to very complex transformations on STGs. Even transformations that convert a free choice net into a correct non-free choice net, and a 1-safe net into a correct 2-safe net are feasible. Addition of transitions that do not follow the Petri net firing rule is also possible.>

At the highest abstraction level, the specification of a data path consists of a number of interconnected abstract building blocks and a constraint on the minimal clock frequency. An algorithm which optimally selects hardware blocks for implementing these abstract building blocks is presented. A technique for hierarchical redistribution and insertion of pipeline registers is also presented. Finally, the two optimization tasks are combined. This combination makes the area tradeoff between the cost of additional speedup circuitry and pipeline registers possible. The techniques are based on accurate hierarchical timing models for the hardware blocks. The automation relieves the designer of the numerous, time-consuming critical path verifications and area evaluations that are required to explore the large design space. The implementation of the algorithms has resulted in a CAD tool called HANDEL, embedded in the data-path compiler CHOPIN.>

The proposed synthesis method starts from a graph-theoretic specification called a signal transition graph (STG). A method for transforming a given STG into an STG that satisfies the original timing behavior and that in addition obeys the unique state coding requirement is given. It is shown that in general, many valid solutions to this problem are possible. Therefore, an attempt is made to find a transformed STG that can be realized in a circuit with optimized speed and area.>

A preprocessing technique for scheduling of large hierarchical and conditional DSP (digital signal processing) applications on a multiregister file architecture is described. Its goals are the optimization of the register cost and the reduction of the time complexity of complex techniques. These are both achieved by reducing the operation mobility through hierarchical clustering. The metric used in the clustering process is a multidimensional distance vector, based on a hierarchical and multidimensional extension of the min-flow algorithm. Network models are presented to take loop hierarchy and conditions into account. By scheduling the clusters separately, a large scheduling problem is divided into several smaller scheduling problems, which makes complex, optimal scheduling techniques feasible again for the scheduling of large graphs.>

Synthesis support for the design of asynchronous circuits is crucial. The synthesis method proposed starts from a graph-theoretic specification called a signal transition graph (STG). This work deals with the theoretical foundations of a method to transform a given STG into an STG that satisfies the original timing behavior and that in addition obeys the unique state coding requirement. It is shown that in general, many valid solutions to this problem are possible. The authors find a transformed STG that can be realized in a circuit with optimized speed and area.>

Pipelining and hardware selection are important optimization tasks in the design of high-performance data paths. At the highest abstraction level, the specification of a data path consists of a number of interconnected abstract building blocks and a constraint on the minimal required clock frequency. An algorithm which optimally selects hardware blocks from a library for implementing these abstract building blocks is presented, and a technique for hierarchical redistribution and insertion of pipeline registers is described. Finally, both optimization tasks are combined. This combination makes the area tradeoff between additional speed-up circuitry and pipeline registers possible.>

The state of the art of compiling digital signal processing (DSP) algorithms into silicon is discussed. It is indicated how digital signal processing differs from numerical data processing, including the consequences for the synthesis tools. On the basis of a broad range of DSP applications, four classes of architectures are then distinguished to serve as templates for four different synthesis systems. Although each of these four silicon compilers is tuned to a specific class of applications in order to generate area-efficient chips, they all accept as input the same behavioral DSP specification. The four selected architectural styles are best characterized by hard-wired bit-serial data-paths, microcoded multiprocessors, cooperating bit-parallel data-paths, and regular arrays. The characteristics of the first three architectures are treated in more detail in a discussion of three different Cathedral synthesis environments for their respective design. A fourth Cathedral environment, aiming at the synthesis of regular arrays, is still in an early stage of development and is not discussed. The claims for the compilers are substantiated by typical designs.>

A computer program for microcode compilation for custom digital signal processors is presented. This tool is part of the CATHEDRAL II silicon compiler. The following optimization problems are highlighted: scheduling, hardware assignment, and loop folding. Efficient techniques to solve these problems are developed. This allows for the automatic synthesis of processor architectures which simultaneously exploit pipelining and parallelism. A demonstrator design is presented.>

In this paper, we discuss a control-flow transformation called loop folding, during the scheduling of register-transfer code for DSP-systems. Loop folding is functionally equivalent to data-path pipelining. An iterative loop-folding procedure, implemented in the CATHEDRAL II compiler, is presented. This technique may significantly improve the utilization of parallel hardware, available in a data path.

CAD tools to support a top-down custom design methodology for integrated digital filters are presented. The methodology is based on a tool-box concept, which makes use of specialised analysis, synthesis and optimization programs at each design level: the network, the architecture and the circuit layout. In this paper, CAD tools for filter synthesis, network optimization and architecture optimization are developed. These tools complement design aids for architecture synthesis, and automatic layout generation (silicon compilers) to create a complete design environment. By combining both synthesis as well as optimization aids at each design level, it is possible to achieve complete automation while retaining efficient use of silicon area, speed and power consumption. Application of these tools to the custom integration of wave digital filters with bit-serial architectures is demonstrated.