parallelism

[glen e. p. ropella]

Since parallelism has come up, I'd like to pass on a tidbit
from a recent paper on multi-threaded computation.  I like
it because it's all about providing the processors with
autonomy and self-interested behavior (a.k.a. "agency").

From: Blumofe, R. D. and Leiserson, C. E.; "Scheduling
Multithreaded Computations by Work Stealing". Journal of the
ACM; Vol. 46, No. 5, September 1999, pp. 720–748.

> Two scheduling paradigms have arisen to address the problem of scheduling
> multithreaded computations: work sharing and work stealing. In work sharing,
> whenever a processor generates new threads, the scheduler attempts to migrate
> some of them to other processors in hopes of distributing the work to 
> underuti-lized processors. In work stealing, however, underutilized 
> processors take the initiative: they attempt to “steal” threads from other 
> processors. Intuitively, the migration of threads occurs less frequently 
> with work stealing than with work sharing, since when all processors have 
> work to do, no threads are migrated by a work-stealing scheduler, but 
> threads are always migrated by a work-sharing scheduler.

This is rather cool from an ALife perspective in that the
work becomes the malthusian resource.  They developed a randomized
work stealing algorithm where the "randomized" part refers to the
uniformly random selection by a thief of a victim processor from
which work is stolen.  It's unclear from my first read of the
article what defines the space of processors the thief processors
choose randomly from.  But, if we could do something akin to
what Mosix does with its "processor pool", where each processor
randomly configures a multicast signal periodically, letting some
subset of the total populace know of its existence, then not only
would the pool of potential work be distributed (as in the article)
but we'd also have a scalable mechanism for dynamic machine
configuration.  I'm not sure we could rip out the homunculus of a
Mosix system, though, without killing the body.

I suppose the question I'm trying to raise, here, is "do we want
to make the machine/model a close mapping?  or do we want to go
full-on for logical abstraction and build things like virtual
machines?"

glen

--
glen e. p. ropella =><= The front line is everywhere. Hail Eris!
Home: http://forager.swarm.com/~gepr              (505) 424-0448
Work: http://www.swarm.com                        (505) 995-0818


                 ==================================
  Swarm-Modelling is for discussion of Simulation and Modelling techniques
  esp. using Swarm.  For list administration needs (esp. [un]subscribing),
  please send a message to <address@hidden> with "help" in the
  body of the message.
                 ==================================