Interaction nets are a particular kind of graph rewriting system that have many properties that make them useful for capturing sharing and parallelism. There have been a number of research e orts towards implementing interaction nets in parallel, and these have focused on the implementation technologies. In this paper we investigate a related question: when is an interaction net system suitable for parallel evaluation? We observe that some nets are cannot bene t from parallelism (they are sequential) and some have the potential to be evaluated in a highly parallel way. This rst investigation aims to highlight a number of issues, by presenting experimental evidence for a number of case studies. We hope this can be used to help pave the way to a wider use of this technology for parallel evaluation.
Interaction nets are a model of computation based on a restricted form of graph rewriting: the rewrite rules must be between two nodes on the left-hand side, be local (not change any part of graph other than the two nodes), and there must be at most one rule for each pair of nodes. These constraints have no impact on the expressive power of interaction nets (they are Turing complete), but they o er a very useful feature: they are con uent by construction. Taken with the locality constraint they lend themselves to parallel evaluation: all rewrite rules that can apply can be rewritten in one parallel step.
The question that we propose in this paper is: when is a particular interaction net system well suited for parallel evaluation. More precisely, are some interaction nets \more parallel" than others? A question that naturally follows from this is can we transform a net so that it is more suited for parallel evaluation. Once we have understood this, we can also ask the reverse question: can a net be made sequential? The purpose of this paper is to make a start to investigate these questions, and we begin with an empirical study of interaction systems to identify when they are suitable for parallel evaluation or not.
We take a number of typical examples (some common ones from the literature together with some new ones we made up for this paper) to see if they bene t from parallel evaluation. In addition, we make some observations about how programs can be transformed so that parallelism is more useful. Using these examples, we give some heuristics for getting more parallelism out of an interaction net system.
Related work. There have been a number of studies for the parallel
implementation of interaction nets: Pinto [
In the graphical rewriting system of interaction nets [
x1 xn Nodes are drawn variably as circles, triangles or squares. A net built on is an undirected graph with nodes at the vertices. The edges of the net connect nodes together at the ports such that there is only one edge at every port. A port which is not connected is called a free port.
Two nodes ( ; ) 2 connected via their principal ports form an active pair, which is the interaction nets analogue of a redex. A rule (( ; ) =) N ) replaces the pair ( ; ) by the net N . All the free ports are preserved during reduction, and there is at most one rule for each pair of agents. The following diagram illustrates the idea, where N is any net built from .
xn x1
The most powerful property of this system is that it is one-step con uent: the order of rewriting is not important, and all sequences of rewrites are of the same length (in fact they are permutations). This has practical consequences: the diagrammatic transformations can be applied in any order, or even in parallel, to give the correct answer. It is the latter feature that we develop in this paper.
We de ne some notions of nets and evaluation. A net is called sequential if there is at most one active pair that can be reduced at each step. We say that a net is evaluated sequentially if one active pair is reduced at each step. For our notion of parallel evaluation, we require that all active pairs in a net are reduced simultaneously, and then any redexes that were created are evaluated at the next step. We do not bound the number of active pairs that can be reduced in parallel. We remark that the number of parallel steps will always be less than or equal to the number of sequential steps (for a sequential net, the number of steps is the same for sequential and parallel evaluation).
As an example, consider unary numbers with addition. We represent the following term rewriting system add(Z,y) = y add(S(x),y) = add(x,S(y)) as a system of nets with agents Z, S, +:
Z
S + together with two rewrite rules: We observe that addition of two numbers is sequential: at any time there is just one active pair, and reducing this active pair creates one more active pair, and so on. In terms of cost, reducing add(n,m) requires n + 1 interactions. If we consider the net corresponding to the term add(add(m; n); p), then the system is sequential, and the costs are now 2m + n + 2. Using associativity of addition, the situation changes signi cantly. The net corresponding to add(m; add(n; p)) has sequential cost m+1+n+1 = m+n+2, and parallel cost max(m+1; n+1). This is signi cantly more e cient sequentially, and moreover is able to bene t from parallel evaluation. The example becomes even more interesting if we change the system to an alternative version of addition: add(Z,y) = y add(S(x),y) = S(add(x,y)) The two interaction rules are now: +
+ =)
S + =)
S + Z
Unlike the previous system, the term add(add(m; n); p) already has scope for parallelism. The sequential cost is now 2m + n + 2 and the parallel cost is m + n + 2. But again, if we use associativity then we can do even better and achieve sequential cost m + n + 2 and parallel cost max(m + 1; n + 1) for the term add(m; add(n; p)).
These examples illustrate that some nets are sequential; some nets can use properties of the system (in this case associativity of addition) to get better sequential and parallel behaviours; and some systems can have modi ed rules that are more e cient, and also more appropriate to exploit parallelism. The next section gives examples where there is scope for parallelism in nets. 3
The previous arithmetic example demonstrates that some systems are more useful than others for parallel evaluation. In this section we give some empirical case studies for a number of di erent systems to show that when a suitable system can be found, the parallel evaluation gives signi cantly better results than sequential evaluation.
Fibonacci. The Fibonacci function is a good example where many recursive calls generate a lot of possibilities for parallel evaluation. We build the interaction net system that corresponds to the term rewriting system: fib 0 = fib 1 = 1 fib n = fib(n-1) + fib(n-2)
Using a direct encoding of this system together with addition de ned previously, we can obtain an interaction system:
Fib Fib2
Z Z ⇒ ⇒
S Z S Z
Fib Fib2
S S ⇒ ⇒
Fib2 Fib
Fib
Dup S S S Z S
S →
Fib The following is an example of rewriting:
Fib fib 3
S S S Z →
Fib2 +
Fib
S
→ Dup
Fib S Z
S Z +
Fib fib 1 + fib 2
S S Z With respect to the two versions of the addition operation introduced in Section 2, we call the former a batch operation, which returns the computational result after nishing processing all of the given data, and the latter a streaming operation, which computes one (or a small number of) elements of the given data and returns partial parts of the computational result immediately. The graphs in Figure 1 show the number of interactions in each version, where we plot sequential steps against parallel steps to indicate the rate of growth of each one. Both graphs demonstrate that the sequential computation is exponential, while the parallel one is quadratic. We remark that, in the parallel execution, the numbers of steps with the streaming operation are less than a half of the numbers with the batch operation. This result is illustrated in the third graph in the gure.
By allowing attributes as labels of agents, we can include integer numbers in agents. In addition, we can use conditional rewritings, preserving the one-step con uence, when these conditions on attributes are disjoint. In this case, the system of the Fibonacci function is written as follows:
Fib Fib Fib n n n n=0 ⇒ n=1 ⇒ 1 1 not(n=0) and not(n=1) ⇒
Add
Fib Fib n-1 n-2
Add
(n) n m ⇒ ⇒
(n) n+m There is very little di erence between the load balances of fib (n 1) and fib (n 2), and thus this system gives the following graph, demonstrating that the growth rate for parallel computation is linear, while the sequential rate is exponential: 1200 1000 800 Ackermann. The Ackermann function is de ned by three cases: ack 0 n = n+1, ack m 0 = ack (m-1) 1, and ack m n = ack (m-1) (ack m (n-1)). We can build the interaction net system on the unary natural numbers that corresponds to the term rewriting system as follows:
A y r
Z ⇒
S y
r fib n (batch additive operation) fib n (streaming additive operation) 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12
14 n Z
A A A A
S Z 2 1 x r ⇒ r
Pred x x r ⇒
Dup where the agent Dup duplicates S and Z agents. The following is an example of rewriting: Dup
A
A
Z →
S Z
A2 y → Pred
A n n not(n=0) ⇒
S Z
A A x
S Z
A m-1
1 m-1 A
Pred
A
r m n-1 1 0 When we use numbers as attributes, the system can be written as: (a) unary natural numbers (b) integers On the other hand, in the case of the computation on unary natural numbers, the A2 interacts with the streaming result of ack 0 (ack 1 0): ack 3 n
seqpuaernatlilaell n S Z A A A
S Z m-1
1 m-1 A m-1 A m n-1 m S Z
S Z
A2 A2(m) A2(m) A2(m) →
Z
A n n S n=0 ⇒ ⇒ A
A
Z
A2
S m m=0 ⇒ m not⇒(m=0) m S ⇒ ⇒
S A2(m) n+m
Sum (n+1) Here, borrowing the S agent to denote numbers greater than 0, we change the rules, especially in the case of ack 0 n, Addn into S as follows: Thanks to the introduction of the S agent, A2 can be processed without waiting for the result of ack 1 0. This therefore gives a streaming operation:
Sum (0) Sum (0) A2(1)
S
In addition, the benchmark graph shows that the improved system is more e
cient and more appropriate to exploit parallelism:
ack 3 n (integers, streaming)
ack 3 n (integers, in parallel)
A
n
Sorting. Bubble sort is a very simple sorting algorithm that can bene t from
parallel evaluation in interaction nets. One version of this algorithm, written in
Standard ML [
if x > x2 then x2::(bsortsub (x::xs)) else x::(bsortsub(x2::xs)) | bsortsub x = x fun bsort t = let val s = bsortsub t in if t=s then s else bsort s end; Using a direct encoding of this program, we obtain the interaction system: BS BS
Nil x ⇒ ⇒
Nil EQn(x) y y x = y ⇒ not⇒(x= y) Nil n ⇒ ⇒
Nil Nil n n
y For instance, a list [3; 4; 2] is sorted as follows: 3 4 2
Nil →
EQn(3) where the and agents are de ned as a duplicator and an eraser:
EQ EQ x ⇒ ⇒ l i
N This system shows that parallel bubble sorting is linear, whereas sequential evaluation is quadratic, as indicated in the graph below.
BS → → → → →
BS BS
BS BS BS BS 2 3
Nil x 4 3 3 2 B(2) 3 However, it contains the equality test operation by EQ and EQn to check whether the sorted list is the same as the given list. In comparison to the typical functional programming languages, interaction nets require copying and erasing of lists for the test that can cause ine cient computation. Moreover, the sorting process is applied to the sorted list by B again and again. Taking into account that the B moves the maximum number in the given unsorted list into the head of the sorted list, we can obtain a more e cient system: For instance, a list [3; 4; 2] is sorted as follows: The system reduces the number of computational steps signi cantly, and gives the best expected behaviour as follows:
B(x) Nil y y ⇒ x y ⇒
direct improved 10 20 30 50 60
70 40 length 0 Summary/discussion. All these examples show the scope for harnessing parallelism from an empirical study: some systems do not bene t, whereas others allow quadratic computations be executed in linear parallel complexity. However, these results give a avour of the potential, and do not necessarily mean that they can be implemented like this in practice. 4
In this section we examine the potential of parallelism illustrated by the graphs in Section 3, by using a multi-threaded parallel interpreter of interaction nets, called Inpla, implemented with gcc 4.6.3 and the Posix-thread library.
We compare the execution time of Inpla with other evaluators and interpreters. The programs were run on a Linux PC (2.4GHz, Core i7, 16GB) and the execution time was measured using the UNIX time command as the average of ve executions.
First, in executions of the pure interaction nets, we take INET [
Next, we compare Inpla with Standard ML of New Jersey (SML v110.74) [
Next we analyse the results of the parallel execution in Inpla by using graphs in Section 3, which show the trends of steps in parallel execution on the assumption of the unbounded resources. We may write \parallel(n)" in the following graphs to make explicit that Inplan is used for the experiment.
Fibonacci function. Figure 3 shows the execution time of each program for Fibonacci function by using Inpla. We see that each the sequential execution is exponential as shown in the graphs on the assumption of the unbounded resources. The increase rate of execution time in the parallel execution by Inpla gradually becomes close to, according to increasing the number of threads, the trends of the parallel computation in the graphs on the assumption.
We note that, in the computation of unary natural numbers, the execution of the streaming version is slower than the batch version as shown in the graph on the left side in Figure 4. The graph on the right side shows the ratio of steps in the streaming version to steps in the batch version on the assumption of the fib n (unary natural numbers, batch-add, Inpla) 6.0 fib n (unary natural numbers, streaming-add, Inpla) 6.0 unbounded resources. The ratio becomes around 0.4 according to increasing n in ack 3 n. This means that there is a limited bene t of the parallelism, even if we assume unbounded resources. In the real computation, the cost of parallel execution more a ects the execution time in comparison to the bene t of the parallelism, and thus the streaming version becomes slower.
Ackermann function. Figure 5 shows the execution time of each program for Ackermann function by using Inpla. We see that, except for the batch operation version, the parallel computation follows well the trends on the assumption of the unbounded resources. On the other hand, the parallel execution of the batch operation version takes quite a long time compared to the streaming version. This is because, in the unbounded resources, not only that there is no signi cant di erence in sequential and parallel execution, but also that there is a cost of parallel execution such as scheduling of threads execution uselessly. These are some of the reasons why the parallel execution does not always have good performance, but are improved in the streaming version.
Bubble sort. Figure 6 shows the execution time of the two programs for Bubble sort using Inpla. As anticipated by the graphs on the assumption of the unbounded resources, we see that the improved version performs best as expected.
Fig. 5. The execution time of Ackermann function by Inpla Although discussed for many years, we believe that parallel implementations of interaction nets is still a very new area and much needs to be done. In this work we have assumed unbounded resources in terms of the number of processing elements available. This is a reasonable assumption with GPU when many thousands of processing elements are available. We analysed the execution result of the multi-threaded execution by using the investigation result on the assumption, and also showed that, on the one hand, these perform as the best expected, and on the other hand, some of execution results take something away from the investigation results due to an overhead of using parallel technologies as anticipated by the investigation. We hope the ideas in this paper may help in moving this work forward.