4/14/2009

Thread Model for Multi-threading Programming

The meaning of Thread Model (A.K.A. Thread Paradigm, Thread Design Pattern) varies in different context, it may refer to:
- How thread is implemented and its relation ship with process in OS
- How multi-threading is used to implement client/server based system
- How (usually multiple) thread works together to accomplish some large scale & complicated task

In this post, Thread Model means how to arrange multiple threads to work together and get assigned tasks done.

1. The Models

Master/Slave (a.k.a Boss/Worker or Master/Worker)
Master divide the whole big task into small sub tasks (a.k.a. work item), assign them to those worker threads, and then wait/poll until all these work items are done. Thread Pool, Work Queue are all variants of this model.

This model is best suitable for asynchronous I/O framework, such as scalable network service or work queue library. The boss thread receives client requests, put them into some queue and the worker threads fetch one request, serve it and continue the loop ...

Pipeline
The pipeline model divides up a task into a series of steps, and passes the results of one step on to the thread processing the next. Each thread does one thing to each piece of data and passes the results to the next thread in line. Usually, all stages are active at the same time, thus the whole system throughput is limited by the lowest stage. Very similar to assembly in manufacturing industry .

This model is suitable for stream data processing such as 3D graphic rendering.

Work Crew (a.k.a Peer Model)
All threads are the same type, each process some specific portion of the data, but perform the same operations. These threads may need to communicate in some predefined way and cooperate in the remaining steps. [for example, SMP version of merge/sort]

The peer model is suitable for applications that have a fixed or well-defined set of inputs (classical HPC applicatioins), such as matrix multipliers, parallel database search engines etc.

Producer/Consumer
It's just a special(also simple) case of Pipeline model or kind of Master/Slave model, depends on what's your perspective. In this model, producer output some data in to some buffer, and the consumer input some data from the bufffer. If the data is work item descriptioin, it is kind of special Master/Slave model; if it's pure data that needs some further manipulation, it is kind of Pipeline model.

2. Case Studies

WPF thread model
http://msdn.microsoft.com/en-us/library/ms741870.aspx

COM thread model
http://blogs.msdn.com/oldnewthing/archive/2004/06/02/146671.aspx
http://blogs.msdn.com/larryosterman/archive/2004/04/28/122240.aspx

Apache Axis2/C
http://wso2.org/library/articles/understanding-axis2-c-threading-model

Language Thread Model Overview(C#/Python/Perl/Ruby)
http://justin.harmonize.fm/index.php/2008/09/threading-model-overview/

[Reference]
1. Thread Design Pattern, http://www.cercs.gatech.edu/multicore/images/f/f0/MultithreadingModels.ppt
2. Concurrent Programming with Threads, http://www.gridbus.org/~raj/tut/multi-threading.ppt
3. Perl Thread Doc http://perldoc.perl.org/perlthrtut.html
4. HPC thread model, http://software.intel.com/en-us/articles/threading-models-for-high-performance-computing-pthreads-or-openmp/
5. The Thread Model, http://www.informit.com/articles/article.aspx?p=169479&seqNum=5
6. Pthread Tutorial, http://cs.gmu.edu/~white/CS571/pthreadTutorial.pdf
7. Another Pthread Tutorial, http://randu.org/tutorials/threads/
8. Parallel and Distributed Programming Using C++, http://www.informit.com/store/product.aspx?isbn=0131013769