Dear all, I am experiencing inefficiency while using the Futures library within PolyML. Parallel threads are being forced to 'sleep' for several seconds at a time for no clear reason, and I suspect it may be due to memory management between multiple threads. The test machine has 80GB RAM and 24 available cores. The parallel process works in roughly the same way as the Bag of Tasks Model with Replacements: (I'll refer to the distributor of tasks as the Controller, and other threads as Workers) 1. The Controller constructs an initial list of tasks.2. It sends the tasks to Workers in parallel, distributing across cores appropriately. Tasks are spawned by Future calls. They return a mixture of new tasks and results.3. It synchronises on all of the spawned tasks, organises them and repeats from (2) if any tasks remain. Tasks require a modest amount of memory and significant time to run, but there are 100,000s of them. The memory consumed can rise by 10GB in a few seconds but does not exceed the available RAM, and is held almost entirely by the Controller. The process can take minutes to run, but I see that spawned Futures in the program are required to sleep for the majority (~75%) of the time. The turnover in memory is very high as well, especially in the Controller thread, so calls to the garbage collector can reduce the RAM required dramatically. Initially, as the original problem size grows the speedup via parallelisation rises to a peak of around 6 times, requiring only a few GBs of RAM. However, as the problem size continues to rise and the problem should be easier to parallelise, the speedup falls to the point where a sequential algorithm evaluating tasks one at a time is more efficient. Artificial tests show that when virtually no memory is required, a speedup of over 10 times is quite easy to achieve. What I believe might be causing this is the allocation of segment sizes to threads in the heap. I believe that calls to the common memory pool to change the segment size are causing all threads to sleep unnecessarily. Does each thread currently have its own independent adaptive segment size, or are all threads required to use the same segment size? Do all threads have to pause if one segment size is being changed? I have timed the synchronisation phase above and it requires 10-100s of microseconds typically, so not accounting for the regular sleep times of several seconds. I know the threads are being paused mid-task computation, and I have tried increasing the heap size as well to no effect. Does anyone know what might be causing this behaviour?Best regards,Michael
It's difficult to be sure what's happening without really examining the application. I suspect, though, that this has something to do with garbage collection. I take it you are using Poly/ML 5.5 and not an earlier version? Each thread does have its own segment to allocate in but getting another segment does not involve any other thread. When the memory runs out and a GC is needed all the threads are stopped. GC is run as a completely separate phase and isn't overlapped with any ML execution. Since version 5.5. the GC has been parallelised unless explicitly overridden with --gcthreads.
There are ways to get information from the Poly/ML run-time system to help you understand what is happening. The --debug option causes various parts of the RTS to print information. See poly --help for a list of the options. The PolyML.Statistics will get information out about the current process and can also be used to get information about another poly process. Magnus Stenqvist, a student of Tjark Weber, wrote some code to view the statistics of another process. I haven't tried it myself yet but it's here https://bitbucket.org/manne/poly-ml-system-monitor if you want to try it.
David
On 08/04/2013 19:21, Michael Bradley wrote:
Dear all, I am experiencing inefficiency while using the Futures library within PolyML. Parallel threads are being forced to 'sleep' for several seconds at a time for no clear reason, and I suspect it may be due to memory management between multiple threads. The test
On Mon, 8 Apr 2013, Michael Bradley wrote:
I am experiencing inefficiency while using the Futures library within PolyML.
Can you point to the actual "Futures library" that is used here? I only know the one I made for Isabelle/ML, but I think there are spin-offs.
The question how to include a standard futures library in the Poly/ML distribution is still open.
Tasks require a modest amount of memory and significant time to run, but there are 100,000s of them.
Isabelle/ML futures (or derivatives) should normally work within this range of 10^5, although the basic assumption is that future dependencies are relatively sparse.
Makarius
Thanks Makarius and David for your quick replies.I am using PolyML 5.5 and I am using the Futures library in IsapLib: https://github.com/iislucas/isaplib. All of the tasks are independent. I haven't had the chance to look properly into the debugging yet (revising!), but I'll let you know once I have.Many thanks,Michael
Date: Wed, 10 Apr 2013 14:21:10 +0200 From: makarius@sketis.net To: michael.bradley@hotmail.co.uk CC: polyml@inf.ed.ac.uk Subject: Re: [polyml] Memory Management across multiple threads using Futures Library
On Mon, 8 Apr 2013, Michael Bradley wrote:
I am experiencing inefficiency while using the Futures library within PolyML.
Can you point to the actual "Futures library" that is used here? I only know the one I made for Isabelle/ML, but I think there are spin-offs.
The question how to include a standard futures library in the Poly/ML distribution is still open.
Tasks require a modest amount of memory and significant time to run, but there are 100,000s of them.
Isabelle/ML futures (or derivatives) should normally work within this range of 10^5, although the basic assumption is that future dependencies are relatively sparse.
Makarius
On Wed, 10 Apr 2013, Michael Bradley wrote:
I am using PolyML 5.5 and I am using the Futures library in IsapLib: https://github.com/iislucas/isaplib. All of the tasks are independent. I haven't had the chance to look properly into the debugging yet (revising!), but I'll let you know once I have.
It seems you are actually one of the maintainers of this spin-off library of Isabelle/ML, which was started by Lucas Dixon some years ago.
If there is anything to be amended in the master sources within Isabelle, I am ready to revisit certain fine points -- it has a natural bias towards particular applications within the proof assistant. (I am not accepting arbitrary patches, though, since these things are very delicate.)
Just keep us informed here about your findings -- it is very relevant for any high-performance applications of Poly/ML.
Note that for further exploration, "Future.ML_statistics := true" produces a property list with summary of the Poly/ML runtime status and Isabelle/ML future task queue and worker thread farm every 0.5s -- it subsumes PolyML.Statistics.getLocalStats in particular. To see any of the results, you need to provide a suitable implementation of Output.Private_Hooks.protocol_message_fn, e.g. to print it or store it somewhere else.
These global protocol hooks are normally managed by the Isabelle/ML session startup, so you have to imitate this manually. Alternatively, you can run under regular Isabelle/ML with Isabelle/jEdit, and then use its Monitor panel (the online chart-drawing of that data is still a bit crude).
Yet another way is to run your own ML monitoring thread that uses PolyML.Statistics.getLocalStats or similar peridically -- in Isabelle/ML this is built into the "scheduler thread" of the future task farm.
Makarius
On 12 April 2013 15:01, Makarius makarius@sketis.net wrote:
On Wed, 10 Apr 2013, Michael Bradley wrote:
I am using PolyML 5.5 and I am using the Futures library in IsapLib:
https://github.com/iislucas/**isaplibhttps://github.com/iislucas/isaplib. All of the tasks are independent. I haven't had the chance to look properly into the debugging yet (revising!), but I'll let you know once I have.
It seems you are actually one of the maintainers of this spin-off library of Isabelle/ML, which was started by Lucas Dixon some years ago.
https://github.com/iislucas/**isaplib https://github.com/iislucas/isaplib is a copy of Isabelle's generic polyml code with some additions by myself and others. I updated it recently form Isabelle 2013's libraries, so it should be the same.
best, lucas