Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2002-10-11
2004-03-23
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000, C717S132000, C717S139000, C717S155000, C703S014000, C703S028000
Reexamination Certificate
active
06711717
ABSTRACT:
BACKGROUND OF THE INVENTION
Portions of the disclosure of this patent document contain material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
1. Field of the Invention
The present invention relates to circuit design, and in particular the invention is directed to a programming language method and an associated compiler system for generating logical circuit design.
2. Background Art
In software systems, we usually compile a program as follows. First, we convert the high-level program into an intermediate-language representation; this is mainly a syntactic transformation for streamlining the syntax of the program to simplify automatic translation tools' analysis of the statements of the program. Secondly, we convert the intermediate-level representation into a dataflow graph, which is an abstract representation of how each value computed by the program depends on previous operations and of how later operations depend on the value. Thirdly, we manipulate the dataflow graph, aiming at lowering the cost of evaluating the statements it implies, but maintaining its meaning. Lastly, we convert the optimized dataflow graph into a machine language program, which can be loaded and executed by a processor when desired.
The technique that has been evolved for compiling software programs into machine language is attractive because it cleanly separates the question of what is computed from how it is computed. Specifically, given a simple program that performs actions that are independent, the dataflow graph can be used to deduce this property. Having determined that the actions are independent, the compiler can convert them separately into the target language. The dataflow graph also represents the constraints on the reordering of actions in the program.
The dataflow technique can be applied to the compiling of HSE (Handshaking Expansion) into PRS (Production-Rule Set). However, because the necessary properties (stability and noninterference) are global system properties, this is not simple. The only known algorithms that work on general HSE programs conduct exhaustive state-space exploration. As far as is known, these algorithms all take exponential time in the worst case, and they do not in practice work on large systems.
The difficulties of directly compiling from a higher-level description to PRS suggest that this is the wrong way of going about things. A description of an algorithm at the level of the sequence of actions on each bit (or electrical node) of a system is simply at too fine a level for most purposes. Once an algorithm has been described in this much detail, it has been over-sequenced; and removing the extra sequencing is too difficult. The bad level of specification that we speak of is exactly the HSE level.
That the compilation from HSE to PRS is hard is not the only problem with this approach. Another is that we have no trustworthy metrics for determining when one compilation is better than another. While we could possibly develop such metrics for determining when a given compilation result will run faster than another in a known environment, we may not know a priori all the parameters of the environment where a circuit will operate; if we had to know these parameters before compiling the circuit, we should certainly not be able to claim that the compilation procedure is modular. And modularity is the principle, above all others, that we strive for in asynchronous design. Better then to abandon the HSE level in our day-to-day design work and use PRS templates for compiling directly from CHP to PRS; the resulting PRS could be trusted to work efficiently in most environments.
As an aside, it is important to note the description of the problem above is not a condemnation of the HSE language itself. The HSE notation is, as we have seen, extremely useful for designing the templates used for compiling from CHP to PRS. The HSE language is indeed the most convenient of the languages we use for describing handshaking behaviors (as it should be). What we are suggesting is however that we should probably not manipulate the HSE descriptions of processes too frequently; we should do it only when we are developing the compilation templates or when we have to design some special circuit that we do not know how to design well using the day-to-day templates.
SUMMARY OF THE INVENTION
The present invention is a programming language method and its associated compiler system for generating logical circuit designs.
One embodiment of the present invention is a programming language method called Pipeline Language 1 (PL1). The PL1 language is a simple language for describing the small processes that are the targets of hardware systems that we desire to build. The semantics of the PL1 language allow the implementation to add more slack than exists in the specification; hence the language is appropriate for the design of slack-elastic systems.
In most message-passing programming languages (CHP in particular), using a data value that arrives on a channel first requires receiving it. In the hardware implementation, however, we can use and receive the value at the same time, or even delay the acknowledging of the value so that it remains pending. This functionality we have added to CHP with the value probe and peek operations. In the PL1 language the value probe and peek are the most basic operations: receiving a value is done by first using it (the peek), and then acknowledging it as a separate action.
PL1 programs consist of sets of guarded commands. The guards are not necessarily mutually exclusive. The semantics are that the process waits until it can determine, for each guard, whether or not it will be true for the next set of values that shall arrive. Thus we can evaluate expressions while banishing from our language the “undefined” value of a channel: there is in PL1 no way of writing the true negated probe.
PL1 automates the design procedure from CHP-level specification to STAPL (Single Track Asynchronous Pulse Logic) circuit. A more detailed description of STAPL is in co-pending U.S. Patent Application titled “Method and Apparatus for an Asynchronous Pulse Logic Circuit” filed Oct. 11, 2002, Ser. No. 10/xxx,xxx, and is hereby incorporated by reference. This automation helps STAPL circuit designers avoid both needless labor and careless mistakes.
The designer usually designs circuits at a high level of abstraction, i.e., in terms of digital abstractions. For this, the abstract CHP-level of description is ideal. Next, the design is compiled from the CHP to transistor networks, and thence finally to concrete geometric lay-out. The automation offered by PL1 reduces the amount of work done by human designers, especially at the level when intricate but mindless tasks like logic minimization are needed.
The reason the PL1 language is preferable to CHP follows from the PL1 language's being capable of expressing only a small fraction of what the CHP language can express. It is a fraction whose compilation into efficient APL and QDI circuits is well known. However, the PL1 language is not intended to replace the CHP language; on the contrary, it is expected that software tools will be written that shall be able to automatically convert CHP into PL1, or better yet, into PL1-equivalent data structures.
Another embodiment of the present invention is a compiler system that enforces the language of PL1 and creates valid compilation of programs written in the PL1 language. The compiler has two main components—a front-end module and a back-end module. The front-end module is technology-independent. It parses the input program, converts the input into BDD expressions, checks the determinism conditions of the input program, generates BDD expressions for assignments and sends and finally converts the BDD expressions to unary representation so they can be received
Martin Alain J.
Nyström Mika
California Institute of Technology
Coudert Brothers LLP
Harriman II, Esq. J. D.
Rossoshek Helen
Siek Vuthe
LandOfFree
Method and system for compiling circuit designs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for compiling circuit designs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for compiling circuit designs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3276171