/ V. B. Marakhovsky / Professor
/ Zi Xue Cheng / Assistant Professor
/ Kshirasagar Naik / Assistant Professor
Computer Networks Laboratory is working in four directions within Research Projects and Top-Down Education Course-ware Development Projects:
1. Logical-timing and Decentralized Control in Computing Systems
Refereed Journal Papers
In this paper, we show that by suitably selecting a notation to construct synchronization requirement specifications (SRS) for multimedia presentation we can express the timing characteristics at an abstract level, verify the specification, and obtain a hardware implementation through a sequence of transformations of the specification. First, we introduce the notion of a well-formed SRS and its hardware model. Second, we model an SRS as a timed Petri net and interpret the transitions of the net as hardware signals. To obtain logic functions from the SRS, we simplify the net and obtain a signal transition graph satisfying the unique state coding property. Finally, we show how to obtain a logic-level design of synchronizers.
A procedure of designing a self-timed device defined by the model of finite automaton is suggested. In accordance with the chosen automaton standard implementation structure from the automaton transition/output graph one derives the Signal Graph Specification that then is processed by the formal synthesis procedure for self-timed implementation. The design procedure is illustrated by two examples: Stack Memory and Counter with Constant Acknowledge Delay.
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.
In this paper, we first propose an ADT specification Model which defines a data carrier part of an ADT as a combination of constructors of four patterns. Based on the specification model, a similarity definition is given. Furthermore we have designed the support system. Finally, in order to evaluate the effectiveness of the system, we experimented with data types of service and protocol in data communication field. From the evaluation, the effectiveness of the system is ensured.
No abstract.
In this paper, we propose a scheme for distributed implementation of the disabling operator in LOTOS. Our main contribution lies in transforming the operational semantics of the disabling operator to a distributed implementation. The distributed implementation is specified as a hierarchy of finite-state machines (FSM) which communicate among themselves by message passing. We define an agent process for each behavior expression not containing any disabling operator and a coordinator process for each instance of the disabling operator. After selecting an event, an agent process requests a coordinator process whether it can execute the event. The coordinator processes collectively keep track of the status of all the agent processes and accordingly allow or disallow an agent to execute the event. A three-way interaction mechanism between an agent and a coordinator and between two coordinators is defined. Detailed behaviors of the agent and coordinator processes are specified as communicating FSMs, which are easy to implement.
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.
The problem of global synchronization is solved for asynchronous processor arrays and multiprocessor systems with an arbitrary interconnection graph. Global synchronization of asynchronous systems is treated as a homomorphic 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; the latter plays the role of a global asynchronous clock. For the case of a synchronous system with two-phase master-slave synchronization, a simple implementation of the synchro-stratum for the corresponding asynchronous system is proposed. It is shown that, depending on the local behavior of the processors, the synchro-stratum is able to perform two types of global synchronization: parallel synchronization and synchronization that uses a system of synchro-waves.
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.
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.
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.
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.
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.
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.
First-order multiparty interactions, a generation of multiparty synchronization, are a powerful communication mechanism that allows a set of processes to enroll into different roles of an interaction and to execute the interaction in a synchronous way, and guarantees conflict interactions to be executed exclusively. It is not a trivial problem to implement first-order multiparty interactions in a network environment. The implementation has to maintain the synchronous and exclusive properties mentioned above, be fair and make progress. Recently, Joung et al. gave a definition of the first-order multiparty interactions and presented a distributed algorithm with message complexity $O(|P|^2)$ as solution to the problem (Joung et al.), where $|P|$ is the number of set of processes which may potentially enroll into some roles of the interaction. So far Joung's algorithm is the only one for first-order multiparty interactions by our knowledge. In Joung's algorithm, a coordinator is devised for each process, and each coordinator tries to capture other processes for establishing a quorum. The Joung's algorithm is not a fully distributed one due to the following two reasons: (1) every coordinator has to know and keep global information about the potential enrollment relation between processes and roles, and (2) the local computation time complexity is unbalanced. In this paper, we propose a new distributed algorithm for implementing first-order multiparty interactions based on a new implementation model, in which a role manager is devised for each role. Our algorithm solves the problem with $O(|R|^2 \cdot |P|)$ messages per interaction as opposed to $|P|^2$ messages required in (Joung et al.), where $|R|$ is the number of roles of the interaction and $|P|$ is the number of processes. Our algorithm is more efficient than that in (Joung et al.) when $|R|^2 < |P|$. Furthermore our algorithm is closer to the fully distributed one than that in (Joung et al.) in the sense that (1) every process (role manager) only knows its adjacent role managers (processes), and (2) the time complexity of local computation in each process and role manager is equal.
We consider the problems of distributed ranking and sorting on a Coterie, a communication structure which has proven to be a good candidate as underlying interconnection network for distributed processing. Ranking and sorting problems are harder than a consensus one, a vital and well studied problem in distributed processing, in that the later one computes for only one function (e.g. summation), while the former one actually performs $n$ functions, as ranking is to rank the key in each of $n$ sites. The currently best known decentralized consensus protocols on a coterie uses $O(n\sqrt{n})$ messages, and requires two rounds of message exchange. In this paper we show that both ranking and sorting can be done on a coterie with the same message complexity although the problems we investigate are much harder. We first present a two-round ranking algorithm which requires only $O(n\sqrt{n})$ messages. Then using this ranking algorithm, we obtain a sorting algorithm which also uses only $O(n\sqrt{n})$ messages, but requires two more rounds of message exchange. Our schemes are optimal in the sense that the lower bound of messages needed for achieving a consensus is $\Omega(n\sqrt{n})$.