Re: GNAT and large number of threads

[Wiktor Moskwa <wiktorDOTmoskwa@gmail.com>]

On 26.04.2007, Gene <gene.ressler@gmail.com> wrote:
>
> I can't answer your question directly, but the approach of using tasks
> as abstract data structures is asking for trouble.
>
> Tasks are appropriate when you _need_ independent computation threads:
> I/O with multiple devices, editing a file while a copy is being
> written to disk, you get the idea.  Protocol simulation doesn't fit
> this bill.  Nodes are essentially data. If you have only a single
> processor, you should run in the environment task.  If you need to
> exploit an MP environment, then use a task pool of N tasks for N
> processors.
>
> In other words, represent data with data structures and computation
> threads with tasks.  For your problem, you might want to represent
> each node as a set of input and output queues.  Apply one (or more)
> computation thread(s) to identify an appropriate node, remove inputs,
> create and add outputs to respective queues, then move on to another
> node. 

I decided to use one thread per node to simulate nodes executing
"in the same time" (in reality sequentially but at least with 
interleaving operations). An operating system schedules my threads and 
switches between them so I don't have to choose which node should be 
processed.

Thank you for your advice, it showed me new way to look at such
applications. Unfortunately I lack some experience in multi-threaded 
programming.

> A heap keyed on number of inputs left to define will always have
> a node with all inputs defined at the top. Multiple threads from a
> pool work exactly the same way except the queues are protected for
> synchronization.

It would be a good solution to scheduling if nodes produced output
messages based only on input messages. In case of this protocol(*)
every node periodically produces some messages to discover new nodes
in the network and to update internal references to other nodes.

It could be simplified that every N seconds worker threads execute
periodic procedures for all nodes and then go back to normal processing
based on a priority queue that you suggested. But I have no idea (yet) 
how to do it in case when periodic procedures can be invoked for each
node at different time.
Another thing to consider is how to modify this algorithm to reduce
chance of starving some nodes.

Thanks for answer and ideas,
Wiktor

[*] Chord distributed hash lookup protocol

-- 
Wiktor Moskwa