<link href="../style_sheet.css" rel="stylesheet" type="text/css">

# For Each

`For Each` is a set of utility classes that enable the quick and easy
construction of cross platform jobs that perform the same operation on several
pieces of data.

- SerialForEach

Working around the SPU local store limitations can be a pain. You have to DMA
things in, do double-buffering, split things up, etcetera, yadda yadda. `Serial
For Each` makes your life easier. Originally presented as SpuStream as written
by Tiburon, we've taken their ideas and aligned it with `Parallel For Each`. To
illustrate, let's use an example. Imagine we had a collection of vectors that
we wanted to calculate the squares of a set of vectors.        

        // Create some data
        const int numVectors = 20000;
        Vector3* vectors = new Vector3[numVectors];
        float* squares = new float[numVectors];
        
        // Fill the vector array somehow
        
        // A batch descriptor contains a set 
        // of in, out, or in-out streams
        EA::Jobs::BatchDesc bd(numVectors);
        
        // SetArray sets the input and output 
        // for a particular stream
        bd.SetArray<Vector3>(0, vectors, 0);
        bd.SetArray<float>(1, 0, squares);
        
        // Go...
        SerialForEach sfe(jobScheduler, squareVectorEntryPoint, bd);
        sfe.Run();
        sfe.WaitOn();

You may say; that looks rather complicated. Well, you'll get even more worried
once you see the actual job itself. But bear with us, soon the motivation for
this will become apparent. Here's the job which does the actual work:  

        void SquareVector(uint32_t batchDescEa, uint32_t jobIdx, uint32_t, uint32_t)
        {
            const int bufferSize = 32 * 1024;

            #if defined EA_PLATFORM_PS3_SPU
                char buffer[bufferSize];    // Local buffer on the SPU
            #else
                char *buffer = 0;           // Working directly on main-memory on other platforms
            #endif

            BatchProcessor bp(batchDescEa, jobIdx, buffer, bufferSize);

            // Note the inner- and outer-loop pattern. The outer-loop does 
            // all the complicated DMA, double buffer, and other work.
            for (bp.First(); ! bp.Done(); bp.Next())
            {
                const Vector3* vectors = bp.GetArray<Vector3>(0);
                float* squares = bp.GetArray<float>(1);
                for (int i = 0; i < bp.GetNumElements(); ++i)
                {
                    squares[i] = DotProduct(vectors[i], vectors[i]);
                }
            }
        }

Alright, so you might be wondering why on earth anybody would be interested in
writing code like the above. Well, for starters, you're going to have to write
something like the above for the SPU no matter how you look at it. The
advantage is that we've already done the hard work for you. You just provide a
working area (the local buffer) and we DMA for you, we double-buffer, make sure
it fits, that alignment is respected, etcetera.
 
You can have up to sixteen input, output and in-out streams. You can redirect
the streams. You have control over how many elements you want per batch, or you
can let us figure it out for you. We have removed as many constraints on
element and stream size as possible without sacrificing performance.

Note that the above code is completely cross-platform. As mentioned earlier,
start on Xenon, go to PPU, and then dare to leap onto the SPUs. In our
experience, things tend to work on the SPUs out of the box.


- ParallelForEach

Given the exact same code as above, all we have to do is change:
 
        SerialForEach sfe(jobScheduler, squareVectorEntryPoint, bd);
        sfe.Run();
        sfe.WaitOn();
 
...into..
    
        const int numExecutionUnits = 4;
        ParallelForEach pfe(jobScheduler, squareVectorEntryPoint, bd, numExecutionUnits);
        pfe.Run();
        pfe.WaitOn();
 
And now your work is properly split up across the number of execution units you
asked for. 

- BatchProcessor & BatchDesc

The foreach object works on up to 16 arrays of elements (each array can be of a
different element type). Each array has to have the same number of elements.
The arrays are divided into batches which are processed. When using
`ParallelForEach` you cannot depend on ordered evaluation. Each array in a
batch has independent source and destination specifications; i.e. you can
choose to write the results back in place or redirect them to another area of
memory.

