Mature biological neurons continually grow new connections in real-time, as learning occurs. To support similar life-long learning in silicon, it is important to build neuromorphic circuits that model structural plasticity as well as synaptic plasticity. Traditionally, AER packet switching networks have been used for system connection, but suffer from timing issues in real-time modeling of biological neuronal networks. This paper presents a connective fabric capable of growing new real-time connections in an existing neuromorphic circuit or FPGA. We introduce a more biologically-inspired approach to the connection and lifelong learning problems, where physical wire connections are grown between neurons throughout the system's lifetime, using switching hardware adapted from FPGA interconnect and a Lee-like routing algorithm inspired by Physarum polycephalum, a common myxomycete (acellular slime mold). By autonomously routing around both areas of high congestion and fabrication defects, this design is naturally suited for wafer-scale integration, or applications where damage accumulates over time. By more closely modeling the biological process of new synapse connections, future neuromorphic circuits, FPGAs, and spiking neural networks (SNNs) may become more brainlike by incorporating new forms of connectivity and lifelong learning.

Understanding how biological neurons encode information through neural signaling is crucial in building rich computational hardware neuromorphic systems. This paper creates a neuromorphic neuron model capable of processing and performing complex tasks autonomously and in real-time through neural modulation and dynamic neural encoding. We test the autonomous behavioral capability by mimicking Layer 5 Pyramidal Neurons' (L5PNs) coincident detection encoding behavior using a small network of neurons. The results show that individual output neurons can autonomously encode different received Action Potential (AP) patterns to their time of occurrence into unique output AP patterns. Such property might influence future neuromorphic autonomous encoding systems without the need for a large number of neurons. Implementation of circuits was conducted using the 45nm CMOS technology node, and functional verification is discussed in detail using Cadence Virtuoso Simulator tools.

Sensory information in the brain is encoded by intricate spiking patterns. Transient characteristics of individual action potentials may be used in neural encoding. Inspired by behaviors found in biological neurons, we have designed a neuromorphic circuit of a neuron that exhibits input-specific spiking. Our neuron circuit has multiple dendrites and uses properties of localized high-voltage-activated (HVA) Ca2+channels to generate action potentials with distinct shapes depending on the location of stimulation received at input synapses. Through circuit simulations, we show that our neuron circuit can encode differences in spatial locations of input stimuli through precise characteristics of output spikes, and spike shapes are tunable. We then show that neuron circuits, in conjunction with astrocytes, can be used to replace damaged neurons processing sensory inputs with healthy neurons augmented to process their own sensory inputs as well as the inputs originally intended for the damaged neurons, using spiking shapes to signal input sources.

A neuromorphic model of C. elegans undulating motion and simulation results are presented. The model contains 72 neurons and ancillary timing circuits that model the worm's motion due to a gentle touch. Analog CMOS circuits model sensory neurons, interneurons, and motor neurons, including synapses.

In neurons, the essence of nonlinear dendritic computations cannot be neglected as some neural behaviors depend heavily on these functions. In this paper, a power-efficient biomimetic intra-branch dendritic adder is introduced to emulate dendritic computations within the branches of the dendritic arbor. The proposed adder is implemented using 45nm CMOS technology. While exhibiting nonlinear behavior to post-synaptic input potentials, our simulation results shows that the adder consumes 2.95X and 10.8X less power, in processing of EPSPs and IPSPs, respectively, compared to the traditional adder used extensively in the BioRC project when implemented in the same technology.

Noise can play beneficial roles in neural network systems from biology to neuromorphic computing through stochastic resonance, averaging signals, and other mechanisms. To achieve the benefits of noise in neuromorphic circuits, we propose a random pulse generator(RPG) as a source of noise and describe its implementation in neuromorphic circuits. The RPG includes three components: an LED, a wave guide, and a single-photon avalanche diode(SPAD). The LED will generate photons in Poisson-distributed time intervals with Gaussian-distributed amplitude. Through a wave guide, the SPAD senses the photons and generate uV wavelength random pulses. The noise can be implemented in a discrete manner by connecting to an amplifier and in a continuous manner by connecting to a current mirror. The design was simulated using CMOS 180nm SPICE models. The generated variable signals are used in different parts of a BioRC neuromorphic neuron to implement a noisy neuron following different neurological findings. The noisy neuron's random postsynaptic potential(PSP), along with mechanisms to support stochastic resonance, noise inhibition and noise-forced spiking were demonstrated.

