Geoscience Reference
In-Depth Information
collate the results at the end of the runs. This kind of problem can almost always produce near linear
speed-ups without much work on the part of the programmer. Harder forms of parallelism are where
there is insufficient room in the memory of each processor to store the problem or where the model
is only to be run once or a few times. Examples of this are often found in physical geography, such
as climate models which cover the whole of the Earth, or in human geography with large spatial
interaction models where the cost matrix and the trip matrix must be stored. In this case, it becomes
necessary to divide the problem up between different processors. This nearly always involves the
program in communicating between the processors which takes up time when the processor could
be performing real work. In problems of this type, it is quite possible to achieve speed-ups of sig-
nificantly less than N . If the number of processors becomes too large compared to the size of the
program task, then communication will completely swamp the problem runtime. For instance, in
the example of the brick wall mentioned earlier, if a team of 1000 bricklayers was put to work, then
it would be very unlikely that any bricks would have been laid at the end of the first day since the
foreman would still be trying to sort out the teams.
How to divide up a problem is also an important part of the parallelisation task. In a simple
model, it may be possible to simply divide the problem up evenly between the processors. This is
often the approach carried out in computational physics and chemistry where problem shapes are
often rectangular and evenly spaced. Unfortunately, in geography, this is rarely the case. The spa-
tial interaction problem can be divided up in this way since journeys to work are usually local and
it is possible to split the rows of the matrix in such a way as to spread out the major conurbations.
However, if you wished to carry out a pattern recognition task on a population raster map of Great
Britain, then one approach might be to divide the map up into as many rectangles as there are pro-
cessors and assign one rectangle to each processor (Figure 3.1a). However, the processor that was
allocated to the top right-hand rectangle would finish almost immediately since it contains mostly
sea, whereas the one that was allocated the bottom-right rectangle would take a long time since
it had the whole of London to deal with. In this case, it would be better to divide the map up into
smaller regions (Figure 3.1b) and to allocate several regions to each processor or to hand out the next
region to each processor as it finished. Care has to be taken not to divide the problem into regions
too small for the processors to work on efficiently or more time will be spent allocating areas than
will be spent working on them.
(a)
(b)
FIGURE 3.1 Two possible ways [(a) and (b)] of dividing up a raster population map of the United Kingdom.
(From OS Boundary-Line Great Britain [Shapefile geospatial data], Coverage: Great Britain, Ordnance
Survey, GB. Using: EDINA Digimap Ordnance Survey Service, http://edina.ac.uk/digimap, Downloaded:
October 2013.)
Search WWH ::




Custom Search