[Nottingham] Eager Queues and GNU Hurd.

[Martin]

Jason Cozens wrote:
> Hi,
> 
> I've just registered for a SourceForge project relating to what I
> mentioned last night. This is what I told them, I hope it's not too long
> for this list:

I'll admit that anything longer than a "few lines" gets left until
sometime "later" where that "later" often includes a good mug of
coffee... ;-)


> Eager Queue Protocol
> ====================
> 
> The Problem - Simple Statement
> ==============================
> 
> A pool of processors is available to do work. The work is of a
> heterogeneous nature so that the processors can not be organised into
> a regular structure. The work requests come from the processors
> themselves. Processors may also come and go from the pool.

Sounds very interesting and especially so with the current moves away
from single core CPUs and also for the move away from deep
pipelines/vector operation. (Note Intel's "Netburst" deep pipelines
fiasco for their P4.) There's recently such as the 'cell' processor and
the multiple processor elements of the latest GPUs just waiting to be
utilised better.


> How can the processors be organised so that the work is scheduled in
> a reasonably good way so that there is no centralised scheduling
> process.

I like the "no centralised" bit :-)


> Solution
> ========
> 
> A protocol that uses UDP is defined called the Eager Queue Protocol.
> This protocol works in a similar way to a job exchange. Workers enter
[...]
> The protocol uses UDP a well established and widely available protocol.
> The main benefit of the protocol will be to move away from a centralised
> OS Kernel that is responsible for the scheduling of processes. Since
> there is no central processor it should be able to make the system fault
> tolerant and also have live hardware updates.
> 
> It is hoped that one of the main benefits of parallel computing might be
> realised, that is that high performance is gained in a heterogeneous
> environment by aggregating many cheap processors rather than by the use
> of ever more powerful and expensive processors.
> 
>>From initial investigations it look as though EQP will be able to
> combine with the translators of GNU Hurd.

YEAH!!

My first thought is that there is an awful lot of _broadcasting_ going
on with that lot that could then quickly swamp a network as you add more
processors / processing elements. You also get more overhead with all
the broadcast noise that everyone must listen to. A bit like controlling
the job market with spam rather than filtering via recruiting agencies...?


> Rough Outline of What Happens
> =============================
[...]
> Idling Eager Queue
> ==================
[...]
>   P1 Listens.
>   -
>   P1!JOIN:[P1]                          1st Broadcast
>   -
>   P1!UPDATE:[P1]                        2nd Broadcast
>   -
>   P1!UPDATE:[P1]
>   P2!JOIN:[P2,P1]
>   -
>   P1!UPDATE:[P1,P2]
>   -
>   P2!UPDATE:[P2,P1]
>   P3!JOIN:[P3,P2,P1]
[...]

That looks very similar to some of the stuff we saw on Thursday night
after the beers interval! :-P


> References
> ==========
> 
> Some earlier ideas in eager queues can be seen at:
> 
>         http://developer.novell.com/wiki/index.php/OpenEd_-_Lab_4


More seriously:

I've long been uneasy about continuing to rely on one (big) monolithic
kernel and then having to bolt on mutexes/spin-locks and various other
mechanisms to mitigate/block races and confusion between multiple
processors/processes all running on and fighting for the same one lump
of hardware.

Meanwhile, the idea of the transputer came and went... And others and
more esoteric such as various "active memory" and "processor element
arrays" massively parallel systems...

And then there is the GNU Hurd...


Jason, as mentioned Thursday, care to give a talk? (Please :-) )

For the non-techies: This is an interestingly different way to arrange
what your CPU/hardware works on next. It's easy really!

Cheers,
Martin



Transputer:
http://en.wikipedia.org/wiki/Transputer
http://www.atarimuseum.com/computers/16bits/transputer.html
http://www.classiccmp.org/transputer/

-- 
----------------
Martin Lomas
martin at ml1.co.uk
----------------