Re: [boost] [threadpool] relation with TR2 proposal

Subject: Re: [boost] [threadpool] relation with TR2 proposal
From: Johan Torp (johan.torp_at_[hidden])
Date: 2008-09-16 05:49:49

viboes wrote:
> 
>> My _guess_ is that the C++ standard committee is targeting a thread pool
>> which can help to ease extraction of parallel performance, not a fully
>> configurable templated thread pool with lots of neat features.
> 
> It's my _guess_ also. I think that the Boost threadpool library must 
> integrate child-tasks and task stealing between worker threads.
> 

I haven't though about it much but I think you might be able to separate
scheduling from a thread pool library. You could even split it into three
pieces, a generic passive thread pool, scheduling algorithms and a
launch_in_pool free function which employs a single static thread pool and
some scheduling behind the scenes.

viboes wrote:
> 
>> I believe the standard efforts are inspired by what java (see
>> java.util.concurrency and the part called the fork-join framework) and 
>> .NET
>> standard libraries (TPL, task parallel library) and intel thread building
>> blocks (a C++ library) provide.
> 
> Are you talking about the C++ standard efforts? The n2276 proposal is a 
> simple thread pool without possibility to steel tasks betweer worker 
> threads. Are there other work in progress?
> 

Actually, I thought that the idea behind N2276 was to leave a lot of space
in the definition of the launch_in_pool so that library implementors could
have sophisticated work-stealing behind the scenes.

viboes wrote:
> 
> BTW, is someone already working on the FJTask adaptation to C++, or 
> something like that?
> 

I believe Intel TBB has come the longest way in extracting task level
parallelism via thread pools. I suspect a C++ solution will differ quite a
lot from a java implementation since the languages are so different.

viboes wrote:
> 
>> Read section 4.6 of my master's thesis to get a basic understanding of
>> thread-level scheduling, it can be found at: www.johantorp.com
> I'll take a look. Could you resume the conclusion of your thesis?
> 

My thesis tries to summarize the parallel shift as a whole, thread level
scheduling is just discussed on a page or two. Here is the title and
abstract:

Part 1 - A bird's eye view of desktop parallelism,
Part 2 - Zooming in on C++0x's memory model

The first part is an overview of the paradigmatic shift to parallelism that
is currently taking place. It explains why processors need to become
parallel, how they might function and which types of parallelism there are.
Given that information, it explains why threads and locks is not a suitable
programming model, how threading is being improved and used to extract
parallel performance and what problems awaits new parallel programming
models and how they might work. The final chapter surveys the landscape of
existing parallel software and hardware projects and relates them to the
overview. The overview is intended for desktop and embedded programmers and
architects.

The second part explains how to use C++'s upcoming memory model and atomic
API. It also relates the memory model to classical definitions of
distributed computing in an attempt to bridge the gap in terminology between
the research literature and C++. An implementation of hazard pointers and a
lock-free stack and queue are given as example C++0x code. This part is
aimed at expert C++ developers and the research community.

PDF available at: www.johantorp.com

viboes wrote:
> 
>> To my knowledge, out of
>> the .NET, java and TBB, only TBB exposes its thread pool. 
> 
> Doesn't FJTask expose the worker thread on FJTaskRunner.java class?
> 

I meant that you couldn't explicitly control how the thread pool behaved
(scheduling stategies and parameters). But it might very well be wrong, I
haven't had a deep look at Java and .NET's solution. 

viboes wrote:
> 
> What do you mean by a decent implementation?
> 

One which can extract most task level parallel performance (given the task
decomposition the user has provided) on many different processor
architectures and OSes.

viboes wrote:
> 
>> In practice, just providing the interface to launch_in_pool has proven
>> difficult as it returns a future value. The problem is nailing down a 
>> future
>> interface which is both expressive and can be implemented in a
>> lightweight
>> manner.
> 
> Could you elaborate more, which difficulties?
> What is missing on the current Future proposals for you?
> 

There are at least two things which still needs be solved:
1. How to wait for multiple futures
2. How to employ work-stealing when one thread waits on a future

An expressive solution is to allow some callback hooks (for future::wait and
promise::set) but that is quite hackish. IMO you should not be able to
inject arbitrary code which is run in promise::set via a future object that
runs on a completely different thread. 

I'm really not satisfied with the wait_for_any and wait_for_all proposal or
operators proposal either. Window's traditional WaitForMultipleObject and
POSIX select statement is IMHO very flawed. You have to collect a lot of
handles from all over your program and then wait for them in one place. This
really inverts the architecture of your program. I'd like a solution which
is expressive enough to "lift" an aribitrary function to futures. I.e.:

R foo(int a, int b) should be easily rewritten as future<R> foo(future<int>
a, future<int> b)

You could say that I want futures to be as composable as the retry and
orElse constructs of transactional memory (see my thesis if you are not
familiar with transactional memory). You might also want to support waiting
on a dynamic set of futures and as soon as one of them becomes ready. 

There is no agreement on what use cases futures should or have to support.
The problem is that the waiting and combining use cases really affect the
interface and if we do not support them, there will be interoperability
problems between different libraries (such as poet, thread pools and asio)
which might need to have their own specialized and non compatible future
objects. To allow extracting maximum task level parallelism, there is also a
need that futures are really lightweight. For more information, see:

http://www.nabble.com/-future--Early-draft-of-wait-for-multiple-futures-interface-to17242880.html#a17242880
http://www.nabble.com/Updated-version-of-futures-library-to17555389.html#a17613302

Best Regards, Johan Torp
www.johantorp.com
-- 
View this message in context: http://www.nabble.com/-threadpool--relation-with-TR2-proposal-tp19452045p19508651.html
Sent from the Boost - Dev mailing list archive at Nabble.com.