Performance Portability of Parallel Programs
on Networks of Workstations
1 Introduction
Networks of heterogeneous nodes are emerging as the most di used computing plat-
forms. Exploiting the parallelism intrinsic in distributed systems is a di cult goal
because these platforms are essentially di erent from traditional parallel machines, es-
pecially if we refer to nondedicated platforms where the computational power of nodes
may be highly variable. The peculiarities of network computing carry the portability-
vs-e ciency issue to extremes. Letting the programmer take into account the irregular-
ities of each platform greatly increases programming complexity and hinders program
portability. Conversely, not taking the platform characteristics into account prevents
the achievement of e cient network computations. Therefore, an e cient portability
is strictly related to the possibility that the program can adapt itself to the dynamic
characteristics of the platform (self-adaptable application). In this paper, we describe a
framework that adds self-adaptivity to SPMD applications with message-passing.
When the platform consists of nondedicated nodes with nonuniform and variable
computational powers, the application requires complex communication patterns and
nonuniform data-distributions that can be optimized at runtime only. Standard libraries
such as PVM and MPI provide the programmer with abstract machines that hide
the heterogeneity due to the di erent operating systems, data representations, and
communication layers. However, they do not overcome other ine ciencies of network
computing which are due to irregular topology, nonuniform workload distribution, and
the unpredictable power variability of nondedicated resources.
Supported by the Italian Ministry of University and Scienti c Research in the framework of the
project High Performance Systems for Distributed Applications.
, The Dame framework described in this paper provides an abstract machine which
emulates the main features of a distributed memory parallel computer that is, regu-
lar interconnection network topology, nodes having uniform and static computational
powers, and homogeneous operating system and data representation [5]. The novel
features of Dame, with respect to the former version, reside in the optimization of the
programming primitives. The Dame runtime support adapts the program written for
the abstract (regular) parallel machine into a code able to run e ciently on networks
of workstations. The originality of the design choices and solutions to the portability-
vs-e ciency issue mainly comes from the considered SPMD paradigm. This allows
us to make optimizations that are impossible to realize in other paradigms, such as
task and object oriented parallelism. Task parallelism is surely the most investigated
paradigm for self-adaptive applications. However, the big overheads are due to task
stopping, transferring and restarting. An interesting proposal for enriching PVM appli-
cations with process migration supports that adapt workload to workstation conditions
is MPVM [2], while thread migrations are proposed in UPVM [2] and Nomadic Threads
[9]. For data-oriented parallelism, some remarkable results have been obtained for the
master/slave paradigm [2, 8] and for environments integrated with automatic compil-
ers [7]. Other projects that present some similarities with Dame goals use di erent
programming paradigms and languages, such as Linda [1] and Dataparallel C [10].
The paper is organized as follows. Section 2 discusses the design decisions taken
to allow portability and self-adaptivity of SPMD applications, and describes the main
features of the proposed programming paradigm. Section 3 outlines Dame's interven-
tion in the startup phase and focuses on the runtime support. Section 4 shows some
experimental results, while Section 5 concludes the paper with some nal remarks.
2 E cient portability
2.1 Abstract machine
The Dame abstract machine has to satisfy three important requirements that address
the portability-vs-e ciency issue.
1. Hiding most details of the actual platform, to simplify parallel programming. The
programmer refers to a virtual data-distribution that is, a data domain which is
uniformly distributed among the nodes.
2. Allowing the execution of a Dame program on any platform independently of
the number and type of nodes. The code portability is obtained through a set of
high-level programming primitives oriented to the virtual data-distribution.
3. Guaranteeing the e ciency of Dame programs running on networks of worksta-
tions. The performance portability is achieved by assigning to each processor a
workload that takes the (variable) computational power of each processor into
account. If signi cant power variations occur during computation, a data recon-
guration process is activated.
Through this average-level abstract machine, Dame simpli es the programming task
still preserving the e ciency of this kind of computations. Comparing our choice with
other proposals, Dame can be considered intermediate between the ADM [2] and Linda
[1] abstract machine. It hides system heterogeneity, node nonuniformity, and runtime
on Networks of Workstations
1 Introduction
Networks of heterogeneous nodes are emerging as the most di used computing plat-
forms. Exploiting the parallelism intrinsic in distributed systems is a di cult goal
because these platforms are essentially di erent from traditional parallel machines, es-
pecially if we refer to nondedicated platforms where the computational power of nodes
may be highly variable. The peculiarities of network computing carry the portability-
vs-e ciency issue to extremes. Letting the programmer take into account the irregular-
ities of each platform greatly increases programming complexity and hinders program
portability. Conversely, not taking the platform characteristics into account prevents
the achievement of e cient network computations. Therefore, an e cient portability
is strictly related to the possibility that the program can adapt itself to the dynamic
characteristics of the platform (self-adaptable application). In this paper, we describe a
framework that adds self-adaptivity to SPMD applications with message-passing.
When the platform consists of nondedicated nodes with nonuniform and variable
computational powers, the application requires complex communication patterns and
nonuniform data-distributions that can be optimized at runtime only. Standard libraries
such as PVM and MPI provide the programmer with abstract machines that hide
the heterogeneity due to the di erent operating systems, data representations, and
communication layers. However, they do not overcome other ine ciencies of network
computing which are due to irregular topology, nonuniform workload distribution, and
the unpredictable power variability of nondedicated resources.
Supported by the Italian Ministry of University and Scienti c Research in the framework of the
project High Performance Systems for Distributed Applications.
, The Dame framework described in this paper provides an abstract machine which
emulates the main features of a distributed memory parallel computer that is, regu-
lar interconnection network topology, nodes having uniform and static computational
powers, and homogeneous operating system and data representation [5]. The novel
features of Dame, with respect to the former version, reside in the optimization of the
programming primitives. The Dame runtime support adapts the program written for
the abstract (regular) parallel machine into a code able to run e ciently on networks
of workstations. The originality of the design choices and solutions to the portability-
vs-e ciency issue mainly comes from the considered SPMD paradigm. This allows
us to make optimizations that are impossible to realize in other paradigms, such as
task and object oriented parallelism. Task parallelism is surely the most investigated
paradigm for self-adaptive applications. However, the big overheads are due to task
stopping, transferring and restarting. An interesting proposal for enriching PVM appli-
cations with process migration supports that adapt workload to workstation conditions
is MPVM [2], while thread migrations are proposed in UPVM [2] and Nomadic Threads
[9]. For data-oriented parallelism, some remarkable results have been obtained for the
master/slave paradigm [2, 8] and for environments integrated with automatic compil-
ers [7]. Other projects that present some similarities with Dame goals use di erent
programming paradigms and languages, such as Linda [1] and Dataparallel C [10].
The paper is organized as follows. Section 2 discusses the design decisions taken
to allow portability and self-adaptivity of SPMD applications, and describes the main
features of the proposed programming paradigm. Section 3 outlines Dame's interven-
tion in the startup phase and focuses on the runtime support. Section 4 shows some
experimental results, while Section 5 concludes the paper with some nal remarks.
2 E cient portability
2.1 Abstract machine
The Dame abstract machine has to satisfy three important requirements that address
the portability-vs-e ciency issue.
1. Hiding most details of the actual platform, to simplify parallel programming. The
programmer refers to a virtual data-distribution that is, a data domain which is
uniformly distributed among the nodes.
2. Allowing the execution of a Dame program on any platform independently of
the number and type of nodes. The code portability is obtained through a set of
high-level programming primitives oriented to the virtual data-distribution.
3. Guaranteeing the e ciency of Dame programs running on networks of worksta-
tions. The performance portability is achieved by assigning to each processor a
workload that takes the (variable) computational power of each processor into
account. If signi cant power variations occur during computation, a data recon-
guration process is activated.
Through this average-level abstract machine, Dame simpli es the programming task
still preserving the e ciency of this kind of computations. Comparing our choice with
other proposals, Dame can be considered intermediate between the ADM [2] and Linda
[1] abstract machine. It hides system heterogeneity, node nonuniformity, and runtime
