Ad hoc Geek

Pixel Bender has been around for a little while now and it’s a very cool idea, promising incredible speed improvements by allowing developers to make the most of multi-core processors and GPUs. It seems as though it was designed primarily for Adobe image manipulation software, but, since images are just arrays of bytes it can also be used to speed up any parallelisable code you might have within Flash.

A fast intro to Pixel Bender

The main unit of operation in pixel bender is the kernel. Generally, each kernel will take a source image and calculate the value of a single pixel in the output image. i.e. for every pixel in your source image, a single kernel instance will be run which can use that whole image to calculate the value of a single pixel (although you won’t usually want it to look at the whole image – the less dependent it is on other pixels, the faster it can run).

The kernel language is intended to be fast and as such is fairly simplistic. A simple kernel which converts every pixel in the source image to black would be written as follows :

<languageVersion : 1.0;>
 
kernel Gothify
<   namespace : "com.example";
    vendor : "Example.com";
    version : 1;
    description : "Fills every pixel in the source image with black";
>
{        
    input image4 source;
    output pixel4 result;
 
    void evaluatePixel()
    {
        result = pixel4(0,0,0,1.0);
    }
}

The developer’s guide says to use pixel4(0,0,0,0), but since the last value is the alpha channel, that just ends up with a transparent black image. It also doesn’t include the input image4, and while this may do something in photoshop, it’s not going to give you any output in the pixel bender IDE.

Now, an image is basically just an array of pixels, and, within pixel bender, a 4-channel pixel (a pixel4 type) is just a vector of floats. We can use any values within a pixel4, limited only by the bounds of a standard float size. So, we could change the evaluatePixel function above to the following and it wouldn’t make any difference to the output image :

void evaluatePixel()
{
    result = pixel4(-1500.67,-45.0,-32.333,515.47);
}

It’s only the values between 0.0 and 1.0 that can change the output colour, anything above 1.0 is at maximum and anything below 0.0 is at minimum. This means we can use pixel bender to operate on any array of floating point values as long as we’re happy for it to operate on pixel sized chunks of data in isolation (the pixel bender graph language does allow chaining of kernels, but this isn’t available to us in the flash player, so I’m going to ignore it for now).

Parallelising the Binomial Option Pricing Algorithm

There’s a short, fairly readable paper here [Ganesan, Chamberlain, Buhler] which gives some ideas for how to parallelise the algorithm. I’m only going to implement the scheme which is probably best illustrated by their fig. 2. This requires me to pass to each kernel the input image (array of option values at time T), the risk-neutral probability of an up-tick and the discount factor over one time step.
I’ll then have to call the resulting kernel (or array of kernels, depending on how you think of it), N-1 times to get the final option price.

The kernel I wrote ended up like this :

<languageVersion : 1.0;>
 
kernel BinomialOptionPricer
<   namespace : "com.adhocgeek";
    vendor : "Ad hoc Geek";
    version : 1;
    description : "Calculates the one step binomial option price";
>
{
    input image3 src;
    output pixel3 dst;
 
    parameter float p; //risk-neutral probability of an up-tick
    parameter float df; //discount factor over one time step
 
    void evaluatePixel()
    {
        pixel3 down = sampleNearest(src, outCoord());
        pixel3 up = sampleNearest(src, outCoord() + float2(1.0, 0));
        float V = (p*up.x + (1.0-p)*down.x)*df;
 
        dst = pixel3(V, 0, 0);
    }
}

Using the Pixel Bender Filter in Actionscript

This is actually incredibly easy. Flash 10 gives us a new class called the Shader which represents a Pixel Bender kernel. You can use this with the new ShaderJob class to trigger a set of kernel operations on any vector or byte array that you’ve created. I’m not going to try and write a tutorial, so here’s the final actionscript code I wrote (you should notice it’s quite similar to the previous version):

[Embed("BinomialOptionPricer.pbj", mimeType="application/octet-stream")]
private var BinomialOptionPricer:Class;
 
private function getPrice(  N:Number, //Number of steps
                                    T:Number, //Time to expiry (in years)
                                    S:Number, //Spot price of underlying
                                    K:Number, //Option strike
                                    v:Number, //Volatility of underlying
                                    r:Number, //risk-free rate
                                    NUMOPTIONS:Number 
                                 ):Number
{
    var dt:Number = T/N; //one time step
 
    var u:Number = 1 + v*Math.sqrt(dt); //up-tick
    var d:Number = 1 - v*Math.sqrt(dt); //down-tick
    var p:Number = 0.5 + r*Math.sqrt(dt)/(2*v); //risk-neutral prob. of up-tick
    var df:Number = 1/(1+r*dt); //discount factor over 1 time step, dt
 
    var optionValues:Vector.<Number> = new Vector.<Number>();
 
    //Populate the fake pixels array 
    var i:int, j:int, ST:Number;
    for (j=0; j < NUMOPTIONS; j++)
    {
        for (i=0; i < N+1; i++) 
        {
            ST = spot.value * Math.pow(u, i) * Math.pow(d, N-i);
            optionValues.push((ST > K)? ST - K : 0);
            optionValues.push(0);
            optionValues.push(0);
        }
    }
 
 
    //work backwards to get expected option value at each previous stage
    var sj:ShaderJob;
    var shader:Shader = new Shader(new BinomialOptionPricer() as ByteArray);
    shader.data.src.input = optionValues;
    shader.data.src.height = NUMOPTIONS;
    shader.data.p.value = [p];
    shader.data.df.value = [df];
    for (i=N; i > 0; i--)
    {
        shader.data.src.width = i+1;
        sj = new ShaderJob(shader, optionValues, i+1, NUMOPTIONS);
        sj.start(true);
    }
 
    return optionValues[0]; 
}

Points to note are where I’ve embedded the kernel in the actionscript itself and where I’ve added the ability to run the calculation multiple times in parallel (simulating running the calculation for many different options at once). Each line in the source “image” represents a different option (although they’re all using the same source data at the moment).

Here (if you have Flash Player 10 installed) is the resulting swf (view source enabled, of course) :

It’s slightly faster than the straight actionscript version, but not by a great deal, where it really shines is in calculating multiple options at once. There’s an interesting non-linear relationship between the number of lines in the source “image” and the speed of this particular algorithm. I might graph it at some point…