Power efficiency of the dendritic arbor has a high impact on the overall power efficiency of a neuromorphic design. We deploy a sub-threshold switched-capacitor mechanism and power gating to carry out summation of post synaptic potentials (PSPs) as well as capturing passive properties of dendrites through sampling PSPs on the capacitors and serializing them to perform summation rather than providing current through active devices as used in earlier designs. The power efficiency of the proposed 45nm CMOS circuit is demonstrated and compared to existing circuits used as dendritic arbors.

In this paper, We demonstrate biomimetic neural circuits (CMOS circuits) responsible for touch induced-locomotion in the nematode Caenorhabditis elegans (C. elegans). Our circuits model the neural network responsible for touch-induced locomotion of C. elegans worm (Chalfie and Sulston, 1985 [1]). Most animals use action potentials (spikes) for information transfer across neurons. Our initial touch-sensitive neural circuit presented here uses spiking neurons from the BioRC library. However, C. elegans neurons communicate with each other through graded potentials instead of action potentials, requiring redesign of the BioRC neuromorphic circuits to mimic a non-spiking neural network representing motion in C. elegans. Each neuron designed uses basic circuits like spike-responsive or graded-potential excitatory or inhibitory synapses, a voltage adder (dendritic computations) and an axon hillock (for spiking motor neurons). A neuromorphic neural network was constructed in CMOS using our neural circuits to implement touch-induced locomotion. We simulated spiking and non-spiking neural networks to demonstrate how signals propagate from sensory neurons to motor neurons when either posterior or anterior gentle touch is applied to the worm. We have demonstrated similarity between simulation results and biological measurements.

We present an electronic cortical neuron with nonlinear dendritic computations that performs border-ownership assignment. The circuit is simulated using a carbon nanotube field-effect transistor SPICE model. We demonstrate that our neuron can distinguish convex and concave contours, selectively respond to a figure based on the contour and/or disparity cues, and transform this neural information into a border-ownership signal. We demonstrate that a dendritic spike is key to contour detection and increases the robustness of border-ownership neuron firing. We construct an example hierarchical neural network that includes feedforward excitation and lateral inhibition to enhance border-ownership assignment.

We present an electronic cortical neuron incorporating both active and passive dendritic properties. The circuit is simulated using a carbon nanotube field-effect transistor SPICE model. We demonstrate that our neuron can detect coincident spatiotemporal input, and transform this neural information into a precisely-timed output spike. We also demonstrate that a dendritic spike is key to enhance precisely-timed input-output transformation within an individual neuron; without a dendritic spike it would require more neurons to achieve the same level of precision. Our simulation results show reliable firing and improved precision of output spike when a dendritic spike is initiated.

CMOS neuromorphic circuits are proposed to emulate the role of astrocytes in phase synchronization of neuronal activity. We emulate, to a first order, the ability of slow inwards currents (SICs) evoked by the astrocyte, acting on extrasynaptic N-methyl-D-aspartate receptors (NMDAR) of adjacent neurons, as a mechanism for phase synchronization. We do an experiment incorporating two small networks of neurons interacting with astrocytic microdomains. Upon enough synaptic activity, the microdomains interact with each other, generating SIC events on synapses of adjacent neurons. Since the amplitude of SICs is several orders larger compared to synaptic currents, a SIC event drastically enhances the excitatory postsynaptic potential on adjacent neurons simultaneuously. This causes neurons to fire synchronously in phase. Phase synchrony holds for a duration of time proportional to the time constant of SIC decay.

A CMOS neuromorphic circuit is proposed with two main features. First, we emulate the uptake of neurotransmitters by astrocytes, a type of glial cell, that plays an active role in the coordination of information between neurons. Second, we propose a synapse inactivation mechanism, which prevents the saturation of postsynaptic neurons in the absence of an astrocytic process. We show the influence of both mechanisms on the firing of a small network of neurons interacting with an astrocyte. We also incorporate the release of gliotransmitters by the astrocytic microdomain into this network according to the activities of neighbor synapses. This work contribute to better understanding the importance of astrocytes in neuro-glia interactions, and illustrates the active role astrocytes play.

