Satnam Singh's MSDN Blog

The ADSR Envelope of Programming (Humour)

2011-08-04T13:49:51Z

For those of you that grew up with ADSR envelopes on the BBC Microcomputer or the Commodore 64 or on your Korg....(read more)

The Last Programmer Standing will be holding an FPGA

2011-08-01T10:22:32Z

In my article Computing Without Processors http://cacm.acm.org/magazines/2011/8/114935-computing-without-processors/fulltext in the August edition of Communications of the ACM I advocate the deployment of heterogeneous computing technology to help address the ever pressing requirements we have for computing with reduced latency and reduced energy consumption. Significant challenges lie ahead for those that try to reign in the extreme computing and communication power offered by alternative architectures...(read more)

Computing Without Processors article on ACM Queue

2011-06-28T10:12:42Z

My article on Computing Without Processors is on the ACM Queue page now: http://queue.acm.org/detail.cfm?id=2000516 The article explains why it is important for us to learn to program not just regular microprocessors but also many other kinds of computing elements. As we struggle to meet the latency and energy consumption constraints we will inevitably be forced to use heterogeneous architectures which comprise the evolution of today's GPUs (for data-parallelism) and FPGA (for 2D and 3D spatial computing...(read more)

Creating a Windows DLL from a Haskell Program and calling it from C++

2011-04-19T16:40:57Z

Every so often you have to leave the warm comfortable safe world of Haskell and venture out into what some unsavoury types call the "the real world". I've always thought it better to call the real world rather than have it call on me in Haskell-land. But when that does not work you have the bite the bullet and make a DLL that can be called from other Windows programs. Every so often I do this and it works (for a single DLL) and then time passes and GHC changes and then suddenly you have to do something...(read more)

Compiling C# Programs to FPGA Circuits: An Ethernet Packet Processing Example

2011-02-15T18:10:46Z

In a previous blog article I showed how to get the default Ethernet address swap circuit working on the ML605 board. The address swap module (which can be generated in VHDL or Verilog) is tedious to write yourself because you have to explicitly write it as a state machine. In typical hardware description languages you have "lost the semicolon" and the program you write very much resembles coding with call-backs in GUIs or REST-style programming or writing directly in continuation passing style. With...(read more)

Using the Virtex-6 Embedded Tri-Mode Ethernet MAC Wrapper v1.4 with the ML605 Board

2011-02-11T13:10:13Z

Whenever I get a new Xilinx development board I go through the tedious process of porting my circuits that use Ethernet communication to the new board. To save other people the pain I went through to get this to work I have written this blog which outlines the changes you need to make to the automatically generated Ethernet MAC wrapper to make the default echo circuit work. Note that these instructions only apply to the Xilinx ML605 development board : I have tested these instructions with ISE version...(read more)

Reconfigurable Data Processing for Clouds

2011-01-18T14:28:20Z

Along with Anil Madhavapeddy at the University of Cambridge I've been thinking about how to apply reconfigurable computing technology (for example FPGAs ) in data-centres and in cloud computing systems. Reconfigurable computing for some time now has had the potential to make a huge impact on mainstream high performance computing. We will soon have a million LUTs or more of highly parallel fine grain parallel processing power, and the ability to define high bandwidth custom memory hierarchies offers...(read more)

Computing a Parallel Facebook Life

2011-01-14T22:41:38Z

Soon there will be so much information about our lives entered into social network systems to allow us to perform calculations with this historical data to compute "what-if" scenarios i.e. compute a parallel life we could have had if we had made some different decision in the past. For example, if I had gone to Bill's party instead of Craig's party two years ago I would have met Bob there and never have met Anders etc. etc. We could synthesize an entire parallel life based on all the information...(read more)

Learn about alternative high performance computing at the FPGA 2011 conference

2010-12-28T13:01:58Z

The ACM/SIGDA International Symposium on Field-Programmable Gate Arrays is the premier conference for presentation of advances in all areas related to FPGA technology. FPGAs for computing used to be confined to a niche market of engineers that were willing to carefully hand craft circuits to get extreme performance that could not be achieved with regular processors or GPUs. Today FPGAs are become one of the exciting new processing elements that form the heart of heterogeneous computing systems that...(read more)