A `Batch Description` is used to collect up the information about the arrays of
data to be processed by a foreach instance. The `Batch` instance is used to
fetch batches for processing.

## Input and Output in more detail

    bd.SetArray<int>(0, inputStream, outputStream);

Tells the job side (Batch) to read the array from `inputStream` into a
single buffer in the job and then to take that *same* buffer, probably
modified, and write it back out to `outputStream`.

So:

    int *src = bp.GetArray<int>(0); 
    *src = <modifications that are DMA'd/MemCpy'd to outputStream>

This makes sense when using buffers, but becomes totally bizarre when not using
them (so called pass through mode).  So we assert when both input and output
are set, input != output, and there is no user supplied buffer.  When input ==
output and there is no user supplied buffer we modify the data directly.

## Data lifetime issues

PFE and SFE make a copy of the descriptor past in, so you don't have to keep
the descriptor around.  (This does limit us to 16 pending/running PFE/SFE
instances.)  The data the descriptor points to has to remain valid until the
PFE jobs have completed.

You can include a PFE/SFE as part of a dependency tree using
AddJobInstances, GetBeginJobInstanceHandle() and GetEndJobInstanceHandle()
instead of calling Run().  You don't have to keep the PFE/SFE object around
when using them in a dependency tree.  Once things are setup you can "fire and
forget".

## SPU imposed limitations

### Buffer size maximum

The SPU only have 256k of memory for all code and data.  This limits the
practical overall buffer space for working on data to 128k to 196k,
depending on the size of the code and usage of the stack.

You can declare the buffer size yourself, or use the Job Manager's `SpuHeap` 
functionality.

### Element size maximum

The sum of the sizes of all element types across all arrays must fit within
half of the buffer space given. (This is because we double buffer DMAs to
hide latency.)

### Element alignment

Each array must take a multiple of 16 bytes worth of space and must start on a
16 byte aligned address. The easiest way to ensure your total data size is a
multiple of 16 is to always work on a multiple of 16 elements.

Batch division must result in batches that contain a multiple of 16 bytes per
array. By default we try to automatically calculate proper batch divisions, but
also allow the caller to override the size of each batch.

### Data must not reside on the stack

The ps3 DMA functions will not DMA data from the PPU stack to the SPU.

## Set Up

- Create arrays (16 byte aligned and sized to be a multiple of 16)
- Create a `BatchDesc` instance.
- Call SetArray on the `BatchDesc` for each array.

### Data

        // in a common header file
        static int const sIntArrayIndex = 0;
        static int const sYourStructArrayIndex = 1;
        static int const sBoolArrayIndex = 2;


        // in local (ie: PPU) code
        int const numElements = 1024;

        int * intArray = YourAlignedAllocator(numElements * sizeof(int));
        YourStruct * yourStructArray = YourAlignedAllocator(numElements * sizeof(YourStruct));
        bool * boolArray = YourAlignedAllocator(numElements * sizeof(bool));

        BatchDesc batchDesc(numElements);

        // intArray is input only
        batchDesc.SetArray<int>(sIntArrayIndex, &intArray[0], 0);
        
        // yourStructArray is input/output, modified in place.
        batchDesc.SetArray<YourStruct>(sYourStructArrayIndex, &yourStructArray[0], &yourStructArray[0]);

        // boolArray is output only
        batchDesc.SetArray<bool>(sBoolArrayIndex, &boolArray[0]);

### Job

        // batchDescEa is passed to the job as its first parameter.
        // jobIndex is passed to the job as its second parameter.

        const size_t bufferSize = 40 * 1024;

        // be sure to allocate you buffer on the stack and not globally, since
        // globals are shared across all jobs when they run in the local environment
        EA_PREFIX_ALIGN(16) char buffer[bufferSize] EA_POSTFIX_ALIGN(16);

        BatchProcessor batchProcessor(batchDescEa, jobIndex, buffer, bufferSize);

        for( batchProcessor.First(); ! batchProcessor.Done(); batchProcessor.Next() )
        {
            int const * intSlice = batchProcessor.GetArray<int>(sIntArrayIndex);
            YourStruct * yourStructSlice = batchProcessor.GetArray<YoutStruct>(sYourStructArrayIndex);
            bool * boolSlice = batchProcessor.GetArray<bool>(sBoolArrayIndex);

            int numElements = batchProcessor.GetNumElements();
            int elementOffset = batchProcessor.GetElementOffset();

            for (int j = 0; j < numElements; ++j)
            {
                // each Slice contains [elementOffset, elementOffset + batchSize) of its respective Array.
                // the YouStruct and bool Slices can me modifed and the results will be DMA'd back.
            }
        }

