This is an attempt to outline the nature of my work sans the jargon ... A summary of work done and a list of publications are also available.
Collaborators : L.Kazerouni, R.K.Shyamasundar
One of the various approaches tried to minimize computation time for large numerical problems was the use of a large network of relatively simple processors designed to work in close unison in order to solve the problem at hand. The perceived advantage of such a system was the relative cheapness of the individual processors involved and the potential to add to the network [or scale] at will. Many variations on this theme are in vogue today. A systolic array is one of them.
Systolic Arrays consists of a large number of processors connected together in some regular pattern such that each processor is connected to its nearest neighbours. In addition, each of these processors run the same(or similar) program. Each processor can be thought of a unit that takes in data (from a neighbouring node), does some computation on it and passes on the result (to its neighbour). This imagery being very much like the way the heart pumps blood, the name systolic array stuck.
Well, systolic arrays didn't turn out to be the panacea for all of todays numerical problems. By and by systolic arrays came to be used widely to solve problems that could be characterized by what are called recurrence equations. Methods were developed whereby problems that could be characterized by recurrences were solvable using systolic arrays.
Initially methods catered largely to a subclass of recurrence equations called Uniform Recurrence Equations. Most methods also required considerable user intervention in the process of translating from recurrence equations to systolic programs.
Our contribution has been the development and further refinement of a method/algorithm to translate (or map) a problem characterized by linear recurrences (that can be computed) onto systolic arrays in an efficient manner. The method is applicable to a larger class of problems and does not require user intervention in making educated choices along the way. Further, the method is geared towards generating a solution for a general n-dimensional virtual array which is then transformed to fit a real interconnection pattern.
With the reduction in the cost of VLSI components, the use of special purpose hardware is becoming an economically viable technique for solving todays numerical problems. A case in point is the use of Field Programmable Gate Arrays to implement specialized image processing algorithms.
Collaborators : R.K.Shyamasundar
Reactive programs have to react to environmental stimuli and respond within externally imposed time constraints. Reactive programs assume importance in areas like robotics, process control and fly-by-wire systems. Of major interest in the area is the possibility of mechanically verifying code, especially those put to use in safety critical environments. ESTEREL is deterministic synchronous programming paradigm that addresses issues involved in reactive programming, including verification.
CRP is an extension of ESTEREL allows for a network of ESTEREL nodes to communicate over an asynchronous medium. Further, all the proof techniques that were applicable in the case of pure ESTEREL still are! All communication between these nodes are implemented using message passing over named channels.
Our contribution has been the development and analysis of viable protocols for the implementation of CRP. We have shown that these protocols are deadlock free, efficient, and flexible enough to allow for different modes of communications depending on application requirement. Implementations for the same on a network of SunSparcs are in progress.
These concepts are gaining ground in industrial practice especially in the area of military avionics.
Collaborators : R.K.Shyamasundar
Common knowledge refers (informally) to a state where ever entity knows a fact, knows that all the others know the fact and so on. In a sense we can consider this state to be one of perfect knowledge about some fact.
In the context of communicating processes, this roughly corresponds to each pair of communicating processes knowing the exact status of the communication that took place between them. In particular, in should never be the case that one process assumes a communication to have taken place when in fact the corresponding process believes it has failed to communicate. such situation lead to inconsistencies with respect to what is considered as fact within the network.
Our work focusses on the interplay between preemption and common knowledge. We have shown that it is impossible to attain common knowledge in a system which supports preemption. This implies that the asymmetry that exists between the sender and receiver in CRP can never be totally eliminated. We have also shown that with the introduction of a freeze, we can attain common knowledge at the cost of reactivity.
Collaborators : R.K.Shyamasundar, Gérard Berry, S.Ramesh
Real life situations demand the ability to specify independent clocks to various submodules that constitute a system. A case in point is a typical computer, where the CPU, memory modules and the I/O subsystem run on different clocks.
A generalization of ESTEREL, M-EST allows for the specification of different clocks for modules of an ESTEREL program. The use of specific signals for clocking introduces the need for latching a signal. This facility also allows one to deal with asynchrony.
This work is currently under development, and we are in the process of understanding the subtleties involved in the use of latched signals in an environment that supports preemption.
One new concept that came about was the notion of shallow suspension. Essentially, it is a form of suspension which permits some constituent parts to continue functioning. It is now evident that to preserve modularity, one has to support shallow preemption.
Collaborators : Albert Benveniste, Claude Jard, R.K.Shyamasundar
Synchronous systems those in which the occurrences of inputs and the generation of corresponding outputs occur instantaneously. In contrast, asynchronous systems only require that outputs follow inputs and the delay between inputs and outputs are disregarded.
For ease of study, it is often desirable to model one kind of system as the other to study specific properties. It then becomes necessary to study the necessary and sufficient conditions each system must satisfy such that the transformation becomes feasible.
Our work in this area focuses on characterising synchronous and asynchronous systems in a rigorous manner and also identifying the requisite criteria that each must satisfy to enable transforming one kind into the other.