Compiling C# Programs into FPGA Circuits: Factorial Example

2010-10-15T15:34:07Z

This blog article gives a practical introduction to how C# programs can be compiled into FPGA circuits using the Kiwi system developed by myself and David Greaves at the University of Cambridge Computer Lab. Our starting point will be a C# program developed inside Visual Studio 2010 for computing factorial: This program can be compiled and executed inside Visual Studio to report the factorial of 5 (i.e. 120). However, using our Kiwi system this program can also be converted into a Verilog circuit...(read more)

F# Black-Scholes running on GPUs and SSE3 Multicore Processors using Accelerator

2010-10-14T09:05:23Z

The Accelerator library from Microsoft helps us write code which can execute on GPUs and multicore processors using SSE3 vector instructions. There is also an experimental FPGA target. To illustrate data-parallel programming in F# using Accelerator I show below an implementation of the Black-Scholes computation which is based on the sample from the CUDA SDK by Victor Podlozhnyuk at NVIDIA and we also draw inspiration from Geoff Mainland's Haskell reformulation of this sample. The objective of this...(read more)

Kiwi Synthesis of C# and F# Combinational Circuit Models into FPGA Circuits

2010-04-28T16:02:30Z

The Kiwi project aims to automatically translate concurrent C# and F# programs into FPGA circuits for accelerated execution. I work with David Greaves at the University of Cambridge Computer Laboratory and we have a prototype system that consumes .NET bytecode and converts it into VHDL or Verilog circuit descriptions. Kiwi usually produces a sequential circuit from a multi-threaded C# program which typically implements a data-path or finite state machine. However, it would also be convenient to describe...(read more)

A C# implementation of a convolver using Accelerator for GPGPU and multicore targets using LINQ operators

2010-01-11T12:43:41Z

In a previous blog post I showed how a 2D convolver can be written in F# using Microsoft's Accelerator system for GPGPU and SIMD x64 multicore programming targets. This blog article explains how the same 2D convolver can also be nicely expressed in C# and it illustrates a few cool C# and LINQ features including type inference, extension methods, the indexed Select operator and the Aggregate operator. I also give a more old school C# implementation at the end of this blog article. First, here is the...(read more)

An F# Functional Geometry Description of Escher's Fish

2010-01-06T01:58:00Z

This blog explains how Escher 's fish wood carving can be expressed in F# using functional geometry which was first presented by Peter Henderson in 1982. This very functional and compositional style of describing pictures is nicely expressed in F# . Functional geometry provides us with a nice algebra for pictures which has been used by the author as the basis of a system for automatically computing the layout of digital circuits expressed in functional languages (e.g. Lava ). First, here is...(read more)

Distracted by Abstraction - A poem about F#

2009-12-25T14:10:00Z

You infer the intent in my expression, Although not always without qualification. My heart was torn between function and object, But you have rendered them as one. I've always been lazy by nature, Yet I'm drawn to your conditional strictness. I have emerged downcast from a haze of inheritance, To a higher order Nirvana. Although by any unit of measure, You're not a principled type. I yearn so deeply to functorize you, But you say that all you want is your own private namespace. ...(read more)

GPGPU and x64 Multicore Programming with Accelerator from F#

2009-12-15T13:50:00Z

Microsoft recently released a preview of the Accelerator V2 GPU and x64 multicore programming system on Microsoft Connect. This system provides a civilized level of abstraction for writing data-parallel programs that execute on GPUs and multicore processors. An experimental FPGA target is under development.

Even on my low end graphics card I get pretty impressive performance results for the 2D convolver that is described in this blog. All 8 cores of my 64-bit Windows 7 workstation are also effectively exercised by the x64 multicore target, which exploits SIMD processor instructions and multithreading. I won't say anything about performance in this blog post since what I want to focus on is how to use Accelerator from the F# functional programming language. We will work backwards by starting off with a complete implementation of a two dimensional convolver. Step by step we show how this convolver is expressed using Accelerator from F#.

First here is the beautiful implementation of a two dimensional convolver. The rest of this post explains why this code works.

open System

open Microsoft.ParallelArrays

[<EntryPoint>]

let main(args) =

// Declare a filter kernel for the convolution

