Re: Another approach to parallel programming

On 2015-08-26, Kao Hsiang <0xe0e1e@gmail.com> wrote:
> In recent years, I have been concerned about parallel programming in a new way.
> Gradually I formed an idea about a approach of imperative parallel programming.
>
> -------------
> Let f(a,b,c,...) be any function(or subroutine), we define that a,b,c,... can be executed parallelly,
> and f depends on a,b,c,... so it executes after its arguments.
> and I think it can be a basic primitive of imperative parallel programming.
>
> Next we define block "to{...}" and block "do{...}" (in library)
> "to" is a null function with variable arguments to represent parallel sentences.
> "do" is a function "do(a,func b()) {b();}" with argments "a" and a closure "b" (continuation-passing style) to represent sequential sentences.
> And then the instruction-level parallel programming can be easily implemented based on f.
>
> It can be compiled into vm bytecode/ VLIW architecture code / os-based threads.
> ------------
>
> Sorry about my broken English. Now I plan to implement a new
> language based on the above idea. I think this language will be useful
> and convenient for parallel programming.


One afternoon Lisp macro job.


  ;; equivalent of "to"
  (defmacro par (&rest forms)
      ;; exercise for reader:
      ;; ... generate code which farms out forms to threads, then joins
      )


  ;; "do" function
  (defun seq-fun (a b)
      (funcall b))


  ;; macro to sequence variable forms using seq-fun
  (defmacro seq (&rest forms)
      (cond
          ((null forms) nil)
          ((null (rest forms)) (first forms))
          (t `(seq-fun ,(first forms) (lambda () (seq ,@(rest forms)))))))


Quick test of seq in CLISP:


Empty case: (seq) -> nil


    [1]> (macroexpand '(seq))
    NIL ;
    T


One argument case: (seq whatever) -> whatever


    [2]> (macroexpand '(seq 1))
    1 ;
    T


Two arguments: (seq this that) -> (seq-fun this (lambda () (seq that)))


    [3]> (macroexpand '(seq 1 2))
    (SEQ-FUN 1 (LAMBDA NIL (SEQ 2))) ;
    T


Execution test


    [5]> (seq (print 'a) (print 'b) (print 'c))
    A
    B
    C
    C
(Last C is result of evaluation.)


All pretty pointless; why not just use the left-to-right sequencing built into
the target language. We would need this CPS style only if the target language
doesn't give us left-to-right order evaluation for function aruments, but does
guarantee that function arguments evaluate before bodies.


All that is left to code is the parallel construct par. Various approaches
are possible, such as turn the eforms into lambdas, which are then queued
to a thread pool.


Suppose we have some global *thread-pool* object such that
(tp-queue *thread-pool* j f) queues a function for execution,
associating it with job ID j (which is a symbol).
Suppose (tp-wait *thread-pool* j) waits for all previous
work queued for job j to finish.


Without much ado, we can write par:


    (defmacro par (&rest forms)
        (let* ((job-id-var (gensym))
                      (queue-cmds (mapcar (lambda (form)
                                                                    `(tp-queue *thread-pool* ,job-id-var
                                                                                          (lambda () ,form)))
                                                              forms)))
          `(let ((,job-id-var (gensym)))
                ,@queue-cmds
                (tp-wait *thread-pool* ,job-id-var))))


Tests:


Zero job case. Here, hopefully tp-wait will just fall through
since there is nothing under the given job ID.


    [2]> (macroexpand '(par))
    (LET ((#:G3210 (GENSYM))) (PROGN) (TP-WAIT *THREAD-POOL* #:G3210)) ;
    T


Three jobs:


    [3]> (macroexpand '(par (do-laundry) (vacuum-house) (wait-for-phone-call)))
    (LET ((#:G3211 (GENSYM)))
      (TP-QUEUE *THREAD-POOL* #:G3211 (LAMBDA NIL (DO-LAUNDRY)))
      (TP-QUEUE *THREAD-POOL* #:G3211 (LAMBDA NIL (VACUUM-HOUSE)))
      (TP-QUEUE *THREAD-POOL* #:G3211 (LAMBDA NIL (WAIT-FOR-PHONE-CALL)))
      (TP-WAIT *THREAD-POOL* #:G3211)) ;
    T


Looks good! A new job ID symbol is dynamically created by calling (gensym)
and stored in the #:G3211 variable. The three forms, turned into
the bodies of anonymous functions, are queued to the thread pool, all
under this same job ID. Then, a wait is executed to collect them all.


We just have to implement tp-queue and tp-wait, and the *thread-pool*
object.

Return to the comp.compilers page.
Search the comp.compilers archives again.