PLACE |
spec |
solutions |
Cilk |
Cilk is only different from C in its support for concurrency. The reason to write a program in Cilk is that we want it basically in C, but concurrent. In the case of the RPN calculator, one thing that can be parallelized is the evaluation of subexpressions. For example, in the expression 5 1 + 2 / 7 2 + *
the subexpressions 5 1 + 2 /
and 7 2 +
can be evaluated concurrently in order to arrive at 3 9 *
. The subexpressions can be further parallelized, down to single numbers.
In order to make use of concurrency, we have to find, for any given operator, which parts of the expression yield the values of that operator's arguments – the span of the operator. We saw how to do this in the general discussion of the problem. The program shown below ‘compiles’ an expression from an input string by successively extracting tokens from it and determining each token's type (number or operator), value (for numbers), and span. This is done in the procedure compile
, which builds a sequence of tokens and returns their number or -1
, the latter signifying a syntax error.
The first loop in compile
reads an input line into the buffer pb
. The second one then cuts tokens from the line and parses and stores each one as said. A sequence expr
is thus being built up of the ‘compiled’ tokens. For each element of expr
its oper
field is 0
for a number, and one of '+'
, '-'
, '*'
, and '/'
for an operation.
Both pb
and expr
are dynamic arrays, their sizes being augmented as needed by calls to realloc
.
Once compile
creates the sequence expr
, it remains for eval
to work backwards on it in order to evaluate the expression. The integer parameter of eval
is the index within expr
from where the evaluation for the current call of eval
starts.
Note that for all indices n
within expr
the subexpression whose evaluation starts at n
comprises the elements of expr
in the index range [expr[n].span,n]
. If expr[n]
is a number, then expr[n].span = n
holds and therefore that range contains a single element: the number itself.
eval
looks like a recursive procedure, because it contains calls to itself, but it isn't really recursive. Instead, the two calls to eval
are separate threads, executed concurrently to each other and to the thread that spawn
s them, and joined (sync
ed) again with that thread after they produce the results of the subexpressions. The initial call to eval
in main
is also spawn
ed as a separate thread and sync
ed back to the main one as it finishes.
On the other hand, were the cilk
, spawn
, and sync
words not present in the program, eval
would be a sequential recursive procedure, and the whole program would still be a correct implementation of the calculator – in plain C. Note that the computation and use of span
values, and therefore also the eval
's parameter, would then be superfluous as the recursive evaluation in eval
could simply traverse expr
backwards in a strictly sequential manner – no need to know in advance any points within expr
(cf. C and C++, among others).
In this implementation, we spawn threads only after we have an input line completely read and transformed into the sequence expr
. This is not the only way to go. We could have made the program more eagerly concurrent by spawning a thread as soon as in the course of reading we reach an operator token. So we would have been able to do some partial evaluation of the expression while concurrently parsing the rest of it.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <cilk.h> struct {int oper,span; double val;} * expr; char *pb; int isz,ssz; #define OI(i) (expr[i-1].span) int compile(int c) { int n,s,k,i; double x; char *p,*q,*qq, op[] = "+-*/"; for ( p = pb, n = s = k = 0 ; c!=EOF && c!='\n' ; *p++ = c, ++n, c=getchar() ) { if (c==' ' || c=='\t') s = 0; else if (s==0) {s = 1; ++k;} if (n+1==isz) { pb = realloc(pb,isz*=2); p = pb+n; } } *p = 0; if (ssz<k) expr = realloc(expr,(ssz=k)*sizeof(*expr)); for (i=n=0,p=pb; i<k; p=NULL,++i) { q = strtok(p," \t"); if (q[1]==0 && NULL!=(qq=strchr(op,*q))) { if (n<2) return -1; expr[i].oper = op[qq-op]; expr[i].span = OI(OI(i)); --n; } else if (x=strtod(q,&qq),*qq==0) { expr[i].val = x; expr[i].oper = 0; expr[i].span = i; ++n; } else return -1; } if (n>1) return -1; return k; } cilk double eval(int n) { double x,y; if (expr[n].oper==0) return expr[n].val; y = spawn eval(n-1); x = spawn eval(OI(n)-1); sync; switch (expr[n].oper) { case '+': return x+y; case '-': return x-y; case '*': return x*y; case '/': return x/y; } } cilk int main() { int c,k; double x; pb = malloc(isz=2); expr = malloc((ssz=1)*sizeof(*expr)); while ((c=getchar())!=EOF) { k = compile(c); if (k>0) { x = spawn eval(k-1); sync; printf("%f\n",x); } else if (k<0) printf("error\n"); } return 0; }
boykobbatgmaildotcom