let testKernel = Array.map float32 [| 2; 5; 7; 4; 3 |]

// Specify the size of each dimension of the input array

let inputSize = 10

// Create a pseudo-random number generator

let random = Random (42)

// Declare a psueduo-input data array

let testData = Array2D.init inputSize inputSize (fun i j -> float32 (random.NextDouble() *

float (random.Next(1, 100))))

// Create an Accelerator float parallel array for the F# input array

use testArray = new FloatParallelArray(testData)

// Declare a function to convolve in the X or Y direction

let rec convolve (shifts : int -> int []) (kernel : float32 []) i (a : FloatParallelArray)

= let e = kernel.[i] * ParallelArrays.Shift(a, shifts i)

if i = 0 then

else

e + convolve shifts kernel (i-1) a

// Declare a 2D convolver

let convolveXY kernel input

= // First convolve in the X direction and then in the Y direction

let convolveX = convolve (fun i -> [| -i; 0 |]) kernel (kernel.Length - 1) input

let convolveY = convolve (fun i -> [| 0; -i |]) kernel (kernel.Length - 1) convolveX

convolveY

// Create a DX9 target and use it to convolve the test input

use dx9Target = new DX9Target()

let convolveDX9 = dx9Target.ToArray2D (convolveXY testKernel testArray)

printfn "DX9: -> \r\n%A" convolveDX9

// Create a X64 multi-core target and use it to convolve the test input

use x64MCTarget = new X64MulticoreTarget()

let convolveMC = x64MCTarget.ToArray2D (convolveXY testKernel testArray)

printfn "MC: -> \r\n%A" convolveMC

This program sets up a pseudo-random two dimensional input array, declares a two dimensional convolver and then uses two of the targets supported by Accelerator to convolve the input array. The first target uses a GPU to perform the convolution and the second target uses multiple x64 processor cores and makes use of special SIMD instructions. When this program is run it produces the following output:

DX9: ->

[[4124.88916f; 4006.17432f; 3619.18579f; 4345.93262f; 6214.79004f; 7851.854f;

6639.24854f; 6447.55664f; 4849.12109f; 5399.95215f]

[3999.14282f; 3891.52783f; 3691.94263f; 4562.6543f; 6413.09766f; 7815.42236f;

6846.51172f; 6543.7251f; 4950.29443f; 5539.11377f]

[4643.48877f; 4448.87451f; 4293.98975f; 4958.56201f; 6505.2334f; 7420.50586f;

7069.68311f; 6669.47803f; 5239.27148f; 5991.7793f]

[5392.69336f; 5102.70215f; 4892.03027f; 5074.26025f; 5990.81055f; 6369.36475f;

6808.10986f; 6476.23047f; 5292.99463f; 6154.81885f]

[8989.50488f; 8397.94434f; 7150.7959f; 5570.37061f; 5170.64307f; 5217.95703f;

6137.8042f; 6353.71484f; 5624.02979f; 6247.72852f]

[12248.4824f; 11455.2373f; 9597.80078f; 6825.54688f; 5358.00586f; 4921.00293f;

6604.14258f; 7520.95361f; 7361.63232f; 7363.42578f]

[16833.0352f; 15605.6055f; 12528.748f; 8065.896f; 5745.88574f; 5093.6792f;

7391.62354f; 9219.54004f; 9945.78711f; 9624.86328f]

[13102.8984f; 12436.5234f; 10673.6123f; 7992.61035f; 6201.81299f; 5618.32861f;

7226.84521f; 9439.95508f; 10573.7754f; 10420.5703f]

[14555.6426f; 14135.1074f; 12600.9141f; 10219.6904f; 8211.8623f; 7361.39746f;

7424.83643f; 9536.95605f; 10884.3418f; 10907.2549f]

[10885.0293f; 11083.6436f; 11301.6055f; 11469.3613f; 10785.7178f; 10094.2041f;

9660.19238f; 11580.3281f; 12738.5098f; 12256.5371f]]

MC: ->

