Generating high quality code for embedded processors is made difficult by irregular architectures and highly encoded parallel instructions. Rather than dealing with the target machine at every stage of the compilation, a promising new methodology employs generic algorithms to optimize code for an idealized abstraction of the true target machine. This code, called reference code, is then mapped to the real instruction set by enhanced genetic algorithms. One perturbs the original schedule to find a number of alternative (parallel) instruction sequences, and the other evolves feasible register assignments, if possible, for each sequence. This paper describes the strategy for mapping idealized code into actual code. The COGEN(T) system employs this methodology to produce good code for different commercial DSPs and ASIPs.

Generating high quality code for embedded processors is made difficult by irregular architectures and highly encoded parallel instructions. Rather than deal with the target machine at every stage of the compilation, a promising new methodology employs generic algorithms to optimize code for an idealized abstraction of the true target machine. This code, called reference code, is then mapped to the real instruction set by enhanced genetic algorithms. One perturbs the original schedule to find a number of alternative (parallel) instruction sequences, and the other evolves feasible register assignments, if possible, for each sequence. This paper describes the strategy for mapping idealized code into actual code. The COGEN(T) system employs this methodology to produce good code for different commercial DSPs and ASIPs.

This paper presents a novel approach to the concurrent solution of three High-Level Synthesis (HLS) problems that are modeled as a Constraint-Satisfaction Problem (CSP) and solved using an Enhanced Genetic Algorithm (EGA). We focus on the core problems of high-level synthesis: Scheduling, Allocation, and Binding. Scheduling consists of assigning of operations in a Data-Flow Graph (DFG) to control steps or clock cycles. Allocation selects specific numbers and types of functional units from a hardware library to perform the operations specified in the DFG. Binding assigns constituent operations of the DFG to specific unit instances. A very general version of this problem is considered where functional units may perform different operations in different numbers of control steps. The EGA is designed to solve CSPs quickly and does not require a user to specify appropriate mutation and crossover rates a priori; these are determined automatically during the course of the genetic search. The enhancements include a directed mutation operator and a new type of elitism that avoids premature convergence. The HLS problems are solved by applying two EGAs in a hierarchical manner. The first performs allocation, while the second performs scheduling and binding and serves as the fitness function for the second. When compared to other, well-known techniques, our results show a reduction in time to obtain optimal solutions for standard benchmarks.

Presents a novel approach to the high-level synthesis problems of scheduling, allocation, and binding for multiblock behavioral descriptions. Our design tool, JOSHUA, uses an integer linear programming (ILP) formulation to solve the three interdependent subproblems simultaneously and optimally. The system allows the designer to minimize time, area, and the number of microwords for the entire design, or for specific segments of the design. A diverse module library provides a selection of modules that can perform a specific operation in differing amounts of time (control steps). A novel feature is the ability to select an implementation for part of an algorithm from among a set of implementation alternatives. The system can also handle the issues of path frequencies, loops, parallel threads of execution, and register allocation.>

The problem of minimizing interconnection complexity in behavioral level synthesis is considered. In particular, it is assumed that logical connection requirements have already been determined, with a corresponding level of multiplexing implied. The total amount of multiplexing is further reduced by combining connections onto shared path segments, when possible. Using the number of equivalent 2*1 multiplexers as the measure of interconnection complexity, the optimum solution to this problem can be guaranteed. The solution technique uses integer linear programming, preceded by a process that reduces the problem space without compromising optimality. It is shown how to minimize the total number of tristate buffers in a bus implementation.>

The authors address the issue of area-time trade off in VLSI circuits using the BILBO methodology of BIST. The issue has been dealt with in an integrated manner. Two distinct approaches, integer linear programming and graph theoretic have been presented.>

When BILBO tests are being generated and scheduled, resource conflicts between I-paths and tests present many difficulties. The authors explore: how pipelining is limited by potential internal conflicts; ways to promote pipelining during test plan generation and how to incorporate a test into a test phase already containing tests that conflict with it. They do not directly address the general problems of test plan generation or test scheduling. What is offered is insight into the difficulties that (potential) conflicts provide and techniques for handling these difficulties. The insights are primarily theoretical, but the resulting techniques could be viewed as possible extensions to existing methodologies.>