This paper focuses on the resource sharing problem when performing high-level synthesis. It argues that the conventionally accepted synthesis flow when resource sharing is done after scheduling is sub-optimal because it cannot account for timing penalties from resource merging. The paper describes a competitive approach when resource sharing and scheduling are performed simultaneously. It provides a quantitative evaluation of both approaches and shows that performing sharing during scheduling wins over the conventional approach in terms of quality of results.

This paper proposes an enhanced scheduling approach for high-level synthesis, which relies on a multi-cycle behavioral timing analysis step that is performed before and during scheduling. The goal of this analysis is to accurately evaluate the criticality of operations and determine the most suitable candidate resources to implement them. The efficiency of the approach is confirmed by testing it on industrial examples, where it achieves, on average, 9% area savings after logic synthesis.

The state-of-the-art design practice for complex SoCs employs multiple models of hardware components with different use cases. The cost of building and maintaining those models is high, and verifying the consistency among those models is time consuming. This paper highlights needs and issues of creating these models, and presents emerging approaches for developing solutions to address the issues.

This paper describes an approach to pipelining in high-level synthesis that modifies the control/data flow graph before and after scheduling. This enables the direct re-use of a pre-existing, timing- and area-aware non-pipelined simultaneous scheduler and binder. Such an approach ensures that the RTL output can be synthesized within the given timing and area constraints. Results from real industrial designs show the effectiveness of this approach in improving Pareto optimality with respect to area, delay and power.

The widespread acceptance of High-level synthesis as a mainstream tool mostly depends on its tight integration with the following RTL-to-GDSII design flow. A key aspect is the handling of so-called Engineering Change Orders (ECOs), i.e. minor changes required to fix small functional bugs or meet performance requirements late in the design cycle. Traditional high-level synthesis has attempted to optimize at best the output logic. However, in the ECO scenario the goal is to implement the required change with as few modifications as possible to the RTL, logic netlist, placed netlist and layout. In this paper we show how, by judiciously changing the internal databases used by the tool to match as much as possible the original design, one can achieve minimal impact and implement ECOs in truly incremental mode, while full-blow re-synthesis would lead to massive unnecessary downstream changes. The tool essentially matches source constructs between the original and the ECO design, and copies as many synthesis decisions as possible from the original design to the ECO design.

Hardware synthesis is the process by which system-level, Register Transfer (RT)-level, or behavioral descriptions can be turned into real implementations, in terms of logic gates. Scheduling is one of the most time-consuming steps in the overall design flow, and may become much more complex when performing hardware synthesis from high-level specifications. Exploiting a single scheduling strategy on very large designs is often reductive and potentially inadequate. Furthermore, finding the “best” single candidate among all possible scheduling algorithms is practically infeasible. In this article we introduce a hybrid scheduling approach that is a preliminary step towards a comprehensive solution not yet provided by industrial or by academic solutions. Our method relies on an abstract symbolic representation of data flow nodes (operations) bound to control flow paths: it produces a more realistic lower bound during the prescheduling resource estimation step and speeds up slower but accurate heuristic scheduling techniques, thus achieving a globally improved result.

In the design of highly complex, heterogeneous, and concurrent systems, deadlock detection and resolution remains an important issue. In this paper, we systematically analyze the synchronization dependencies in concurrent systems modeled in the Metropolis design environment, where system functions, high level architectures and function-architecture mappings can be modeled and simulated. We propose a data structure called the dynamic synchronization dependency graph, which captures the runtime (blocking) dependencies. A loop-detection algorithm is then used to detect deadlocks and help designers quickly isolate and identify modeling errors that cause the deadlock problems. We demonstrate our approach through a real world design example, which is a complex functional model for video processing and a high level model of function-architecture mapping.

Efficient evaluation of design choices, in terms of selection of algorithms to be implemented as hardware or software, and finding an optimal HW/SW design mix is an important requirement in the design flow of embedded systems. Time-to-market, faster upgradability and flexibility are some of the driving points to put increasing amounts of functionality as software executed on general purpose processing elements. In this scenario, dividing a monolithic task into multiple interacting tasks, and scheduling them on limited processing elements has become very important for a system designer. The paper presents an approach to model time-slice based task schedulers in the designs where the performance estimate of hardware and software models is less than time-slice accurate. The approach aims to increase the simulation efficiency of designs modeled at system level. We used Metropolis (Balarin, F. et al., IEEE Computer, vol.36, no.4, p.45-52, 2003) as our codesign environment.