[[4124.88965f; 4006.17529f; 3619.18652f; 4345.93311f; 6214.79053f; 7851.85449f;

6639.24902f; 6447.55664f; 4849.12109f; 5399.95215f]

[3999.14282f; 3891.52783f; 3691.94263f; 4562.6543f; 6413.09814f; 7815.42236f;

6846.51172f; 6543.7251f; 4950.29443f; 5539.11377f]

[4643.48877f; 4448.87451f; 4293.98975f; 4958.56201f; 6505.23389f; 7420.50586f;

7069.68311f; 6669.47803f; 5239.27148f; 5991.7793f]

[5392.69336f; 5102.70215f; 4892.03027f; 5074.26074f; 5990.81152f; 6369.36523f;

6808.10986f; 6476.23047f; 5292.99463f; 6154.81934f]

[8989.50488f; 8397.94434f; 7150.7959f; 5570.37061f; 5170.64307f; 5217.95752f;

6137.80469f; 6353.71484f; 5624.03027f; 6247.72852f]

[12248.4844f; 11455.2383f; 9597.80078f; 6825.54785f; 5358.00586f; 4921.00293f;

6604.14355f; 7520.95459f; 7361.63232f; 7363.42627f]

[16833.0352f; 15605.6055f; 12528.748f; 8065.896f; 5745.88574f; 5093.67969f;

7391.62354f; 9219.54004f; 9945.78906f; 9624.86328f]

[13102.8984f; 12436.5234f; 10673.6133f; 7992.61084f; 6201.81348f; 5618.3291f;

7226.84521f; 9439.95605f; 10573.7754f; 10420.5713f]

[14555.6426f; 14135.1074f; 12600.916f; 10219.6914f; 8211.86328f; 7361.39795f;

7424.83643f; 9536.95703f; 10884.3418f; 10907.2559f]

[10885.0293f; 11083.6445f; 11301.6074f; 11469.3633f; 10785.7188f; 10094.2051f;

9660.19336f; 11580.3281f; 12738.5107f; 12256.5371f]]

A convolver computes a weighted average around some point. Image editing programs typically have an operation that smoothes an image and this is usually performed by a two dimensional convolution around each pixel. We shall discuss how to implement a one dimensional (1D) convolver fist and then generalize this to a two dimensional (2D) convolver afterwards. A convolution in one dimension can be expressed as a weighted sum around each value in an input array (or stream):

Here is a concrete example of a one dimensional convolution of an eight element array x which is being convolved by a five element filter kernel a to produce an eight element result array y. The filter kernel a appears to be like a window which slides across each element of the input array. To simplify the explanation and code, the filter is placed to the left of the element being convolved. A more realistic convolver would centre the filter kernel over the element being convolved but that introduces some extra boundary condition code which I donÃ¢ÂÂt want to get bogged down with in this blog.

We can implement a 1D software convolver in F# as follows:

let clamp i (input : float32 [])

= if i < 0 then

input.[0]

else

input.[i]

let convolveAt i (kernel : float32 []) input

= Array.sum [| for k in 0 .. kernel.Length - 1 -> clamp (i-k) input * kernel.[k] |]

let softwareConvolver kernel (input : float32 [])

= [| for i in 0 .. input.Length - 1 -> convolveAt i kernel input |]

The clamp function has the following type which accepts an array index of type int and an array of float32 values and returns an element of the array or a clamped value.

val clamp : int -> float32 [] -> float32

This function allows us to define values for negative array indices and works by returning the value of the first array element input.[0] whenever we try to compute a negative index of the input array. Note that in F# arrays are indexed with the .[...] notation.

The convolveAt function has the type:

val convolveAt : int -> float32 [] -> float32 [] -> float32

and computes the convolution of a single position in the input array to produce the result at the corresponding output array. For example, the picture above illustrates the calculation of:

convolveAt 5 [| 2; 5; 7; 4; 3 |] [| 7; 2; 5; 9; 3; 8; 6; 4 |]

Note that array literals in F# are written using [| ... |] brackets. The definition of convolveAt makes use of an array comprehension which allows us to specify an expression that defines the values of an array:

[| for k in 0 .. kernel.Length - 1 -> clamp (i-k) input * kernel.[k] |]

If the value of kernel.Length is 5 and if we are convolving at the first array index value of 0 for i then this is equivalent to writing:

