Assignment of Task Modules in Hypercube Multicomputers with Component Failures for Communication Efficiency.
The problem of assigning task modules within a hypercube multicomputer with possible link failures is investigated. A concept of indirect optimization is introduced and a function, called communication traffic, is proposed as the objective of optimization. The assignments obtained from optimizing this function are shown to significantly improve the actual communication performance measure, called communication turnaround time, over random assignments.
Introduction
While the abundance of nodes in a hypercube multicomputer allows for executing tasks
that require a large number of nodes, inter-node communication is still a major bottleneck
in achieving the overall speedup. To achieve communication efficiency, considerable efforts
have been made to improve routing algorithms and switching mechanisms, which are basically
concerned with system-level implementations. Communication efficiency must also be
improved on a per-task basis by exploiting the communication locality among task modules.
To assign task modules for an "optimal" performance, the run-time behavior of these
modules must be known a priori to some extent. However, as stated in the Halting Problem
in computing theory, there is no way to predict the exact run-time behavior of a program
before it is actually executed. In case of distributed computation, it is also very difficult
to predict the timing of communication events before a set of task modules are actually
executed.
In the graph-mapping approach (e.g., [3]) the timing aspects of module communication
are ignored, and a simple objective function is proposed for optimization. It is generally
The work reported in this paper was supported in part by the Office of Naval Research under grants N00014-
85-K-0122 and N00014-91-J-1115. Any opinions, findings, and recommendations in this paper are those of
the authors and do not reflect the views of the ONR.
difficult to relate this objective to any of well-known performance measures, such as task
execution time. By contrast, any more complicated approach (e.g., [5]) requires a substantial
amount of knowledge of the run-time behavior of task modules, which may not be available
unless the task is tested thoroughly beforehand.
Our primary goal in this paper is to optimize communication performance. We use a relatively
simple objective function and verify (with simulations) that optimizing this function
actually leads to better communication performance, especially for assigning communication-
bound tasks. Focusing on communication performance differentiates our work from others'
related to more generic aspects of task assignment. Taking a communication-oriented approach
to the task assignment problem is hardly a limitation, since inter-node communication
is of the utmost importance to the performance and fault-tolerance of any distributed
system.
This paper is organized as follows. In Section 2, we present the basic system model
and assumptions used. Our problem is also formally stated there. In Section 3, the NP-hardness
of minimizing communication traffic is stated first in order to justify the use of
heuristic algorithms. Several heuristic algorithms are then used to find good suboptimal
solutions. These algorithms are tested extensively for various inputs to assess the quality
of the assignments obtained from them. We then simulate these algorithms to verify the
actual quality of the assignments found by minimizing communication traffic. The effects
of inaccuracy in describing the task behavior are also discussed there. Section 4 deals with
the case where an alternative fault-tolerant routing scheme is used. The paper concludes
with Section 5.
Preliminaries
The communication volume between each pair of modules is expressed in number of
packets to be exchanged between them. A message may be composed of a number of
packets. Inter-module communications are assumed to be accomplished via message passing.
A message is routed from the source to the destination via a fault-free shortest path under
circuit or message switching.
Since most existing hypercubes do not support a per-node multi-programming environ-
ment, it is assumed that at most one module is assigned to a node, i.e., the mapping between
nodes and modules is one-to-one. For a task with M modules such that 2
some integer n, one can add some "dummy" modules and make it a task with 2 n modules.
So, we will henceforth assume is the dimension of the subcube allocated
by the host to execute the task, and thus, the mapping of modules into subcube nodes is
one-to-one and onto.
For a network of nodes, we define a communication event between modules (CEBM)
as an instance that a module needs to send a message to another module, while defining
a communication event between nodes (CEBN) as an instance of a node needing to send
a message to some other node. In circuit switching, these two are indistinguishable. In
message switching, however, a single CEBM can become several CEBNs. For example, when
a pair of modules reside in two different nodes which are 2 hops apart, in circuit switching a
CEBM from one module to the other is just a CEBN from one node to the other node. For
message switching, however, this CEBM becomes two CEBNs: one from the source to the
intermediate node, and the other from the intermediate node to the destination. We said
there is an outstanding CEBN if a message is to be sent by a node. An outstanding CEBN
is said to be processed if it is sent from the source node to a neighboring destination node.
An outstanding CEBN may not be processed immediately due to the limited link resources
available. A CEBN is said to be blocked if it is not processed immediately.
The goodness of a task assignment for hypercubes is measured by the communication
turnaround time (CTT), which is the time span from the the first CEBN becoming outstanding
to all CEBNs being processed. As an illustrative example, in Fig. 1 we have a
simple network of 4 nodes with 3 CEBMs. The status of each link during the execution
under both circuit and message switching is shown in this figure. Note that the computation
time needed is invariant among different assignments, since at most one module is assigned
to each node. Therefore, CTT is the main source of difference in the completion time of a
task.
CTT cannot be easily described as a mathematical function, and the exact value of CTT
depends largely on the timing of communication events, thus making it impractical to use
any direct optimization of CTT. However, as we shall see, for communication-bound tasks,
minimizing a certain simple function can usually minimize CTT.
The communication cost in executing a set of task modules is defined as the sum of
time units during which links are kept busy with the messages among these modules. In
other words, it is a measure of the total communication resources used by an instance of
task execution measured in time units.
Suppose c(h) is the number of time units links are kept busy with a packet sent over a
path of h hops. The sum of time units links are kept busy for related purposes other than
packet transmission - such as establishing a connection - is assumed to be negligible.
For message-switched hypercubes, relation may not be accurate
for circuit-switched hypercubes. However, if the "call request" signal to hunt for a free
path occupies each link only for a very short time, then this expression would be a good
approximation even for circuit-switched hypercubes.
By defining c(1) as a unit of communication traffic (i.e., the link usage by one packet
traversing one link), the communication traffic resulting from executing a task under assignment
a becomes:
1-i-n
is the number of packets traversing over i
links. One can easily see that cost com (a) / k(a).
In both type of switching, communication traffic is proportional to the total link occupation
time, two communicating modules placed far apart will require more communication
resources, and there is a higher possibility that some other instances of communication will
be blocked and/or delayed, which in turn leads to an increase of CTT. Therefore, reduction
of communication traffic is crucial to the CTT associated with communication-bound tasks.
When introducing the notion of communication cost and communication traffic, we deliberately
avoided the low-level timing details. We only consider the total number of packets
to be sent/received between a pair of task modules during the whole mission time, thus allowing
for a simple objective function that can be translated into a simple combinatorial
optimization problem.
The following notation will be used throughout the paper:
the dimension of a subcube available for executing the task under consideration.
an M \Theta M communication volume matrix, where U ij is the communication volume
from m i to m j expressed in number of packets, and M is the number of task modules.
As mentioned earlier, we will assume specified otherwise. Note that
since a module does not send messages to itself.
vector denoting an assignment, the i-th component of which represents
the fact that m i is assigned to a node whose address is a i ,
the distance (i.e., the length of a shortest path) between node n i and
and is dependent upon the routing algorithm used. For now, we will assume
case where D(n can be different from D(n
will be discussed in Section 4.) Before making a module assignment, D(n are
calculated for a subcube assigned to the task under consideration with a shortest-path
routing algorithm. Note that the distance between a pair of nodes may be greater
than their Hamming distance and depends on the number of faulty links and the
routing scheme used.
Optimization Algorithms and Performance Evaluation
Although the objective function we proposed is simple in nature, optimizing it is still a
difficult problem, as formally stated in the following theorem.
Theorem 1: Given an M \Theta M task communication volume matrix U where
it is NP-hard to find an optimal mapping a of an M-module task onto an n-dimensional
fault-free hypercube.
The theorem can be proved by restricting to the fault-free hypercube embedding problem
discussed in [4]. The proof is presented in [6] and will not be repeated here.
Thus, there is no known polynomial-time algorithm to find an optimal mapping/assignment.
Note that minimizing CTT, rather than communication traffic itself, is our ultimate goal.
As we shall see, good heuristic algorithms will suffice in most situations. An optimal solution
that minimizes communication traffic is usually computationally expensive, and may
only improve slightly over fast algorithms in terms of minimizing CTT, our actual objective.
One simple greedy heuristic which has been tested to work well in fault-free cases [6]
is given below. Consider each task as a weighted graph with vertices representing modules
and edge weights representing communication volumes. For any two nodes x and y under
the shortest-path routing, D(x; Therefore, it is sufficient to use an undirected
graph with as the weight on the edge connecting m i and m j . We want to find
a Hamiltonian cycle in this task graph with as high a total edge-weight as possible, and
then embed this cycle into a Hamiltonian cycle in the hypercube. A Hamiltonian cycle in
a fault-free hypercube can be easily found with Gray-code enumeration.
In an injured hypercube with faulty links, however, there may not be any Hamiltonian
cycle available for embedding. So, we define a weighted relaxed (WR) Hamiltonian cycle in
an injured hypercube (with no disconnected node) as a relaxed version of Hamiltonian cycle,
such that two nodes x and y can be linked in the cycle via a virtual edge which may be a
path from x to y through some intermediate nodes. The weight on each virtual edge of the
cycle is the number of physical edges on it. The greedy algorithm embeds the Hamiltonian
cycle in the task graph with the maximum weight (found by a greedy approach) into the
minimum-weight WR Hamiltonian cycle in the injured hypercube (also found via a greedy
approach).
Two other (more complex) heuristic algorithms are also implemented and tested: a
bottom-up approach algorithm similar to the one proposed in [3], and a top-down approach
proposed in [2]. Both of these algorithms are modified to handle cases with broken links. A
third non-deterministic approach using the simulated annealing method is also implemented
and tested, where 2-opting is used as the perturb function.
To compare the quality of the assignments found by these algorithms with respect to
communication traffic, we simulated these algorithms using input tasks with randomly
generated communication volumes among their modules.
Each algorithm was executed for 1000 randomly-generated tasks where U ij 's are characterized
by a normally-distributed random variable with mean - and variance oe 2 . Changing
the value of - is found to have little effect on the relative performance of assignments found
with different algorithms as long as the ratio oe=- remains constant. It is also found that, as
oe=- approaches zero, the difference in communication traffic between random assignments
and those assignments found with the above three algorithms gets smaller, while the difference
gets larger as oe=- increases. This is consistent with the fact that when all U ij 's are
identical, all assignments will lead to an identical communication traffic, and all assignment
algorithms will perform identically.
For the input tasks used to obtain the plots in Fig. 2, U ij 's are characterized with
and the horizontal axis depicts the number of faulty links while the vertical axis
represents communication traffic. In this figure, "A1" represents the greedy algorithm,
while "A2" represents the communication traffic achieved with either top-down or bottom-up
algorithms, whichever yields smaller communication traffic. This is to enhance the
readability of the plots since the performance of the top-down and bottom-up algorithms
turns out to be very close to each other.
It can be seen from the above result that the greedy approach performs surprisingly
well. Complex (i.e., top-down and bottom-up) approaches outperform the simple greedy
approach only by a small margin. Furthermore, as the number of faulty links increases,
the gap between the two curves gets narrower. This can be explained by the fact that
both the top-down and bottom-up approaches are best suited for fault-free (thus regular)
hypercubes. For hypercubes with faulty links, the interconnection structure is no longer
symmetric or regular. In such a case, the partitioning mechanism in the top-down approach
and the combining mechanism in the bottom-up approach must use less accurate heuristic
decisions, hence degrading the performance.
The simulated annealing approach ("A3"), on the other hand, has shown more consistent
performances. Its advantages over other algorithms become more pronounced as the cube
size and the number of link failures increase. Therefore, we can conclude that this approach
is more adaptable to irregular structures.
In

Table

1, we show the relative timings of various algorithms used. The algorithms are
tested on a DEC 5000 workstation running Ultrix operating system. Though we have only
shown the performance data for problem size of 16, the relative performances
of different algorithms are found to be consistent at least up to the problem size of
To demonstrate why minimizing communication traffic can be effective, we also need to
compare the CTTs of those assignments found with different algorithms. Our simulation
model for this purpose is described below.
Timing: A time unit is selected as the time required to send a packet over a single communication
link.
Routing algorithm and mechanism:
ffl Link failures are detected before task assignment and execution. Each message is
routed through a fault-free shortest path determined prior to the execution of this
task. We assume there are no additional link failures during the execution of this
task.
ffl Under message switching, the routing mechanism at an intermediate node on a path
will take a certain amount of time to forward a message from one link to the next.
We assume this time to be relatively small and absorbed into the length of the corresponding
message.
ffl The propagation delay on a communication path is assumed to be negligible.
Task communication behavior:
ffl T , given for each task, denotes the time span between the arrival time of the first
and the last CEBMs. The arrival times of CEBMs are uniformly distributed in
Hence, for a given task assignment, a larger T represents the task being more
computation-bound, while a smaller T represents the task being more communication-
bound.
ffl L msg denotes the maximum message length measured in number of packets. The communication
volume between each pair of modules is randomly grouped into messages
of lengths within [1; L msg ].
Message scheduling and queueing: If a link is busy when it is to be used for transmitting
an incoming message, the message is stored in a FIFO queue at the source end of the link.
When more than one message requests the use of the same link at a time, one of them is
randomly chosen to use the link. This selection procedure is repeated until all requests are
honored.
The goal of our simulation is to comparatively evaluate the goodness of different assignments
under the same execution environment, but not to compare the performance of
different system implementations. So, the simulation results should not be used to determine
the relative performance of different switching methods or routing algorithms.
The assignments found are fed into an event-driven simulator to evaluate their performance
in a close to real-world environment. The results are plotted in Fig. 3 for message
switching systems. Input tasks used here are the same as those used for Fig. 2. We set
circuit-switched hypercubes are found to be similar
in most situations and thus are not presented.
The effects of changing T under the same assignment for a given task are shown in

Table

2 for message switching without link failures. The results are found to be similar to
those under circuit switching. For the cases of
T in the range [10; 300] does not have any significant impact on the relative performance of
assignments found with different algorithms. The assignments found with all of the above
algorithms have shown substantial improvements over random assignments 8 T 2 [10; 300].
This is because the network gets saturated with messages when
In case of the network becomes less congested at T - 160 and the
differences of CTTs among different assignment algorithms start to diminish. So, we can
conclude that minimizing communication traffic yields a peak improvement when the task
to be assigned is communication-bound and the communication network may become highly
congested during the execution of this task. For the T value which results
in small performance differences is approximately 750, while for it is about
2; 250. However, when T is relatively small and the network is not near saturation, the
difference in message queue length can be made smaller by using the assignments obtained
from the minimization of communication traffic. Depending on system implementation, the
performance of a node may also be influenced by the length of message queue it has to
maintain.
The effects of changing L msg are more subtle than changing T . Generally, shorter
message lengths result in better performances in circuit-switched hypercubes, while for
message-switched hypercubes, changing the message length does not affect system performance
notably if the overall communication traffic is fixed.
Our simulation results have indicated that different switching techniques do not matter
much to system performance for communication-bound tasks. Circuit switching is shown
to have only a slightly better performance than message switching for the same task as-
signments. However, as mentioned earlier, the actual performance will depend on system
implementation, and thus, the simulation results should not be used to compare the effectiveness
of the two switching methods.
When the number of faulty links grows within our preset range (i.e., less than one
third of all links), CTT also increases. For smaller hypercubes, such as introducing
even one more faulty link can make a significant difference in CTT. This effect gets more
pronounced when the number of link failures becomes larger, as one can see in Fig. 3. As
the cube size increases, there will be more fault-free links, hence making lesser impacts of
a single link failure on system performance.
Though the proposed assignment scheme requires only minimal information of run-time
task behaviors, we still need the communication matrix to assign a task. It is obvious that
unless the task has been fully tested and each message length is exactly calculated, the
entries in the communication matrix cannot be absolutely accurate. To study the effects
of an inaccurate communication matrix, we repeated the simulation for evaluating CTT
while introducing uncertainties in the communication matrix. In Fig. 4, the input tasks
are essentially the same as those in Fig. 3, but there is a maximum of 20% error in each
during an instance of actual task execution, the number of packets exchanged
From Fig. 4, one can see that inaccuracies in U ij 's affect
communication performance, especially when the cube size and number of link failures are
large. However, when the number of link failures is less than one sixth of all links, the
overall performances of various assignment algorithms are still quite close to those in the
case with exact U ij 's.
4 An Alternative Routing Algorithm
Thus far, we have assumed that the hypercube is implemented with a routing scheme
which routes messages from the source to the destination via fixed, shortest paths determined
before the execution of each task. However, there are several practical problems
with this assumption. For instance, all faulty links must be known before making a task
assignment, which may not always be possible. Also, if additional link failures occur after
the assignment, the execution of the task may become unsuccessful.
To overcome these problems, we must use a routing algorithm that is more adaptive
to system changes. For instance, the DFS routing scheme proposed in [1] is an adaptive
fault-tolerant routing algorithm which uses only a limited amount of global link status infor-
mation. Under this algorithm, the system does not require a priori link status information,
and communications can be completed even if some unexpected link failures occur during
task execution as long as all nodes involved remain connected. However, due to the adaptive
nature of the DFS routing algorithm, it is difficult to predict the length of the path used
for routing a message during task execution, especially in the presence of link failures. So,
cannot be accurately estimated, thus making it difficult to minimize the overall communication
traffic. Furthermore, under some routing scheme like the DFS routing, due to
the lack of global link status information, the length of the path chosen for communication
from node x to node y may not be the same as the one chosen for that from y to x. For exam-
ple, suppose we have a 3-cube with three broken links, 00 , 0   0, and \Lambda01. Then the length
of path chosen under the DFS routing from 000 to 111 is 3. But the path chosen to route
messages from 111 to 000 is 111 !110 !001 !101 !001 !110 !010 !011 !001 !000,
which has a length of 9. The routing schemes with this nature are said to be asymmet-
ric. In most cases, a routing scheme becomes asymmetric only in the presence of faulty
components.
Based on the above observations, one may jump to a conclusion that there is no way
to minimize the communication traffic of an assignment, and hence it will be impossible to
improve communication efficiency by appropriately placing task modules. However, as our
simulation results show below, use of the proposed objective function, even by assigning
task modules to the nodes as if there were no faulty links, can still significantly improve
communication performance over random assignments when the number of faulty links is
within a certain range.
Three assignment strategies are compared in our simulation. The first is the usual
random assignment. The second is to apply the greedy algorithm to the hypercube without
knowing which links are faulty. The third assumes perfect knowledge of link failures and
how each message will be routed during the execution. This strategy is an unrealistic,
ideal case, which gives an upper bound of performance improvement with communication
traffic, whereas the second strategy provides a lower bound. In real applications, depending
on the knowledge available during the task assignment phase, the performance should lie
somewhere between these two extremes.
Fig. 5 shows the communication traffic of the assignments under the DFS routing for
the same set of input tasks as in Fig. 2. "S1" represents the assignments found with no
knowledge of faulty links, while "S2" represents those found with complete knowledge of
faulty links and the routing paths of all messages. It can be easily seen that under the
DFS routing, the overall communication traffic is higher than the routing algorithm used
before. Nevertheless, the assignments "S1" still generate smaller communication traffic than
random assignments, though the improvement becomes insignificant as the number of faulty
links increases.
The same set of input tasks used in Fig. 3 are employed again for event-driven sim-
ulations, except that the DFS routing is used here. Since the DFS routing is designed
based on the operating principles of message switching, we only simulate the hypercubes
implemented with this switching method.
The measured CTTs of these assignments are plotted in Fig. 6. It is found that, without
knowledge of faulty links, assignments "S1" still improves over random assignments with
a margin of at least 10% when the number of faulty links is more than one eighth of the
total links. This margin increases as the number of faulty links increases, but starts to
level off when the percentage of faulty links approaches 33%. The assignments "S2" show
even larger improvements and improve over random assignments with a steadily increasing
margin as the number of link failures increases.
By comparing Fig. 6 with Fig. 3, one can see that, though the DFS routing results in an
overall higher communication traffic, it results in smaller CTTs when the number of faulty
links is relatively small. This is due to the fact that the DFS routing chooses communication
paths in a more "spread out" fashion and causes less congestion than the shortest fixed-
path scheme used before. This advantage diminishes after the number of faulty links grows
beyond one fifth of all links. When the percentage of faulty links reaches 25%, the DFS
routing begins to yield larger CTTs than the shortest path routing. This is because paths
available between nodes are becoming fewer, so messages cannot be spread out to more
paths under the DFS routing. Also, the greater communication traffic overhead of the DFS
routing starts to have dominant effects. Note, however, that implementation details will be
crucial in actual applications and these simulation results should not be used to judge the
relative merits of different routing algorithms.
Concluding Remarks
Using a simple objective function, we formulated and solved the problem of mapping
a task which is composed of multiple interacting modules into a hypercube with possible
faulty links. The goal was to optimize communication performance, measured in communication
turnaround time. Due to the difficulties in optimizing this objective directly, a
function called communication traffic is proposed. By minimizing this function, we could
find assignments with the optimal communication performance using heuristic combinatorial
techniques. Several algorithms that find assignments by minimizing communication
traffic are implemented and comparatively evaluated. The assignments found with these
algorithms are also evaluated with simulations. It has been shown that for communication-
bound tasks, they have significant improvements over random assignments with respect to
an actual communication performance measure, i.e., the communication turnaround time.
We also analyzed the case where an alternative routing algorithm like the DFS routing
is used. Our task assignment criterion is again shown to work well in this case.
Although we have focused our attention on hypercube multicomputers, the objective
function we developed can be generalized to other distributed systems with different interconnection
topologies. In fact, when we consider hypercubes with faulty links, they
are actually no longer hypercubes, but they are subgraphs of hypercubes. For systems
with other interconnection topologies, as long as they adopt message switching or circuit
switching and the length of the path chosen by the routing scheme between each pair of
nodes is known before a task assignment, our assignment criterion can be applied to these
architectures.



--R

"Depth-first search approach for fault-tolerant routing in hypercube multicomputers,"
"Task allocation onto a hypercube by recursive mincut bipartitioning,"
"A task mapping method for a hypercube by combining subcubes,"
"Hypercube embedding is NP-complete,"
"Temporal communication graphs: A new graph theoretic model for mapping and scheduling in distributed memory systems,"
"Communication-oriented assignment of task modules in hypercube multicomputers,"
--TR
Task allocation onto a hypercube by recursive mincut bipartitioning
Depth-First Search Approach for Fault-Tolerant Routing in Hypercube Multicomputers

--CTR
Tarek F. Abdelzaher , Ella M. Atkins , Kang G. Shin, QoS Negotiation in Real-Time Systems and Its Application to Automated Flight Control, IEEE Transactions on Computers, v.49 n.11, p.1170-1183, November 2000
Dar-Tzen Peng , Kang G. Shin , Tarek F. Abdelzaher, Assignment and Scheduling Communicating Periodic Tasks in Distributed Real-Time Systems, IEEE Transactions on Software Engineering, v.23 n.12, p.745-758, December 1997
hypercube multicomputers;fault-tolerant routing;communication cost;component failures;communication turnaround time;optimization;communication traffic;indirect optimization;task assignment;NP hard problem;link failures;telecommunication traffic;performance measure;communication efficiency;task modules;hypercube networks