Logic Synthesis for Asynchronous Controllers and Interfaces | springerprofessional.de

Springer Professional

nach oben

2002 | Buch

Kapitel lesen Erstes Kapitel lesen

Logic Synthesis for Asynchronous Controllers and Interfaces

verfasst von: Prof. J. Cortadella, Dr. M. Kishinevsky, Dr. A. Kondratyev, Prof. L. Lavagno, Prof. A. Yakovlev

Verlag: Springer Berlin Heidelberg

Buchreihe : Springer Series in Advanced Microelectronics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is the result of a long friendship, of a broad international co operation, and of a bold dream. It is the summary of work carried out by the authors, and several other wonderful people, during more than 15 years, across 3 continents, in the course of countless meetings, workshops and discus sions. It shows that neither language nor distance can be an obstacle to close scientific cooperation, when there is unity of goals and true collaboration. When we started, we had very different approaches to handling the mys terious, almost magical world of asynchronous circuits. Some were more theo retical, some were closer to physical reality, some were driven mostly by design needs. In the end, we all shared the same belief that true Electronic Design Automation research must be solidly grounded in formal models, practically minded to avoid excessive complexity, and tested "in the field" in the form of experimental tools. The results are this book, and the CAD tool petrify. The latter can be downloaded and tried by anybody bold (or desperate) enough to tread into the clockless (but not lawless) domain of small-scale asynchronicity. The URL is http://www.lsi. upc. esr j ordic/petrify. We believe that asynchronous circuits are a wonderful object, that aban dons some of the almost militaristic law and order that governs synchronous circuits, to improve in terms of simplicity, energy efficiency and performance.

Anzeige

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract

This book is devoted to an in-depth study of logic synthesis techniques for asynchronous control circuits. These are logic circuits that do not rely on global synchronization signals, the clocks, to dictate the interval of time at which other signals are sampled. The difficulty with their design is well known since the late 1950’s. Asynchronous circuits cannot distinguish between combinational behavior, governed by Boolean algebra, and sequential behavior, governed by Finite State Machine (FSM) algebra. This separation, together with static timing analysis to compute minimum clock cycles, is essential to modern synchronous logic design. Asynchronous circuits can still, by means of appropriate delay models, abstract away most complex electric and timing properties of transistors and wires. However, both synthesis and analysis of asynchronous circuits must consider everything as sequential, and hence are subject to the state explosion problem which plagues the sequential world.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

2. Design Flow

Abstract

The main purpose of this book is to present a methodology to design asynchronous control circuits, i.e. those circuits that synchronize the operations performed by the functional units of the data-path through handshake protocols.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

3. Background

Abstract

In this chapter we will introduce models that are used for the specification, synthesis and verification of asynchronous circuits: Petri Nets and Transition Systems. We will also discuss relationships between the two, and transformations that can be done with each of them. These relationships and transformations are interesting within the context of asynchronous circuit synthesis for several reasons. Firstly, some of the synthesis steps, in particular state encoding as discussed in Chap. 5, can be made more efficient by using concepts, such as regions, that were first define to transform Transition Systems into Petri Nets. Secondly, that same transformation can be used to show in a readable form the result of various synthesis steps to the designer (back-annotation). Thirdly, the “new signal insertion” transformation, that is the basis of most synthesis phases, is defined so that it preserves some theoretically important properties of Transition Systems that are discussed in this Chapter.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

4. Logic Synthesis

Abstract

Chapter 2 has already outhned the main concepts and techniques behind our approach to the design of asynchronous control circuits. The key stage in this approach is logic synthesis from Signal Transition Graphs (STGs), a model which offers important advantages to the asynchronous controller and interface designer. On one hand, STGs are very similar to Timing Diagrams, which can be seen as a conventional pragmatic design notation. On the other hand, they are based on the formally sound theory of Petri nets, with a clearly defined syntax and semantics, and a plethora of algorithms and techniques for model analysis and transformations.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