[| clamp (- 4) input * kernel.[4] ;

clamp (- 3) input * kernel.[3] ;

clamp (- 2) input * kernel.[2] ;

clamp (- 1) input * kernel.[1] ;

clamp 0 input * kernel.[0] ;

The final step is to sum the elements of this array which is accomplished with a call to the Array.sum library function.

We can also exploit an array comprehension to produce the completely convolved result array by applying the single point convolution function to every element of the array by using the software function which has the type:

val softwareConvolver : float32 [] -> float32 [] -> float32 []

and the definition:

let softwareConvolver kernel (input : float32 [])

= [| for i in 0 .. input.Length - 1 -> convolveAt i kernel input |]

Although this code correctly implements a 1D convolver it is not an ideal starting point for a parallel implementation of convolution. To make an efficient implementation of the convolver for Accelerator we have to express the computation avoiding the manipulation of absolute array indices. Instead we should try to think in terms of whole array operations and relative array indices. The first step in this direction is to think about how to compute the whole result array y rather than how to compute an individual element y[i]. That is, we wish to compute an array which has the following form:

y = [y[0], y[1], y[2], y[3], y[4], y[5], y[6], y[7]]

Furthermore, we wish to define y using only whole array operations. To help spot how we should do this the equations for y are expanded:

y[0] = a[0]x[0] + a[1]x[-1] + a[2]x[-2] + a[3]x[-3] + a[4]x[-4]

y[1] = a[0]x[1] + a[1]x[0] + a[2]x[-1] + a[3]x[-2] + a[4]x[-3]

y[2] = a[0]x[2] + a[1]x[1] + a[2]x[0] + a[3]x[-1] + a[4]x[-2]

y[3] = a[0]x[3] + a[1]x[2] + a[2]x[1] + a[3]x[0] + a[4]x[-1]

y[4] = a[0]x[4] + a[1]x[3] + a[2]x[2] + a[3]x[1] + a[4]x[0]

y[5] = a[0]x[5] + a[1]x[4] + a[2]x[3] + a[3]x[2] + a[4]x[1]

y[6] = a[0]x[6] + a[1]x[5] + a[2]x[4] + a[3]x[3] + a[4]x[2]

y[7] = a[0]x[7] + a[1]x[6] + a[2]x[5] + a[3]x[4] + a[4]x[3]

We need some way of expressing the result of y in terms of whole array operations on a or x or through the use of only relative indices i.e. we wish to avoid mentioning absolute indices. Notice that the computation above does have whole operations e.g. the second column on the left shows the whole of the x array (shifted left by one) is multiplied by the scalar value a[1]. The pattern occurs across all four columns with each column corresponding to one of the five coefficients. In each column the corresponding scalar coefficient value is used to multiply a shifted version of the x input. This observation allows us to express the value of y using only whole array operations on x and its shifted counterparts. The calculations below represent the x and y arrays as a vector. The multiplication corresponds to the multiplication of a vector by a scalar value. The addition corresponds to the addition of two vectors.

y = [y[0], y[1], y[2], y[3], y[4], y[5], y[6], y[7]]

= a[0] * [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7]] +

a[1] * [x[-1], x[0], x[1], x[2], x[3], x[4], x[5], x[6]] +

a[2] * [x[-2], x[-1], x[0], x[1], x[2], x[3], x[4], x[5]] +

a[3] * [x[-3], x[-2], x[-1], x[0], x[1], x[2], x[3], x[4]] +

a[4] * [x[-4], x[-3], x[-2], x[-1], x[0], x[1], x[2], x[3]]

This representation is an improvement from the original representation because it contains vector multiplications and vector additions which can be performed in parallel. The original formulation contained multiplications of scalar values (i.e. an element of the coefficient array) by scalar values (e.g. an element of the input array). This representation is not directly amenable to a parallel implementation.

To make the nature of the data-parallel operation shown above clearer we introduce the shift operator which takes as input an array and an amount to shift by N and returns an array of the same size except all the elements are shifted up by the specified number of positions. The first N elements of the result array are clamped by filling them with the first element of the input array. Here are some examples of shifts:

shift (x, 0) = [7, 2, 5, 9, 3, 8, 6, 4] = x

shift (x, -1) = [7, 7, 2, 5, 9, 3, 8, 6]

