Subj : Spreading jobs among threads
To   : comp.programming.threads
From : Christoph Bartoschek
Date : Thu Mar 03 2005 01:06 am

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

.