We describe a system as a set of communicating concurrent programs. Quasi-static scheduling compiles the concurrent programs into a sequential one. It uses a Petri net as an intermediate model of the system. However, Petri nets generated from many interesting applications are not schedulable. In this paper, we show the underlying mechanism which causes unschedulability in terms of the structure of a Petri net. We introduce a Petri net structural property and prove unschedulability if the property holds. We propose a linear programming based algorithm to check the property, and prove the algorithm is valid. Our approach prove unschedulability typically within a second for Petri nets generated from industrial JPEG and MPEG codecs, while the scheduler fails to terminate within 24 hours.

A reactive system must process inputs from the environment at the speed and with the delay dictated by the environment. The synthesis of reactive software from a modular concurrent specification model generates a set of concurrent tasks coordinated by an operating system. This paper presents a synthesis approach for reactive software that is aimed at minimizing the overhead introduced by the operating system and the interaction among the concurrent tasks. A formal model based on Petri nets is used to synthesize the tasks and verify the correctness of their composition. A practical application of the approach is illustrated by means of a real-life industrial example, which shows the significant impact of the approach on the performance of the system.

Noise affects circuit operation by varying circuit delays and causing latches to capture incorrect values. Conventional noise analysis techniques can detect some of such noise faults, but accurate analysis requires a careful examination of timing and functional properties of the circuit. In this paper, a method of characterizing correlation of signal transitions in nets by considering in a unified way both timing and functionality of the signals is proposed. An analysis procedure to eliminate noise faults that cannot actually happen when such correlations are considered is described. The timed-Boolean logic is used to characterize signal transitions in a time interval, and correlations are checked by solving Boolean satisfiability (SAT) between aggressor and victim transitions under the min-max delay model for gates. The method is applicable for checking noise faults at a single net, on a path, or in a cone of logic. The proposed technique is scalable as it keeps the size of Boolean formulation linear to the size of the modeled circuit. It has been applied on a set of large circuits, eliminating up to 50% of noise delay faults reported by a conventional noise-analysis method.

Noise affects circuit operation by increasing gate delays and causing latches to capture incorrect values. Noise analysis techniques can detect some of such noise faults, but accurate analysis requires a careful examination of timing and functional properties of the circuit. This paper proposes a method to check the "true" noise impact on path delay. It uses four-variable Boolean logic to characterize signal transitions in a time interval, and formulates Boolean satisfiability between aggressors and a victim under the min-max delay model for gates. The proposed technique is scalable as it keeps the size of Boolean formulation linear to the size of the modeled circuit. By applying it to a set of large circuits, it has eliminated up to 50% of noise delay faults reported by conventional noise analysis method.

Separating the description of important aspects of a design such as behavior and architecture, or computation and communication, may yield significant advantages in design time as well as in re-usability of the design. However, exploiting fully the re-usability opportunities offered by this approach implies to keep the various aspects of the design separated while verifying the design at a given level of abstraction. In particular, simulation of the design may undergo significant overhead versus a traditional approach where the design is represented and analyzed monolithically. In this paper, we present a few techniques that eliminate almost entirely the overhead while maintaining the positive aspects of the separation of concerns. Experimental results on a complex design back this assertion.

In the era of billion-transistor design, it is critical to establish effective verification methodologies from the system level, all the way down to the implementations. In this paper, we introduce logic of constraints (LOC), a logic that is particularly suited to express quantitative performance constraints as well as functional constraints. We analyze the expressiveness of LOC and show that it is important and different from linear temporal logic, upon which traditional hardware assertion languages (e.g., PSL and OpenVera) are based. We propose an automatic simulation trace checking/runtime monitoring methodology that can be used to verify system designs very efficiently. Since a subset of LOC is decidable, we also discuss the formal verification approach for LOC formulas. Through several industrial case studies, we demonstrate the usefulness of the LOC formalism and the corresponding simulation and verification approach at the higher transaction level of abstraction.

Noise a#ects circuit operation by increasing gate delays and causing latches to capture incorrect values. This paper proposes a method of characterizing correlation of signal transitions in multiple nets by considering both timing and functionality of the signals, and uses it in an analysis procedure to eliminate noise faults that cannot actually happen when such correlations are considered. It uses four-variable Boolean logic to characterize signal transitions in a time interval, and formulates Boolean satisfiability between aggressors and a victim under the min-max delay model for gates. The technique has been successfully applied to commercial ASIC designs and has eliminated up to 35% of delay noise faults reported by a state-of-the-art noise analysis tool.

