Subj : Re: Spreading jobs among threads
To   : comp.programming.threads
From : Randy
Date : Wed Mar 02 2005 07:33 pm

Christoph Bartoschek wrote:
> Hi,
> 
> I would like to know whether there exist algorithms for the following
> problem or how the official name for the problem is to search for good
> algorithms:
> 
> There is a relatively small set of ressources R = {r1, r2, ..., rn}. (n is
> 64 for example) Then there exists a relatively large set of jobs J = {j1,
> j2, ..., jm}.  (m is 10000000 for example). Each job j1 has an assoziated
> subset Si of R. Each Subset Si contains the ressources one has to use to
> complete Job j1. Then there exist t threads which have to complete all
> jobs. During the execution of a job the ressources are reserved exclusive
> to the thread doing the job. One does not know how long it takes to
> complete a job, but one can estimate that the time is roughly proportional
> to the number of ressources used by the job.
> 
> The task is to divide the jobs among the threads and order them approprietly
> such that the time needed by t threads to complete all jobs is minimized.
> Additionally the overhead for searching the next job should be minimized.
> 
> Currently the jobs are put into a large queue and the threads select them
> from the queue. Then they try to acquire all ressources needed for the job.
> When one or more ressources are already locked by another thread, the job
> is put at the end of the queue and the next one is tried. When a job is
> finished, it is removed and all ressources are freed.
> 
> This simple algorithm wastes to much CPU time in searching for the next job,
> which can be executed, especially when a job requires a lot of ressources
> and nearly all other jobs cannot be started. Then the threads whithout jobs
> run through the queue and cannot wait for the job to complete.
> 
> Does anybody know a better algorithm or give me a hint where to search? The
> whole thing has similarities with hard packing problems, but they are not
> really the same.
> 
> Greets
> Christoph Bartoschek

Interesting problem.  It's clearly a dynamic constraint satisfaction problem,
with 1) imprecise runtime prediction, 2) sharing multiple resources, 3) dynamic
resource allocation and evaluation.

Because your runtimes cannot be predicted precisely, you can never get optimal
results.  If you can make a reasonably close estimate of runtime (e.g. within
20%), I would consider doing a static scheduling analysis using multiple
processors at the beginning of the run.  Generate the best schedule you can
build within X amount of analysis runtime, then follow the schedule while
backfilling with minimal jobs to compensate for the bigger holes in your
schedule (or for the more inaccurate time estimates for individual jobs).

If you insist on scheduling dynamically, I would consider building a
'blackboard' that's visible to all processes, that indicates which resources are
in use.  As each process begins to run, it indicates on the blackboard which
resources it has reserved.  Then the process updates the blackboard during its
run as each resource is freed.  Potentially this will allow other waiting
processes to get started earlier.

In general, I would think that starting the longest jobs (or the jobs using most
resources) first while backfilling with smaller jobs would be a good rule of
thumb (the greedy approach).

    Randy

-- 
Randy Crawford   http://www.ruf.rice.edu/~rand   rand AT rice DOT edu

.