A data and task parallel image processing environment.
The paper presents a data and task parallel low-level image processing environment for distributed memory systems. Image processing operators are parallelized by data decomposition using algorithmic skeletons. Image processing applications are parallelized by task decomposition, based on the image application task graph. In this way, an image processing application can be parallelized both by data and task decomposition, and thus better speed-ups can be obtained. We validate our method on the multi-baseline stereo vision application.
Introduction
Image processing is widely used in many application areas including the lm industry, medical
imaging, industrial manufacturing, weather forecasting etc. In some of these areas the
size of the images is very large yet the processing time has to be very small and sometimes
real-time processing is required. Therefore, during the last decade there has been an increasing
interest in the developing and the use of parallel algorithms in image processing. Many
algorithms have been developed for parallelizing dierent image operators on dierent parallel
architectures. Most of these parallel image processing algorithms are either architecture
dependent, or specically developed for dierent applications and hard to implement for a
typical image processing user without enough knowledge of parallel computing.
In this paper we present an approach of adding data and task parallelism to an image
processing library using algorithmic skeletons [3, 4, 5] and the Image Application Task Graph
(IATG). Skeletons are algorithmic abstractions common to a series of applications, which
can be implemented in parallel. Skeletons are embedded in a sequential host language, thus
being the only source of parallelism in a program. Using skeletons we create a data parallel
image processing framework which is very easy to use for a typical image processing user.
It is already known that exploiting both task and data parallelism in a program to
solve very large computational problems yields better speedups compared to either pure
task parallelism or pure data parallelism [7, 8]. The main reason is that both data and task
parallelism are relatively limited, and therefore using only one of them limits the achievable
performance. Thus, exploiting mixed task and data parallelism has emerged as a natural
solution. For many applications from the eld of signal and image processing, data set
sizes are limited by physical constraints and cannot be easily increased. In such cases the
amount of available data parallelism is limited. For example, in the multi-baseline stereo
application described in Section 5, the size of an image is determined by the circuitry of the
video cameras and the throughput of the camera interface. Increasing the image size means
buying new cameras and building a faster interface, which may not be feasible. Since the
data parallelism is limited, additional parallelism may come from tasking. By coding the
image processing application using skeletons and having the IATG we obtain a both data
and task parallel environment.
The paper is organized as follows. Section 2 brie
y presents a description of algorithmic
skeletons and a survey of related work. Section 3 presents a classication of low-level image
operators and skeletons for parallel low-level image processing on a distributed memory
system. Section 4 presents some related work and describes the Image Application Task
Graph used in the task parallel framework. The multi-baseline stereo vision application
together with its data parallel code using skeletons versus sequential code and the speedup
results for the data parallel approach versus the data and task parallel approach is presented
in Section 5. Finally, concluding remarks are made in Section 6.
Skeletons and related work
Skeletons are algorithmic abstractions which encapsulate dierent forms of parallelism, common
to a series of applications. The aim is to obtain environments or languages that allow
easy parallel programming, in which the user does not have to handle with problems as com-
munication, synchronization, deadlocks or non-deterministic program runs. Usually, they are
embedded in a sequential host language and they are used to code and hide the parallelism
from the application user.
The concept of algorithmic skeletons is not new and a lot of research is done to demonstrate
their usefulness in parallel programming. Most skeletons are polymorphic higher-order
functions, and can be dened in functional languages in a straightforward way. This is the
reason why most skeletons are build upon a functional language [3, 4]. Work has also been
done in using skeletons in image processing. In [5] Serot et al. presents a parallel image
processing environment using skeletons on top of CAML functional language.
In this paper we develop algorithmic skeletons to create a parallel image processing
environment ready to use for easy implementation/development of parallel image processing
applications. The dierence from the previous approach [5] is that we allow the application
to be implemented in a C programming environment and that we allow the possibility to
use/implement dierent scheduling algorithms for obtaining the minimum execution time.
3 Skeletons for low-level image processing
3.1 A classication of low-level image operators
Low-level image processing operators use the values of the image pixels to modify the image
in some way. They can be divided into point operators, neighborhood operators and global
operators [1, 2]. Below, we disscus in detail about all these three types of operators.
1. Point operators
Image point operators are the most powerful functions in image processing. A large
group of operators falls in this category. Their main characteristics is that a pixel from
the output image depends only on the corresponding pixel from the input image. Point
operators are used to copy an image from one memory location to another, in arithmetic
and logical operations, table lookup, image compositing. We will discuss in detail
arithmetic and logic operators, classifying them from the point of view of the number of
images involved, this being an important issue in developing skeletons for them.
Arithmetic and logic operations
Image ALU operations are fundamental operations needed in almost any imaging product
for a variety of purposes. We refer to operations between an image and a constant as
monadic operations, operations between two images as dyadic operations and operations
involving three images as triadic operations.
{ Monadic image operations
Monadic image operators are ALU operators between an image and a constant. These
operations are shown in Table 1 - s(x; y) and d(x; y) are the source and destination
pixel values at location (x; y), and K is the constant.

Table

1 Monadic image operations
Function Operation
Add constant d(x;
Subtract constant d(x;
Multiply constant d(x;
Divide by constant d(x;
Or constant d(x;
And constant d(x;
Xor constant d(x;
Absolute value d(x;
Monadic operations are useful in many situations. For instance, they can be used to
add or subtract a bias value to make a picture brighter or darker.
{ Dyadic image operators
Dyadic image operators are arithmetic and logical functions between the pixels of
two source images producing a destination image. These functions are shown below
in

Table

are the two source images that are used to create
the destination image d(x; y).

Table

operations
Function Operation
Add
Subtract
Multiply
Divide
Min
Or
And
Dyadic operators have many uses in image processing. For example, the subtraction
of one image from another is useful for studying the
ow of blood in digital
subtraction angiography or motion compensation in video coding. Addition of images
is a useful step in many complex imaging algorithms like development of image
restoration algorithms for moddeling additive noise, and special eects, such as image
morphing, in motion pictures.
{ Triadic image operators
Triadic operators use three input images for the computation of an output image.
An example of such an operation is alpha blending. Image compositing is a useful
function for both graphics and computer imaging. In graphics, compositing is used
to combine several images into one. Typically, these images are rendered separately,
possibly using dierent rendering algorithms. For example, the images may be rendered
separately, possibly using dierent types of rendering hardware for dierent
algorithms. In image processing, compositing is needed for any product that needs
to merge multiple pictures into one nal image. All image editing programs, as well
as programs that combine synthetically generated images with scanned images, need
this function.
In computer imaging, the term alpha blend can be dened using two source images
and S2, an alpha image  and a destination image D, see formula (1).
Another example of a triadic operator is the squared dierence between a reference
image and two shifted images, an operator used in the multi-baseline stereo vision
application, described in Section 5.

Table

3 Triadic image operations
Function Operation
Alpha blend d(x;
Squared di d(x;
2. Local neighborhood operators
Neighborhood operators (lters) create a destination pixel based on the criteria that
depend on the source pixel and the value of pixels in the \neighborhood" surrounding it.
Neighborhood lters are largely used in computer imaging. They are used for enhancing
and changing the appearance of images by sharpening, blurring, crispening the edges, and
noise removal. They are also useful in image processing applications as object recognition,
image restoration, and image data compression. We dene a lter as an operation that
changes pixels of the source image based on their values and those of their surrounding
pixels. We may have linear and nonlinear lters.
Linear ltering versus nonlinear ltering
Generally speaking, a lter in imaging refers to any process that produces a destination
image from a source image. A linear lter has the property that a weighted sum of the
source images produces a similarly weighted sum of the destination images.
In contrast to linear lters, nonlinear lters are somewhat more dicult to characterize.
This is because the output of the lter for a given input cannot be predicted by the
impulse response. Nonlinear lters behave dierently for dierent inputs.
Linear ltering using two-dimensional discrete convolution
In imaging, two-dimensional convolution is the most common way to implement a linear
lter. The operation is performed between a source image and a two-dimensional
convolution kernel to produce a destination image. The convolution kernel is typically
much smaller than the source image. Starting at the top of the image (the top left corner
which is also the origin of the image), the kernel is moved horizontally over the image,
one pixel at a time. Then it is moved down one row and moved horizontally again. This
process is continued until the kernel has traversed the entire image. For the destination
pixel at row m and column n, the kernel is centered at the same location in the source
image.
Mathematically, two-dimensional discrete convolution is dened as a double summation.
Given an MN image f(m; n) and KL convolution kernel h(k; l), we dene the origin
of each to be at the top left corner. We assume that f(m; n) is much larger than h(k; l).
Then, the result of convolving f(m; n) by h(k; l) is the image g(m; n) given by formula
In the above formula we assume that K;L are odd numbers and we extend the image
by (K 1)=2 lines in each vertical direction and by (L 1)=2 columns in each horizontal
direction. The sequential time complexity of this operation is O(MNKL). As it can
be observed, this is a time consuming operation, very well tted to the data parallel
approach.
3. Global operators
Global operators create a destination pixel based on the entire image information. A representative
example of an operator within this class is the Discrete Fourier Transform
(DFT). The Discrete Fourier Transform converts an input data set from the tempo-
ral/spatial domain to the frequency domain, and vice versa. It has a lot of applications
in image processing, being used for image enhancement, restoration, and compression.
In image processing the input is a set of pixels forming a two-dimensional function that
is already discrete. The formula for the output pixel X lm is the following:
x jk e 2i( jl
where j and k are column coordinates, 0  j  N 1 and 0  k  M 1.
We also include in the class of global operators, operators like the histogram transform,
which do not have an image as output, but another data structure.
3.2 Data parallelism of low-level image operators
From the operator description given in the previous section we conclude that point, neighborhood
and global image processing operators can be parallelized using the data parallel
paradigm with a host/node approach. A host processor is selected for splitting and distributing
the data to the other nodes. The host also processes a part of the image. Each
node processes its received part of the image and then the host gathers and assembles the
image back together. In Figures 1, 2 and 3 we present the data parallel paradigm with the
host/node approach for point, neighborhood and global operators. For global operators we
send the entire image to the corresponding nodes but each node will process only a certain
part of the image. In order to avoid extra inter-processor communication due to the border
information exchange for neighborhood operators we extend and partition the image as
showed in Figure 2. In this way, each node processor receives all the data needed for applying
the neighborhood operator.
Original Image Processed Image
Master 0
Master 0
node 1
node 2
node n-1
Master 0
Fig. 1. DCG skeleton for point operators
Original Image
Extended Image
Master
Master
node 1
node 2
node n-1
Master0Processed Image
Fig. 2. DCG skeleton for neighborhood operator
Original Image
Processed area at 0
Processed area at 1
Processed area at 2
Processed area at n-1
Processed Image
Master
Master (0) (0)
Fig. 3. DCG skeleton for global operators
Based on the above observations we identify a number of skeletons for parallel processing
of low-level image processing operators. They are named according to the type of the low-level
operator and the number of images involved in the operation. Headers of some skeletons
are shown below. All of them are based on a "Distribute Compute and Gather" (DCG) main
skeleton, previously known as the map skeleton [4], suitable for regular applications as the
low-level operators from image processing. The implementation of all the skeletons is based
on the ideea described in the above paragraph, see Figures 1, 2 and 3. Each skeleton can
run on a set of processors. From this set of processors a host processor is selected to split
and distribute the image(s) to the other nodes, each other node from the set receives a part
of the image(s) and the image operator which should be applied on it, then the computation
takes place and the result is sent back to the host processor. The skeletons are implemented
in C using MPI-Panda library [19, 20]. The implementation is transparent to the user.
void ImagePointDist_1IO(unsigned int n,char *name,void(*im_op)());
// DCG skeleton for monadic point operators - one Input/Output
void ImagePointDist_1IO_C(unsigned int n,char *name, void(*im_op)(),float ct);
// DCG skeleton for monadic point operators which need a constant value as pararameter
// one Input/Output
void ImagePointDist_1I_1O(unsigned int n,char *name1,char *name2,void(*im_op)());
// DCG skeleton for monadic/dyadic point operators - one Input and one Output
void ImagePointDist_1IO_1I(unsigned int n,char *name1,char *name2,void(*im_op)());
// DCG skeleton for monadic/dyadic point operators - one Input/Output and one Input.
void ImagePointDist_2I_1O(unsigned int n,char *name1,char *name2,char *name3,void(*im_op)());
// DCG skeleton for dyadic/triadic point operators - 2 Inputs and one Output
void ImagePointDist_2I_2O(unsigned int n,char *name1,char *name2,char *name3,char *name4,
Inputs and 2 Outputs
void ImagePointDist_3I_1O(unsigned int n,char *name1,char *name2,char *name3,char *name4,
// DCG skeleton for triadic point operators - 3 Inputs and one Output
void ImageWindowDist_1IO(unsigned int n,char *name,Window *win,void(*im_op)());
// DCG skeleton for neighborhood operators - one Input/Output
void ImageWindowDist_1I_1O(unsigned int n,char *name1,char *name2,Window *win,void(*im_op)());
// DCG skeleton for neighborhood operators - one Input and one Output
void ImageGlobalDist_1IO(unsigned int n,char *name,void(*im_op)());
// DCG skeleton for global operators - one Input/Output
We develop several types of skeletons, which depend on the type of the low-level operator
(point, neighborhood, global) and the number of input/output images. With each skeleton
we associate a parameter which represents the task number corresponding to that skeleton.
This is used by the task parallel framework. Depending on the skeleton type, one or more
identiers of the images are given as parameters. The last argument is the point operator for
processing the image(s). So, each skeleton is used for a number of low-level image processing
operators which perform in a similar way (for instance all dyadic point operators take two
input images, combine and process them depending on the operator type and then produce
an output image). Depending on the operator type and the skeleton type, there might exist
additional parameters necessary for the image operator. For point operators we assigned the
ImagePointDist skeletons, for neighborhood operators we assigned the ImageWindowDist
skeletons, and for global operators we assigned the ImageGlobalDist skeletons. Some of the
skeletons modify the input image (ImagePointDist 1IO, ImageWindowDist 1IO, ImageGlob-
alDist 1IO, so 1IO stands for 1 Input/Output image), other skeletons take a number of input
images and create a new output image, for example the ImagePointDist 2I 1O skeleton for
point operators takes 2 input images and creates a new output image. This skeleton is necessary
for dyadic point operators (like addition, subtraction, etc., see Table 2) which create
a new image by processing two input images. Similarly, the skeleton ImagePointDist 3I 1O
for point operators takes 3 input images and creates a new output image. An example of a
low-level image processing operator suitable for this type of skeleton is the squared dierence
between one reference image and two disparity images, operator used in the multi-baseline
stereo vision application, see Table 3 and Section 5. Similar skeletons exist also for local
neighborhood and global operators. ImagePointDist 1IO C is a skeleton for monadic point
operators which need a constant value as parameter, for processing the input image, see

Table

1.
Below we present an example of using the skeletons to code a very simple image processing
application in a data-parallel way. It is an image processing application of edge detection
using Laplace and Sobel operators. First we read the input image and we create the two
output images and a 3  3 window, and then we apply the Laplace and Sobel operators
on the num nodes number of processors. num nodes is the number of nodes on which
the application is run and is detected on the rst line of the partial code showed below.
image in is the name of the input image given as input parameter to both skeletons and
image l, image s are the output parameters (images) for each skeleton. We have used a
ImageWindowDist 1I 1O skeleton to perform both operators. The last two parameters are
the window used (which contains information about the size and the data of the window)
and the image operator that is applied via the skeleton.
4 The task parallel framework
Recently, it has been shown that exploiting both task and data parallelism in a program
to solve very large computational problems yields better speedups compared to either pure
data parallelism or either pure task parallelism [7, 8]. The main reason is that both task
and data parallelism are relatively limited, and therefore using only one of them bounds the
achievable performance. Thus, exploiting mixed task and data parallelism has emerged as
a natural solution. We show that applying both data and task parallelism can improve the
speedup at the application level.
There have been considerable eort in adding task-parallel support to data-parallel lan-
guages, as in Fx [10], Fortran M [11] or Paradigm HPF [7], or adding data-parallel support
to task-parallel languages such as in Orca [12]. In order to fully exploit the potential advantage
of the mixed task and data parallelism, ecient support for task and data parallelism
is a critical issue. This can be done not only at the compiler level, but also at the application
level and applications from the image processing eld are very suitable for this technique.
Mixed task and data parallel techniques use a directed acyclic graph, in the literature
also called a Macro Data
ow Graph (MDG) [7], in which data parallel tasks (in our case the
image processing operators) are the nodes and the precedence relationships are the edges.
For the purpose of our work we change the name of this graph to the Image Application
Task Graph (IATG).
4.1 The Image Application Task Graph model
A task parallel program can be modeled by a Macro Data
ow communication Graph [7],
which is a directed acyclic graph c), where:
{ V is the nite set of nodes which represents tasks (image processing operators)
{ E is the set of directed edges which represent precedence constraints between tasks:
{ w is the weight function which gives the weight (processing time) of each
node (task). Task weights are positive integers.
{ c is the communication function c which gives the weight (communication
time) of each edge. Communication weights are positive integers.
An Image processing Application Task Graph (IATG) is, in fact, an MDG in which
each node stands for an image processing operator and each edge stands for a precedence
constraint between two adjacent operators. In this case, a node represents a larger entity
that in the MDG where a node can be any simple instruction from the program.
Some important properties of the IATG are:
{ It is a weighted directed acyclic graph.
{ Nodes represent image processing operators and edges represent precedence constraints
between them.
{ The are two distinguished nodes: START precedes all other nodes and STOP succeeds
all other nodes.
We dene a well balanced IATG as an application task graph which has the same type
of tasks (image operators) on each level. An example is the IATG of the multi-baseline
stereo vision application, described in Section 5 Figure 7, which on the rst level has the
squared dierence operator applied to 3 images for each task and on the second level the
error operator is executed by all the tasks. Moreover, the graph edges form a regular pattern.
The weights of nodes and edges in the IATG are based on the concepts of processing
and communication costs. Processing costs account for the computation and communication
costs of data parallel tasks - image processing operators corresponding to nodes, and depend
on the number of processors allocated to the node. Communication costs account for the
costs of data communication between nodes.
4.2 Processing cost model
A node in the IATG represents a processing task (an image processing operator applied via
a DCG skeleton, as described in Section 3.2) that runs non-preemptively on any number of
processors. Each task i is assumed to have a computation cost, denoted T exec (i; p i ), which
is a function of the number of processors. The computation cost function of the task can be
obtained either by estimation or by proling.
For cost estimation we use Amdahl's law. According to it, the execution time of the task
is:
where i is the task number, p i is the number of processors on which task i is executed,
is the task's execution time on a single processor and  is the fraction of the task that
executes serially.
If we use proling, the task's execution costs are either tted to a function similar to
the one described above (in the case that data is not available for all processors), or the
proled values can be used directly through a table. The values are simple to determine,
we measure the execution times of the basic image processing operators implemented in the
image processing library and we tabulate their values.
4.3 Communication cost model
Data communication (redistribution) is essential for implementing an execution scheme
which uses both data and task parallelism. Individual tasks are executed in a data parallel
fashion on subsets of processors and the data dependences between tasks may necessitate
not only changing the set of processors but also the distribution scheme. Figure 4 illustrates
a classical approach of redistribution between a pair of tasks. Task TaskA is executed using
seven processors and reads from data D. Task TaskB is executed using four processors and
reads from the same data D. This necessitates the redistribution of the data D from the
seven processors executing task TaskA to the four processors executing task TaskB. In
addition to changing the set of processors we could also change the distribution scheme of
the data D. For instance, if D is a two dimensional data then TaskA might use a block
distribution for D, whereas TaskB might use a row-stripe distribution.
Processors executing TaskB
Processors executing TaskA
Redistribution
Fig. 4. Data redistribution between
two tasks
Processors executing TaskB
Processors executing TaskA
master A
master B
Fig. 5. Image communication between
two host processors
We reduce the complexity of the problem rst by allowing only one type of distribution
scheme (row-stripe) and second by sending images only between two processors (the selected
host processors from the two sets of processors), as shown in Figure 5.
An edge in the IATG corresponds to a precedence relationship and has associated a communication
cost, denoted through Tcomm (i; which depends on the network characteristics
(latency, bandwidth) and the amount of data to be transferred. It should be emphasized
that there are two types of communication times. First, we have internal communication
time which represents the time for internal transfer of data between the processors allocated
to a task. This quantity is part of the term  of the execution time associated to a node of
the graph. Secondly, we have external communication time which is the time of transferring
data, i.e. images, between two processors. These two processors represent the host processors
for the two associated image processing tasks (corresponding to the two adjacent graph
nodes). This quantity is actually the communication cost of an edge of the graph.
In this case we can also use either cost estimation or proling to determine the communication
time. In state-of-the-art of distributed memory systems the time to send a message
containing L units of data from a processor to another processor can be modeled as:
are the startup and per byte cost for point-to-point communication and L is
the length of the message, in bytes.
We run our experiments on a distributed memory system which consists of a cluster of
Pentium Pro/200Mhz PCs with 64Mb RAM running Linux, and connected through Myrinet
in a 3D-mesh topology, with dimension order routing [16]. Figure 6 shows the performance
of point-to-point communication operations and the predicted communication time. The
reported time is the minimum time obtained over 20 executions of the same code. It is
reasonable to select the minimum value because of the possible interference caused by other
users' trac in the network. From these measurements we perform a linear tting and we
extract the communication parameters t s and t b . In Figure 6 we see that the predicted
communication time, based on the above formula, approximates very good the measured
communication time.
measured
predicted
time(microseconds)
message size (2
Fig. 6. Performance of point-to-point communication on DAS
4.4 IATG cost properties
A task with no input edges is called an entry task and a task with no output edges is
called an exit task. The length of a path from the graph is the sum of the computation and
communication costs of all nodes and edges belonging to the path. We dene the Critical
Path [7] (CP) as the longest path in the graph. If we have a graph with n nodes, where n
is the last node of the graph and t i represents the nish time of node i, T exec (i; p i ) is the
execution time of task i on a set of p i nodes then the critical path is given by the formulas
and (7), where PRED i is the set of immediate predecessor nodes of node i.
We dene the Average Area [7] (A) of an IATG with n nodes (tasks) for a P processor
system as in formula (8), where p i is the number of processors allocated to task T i .
A =P
The critical path represents the longest path in the IATG and the average area provides
a measure of the processor-time area required by the IATG. Based on these two formulas,
processors are allocated to tasks according to the results obtained by solving the following
minimization problem:
subject to
After solving the allocation problem, a scheduler is needed to schedule the tasks to
obtain a minimum execution time. The classical approach is the well-known list scheduling
paradigm [13] introduced by Graham, which schedules one processor tasks (tasks running
only on one processor). Scheduling is known to be NP-complete for one processor tasks. Since
then several other list scheduling algorithms were proposed, and the scheduling problem was
also extended to multiple processor tasks (tasks that run non-preemptively on any number
of processors) [7]. Therefore, multiple processor task scheduling is also NP-complete and
heuristics are used.
The intuition behind minimizing  in equation (9) is that  represents a theoretical lower
bound on the time required to execute the image processing application corresponding to
the IATG. The execution time of the application can neither be smaller than the critical
path of the graph nor be less than the average area of the graph.
As the TSAS's convex programming algorithm [7] for determining the number of processors
for each task was not available, we have used in the experimental part of Section 5 the
nonlinear solver based on SNOPT [17] available on the internet [18] for solving the previous
problem. For solving the scheduling problem, the proposed scheduling algorithm
presented in [7] is used. Another possibility is to use scheduling algorithms developed for
data and task parallel graphs [8, 9].
5 Experiments
To evaluate the benets of the propose data parallel framework based on skeletons and also
of the task parallel framework based on the IATG, we rst compare the code of the multi-baseline
stereo vision algorithm with and without using skeletons (with and without data
parallelism). Then we compare the speed-ups obtained by applying only data parallelism to
the application, with the speed-ups obtained with both data and task parallelism.
The multi-baseline stereo vision application uses an algorithm developed by Okutomi
and Kanade [6] and described by Webb and al. [14, 15], that gives greater accuracy in depth
through the use of more than two cameras. Input consists of three n  n images acquired
from three horizontally aligned, equally spaced cameras. One image is the reference image,
the other two are named match images. For each of 16 disparities, 15, the rst
match image is shifted by d pixels, the second image is shifted by 2d pixels. A dierence
image is formed by computing the sum of squared dierences between the corresponding
pixels of the reference image and the shifted match images. Next, an error image is formed
by replacing each pixel in the dierence image with the sum of the pixels in a surrounding
13  13 window. A disparity image is then formed by nding, for each pixel, the disparity
that minimizes error. Finally, the depth of each pixel is displayed as a simple function of its
disparity. Figure 7 presents the IATG of this application.
It can be observed that the computation of the dierence images requires point op-
erators, while the computation of the error images requires neighborhood operators. The
computation of the disparity image requires also a point operator.
Input: ref, m1, m2 (the reference and the two match images)
for d=0,15
Task T1,d: m1 shifted by d pixels
Task T2,d: m2 shifted by 2*d pixels
Task T5: Disparity image = d which minimizes the err image
Pseudocode of the multi-baseline stereo vision application
broadcast
diff0
diff1
diff2
diff15
err0
err1
err2
reduce
ref
disparity image13171933
Fig. 7. Multi-baseline stereo vision IATG
Below we present the sequential code of the application versus the data parallel code
of the application. Coding the application by just combining a number of skeletons doesn't
require much eort from the image processing user, yet it parallelizes the application. The
data and task parallel code is slightly more dicult and we do not present it here.
{
Sequential code
{
{
{
ImagePointDist_3I_1O(d,"im","ref","m1",
DT-PIPE code based on skeletons
Besides creating the images on the host processor, the code is nearly the same, only the
function headers dier. The skeleton have as parameters the name of the images, the window
and the image operator, while in the sequential version operator headers have as parameters
the images and the window. The skeletons are implemented in C using MPI [19].
The results of the data parallel approach are compared with the results obtained using
data and task parallelism on a distributed memory system which consists of a cluster of
Pentium Pro/200Mhz PCs with 64Mb RAM running Linux [16], and connected through
Myrinet in a 3D-mesh topology, with dimension order routing. In the task parallel framework
we use a special mechanism to register the images on the processors where they are rst
created. Moreover, each skeleton has associated the task number to which it corresponds.
We use 1, 2, 4, 8, 16, 32 and 64 processing nodes in the pool. Three articial reference
images of sizes 256  256, 512  512 and 1024  1024 are used. The code is written using C
and MPI message passing library. The multi-baseline stereo vision algorithm is an example
of a regular well balanced application in which task parallelism can be applied without the
need of an allocator of scheduler. Just for comparison reasons, we have used the algorithm
described in [7] and we have obtained identical results (we divide the number of nodes to the
number of tasks and we obtain the number of the nodes on which each task should run). In

Figure

8 we show the speed-ups obtained for the data parallel approach for dierent image
sizes.

Figure

9 shows the speed-up of the same application using the data and task parallel
approach, also for dierent image sizes. We can observe that the speed-ups become quickly
saturated for the data-parallel approach while the speed-ups for the data and task parallel
approach perform very good. In fact, we have pure task parallelism up to 16 processors
and data and task parallelism from 16 on. So, the pure task parallel speed-ups will become
attened from 16 processors on because at this type of application is better to rst apply
task parallelism and then to add data parallelism. Using both data and task parallelism is
more ecient than using only data parallelism.
Processors
Fig. 8. Speed-up for the data-parallel approac

Processors81624324048
Fig. 9. Speed-up for the data and task parallel
approach
6 Conclusions
We have presented an environment for data and task parallel image processing. The data
parallel framework, based on algorithmic skeletons, is easy to use for any image processing
user. The task parallel environment is based on the Image Application Task Graph and
computing the IATG communication and processing costs. If the IATG is a regular well
balanced graph task parallelism can be applied without the need of these computations.
We showed an example of using skeletons and the task parallel framework for the multi-baseline
stereo vision application. The multi-baseline stereo vision is an example of an image
processing application which contain parallel tasks, each of the tasks being a very simple
image point or neighborhood operator. Using both data and task parallelism is more ecient
than using only data parallelism. Our code for the data and task parallel environment,
using C and the MPI-Panda library [19, 20] can be easily ported to other parallel
machines.



--R

Parallel Algorithms for Digital Image Processing
Parallel Programming
"Algorithmic skeletons: structured management of parallel computations"
Skeletons for structured parallel composition

A multiple-baseline stereo
A framework for exploiting task and data parallelism on distributed memory multicomputers
Optimal use of mixed task and data parallelism for pipelined compu- tations
CPR: Mixed Task and Data Parallel Scheduling for Distributed Systems
A new model for integrated nested task and data parallel program- ming
Fortran M: A language for modular parallel programming
A task and data parallel programming language based on shared objects
Bounds on multiprocessing timing anomalies

Implementation and Performance of Fast Parallel Multi-Baseline Stereo Vision
The Distributed ASCI supercomputer (DAS) site
User's guide for snopt 5.3: A fortran package for large-scale nonlinear programming
Lucent Technologies AMPL site
"MPI - The Complete Reference, vol.1, The MPI Core"
Experience with a portability layer for implementing parallel programming systems
--TR
Algorithmic skeletons
Parallel algorithms
Fortran M
A new model for integrated nested task and data parallel programming
A Framework for Exploiting Task and Data Parallelism on Distributed Memory Multicomputers
A task- and data-parallel programming language based on shared objects
Optimal use of mixed task and data parallelism for pipelined computations
MPI-The Complete Reference
A Multiple-Baseline Stereo
CPR

--CTR
Development platform for parallel image processing, Proceedings of the 6th WSEAS International Conference on Signal, Speech and Image Processing, p.31-36, September 22-24, 2006, Lisbon, Portugal
Antonio Plaza , David Valencia , Javier Plaza , Pablo Martinez, Commodity cluster-based parallel processing of hyperspectral imagery, Journal of Parallel and Distributed Computing, v.66 n.3, p.345-358, March 2006
Frank J. Seinstra , Dennis Koelma , Andrew D. Bagdanov, Finite State Machine-Based Optimization of Data Parallel Regular Domain Problems Applied in Low-Level Image Processing, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.865-877, October 2004
data parallelism;skeletons;image processing;task parallelism