## Execution

        // in local (ie: PPU) code

        ParallelForEach pfe(mJobScheduler, mForEachJobEntryPoint, bd, numJobs);

        pfe.WaitForEnd(); // TODO: rename

## Pass-Through mode on non-SPU platforms

If you pass in a buffer to the `BatchProcessor` constructor on a non-SPU
platform the `BatchProcessor` code will emulate an SPU DMA by coping the array
data into the buffer and back out to array. In general you'll want avoid this
in final code by passing in a NULL pointer for the buffer on non-SPU platforms.

IE:

        // batchDescEa is passed to the job as its first parameter.
        // jobIndex is passed to the job as its second parameter.

        const size_t bufferSize = 40 * 1024;

        #ifdef EA_PLATFORM_PS3_SPU
            // be sure to allocate you buffer on the stack and not globally, since
            // globals are shared across all jobs when they run in the local environment
            EA_PREFIX_ALIGN(16) char buffer[bufferSize] EA_POSTFIX_ALIGN(16);
        #else
            char buffer = 0;
        #endif

        BatchProcessor batchProcessor(batchDescEa, jobIndex, buffer, bufferSize);

## Controlling the number of elements per batch

You may want to override the automatic batch division algorithm. We provide
the following methods for doing this:

- BatchDesc::SetElementsPerBatch(int N)
    Completely overrides the internal calculation and uses the number you
    provide. The total number of elements to be processed must be a multiple of
    N.

- BatchDesc::SetElementMultiplePerBatch(int N)
    Ensure that batches have N-many elements. (IE: if N is 3, batches will have
    a multiple of 3 elements in them) The total must be divisible into N
    evenly.

## Dynamic vs Even load balancing

The `ParallelForEach` constructors last argument is the batch division method,
and default to `FOR_EACH_DIVISION_DYNAMIC`. The other currently available option
is `FOR_EACH_DIVISION_EVEN`.

- FOR_EACH_DIVISION_DYNAMIC
    Used when the amount of time taken to process an element A vs element B can
    greatly vary. This is the default since we don't know anything about the
    amount of time a given element will take to process. Unfortunately dynamic
    balancing requires active co-ordination amongst the jobs processing the
    batches. Co-ordinating has overhead that eats up some time. A example of
    where dynamic balancing makes sense would be rendering a fractal. Some
    pixels will take considerably more time to computer than others, so an even
    division of pixels across all jobs would lead to some jobs finishing
    earlier than other jobs.

- FOR_EACH_DIVISION_EVEN
    If the time it takes to process any given element is around the same we can
    pre-divide the work into evenly balanced batches. Since the jobs no longer
    have to co-ordinate when running we gain back some speed.

## Other Notes

There is a hard coded limit of 16 Arrays per BatchDesc.

You can pass two addition parameters to each job. (These are called Param2 and
Param3 to mirror the Job interface. Param0 and Param1 are used by the foreach
instance.) You'll probably want to pass in the effective address of more
parameters that you can then DMA over using the Dma Wrappers.

You can use SleepOn() be calling SetAllowSleepOn() on the for each instance.

## FAQ

Q. How do I output less elements than I input. (Say for Triangle Culling)
A. PFE can still be used for the input, but you'll have to manage the output
   manually. This can be done by using the Dma and Atomic wrappers in JobUtil.

Q. How do I output a predictable fraction of the elements I input.
A. Redefine you input into a struct that contains N inputs so you input and
   output elements counts are once again equal.

Q. How do I get overlapping batches?
A. Run multiple PFE instances offsetting their starting points.


# Need help?

Join the Job Managers Users mailing list and post your problem. We'll be happy
to help.