R -> A -> C -> D -> B -> E -> DEach capital letter represents an object of a class that inherits from Task. The user would specify the tree by typing something like this (if the tree above is confusing this might be clearer, I tried to make a clearer ASCII tree but the forum gobbles it): C.depends(A); D.depends(A); D.depends(B); E.depends(B); A.depends®; B.depends®; The tree represents control flow. When the tree is told to Start(), then R->Run() will be called and so some computation. When the computation is finished, R will have created some data. This data will be input for the A and B tasks, and A and B will be started in parallel (they each have their own thread). Then when A finishes it will give the data it computed to C and C will run. When B finishes it will gives its data to E and E will run. Notice that D is a child of both A and B. When both A and B are finished their combined data will be given to D and D will run. The general idea is that when all of the parents Tasks of a Task have been completed, that Task runs (its 'dependencies' are satisfied). The question is: How the heck do I implement this tree? Just getting the Run() functions to run multithreaded and in the proper order I don't think is too tough. The problem is how Tasks should pass data to each other (what actually happens when I wrote 'give the data' above). Ideally, the user should be able to specify that a Task produces a value of any arbitrary type, so long as child tasks are written to take an input of that type. My first thought was to make Task a templated class, with an input type parameter and an output type parameter. But looking at the example tree, D has _two_ inputs. The goal here is to avoid shared mutable data across threads (which leads to bugs). With this tree, if A is already done and B finishes, D and E will start simultaneously. Since A and B are known to have finished, so the data they computed is 'done cooking,' so there's no worrying about D or E reading garbage. And if D and E are only given _const references_ to the the result of B's computation, then they can't step on each other's toes either, and the compiler could check for this. But I just can't think of how to represent this tree in C++. If every task only had one input, things would be simpler, but Tasks like D exist in my application. I've thought about preprocessor and template magic, but the inspiration isn't coming. I think Boost's MPL could maybe help, but the online documentation is as opaque as steel. Any ideas?
Need help w/ C++ threading abstraction,
Members - Reputation: 122
Posted 20 February 2008 - 04:16 PM
Members - Reputation: 340
Posted 20 February 2008 - 09:28 PM
I assume what you're looking for is flexibility in being able to design and assemble components in an arbitrary fashion at runtime. This type of architecture is attractive in situations where you need to be able to add numeric/scientific data transformations to a data set (eg. for image processing). The best example of this architecture is Microsoft's DirectShow.
If you need flexibility at runtime, static typing may not be the best way to go. Although templates and MPL might allow you to produce a working system, they tend to be quite brittle from a design perspective - you still have to do a lot of work duplicating function signatures that you're over-riding. An alternative is to pass less strictly typed objects around your system, and add runtime tests to check whether data is in the correct format. boost::any is a neat way to do this. From experience, you're probably better off to look at a language which has better built in support for reflection and dynamic typing (Python/C#/Java/MATLAB). If performance in these languages is an issue, consider rewriting only the performance critical task bodies in C/C++.
From a concurrency perspective, such architectures tend to scale poorly with respect to load balancing and resources. One thread per task isn't necessarily the best way to divide the problem into pieces, particularly if the arrangement of pipes and filters can change at runtime. For example, a single thread in the middle of the pipeline can have a severe impact on performance for the rest of the components (threads later in the queue are left with nothing to do), which effectively makes the problem serial. An alternative approach is to use a job queue and a thread pool with size dependent on available resources (number of cores).
Members - Reputation: 2109
Posted 21 February 2008 - 12:52 AM
One way of doing this (and there are many others), is to use the concept of futures in combination with a thread pool behind the scenes.
The idea is that a future<T> object represents a T value that may or may not have materialized yet. When the future is accessed, it will either return the value immediately, or wait until it has been generated. The work needed to generate the T is usually done in another thread.
So if you have a function f() that needs the results of g() and h(), which can be run in parallel, you can just write:
std::string g(int x, int y);
double h(const char *name);
future<std::string> s = call(g, 42, 123);
future<double> d = call(h, "Edd");
// maybe do some more work in the mean time
// use the values
This is much more natural. Of course, it's not the right abstraction for every purpose, but in some cases it makes things much easier to read/maintain. This may be one of those cases. There's still a tree involved, but it's implicit. The programmer doesn't have to worry about getting the dependencies right, this is done for them.
If you're interested, I have an implementation of this. It handles various things such as the propagation of exceptions in to the parent thread, passing arguments to the function to be called asynchronously, support for functors as well as functions, and so on.
I plan to add support for custom task dispatching policies in a future version. For now it will create an extra thread if all current threads are busy.
Members - Reputation: 122
Posted 21 February 2008 - 07:52 AM
I actually don't need runtime flexibility. I've thought about just passing around the data typelessly somehow although I wasn't aware about the existence of boost::any. I may go that route for simplicity's sake.
My main concern here is making it hard for people using the API to screw things up and make it really easy to write clear code. By declaring the inputs and outputs for each task, and specifying how they're connected, you get a nice explicit dependency tree and what runs in parallel is obvious.
I'd actually like to have two sources of inputs for Tasks. Sometimes input comes from other tasks, but sometimes it comes from options specified in the GUI. Then to display the options the app-user can use, a tree of options would appear reflecting the dependency tree of tasks.
I hadn't heard of futures before but I could see using them to implement this. You maybe right that making the tree explicit is less natural and might be more prone to breakage, that's something I'll have to think about. It'd still be nice to be able to display a tree to the app-user, and I'm not sure I could do that just using futures (although like I said I could maybe use futures to implement the tree). I'd like for the programmer to not need to think about threading problems as much as possible...
It'd be nice if for example that if Task A gives data to Task B and to Task C, that Task B and C only got a const reference to the data so they couldn't hurt each other, but allow child tasks to get non-const references when they're the only child, or if the user specifies an option to make copies. Hrm...