An implementation of MapReduce for FPGAs for use with Reconfigure.io. You specify your mapper and reducer and use our framework to produce FPGA code that provides parallel processing.
Our MapReduce framework is provided as a way of scaling up simple functions, and as a template for other parallel patterns.
For more background info, see our blog post.
$ go get github.com/ReconfigureIO/reco-map-reduce/cmd/generate-framework $ go get golang.org/x/tools/cmd/bundle
- Create an
input.gofile to define your mapper and reducer, as well as the necessary types.
- Create a
reco.ymlfile and specify the mapper and reducer's information (example)
generate-framework -output mapreduce.goto create the
Topfunction of your FPGA code.
bundle -prefix " " -o main.go .to bundle both your
input.go, and the generated
Topfunction into a single
- Use the
recotool as normal to simulate, build and deploy your program.
MapReduce is a framework for processing problems with the potential for parallelism across large datasets using a number of nodes. This usually means multiple computers in a network cluster or spread out geographically in a grid, but in the context of Reconfigure.io, our nodes are individual elements of circuitry on the same FPGA. Put simply, you write the functions required to process the data on one node and MapReduce farms this out to multiple nodes.
Reconfigure.io MapReduce projects have this initial structure:
cmd │ └── test │ └── main.go ├── input.go └── reco.yml
input.go contains all the user-definable functions that will be used in the generated FPGA code.
Mappers are used to farm out data to multiple workers. You choose how many instances of the your mapper function to create, and a routing mechanism is automatically set up to fetch and send data elements to available mappers.
Each reducer takes two inputs from a previous mapper or reducer stage, and generates one output. You choose how many reducer phases there should be and a tree of reducers is automatically created.
reco.yml contains all the settings required to generate the MapReduce framework for a project. The basic structure looks like this:
mapper: type: typeWidth: deserialize: function: replicate: reducer: type: typeWidth: serialize: function: depth: empty:
typeWidthjust set the type and width of the data we'll be dealing with.
emptyare set to refer to functions that are defined within
serializeare used to pipe data elements into and out of the fabric of the FPGA.
functiondefines what each mapper does with its sample data element.
functiondefines how each reducer processes it's two inputs to create a single output.
replicateis the number of mapper instances you want to create.
depthis the number of reducer stages to include (max=log(mappers)).
emptyis a function defined to generate a suitable initial value for the project, this will be used to feed empty inputs to reducers.
There are a number of constraints around the kind of example for which MapReduce is a good fit:
- Mappers need to work in a single input element and produce a single output element.
- Reducers need to combine two output elements into a single output element, in a way that is associative (e.g.
max(max(a,b), c) == max(a, max(b, c)))
- The Reducer also needs an initial value - for this familiar with abstract algebra is called a ‘monoid’.
Pull requests & issues are enthusiastically accepted!
By participating in this project you agree to follow our Code of Conduct.