shift (x, -2) = [7, 7, 7, 2, 5, 9, 3, 8]

Using the shift operator we can re-express y as:

y = a[0] * shift (x, 0) + a[1] * shift (x, -1) + a[2] * shift (x, -2) + a[3] * shift (x, -3) +

a[4] * shift (x, -4)

This leads to a data-parallel implementation which can perform each coefficient multiplication in parallel with the others followed by a sum in parallel. These parallel operations are described in the following figure.

Each blue arrow in this picture corresponds to a data-parallel operation. The F# program below shows how to implement this 1D convolution using both the DX9 GPU target and the x64 SIMD multi-core target.

open System

open Microsoft.ParallelArrays

[<EntryPoint>]

let main(args) =

// Declare an input data array

let inputData = Array.map float32 [| 7; 2; 5; 9; 3; 8; 6; 4 |]

// Declare filter kernel for the convolution

let kernel = Array.map float32 [| 2; 5; 7; 4; 3 |]

let kernelSize = Array.length kernel

// Create an Accelerator float parallel array for the F# input array

use inputArray = new FloatParallelArray(inputData)

// Build the expression

let rec expr i = let e = kernel.[i] *

ParallelArrays.Shift(inputArray, -i)

if i = 0 then

else

e + expr (i-1)

// Create DX9 target and compute result

use dx9Target = new DX9Target()

let resDX = dx9Target.ToArray1D(expr (kernelSize-1))

printfn "DX9 --> \r\n%A" resDX

// Create X64 multi-core target and compute result

use mc64Target = new X64MulticoreTarget()

let resMC = mc64Target.ToArray1D(expr (kernelSize-1))

printfn "X64MC --> \r\n%A" resMC

When run this produces the expected output:

DX9 -->

[|147.0f; 137.0f; 118.0f; 106.0f; 115.0f; 120.0f; 124.0f; 133.0f|]

X64MC -->

[|147.0f; 137.0f; 118.0f; 106.0f; 115.0f; 120.0f; 124.0f; 133.0f|]

To use an Accelerator target the input data must be created for an Accelerator data-parallel array. Typically the data represented by these arrays will be held in some memory specified by the target implementation. For example, for the DX9 GPU target the input values will be copied to memory on your graphics card. Accelerator provides several methods for creating data parallel arrays and here we create a floating point data-parallel array using a constructor:

new :: float32 [] -> FloatParallelArray

and the type of inputArray is FloatParallelArray .

In your F# program you should think of a FloatParallelArray as being a reference or a handle to some real array somewhere else. When you write computations over values of type FloatParallelArray what you are really doing is building up a symbolic expression tree that represents the computation that you want. When you try to evaluate such an expression the Accelerator system JITs (e.g. to GPU code via DX9) to produce the actual code for performing your computation and executes it with the data in the input data-parallel arrays and transmits the result back to your F# program.

Accelerator provides a library of data-parallel arrays and data-parallel operations over its data-parallel arrays. To perform a data-parallel multiplication of a data-parallel array by a single kernel coefficient we use one of AcceleratorÃ¢ÂÂs data-parallel multiplication operations (there are many other overloads):

val (*) : FloatParallelArray -> FloatParallelArray -> FloatParallelArray

This does not immediately perform the multiplication. What is really happening is that an expression tree is built up with a multiplication node in it. However, the JIT-ing nature of the Accelerator implementation almost makes it looks like the code is being executed immediately.

The addition operation used in the 1D convolver is also a data-parallel addition over FloatParallelArrays:

val (+) : FloatParallelArray -> FloatParallelArray -> FloatParallelArray

Finally, the shift operation here works over one dimensional arrays of type FloatParallelArray and takes just one number which specified how much to shift by:

val ParallelArrays.Shift : FloatParallelArray -> int -> FloatParallelArray

We may be tempted to specify the overall expression for the convolver by writing:

let convolver1D kernel input

= List.fold 0 [ for k in 0 .. kernel.Length - 1

-> kernel.[i] * ParallelArrays.Shift(inputArray, -i) ]

and how nice that would be but sadly we donÃ¢ÂÂt have a proper 0 yet so instead we write a recursive formulation:

// Build the expression

let rec expr i = let e = kernel.[i] *

