Adi Levin's Blog for programmers

July 24, 2009

Multithreading Patterns #1 – Fork-Join

Filed under: Multithreading — Adi Levin @ 11:33 am
Tags: ,

The purpose of the Fork-Join patten is to parallelize a part of an algorithm through task-parallelism.

“Fork” means that the calling thread asks other threads to perform tasks, instead of performing it sequentially.

“Join” means that the calling thread waits until all tasks have been accomplished by the other threads. In some cases the “Join” operation is more complicated – it requires to merge the results of the different threads.

Examples:

1. Parallel “for” loop. Each iteration of the loop becomes a task, or a range of iterations of the loop become a task. For an example, see my post on Asynchronous Procedure Call.

2. Parallel reduction – for example, computing the sum of an array. Break the array into N parts. Each task of the N tasks will be reponsible for summing up a part of the array. The “Join” operation means summing up the N results, and waiting for all of the tasks to complete.

3. Parallel activation of two independent parts of an algorithm.

This is a very useful pattern, and it does not require broad changes of the software. It parallelizes a certain segment of code, without requiring changes in other parts of the code.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: