Computer Logical Design Laboratory

/ V. I. Varshavsky / Professor
/ Rafail A. Lashevsky / Professor
/ V. V. Smolensky / Research Associate

The Computer Logic Design Laboratory is carrying out the following Research Projects and Top-Down Education Courseware Development Projects:

• Self-Timing and Event-Driven Systems
• Hardware Support of Self-Timing and Event-Driven Systems

In 1994, the major directions and results of work on these projects were:

1. Global Synchronization of Asynchronous Arrays

The solution of this problem is based on decomposing the system to the processor stratum and the synchrostratum that plays the role of a global asynchronous clock. The synchrostratum can perform two types of global synchronization: parallel synchronization and synchronization using a system of synchrowaves. In the case of a synchronous system with two-phase master-slave synchronization, several implementations of the synchrostratum for the corresponding asynchronous systems have been designed.

2. Organizing Asynchronous Behavior in a Multiprocessor Array using Current Sensors

An analysis of existing current sensors (CS) has been made. The results displayed significant dependence of reaction time on the ratio of the maximum and minimum current detected. An improvement has been suggested to minimize the reaction time. Additional chip areas in circuits with CS have been evaluated. The results of the work allow one to estimate the real cost of using CS and suggest reasonable areas of application. Two ways of interaction between blocks with CS have been suggested.

3. Self-timed Interfaces

The possibility of organizing a single-wire bit handshake has been demonstrated and self-timed circuits of transmission/reception were developed with throughput no worse than that of double-wire circuits. Using a single-wire bit handshake allows one to transmit an $n$-binary code by $n+1$ communication lines.

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, 12(1):14--23, 1995.

   A procedure for designing a self-timed device defined by the finite automaton model is suggested. This procedure proves useful when designing these devices using the available synchronous synchronous behavior specifications. The effectiveness of the procedure is illustrated by applying it to the design of a stack memory and constant acknowledgement delay counter.

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 the 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. The method is illustrated by some examples.

3. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Self-timed data transmission in massively parallel computing systems. Integrated Computer Aided Engineering (in printing), 1995.

   Local processes in MPCS can be globally coordinated via handshake using current indication. The known current sensors are considered, the functioning of the best one is analyzed and its shortcomings are revealed. A new circuit with wide range of the measured current is suggested. The principles of control in circuits with current sensors are developed. Self-timed data exchange between local processes of the system is discussed. Transmission/reception circuits with single-wire bit handshake are demonstrated. Their transmission rate is no worse than that of double-wire circuits. They allow one to transmit combinations of $n$-bit code by $n+2$ communication lines.

1. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Asynchronous interaction in massively parallel computing systems. In V. L. Narasimhan, editor, IEEE First International Conference on Algorithms and Architecture for Parallel Processing ICA 3PP-95, volume 2, pages 481--492, Brisbane, Australia, April 1995. The University of Queensland, IEEE CS Press.

   The problems are discussed that arise when designing massively parallel computer systems. The transition from globally synchronized working of such systems to globally asynchronous behavior resolves most of them. The problems of asynchronous interaction of local processes with the system of their global coordination on the base of handshake are considered as well as the problems of self-timed data transmission between processes. If the system modules that realize local processes are not asynchronous and implemented in CMOS-technology, then, to detect the moments of the transient processes completion in them, the idea of current indication is used. A circuit of a current sensor is suggested with wide range of permissible changes of the measured current and with admissible characteristics. Two ways of organizing the interaction between circuits with current sensors are developed. The principles of self-timed data exchange between local processes of the system and data transmission by means of a dual-rail code and binary code with handshake for every bit are considered. The possibility of organizing single-wire bit handshake is demonstrated and its self-timed implementation is developed with the transmission rate no worse than that of double-wire bit handshake.

2. V. Varshavsky, V. Marakhovsky, and R. Lashevsky. Critical view on the current sensor application for self-timing in vlsi systems. In VLSI'95 Conference, Tokyo, Japan, August 1995.

   To solve the problem of global synchronization in massively parallel VLSI systems, it is necessary to organize asynchronous interaction between system blocks. The possibility of applying current sensors for detection of the end of signal transitions to construct asynchronous blocks in CMOS-technology is discussed. For known current sensors, their design principles and characteristics are analyzed. Two ways of organizing the interaction between circuits with current sensors are suggested. Stubborn problems of using the known current sensors that appear due to the imperfection of their characteristics are formulated. A current sensor is suggested that removes the major of these problems but is capable of working only with a particular circuit class. However, simulation results indicated that using even such sensors is not efficient enough.

