Computer Logical Design Laboratory

/ V. I. Varshavsky / Professor
/ Rafail A. Lashevsky / Professor
/ Robert H. Fujii / Associate Professor
/ V. V. Smolensky / Research Associate
/ E. V. Varshavskaya / Research Associate

Computer Logic Design Laboratory carries out two projects:

1. "Performance-driven algorithms for VLSI layout"

In the VLSI automated physical layout area, the use of fuzzy logic to automatically control genetic algorithm parameters is being explored. Parallel algorithms utilizing such approaches are also being developed.

2. "Self-Timing and Event-Driven Architecture"

The works were directed to solve the following problems:

2.1. Global synchronization of asynchronous arrays.

Problem: The complication of Wave Propagation and Systolic Arrays makes their common synchronization extremely difficult, often impossible. If there are several initiating processors or wave front propagation rate has to be measured, the conventional asynchronous approach (asynchronous and pipelined interaction between the processors) causes ambiguous or conflict situations.

Results: The array should be divided to two strata - synchrostratum (a self-timed pipelined array with one rhythm driver) generating a system of unidirectional synchrowaves, and an array synchronized by these waves. The implementation as well as the algorithms of synchrostratum behavior and strata interaction are developed.

2.2. Self-Timed Systems with Current Sensors.

Problem: Self-timed CMOS devices can be built from usual circuits provided with current sensors that fix the moments of transition processes completion. However, the available sensors have limited range of indicated currents and impulse output signals incompatible with delay-insensitivity.

Results: A current sensor has been modified. This expands the range of indicated currents with minimal loss of performance. Calculation methods are developed using the parameters of current range, performance and occupied area. Current shunt is suggested transforming impulse reaction of a sensor to potential one. Several variants of asynchronous buses insensitive to delay skew with minimal redundancy and maximal performance are developed.

2.3. Self-Timed Circuit Design from "Gate Structure".

Problem: A designer usually has a notion about future device structure. How can he take it into account during the iterative procedure "specification - design - specification..."?

Results: Self-timed device synthesis method for gate structure "master-slave finite automata" is developed. The method of direct translating event specifications to gate level implementation is modified. For the method of succesive inserting gate behavior into the initial specification and dealing with specification projections to limited event subsets, initial ideas are formulated.

2.4.Transmormation of arbitrary faults to stuck-at faults.

Problem: Self-timed circuits have the property of full self-checking in respect to stuck-at faults at gate outputs that make up 40-60%of the total number. For super-reliable systems it is inefficient.

Results: General approaches to constructing self-checking circuits are formulated. The ways to insert redundancy for transforming arbitrary faults and failures to an unlimited delay are suggested.

Refereed Journal Papers

1. V. Varshavsky, V. Marakhovsky, and V. Smolensky. Design of self-timed non-autonomous devices specified by the model of finite automaton. IEEE Design &Test of Computers, special issue on Asynchronous Circuits and Systems, June 1994.

   A procedure of designing a self-timed non-autonomous device defined by the model of finite automaton is suggested. The procedure is based on the standard realization of a finite automaton and uses a CAD system. In accordance with the chosen standard realization from the automaton transition/output graph one derives the linearized specification of the device being designed in the language CD (Change Diagram) that then is processed by the CAD system. Such an approach in a number of cases provides good circuit solutions. It is illustrated by two examples of designing self-timed devices: Self-Timed Stack Memory and Pipelined Counter with Constant Acknowledge Delay.

   
   

2. M. Kishinevsky, A. Kondratyev, A. Taubin, and V. Varshavsky. Analysis and identification of speed-independent circuits on an event model. Formal Methods in System Design, (4):33-75, 1994.

   The object of this article is the analysis of asynchronous circuits for speed independence or delay insensitivity. The circuits are specified as a netlist of logic functions describing the components. The analysis is based on a derivation of an event specification of the circuit behavior in a form of a signal graph. Signal graphs can be viewed either as a formalization of timing diagrams, or as a signal interpreted version of marked graphs (a subclass of Petri nets). The main advantage of this method is that a state explosion is avoided. A restoration of an event specification of a circuit also helps to solve the behavior identification problem, i.e., to compare the obtained specification with the desired specification. We illustrate the method by means of some examples.

Refereed Proceeding Papers

1. R. Fujii and E. Mellon. Darwin: A timing driven placement algorithm using the genetic optimization approach. In International Conf. on VLSI and CAD, Korea, Nov. 1993.

   The objective of timing driven placement optimization is to find a mapping of devices onto a set of possible locations that affords maximum timing margin. This paper presents DARWIN, an adaptation of the genetic algorithm to achieve timing driven placement optimization. Several key aspects of the standard genetic search technique were modified for placement optimization including a new fitness operator based on timing margin, and a new solution space encoding scheme.

   
   

2. V. Varshavsky and T.A. Chu. Self-timing - tools for hardware support of parallel concurrent and event-driven process control. In Massively Parallel Computer Systems '94. IEEE Computer Society &Euromicro, September 1994.

   General methodological problems are considered in the report in conformity with processor array behavior. The general idea of self-timing is formulated; advantages and disadvantages of self-timing and a brief summary of the main practical achievements are given. A general method of asynchronous array global synchronization is suggested that is allotting a special synchro-stratum with one rhythm source. Two examples of solving problems in one-dimensional asynchronous automata arrays are given: bisection and up-down counting with constant response time. In both of the examples one solves the problem of the interaction between two cross waves propagating along the array concurrently.

Books

1. M. Kishinevsky, A. Kondratyev, A. Taubin, and V. Varshavsky. Concurrent Hardware. The Theory and Practice of Self-Timed Design. J.Willey &Sons, Dec. 1993.

Technical Reports

1. V. Varshavsky and V. Marakhovsky. Fault-tolerant self-timed system mono-channel. , In Technical Report of IEICE. CPSY 94-14-2615., 1994.

Academic Activities

1. V. Varshavsky and V. Marakhovsky. Self-timed circuit design, Nov. 1993.

   Invited presentation in Ibaraki Workshop on Self-Timing.

   
   

2. V. Varshavsky. Introduction to self-timed/asynchronous system design, Nov. 1993.

   Invited presentation at Ibaraki Workshop on Self-Timing.

   
   

3. V. Varshavsky and V. Marakhovsky. Self-timed fault-tolerant system bus, Jun. 1994.

   Invited presentation in Aizu Workshop on Fault-Tolerance.

   
   

4. V. Varshavsky. Self-checking and self-recovery in self-timed devices, Jun. 1994.

   Invited presentation on Aizu Workshop on Fault-Tolerance.

   
   

5. V. Varshavsky. Self-checking and self-recovery in self-timed devices, March 1994.

   Invited presentation at conference on Fault-Tolerance.

Others

1. Marakhovsky V. Varshavsky, V. and T.A. Chu. Global synchronization in asynchronous arrays, IEEE Computer Society, Technical Committee on VLSI in cooperation with IFIP WG 10.5, November 1994.

   Paper submitted to International Simposium on Advanced Research in Asynchronous Circuits and Systems.