ParallelArrays.Shift(inputArray, -i)

if i = 0 then

else

e + expr (i-1)

where expr has the type:

val expr : int -> FloatParallelArray

Given the index of the highest element in the kernel this function builds up an expression which computes the 1D convolution. This expression is used to call the DX9 GPU target to perform the computation and retrieve the result resDX which has the type float32 []:

// Create DX9 target and compute result

use dx9Target = new DX9Target()

let resDX = dx9Target.ToArray1D(expr (kernelSize-1))

printfn "DX9 --> \r\n%A" resDX

A target only needs to be created once. The first time a target is created for DX9 there is a delay while the system is initialized. For benchmarking it is a good idea to perform a dummy computation first to Ã¢ÂÂwarm upÃ¢ÂÂ the system.

The previous example convolved a one dimensional (1D) matrix. In this section we show how we can convolve a 2D matrix by applying the convolution independently to each line. This computation is illustrated in the diagram below for the following array of arrays:

[|[|7; 2; 5; 9; 3; 8; 6; 4 |];

[|2; 8; 7; 4; 8; 9; 3; 5 |]|]

An F# version of a 1D convolution of 2D input data is shown below which illustrates convolution in the X and Y directions (independently).

open System

open Microsoft.ParallelArrays

[<EntryPoint>]

let main(args) =

// Declare an input data array

let inputData

= Array2D.map float32 (array2D [ [ 7; 2; 5; 9; 3; 8; 6; 4 ];

[ 2; 8; 7; 4; 8; 9; 3; 5 ] ])

// Declare filter kernel for the convolution

let kernel : = Array.map float32 [| 2; 5; 7; 4; 3 |] ;

let kernelSize = kernel.Length

// Create an Accelerator float parallel array for the F# input array

use inputArray = new FloatParallelArray(inputData)

// Build the expression to convolve in the Y direction

let rec exprY i = let e = kernel.[i] *

ParallelArrays.Shift(inputArray, [| 0; -i |])

if i = 0 then

else

e + exprY (i-1)

// Create DX9 target and compute result

use dx9Target = new DX9Target()

let resDXY = dx9Target.ToArray2D(exprY (kernelSize-1))

printfn "DX9 Y-dir --> \r\n%A" resDXY

// Build the expression to convolve in the X direction

let rec exprX i = let e = kernel.[i] *

ParallelArrays.Shift(inputArray, [| -i; 0 |])

if i = 0 then

else

e + exprX (i-1)

let resDXY = dx9Target.ToArray2D(exprX (kernelSize-1))

printfn "DX9 X-dir --> \r\n%A" resDXY

When run, this code computes the correct values:

$ convolver_fs_1d_of_2d_input.exe

DX9 Y-dir -->

[[147.0f; 137.0f; 118.0f; 106.0f; 115.0f; 120.0f; 124.0f; 133.0f]

[42.0f; 54.0f; 82.0f; 113.0f; 123.0f; 138.0f; 144.0f; 132.0f]]

DX9 X-dir -->

[[147.0f; 42.0f; 105.0f; 189.0f; 63.0f; 168.0f; 126.0f; 84.0f]

[137.0f; 54.0f; 109.0f; 179.0f; 73.0f; 170.0f; 120.0f; 86.0f]]

Although this code performs multiplication, shifting and adding of arrays as we saw before in this case we use a different overloaded functions that work over two dimensional arrays and the shift operation uses a two element array to specify how much to shift by in each direction.

val ParallelArrays.Shift : FloatParallelArray -> int [] -> FloatParallelArray

We can make a two dimensional convolver by first convolving in the x-direction and then convolving in the y-direction. Or we can perform a convolution in the y-direction and then in the x-direction. To convolve a 2D matrix we need to use a version of the shift operator which takes two arguments which describe how much to shift by in each dimension. Shifting just in the x-direction is illustrated in the diagram below.

A function which shifts a 2D array just in the x-direction could be written as:

let rec convolveXDir (kernel : float32 []) i (a : FloatParallelArray)

= let e = kernel.[i] * ParallelArrays.Shift(a, [| -i; 0 |])

if i = 0 then

else

e + convolveXDir kernel (i-1) a