Variable behavior has been observed in several mechanisms found in biological neurons, resulting in changes in neural behavior that might be useful to capture in neuromorphic circuits. This paper presents a neuromorphic cortical neuron with synaptic neurotransmitter-release variability, which is designed to be used in neural networks as part of the Biomimetic Real-Time Cortex project. This neuron has been designed and simulated using carbon nanotube (CNT) transistors, which is one of several nanotechnologies under consideration to meet the challenges of scale presented by the cortex. Some research results suggest that some instances of variability are stochastic, while others indicate that some instances of variability are chaotic. In this paper, both possible sources of variability are considered by embedding either Gaussian noise or a chaotic signal into the neuromorphic or synaptic circuit and observing the simulation results. In order to embed chaotic behavior into the neuromorphic circuit, a chaotic signal generator circuit is presented, implemented with CNT transistors that could be embedded in the electronic neural circuit, and simulated using CNT SPICE models. The circuit uses a chaotic piecewise linear 1-D map implemented by switched-current circuits. The simulation results presented in this paper illustrate that neurotransmitter-release variability plays a beneficial role in the reliability of spike generation. In an examination of this reliability, the precision of spike timing in the CNT circuit simulations is found to be dependent on stimulus (postsynaptic potential) transients. Postsynaptic potentials with low neurotransmitter release variability or without neurotransmitter release variability produce imprecise spike trains, whereas postsynaptic potentials with high neurotransmitter-release variability produce spike trains with reproducible timing.

Glial cells play an active role in the central nervous system. We present a CMOS neuromorphic circuit as part of the BioRC Biomimetic Real-time Cortex that emulates a glial microdomain, including several neurons interconnected in a small network. The glial cell, an astrocyte, influences neural behavior to stimulate a neuron to fire. Without glial intervention, the neuron would not have sufficient excitatory postsynaptic potential to fire. This circuit represents a first-order model of the reciprocal feedback between neurons and astrocytes involving gliotransmitters and neurotransmitters, and of the calcium concentrations induced in the astrocytes. Much more complex interaction has been observed and will be implemented in the future.

We present an evolutionary methodology that explores the evolution of network topology when a uniform growth of the network traffic is considered. The network redesign problem is formulated as an optimization problem, subject to a set of design and performance constraints, while minimizing the redesign cost by maintaining as many as possible of the network devices that constitute the original topology. The experimental results for a 3-level network redesign problem (consisting of 65 client nodes) demonstrate the value of the search technique within the genetic algorithms in finding good solutions with respect to redesign cost and time.

iCAD, an evolutionary program, concurrently designs hierarchical network topologies and data management systems for data intensive applications, enabling all of a network's clients to communicate and access servers efficiently, while minimizing design cost. iCAD chooses network hardware technologies, determines the data management system (selecting and placing servers; allocating files into servers) and integrates the data management system with the network. An object-oriented chromosome tree is used to explicitly represent all input and decision parameters. A compound crossover is formulated to merge two trees without repair. The experiment indicates the effectiveness of iCAD in finding good designs in a short time.

We present a novel technique to predict energy and power consumption in an electronic system, given its behavioral specification and library components. The early prediction gives circuit designers the freedom to make numerous high-level choices (such as die size, package type, and latency of the pipeline) with confidence that the final implementation will meet power and energy as well as cost and performance constraints. Our unique statistical estimation technique associates low-level, technology dependent physical and electrical parameters, with expected circuit resources and interconnect. Further correlations with switching activity yield accurate results consistent with implementations. All feasible designs are investigated using this technique and the designer may tradeoff between small size, high speed, low energy, and low power. The results for designs of two popular signal processing applications, predicted prior to synthesis, are within 10% accuracy of power estimates performed on synthesized layouts.

In this paper we describe a computer-aided design (CAD) tool for automatically designing and integrating network and data management hardware for data-intensive multimedia applications, such as the animation film studio. The tool determines the network strategy, interconnection hardware required, number and location of proxies and servers, and file allocation.

In typical hardware implementations of an arithmetic-intensive algorithm, designers must determine the word lengths of resources such as adders, multipliers, and registers. This paper presents algorithmic level theory and optimization techniques to select distinct word lengths for each computation which meet the desired accuracy and minimize the design cost for the given performance constraints. The reduction in cost is possible by avoiding unnecessary bit-level computations that do not contribute significantly to the accuracy of the final results. Thus we have introduced a new optimization variable, computation accuracy, into data-path synthesis. Our results show on an average, a 30% reduction in functional-resource area using distinct word lengths as opposed to use of a single optimized word length for the entire algorithm.

This paper introduces a basic mixedinteger-linear model (MILP) to design application-specificheterogeneous multiprocessors (ASHM) allowingimprecise computation of tasks executed ina non-preemptive mode.The proposed model wasused in the development of a genetic algorithm integratedinto the tool set MEGA that uses soft computingtechniques for design of optimal/near-optimalASHMs subject to constraints on performance, costand output-data quality.

System level design and behavior transformations have been rapidly establishing themselves as design steps with the most in uential impact onnal performance metrics, throughput and latency, o f a design.In this paper we develop a formal ILPbased approach for throughput and latency optimization when algorithm-architecture matching, retiming, and pipelining are considered simultaneously.The effectiveness of the approach is demonstrated on several real-life examples.

