[plt-scheme] Can this be done in Scheme (parallelism)?

From: Gregory Woodhouse (gregory.woodhouse at sbcglobal.net)
Date: Wed Jan 18 09:40:40 EST 2006

You may recall that I wrote a little Scheme program to demonstrate  
the interleaving of threads:

(define (the-body x)
   (begin
     (let loop ((i 0))
       (begin
         (if (< i 25)
             (begin
               (display x)
               (loop (+ i 1))))))))
;The use of t1 and t2 here is an artifice to
;suppress display of the thread ID
(define t1 '())
(define t2 '())
(begin
   (set! t1 (thread
              (lambda () (the-body "A"))))
   (set! t2 (thread
             (lambda () (the-body "B")))))

The output is something like


BBBBABBBBBBBBBBBBBBBBBBBBBAAAAAAAAAAAAAAAAAAAAAAAA

Out of curiosity, I decided to try writing a similar program in  
MUMPS. In this case, I didn't have the option of having two threads  
writing to the display, so I needed a different approach. What I  
decided to do was launch to processes with the MUMPS JOB (or just J)  
command and have them write to a shared (global, in MUMPS jargon)  
array. Here is the code

EN             ; ; 1/17/06 6:55pm
          N I,X,X1,CNT
          S ^XTMP("GREG")=0
          J RUN("A")
          J RUN("B")
          S I=0,X="",X1="",CNT=0
          F  S I=$O(^XTMP("GREG",I)) Q:((I="")!(CNT>10))  D
          .S X1=X
          .S X=$G(^XTMP("GREG",I))
          .W:X'=X1 !,"Changing to ",X," at I = ",I
          .S:X'=X1 CNT=CNT+1
          K ^XTMP("GREG")
          Q
RUN(X)     ;
          N I,J
          F I=1:1:250000 D
          .S J=$INCREMENT(^XTMP("GREG"))
          .S ^XTMP("GREG",J)=$G(X)
          Q

(Note that $INCREMENT is not part of the language standard.)

I was astonished to see that the first job ran through about 150,000  
A's before the second one got started, but then they strictly  
alternated! That is, the sequence was something like

AAAAAAAA....ABABABABA....B

and the alternation was absolute. Well, that was a real puzzle, but  
then it occurred to me that both processes were running EXACTLY the  
same code. Could this be a SIMD effect? (I ran this test on an  
Alpha.) To test the idea, I tried running the same code on a Pentium  
(running XP) and the results were similar to what I initially  
expected (because of the difference in processor speeds, I reduced  
the number of iterations to just 5,000):

VISTA>D ^ZZGREG2

Changing to A at I = 1
Changing to B at I = 457
Changing to A at I = 884
Changing to B at I = 885
Changing to A at I = 1087
Changing to B at I = 1306
Changing to A at I = 1307
Changing to B at I = 1479
Changing to A at I = 2815
Changing to B at I = 7002
Changing to A at I = 11044

In other words, we would see runs of A's and B's of a few hundred in  
length, meaning each job got through that many iterations without  
being preempted.

Well, I don't have access to Scheme on a modern architecture (but  
what about the Duos used by the new MacBooks?) but I can't help but  
wonder if it's possible to exhibit the same sort of parallelism in  
Scheme? Or is my basic theory here wrong, and it's something else  
that I'm seeing?




===
Gregory Woodhouse
gregory.woodhouse at sbcglobal.net

"The most incomprehensible thing about
the world is that it is at all comprehensible."
  --Albert Einstein (1879-1955)





Posted on the users mailing list.