# A Parallel Processing Template for Divide & Conquer Problems

I’ve written a program for solving a problem using standard single-threaded code. However, it looks like it could be recast as a multi-threaded problem using divide & conquer. Since this is a first attempt at multi-thread programming (and debugging), I thought it might be advisable to separate the problem itself from the parallel management. The following is a multi-threaded divide & conquer skeleton, which hopefully the actual problem could fit into. I would appreciate a code check and any relevant advice about how to better code multi-threaded applications like this.

To run the following code, simply switch to the :test package and execute (main) after loading. The printout shows when any thread receives a problem (its size—eg, 34), and if it is split, what the random split is—eg, (13 21). If it is not split because it is too small, the printout just shows the simulated processing of what’s remaining.

Secondary questions: 1) The function main uses up a whole thread just waiting for problem completion. Is there a way to use this thread too? 2) Can the number of queues or queue accesses be reduced? 3) Would a so-called sequence diagram be the best way to verify correctness? Ie, is this worth learning, or is there a better way. (Ps: The program seems to run OK, but I’m not even sure how to simulate the duration of a thread.) Thanks for any time you can spare.

EDITS 3/30/19: 1) Replaced with-temp-kernel (1) with (setf lparallel:*kernel* (lparallel:make-kernel *num-threads*)) and (lparallel:end-kernel) to follow library recommended way to start and stop lparallel kernel. 2) Added tracing queues for each thread to collect each thread’s problem solution progress for debugging. 3) Added epilog code to main to printout the trace of each thread after kernel shutdown, in order to avoid printing interference during shutdown.

#-:lparallel  (ql:quickload :lparallel)

(defpackage :test (:use :cl :lparallel :lparallel.queue))

(in-package :test)

(defparameter *problem* 100)  ;estimated size of the main problem

(defparameter *problem-size-cutoff* 5)  ;don't split small problems

(defun thread (problems idles trace done)
(loop do
(let ((problem (pop-queue problems)))  ;blocks until a problem is available
(pop-queue idles)  ;one (this) thread is no longer idle
(push-queue problem trace)  ;track this thread's solution of its problem
(loop do
(when (and (> problem (* 2 *problem-size-cutoff*))  ;don't split if small problem
(>= (queue-count idles) 1))  ;ie, some threads are idle
(let ((n (+ (random (- problem (* 2 *problem-size-cutoff*)))
*problem-size-cutoff*)))  ;split problem
(sleep .01)  ;time to run splitting algorithm
(push-queue n problems)  ;n is random size of subproblem split
(setf problem (- problem n))  ;remaining problem size after split
(push-queue (list n problem) trace)))  ;track this thread's splitting
(decf problem) (sleep .1)  ;work more on current problem
(push-queue problem trace)  ;track this thread's incremental progress
(push-queue t idles)  ;this thread now idle
(progn (push-queue t done)  ;signal all done to main
(return)))))))  ;return from inner loop to get new problem

(defun main ()
"The main consumer of parallel thread processing."
(let ((c (make-channel))
(problems (make-queue))  ;holds current problems to be solved
(idles (make-queue))  ;holds a t for each current idle thread
(traces nil)  ;holds a trace of the progress of each thread for debugging
(done (make-queue)))  ;signals t when all processing is done
(loop for i from 1 to *num-threads*  ;get all threads up & running
do (let ((trace (make-queue)))  ;track the progress of a thread using a queue
(push trace traces)