Graphical Models of Computation

Models of Computation (MoC's) are abstract representations of a family of related computer-based systems. Although the word ``model'' will be kept for consistency with existing literature, it is clear that following the definitions given in the previous sections, the word ``metamodel'' would be much more appropriate. A MoC offers a particular abstract vision with a particular purpose that can be instantiated to model many different systems. Using the proper model of computation improves the development process and yields a better understanding of the system under design and its properties. Selecting the appropriate model of computation depends on the purpose but the choice is also generally conditioned by the application domain: DSP applications, for instance, will generally benefit from Dataflow models while control-intensive application mostly use Finite State Machine or similar models.

General design paradigms such as object-oriented, functional or logic may be interpreted as being models of computations. Nevertheless, such paradigms are still too abstract and generic to be really useful as a model of computation. As a matter of fact, a single paradigm may be used to model different models of computations and a single model of computation may be well consist on applying different general purpose paradigms. After having decided to use the object-oriented paradigm, much work in this thesis will be on finding the most appropriate Model of Computation it is therefore important to first understand what are the ones most related to our domain of interest.

Most useful models of computation belong to the category of ``graphical MoC's''. By graphical we are expressing the fact that according to the model, the system being modeled can be explicitly specified by a graph, being a graph a general mathematical construct formed by ``arcs'' and ``nodes''. Many MoC's are obtained by assigning a concrete semantic to arcs and nodes and by restricting the general structure of the graph (see figure 1.2). A non-exhaustive list of graphical MoC's includes: Queueing Models, Finite State Machines, State Charts, Petri Nets, Process Networks and Dataflow Networks^1.4.

Figure 1.2: Graph

Although the rest of this section will give a more detailed view of the models of interest, we will now briefly give a description of each of these models in order to have a first general overview:

• Queueing Models is a graphical model where nodes represent complex operators such as Poisson queues or decision nodes and arcs represent events/tokens/requests. They are used for performance estimation, like determining the total latency of a network of queueing nodes.
• Finite State Machines are especially useful for specifying sequential control in control-intensive tasks and protocols. An FSM graph is made up of inputs, outputs, states, initial state, next state and outs. The model is not Turing complete and it renders models that are more suitable for formal analysis.
• State Charts is a graphical model consisting on states, events, conditions and actions. Events and conditions cause transitions and there are AND and OR compositions of states.
• Petri Nets is a graphical model for describing and studying systems with concurrent, asynchronous, distributed, non-deterministic, and parallel characteristics. It consists of places, transitions and arcs that connect them. A Petri net is executed by the firing rules that transmit the marks or tokens from one place to another and such firing is enabled just when each input place has a token inside.
• Process Networks or Kahn Process Networks is a concurrent model of computation that is a superset of data flow models. As a directed graph, each arc represents a FIFO queue for communication and each node represents an independent, concurrent process.
• Dataflow Networks is a special case of Process Networks where nodes are actors that respond to firing rules.

We will now describe the last three of these models for their relation to the CLAM network model.