Verification of system designs continues to be a major challenge today. Simulation remains the primary tool for making sure that implementations perform as they should. We present algorithms to automatically generate trace checkers from formulas written in the formal quantitative constraint language, Logic Of Constraints (LOC), to analyze the simulation traces for functional and performance constraint violations. For many interesting formulas, the checkers exhibit linear time complexity and constant memory usage. We illustrate the usefulness and efficiency of this approach with large designs and traces.

In this paper we describe a technology mapping technique based on the logical effort theory [13]. First, we appropriately characterize a given standard cell library and extract from it a set of cell classes. Each cell-class is assigned a constant-delay model and corresponding load-bounds, which define the conditions of the delay model's validity. Next, we perform technology mapping using the classes determined in the first step. We propose several effective area-optimization heuristics which allow us to apply our algorithm directly to general graphs. Experimental results show that our gain-based mapping algorithm achieves reduced delay with less area, compared to the mapper in SIS [15]. By adjusting the constant delay model associated with each class, we determine the area-delay trade-off curve. We achieve the best area-delay trade-off using a design-specific constant delay models.

We have developed a technique to compute a Quasi Static Schedule of a concurrent specification for the software partition of an embedded system. Previous work did not take into account correlations among run-time values of variables, and therefore tried to find a schedule for all possible outcomes of conditional expressions. This is advantageous on one hand, because by abstracting data values one can find schedules in many cases for an originally undecidable problem. On the other hand it may lead to exploring false paths, i.e., paths that can never happen at run-time due to constraints on how the variables are updated. This affects the applicability of the approach, because it leads to an explosion in the running time and the memory requirements of the compile-time scheduler itself. Even worse, it also leads to an increase in the final code size of the generated software. In this paper we propose a semi-automatic algorithm to solve the problem of false paths: the designer identifies and tags critical expressions, and synchronization channels are automatically added to the specification to drive the search of a schedule.

This paper proposes a procedure for minimizing the code size of sequential programs for reactive systems. It identifies repeated code segments (a generalization of basic blocks to directed rooted trees) and finds a minimal covering of the input control flow graphs with code segments. The segments are disjunct, i.e. no two segments have the same code in common. The program is minimal in the sense that the number of code segments is minimum under the property of disjunction for the given control flow specification. The procedure makes no assumption on the target processor architecture, and is meant to be used between task synthesis algorithms from a concurrent specification and a standard compiler for the target architecture. It is aimed at optimizing the size of very large, automatically generated flat code, and extends dramatically the scope of classical common sub-expression identification techniques. The potential effectiveness of the proposed approach is demonstrated through preliminary experiments.

The problem of optimal software synthesis for concurrent processes to be implemented on a single processor is addressed. The approach calls for the representation of the concurrent processes with Petri nets that give a theoretical foundation for the scheduling algorithm that sequentializes the concurrent processes and for the code generation step. The approach maximizes the amount of static scheduling to reduce the need of context switch and operating system intervention. Experimental results show the potential of our method to reduce software design time and errors.

We present a technology mapping procedure in which an area-delay trade-off curve is constructed at each node using matches found for different decompositions of the node. This information is used effectively to find implementations that meet delay constraints while reducing area. The procedure combines state-of-the-art mapping procedures, in which a graph covering is applied to a special graph structure which succinctly encodes many representations. Major challenges were avoiding memory explosion and finding good cost estimations. The combined procedure outperforms the best result among any of the procedures used separately.

A problem in technology mapping is that the quality of the final implementation depends significantly on the initially provided circuit structure. This problem is critical, especially for mapping with tight and complicated constraints. In this paper, we propose a procedure which takes into account a large number of circuit structures during technology mapping. A set of circuit structures is compactly encoded in a single graph, and the procedure dynamically modifies the set during technology mapping by applying simple local transformations to the graph. State-of-the-art technology mapping algorithms are naturally extended, so that the procedure finds an optimal tree implementation over all of the circuit structures examined. We show that the procedure effectively explores the entire solution space obtained by applying algebraic decomposition exhaustively. However, the run time is proportional to the size of the graph, which is typically logarithmic in the number of circuit structures encoded. The procedure has been implemented and used for commercial design projects, We present experimental results on benchmark examples to demonstrate its effectiveness.

