9 months ago

An introduction to parallel programming

Put all four cores in your Raspberry Pi to work by running tasks in parallel

We are used to the idea that the Raspberry Pi has revolutionised education and the maker community, but since the launch of the Pi 2 it has joined one of the biggest revolutions in the history of computing: the change from single‑processor to multi-processor computers. This is fundamentally changing the way we think about writing programs. The Pi 2 and Pi 3 both contain quad‑core processors, which means that they can run four tasks simultaneously. In principle, this gives us four times the original speed, but in practice it can be difficult to make use of this extra power. In this article, we introduce one of the simplest approaches to parallel programming that will enable you to make use of all the processing power on your Pi.

The full article can be found in The MagPi 52 and was written by James Hobro.

Three-core breakfast

Before we write any programs, let’s look at something that most of us do every day: make breakfast. If we try to describe this in what might seem the obvious way – a list of instructions – it might look something like the list in Fig 1.

Figure 1 - Breakfast List

Figure 1 – Breakfast List

The breakfast list is a sequential program. It contains all the instructions necessary to make breakfast, but something important is missing. In reality, we would never perform these tasks in sequence – we would do some of them in parallel. After all, it’s possible to boil the kettle and toast a slice of bread at the same time. But not all the tasks can be performed simultaneously – you can’t make the tea until the kettle has boiled. How can we describe this? One way to do it is with a task dependency graph. Each task in the graph can only start once all the others it depends on have been completed. The breakfast task dependency graph (Fig 2) is a much more useful description than the sequential program; it’s no coincidence that it describes more closely what we actually do when making breakfast, starting with all the tasks at the top of the graph and working our way down. As each of the initial tasks is completed, we can move on to the ones lower down that depend on it: once the kettle has boiled, we make the tea. Of course, not all programs that we’d like to run in parallel can be broken down in this way, but a task dependency graph offers a simple and powerful way to solve many problems in parallel.

Figure 2 - Breakfast task dependency graph

Figure 2 – Breakfast task dependency graph

Meet your maker

So how can we apply this to the Raspberry Pi 2 or 3? Raspbian contains a utility called Make, which follows a task dependency graph, executing tasks in the appropriate order and, where possible, running them in parallel using all four of the cores on your Pi. Make was designed to build programs in languages like C or C++ that require source code to be compiled to binary object files, executable programs, and libraries. However, it can be used to solve any problem that can be expressed as a set of tasks with dependencies. To use Make, we need to write a ‘makefile’ which describes how each task depends on the others. As an example, we will generate a collage of thumbnail images from a set of original image files. This is often required when dealing with large numbers of image files, for example when managing photos on a server. As well as running Make, we’re going to use ImageMagick for the image conversion, so ensure that both packages are installed on your Pi by running:

We’re going to use Make first to create a thumbnail image for each of the originals, then finally combine them all in the collage. The majority of the work is in the generation of the thumbnails. The dependency graph (Fig 3) shows the relationship between each original image, its thumbnail, and the final collage. Since each thumbnail can be generated independently, we can put all four of our cores to work generating thumbnails, then finally create the collage once they’re all ready.

Figure 3 - Collage dependency graph

Figure 3 – Collage dependency graph

Makefile rules

The makefile is all we need to describe our tasks and their dependencies. First, it defines the lists of original image files and thumbnails that we’re going to work with. Then we define the two dependency rules in the graph. The first rule describes how to generate a thumbnail from a full-size image. It says that any file in the fullsize directory should be converted to a thumbnail with the same name in the thumbs directory, using the convert command. Note that the lines containing commands in a makefile must begin with a tab character (not spaces), shown in the listing as a long underscore. Our second rule specifies that the final collage depends on all the thumbnail images. It uses the montage command to create the collage and then displays it. Notice that we’ve told Make which commands will be used to rescale and combine the images, but we’ve not specified an execution order. Make will work this out for itself. We have moved away from writing a sequential program to describing a set of tasks and their dependencies, allowing the system to work out how to solve them most efficiently.

The simplest way to run our program is to type:

This will launch Make, which will read the rules we have specified in the makefile and get to work launching the tasks required in the correct order. However, by default Make assumes that only one core is available, so it will run each task sequentially. Luckily, we can easily tell it to use multiple cores:

This command specifies that Make should execute up to four jobs simultaneously, and your thumbnails and collage will be generated up to four times faster than on a single core. Now try adding some new pictures to the fullsize directory or updating some of the existing pictures and rerun Make. It will now do only the work necessary to update your collage. Because Make understands the dependency graph and can see the date stamps on all the files in the graph, it can work out exactly which tasks are required and will not redo any work unnecessarily. This also means that you can stop it in the middle of a job and it will pick up the unfinished tasks correctly the next time you run it. Typing:

…will clean up by deleting the generated thumbnails and collage.

Code listing

Makefile