Scalable Parallel Implementations of List Ranking on Fine-Grained Machines.
AbstractWe present analytical and experimental results for fine-grained list ranking algorithms. We compare the scalability of two representative algorithms on random lists, then address the question of how the locality properties of image edge lists can be used to improve the performance of this highly data-dependent operation. Starting with Wyllie's algorithm and Anderson and Miller's randomized algorithm as bases, we use the spatial locality of edge links to derive scalable algorithms designed to exploit the characteristics of image edges. Tested on actual and synthetic edge data, this approach achieves significant speedup on the MasPar MP-1 and MP-2, compared to the standard list ranking algorithms. The modified algorithms exhibit good scalability and are robust across a wide variety of image types. We also show that load balancing on fine grained machines performs well only for large problem to machine size ratios.
Introduction
List ranking is a fundamental operation in many algorithms for graph theory and computer vision
problems. Moreover, it is representative of a large class of fine grained data dependent algorithms.
Given a linked list of n cells, list ranking determines the distance of each cell from the head of
the list. On a sequential machine, this problem can be solved in O(n) time by simply traversing
the list once. However, it is much more difficult to perform list ranking on parallel machines
due to its irregular and data dependent communication patterns. The problem of list ranking of
random lists has been studied extensively on PRAM models and several clever techniques have
been developed to implement these algorithms on existing parallel machines [2, 3, 10, 11]. In this
paper, we study the scalability of these techniques on fine-grained machines. We then present
efficient algorithms to perform list ranking on edge pixels in images. Performance results based
on implementations on MasPar machines are discussed.
Most of the algorithms proposed in the literature are either simple but not work-efficient [2,
10, 11] or are work-efficient but employ complex data structures and have large constant factors
associated with them [1, 3, 11, 12]. In order to study the performance and scalability of these
algorithms in an actual application scenario and on existing parallel machines, we have chosen
two representative algorithms, Wyllie's algorithm and Anderson & Miller's randomized algorithm
[11]. We assume that list ranking is an intermediate step in a parallel task. Therefore, in the
general case, a linked list is likely to spread over the entire machine in a random fashion. We then
study the performance of these algorithms in applications such as computer vision and image
processing where locality of linked lists is present due to the neighborhood connectivity of edge
pixels. For this purpose, we present a modified approach that takes advantage of the locality and
connectivity properties. A similar technique has been described in [10] for arbitrary linked lists.
In Reid-Miller's work, the assignment of list cells to processors is determined by the algorithm,
whereas, for the arbitrary case, we assume pre-assigned random cell distribution. Our approach
was derived independently and was motivated by the contrast between the random list case and
the characteristics of edges in images.
We show that in the case of random lists where cells are randomly pre-assigned to processors,
the Randomized Algorithm runs faster than Wyllie's Algorithm on MasPar machines when lists
are relatively long. However, Wyllie's Algorithm performs better for short lists. This agrees
with the results reported on other machines [2, 10]. This also implies that in order to achieve
scalability, a poly-algorithmic approach is needed That is, for long lists use the Randomized
Algorithm and when the sizes of lists are reduced to a certain length, use Wyllie's Algorithm.
This approach has also been used to design theoretically processor-time optimal solutions. We
show, however, that for list ranking of edge pixels of images on fine-grained SIMD machines,
the standard Wyllie's Algorithm and Randomized Algorithm do not take good advantage of
the image edge characteristics. A modified technique described in Section 4 runs about two
to ten times faster (depending on the image size) than the standard Wyllie's and Randomized
algorithms on a 16K processor MasPar MP-1. Moreover, whereas the standard algorithms do
not scale well on image edge lists, the modified algorithms exhibit good scalability with respect
to increases in both image size and number of processors. We study the performance of the
proposed algorithms on images with varying edge characteristics.
In the remainder of Section 1, we briefly describe the architecture of the MasPar machines,
and outline the notion of scalability used in our work. Section 2 presents an overview of parallel
algorithms for list ranking. The performance results of standard Wyllie's and Randomized algorithms
are discussed in Section 3 and their scalability behavior is analyzed. Efficient parallel
algorithms for performing list ranking on image edge lists are presented in Section 4. Section 5
contains implementation results and discusses scalability of the modified parallel list ranking
algorithms on image edge lists.
1.1 Fine-grained SIMD Machines
The parallel algorithms described in this paper are implemented on MasPar MP-1 and MP-2
fine-grained SIMD machines. Fine-grained machines, in general, are characterized by a large
number of processors with a fairly simple Arithmetic Logic Unit (ALU) in each processor. The
MasPar machines are massively parallel SIMD machines. A MasPar MP-series system consists of
a high performance Unix Workstation as a Front End and a Data Parallel Unit (DPU) consisting
of 1K to 16K processing elements (PEs), each with 16 Kbytes to 1-Mbyte of memory. All PEs
execute the instructions broadcast by an Array Control Unit (ACU) in lock step. PEs have
indirect addressing capability and can be selectively disabled. The clock rate for both MP-1 and
MP-2 machines is 12.5 MHz. Processors in the MP-2 employ a 32-bit ALU compared with a
4-bit ALU in MP-1 processors.
Each PE is connected to its eight neighbors via the Xnet for local communication. Besides
the Xnet, these machines have a global router network that provides direct point-to-point global
communication. The router is implemented by a three-stage circuit switched network. It provides
point-to-point communication between any two PEs with constant latency, regardless of the
distance between them. A third network, called the global or-tree, is used to move data from
individual processors to the ACU. This network can be used to perform global operations such
as global maximum, prefix sum, global OR, etc. across the data in the entire array.
For our experiments, we have used the MasPar MP-1 and MP-2 as being representative of fine-grained
machines. The use of the router network, which provides point-to-point communication
between any two processors with constant latency, ensures that our performance results are
independent of any specific network topology. Also, we have run our experiments on both
the MP-1 and MP-2 to show the effects of processing power of individual processors on the
performance of the algorithms. We have used an extended version of sequential ANSI C, the
MasPar Programming Language (MPL), to keep our implementations free of machine-dependent
software features.
1.2 Scalability of Parallel Algorithms
We analyze the scalability of our algorithms and implementations using several architecture
and algorithm parameters. We study the performance by varying machine and problem size,
by varying the characteristics of the input image, and by varying the processor speed. Several
notions of scalability exist [5]. In our analyses we define scalability as follows: Consider an
algorithm that runs in T (n; p) time on a p processor architecture and the input problem size
is n. The algorithm is considered scalable on the architecture if T (n; p) increases linearly with
an increase in the problem size, or decreases linearly with an increasing number of processors
(machine size) [7, 8]. In our experiments, we use this definition intutively to study the scalability
of the algorithms and implememntations.
It is likely that no single algorithm is scalable over the entire range of machine and problem
sizes. One of the important factors limiting the range of scalability is the sequential component
of the parallel algorithm. We identify the regions of scalability for different algorithms presented
in this paper and compare the analytical results with the experimental data.
Parallel Algorithms for List Ranking
In our implementations, we use Wyllie's parallel algorithm and Anderson & Miller's randomized
algorithm for list ranking [11]. In this section, we outline these algorithms for the general case of
random lists. Compared with other parallel algorithms for list ranking in the literature [11, 3, 12],
we have chosen these algorithms because of their simplicity, ease of implementation, and small
constant factors. In particular, the deterministic algorithms based on ruling sets and graph
coloring [3] are not easily amenable to implementation on existing parallel machines.
2.1 Wyllie's Pointer Jumping Algorithm
be a linked list of n cells such that
then c i
is the head of the list. The first element in the list which has no predecessor is referred
to as the tail of the list. The list ranking problem deals with finding the rank of each cell i with
respect to the head of the list.
Wyllie's Algorithm uses pointer jumping or dereferencing to find the rank of a cell. In pointer
jumping, the successor of a cell c i
is modified to be its successor's successor. That is, given
, one iteration of pointer jumping reassigns the successor of c i
to be c i+2
. Each
cell c i maintains a value rank[i] which is the distance of the cell c i from its current successor
succ[i]. Intuitively, after each round a linked list is divided into two linked lists of half the length
(see Fig. 1 a).
After log(n) iterations, all the cells point to nil and rank[i] contains the exact rank of cell
c i . On p processors, each processor is assigned n=p cells at random. Although this algorithm
is simple and has a running time of O( n log n
on a p-processor machine, it is not work-efficient
compared with the serial algorithm, which takes O(n) time. In the next section we describe a
work-efficient randomized algorithm.
2.2 Anderson and Miller's Randomized Algorithm
Anderson & Miller's Randomized algorithm is a modified version of the work-efficient algorithm
devised by Miller & Reif [9]. Assume that each processor holds n=p cells as a queue. The
algorithm consists of two phases.
In the first phase, called the pointer jumping phase, each processor "splices" out the cell at the
top of its queue with a condition that two consecutive cells of the list assigned to two different
processors are not spliced out simultaneously. In order to decide which cells to splice out, each
processor tosses a coin and assigns H or T to the cell at the top of its queue. Furthermore, all
the cells not at the top of the queue are assigned T. A processor splices out the cell at the top
of its queue only if that cell is marked H and its predecessor is assigned T (see Fig. 1 b). The
first phase ends when all of the cells in each processor are spliced out. The splicing out of cell c i
consists of two atomic assignments followed by updating of rank[i] as follows:
In the second phase, referred to as the reconstruction phase, the cells are put back into the
a b c d
a b c d
a b c d
(a) (b)

Figure

1: (a) Pointer jumping in Wyllie's algorithms. Edge labels show the rank of the edge's
predecessor cell in the current iteration; (b) Splicing condition in Anderson & Miller's algorithm.
's top cell will be spliced out.
queue in reverse of the order in which they were spliced out. In reconstructing the queue, the
rank of each cell c i
with respect to the head of the list is updated:
The expected running time of this algorithm is O(n=p), assuming n=p - log n. Additional
details of the algorithm and the analysis can be found in [11]. In the rest of this paper, we refer
to this algorithm as the Randomized Algorithm.
3 Implementation Results using Random Lists
The algorithms presented in the previous section have been implemented on the MasPar ma-
chines. In this section, we study the impact of various machine and problem parameters on the
performance of these algorithms on random lists. To generate a random linked list of size n, we
traverse an array of n cells in serial order, and for each cell we assign a pointer to a random
location in the array. It is ensured that a cell in the array is pointed to by no more than one other
cell. For the input to the Randomized Algorithm, we also assign reverse pointers in the target
location to generate a doubly linked list, as required by the algorithm. The resulting random
linked list is then read into the parallel processor array so that every processor holds n=p cells
of the array. Since the n=p cells in the processor may point to any of the n array locations, the
sublist in each processor does not generally contain successive cells in the linked list.
3.1 Scalability Analysis
Fig. 2 shows the performance of the Wyllie's and Randomized algorithms on a MasPar MP-1
using various machine and problem sizes. The experimental results presented in Fig. 2 (a) and (b)
are consistent with the theoretical analysis. The asymptotic complexity of Wyllie's Algorithm for
a random list of size n on p processors is O((n=p) log n), while the complexity of the Randomized
Algorithm is O(n=p). However, the Randomized Algorithm has larger constant factors due to
the increased overhead of coin-tossing and the record keeping involved in the reconstruction
stage of the algorithm. Wyllie's Algorithm is more suited for smaller linked lists due to its small
constant factors. The Randomized Algorithm outperforms Wyllie's Algorithm as the problem
size increases. This is because of the probabilistic splicing of the elements which generates lower
congestion in the communication network. For the example shown in Fig. 2 (a), the crossover
point occurs for a random list of size 94K elements on a 16K processor MP-1.
Random List Size (n)
Time
MP-1: 16,384 Processors
___ Wyllie
_._ Randomized
Number of Processors (p)
Time
Random List
___ Wyllie
_._ Randomized
(a) (b)

Figure

2: (a) Performance of Wyllie's and Randomized algorithms on the MP-1 for a random
list of varying size; and (b) performance of the algorithms on a random list of size 16K, varying
the number of processors of the MP-1
An interesting feature of Fig. 2 (b) is that the execution time of the Randomized Algorithm
starts increasing when the number of processors exceeds 4K for a random list of size 16K. This is
because, for a fixed problem size, as the number of processors increases beyond a certain point,
the size of the queue (n=p) in each processor becomes very small. Hence it is likely that the cell
at the top of the queue in a processor is pointed to by a cell at the top of the queue in another
processor, thus reducing the chance that the cell is spliced out in a particular iteration. This
increases the total number of iterations and thus increases the execution time of the algorithm.
By varying the problem size and machine size, we are able to determine the regions of problem
and machine size for which each algorithm is fastest. These experiments also demonstrate that
scalability is best achieved by changing the algorithm approach as the problem size increases.
This, in fact, agrees with the approaches used by algorithm designers to develop processor-time
optimal solutions for the list ranking problem [11].
We performed the experiments on the MasPar MP-2 as well. The MP-1 and MP-2 use the
same router communication network. The only difference between the architectures is the faster
processors on the MP-2. Thus, to study the impact of processor speed, we compare the performance
of the algorithms on 4096 processors of the MP-1 and MP-2. In both cases, for problem
sizes greater than 16K, the Randomized Algorithm outperforms Wyllie's Algorithm. However,
Wyllie's Algorithm is 35% faster and the Randomized Algorithm is 40% faster on the MP-2.
In computer vision, list ranking is an intermediate step in various edge-based matching and
represent them in a compact data structure for efficient processing in subsequent steps [2]. We
assume input in the form of binary images with each pixel marked as an edge or non-edge pixel.
Furthermore, as a result of an operation such as edge linking, each edge pixel points to the
successor edge pixel in its 8-connected neighborhood, where the successor function defines the
direction of the edge. An n \Theta n image is divided into p subimages of size n
\Theta n
, and each
processor is assigned one subimage. This straightforward division and distribution of edge pixels
to processors might cause load imbalance. Section 5.5 describes the effect of load imbalance,
and presents an alternative data-distribution scheme that improves the load balance across the
processors.
4.1 Image Edge Lists
Fig. 5 shows edge maps derived from various real and synthetic images. In particular, Fig. 5
(a) is an image of a picnic scene, and Fig. 5 (b) is the edge map obtained by performing edge
detection on the picnic image. This is followed by an edge linking operation that creates linked
lists of contiguous edge pixels. The image edge lists used in our experiments were derived by
performing sequential edge linking [4] operations on the edge maps of various images.
The edge lists resulting from images typically have several properties that may affect the
efficiency of the standard list ranking algorithms. For example, on the average, the number of
lists is fairly large, the lists are short in length, and these edge lists exhibit spatial continuity.
This implies that list cells assigned to a single processor are contiguous and they form sublists.
Furthermore, one processor may contain pieces of several edge lists. On one hand, these properties
can adversely affect the performance of the standard list ranking algorithms. For example, if we
run Wyllie's Algorithm disregarding the connectivity property, several edge points belonging to
the same sublist in a processor may compete for the communication links to access the successor
information from other processors. Similarly, in the Randomized Algorithm, a processor may be
tossing the coin for an edge point while its successor is already stored in the same processor. These
overheads make the standard Wyllie's or Randomized algorithms unattractive for computing
ranks for edge pixels in images. On the other hand, some of the image edge properties can be
used to modify the standard algorithms to achieve better performance on edge lists in images,
as described in the next section.
4.2 Modified Algorithms
Fig. 3 compares the performance of the Wyllie's and Randomized algorithms on random lists
versus their performance on edge maps of equivalent sizes obtained from the picnic image. This
is achieved by counting the number of edge pixels in the picnic image, and creating a random
list with the same number of elements. From Fig. 3, it is clear that the locality properties of the
image edge lists cause performance degradation, especially for large image sizes.
- Wyllie's on Picnic Image
___ Wyllie's on Random List
Image Size
Execution
Time
Wyllie's Algorithm
- Randomized on Picnic Image
___ Randomized on Random List
Image size
Execution
Time
Randomized Algorithm
(a) (b)

Figure

3: Comparison of the performance of the algorithms on random lists versus equivalent
sizes of the picnic image on a 16K processor MP-1.
In the following, we outline a modified approach that takes advantage of the connectivity
property inside a processor by reducing each sublist to a single edge, called a by-pass edge. The
approach then uses the Wyllie's or Randomized algorithm over the by-pass edges in the image.
In addition to eliminating redundant work within the processors, this approach also reduces the
amount of communication across processors. The approach consists of three steps:
Step 1. Convert each sublist of contiguous edge pixels in a subimage into a by-pass edge by
performing a serial list ranking operation on all sublists within a processor (for example,
see Fig. 4). Associate with each such edge the length of the sublist it is representing. For
lists that span processors, their corresponding by-pass edges are connected.
By-pass edge
Image contour
Processor i

Figure

4: By-pass edges.
Step 2. Run Wyllie's Algorithm or the Randomized Algorithm on the lists of by-pass edges.
Step 3. Serially update the rank of each edge pixel within a subimage using the final rank of
the by-pass edge that represents the pixel.
The modified algorithms can thus be thought of as a combination of serial and parallel list
ranking algorithms.
To analyze the scalability of the list ranking algorithms on image edge lists, we assume that
the image has n edge pixels uniformly distributed across p processors such that each processor
holds O(n=p) edge pixels. This simplifying assumption is unlikely to be strictly true for actual
images. However, since the number of edge pixels per processor is relatively low in fine-grained
implementations, the extent to which the number of edge pixels per processor deviates from
O(n=p) will be limited.
In the modified approach, the first step takes O(n=p) computation time to form the by-pass
edges. The last step takes O(n=p) time to update the rank of each edge pixel. Thus the total
time taken by the serial component of the modified algorithms is O(n=p).
To analyze the parallel execution time of the second step, we assume that the image has
multiple edge lists of varying lengths, and the length of the longest edge is l. Note that l is
a property of the underlying image from which the edge map was derived. Since the edges are
assumed to be uniformly distributed across the processors, the length of the longest list consisting
of by-pass edges is O(l=p). We further assume that the n=p pixels in each processor can be divided
into k sets such that each set contains successive pixels of an edge list assigned to the processor
(i.e. each processor contains k by-pass edges after the first step of the algorithm). Again, this
is a simplifying assumption. Under these assumptions, the execution time of the second step is
log l) for Wyllie's Algorithm, and O(k) expected time for the Randomized
Algorithm (assuming k - log(kp)). This is the time taken by the parallel component of the
modified algorithms.
Therefore, the total execution time is O(n=p+k log l) for the Modified Wyllie's Algorithm, and
O(n=p+ for the Modified Randomized Algorithm. Since the constant factors for the Modified
Randomized Algorithm are higher, it will outperform the Modified Wyllie's Algorithm only if l
is large (i.e. the image has very long edges).
The algorithms presented in this section are inherently fine-grained due to the high commu-
nication/computation ratio and irregular patterns of interprocessor communication. Efficient
algorithms for coarse-grained machines and their implementation are described in [6].
5 Implementation Results Using Image Edge Lists
We have used the edge maps from a number of real and synthetic images to study the performance
of list ranking algorithms. Fig. 5 shows the edgemaps used in our experiments. Fig. 5 (b), (c),
and (d) are derived by performing edge detection and edge linking operations on gray-scale
images. The edge characteristics of these images differ significantly. For example, the edges of
the written text image are more local compared to the other images. Typically, the edge density
(percent of edge pixels compared to the total number of pixels) of these real images is in the
range of 3 to 8 percent. As a contrast to these edge maps, we have also generated synthetic
edge maps of varying edge density and length. Fig. 5 (e) and (f) show synthetically generated
edge maps of straight lines and a spiral, respectively. We have generated these images with edge
densities ranging from 5 to 50 percent. The edge characteristics of the real and synthetic images
help in gaining insight into the performance of the algorithms on images of varying edge density
and edge length.
5.1 Comparison with Standard Algorithms
The performance of the modified algorithms is compared to the performance of the standard
algorithms in Fig. 6. Fig. 6 (a) shows the execution times for varying sizes of the picnic image on
a 16K processor MP-1. The modified algorithms are significantly faster than the straightforward
Wyllie's or Randomized algorithms. This is because these algorithms efficiently exploit the
locality of edges in images. We have verified the results on different machine sizes of the MP-1
and MP-2.
Fig. 6 (b) shows execution times of the algorithms for the dense synthetic spiral edge maps.
The spiral edge map is very different from the picnic edge map because it has much higher edge
density, and much longer image edges. Despite these vastly different image characteristics, the
modified algorithms are significantly faster than the standard algorithms. We have also tested
the algorithms on the different edge maps shown in Fig. 5 with similar results. Thus we conclude
that our modifications result in significant performance improvement over the standard Wyllie's
and Randomized algorithms for image edge lists. We point out that in Fig. 6, the relative
performance of the modified algorithms varies depending on the image characteristics. For the
spiral image, the Modified Randomized Algorithm is faster than Modified Wyllie's for images
of size greater than 350 \Theta 350 pixels. On the other hand, for the picnic image, the Modified
Randomized Algorithm is always slower than Modified Wyllie's. We explain this behavior in
detail in Section 5.3.
5.2 Scalability Analysis
The scalability of the modified algorithms has been studied using different images, and varying
the image size and number of processors. Results obtained using different edge maps shown in
Fig. 5 are similar. Hence we restrict our discussion to the performance of the modified algorithms
(a) (b)
(c) (d)

Figure

5: Picnic image and detected edge contours of different images used in our experiments:
(a) real picnic scene, (b) edgemap of the picnic scene (c) edgemap of written text, (d) edgemap
of street scene, (e) synthetic edgemap with straight lines, and (f) synthetic edgemap of a spiral.
. Randomized
_. Modified Randomized
___ Modified Wyllie
Image Size
Execution
Time
Picnic Image
6 . Randomized
_. Modified Randomized
___ Modified Wyllie
Image Size
Execution
Time
Dense Spiral Image
(a) (b)

Figure

Performance of the algorithms for various sizes of (a) the picnic image, and (b) the
spiral image; on 16,384 processors of the MP-1.
on the edge map derived from the picnic scene.
Fig. 7 examines the scalability of the Modified Wyllie and Modified Randomized algorithms
with respect to increasing problem size. The plot displays the overall execution time, as well as
the serial and parallel components of the modified algorithms. For small image sizes, the parallel
component dominates the overall execution time. This is because of the relatively large constant
factors of the parallel component compared to the sequential component. For large image sizes,
as the subimage size per processor grows, the execution time of the sequential component grows
much faster than the corresponding parallel component. This is consistent with the analytical
results since the execution time for the sequential list ranking component grows linearly with the
size of the subimage (O(n=p)), while the parallel component grows in proportion to the number of
by-pass edges in a subimage. In the case of the Modified Wyllie's Algorithm, the crossover point
between the execution times of sequential and parallel components occurs when the subimage
size assigned to each processor is 64 pixels. In the case of the Modified Randomized Algorithm,
the crossover point occurs when the subimage size is 128 pixels (see Fig. 8 (b)).
Fig. 8 shows the scalability behavior of the modified algorithms with respect to changes in the
machine size. We notice that the sequential component dominates the execution time for a high
problem/machine size ratio, and the parallel component dominates for a low problem/machine
size ratio. The results shown are for the MP-1. For the MP-2, the performance curves have
. Sequential
Parallel
___ Total
Image Size
Execution
Time
Modified Wyllie's
Parallel
___ Total
Image Size
Execution
Time
Modified Randomized
(a) (b)

Figure

7: Performance of the sequential and parallel components of (a) the Modified Wyllie, and
(b) Modified Randomized algorithms. (Execution time for the picnic image on the 16K processor
MP-1.)
similar shape. However, for the MP-2 the crossover point at which the parallel component
begins to dominate the execution time occurs for a larger problem/machine size ratio due to the
faster processors (higher computation/communication ratio) than the MP-1.
. Sequential
Parallel
___ Total
Number of Processors
Execution
Time
Modified Wyllie's
. Sequential
Parallel
___ Total
Number of Processors
Execution
Time
Modified Randomized
(a) (b)

Figure

8: Scalability with respect to number of processors for (a) the Modified Wyllie's Algo-
rithm, and (b) the Modified Randomized Algorithm. (Execution time for the picnic image of
size 512 \Theta 512 on the MP-1.)
Fig. 9 plots the performance of the modified algorithms when the number of processors increases
linearly with the image size. Thus the problem-size/machine-size ratio is constant, and
the size of the subimage in a processor is constant. We observe that the sequential time, which is
proportional to the size of the subimage in a processor, remains approximately the same, while
there is a small increase in the parallel component. This is due to the fact that in MasPar ma-0.10.2
_. Sequential
Parallel
___ Total
Image Size
Execution
Time
Modified Wyllie's
Parallel
___ Total
Image Size
Execution
Time
Modified Randomized
(a) (b)

Figure

9: Scalability for constant problem-size/machine-size ratio (256 elements per processor)
on the MP-1: (a) the Modified Wyllie's Algorithm, and (b) the Modified Randomized Algorithm.
chines, with the increase in number of processors, the number of links in the router network does
not change proportionally. However, since the overall increase in the execution time is small,
we conclude that the modified algorithms exhibit speedup proportional to the image size, if the
ratio of image-size to number of processors is constant.
5.3 Effect of Image Characteristics
We have studied the performance of our algorithms on images with varying characteristics in
terms of edge density and edge lengths. As discussed in Section 4.2, the total execution time is
O(n=p+k log l) for the Modified Wyllie's Algorithm, and O(n=p+k) for the Modified Randomized
Algorithm. Fig. 10 indicates that increase in execution time is proportional to the increase in image
edge density (O(n=p)), and this is true for both Modified Wyllie's and Modified Randomized
algorithms.
Fig. 11 shows the behavior of modified algorithms on edge maps with varying edge lengths.
In Fig. 11 (a), the Modified Randomized Algorithm is always slower than the Modified Wyllie's
Algorithm. This is also the case for the picnic scene image (see Fig. 6 (a)). This is due to the
large constant factors for the Modified Randomized Algorithm.
However, in Fig. 11 (b), the Modified Randomized Algorithm is significantly faster than the
Modified Wyllie's Algorithm beyond a certain image-size to machine-size ratio. This is because
. image
___ image
Image size
Execution
time
Modified Wyllie's
. image
___ image
Image size
Execution
time
Modified Randomized
(a) (b)

Figure

10: Performance on the synthetic line image of varying density on a 16K processor MP-1:
(a) the Modified Wyllie's Algorithm, and (b) the Modified Randomized Algorithm.
Modified Wyllie's
___ Modified Randomized
Image size
Execution
time
Line Image
Modified Wyllie's
___ Modified Randomized
Image size
Execution
time
Spiral Image
(a) (b)

Figure

11: Performance of the modified algorithms on synthetic images with the same density
but different edge lengths on a 16K processor MP-1: (a) line image, and (b) spiral image.
the parallel execution time of the Modified Randomized Algorithm is O(k), compared to O(k log l)
for the Modified Wyllie's Algorithm. Since the serial component for an equal-density line image
and spiral image is the same (O(n=p)), we expect the Modified Randomized Algorithm to run
faster when the length of the longest edge (l) is large as in the case of the spiral image.
5.4 MP-1 vs MP-2
The effect of the processor speed on the performance of the algorithms is studied by executing
the algorithms on 4K processor MasPar MP-1 and MP-2 machines. As shown in Fig. 12, Wyllie's
algorithm is faster on the MP-2 compared with MP-1. It is primarily due to increased processor
speed. Similar behavior is exhibited by the Randomized algorithm. It is worth noting that
although the MP-2 has lower execution times, the scalability behavior of the algorithms on the
two machines is very similar. The crossover point when the sequential component dominates the
overall execution time occurs for a larger image-size/machine-size ratio on the MP-2.
. Sequential
Parallel
___ Total
Image Size
Execution
Time
Modified Wyllie's on MP-1
. Sequential
Parallel
___ Total
Image Size
Execution
Time
Modified Wyllie's on MP-2
(a) (b)

Figure

12: Performance of the Modified Wyllie's Algorithm on varying sizes of the picnic image
on (a) 4K processors of the MP-1, and (b) 4K processors of the MP-2
5.5 Load Balancing
In an input derived from a real (as opposed to synthetic) image, it is very likely that edge contours
are concentrated in a particular portion of the image. In this case, simple partitioning of the image
into p subimages and assigning each subimage to a processor may yield an unbalanced load across
processors. In order to study the effect of load imbalance on performance, we have experimented
with various load-balancing techniques. In general, techniques based on first computing the load
variance across processors then redistributing the load to the processors with light loads have
failed to yield high performance. This is because the computation and data redistribution for
the load-balancing step become a significant part of the total execution time. Further, regardless
of the load redistribution, communication overhead remains the same.
In the following, we outline a simple heuristic to address the load balancing problem and
present performance results. The heuristic is based on dividing the input image into more than
subimages and assigning more than one subimage to each processor.
Partition the input image into kp identical sized subimages. Number the subimages in a row-
shuffled order as follows. Arrange the subimages into k sets such that each set contains a
grid of contiguous subimages. Number the subimages in each set in row-major order. From each
set to processor j, where example row-shuffled
ordering of an image on a 16 processor machine assuming shown in Figure 13.

Figure

13: A heuristic partitioning scheme of an input image on a 16 processor machine.

Figure

14 compares the distribution of edge pixels of the 1K \Theta 1K picnic image on a 16K
processor MP-1 using simple partitioning and using the partitioning based on the above described
heuristic. In the load-balanced partitioning scheme the number of processors having zero edge
pixels is reduced by half. At the same time, the variance of load (edge pixels per processor)
across the entire machine is reduced from 21.4 to 8.9.

Figures

15 and 16 compare the performance of the Modified Wyllie's Algorithm with and
without load-balancing, while varying the image and machine sizes. We observe that load-balancing
pays off only for very large image sizes. In the case of the simple partitioning scheme
used in the earlier sections, the sequential execution time dominates the parallel execution time
for large image sizes. In the load-balanced partitioning scheme, the sequential execution time
has been reduced at the expense of an increase in the parallel component. The increase in the
parallel component is due to the fact that more edge pixels in a processor now have successors
residing in other processors. This increases contention over the communication links during the
pointer jumping phase and thus increases the parallel time. The sequential time decreases only
for large ratios of N and p because the extent of load imbalance possible for small ratios will
always be low since the size of the subimage assigned to a processor is very small. This claim is
well supported by Figures 15 (b) and 16 (b).
Number
of
Processors
Number
of
Processors
(a) (b)

Figure

14: Histogram of edge-pixel distribution of the 1K \Theta 1K picnic image on 16K processors
of the MP-1: (a) the original distribution, and (b) the distribution after load-balancing.
In conclusion, a load-balancing scheme performs well for large image-size to machine-size ratios.
In terms of scalability with respect to machine size as well as problem size, the behavior using
the load balancing scheme is not much different than with the simple partitioning scheme.
Unbalanced
___ Load-Balanced
Image Size
Execution
Time
Execution Time
_. Parallel (unbalanced)
___ Parallel (load-balanced)
Image Size
Execution
Time
Sequential and Parallel Components
(a) (b)

Figure

15: Comparison of the execution time of the unbalanced and load-balanced Modified
Wyllie's Algorithm: (a) overall execution time, and (b) sequential and parallel components.
(Execution time for the picnic image on the 16K processor MP-1.)
1,024 4,096 16,3840.020.06_. Unbalanced
___ Load-Balanced
Number of Processors
Execution
Time
Execution Time
1,024 4,096 16,3840.010.030.05. Sequential (unbalanced)
_. Parallel (unbalanced)
___ Parallel (load-balanced)
Number of Processors
Execution
Time
Sequential and Parallel Components
(a) (b)

Figure

Comparison of the scalability with respect to number of processors for the unbalanced
and load-balanced Modified Wyllie's Algorithm: (a) overall execution time, and (b) sequential
and parallel components. (Execution time for the picnic image of size 512 \Theta 512 on the MP-1.)
6 Conclusions
In this paper, we have studied the scalability of list ranking algorithms on fine grained machines
and have presented efficient algorithms for list ranking of image edge lists. The Wyllie's and
Anderson & Miller's algorithms for list ranking are chosen as representative of deterministic and
randomized algorithms, respectively. The performance of these algorithms is studied on random
lists and image edge lists. It is shown that these algorithms perform poorly for image edge
lists. Also, no single algorithm covers the entire range of scalability. We show that a poly-
algorithmic approach, in which the algorithmic approach changes as the data size is reduced,
is required for scalability across all machine and problem sizes. For image edge lists, we have
presented modified algorithms that exploit the locality property of the edge lists. Performance of
our modified algorithms on actual images demonstrates the gains that can be achieved by using
applications characteristics in the algorithm design. On a 16K processor MasPar MP-1, the
modified algorithms run about two times faster on small images and about ten times faster on
large images than the standard Wyllie's and Randomized algorithms. The modified algorithms
are robust across a wide variety of images. Finally, the results of our extensive experimentation
have shown that while the standard algorithms were not scalable for list ranking on image edge
lists, the tailored algorithms exhibited good scalability with respect to increases both in image
size and number of processors, and also with respect to changes in image characteristics. We
have also shown that load balancing on fine grained machines does not pay off unless the problem
to machine size ratio is very large.
In summary, this study provides insight into the performance of fine-grained machines for
applications that employ light computations but have intense data dependent communications.
In contrast to our results for list ranking of edge lists on coarse-grained machines, the results
presented here demonstrate that implementations of communication intensive problems on fine-grained
machines are very sensitive to the characteristics of the input data and machine parameters




--R

"A simple parallel tree contraction algorithm,"
"Efficient parallel processing of image contours,"
"Faster optimal parallel prefix sums and list ranking,"
"Sequential edge linking,"
Measuring the scalability of parallel algorithms and architectures.
"Contour ranking on coarse grained machines: A case study for low-level vision computations,"
An Introduction to Parallel Algorithms
"Scalable data parallel algorithms and implementations for object recog- nition,"
"Parallel tree contraction and its applications,"
"List ranking and list scan on the Cray C-90,"
"List Ranking and Parallel Tree Contraction,"
"Efficient algorithms for list ranking and for solving graph problems on the hypercube,"
--TR

--CTR
Isabelle Gurin Lassous , Jens Gustedt, Portable list ranking: an experimental study, Journal of Experimental Algorithmics (JEA), 7, p.7, 2002
parallel algorithms;fine-grained parallel processing;image processing;scalable algorithms;list ranking;computer vision