3. A. Yakovlev, V. Varshavsky, V. Marakhovsky, and A. Semenov. Asynchronous pipeline token ring interface. In 2nd Working Conference on Asynchronous Design Methodologies, London, UK, May 1995.

   We describe the design of a speed-independent communication channel based on a pipeline token-ring architecture. We believe that this approach can help reduce some negative "analogue" effects inherent in asynchronous buses (including on-chip ones) by means of using only "point-to-point" interconnections. We briefly outline the major ideas of the channal's organization, protocol and our syntax-driven implementation of the channel protocol controller. The protocol has been recently verified for deadlock-freedom and fairness.

4. V. Varshavsky and T. A. Chu. Self-timing - tools for hardware support of parallel concurrent and event-driven process control. In Proceedings of the First International Conference on Massively Parallel Computer Systems (MPCS), pages 472--477, Ischia, Italy, May 1994. IEEE Computer Society & Euromicro, IEEE Computer Society Press.

5. V. Varshavsky and V. Marakhovsky. Fault-tolerant self-timed system mono-channel. In Technical Report of IEICE. CPSY94-14 26, pages 80--85, Tokyo, Japan, 1994. the Institute of Electronics, Information and Communication Engineers.

   The problems of designing self-timed circuitry based fault-tolerant ring communication channel for multicomputer control systems are discussed. The technical solutions suggested are the basis of the logic project of a communication channel adopter designed for a fault-tolerant airborne multicomputer system with the local area network architecture. The basic element of such an adopter is a monochannel controller consisting of the protocol automaton and the automaton of control and recovery. The approaches to self-timed realization of these automata are stated as well as the principles of monochannel self-recovery organization when a failure of some of its communication lines or the equipment connected with them occurs.

6. A. Kondratyev, A. Taubin, V. Varshavsky, M. Kishinevsky, and E. Pissaloux. Change diagram: a behavior model for very speed vlsi circuits highly parallel systems. In Proceedings of Euromicro Workshop on Parallel and Distributed Processing, pages 220--226, Malaga, Spain, January 1994. IEEE Computer Society Press, IEEE Computer Society Press.

7. V. Varshavsky, V. Marakhovsky, and T. A. Chu. Logical timing (global synchronization of asynchronous arrays). In International Symposium on Parallel Algorithm/Architecture Synthesis, pages 130--138, Aizu-Wakamatsu, Japan, March 1995. The University of Aizu, IEEE CS Press.

   The problem of global synchronization is considered for asynchronous processor arrays of arbitrary dimension and for asynchronous multiprocessor systems with an arbitrary interconnection graph. The concepts of synchronism, asynchronism synchronization, logical and physical time are discussed. Global synchronization of asynchronous systems is treated as a homomorphous mapping of an asynchronous system behavior in logical time onto the behavior of the corresponding synchronous system with a common clock functioning in physical time. The solution is based on decomposing the system to the processor stratum and synchro-stratum that plays the role of a global asynchronous clock. This decomposition requires the organization of matched interaction on the base of a handshake between the processors and synchro-stratum. For the case of a synchronous system with two-phase master-slave synchronization, a simple realization of the synchro-stratum for the corresponding asynchronous system is suggested. It is shown that, depending on the local behavior of the processors, the synchro-stratum can perform two types of global synchronization: parallel synchronization and synchronization that uses a system of synchrowaves.

8. V. Varshavsky. Asynchronous interaction in massively parallel computing systems (keynote speech). In V. L. Narasimhan, editor, IEEE First International Conference on Algorithms and Architecture for Parallel Processing (ICA 3PP-95), Brisbane, Australia, April 1995. The University of Queensland, IEEE CS Press.

1. Rafail A. Lashevsky, Lecture ``Delay-Insensitive Buses with Current Sensors" at the Department of Electronic Engineering Faculty of Engineering, Osaka University, April 1994.

2. Rafail A. Lashevsky, Report ``Current Sensors in CMOS VLSI Circuits" at the seminar ``Self-Timing and Event-Driven Systems" at the University of Aizu, February 1995.

3. Victor I. Varshavsky, Membership in ACM, 1994.