5. State Encoding

Abstract

As we discussed in the previous chapter, some violations of STG and SG implementabihty conditions, such as output persistency and consistency, are considered to be essential for implement ability, and thus if violated they must be fixed by the designer. Complete State Coding (CSC) is also required for implement ability, however a specification that does not satisfy it can be transformed in such a way that its behavior remains externally equivalent to the original specification, yet the new SG satisfies CSC. One of the important conclusions of this chapter is that under reasonable assumptions about the class of specifications, the suggested methods to ensure CSC are effective and always converge.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

6. Logic Decomposition

Abstract

This chapter tackles one of the main problems of asynchronous circuit design: that of decomposing a complex Boolean function into elementary gates from a given library. In the synchronous case this is traditionally solved as two sub-problems. During the technology-independent phase [7, 8, 122, 10] one applies the theorems of Boolean algebra, and in particular Boolean and algebraic division operations, to optimally decompose the logic with a technology-independent cost function (e.g. literals for area and levels for delay). The result of this phase is a netlist of “canonical” technology-independent basic gates (e.g. inverters and 2-input nand gates). During the technology-dependent phase one maps the decomposed logic to the gates that are available in the library [123, 124]. The cost function at this stage may include more precise area and delay information, possibly including the effect of capacitive load and wiring estimates derived from approximate placement. Throughout this chapter we will assume a good knowledge of combinational logic synthesis techniques, as described in the above references.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

7. Synthesis with Relative Timing

Abstract

This chapter presents a synthesis approach for asynchronous circuits that takes timing into account. A fundamental problem appears when synthesis with timing is performed: the delays of the components are not known because the system has not been synthesized yet, and the system cannot be synthesized by using timing information because the components of the system are not known yet. This poses a chicken-and-egg problem that can be solved with the notion of relative timing and an iterative design flow.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

8. Design Examples

Abstract

This chapter presents a set of design examples that reflect typical cases in which the methods described in the previous chapters may be used. These examples also illustrate the practical strengths and weaknesses of the methodology, depending on the type of controllers or interfaces synthesized with it. This issue is important for two reasons. One is that real life design cases typically involve a combination of manual and automatic synthesis activities. In this respect, the reader should not overestimate the expressiveness of the language of STGs, or even PNs, as well as the power of algorithms and tools to always produce robust and efficient circuits. The class of PNs for which the corresponding STG can be implemented as a logic circuit is basically only restricted by the property of boundedness. No structural constraints are imposed on PNs. However, the method clearly has practical limitations. Those are related, firstly, to the limited size of the STGs that can be realistically implemented into circuits by the existing software tools (effectiveness aspect), and secondly, to the types of PNs and their signal interpretation, for example whether they involve regular patterns or require massive additional state coding (efficiency aspect). Some of our examples will reveal such problems.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

9. Other Work

Abstract

There are still several open issues in the design of asynchronous circuits that have not been completely covered by CAD tools. Some of them, and related research, are described in the next few sections. The interested reader is referred to a recent special issue of “Proceeedings of the IEEE” [175] for further references.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

10. Conclusions

Abstract

At the time of writing, the role of asynchronous circuits in the designer’s community is still unclear. Even though several advantages are claimed for asynchronous circuits, the methodologies to design and analyze them have tangible differences with respect to those used for synchronous circuits.

J. Cortadella, M. Kishinevsky, A. Kondratyev, L. Lavagno, A. Yakovlev

Backmatter

Titel: Logic Synthesis for Asynchronous Controllers and Interfaces
verfasst von: Prof. J. Cortadella
Dr. M. Kishinevsky
Dr. A. Kondratyev
Prof. L. Lavagno
Prof. A. Yakovlev
Copyright-Jahr: 2002
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-55989-1
Print ISBN: 978-3-642-62776-7
DOI: https://doi.org/10.1007/978-3-642-55989-1