A model for parallel systems composed by mutually asynchronous modules

A model for digital parallel systems composed by mutually asynchronous modules, each of them with processing speed in general variable, is described, by means of which it is possible to realize parallel and/or pipeline computers in a systematic and correct way. Each module of a system corresponding to the proposed model has its own control part and its own operation part, and the behaviour of the entire system, called PMC system, depends exclusively on the exchange of messages among the control parts of the modules belonging to the system. Moreover the modules exchange each other data by means of queues: data held in queues and messages are the only resources shared by modules. Three rules of message exchange among modules are defined, obtaining three types of systems called PMC systems with weakly linked modules, with strongly linked modules and with strongly linked modules looking-ahead. Some ways of transmitting messages are introduced which give rise to several schemes of the control structure of the entire system. The activity of a PMC system is described by a graph; by some constraints Lmposed on this graph it is possible to define a class of systems, called PMC linear systems, into which any PMC system can be transformed. For PMC linear systems, with regard to the rules of message exchange, general conditions are given under which such systems are determinate and deadlock-free.