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 N1xN1. The left-hand process calculates the function f, then does a test N2->N1+N3. If the behaviour arrives in N1 then it repeats. If the behaviour arrives in N3 it waits until also the second component (which has meanwhile been calculating g) arrives in N3. They then both make a synchronized action returning to N1. And so on.
It is a rather simple abstract example, but already the state space of the composite has 9 summands NixNj. (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 N1xN1. (I wont bother to specify the precise spans between the summands.)
Notice that the graph is non-deterministic at N3xN3 - 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 N1xN1). 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.)
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 N1xN1. The left-hand process calculates the function f, then does a test N2->N1+N3. If the behaviour arrives in N1 then it repeats. If the behaviour arrives in N3 it waits until also the second component (which has meanwhile been calculating g) arrives in N3. They then both make a synchronized action returning to N1. And so on.
It is a rather simple abstract example, but already the state space of the composite has 9 summands NixNj. (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 N1xN1. (I wont bother to specify the precise spans between the summands.)
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
posted by Unknown at 6:03 AM
0 Comments:
Post a Comment
<< Home