The first time you sign into developerWorks, a profile is created for you. Select information in your profile (name, country/region, and company) is displayed to the public and will accompany any content you post. You may update your IBM account at any time.

All information submitted is secure.

The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerworks.

All information submitted is secure.

# Fun with ALF, Part 6: Using task dependency

An example of how to use task dependency in a two-stage pipeline application

Kane Scarlett is a technology journalist/analyst with 20 years in the business, working for such publishers as National Geographic, Population Reference Bureau, Miller Freeman, and IDG, and managing, editing, and writing for such august journals as JavaWorld, LinuxWorld, and of course, developerWorks.

Summary:  In this Cell Broadband Engine™ (Cell/B.E.) series, learn how to use the Accelerated Library Framework (ALF) task dependency in a two-stage pipeline application. The "ALF for Cell/B.E. Programmer's Guide and API Reference, Version 3.0" (see Resources) is the source for the content.

View more content in this series

Date:  22 Jul 2008
Also available in:   Japanese

Activity:  22977 views

## More fun with ALF

Look for more in the Fun with ALF series:

And watch for similar Fun with series addressing DaCS, BLAS, and other technologies to make your Cell/B.E. programming easier.

Introduction

This article provides an example that shows how task dependency is used in a two-stage pipeline application. The problem is a simple simulation. An object P is placed in the middle of a flat surface with a bounding rectangular box. On each simulation step, the object moves in a random distance in a random direction. It moves back to the initial position when it hits the side walls of the bounding box. The problem is to calculate the number of hits to the four walls in a given time period (also known as playing Pong).

Figure 1. Object P randomly hits the side wall of the bounding box

A two-stage pipeline is used to solve the problem so that the random number generation and the simulation can be paralleled:

• The first stage generates random numbers using a pseudo-random number generator.
• The second stage simulates the movements.

Because ALF currently does not support pipeline directly, a pipeline structure is simulated using task dependency. There are two tasks that correspond to the two pipeline stages.

For this problem, each simulation step needs only a small amount of data, just as a motion vector. Although ALF does not have a strict limit on how small the data can be, it is better to use larger data blocks for performance considerations. Therefore, the data for thousands of simulation steps is grouped into a single work block.

For the stage 1 task, a Lagged Fibonacci pseudo-random number generator (PRNG) is used for simplicity. (A Lagged Fibonacci generator is an example of a pseudo-random number generator: a class of random number generator that is aims to be an improvement over the standard linear congruential generator. These are based on a generalization of the Fibonacci sequence, which can be described by the recurrence relation, an equation that defines a sequence recursively, so that each term of the sequence is defined as a function of the preceding terms.)

In this example, the algorithm is `Sn=(Sn-j^Sn-k)%232`, where k > n > 0 and k = 71, j = 65. The algorithm requires a length k history buffer to save the older values. In this implementation, the task context is used for the history buffer. Because no input data is needed, the work block for this task has only output data.

For the stage 2 task, the task context is used to save the current status of the simulation, including the position of the object and the number of hits to the walls. The work block in this stage has only input data, which are the PRNG results from stage 1.

Another target of pipelining is to overlap the execution of different stages for performance improvement. This requires work-block-level task synchronization between stages, which ALF does not yet support. The alternative approach is to use multiple tasks in which each task only handles a percentage of the work blocks for the whole simulation.

Putting it all together

So there are now two stage tasks. For each chunk of work blocks, the following two tasks are created:

• The stage 1 task generates the random numbers and writes out the results to a temporary buffer.
• The stage 2 task reads the random numbers from the temporary buffer to do the simulation.

A task dependency is set between the two tasks to make sure the stage 2 task can get the correct results from stage 1 task. Because both the PRNG and the simulation have internal states, you have to pass the states data between the succeeding tasks of the same stage to preserve the states. The approach described here enables the tasks for the same stage to share the same task context buffer. Dependencies are used to make sure the tasks access the shared task context in the correct order.

Figure 2 shows the task dependency.

Figure 2. Task dependency with an unlimited number of interstage buffers

To further reduce the use of temporary intermediate buffers, you can use double or multi-buffering technology for the intermediate buffers. The task dependency graph for double buffering the intermediate buffers is shown in Figure 3.

Figure 3. Task dependency using double buffers

In this example, a new dependency is added between the n-2nd stage 2 task and the nth stage 1 task to make sure the stage 1 task does not overwrite the data that might still be in use by the previous stage 2 task. This is what is implemented in the sample code. You can find the complete source code in the sample SDK directory pipe_line.

Conclusion

Resources

Learn

Get products and technologies

Discuss

Kane Scarlett is a technology journalist/analyst with 20 years in the business, working for such publishers as National Geographic, Population Reference Bureau, Miller Freeman, and IDG, and managing, editing, and writing for such august journals as JavaWorld, LinuxWorld, and of course, developerWorks.

Report abuse help

# Report abuse

Thank you. This entry has been flagged for moderator attention.

Report abuse help

# Report abuse

Report abuse submission failed. Please try again later.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Multicore acceleration
ArticleID=322854
ArticleTitle=Fun with ALF, Part 6: Using task dependency
publish-date=07222008
author1-email=kane@us.ibm.com
author1-email-cc=

## IBM SmartCloud trial. No charge.

Unleash the power of hybrid cloud computing today!