/ V. I. Varshavsky / Professor
/ Rafail A. Lashevsky / Professor
/ V. V. Smolensky / Research Associate
The Computer Logic Design Laboratory carried out the following Research Projects:
In 1996, the major directions and results of the work on these projects were:
1. Data-Controlled Delays in the Asynchronous Design. In order to increase the efficiency of using padding delays to produce signals of transient process completion, we suggest to use data-controlled incorporated delays in the cases when the variations of transient process duration are determined by the sets of input signal values. Data controlled delay is illustrated by an example of adder design.
2. Asynchronous Control Device Design by Net Model Behavior Simulation. The design is based on the compilation of standard circuit modules corresponding to PN fragments into a net modeling PN behavior. Modifications of the known modules, a number of new module types, and the procedures of minimization are developed.
3. Hardware Support of Discrete Event Coordination. To build asynchronous control circuits that coordinate process interaction, the method of direct translation of interact specification using Petri nets is being developed.
4. Towards Self-Checking and Self-Recovery in Self-Timed Embedded Systems. A general trend in design of embedded systems is an increasing role of hardware in providing their main functionality. Classical hardware designs for dependability use clock and are dependent on the clock distribution logic, which itself becomes more complex. Asynchronous circuits are posed as a promising alternative for embedded systems. Self-timed designs offer inherent self-checking properties due to their ability to acknowledge the completion of transient processin subcomponents.
5. Self-Timed Data Transmission in Massively Parallel Computing Systems. The current sensor with wide range of the measured current is suggested. The principles of control in circuits with current sensors are developed. Self-timed transmission/reception circuits with single-wire bit handshake are suggested which allow to transmit combinations of n-bit code by n+2 communication lines.
6. Global Synchronization of Asynchronous Arrays in Logical Time. Our approach is decomposing the asynchronous array to synchro-stratum which acts as a distributed asynchronous clock and automata stratum whose automata have a construction similar to that of the synchronous prototype array automata. For various disciplines of prototype synchronization, the corresponding variants of synchro-stratum implementation for the asynchronous analogue are developed.
7. vMOS Threshold Gates. Using MOS-transistor with floating gates (vMOS) for building threshold logics is invesigated. Design methodology for static and clicked vMOS circuits is developed. Threshold gate with alterable input weights and threshold is proposed.
8. Logic Design for Nanoelectronics. The problems are considered which occur in logical design of the next generation of integral circuits based on quantum devices and nanotechnology.
Refereed Proceeding Papers
The problem of global synchronization in massively parallel systems is discussed for the level of models represented by asynchronous cellular automata arrays. Synchronization is called global if a given asynchronous automata array functions in logical time so that its behavior can be homomorphously mapped to the behavior of the prototype synchronous system in physical time. Our approach is decomposing the asynchronous array to synchro-stratum which acts as a distributed asynchronous clock and automata stratum whose automata have a construction similar to that of the synchronous prototype automata. For various disciplines of prototype synchronization, the corresponding variants of synchro-stratum implementation are discussed for the asynchronous analogue.
System time has a dual nature. On the one hand, artificial systems function in natural physical time. On the other hand, the behavior of artificial systems is specified in artificial logical time. The article is devoted to the key problem of organizing temporal behavior of systems (System Timing), which is the interaction between physical and logical times. Algebraic properties of causally determined systems and the interface between physical and logical times are discussed. Decomposition of the system to Synchro-Stratum and Processor-Stratum is introduced. Synchro-Stratum is interpreted as a distributed asynchronous system clock. Hardware implementation of Synchro-Stratum is considered along with some properties of its behavior.
The problem of global synchronization for asynchronous cellular automata arrays is considered. Global synchronization of an asynchronous system is treated as a homomorphic mapping of its behavior in logical time onto the behavior of the corresponding synchronous prototype system that functions in physical time. Here we developed the idea of decomposing an asynchronous array to the automata stratum (close to the synchronous prototype array with cells modified to organize timing handshake) and synchronization stratum which functions as a distributed asynchronous clock. We considered various disciplines of prototype timing and the corresponding synchro-stratum implementations.
In massively parallel and distributed systems, as they grow along with the complexity of the tasks they solve, the share of multi-task regimes, such as real-time control problems, multimedia, signal and image analysis and processing, increases. In the presented paper we discuss a mathematical framework for the organization of resource sharing to attain global maximum in computer performance when we have limited resources, such as common memory, channels and so forth. Local strategy of optimization is considered that leads to the optimal distribution of common resources.
Using novel physical principles and technology development, on the one hand, provide new logical and architectural possibilities and, on the other hand, pose a lot of new problems. By the examples of Tunneling Resonant Transistors, Quantum Dot Cells and CMOS-like Quantum Devices, these possibilities are demonstrated along with some problems to be solved for their efficient usage.
Asynchronous design technique has an approach of using padding delays to produce signals of transient process completion. In order to increase the efficiency of this approach, we suggest to use data-controlled incorporated delays in the cases when the variations of transient process durations are determined by the sets of input signal values. The control over the value of an incorporated delay is illustrated by an example of asynchronous adder design. The results of PSPICE simulation confirm the efficiency of this approach.
We discuss the problem of designing asynchronous control devices for discrete event coordination specified by a Petri net model. The design is based on the compilation of standard circuit modules corresponding to PN fragments into a net modeling PN behavior and on the semantic interpretation of the modeling circuit. The impossibility of asynchronous implementation of the indivisible operation of marking change at the circuit level leads to the necessity of modeling PN with modified rules of marking change. Modifications of the known modules, a number of new module types, the rules of the module connections, and the procedures of minimization are given that considerably improve the quality of the obtained solutions in terms of both speed and area. The design ``reefs'' are fixed. The minimization procedures are usually associated with a change of marking change rules producing the problems of providing the equivalence of the initial and modified PNs.
An approach to design asynchronous systems that coordinate concurrent discrete events of an arbitrary physical nature is discussed. To build asynchronous control circuits that coordinate process interaction, the method of direct translation of interact specifications using Petri nets is being developed. Modifications of the known modules and a number of new modules modeling fragments of Petri nets are given. These modules considerably improve the quality of the obtained solutions. The design ``reefs'' are fixed. The minimization procedures are associated with a change of marking change rules.
Embedded systems often have a limited scope for human intervention in their operation and maintenance. A careful distribution of fault-tolerance responsibilities between hardware and software components is therefor a critical factor of dependability in such systems. A general trend in design of embedded systems is an increasing role oh hardware in providing their main functionality. Classical hardware designs for dependability use clock and are therefore dependent on the clock distribution logic, which itself becomes more complex. Asynchronous circuits are posed as a promising alternative especially for embedded systems, mainly due to their potential for lower power consumption and lower electro-magnetic interference. Additionally, asynchronous designs offer inherent self-checking properties due to their ability to acknowledge the completion of transient in subcomponents. This presentation focuses on a number of techniques for self-checking and self-recovery available in self-timed systems and points to some new challenges.
Local processes in MPCS can be coordinated by asynchronous system of global synchronization via handshake using current sensors for detection of the transient processes completion. The known current sensors are considered, the best one is analyzed and its shortcomings are revealed. Current sensor 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.
The Applied Semiotic approach gives the possibility of such control system creating which would ensure the acceptable control over dynamic nonstationary objects under conditions of incomplete information about objects and environment. The traditional Cybernetic approach has got no efficient models and methods for such objects control. The Applied Semiotic approach to control can lead to especially appreciable practical results in such areas as economy, policy, defense, etc. where control synthesizing are accomplished in dynamic nonstationary environment and are based very often on incomplete, inaccurate and contradictory information.
Semiotic models extend the concept of logical formal system. They describe dynamic systems the states of which are formal systems and transitions between the states are determined by facts/situations external for the system. Semiotic models make it possible to describe the behavior of open systems or systems the knowledge of whose behavior is not complete. This work demonstrates how semiotic models can be used for the aims of control in large systems and for the organization of semiotic knowledge bases.
Semiotic models and mechanisms of their usage permit both to develop the applied software system adding into it new knowledge about subject area and mathematical models and methods and (maybe this is more important) to choose by system itself the models and methods are most adequate to solve entering into it problems.
A novel approach to kanji look-up in a Japanese-English hyperdictionary is suggested that is based on an original classification of kanji elements, properly organized user-friendly menu and three modes of search.