This paper is concerned with logic optimization of multilevel combinational logic circuits. In the light of theoretical work of the past years, where a circuit is modeled by a Boolean network in which each node implements a single-output Boolean function, we address how a concurrent optimization over multiple nodes or components can lead to further optimization compared to conventional minimization techniques. In particular, we provide a procedure for computing maximally compatible sets of permissible relations for multiple nodes. This is a generalization of the classical notion of a compatible set of permissible functions for a single node, where no method is known for correctly computing such a maximal set. We provide a method for computing the set correctly for the general case. Based on this, we develop and implement a procedure for optimizing multiple nodes concurrently. The proposed procedure has been implemented, and we present experimental results.

We present a new delay model for use in logic synthesis. A traditional model treats the area of a library cell as constant and makes the cell's delay a linear function of load. Out model is based on a different, but equally fundamental linearity in the equation relating area, delay, and load: namely, we may keep a cell's delay constantly making its area a linear function of load. This allows us to technology map using a library with continuous device sizing, satisfies certain electrical noise and power constraints, and in certain cases is computationally simpler than a traditional model. We give results to support these claims. A companion paper uses the computational simplicity to explore a wide search space of algebraic factorings in a mapped network.

A problem in technology mapping is that quality of the final implementation depends significantly on the initially provided circuit structure. To resolve this problem, conventional techniques iteratively but separately apply technology independent transformations and technology mapping. In this paper, we propose a procedure which performs logic decomposition and technology mapping simultaneously. We show that the procedure effectively explores all possible algebraic decompositions. It finds an optimal tree implementation over all the circuit structures examined, while the run time is typically logarithmic in the number of decompositions.

This paper is concerned with the problem of optimizing systems of interacting sequential circuit components. Specifically, we consider how one can find the set of sequential behaviors that can be implemented at a component while preserving the behavior of the total system. This paper proposes a method for computing and representing the complete set of permissible behaviors. We show that the complete set can be computed and represented by a single non-deterministic finite state machine, called the E-machine. The transition relation of the E-machine is obtained by a fixed point computation. The procedure has been implemented and initial experimental results are given.

Synchronous Boolean relations can represent sequential don't-care information in synchronous systems. These relations allow greater flexibility in expressing don't-care information than ordinary Boolean relations. Synchronous relations can be used to specify sequential designs at the finite state machine level as well as at the level of combinational elements and latches. The main objective of this paper is to present a heuristic approach to find a minimal implementation for a given synchronous relation. We also show that the synchronous relation formulation can also be used to find a minimal sum-of-products form which implements a function that is compatible with an arbitrary set of Boolean relations.>

This paper is concerned with logic optimization of multi-output gates in multi-level combinational logic circuits. We address how a concurrent minimization over multiple gates can lead to further optimization as compared to conventional single-gate minimization techniques. In particular, we provide a procedure for computing a maximally-compatible set of permissible relations for multiple-output gates. We also propose a heuristic for clustering single-output gates into multi-output gates, so that increased concurrent optimization can be obtained.>

An approach to minimization that is based on a state-of-the-art paradigm for the two-level minimization of functions is presented. Some special properties of relations, in contrast to functions, which must be carefully considered in realizing a high-quality procedure for solving the minimization problem are clarified. An efficient heuristic method to find an optimal sum-of-products representation for a multiple-valued relation is proposed and implemented in the program GYOCRO. It uses multiple-valued decision diagrams (MDDs) to represent the characteristic functions for the relations. Experimental results are presented and compared with previous exact and heuristic Boolean relation minimizers to demonstrate the effectiveness of the proposed method.>

The authors propose a heuristic procedure for the minimization problem of multiple-valued relations based on a paradigm of the more advanced two-level minimization techniques for regular functions. The goal of the procedure is to find a compatible representation with the minimum number of the product terms. The authors present some special properties associated with relations not found in functions. These properties must be carefully accounted for while implementing a procedure that is effective in achieving high quality results. The authors have implemented these algorithms in a program called GYOCRO, and provide experimental evidence of their effectiveness.>

The problem of rectifying design incorrectness due to specification changes as well as design errors of VLSI circuits is formulated and a basic approach using logic synthesis techniques is presented. An efficient approach is presented for rectifying the functional incorrectness by attaching circuitry exterior to the original design. A necessary and sufficient condition for full rectification of the design is provided. It is shown that the proposed approach always succeeds in the rectification of arbitrary combinational circuits. The situation where rectification arises in a practical design process is briefly reviewed.>