A random forest is a widely used machine learning classifier. An FPGA is a good platform for performance acceleration of random forests due to their inherent concurrent memory accesses and computational parallelism. Amortizing the cost of an FPGA implementation among different applications is desirable, but the context switch time between applications significantly influences the forest architecture. Several architectures for random forests implemented within an FPGA are described, and the area-reconfiguration tradeoffs that determine the suitability of each for multiple applications are characterized. We show that each architecture can maximize the area utilization efficiency of an FPGA given a constraint on the context switch time.

Despite best efforts, integrated systems are “born” (manufactured) with a unique `personality' that stems from our inability to precisely fabricate their underlying circuits, and create software a priori for controlling the resulting uncertainty. It is possible to use sophisticated test methods to identify the best-performing systems but this would result in unacceptable yields and correspondingly high costs. The system personality is further shaped by its environment (e.g., temperature, noise and supply voltage) and usage (i.e., the frequency and type of applications executed), and since both can fluctuate over time, so can the system's personality. Systems also “grow old” and degrade due to various wear-out mechanisms (e.g., negative-bias temperature instability), and unexpectedly due to various early-life failure sources. These “nature and nurture” influences make it extremely difficult to design a system that will operate optimally for all possible personalities. To address this challenge, we propose to develop statistical learning in-chip (SLIC). SLIC is a holistic approach to integrated system design based on continuously learning key personality traits on-line, for self-evolving a system to a state that optimizes performance hierarchically across the circuit, platform, and application levels. SLIC will not only optimize integrated-system performance but also reduce costs through yield enhancement since systems that would have before been deemed to have weak personalities (unreliable, faulty, etc.) can now be recovered through the use of SLIC.

As manufacturing processes scale, designers are increasingly dependent on techniques to mitigate manufacturing defect and permanent failure. In embedded systems-on-chip, system lifetime and yield can be increased using slack —under-utilization in execution and storage resources—so that when components are defective, data and tasks can be remapped and rescheduled. For any given system, the design space of possible slack allocations is both large and complex, consisting of every possible way to replace each component in the initial system with another from the component library. Based on the observation that useful slack is often quantized, we have developed Critical Quantity Slack Allocation (CQSA), an approach that effectively and efficiently allocates execution and storage slack to jointly optimize system yield and cost. While exploring less than 1.4% of the slack allocation design space, our approach consistently outperforms alternative slack allocation techniques to find sets of designs within 1.4% of the lifetime-cost Pareto-optimal front. When applied to yield-cost optimization, our approach again outperforms alternative techniques, exploring less than 1.62% of the design space to find sets of designs within 4.27% of the yield-cost Pareto-optimal front. One advantage of managing failure at the system level is that the same techniques that improve lifetime often also improve yield. As a result, with little modification, CQSA is further able to perform effective joint optimization of lifetime and yield, finding designs within 1.6% of the Pareto-optimal front.

Wear-out related permanent faults are projected to make system lifetime a critical issue for all designs. In embedded systems, lifetime can be increased using slack, underutilization in execution and storage resources, so that when components fail, data and tasks can be re-mapped and re-scheduled. The design space of possible slack allocation is both large and complex. However, based on the observation that useful slack is often quantized, we have developed an approach that effectively and efficiently allocates execution and storage slack to jointly optimize system lifetime and cost. While exploring less than 1.4% of the slack allocation design space, our approach consistently outperforms alternative slack allocation techniques to find sets of designs within 1.4% of the lifetime-cost Pareto-optimal front.

Single-chip systems, featuring multiple heterogeneous processors and a variety of communication and memory architectures, have emerged to satisfy the demand for networking, handheld computing, and other custom devices. When simulated at cycle-accurate level, these system models are slow to build and execute, severely limiting the number of design iterations that can be considered. A key challenge in raising the simulation level above the clock cycle is an effective method for estimating contention for shared resources such as memories and busses. This paper introduces a new level of design called the Stochastic Contention Level (SCL). Instead of considering shared resource accesses at the clock cycle granularity, SCL simulations operate on blocks that are thousands to millions of clock cycles long, stochastically capturing contention for shared resources via sampled access attributes, while still retaining an event-based simulation framework. The SCL approach results in speedups of 40{\times} over cycle-accurate simulation, with average simulation errors of less than one percent with 95 percent confidence intervals of about \pm 3 {\rm percent}, providing a unique combination of simulation capabilities, performance, and accuracy. This significant increase in simulation performance enables the system designers to explore more of the design space than possible with traditional simulation approaches.

Emerging single-chip heterogeneous multiprocessors feature hundreds of design elements contending for shared resources, making it difficult to isolate performance impacts of individual design changes. This work is the first to parameterize shared resource accesses in the form of access attributes, summarizing the impact of shared resource contention on system performance, analogous to the way RTL parameters summarize more detailed transistor models. The intuition behind access attributes is that much application and architecture dependent contention information is known during detailed cycle-accurate simulations, and would be useful to inform a higher level model. The detailed contention information is sampled from a short cycle-accurate simulation, "training" a high-level statistical regression model of contention. This contention model can then be used in simulation to estimate the impact of shared resource accesses at a high level of abstraction, enabling the designers to explore contention-related performance impacts of design decisions. Using the access attribute-based contention models resulted in speedups of 40X over cycle-accurate simulation, with average simulation errors of less than 1% with 95% confidence intervals of about ±3%.

Emerging heterogeneous multiprocessors have custom memory and bus architectures that must balance resource sharing and system partitioning to meet cost constraints. We propose an augmented simulated annealing synthesis tool that uses system performance and layout evaluation to drive simultaneous data mapping, memory allocation and bus synthesis. A detailed look at the resulting automated design process reveals an approach that, contrary to prior approaches, optimizes bus topology first rather than last, providing design insight for the development of future tools.

Single-chip heterogeneous multiprocessors (SCHMs) are arising to meet the computational demands of portable and handheld devices. These computing systems are not fully custom designs traditionally targeted by the design automation community, general-purpose designs traditionally targeted by the computer architecture community, nor pure embedded designs traditionally targeted by the real-time community. An entirely new design philosophy will be needed for this hybrid class of computing. The programming of the device will be drawn from a narrower set of applications with execution that persists in the system over a longer period of time than for general-purpose programming. However, the devices will still be programmable, not only at the level of the individual processing element, but across multiple processing elements and even the entire chip. The design of other programmable single chip computers has enjoyed an era where the design tradeoffs could be captured in simulators such as SimpleScalar and performance could be evaluated to the SPEC benchmarks. Motivated by this, we describe new benchmark-based design strategies for SCHMs which we refer to as scenario-oriented design. We include an example and results

Embedded systems encompass a wide range of applications, technologies, and disciplines, necessitating a broad approach to education. We describe embedded system coursework during the first 4 years of university education (the U.S. undergraduate level). Embedded application curriculum areas include: small and single-microcontroller applications, control systems, distributed embedded control, system-on-chip, networking, embedded PCs, critical systems, robotics, computer peripherals, wireless data systems, signal processing, and command and control. Additional cross-cutting skills that are important to embedded system designers include: security, dependability, energy-aware computing, software/systems engineering, real-time computing, and human--computer interaction. We describe lessons learned from teaching courses in many of these areas, as well as general skills taught and approaches used, including a heavy emphasis on course projects to teach system skills.

Heterogeneous multiprocessing is the future of chip design with the potential for tens to hundreds of programmable elements on single chips within the next several years. These chips will have heterogeneous, programmable hardware elements that lead to different execution times for the same software executing on different resources as well as a mix of desktop-style and embedded-style software. They will also have a layer of programming across multiple programmable elements forming the basis of a new kind of programmable system which we refer to as a Programmable Heterogeneous Multiprocessor (PHM). Current modeling approaches use instruction set simulation for performance modeling, but this will become far too prohibitive in terms of simulation time for these larger designs. The fundamental question is what the next higher level of design will be. The high-level modeling, simulation and design required for these programmable systems poses unique challenges, representing a break from traditional hardware design. Programmable systems, including layered concurrent software executing via schedulers on concurrent hardware, are not characterizable with traditional component-based hierarchical composition approaches, including discrete event simulation. We describe the foundations of our layered approach to modeling and performance simulation of PHMs, showing an example design space of a network processor explored using our simulation approach.

As multiprocessor systems-on-chip become a reality, performance modeling becomes a challenge. To quickly evaluate many architectures, some type of high-level simulation is required, including high-level cache simulation. We propose to perform this cache simulation by defining a metric to represent memory behavior independently of cache structure and back-annotate this into the original application. While the annotation phase is complex, requiring time comparable to normal address trace based simulation, it need only be performed once per application set and thus enables simulation to be sped up by a factor of 20 to 50 over trace based simulation. This is important for embedded systems, as software is often evaluated against many input sets and many architectures. Our results show the technique is accurate to within 20% of miss rate for uniprocessors and was able to reduce the die area of a multiprocessor chip by a projected 14% over a naive design by accurately sizing caches for each processor.

Future Systems-on-Chips will include multiple heterogeneous processing units, with complex data-dependent shared resource access patterns dictating the performance of a design. Currently, the most accurate methods of simulating the interactions between these components operate at the cycle-accurate level, which can be very slow to execute for large systems. Analytical models sacrifice accuracy for speed, and cannot cope with dynamic data-dependent behavior well. We propose a hybrid approach combining simulation with piecewise evaluation of analytical models that apply time penalties to simulated regions. Our experimental results show that for representative heterogeneous multiprocessor applications, simulation time can be decreased by 100 times over cycle-accurate models, while the error can be reduced by 60% to 80% over traditional analytical models to within 18% of an ISS simulation.

As System On a Chip (SoC) designs become more like Programmable Heterogeneous Multiprocessors (PHMs), the highest levels of design will place emphasis on the custom design of elements that were traditionally associated with systems in the large. We motivate how schedulers that make dynamic, data-dependent decisions at run-time will be key design elements in PHM SoCs. Starting from a fundamental model, the role schedulers play in PHMs is developed. Model-based scheduling is introduced as an approach to designing schedulers that optimize a PHM's performance. Due to the complexity of the PHM design space, convergence on optimal design requires high-level modeling and simulation. In model-based scheduling, high-level models of scheduling decisions result in actual design elements that appear in real systems. Experiments for a simple two-processor PHM that does a mix of image and text compression are included. Results show the effectiveness of model-based scheduling.

We introduce the application of current techniques for hardware synthesis of combinational logic blocks to large-scale software partitions for eventual implementation of these partitions in a novel memory device called "Co-RAM." The novelty of our approach is based upon the observation that a wide variety of largescale software functionality can be considered "stateless" by conventional hardware synthesis tools and so may be realized as combinational logic. By limiting the functions placed in memory to combinational functions, we eliminate conventional synchronization overhead associated with coprocessors. A significant aspect of Co-RAM is that it is a system design concept that inherently merges hardware and software design styles at the system level, impacting programming styles, system build approaches, and the programmer's view of the underlying machine. A direct consequence of viewing the functionality as combinational is that the system state is not partitioned with the tasks. By Considering Co-RAM functionality to be stateless with respect to system state, Co-RAM functionality is inlined around the advancement of effectively unpartitioned system state. The rules for procedural combinational logic synthesis are shown to apply to a wide variety of software partitions. Results of our investigation project speedups of 8/spl times/ to 1000/spl times/ for a range of algorithms of varying problem size and for projected devices ranging from conventional field programmable gate arrays (FPGAs) to highly specific combinational logic devices.

Our methodology unifies behavioral synthesis and physical design, allowing scheduling, allocation, binding, and placement to occur simultaneously. This is accomplished via set of defined transformation from both domains acting as forces in a single behavioral/physical system. Experiments show results with 50% less area and 10% lower critical path delay than the best results from a commercial behavioral synthesis tool. Our behavioral level area, delay, and individual component location estimates closely match results produced by physical design tools given only pin locations as a starting point.

The Codesign Virtual Machine (CVM) is introduced as a next generation system modeling semantic. The CVM permits unrestricted system-wide software and hardware behaviors to be designed to a single scheduling semantic by resolving time-based (resource) and time-independent (state-interleaved) models of computation. CVM hierarchical relationships of bus and clock state domains provide a means of exploring hardware/software scheduling trade-offs to a consistent semantic model using top-down, bottom-up and iterative design approaches from a high system level to the machine implementation. State domain partitionings permit run-time software schedulers to be resolved with design time physical scheduling as peer- and hierarchically-related architectural abstractions which cut across functional boundaries. The resultant abstraction provides “component-less” paths to physical design with greater accommodation of shared resource modeling. A simulation example is included.

We present our methodology for developing models of on-chip SRAM memory organizations. The models were created to enable the quick evaluation of energy, area, and performance of different memory configurations considered during synthesis. The models are defined in terms of parameters, such as size and mode of operation, which are known at synthesis time. Our methodology does not require knowledge of the underlying memory circuitry and provides models with average percentage errors within 8%. We examine the importance of the different parameters in the models to reduce the time required to develop the models. We found that only ten different memories from a large span of possible memory sizes are needed to obtain reasonably accurate models, with average errors within 15%. In this paper, we present our modeling methodology, discuss the important aspects in developing the models, and examine the parameters necessary in creating accurate models quickly and easily.

Vertical benchmarks are complex system designs represented at multiple levels of abstraction. More effective than componentbased CAD benchmarks, vertical benchmarks enable quantitative comparison of CAD techniques within or across design flows. This work describes the notion of vertical benchmarks and presents our benchmark, which is based on a commercial DSP, by comparing two alternative design flows. 2.

Presents an environment for the exploration of low-power memory configurations. The environment uses accurate models of memory energy, area and delay to evaluate different configurations. Taking the constraints specified by the user and memory profiling information from the application, the environment can optimize the memory organization for a specific application. The environment also places and routes the organizations to provide more accurate energy, area and delay estimates. Our overall memory system estimation is highly accurate, with average absolute percentage errors within 7%. Within the environment, the user can explore powerful energy/area/delay trade-offs. We present results which show energy reductions within the memory system of up to 63%.

While guarded evaluation has proven an effective energy saving technique in arithmetic circuits, good methodologies do not exist for determining when and how to guard for maximal savings.Three new internal guarding techniques are presented in adders that increase energy savings up to 38% over existing external guarding techniques.This allows guarded evaluation to be effective at duty cycles as much as 20% higher than are currently practical.A modeling methodology is presented defining the energy and energy delay of a unit in a generic application space.These models can easily be incorporated into an automated selection technique to determine the optimal guarded implementation.This technique is tested on a DSP ASIP, increasing overall energy savings by preventing unnecessary guarding.The data is generalized and it is observed that guarding is most beneficial when the ratio of guarding transistors to driven computational transistors is 'Ilo or lower.

While reconfigurable computing promises to deliver incomparable performance, it is still a marginal technology due to the high cost of developing and upgrading applications. Hardware virtualization can be used to significantly reduce both these costs. In this paper we describe the benefits of hardware virtualization, and show how it can be achieved using a combination of pipeline reconfiguration and run-time scheduling of both configuration streams and data streams. The result is PipeRench, an architecture that supports robust compilation and provides forward compatibility. Our preliminary performance analysis predicts that PipeRench will outperform commercial FPGAs and DSPs in both overall performance and in performance per mm2.

Most work to date on power reduction has focused at the component level, not at the system level. In this paper, we propose a framework for describing the power behavior of system-level designs. The model consists of a set of resources, an environmental workload specification, and a power management policy, which serves as the heart of the system model. We map this model to a simulation-based framework to obtain an estimate of the system's power dissipation. Accompanying this, we propose an algorithm to optimize power management policies. The optimization algorithm can be used in a tight loop with the estimation engine to derive new power-management policy algorithms for a given system-level description. We tested our approach by applying it to a real-life low-power portable design, achieving a power estimation accuracy of ∼10%, and a 23% reduction in power after policy optimization.

We present techniques for generating addresses for memories containing multiple arrays. Because these techniques rely on the inversion or rearrangement of address bits, they are faster and require less hardware to compute than the traditional technique of addition. Use of these techniques can improve performance and cost of application-specific memory subsystems by decreasing effective access time to arrays and by reducing address generation hardware. The primary drawback to this approach is that extra memory space is occasionally required, but in over a million tested cases, this extra memory space is on average only 2% and no worse than 17.4% of the utilized memory space. This amount of wasted address space is significantly less than the amount required by the only known similar technique and rarely necessitates the allocation of additional memory components. These techniques provide a foundation for adder-free address generation for manually and automatically generated application-specific memory designs.

This paper discusses the mapping of arrays in a behavior to memories in an implementation. We introduce a novel approach to the design of memory systems, which is based on a variety of array grouping techniques and dimensional transformations, and the binding of array groups to memory components with different dimensions, access times, and number of ports. The results of design actions are computed in terms of memory cost, the number of wires necessary to connect the memory to the data path, and the limit of performance imposed by the memory design on the implementation. Three different procedures can be used to find a suitable memory design. All three procedures are directed by a weighted and constrained system cost function, which enables the expression of the user's design priorities. Compared to related research efforts, our approach improves performance by as much as 19%, reduces memory cost as 40%, and decreases the number of wires required to connect the memory to the data path by up to 57%.

Over the past several years there has been a great deal of interest in the design of mixed hardware/software systems, sometimes referred to as hardware/software co-design or hardware/software co-synthesis.However, although many new design methodologies have taken the name hardware/software co-design, they often do not seem to share much in common with one another.This partly due to the fact that the problem itself has so many dimensions.This tutorial describes a set of criteria that can be used to compare differing approaches to hardware/software co-design.These criteria are used in the discussion of a number of published hardware/software co-design techniques to illustrate how a wide range of approaches can be viewed within a single framework.

In this paper we present a set cover based approach (SCP) to multi-way partitioning for minimum delay for Look-Up Table based FPGAs.SCP minimizes the number of chip-crossings on each circuit path with minimum logic duplication costs to achieve implementations with minimum delay and minimum number of chips.The overall complexity of SCP is (V 2 ).Experimental results demonstrate that SCP produces partitions that on the average have 14% fewer chips, 28% fewer pins, and 93% fewer chip-crossings on each circuit path compared to ANN which is a simulated annealing based implementation of classical multi-way partitioning.SCP achieves this performance and compact packing at the cost of duplicating 13% of logic on the average.Additionally, in comparison with a lower bound we observe that SCP has produced near-optimal solutions.

This paper compares software and FPGA-based hardware implementations of two applications. The first application uses hidden Markov models, and the second application is a fuzzy controller. Hidden Markov modeling is used for temporal pattern recognition and speech recognition in particular. Both applications are accelerated when implemented in FPGA-based hardware, but this acceleration is obtained by using different algorithms than those used in software implementations. These different algorithms produce slightly different outputs; therefore both solution quality and performance must be evaluated to compare hardware and software implementations. The experience of designing these applications has implications for hardware/software codesign tools and for the migration of existing software applications to FPGA-based hardware.

This paper presents techniques for generating addresses for memories containing multiple arrays. Because these techniques rely on the inversion or rearrangement of address bits, they are faster and require less hardware to compute than offset addition. Use of these techniques can decrease effective access time to arrays and reduce address generation hardware. The primary drawback is that extra memory space is occasionally required by these techniques, but this extra memory space is on average only 4% and no worse than 25.2% of the utilized memory space. This amount of wasted address space is less than the amount required by similar techniques.

This paper presents a technique for back-annotating the results of high-level synthesis into the source description to produce a timing-accurate behavioral simulation model. The resulting simulation model exhibits the same cycle-by-cycle behavior as a register-transfer level model, but can be simulated in a fraction of the time. This idea has analogies both to software profiling and to back-annotation at lower levels of hardware design. Experimental results demonstrate that the annotated behavioral simulation models run two to three orders of magnitude faster than register-transfer level simulation models, and only about an order of magnitude slower than behavioral models with no timing information.

Though high-level synthesis tools seem to fit nicely into the traditional top-down VLSI design methodology in which an abstract algorithmic model is transformed into a detailed register transfer level implementation, there is an important difference between filling in the details by hand and relying on a high-level synthesis tool to do so.Unlike the hand-designer, an engineer who uses a synthesis tool is not likely to be familiar with the specific register transfer level implementation.Thus, the use of high-level synthesis tools can effectively inhibit the engineer's ability to attack design problems or make informed trade-offs at either the specification or implementation level.A solution to this problem that we have developed in this research is to expose register transfer level implementation detail to the engineer, for both analysis and modification, in terms of the original algorithmic specification of the system.We introduce a new design abstraction that can uniformly represent both the input and output of high level synthesis tools.When coupled with a new type of synthesis tool, the attributed-behavior abstraction can increase the potential for high-level design space exploration by making synthesis results accessible to the engineer.

This paper describes a novel technique to generate test vectors for single stuck-at faults using the behavioral description of the circuit function and the mapping from the behavior into the hardware that implements it. The test vector generation problem is formulated as a mixed integer nonlinear programming (MINLP) problem, and the test vectors are obtained by solving a series of MINLPs. The technique has been implemented and results from this approach show an order of magnitude speed up in test generation compared to existing gate-level sequential test generation tools.

Coloring of conflict graphs and clique partitioning of compatibility graphs have been used in high-level synthesis to map operators, values, and data transfers onto shared resources. However, finding a minimum sized coloring or clique partition is NP hard. One method to overcome this complexity is to identify special types of graphs that can be colored or clique partitioned in polynomial time. Existing high-level synthesis systems have exploited two special types of conflict graphs-interval and circular-arc graphs. However, they have provided no insight into why and how frequently these graphs occur. This paper will investigate the features of behavioral representations and synthesis algorithms that give rise to special conflict and compatibility graphs. We will identify two additional types of graphs useful for high-level synthesis-chordal and comparability graphs-and demonstrate their use in an existing high-level synthesis system.>

Thispaper presents the Snapshot Method, a technique that fills a void in existing synthesis systems by considering inter-instruction data dependencies while defining a pipeline structure.These dependencies can make it impossible to overlap the execution of some sequences of instructions thus the detection and resolution of such sequences is an important contribution of this work.Experimental results for a design of the IBM ROMP architecture are presented.

Article Performance directed technology mapping for look-up table based FPGAs Share on Authors: Prashant Sawkar View Profile , Donald Thomas View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 208–212https://doi.org/10.1145/157485.164672Published:01 July 1993 28citation199DownloadsMetricsTotal Citations28Total Downloads199Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A technique is introduced that gives an engineer greater control over the design space considered by a high level synthesis tool. This is accomplished by allowing the engineer to make assertions about temporal and structural relationships between operations in a data-flow graph that must be reflected in any synthesized result. An engineer can use these assertions to make design trade-offs and improvements while working with a high-level synthesis tool.

In this paper, we present a novel model of CAD tool control that can be used in the constraint-directed control of high-level synthesis tools. To enable this control we introduce the concept of a design space reasoning mechanism. We formally describe a statistical based, machine learning process that automatically generates the tool control knowledge necessary to drive the design space reasoning mechanism. The representation of this tool control knowledge in the form of a fuzzy, linear differential, qualitative model is described. Finally, the experimental results obtained using the Magellan system are presented.>

The tradeoff between using a custom IC and using standard ICs to implement part of a system is formalized. A design tool which demonstrates the ability to make such tradeoffs in the design of a microprocessor-based computer system is introduced. It is shown that effective use of ASIC gate capacity and I/Os results in designs that require as little as 62% of the PC board area needed by designs with no ASIC.>

APARTY is an architectural partitioning tool that uses a novel multistage clustering algorithm to extract the high level structure of an IC design by concentrating on area and interconnect considerations. Performance is addressed implicitly. APARTY works within the framework of the system architect's workbench and can pass system-level structural information along to register-transfer level (RTL) tools to guide the completion of a data-path design. The multistage clustering algorithm and how it is used by APARTY to choose partitions are described. The system architect's workbench and how architectural partitioning can be used to guide synthesis are also described. Results of using APARTY in the design process show improved register-transfer designs. In particular, the number of global routing wires is generally reduced by over 50% by following the partitioning scheme suggested by APARTY.>

We present a single high level synthesis algorithm that schedules the operations of a data dependence graph, allocates the necessary hardware, and maps the operations to specific functional units. This is achieved by extending the global analysis approach developed for force-directed scheduling to include individual module instances. This new algorithm should be applicable to any behavioral synthesis system that schedules operations from a data dependence graph.

Two types of graphs are presented: chordal graphs and comparability graphs. Chordal graphs guarantee a minimum number of registers on a larger number of designs. Comparability graphs reduce the complexity and improve clique partitioning algorithms used in high-level synthesis.>

Architectural partitioning is introduced as a new phase in system level synthesis. Architectural partitioning extracts high level structure from the behavior of an architecture. This paper describes the APARTY architectural partitioner, an automatic Architectural PARTYtioner that supports synthesis in the System Architect's Workbench. APARTY uses a unique multi-stage clustering technique. Knowledge of the high level structure of an architecture aids synthesis tools in choosing a better design in terms of area. For one example, architectural partitioning reduced the number of wiring tracks in the final design by 20%.

An attempt was made to define the algorithmic level of design (also known as the behavioral level) and to provide the designer with the means to explore various design issues. Within the framework of the System Architect's Workbench, a new set of behavioral and structural transformations was developed to allow the interactive exploration of algorithmic-level design alternatives. A description is given of these transformations, and a set of examples is presented both to demonstrate the application of the transformations and to further illustrate their effects.>

A means of linking together the behavioral and structural domains of representation is presented. The approach can be used in a design synthesis system where the input is an abstract behavior of the system to be designed. As transformations are made to the behavior and the logical structure is specified, this approach maintains the correspondences between the two. These correspondences are maintained even when numerous optimizing transformations are applied to the behavior and structure. The result is that the structure designed can be correlated with the initial behavioral description and feedback containing both can be produced for a system-level architect.

Hierarchical design representation can be a useful approach to the problem of handling the complexity of digital designs. A means of linking together hierarchical behavioral representations in a design system is presented. Along with other information, this linking correlates the abstract behavior and logical structure together, opening the way for multilevel analysis aids that include these levels. Multilevel simulation is briefly discussed.

The Design Automation Assistant is a knowledge-based expert-system, KBES, that generates a technology-independent list of operators, registers, data paths and control signals from an algorithmic description of a VLSI system. One merit of codifying knowledge in a KBES is that it can be easily quantified and qualified. This paper takes a retrospective on that codified knowledge base, examining what has been learned about VLSI design. It discusses both the major steps in the implementation design process and the extent to which each rule embodies domain knowledge. Finally, the paper provides an example design with typical rules from each of the major steps in the implementation design process.

This paper presents a method for the automatic synthesis of digital systems from behavioral descriptions. Subtasks in complex problem solving activities like synthesis often interact. As a result, premature binding of decisions can lead to poor designs. Better design choices can be made if decisions are postponed until adequate information is available to make them. The paper details how delayed binding of decisions is implemented in a program called SUGAR and how subtasks are organized so that they cooperate with one another in designing a system.

To represent the increasingly complex designs being produced today, we have developed1 a unified model of design representation that uses three hierarchical, non-isomorphic domains of description that can be coordinated to represent the entire design. Each of these domains contains multiple levels of abstraction; both the domains and the levels are described in detail in this paper. We then show how this model of design representation can be used as a model of design synthesis. It is hoped that this work will lead to a better understanding of design representation and its relationship to the synthesis process.

This paper discusses a design aid which translates the data part of a functional level digital design into a logic level design through the specification of module set information. The constraint driven automatic methodology is discussed and results of using the design aid are presented. Predictors are developed to estimate the logic level design space, thus providing early feedback within the design process.

This paper describes the definition and implementation of a multilevel representation which includes both behavioral and structural information. Information for the representation is generated by the CMU-DA synthesis system. A timing abstraction aid which extracts logic level timing information from a detailed implementation and makes it available for the ISPS behavioral simulator is discussed. Such a multilevel representation and design aid allows the system level designers to be in a closed loop of design aids with the technology level designers.

A design representation that incorporates descriptions at more than one level of abstraction is called a multilevel representation. This paper describes a multilevel representation which includes behavioral and structural levels of description, and a multilevel analysis aid, called timing abstraction, which extracts timing information from a structural design and adds it to a behavior level description. With this design aid, alternate implementations of the same behavior, generated using the CMU-DA synthesis software, can be compared using a behavior level simulator. The timing accuracy is that of the microcode impleinentation, while the speed of the simulation is that of a behavior level simulator.

Design automation at the register transfer level of design is still in its infancy, and it is not yet completely understood what the appropriate measures used in direction the automated design process should be. To establish these measures, results of these design automation systems must be compared with some near optimal designs. A set of statistically based experiments is developed to estimate near optimal designs. A method is demonstrated for gathering data on designer performance, specifically at the different levels of systems design, and in general for calibration of other design automation systems where the intuitive designer still performs more capably than the present design algorithms. An analysis of variance is used to indicate the relative importance of various decisions in a system design. It is shown that the algorithm to be implemented and the hardware design style account for 90 percent of the variation in the results. Thus, selecting the design style (e.g., distributed, microprocessor, pipelined, etc.) is the most important parameter for a design automation system.