arp/ccom/archive/iWarp-papers/spaa93-arbitrary-connection-sets.pdf. It's a snapshot of the page taken as our search engine crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
Supporting sets of arbitrary connections on iWarp through communication context switches
Reprint from the proceedings of the Fifth ACM Symposium on Parallel Algorithms and Architectures
SPAA93, July 1-4, 1993, Schloss Velen, Westfalia, Germany.
Supporting sets of arbitrary connections on iWarp through communication
context switches
Anja Feldmann
Thomas M. Stricker
Thomas E. Warfel
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213-3890
Abstract
In this paper we introduce the ConSet communication model for
distributed memory parallel computers. The communication needs
of an application program can be satised by some arbitrary set of
connections which are partitioned into discrete phases. A commu-
nication context switch is used to select the active phase.
We present an implementation of the ConSet model on the iWarp
and describe its performance characteristics, contrasting it to a mes-
sage passing implementation on the same machine. Our implemen-
tation demonstrates how one existing parallel computer can function
as a recongurable network without needing a new processor in-
terconnect technology.
The ConSet model works best when communication patterns can
be optimized at compile time. We examine the interactions of the
target architecture with the algorithmic problems encountered de-
signing a communication compiler to effectively partition, route,
and schedule connections. We built a prototype communication
compiler for our iWarp implementation, and are using it to generate
iWarp code. Looking at basic communication patterns as well as
patterns generated by an iterative nite element PDE solver, we
compare ConSets performance (using the compilers schedules) to
that of message passing. Our experiments suggest that ConSet com-
munication offers a performance advantage over message passing in
applications where the communication pattern is known at compile
time.
1
Introduction
In connection-based communication a persistent channel is opened
from one processor to another to satisfy an applications communi-
cation needs. A connection provides unidirectional communication
between any two nodes and offers guaranteed bandwidth and la-
tency. Each active connection requires physical network resources;

Supported in part by the Defense Advanced Research Projects Agency,
Information Science and Technology Ofce, under the title "Research on
Parallel Computing," ARPA Order No. 7330. Work furnished in connection
with this research is provided under prime contract MDA97290C0035
issued by DARPA/CMO to Carnegie Mellon University.
thus, only a limited number of connections may be active at one
time. Over an applications lifetime, more connections may be re-
quired than the physical machine can simultaneously support. The
ConSet model therefore promotes the notion of arbitrary sets of
connections which are split into phases. A phase consists of a
subset of connections which can all be held active by the available
hardware resources; exactly one phase is active at any time. Which
particular phase is active is under application control; the appli-
cation requests a communication context switch to swap between
active phases. All connections belonging to the active phase are
themselves active and hence usable by the application. For most
applications, restricting the number of active connections does not
inict a large performance penalty. Our observations indicate that
connection usage by applications shows a high degree of temporal
locality; only a limited number of connections are actually in use at
any one time. We refer to this as communication locality, similar in
concept to locality of reference.
In the iWarp architecture ([BCC
+
88], [BCC
+
90]), connections
between processors are established by chaining multiple logical
channels (see Section 4.1.2) to form a pathway. Once a pathway is
established, data can ow without interruption. Each iWarp node,
referred to as a cell, can support 20 logical channels. Individual
logical channels on one cell may be linked to logical channels
on a neighbor so that arriving data is automatically forwarded;
this mechanism forms pathways. iWarp cells can have multiple
active connections; the exact number depends on the logical channel
allocations. The total pattern of logical channel linkages across the
array, combined with the state of the associated channel buffers,
constitutes the communication context. A communication context
switch is a global operation which efciently switches the pattern of
logical channel linkages over the whole array. When an application
switches phases, precompiled channel linkage information is loaded
into the communication agent from the computation agent at each
cell, thereby causing a new set of connections to become active.
Snyder suggested a highly congurable parallel computer, the
CHiP architecture, based on a similar concept back in 1982 [Sny82]
and created Poker, a programming environment originally moti-
vated by this architecture [Sny84, NSS
+
88]. The major distinctions
are that his processors were embedded into a larger switch lattice,
and his connections are directly established by these switches rather
than with logical channels. CHiP provides no sharing of the physi-
cal links among active connections. iWarps logical channels enable
us to support a greater number of active connections and hence con-
struct more complex networks per phase.
We contrast implementations of the ConSet and message passing
models on the iWarp, which provides reasonable hardware support
for both models. Message passing is an alternative programming model where information which needs to be communicated between
arbitrary processors gets wrapped, addressed and sent out to the
communication network, which in turn is responsible for routing and
delivering the messages. The iWarp communication agent supports
message passing with short-lived pathways and wormhole routing.
ConSet was motivated by a common engineering application,
namely, a nite element problem solver. The nite element method
(e.g. [Joh87]), approximates solutions to partial differential equa-
tions by solving algebraic systems with large, irregular, sparse coef-
cient matrices. These irregularities make load balancing difcult,
and achieving maximum performance on distributed memory par-
allel computers requires precise knowledge of the target architec-
ture together with careful partitioning of the problem. Fortunately,
domain-based problems such as this have an underlying combinato-
rial graph with several useful properties derived from the geometric
structure, among them the fact that all communication is known
in advance [SBF
+
92]. This information can be used by a com-
munication compiler to order, route, and schedule the necessary
communication, in effect providing a globally optimal communica-
tion scheme. The communication compiler automatically generates
the communication code for the parallel program. It partitions the
set of arbitrary connections into distinct phases, then routes and
schedules the communication within each phase. In contrast to the
work of Bianchini and Shen [BS87], the ConSet model schedules
connections rather than packet trafc. The approach of Smitley and
Lee [SL89], to embed the set of connections onto any
r
-regular net-
work, is of little use to us since embedding this network on iWarp
would be as hard as the original problem.
Interest in recongurable networks is not new, and a complete
overview is beyond the scope of this paper. (For more complete
information see [LS91]). The simplest ones allow a program to
specify the desired network type (within some hardware restric-
tions) at load time (e.g. [FLM
+
92]). Most complex SIMD propos-
als can recongure their network topologies at every instruction;
most notable is the polymorphic-torus [LM89]. While this is a nice
theoretical model [BAPRS91], a bus-based architecture is inher-
ently non-scalable with conventional technology. We show how
an existing parallel computer, the iWarp, can function today as a
recongurable network to support phased connection sets.
2
Sets of arbitrary connections (ConSet) as a com-
munication model
Parallel applications are usually constructed from a sequence of
discrete algorithms. Each of these building blocks may use dif-
ferent communication networks, or more precisely, different sets
of arbitrary connections. Neighborhood operations tend to use
meshes, convolutions use butteries, and permutations need a fully-
connected graph. Some connection arrangements may exceed the
available hardware resources and are therefore split into more than
one phase. A phase consists of a subset of connections that can
be held active simultaneously. Usually, there is a communication
schedule for each communication phase, generated by automatic
tools. Figure 1