We present the tile-cached kd-tree, an efficient external-memory (disk) implementation of two-dimensional region query for use in a detailed area router. Most researchers have heretofore focused on in-memory algorithms. However as the need to tackle very large problems increases, conventional in-memory algorithms suffer from unpredictable caching and paging behavior and their performance may degrade considerably. In addition, since the region-query data structure is only part of the overall system, its consumption of large memory resources affects other parts of the system as well. Our implementation takes advantage of spatial locality in the detailed-routing process. We partition the routing space into tiles, each storing the data of objects (rectangles) that lie strictly within it. Objects that cross tile boundaries are separately stored. The data within a tile are then written out to disk, and a configurable cache is used to hold in memory the most recently visited tiles. Experimental results on large real-life routing problems show that this scheme significantly reduces memory usage with tolerable performance penalty.

Unate and binate covering problems are a subclass of general integer linear programming problems with which several problems in logic synthesis, such as two-level logic minimization and technology mapping, are formulated. Previous branch-and-bound methods for solving these problems exactly use lower bounding techniques based on finding maximal independent sets. In this paper, we examine lower bounding techniques based on linear programming relaxation (LPR) for the covering problem. We show that a combination of traditional reductions (essentiality and dominance) and incremental computation of LPR-based lower bounds can exactly solve difficult covering problems orders of magnitude faster than traditional methods.

Before attempting to synthesize hardware from a programming language like C or C++, we need to introduce additional semantics to be able to describe hardware behavior accurately. In particular, concurrency, reactivity, communication mechanisms, and event handling semantics need to be added, Also, a synthesizable subset of the language needs to be defined, together with synthesis semantics for programming language constructs. With these enhancements, it is possible to create C/C++ descriptions of hardware at the well-understood RTL and behavioral levels of abstraction, providing an opportunity to leverage existing, mature hardware-synthesis technology that has been developed in the context of HDL based synthesis to create a C/C++ synthesis system. In this paper, we will present some of the key ingredients of a C/C++ synthesis system and elaborate on the challenges of hardware synthesis from C/C++.

We address the problem of code-size minimization in VLSI systems with embedded DSP processors. Reducing code size reduces the production cost of embedded systems we use data-compression methods to develop code-size minimization strategies. In our framework, the compressed program consists of a skeleton and a dictionary. We show that the dictionary can be computed by solving a set-covering problem derived from the original program. To execute the compressed code, we describe two methods that have different performance characteristics and different degrees of freedom in compressing the code. We also address performance considerations, and show that they can be incorporated easily into the set-covering formulation, and present experimental results obtained with Texas Instruments' optimizing TMS3220C25 compiler.

Code-size minimization in embedded systems is an important problem because code size directly affects production cost. We address the problem of code compression in systems with embedded DSP processors. We use data-compression methods to develop code-size minimization strategies. In our framework, the compressed program consists of a skeleton and a dictionary. We show that the dictionary can be computed by solving a set-covering problem derived from the original program. We also address performance considerations, and show that they can be incorporated easily into the set-covering formulation. Experimental results are presented.

We present a new viewpoint on code generation for directed acyclic graphs (DAGs). Our formulation is based on binate covering , the problem of satisfying, with minimum cost, a set of disjunctive clauses, and can take into account commutativity of operators and of the machine model. An important contribution of this work is a set of necessary and sufficient conditions for a valid schedule to be derived, based on the notion of worms and worm-partitions . This set of conditions can be compactly expressed with clauses that relate scheduling to code selection. For the case of one-register machines, we can derive clauses that lead to generation of optimal code for the DAG. Recent advances in exact binate covering algorithms allows us to use this strategy to generate optimal code for large basic blocks. The optimal code generated by our algorithm results in significant reductions in overall code size.

Unate and binate covering problems are a special class ofgeneral integer linear programming problems with which several problemsin logic synthesis, such as two-level logic minimization and technologymapping, are formulated. Previous branch-and-bound methodsfor exactly solving these problems use lower-bounding techniques basedon finding maximal independent sets. In this paper we examine lower-boundingtechniques based on linear programming relaxation (LPR) forthe binate covering problem. We show that a combination of traditionalreductions (essentiality and dominance) and incremental computation ofLPR-based lower bounds can exactly solve difficult covering problemsorders of magnitude faster than traditional methods.

Reactivity is one of the key features of hardware description languages. We present an efficient implementation of reactivity in the Scenic framework that allows the system designer to model hardware blocks. Scenic allows the designer to use C++ to model mixed hardware--software systems with a C++ compiler and a small library and without the need of a complex event-driven run-time kernel often found embedded in hardware description languages (HDL) such as VHDL and Verilog. Moreover, Scenic hardware descriptions can be easily mapped to HDL and synthesized into hardware implementations using commercially available tools. In this paper we present Scenic's implementation of concurrency (signals and processes) and reactivity (waiting and watching). When C++ is used as an HDL, context-switching overhead can become a significant performance issue during simulation. We introduce the notion of delayed expression objects, or lambdas, to reduce context-switching. Examples and experimental results ...