System-level design involves making major design decisions without having accurate information on the eventual system characteristics. This paper presents a novel constraint-driven methodology to support system-level design. The software assists a designer or a tool in partitioning behavioral specifications onto multiple VLSI chips and in system design while satisfying hard constraints such as individual chip areas, chip pin counts, system throughput (inverse of system initiation interval) and system latency (delay). The software uses search and estimation techniques to perform comprehensive design-space exploration and evaluates partitions supplied by the user or by other synthesis software. The technique determines what design characteristics each partition must possess in order to satisfy area, pin, throughput and latency constraints. The paper also includes results of extensive experiments with the methodology.>

We present a technique and formal model for optimal synthesis of specialized heterogeneous multiprocessors, given task flow graphs to be executed in a pipelined (periodic) fashion. SOS is a formal approach to system synthesis using mixed integer-linear programming, ensuring optimally of the final solutions. SOS was extended to cover the pipelined design style. The extensions were made while trying to avoid a considerable increase in computation time over the non-pipelined case. The extensions include new binary variables as well as new constraints used to ensure numerical convergence. The present tool supports minimization of parameters such as initiation rate, latency and cost.>

Abstract { This paper describes the use of Uni ed System Construction tools under development at the University of Southern California. The goal of the project is to automate the construction of heterogeneous, applicationspeci c systems. Key elements of the USC system include multiprocessor synthesis, multi-chip datapath synthesis, memory-intensive synthesis, and multi-chip partitioning. The tools were applied to design of an image compression chip set, and results of using these tools are reported on here. Our results are comparable to manual designs reported in the literature. 1

The power of retiming is often limited by the underlying topology of a computational structure.We combine the power of retiming with a complete set of algebraic transformations in an iterative improvement framework, where retiming and algebraic speed-up algorithms are successively applied, so that the latter enables the former.The key part of the approach is a new algebraic speed-up algorithm being used for the first time in high-level synthesis for transformations of algebraic expressions so that an arbitrary set of input arrival times and output required times are satisfied.Since the new method moves delays forward only and retiming is done locally and very infrequently, it also always calculates the new initial state efficiently.The proposed approach has yielded results better or equal to the best previously published on all benchmark examples and on several novel real-life examples.

Retiming, algebraic and redundancy manipulation transformations are widely used in both the high level synthesis and the compilers fields. We present a new approach on how these powerful transformations can be applied to improve the performance of embedded systems, by optimizing their latency and throughput. A simple modification is sufficient to adapt both the Leiserson-Saxe retiming algorithm and the recently introduced ERB algorithm for the new task. We introduce a new negative retiming technique and the algorithm which coordinates this technique with both algebraic and redundancy manipulation techniques for latency optimization. The effectiveness of all discussed techniques is demonstrated on a set of "real-life" examples. Latency and throughput are improved by factors of 7.06 and 2.83 respectively, often with minimal or no additional hardware overhead.>

Heterogeneous systems have the potential to achieve enhanced performance as well as cost-effectiveness over homogeneous systems when the application domain is known since they can match the problem structure more closely. It would be useful to have systematic methods for designing such systems for given applications. A formal design method, SOS, has been developed which can be used to synthesize optimal heterogeneous systems for given applications. The method involves creation of a mixed integer-linear programming (MILP) model and solution of the model. The method has been extended to deal with memory costs explicitly, and the extended MILP model is presented. Several experiments were performed with the original as well as the extended MILP model. These results indicate that it is important to include memory costs explicitly at design time.>

Heterogeneous systems can achieve enhanced performance and/or cost-effectiveness over homogeneous systems. SOS, a formal method to synthesize optimal heterogeneous systems for given applications, involves creation and solution of a mixed integer-linear programming model. A primary component of the model is the set of relations to be satisfied to ensure proper ordering of various events in the task execution, and completeness and correctness. Experiments indicate SOS can be useful in designing heterogeneous systems.

The ability to predict area-delay characteristics of designs without actually implementing them is important in producing quality designs in a reasonable time. A mathematical model for predicting the area-delay tradeoff curve for pipelined and nonpipelined data paths, given a data flow graph and a choice of module styles, is proposed. The model has been validated against designs generated by pipelined and nonpipelined data-path synthesis programs.>

This paper presents a novel constraint-driven system-level partitioning approach for behavioral specifications.The software assists a designer in partitioning behavioral specifications onto multiple chips while satisfying hard constraints which include individual chip areas, pin counts, system performance (initiation rate) and system delay.The partitioning method implemented in CHOP is based on predicting the feasibility of tentative partitions by searching through potential implementations of partitions to find combhtations which are feasible while takhtg system integration overhead into account.

This paper describes two experiments designed to show the effects of wiring area and delay and unused area on final chip characteristics.An example behavioral specification is used to produce a range of automatically synthesized designs with varying constraints on cost and performance, using both pipelined and nonpipelined design styles.An analysis of chip layouts is performed, and recommendations for future high-level synthesis programs are given.

This paper describes a formal technique for automated synthesis of multiprocessor systems for given applications.The application task is specified in terms of a graph, and the architecture synthesized includes a set of processing elements and the interconnection architecture between them.The technique generates a task execution schedule along with the architecture.The technique involves creation of a Mixed Integer-Linear Programming (MILP)model and solution of the model.Synthesis of a few example architectures is reported.1

Article 3D scheduling: high-level synthesis with floorplanning Share on Authors: Jen-Pin Weng Department of Electrical Engineering Systems, University of Southern California, University Park, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, University Park, Los Angeles, CAView Profile , Alice C. Parker Department of Electrical Engineering Systems, University of Southern California, University Park, Los Angeles, CA Department of Electrical Engineering Systems, University of Southern California, University Park, Los Angeles, CAView Profile Authors Info & Claims DAC '91: Proceedings of the 28th ACM/IEEE Design Automation ConferenceJune 1991 Pages 668–673https://doi.org/10.1145/127601.127748Online:01 June 1991Publication History 85citation439DownloadsMetricsTotal Citations85Total Downloads439Last 12 Months7Last 6 weeks1 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 novel paradigm for managing the digital process is presented. Under this paradigm, design is seen as a process in which abstract models of design tools are applied to abstract models of design states in a simulated or planning space, until a sequence of design tasks has been constructed to completion. Important parameters of the hypothetical design represented by the terminal states are then estimated. Either the planning is then repeated, or the sequence, or plan, is then executed, or carried out, in an execution space. This execution is monitored for violation of expectations; if violations occur, control is returned to the planner. The knowledge base of the planner is populated with register-transfer level (RTL) concepts for digital system design; it can also be populated with other knowledge sets. The planner forms part of the USC advanced design automation (ADAM) system.>

This paper describes a set of novel tradeoff experiments using MABAL, a Module And Bus ALlocation program. MABAL uses a simple heuristic algorithm to concurrently perform functional unit allocation, register allocation, interconnect allocation and module binding, while minimising overall cost. MABAL was used to produce over 3000 RTL designs from a specification which had been previously scheduled. Tradeoffs between buses and multiplexers and between data steering logic and functional logic were investigated. The results indicate data path tradeoffs are sensitive to the characteristics of the module library used, and illustrate the difficulty of integrating module generation or logic synthesis with high-level synthesis. This tradeoff study has also highlighted MABAL's capabilities and is unlike any other reported in the literature.

High-level synthesis systems start with an abstract behavioral specification of a digital system and find a register-transfer level structure that realizes the given behavior. The various tasks involved in developing a register-transfer level structure from an algorithmic level specification are described. In particular, it is shown how the high-level synthesis task can be decomposed into a number of distinct but not independent subtasks. The techniques that have been developed for solving those subtasks are presented. Areas related to high-level synthesis that are still open problems are examined.>

This paper presents a method for the generation of controller specifications from high-level behavioral descriptions in control and timing graph form. Input descriptions may contain multiple timing constraints, asynchronous and synchronous inputs, data dependent internal loops, and parallel and conditional branches. The timing graph model is transformed automatically to a state table specification of a synchronous finite state machine. The specification method is effective not only for independent data processors, but also for processors constrained by interface requirements and performing I/O protocol translation. The method has been programmed and tested on selected examples. Results from one example are given along with a comparison with results on the same example from another system.

The ADAM synthesis system consists of two major subsystems: the program tools which synthesize RTL designs from behavioral descriptions and the prediction tools which guide the designer in exploring the design space for a good design. In this paper, we demonstrate the necessity for predictions in narrowing the search space. With the aid of an example, we describe the interaction of a designer with the two subsystems in designing an RTL implementation which maximizes performance while meeting a given area constraint.

A complex object-oriented database system constructed using a physical database which is record oriented is described. The data model includes behavioral and timing information, and is comprehensive, covering the entire design process. The use of a commercial record-oriented database allowed rapid implementation of the system, supported schema changes, and provided a multiuser environment with database control support functions. Using such a database to support high-level synthesis activities is novel.>

The standard cell design style is investigated. Two probabilistic models are presented. The first model estimates the wiring space requirements in the routing channels between the cell rows. The second model estimates the number of feedthroughs that must be inserted in the cell rows to interconnect cells placed several rows apart. These models were implemented in the standard cell area estimation program PLEST (PLotting ESTimator). PLEST was used to estimate the areas of a set of 12 standard cell chips. In all cases, the estimates were accurate to within 10% of the actual areas. PLEST's estimation of a chip layout area takes only a few seconds to produce, as compared with more than 10 h to generate the chip layout itself using an industrial layout system.>

A mathematical model is presented for predicting the area-time tradeoff curve for nonpipelined data paths given a data-flow graph and a module set. Specifically, it examines operator cost and delay to predict the lower bound noninferior area-time curve. The model has been validated against designs generated by a program which synthesizes nonpipelined data paths.>

The authors describe a formalism for the representation of interface behavior which can be used for high-level synthesis by a design automation system. The Design Data Structure can represent the many facets of interface behavior in a unified way, including timing constraints, synchronous and asynchronous signals, control flow, and data manipulation. Its descriptive power is more complete than some other formalisms in use, including event and annotated data-flow graphs. The representations described here can be used by data path synthesizers to capture more complex timing information than is typically handled and to separate control from data manipulation information to produce cleaner data flow graphs. The Design Data Structure has been used successfully as an internal representation for a natural-language interface for system specification.>

The authors describe an example signal-processing design which illustrates partitioning, performance, cost, and fault-tolerance tradeoffs. They focus on high-performance multiplication using the power-of-two number representation as implemented in the POTATO (power of two arithmetic time-optimized) chip architecture. The implementation is compared to more conventional designs, and performance estimates are given. It is concluded that the design compares favourably to more conventional implementations.>

The effect of clocking schemes on overlapped execution performance in a digital system is described and quantified. Effects of branching, data dependencies, and resource conflicts between consecutive tasks are considered. Some problems of clocking scheme synthesis for the design of digital systems with maximum execution overlap are examined. Effects of performance of the choice of clocking scheme, partitioning of functions into the time steps, the number of clock phases, the length of each phase (i.e., how to pipeline), and the assignment of functions to clock phases are treated.>

A set of techniques for the synthesis of pipelined data paths is described, and Sehwa, a program that performs such synthesis, is presented. The task includes the generation of data paths from a data-flow graph along with a clocking scheme that overlaps execution of multiple tasks. Some design examples are given. Sehwa can find the minimum-cost design, the highest performance design, and other designs between these two in the design space. Sehwa is written in Franz Lisp and executes within minutes, for problems of practical size, on a VAX 11/750.>

Noun phrases consisting of a sequence of nouns (sometimes referred to as nominal compounds) pose considerable difficulty for language analyzers but are common in many technical domains. The problems are compounded when some of the nouns in the sequence are ambiguously also verbs. The phrasal approach to language analysis, as implemented in PHRAN (PHRasal ANalyzer), has been extended to handle the recognition and partial analysis of such constructions. The phrasal analysis of a noun sequence is performed to an extent sufficient for continued analysis of the sentence in which it appears. PHRAN is currently being used as part of the SPAN (SPecification ANalysis) natural language interface to the USC Advanced Design AutoMation system (ADAM) (Granacki et al, 1985). PHRAN-SPAN is an interface for entering and interpreting digital system specifications, in which long noun sequences occur often. The extensions to PHRAN's knowledge base to recognize these constructs are described, along with the algorithm used to detect and resolve ambiguities which arise in the noun sequences.

This paper describes a natural language interface, PHRAN-SPAN, for specifying the abstract behavior of digital systems in restricted English text. A neutral formal representation for the behavior is described using the USC Design Data Structure. A small set of concepts that characterize digital system behavior are presented using this representation. Finally, an intermediate representation based on Conceptual Dependencies is presented. Its use with a semantic-based parser to translate from English to the formal representation is illustrated by a series of examples.

In this paper we give a model for predicting the shape of cost-speed tradeoff curves for pipelined designs. The model includes prediction of the number of operators, registers and multiplexers from a behavioral specification. It has been verified with the designs generated by an automated pipeline synthesis program, Sehwa. This model was developed as a part of the ADAM Advanced Design Automation System of the University of Southern California.

This paper describes the REAL REgister ALlocation program. REAL uses a track assignment algorithm taken from channel routing called the Left Edge algorithm. REAL is optimal for non-pipelined designs with no conditional branches. It is thought that REAL is also optimal for designs with conditional branches, pipelined or not. Experimental results are included in the report, which illustrate the optimal solutions found by REAL. REAL is part of the ADAM Advanced Design AutoMation system, and will be used to process designs output from MAHA and Sehwa.

This paper describes the automatic design of custom integrated circuits from higher level specifications. The paper covers four topic areas: the problem domain and solution approach, higher level synthesis, module to layout automation systems, typically called silicon compiliers, and expert systems which control the design process. In the first three sections, several features of the VLSI problem domain which complicate automation are listed. The VLSI design process is diagrammed and the individual steps described. The term "silicon compilation" is defined to cover the entire process, and definitions for various subcategories of silicon compilers are given. The next Section describes both algorithmic and knowledge-based techniques Which perform higher level synthesis, including area estimation and module binding concurrent with synthesis. Research at Bell Labs, USC, CMU, and in Canada is described, along with other projects. The fifth section discusses the three categories of silicon compilers: commercially available systems, experimental compilers being developed by industry, and artificial intelligence approaches from university research. A survey of several systems is provided. The last section focuses on two systems developed at CMU and USC which plan or control design activities, Ulysses and DPE. Both systems allow the integration of various design automation tools and determine the proper tool invocation to automatically create a design. ADAM takes an autonomous approach, while ULYSSES follows user-defined scripts.

This paper describes PLEST, a program for estimating the area of standard cell layouts as part of the more general ARREST area estimator embedded in the ADAM system. PLEST is based on a probabilistic model for placement of logic. Given various design parameters, PLEST generates a range of estimates for the possible shapes of the block layout. The program was applied to a set of six layouts. The estimated chip area is, for all six chips, within 10% of the measured area. Further research will be aimed at estimating layout area consumption starting from the register-transfer level design description.

This paper describes a set of techniques for the synthesis of pipelined data paths, and presents Sehwa, a program which performs such synthesis. The task includes the generation of data paths from a data flow graph along with a clocking scheme which overlaps execution of multiple tasks. Some examples which Sehwa has designed are given. Sehwa can find the minimum cost design, the highest performance design, and other designs between these two in the design space. We believe Sehwa to be the first pipelined synthesis program published in the open literature. Sehwa is written in Franz LISP, and executes within minutes for problems of practical size on a VAX 11/750.

MAHA is a program which implements an algorithm for register level synthesis of data paths from a data flow specification. The algorithm is based on a linear hardware assignment to critical path nodes, followed by a cost-based assignment using the concept of the freedom of a node to be scheduled. Functions with the least scheduling freedom are scheduled first. The program either minimizes cost, subject to a time constraint, or maximizes speed subject to a cost constraint. The implementation of this algorithm is presented using examples from the literature.

A stochastic model for estimating measures of placement and routing on gate arrays is presented. Three important problems are addressed: estimating the dimensions of the routing channels, estimating the routability of a channel given the number of tracks, and determining the distribution and moments of wire lengths. In the context of wiring space estimation, exact and asymptotic formulas for the dimensions of routing channels are presented. Next, an expression for the probability that a routing channel with a given number of tracks will be routable is derived, and its asymptotic properties are examined. Finally, a model that characterizes the relationship between wire length distributions and partitioning of logic is developed. The model provides a firm mathematical basis for Rent's rule from which the distribution of wire lengths can be determined. That is, Rent's rule, or in general any similar relation, contains all the information about wire lengths. Based on this, estimates for the average wire length are derived. Numerical results from both simulated and real chips are presented.

This paper describes ADAM, an integrated Advanced Design AutoMation system, with focus on the knowledge-based synthesis subsystem. Working parts of this subsystem include a number of design activities and utilities, and a unified, multidimensional, hierarchical design representation. Two aspects of the synthesis subsystem are described in detail: the design planner and the natural language interface. The planner builds a plan for synthesis and analysis activities, drawing inferences from a knowledge base represented by a semantic net. The natural language interface accepts system-level behavioral specifications. Both of these packages are currently being implemented.

Clocking scheme synthesis includes the partitioning of functions into time steps, the number of clock phases, the length of each phase, (i.e. how to pipeline) and the assignment of functions to clock phases; each of these choices affects performance. Some important problems of clocking scheme synthesis are examined. Two efficient and powerful algorithms which synthesize near optimal clocking schemes have been programmed. These algorithms are applied to synthesis and/or performance evaluation of a design in progress. Optimizing the speed of a previously designed system is also considered.

This paper defines a multiple resolution representation for the two-dimensional gray-scale shapes in an image. This representation is constructed by detecting peaks and ridges in the difference of lowpass (DOLP) transform. Descriptions of shapes which are encoded in this representation may be matched efficiently despite changes in size, orientation, or position. Motivations for a multiple resolution representation are presented first, followed by the definition of the DOLP transform. Techniques are then presented for encoding a symbolic structural description of forms from the DOLP transform. This process involves detecting local peaks and ridges in each bandpass image and in the entire three-dimensional space defined by the DOLP transform. Linking adjacent peaks in different bandpass images gives a multiple resolution tree which describes shape. Peaks which are local maxima in this tree provide landmarks for aligning, manipulating, and matching shapes. Detecting and linking the ridges in each DOLP bandpass image provides a graph which links peaks within a shape in a bandpass image and describes the positions of the boundaries of the shape at multiple resolutions. Detecting and linking the ridges in the DOLP three-space describes elongated forms and links the largest peaks in the tree. The principles for determining the correspondence between symbols in pairs of such descriptions are then described. Such correspondence matching is shown to be simplified by using the correspondence at lower resolutions to constrain the possible correspondence at higher resolutions.

As part of our research on the Carnegie-Mellon University Design Automation System, we have been investigating methods for proving that the system produces correct designs from correct specifications. We have developed a mathematical model for the behavior of hardware descriptions, which we have used to prove that some of the optimizing transformations used in the design system preserve behavioral equivalence. The model, which is based on regular expressions modified by predicates to show data dependence, goes beyond the usual computational models used in program verification, in that it takes into account the proper sequencing of those "events" which represent interactions with the environment. This paper presents the model, shows how it can be used to represent the behavior of descriptions in an ISP-like hardware description language, and gives an example proof of a transformation.

This paper describes a method for formally modeling digital logic using algebraic relations. The relations model digital logic at the register-transfer (RT) level. An RT-level behaviorial specification is used to develop the relations, which express timing relationships that must be satisfied by any correct implementation. An extension of the model is shown which can be used for synthesis at the RT level. The growth rate and computational properties of the model are discussed, and an example of synthesis is shown.

This paper describes a portion of the Carnegie-Mellon University Design Automation (CMU-DA) research. This part involves the design and construction of a data-memory allocator, consisting of a set of algorithms and data structures which synthesize hardware at the register-transfer level from a behavioral description written in ISP. The allocator selects registers and data operators and interconnects them with data paths to form a data part capable of implementing the data operations specified in the behavior. Results indicate that the allocator's performance compares favorably with a human designer when designing an elevator controller and a reduced PDP-8/E. Although optimal designs cannot be guaranteed, upper bounds for the number of components used can be derived from the ISP description.

This paper focuses on automatic synthesis of digital hardware from a behavioral description. Algorithms have been written and tested to perform automatic generation of control hardware and optimized microcode for specified data paths. The optimization algorithms produce a family of results based on cost and speed constraints supplied by the user. The algorithms adapt to these constraints and adjust the amount of parallelism in the synthesized microcode accordingly. Tests were run by generating microcode for a PDP-11/40. Results compared favorably with the human design.

This paper describes the SLIDE language—a hardware-descriptive language desigued for the description of input/output, interfaces, and interconnected digital systems. The language allows the description of asynchronous, concurrent processes which can communicate. Timing and synchronization mechanisms are capable of being described as well. Current research applications include the use of the SLIDE language for I/O simulation and for verification of synchronization mechanisms.

Interconnection design can have a profound effect on the price and performance of a digital system. This paper describes a new simulation facility that is designed to allow the user to describe and simulate the behavior of an interconnected system. The simulator provides the capability to devise, debug, and evaluate digital interconnection schemes.

This paper presents a facility for the description and simulation of the inner machine of microprogrammable processors. The use of this facility for teaching microprogramming and for research is discussed. Twelve simulations are described, and an example simulation shown. Observations about the research are presented, and future research outlined.

This paper describes the design and partial implementation of a real-time sound generation system currently being built at Carnegie-Mellon University. The overall design process is followed, and design decisions are discussed in the light of design goals and overall system constraints. The resulting system consists of a keyboard which is light controlled and an array of microprocessors functioning in a pipeline fashion.

A man/computer input interface is described in this paper. This interface allows human control of the frequency, amplitude, spectral content and envelope of real-time sound production.

An interface for digital computers and peripherals is described in this paper. The design process is traced, beginning with the definition of the problem environment, and the derivation of primitive interfacing functions. The functions are associated with four functional classes; data input/output, data storage, data manipulation, and control. Interface capabilities range from control over the synchronization of input and output pulse data to control over the data word widths acceptable. System limitations include technical, timing, and synchronization problems. The interface is modular, generalized, and user programmable. The control is contained in two levels: a user microprogram, and a read only nanoprogram.