This function captures the shifting right along the rows nature of the x-direction convolution by specifying a shift of i elements along the rows for the i-th iteration (but it never shifts down columns hence the value of 0 in the second element of the array literal).

Shifting in the y-direction is illustrated in the diagram below.

A function which shifts a 2D array just in the y-direction could be written as:

let rec convolveYDir (kernel : float32 []) i (a : FloatParallelArray)

= let e = kernel.[i] * ParallelArrays.Shift(a, [| 0; -i |])

if i = 0 then

else

e + convolveYDir kernel (i-1) a

This function captures the shifting down along the columns of the y-direction convolution by specifying a shift of i elements along the columns for the i-th iteration (but it never shifts along rows hence the value of 0 in the first element of the array literal).

Rather than define two separate functions for convolving in the X and Y directions we can define just one function and pass a higher order function which allows us to abstract the direction of convolution.

// Declare a function to convolve in the X or Y direction

let rec convolve (shifts : int -> int []) (kernel : float32 []) i (a : FloatParallelArray)

= let e = kernel.[i] * ParallelArrays.Shift(a, shifts i)

if i = 0 then

else

e + convolve shifts kernel (i-1) a

// Declare a 2D convolver

let convolveXY kernel input

= // First convolve in the X direction and then in the Y direction

let convolveX = convolve (fun i -> [| -i; 0 |]) kernel (kernel.Length - 1) input

let convolveY = convolve (fun i -> [| 0; -i |]) kernel (kernel.Length - 1) convolveX

convolveY

Note that the convolution function takes a higher order parameter which specifies the shift direction. To convolve in the x-direction we provide a function which is given the degree to shift by i and return the (dx, dy) shift to be applied to the data parallel array i.e. (-i, 0). To shift in the y-direction we provide another function which is given the degree to shift by i and return the (dx, dy) shift to be applied to the data parallel array i.e. (0, -i). We use lambda expressions to defines these functions anonymously (in-line) as arguments to the convolve function.

To run the 2D F# convolver please follow these steps.

· Install Accelerator V2.

· Create a new F# console project and paste in the 2D convolver code at the start of this blog.

· If you are not running a 64-bit operating system please remove the code for using the x64 multi-core target i.e. delete the lines:

// Create a X64 multi-core target and use it to convolve the test input

use x64MCTarget = new X64MulticoreTarget()

let convolveMC = x64MCTarget.ToArray2D (convolveXY testKernel testArray)

printfn "MC: -> \r\n%A" convolveMC

· Add a reference to System.Drawing and the managed Microsoft.Accelerator.dll (under the appropriate directory for your target e.g. C:\Program Files (x86)\Microsoft\Accelerator v2\bin\Managed\Release\Microsoft.Accelerator.dll

· Build under Visual Studio.

· Make sure that you have the right Accelerator.dll in your path for your platform and target e.g. C:\Program Files (x86)\Microsoft\Accelerator v2\bin\x64\Release\Accelerator.dll or make sure to have a copy of this file in your build directory.

· Run the generated EXE from the build directory e.g. bin/Release

If you want to use Accelerator code from inside F# Interactive you will need to reference the Accelerator library e.g.:

#r @"C:\Program Files (x86)\Microsoft\Accelerator v2\bin\Managed\Release\Microsoft.Accelerator.dll";;

The Accelerator system encourages you to express data-parallel algorithms in terms of whole array operations which leads to efficient implementations for various back ends (targets). For example, the discipline of using only whole array operations allows me to make efficient address generator circuits for an experimental FPGA target that I am working on.

Accelerator is quite well suited for writing stencil-style data parallel programs. The expression orientated nature of Accelerator computations make them a nice fit for a functional language like F#. In effect the Accelerator system manifests itself as a domain specific language in F#, C# and C++ (as well as other .NET languages).

The F# code in this blog was written with the participation of Lubomir Litchev and James Margetson. Thank you Lubo and James! I aslo recommend this article on using Accelerator from F#: http://tomasp.net/blog/accelerator-intro.aspx.

The Accelerator system is still a research incubation project and the preview release is designed to solicit feedback. You can email msraccel@microsoft.com or use the Microsoft Connect Feedback Form. Thank you!

Satnam Singh

http://research.microsoft.com/~satnams