Many application-specific architectures provideindirect addressing modes with auto-increment/decrementarithmetic.Since these architectures generally do not featurean indexed addressing mode, stack-allocated variablesmust be accessed by allocating address registers and performingaddress arithmetic.Subsuming address arithmeticinto auto-increment/decrement arithmetic improves boththe performance and size of the generated code.Our objective in this paper is to provide a method forcomprehensively analyzing the performance benefits andhardware cost due to an auto-increment/decrement featurethat varies from -l to +l, and allowing access to k addressregisters in an address generator.We provide this methodvia a parameterizable optimization algorithm that operateson a procedure-wise basis.Hence, the optimizationtechniques in a compiler can be used not only to generateefficient or compact code, but also to help the designerof a custom DSP architecture make decisions on addressarithmetic featuers.We present two sets of experimental results based onselected benchmark programs: (1) the values of l and kbeyond which there is little or no improvement in performance,and (2) the values of l and k which result in minimumcode area.

We investigate the problem of code generation for DSP systems on a chip. Such systems devote a limited quantity of silicon to program ROM, so application software must be maximally dense. Additionally, the software must be written so as to meet various high-performance constraints, which may include hard real-time constraints. Unfortunately, current compiler technology is unable to generate dense, high-performance code for DSPs, whose architectures are highly irregular. Consequently, designers often resort to programming application software in assembly-a Time-consuming, error-prone, and non-portable task. Thus, DSP compiler technology must be improved substantially. We describe some optimizations that significantly improve the quality of compiler-generated code. Our optimizations are applied globally and even across procedure calls. Additionally, they are applied to the machine-dependent assembly representation of the source program. Our target architecture is the Texas Instruments' TMS320C25 DSP.

DSP architectures typically provide indirect addressing modes with autoincrement and decrement. In addition, indexing mode is generally not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into autoincrement and decrement modes improves the size of the generated code. In this article we present a formulation of the problem of optimal storage assignment such that explicit instructions for address arithmetic are minimized. We prove that for the case of a single address register the decision problem is NP-complete, even for a single basic block. We then generalize the problem to multiple address registers. For both cases heuristic algorithms are given, and experimental results are presented.

We address the problem of code optimization for embedded DSP microprocessors.Such processors (e.g., those in the TMS320 series) have highly irregular datapaths, and conventional code generation methods typically result in inefficient code.In this paper we formulate and solve some optimization problems that arise in code generation for processors with irregular datapaths.In addition to instruction scheduling and register allocation, we also formulate the accumulator spilling and mode selection problems that arise in DSP microprocessors.We present optimal and heuristic algorithms that determine an instruction schedule simultaneously optimizing accumulator spilling and mode selection.Experimental results are presented.

We address the problem of instruction selection in code generation for embedded DSP microprocessors. Such processors have highly irregular data-paths, and conventional code generation methods typically result in inefficient code. Instruction selection can be formulated as directed acyclic graph (DAG) covering. Conventional methods for instruction selection use heuristics that break up the DAG into a forest of trees and then cover them independently. This breakup can result in suboptimal solutions for the original DAG. Alternatively, the DAG covering problem can be formulated as a binate covering problem, and solved exactly or heuristically using branch-and-bound methods. We show that optimal instruction selection on a PAG in the case of accumulator-based architectures requires a partial scheduling of nodes in the DAG, and we augment the binate covering formulation to minimize spills and reloads. We show how the irregular data transfer costs of typical DSP data-paths can be modeled in the binate covering formulation.

DSP architectures typically provide indirect addressing modes with auto-increment and decrement. In addition, indexing mode is not available, and there are usually few, if any, general-purpose registers. Hence, it is necessary to use address registers and perform address arithmetic to access automatic variables. Subsuming the address arithmetic into auto-increment and auto-decrement modes improves the size of the generated code.

We show that the problem of factoring a sum-of-products representation of a logic function can be transformed into one of multiple-valued prime generation followed by branch-and-bound covering. We give a factorization method that generates potential Boolean factors by generating the primes of a multiple-valued function with an associated don't-care set. A covering problem is solved wherein a set of primes with minimal cost is selected to obtain a Boolean factorization. This method can exploit Boolean identifiers in factorization such as a-a = a-a = a. Common factors across a set of Boolean functions can be identified by using multiple-output prime generation and covering. We show how all the kernels of an expression can be generated by generating the primes of a multiple-valued function. A covering step can be used to arrive at an algebraic factorization.

A general strategy for automatically generating and verifying sufficient correctness properties for a broad class of synchronous processors is presented. Given a particular specification and implementation pair, it is shown how basic correctness properties can be algorithmically translated into a set of computation tree logic (CTL) formulae which are sufficient for equivalence between the behavioral and logic descriptions. Preliminary experimental results on the verification of microcoded and array processors are presented.>