### The algebra of processes VII

PARALLEL PROGRAMMING in Span(Graph)

Last post I promised to give an example of a parallel program. Here is a very simple one which is the parallel composite of two components both having state space N+N+N (N= natural numbers).

I have distinguished the different summands by subscripts to make the description of the composite clearer:

The first component is a span from 1 to {a,ε}, the second from {a,ε} to 1. The initial value I have in mind is a pair of numbers in N

It is a rather simple abstract example, but already the state space of the composite has 9 summands N

Let me at least draw the graph of the composite, including the summands reachable from N

Notice that the graph is non-deterministic at N

I forgot to say that the programming of each process (component) is done sequentially in Cospan(Graph/{a,ε}).

Another remark: with the finiteness assumptions we have made processes can only communicate by a finite number of signals. To pass (or share) data would require different finiteness assumptions which would allow the alphabets to be infinite.

Next post I would like to discuss the abstract context and describe the distributive laws.

(It seems now that I will not be able to attend the conference for which I wrote the original abstract so I guess these blog posts have been useful after all.)

Last post I promised to give an example of a parallel program. Here is a very simple one which is the parallel composite of two components both having state space N+N+N (N= natural numbers).

I have distinguished the different summands by subscripts to make the description of the composite clearer:

The first component is a span from 1 to {a,ε}, the second from {a,ε} to 1. The initial value I have in mind is a pair of numbers in N

_{1}xN_{1}. The left-hand process calculates the function f, then does a test N_{2}->N_{1}+N_{3}. If the behaviour arrives in N_{1}then it repeats. If the behaviour arrives in N_{3}it waits until also the second component (which has meanwhile been calculating g) arrives in N_{3}. They then both make a synchronized action returning to N_{1}. And so on.It is a rather simple abstract example, but already the state space of the composite has 9 summands N

_{i}xN_{j}. (It would have been nice to program the dining philosophers and their thoughts but I haven't the patience here.)Let me at least draw the graph of the composite, including the summands reachable from N

_{1}xN_{1}. (I wont bother to specify the precise spans between the summands.)Notice that the graph is non-deterministic at N

_{3}xN_{3}- there is no guarantee that both processes will not idle together in this summand indefinitely (this was why I said in the arxiv paper that eventually (in the Italian sense) they will proceed to synchronize on a and return to N_{1}xN_{1}). To make the system deterministic would require more programming.I forgot to say that the programming of each process (component) is done sequentially in Cospan(Graph/{a,ε}).

Another remark: with the finiteness assumptions we have made processes can only communicate by a finite number of signals. To pass (or share) data would require different finiteness assumptions which would allow the alphabets to be infinite.

Next post I would like to discuss the abstract context and describe the distributive laws.

(It seems now that I will not be able to attend the conference for which I wrote the original abstract so I guess these blog posts have been useful after all.)

Labels: category theory, computing

## 0 Comments:

## Post a Comment

<< Home