| Pipeline | Each thread repeatedly performs the same operation on a sequence of data sets, passing each result to another thread for the next step. This is also known as an "assembly line." |
| Work crew | Each thread performs an operation on its own data. Threads in a work crew may all perform the same operation, or each a separate operation, but they always proceed independently. |
| Client/server | A client "contracts" with an independent server for each job. Often the "contract" is anonymous—a request is made through some interface that queues the work item. |
TABLE 4.1
All of these models can be combined in arbitrary ways and modified beyond all recognition to fit individual situations. A step in a pipeline could involve requesting a service from a server thread, and the server might use a work crew, and one or more workers in the crew might use a pipeline. Or a parallel search "engine" might initiate several threads, each trying a different search algorithm.
In pipelining, a stream of "data items" is processed serially by an ordered set of threads (Figure 4.1). Each thread performs a specific operation on each item in sequence, passing the data on to the next thread in the pipeline.
For example, the data might be a scanned image, and thread A might process an image array, thread B might search the processed data for a specific set of fea-tures, and thread C might collect the serial stream of search results from thread B into a report. Or each thread might perform a single step in some sequence of modifications on the data.
The following program, called pipe.c, shows the pieces of a simple pipeline program. Each thread in the pipeline increments its input value by 1 and passes it to the next thread. The main program reads a series of "command lines" from stdin. A command line is either a number, which is fed into the beginning of the pipeline, or the character "=," which causes the program to read the next result from the end of the pipeline and print it to stdout.
FIGURE4.1
1 #include
2 #include "errors.h" 3
4 /*
5 * Internal structure describing a "stage" in the
6 * pipeline. One for each thread, plus a "result
7 * stage" where the final thread can stash the value.
8 */
9 typedef struct stage_tag {
10 pthread_mutex_t mutex; /* Protect data */
11 pthread_cond_t avail; /* Data available */
12 pthread_cond_t ready; /* Ready for data */
13 int data_ready; /* Data present */
14 long data; /* Data to process */
15 pthread_t thread; /* Thread for stage */
16 struct stage_tag *next; /* Next stage */
17 } stage_t; 18
19 /*
20 * External structure representing the entire
21 * pipeline.
22 */
