A straightforward data layout is used in these algorithms for all
platforms. The input image is an 
matrix of integers. We
assign tiles of the image as equally as possible among the processors.
If p is an even power of two, i.e. 
, for even d, the
processors will be arranged in a 
logical
grid. For future reference, we will denote the number of rows in this
logical grid as v and the number of columns as w. For odd d, we
assign the number of rows of the logical processor grid to be 
, and the number of columns
to be 
. Each processor
initially owns a tile of size 
. For
future reference, we assign 
and 
.
We assume that the p processors are labeled consecutively from 0
to p-1 and are assigned in row-major order to the logical processor
grid just described.
Several test images have been used to test the correctness and the
performance of the algorithms presented here. These test images, shown
in Figure 1, are generated at runtime, with
images 1-4, 7, and 9, augmented to the needed image size, while
images 5, 6, and 8, scaled appropriately. Figure 2 is
a 
, 256 grey-level, image from the Second DARPA Image
Understanding Benchmark [47]. The histogramming algorithm
is assumed to be correct because 
, and
for regular patterns, it is easy to verify that each 
equals the percentage of area that grey level i covers in the image.
Verifying the connected components algorithm is more difficult. In
addition to the DARPA Benchmark Image, we include the most widely used
patterns for binary images. A catalog of nine automatically generated
scalable images is used, as shown in Figure 1, and
include horizontal, vertical, and forward- and back-slanting diagonal
bars, a cross, a filled disc, concentric circles with thickness, four
squares inset from the four corners, and a dual-spiral pattern, a
``difficult'' image [42].