Reducing Communication Latency with Path Multiplexing in Optically Interconnected Multiprocessor Systems.
AbstractReducing communication latency, which is a performance bottleneck in optically interconnected multiprocessor systems, is of prominent importance. A conventional approach for establishing connections in multiplexed networks uses a set of independent time slots (or virtual channels) along a path for each connection. This approach requires the use of switching devices capable of interchanging time slots, and thus introduces latency in addition to hardware and control complexity. In this paper, we propose an approach to all-optical Time Division Multiplexed (TDM) communications in multiprocessor systems. The idea is to establish a connection along a path using a set of time slots (or virtual channels) that are dependent on each other, so that no time-slot interchanging is required. We compare the proposed approach with the conventional one in terms of the overall communication latency. We found that, despite the possibility that establishing a connection may take a longer time, the proposed approach will result in lower overall communication latency as it eliminates the delays introduced by the time-slot interchanging switching devices.
Having virtual channels increases bandwidth utilization and facilitates adaptive routing algorithms as well
as the static mapping of the communication requirements of various applications [6-8]. TDM techniques are
also useful for tolerating the propagation latency in optically interconnected multiprocessor systems [9-12],
and for reducing the control complexity of channel allocation in TDM systems [13, 14] and in Wavelength
Division Multiplexed (WDM) systems [15, 16].
A key issue to be addressed in optically interconnected multiprocessor systems is the reduction of the
communication latency which is a performance bottleneck in such systems. In this paper, we describe a
new multiplexing approach for establishing all-optical connections in multiprocessor systems, and compare
it with a conventional multiplexing approach.
The paper is organized as follows. In Section 2, we provide motivations for considering circuit-switching,
and describe possible ways to achieve global synchronization which is required for TDM communication.
In Section 3, we describe how connections, especially virtual connections, are established in multiplexed
networks. Specifically, a conventional approach which we call Link Multiplexing (or LM) is described in
Section 3.1. Using LM, a connection may be established by selecting a time slot on each link independently
of the time slots selected on the other links along a path. Thus, in order to transfer messages between two
possibly different time slots, the switches in the network are required to have the capability of interchanging
time slots [17-19]. The proposed approach called Path Multiplexing (or PM) is described in Section 3.2.
Using that approach, the time slots selected on the links along a path are dependent on each other, such that
no time-slot interchanging is needed to transfer messages along the path. For example, a connection may
be established along a path by selecting the same time slot on every link. Network control, or signaling,
involved in selecting the time slots to establish a connection is described in Section 3.3.
In Section 4.1, we examine the components of the overall communication latency, and compare these
components in the two approaches. Intuitively, given a network containing a set of existing connections, it is
more likely that a set of independent time slots, rather than a set of time slots that are dependent on each other,
is available for establishing a new connection. Therefore, the conventional LM may result in shorter blocking
time. However, time-slot interchanging in LM introduces delays as a part of network propagation latency.
Thus, PM may reduce the overall communication latency, as well as the hardware and control complexities
due to the elimination of time-slot interchanging. In the rest of Section 4, we present both analytic and
simulation results which show that, for the range of parameter values we considered, the proposed PM
approach reduces the overall communication latency when compared to the LM approach. Thus, PM may
be used in the design of high performance, low complexity optically interconnected multiprocessor systems.
We conclude this paper in Section 5.
Communications in TDM Networks
We consider a network which consists of switches having a fixed number of inputs and outputs. Some
of these inputs and outputs are used to interconnect with other switches through a set of external links,
while the others are used to connect to a local processing element through a set of internal links. Figure 1
shows an example with a mesh-like topology. Each switch in this network has four pairs of external links
to adjacent switches and one pair of internal links to a processing element (PE). Each of these links can
be time-multiplexed to create multiple virtual links in multiple time slots. As high bandwidth is easier to
obtain with optical interconnects than with electronic ones [1-3], we propose to use fiber links (connected
with optical switches) as an alternative to support multiprocessor communications.
Circuit Switching
Processors communicate with each other by sending and receiving messages, which can be done via
either circuit-switching or packet-switching. In this paper, we study circuit-switched networks, and in
particular, focus on the communication latency in the two TDM circuit-switching methods, LM and PM,
which will be described in details in Section 3.1 and Section. 3.2, respectively. What motivates this study is
that with optical interconnects, packet-switching would require conversions between electronic and optical
signals at intermediate switching nodes for address decoding purposes. Such conversions are expensive
in both time and implementation cost. On the other hand, since an optically interconnected system has
enough bandwidth, circuit-switching can be used to trade in some bandwidth for the elimination of such
conversions. In addition, with high available bandwidth, software (or protocol) latency and/or hardware (or
network communication) latency become the performance-limiting factors. Using light weight protocols
such as compiled communications [20, 21], and memory mapped interfaces [22-24], software latency can
be significantly reduced. In such cases, it is important to reduce the network communication latency.
Synchronization
Optical clock distribution systems offer less clock skew and better noise immunity than electronic
ones. The relatively larger fan-out of optics makes it possible to distribute a global clock generated by a
high-power laser to hundreds of receiver modules at a high frequency [25]. An optical clock distribution
system in which each processor or switch receives an identical copy of the global clock signal was recently
implemented in the Cray T90 Series with up to processors.
We consider a TDM network, in which global synchronization is required at the data packet level, not
at the bit level. More specifically, multiplexing of different messages is done based on time slots, and the
duration of a time slot is typically equal to the duration of several hundreds of bits. For synchronization
purposes, a guard band at each end of a time slot can be used to accommodate possible drifting or jitters.
For example, if the duration of a time slot is 276 ns, which includes a guard band of 10 ns at each end, then
256 ns can be used to transmit data. If the transmission rate is 1 Gb/s, then a packet having 256 bits can be
transmitted during each time slot. The issues related to the optimal duration of a time slot, which depends
on many factors including the transmission technology as well as the communication requirements of the
applications, will not be addressed in this paper.
In a TDM network, each physical link is time-multiplexed at the rate of time slots. Specifically, the time
horizon on each link is divided into intervals of K time slots, for some K. Each time slot corresponds to a
virtual channel, and each interval of K time slots is referred to as a frame, where K is called the frame size,
or the multiplexing degree. Typically, the time for a signal to travel each link (at most a few feet) is less
than the duration of a guard band. Hence, the processors and switches in the network can be synchronized
under a global time slot clock. A connection can be established by using a set of time slots, one on each
link on a physical path from a source to a destination. For a given link, if time slot
a frame is used to establish a connection, then for the duration of the connection, the same time slot of the
next frame is also used for that connection. However, as will be discussed later, different time slots may or
may not be used on different links depending on whether LM or PM is used.
Establishing Virtual Paths
In order to establish a connection, a physical path (PP) from a source to a destination is chosen first.
Afterwards, a virtual path (VP) consisting of several time slots, one on each link of the physical path, is
selected and the connection is established. How a PP can be selected has been studied extensively and
is well understood [26]. In what follows, we illustrate how a connection can be established assuming
that a PP has been selected. Specifically, in the following two subsections, 3.1 and 3.2, we give detailed
descriptions and examples of how time slots should be selected on two adjacent links, and what kind of
switches are required using the conventional Link Multiplexing (LM) and the proposed Path Multiplexing
(PM) approaches, respectively. Then in subsection 3.3, we describe network control or signaling, that is,
how control information needed to establish a VP is exchanged.
3.1 Link Multiplexing (LM)
One way to establish a VP in a TDM network is the so-called Link Multiplexing (LM) approach. More
specifically, a VP may be established over a set of independent time slots along a PP. This, however, calls
for the use of Time Slot Interchangers (TSIs) in order to transfer the information carried over the same
connection from one time slot on one link to another time slot on the next link along the path.
A TSI capable of interchanging K(? 1) time slots can be viewed as a "black box" having one input
and one output, each being multiplexed with K virtual channels, or equivalently, each carrying frames of K
time slots. In Figure 2(a), K is assumed to be 4, and thus an input or output frame has 4 time slots. The TSI
switches time slots 0, 1, 2 and 3 of the input frame to time slots 2, 0, 3, 1 of the output frame, respectively.
By setting the TSI properly, any time slot of the input frame can be switched to any idle time slot of the
output frame (i.e., any time slot to which no other time slots of the input frame has been switched).
A more generalized form of a TSI is the so-called Time-Space-Time (TST) switch which has S - 1
inputs and outputs. When switch becomes a TSI. When S ? 1, a TST switch may be viewed
as an augmented S \Theta S switch with each input and output being multiplexed with K time slots. By setting
a TST properly, any time slot of any input can be switched to any idle time slot of any output. Figure 2(b)
shows a TST with 4, in which time slot 0 of input Q is switched to time slot 2 of output Y .
We now illustrate the LM approach using an example. As shown in Figure 3, each switch in a network
is required to be a TST switch. Assume that a VP needs to be established on two physical links X and Y .
Since switch ff can interchange time slots, the message may arrive during any time slot i on X and then
leave during any time slot j on Y , where 0 - long as these two time slots are not being
used by other connections. That is, when establishing the connection using LM, time slots i and j will be
selected independently on links X and Y , respectively.
Electronic TSIs
A TSI (or TST) can be implemented either electronically or optically. An electronic implementation of a
TSI for shown in Figure 4. An Optical-to-Electronic (O/E) conversion circuit (i.e. receiver) at the
input side converts the incoming optical signals to electronic ones. The converted signals from time slots 0,
are then stored in input buffers 0, 1, 2 and 3, respectively. The 4 \Theta 4 crossbar switch between the
input and the output buffers is then set such that the content of a given input buffer is copied to a desired
output buffer (Figure 4 shows the setting used in the TSI in Figure 2 (a)). Finally, an Electronic-to-Optical
(E/O) conversion circuit (transmitter) transmits the content of the output buffers 0, 1, 2 and 3 in that order.
One of the drawbacks of an electronic implementation of a TSI (or TST) is the expensive high speed
receiving and transmitting circuits inside each switch, which also makes the TSI (or TST) nontransparent
to bit-rate. Specifically, in a network consisting of S \Theta S TSTs, in addition to one pair of receiving and
transmitting circuits at the processor-to-network (or processor-to-switch) interface, another are
needed inside each switch, one for each input-output link. Since these circuits are designed for a specific
receiving and transmitting speed (say at 1Gb/s), one will have to replace all of them to achieve higher
bit-rate transmissions (say at 2 Gb/s).
Another drawback that is of special interest to us in this paper is the delay introduced in the process
of buffering (and interchanging) time slots because both the input and output frames need to be aligned
according to a frame clock. Specifically, if frame integrity is desired, that is, all the incoming time slots
belonging to an input frame need to be in the same output frame, then every incoming time slot will need to
be delayed by at least K time slots. Some of the incoming time slots will be delayed additionally because
of the need to change their relative positions in the output frame. For example, incoming time slot 0 will
be delayed for 4 slots in order to become outgoing time slot 2. Even if frame integrity is not
desired, an incoming time slot may also have to be delayed. For example, in Figure 4, since incoming time
slot 1 needs to become outgoing time slot 0, it has to be transmitted in the next frame, resulting in a delay
of 3 time slots.
Optical TSIs and TSTs
A TSI (or TST) can also be implemented optically using fiber-loop delay lines and Lithium Niobate
directional couplers (also called switches) [17, 27, 19]. Figure 5 shows an optical TSI for 4. The
TSI consists of five 2 \Theta 2 switches, each of which can be set to either straight ("=") or cross ("X") (the
symbol "?" in the figure stands for "don't-care"). A fiber-loop delay line with one time slot delay is placed
on the lower links between the first and second switches as well as between the fourth and fifth switches.
In addition, a delay of two time slots is placed between the second and third switches as well as between
the third and fourth switches. With each of the five switches set to its sequence of states as shown in the
figure, incoming time slots 0, 1, 2 and 3 become outgoing time slots 2, 0, 3 and 1 after being delayed for
4, 1, 3 and 0 time slots, respectively (Figure 5 shows the setting used in the TSI in Figure 2). Note that in
this implementation, the output frame is not aligned with the input frame. However, because incoming time
slot 3 needs to become outgoing time slot 1, the output frame can not start until time 2. In other words, the
output frame needs to be delayed by 2 time slots. If incoming time slots 0 and 3 need to become outgoing
time slots 3 and 0, respectively, then incoming time slot 0 should be delayed for a maximum delay of 6 time
slots, which is why the total number of delays available in the TSI is 6.
Note that although such an optical implementation eliminates E/O and O/E conversions during the
switching, therefore providing bit-rate transparency, optical TSIs are not without drawbacks. For one
thing, they, like electronic TSIs, will introduce delays as a part of propagation latency of a network as
illustrated above. In addition, not only are the control and hardware more complex, optical TSTs will
introduce additional crosstalks and attenuations of optical signals. These undesirable effects could be
detrimental to the performance of optically interconnected multiprocessor systems. In the next section, we
describe an approach that can establish all-optical connections without using TSTs.
3.2 Path Multiplexing (PM)
Before we describe the proposed approach in details, we first review a connection paradigm, called Reconfiguration
with TDM (RTDM), which was previously developed for indirect networks [13, 14].
Using the RTDM, an indirect network, such as a crossbar or an Multistage Interconnection Network
(MIN), behaves like a Time-Multiplexed Switch (TMS). More specifically, the network repeatedly goes
through a sequence of configurations, one during each time slot. Figure 6 illustrates a possible sequence of
four (4) configurations that a 4 \Theta 4 switch may go through. Like the TST switch shown in Figure 2(b), each
input and output of the TMS is multiplexed with degree However, unlike that TST, a time slot i of
any input link is switched to the same time slot i of an output link in the TMS, as shown in the figure. This
means that such a TMS does not have the capability of interchanging time slots as a TST switch does. As a
result, the signals arriving at a given input during time slot i will go to an output which depends solely on
the switch setting during that time slot.
In an S \Theta S switch, all possible S 2 connections can be established by multiplexing the switch with
degree may result in an unnecessarily long latency because a given
input-output connection is established once every S time slots. RTDM provides efficient multiprocessor
communications through either static [13] or dynamic [14] reconfiguration which reduces the multiplexing
degree K by establishing only those required connections. Note that, one can easily adapt K in a TMS
according to application requirements [13, 14], whereas in an optical TST, K is fixed by the architecture.
The proposed Path Multiplexing approach extends the principle of RTDM to establishing a connection in a
direct network consisting of TMS switches multiplexed with degree K.

Figure

7 illustrates the idea of the PM approach. Let us assume that a VP needs to be established along
links W;X and Y , and that switch ff can be set to interconnect link W with link X during time slot i
(0 K). Consider the case in which the propagation delay on link X is negligible when compared to
the duration of a time slot. Since any message carried on the connection will arrive at switch fi also during
time slot i, we have to be able to set switch fi so that link X is interconnected with link Y during time slot i.
(in the figure, this means i). Note that if the link propagation delay on X is not negligible (say, equal to
then the connection can be established only if during time slot
fi can be set so that link X is interconnected with link Y . In either case, the time slot to be used on link
Y (which is j) is dependent on the time slot used on link X (which is i). In general, when using the PM
approach, the time slots on the links along a path are selected in such a way that packets can flow through
the links without being buffered as no time slot interchanging is required.
3.3 Network Control
In this section, we describe how a connection can be established, assuming that a physical path has
already been chosen. We assume that in addition to the data network, which uses time-multiplexed optical
interconnects, there is a control network which is used to exchange control information needed to establish
virtual (and physical) paths. Although the control network may have a physical topology different from
the data network, we will assume that the same physical topology is used to interconnect routers (or
communication co-processors) that are attached to the switches. As will be discussed next, the amount
of bandwidth required for exchanging control information is relatively low compared to that required for
exchanging data. For example, the address of a node in a system having 1,024 nodes is only 10-bit long.
A control packet may thus be about 20 to 30 bit long, which is about one-tenth of a data packet (assumed
to contain 256 bits). Thus, the control network may operate at a bit-rate that is much lower than the data
network, which makes it feasible to implement the control network in electronics.
Many techniques developed for establishing a PP in a direct network can be applied to establish a VP.
One way to reserve/release a PP in a hypercube was described in [30]. A way to reserve/release a connection
(including a PP and a VP according to the RTDM paradigm) in MINs was described in [13]. Although
there are many variations as how a VP can be established, we will concentrate only on a basic scheme under
distributed control in the following discussions. In particular, we will describe a scheme for PM as the case
for LM is similar.
Let the set of available time slots on a link L be maintained in a list denoted by Avail(L). This list can
be implemented as a K-bit string, where K is the number of time slots in a frame. In addition, there are
two lookup tables called the PP-table and the VP-table, which store information about the links that form a
PP and the time slots that are assigned to a VP, respectively. These information are distributed among the
routers. Specifically, each router has access to the Avail(L) lists of all the outgoing links of the switch it is
attached to. It also has access to the part of the PP-table which specifies which of these outgoing links to
use for a given PP, and the part of the V P -table which specifies which time slot on a particular outgoing
link has been assigned to a given V P .
Control information can be exchanged among the routers in the forms of packets for reserving and
releasing V P s as follows. A source constructs a reservation packet Res V P , buffers a copy of the request,
sends the request to its local router and waits for an acknowledgement (either positive or negative). The
Res V P packet specifies the source and destination addresses or simply the ID of a PP. It also contains a
list of time slots, denoted by Init (also implemented as a K-bit string), during which the processor wishes
to transmit.
Upon receiving the Res V P packet, a router identifies the outgoing link L based on its PP table. The
router then performs the following "set-intersection" operation
(implemented with
a bit-wise AND operation), which updates the list in the packet. If the resulting Init list is not empty, then a
part of the Avail(L) list, which includes the set of time slots in Init, will be "locked" to prevent them from
being used by other V P s. The Res V P packet is then forwarded to the next router along the PP until the
destination is reached.
When Res V P reaches its destination, a time slot from its Init list, denoted by ts, is selected by the
destination processor, which constructs an Ack V P packet containing ts. The Ack V P packet is then
sent back to the source processor in the direction opposite to the one taken by Res V P . Upon receiving
each router "unlocks" the part of Avail(L) list previously "locked" by Res V P . Time slot ts is
deleted from that part (and from Avail(L)) and assigned to the V P . The router also sets the switch it is
attached to so that data carried on the V P will be switched to time slot ts on link L. Finally, Ack V P is
sent to another router until the source is reached.
Upon receiving Ack V P , the source can start message transfer at the beginning of the next transmitting
time slot, which may or may not be during the current frame. If a message is divided into m data packets,
then the message transfer will be completed after m frames since one data packet is sent in a time slot
during each frame. Upon the completion of the message transfer, the source constructs a Rel V P packet,
and sends it to the destination. The time slot assigned to the V P can then be released.
If the resulting Init list in a Res V P packet becomes empty at an intermediate router after the "set-
intersection" operation, the router will drop Res V P , and construct an Nack V P packet. The Nack V P
packet will be sent to the source in a way similar to that an Ack V P is sent. The difference is that this time,
only the "unlock" operation will be performed at each router. After the source receives Nack V P , it may
send a copy of the Res V P packet at a later time.
We note that signaling can be done in LM in a similar way, except that there is no need to maintain the
Init list or perform the "set-intersection" operation. A Res V P packet will "lock" an arbitrary time slot
from the Avail(L) list at each intermediate router. These locked time slots will be "unlocked" by either
an Nack V P or an Ack V P packet, as in PM. In the latter case, the time slots previously locked are then
assigned to the V P .
We also note that when the control network operates at 100 Mbs, which is one-tenth of the bit-rate of the
data network we have assumed (i.e. 1Gbs), the time needed to transmit a control packet is a few hundreds
of nanoseconds, which is about one time slot. Assuming that processing a control packet at a router also
takes a few hundreds of nanoseconds, then the time for a control packet to go from one router to the next is
about slots. The maximal time a source has to wait before it receives an acknowledgement is about
time slots, where H is the number of hops between the source and destination. This amount of time is
a modest overhead when compared to the time for a message to be received by the destination.
Comparing PM with LM
Since TST switches have higher control and hardware complexity than TMS switches, it is more expensive
to adopt the LM approach than the proposed PM approach, especially if the former uses electronic TSTs. In
addition, when it comes to choosing an appropriate multiplexing degree for an application, the PM approach
is much more flexible than the LM approach especially if the latter uses optical TSTs. Complexity and
flexibility aside, what we will focus on in this comparative study, is the performance of these two approaches
in terms of the communication latency they will introduce. As mentioned earlier, it may take longer to
be able to establish a VP in PM than in LM because a request that has to reserve the same time slot on
different links (as in PM) is more likely to be blocked than a request that can reserve possibly different time
slots (as in LM). On the other hand, since the TMSs used in PM do not introduce delays for buffering and
interchanging time slots, data can flow through the network with less delay in PM than in LM, once a VP
is established. Hence, the overall communication latency in the PM approach may be smaller than that in
the LM approach. In the next three subsections, we first examine the components of the communication
latency, and then compare the PM and the LM approaches via analysis and simulations.
4.1 Communication Latency
In circuit-switching, the communication time includes both message-transmission time and communication
latency. If a message is divided into m packets, then the time required for transmitting the message into
the network is Km time slots in either LM or PM, as described in Section 3.3. For a large message size
(i.e. a large m), the bandwidth, not the latency of the network is important. On the other hand, for a small
message size, the latency becomes more important. It is well known that optical interconnects are suitable
for high-bandwidth communications, that is, when the message size is large. One of our focuses in this
paper is to study ways to reduce latency in optically interconnected systems where the message size is small
(say between 512 bits and 2048 bits, or 2 - m - 8). Since the message-transmission time is the same in
LM and PM, it will not be considered in this comparative study of LM and PM.
The communication latency is the sum of two component values: circuit-establishment latency, LE
and network-propagation latency, LN . The former includes blocking time, denoted by LB , and signaling
overhead. The blocking time is largely due to the intervals between the time a request fails and the time
the failed request is resubmitted. Specifically, it is the duration of the period from the time a connection
request is first generated by a source till the time the first packet can be sent over the established connection,
excluding the signaling overhead, which is the amount of time to exchange control information. Since the
signaling overhead depends on many factors such as the network topology and the control scheme used (e.g.
either centralized or distributed), it will not be considered in this comparative study of LM and PM. In other
words, we will use LB in place of LE .
The second component of the communication latency, LN , is the time for a signal to traverse an
established path from a source to a destination. Like the circuit-establishment latency, LN is further
composed of two parts: link propagation latency and switching latency. The first part is the time for an
optical signal to traverse the external links along a path. Since in a reasonable network topology, even the
longest path has less than a few tens of hops, and since an optical signal can traverse each hop in much less
than a nanosecond in a multiprocessor system, the link propagation latency is often negligible relative to
the duration of a time slot (a few hundreds of nanoseconds as discussed in Section 2).
The second part of LN , the switching latency, is the time for a message to go through the switches along
a path. If PM is used, then this part is also negligible since an optical signal traverses a switch in the optical
domain without being buffered. Accordingly, LN can be ignored if PM is used. However, as discussed
in Sec. 3.1, a TST switch capable of interchanging time slots introduces a delay because a signal has to
be buffered in either the optical or the electronic domains, which could vary from 0 to
depending on the implementation of the TSTs as well as on how the time slots need to be interchanged.
For simplicity, we assume that each incoming time slot will be delayed, on average, by K time slots when
going through a TST. Assuming that the distance between a source and a destination is H hops, the total
switching latency along the path, excluding the source or destination points, is K. Accordingly,
if LM is used, LN , which is about can no longer be ignored.
To summarize, if we let the average blocking time in PM and LM be LB (PM) and LB (LM) respectively,
and we denote the communication latency in the two approaches by L(PM) and L(LM), respectively, we
have
Throughout our comparative study of the LM and PM approaches, we will focus on the value of L(PM)
as defined in Eq. 1 and the improvement ratio, I , which is defined as follow :
L(LM) \Theta 100% (3)
Hence, I will be at most 100% when The larger I is, the better PM becomes when
compared to LM. For example, I = 50% means that means that
Our comparative study involves two parts: analytical work and simulation. In both cases, a direct
network whose links are time-multiplexed with degree K is studied and the communication latency resulted
from LM and PM is evaluated. Common assumptions to both the analysis and simulation that simplify our
evaluation processes are made. These assumptions are
1. a predetermined shortest path is used to establish a given connection (even though alternate paths
may exist).
2. each PE has a request buffer of size b. During each time slot, if the buffer is not full, then the PE
generates, with probability r, a new request to transmit a message of average length of m packets,
1. Thus, the message (request) generation rate is r, and the traffic (packet) rate is r
3. a copy of the rejected request is resubmitted after t time slots, where t is a multiple of the frame
duration, K. Note that our previous study in [14] has shown that normalized service time (NST) [31]
is minimized when K is around 3 to 5. Hence, we will focus on the results obtained with a small K.
4. the destination of each message is randomly chosen among all the processors.
We will elaborate on these assumption as we go along.
4.2 Probability Analysis
In this section, we study the probability that a requested connection can be established using either PM or
LM when the network is in a steady-state. This probability will then be used to calculate LB . We consider
an N \Theta N torus in which each switch has four pairs of external links, and the average length of a connection
in terms of number of hops is about N=2.
We will first consider the case in which there is no time-multiplexing. In order to facilitate our analysis,
we assume that the traffic is evenly distributed in the network. Hence, the traffic at all switches is statistically
identical. Moreover, at each switch, the traffic on the input (or output) links is also statistically identical.
We will use the model illustrated in Figure 8 to study the steady-state behavior of the network. We
denote by u the probability that a given time slot on any external link is occupied by a connection. In
addition, we denote by v the probability that a given time slot on the internal link from a PE to its switch
is occupied by a connection (originating from each PE). Then, the probability that a given time slot on the
other internal link (from the switch to the PE) is occupied by a connection (destined to each PE) is also v.
Let H be the average length of a connection (in terms of number of hops). Since the total number of
established connections is vN 2 , each occupying an average of H links, and there are 4N 2 links in a torus,
the probability that a given link is occupied is That is,
Alternatively, the above relationship between u and v can be derived by treating u and v as some fraction of
a connection carried on an external input link and an internal output link, respectively. Since the probability
that a given connection will terminate at any switch is 1=H , we have
We will use the notation P [H; K] (the success probability) or P [H; K] (the failure probability which
to denote the probability that a given connection can or cannot be established between
a source and a destination H hops away when the multiplexing degree is K. In a trivial case where
(which is equivalent to having no time-multiplexing), the LM and the proposed PM approach are
not different and will result in the same P [H; 1]. More specifically, since a connection can be established
only if all the H external links along the path are available, we have
When the multiplexing degree K ? 1, PM and LM approaches will result in different success proba-
bilities. Consider first the case in which PM is used. We may begin with the probability that none of the K
time slots is available on all the H links. Based on Eq. 5, this probability is
Since a connection can be established as long as there is one out of K time slots such that the same time
slot is available along all the H links, we have
We now consider the case in which LM is used. For a given link, the probability that none of the K
time slots is available is u K , thus the probability that at least one time slot is available on that given link is
a connection can be established as long as on each of the H links along the path, one of the
time slots is available, we have
To simplify our analysis, we assume that the effective packet generation rate r 0 is independent of time.
Since P (which is either P PM or PLM ) is the success probability, and v is the probability that a connection
originated from a PE is established, we have
Since P is a function of u (see Eqs. 7 or 6), which in turn is related to v, we can combine Eq. 4 with
Eq. 6 to get the following equation for PM,
Similarly, by combining Eq. 4 with Eq. 7, we get the following equation for LM,
Given H , K and r 0 , we can solve Eq. 9 using the Secant method, for example, to obtain the steady-state
value of u for PM. Similarly, we can obtain the steady-state value of u for LM by solving Eq. 10.
In

Figure

9, we plot the solutions to Eqs. 9 and 10 for specific H , K and r 0 . As expected, the value
of u increases with r 0 . The fact that for a given r 0 , the value of u increases with K is consistent with
previous results which show that, in general, multiplexing can improve both bandwidth utilization and
network throughput [15, 16, 14]. Our results have also shown that for a given r 0 and K, u decreases with
H . This is due to the fact that a longer path has a smaller chance of being established successfully.
After we obtain u, the success probability P can be obtained using Eqs. 6 and 7 for PM and LM,
respectively. Figure 10 shows the steady-state success probability when r similar to u,
increases with K and decreases with H .
Having obtained the success probability P for either PM or LM, we can now determine the blocking time
in the two approaches. If a request is satisfied the first time it is submitted, which occurs with probability P ,
the first packet can be sent after K=2 time slots on average. If t is the resubmission interval after each failure,
then the connection will experience a latency (due to blocking) of (t
latency of (2t Therefore,
which results in
Therefore, we may calculate the blocking time LB (PM) and LB (LM) by substituting P PM and PLM
for P in the above equation. As a result, we can determine the communication latency L(PM) and L(LM)
according to Eq. 1 and Eq. 2, respectively, as follows:
Finally, we can determine the improvement ratio I according to Eq. 3.
Assuming that r respectively, Table 1 shows some of the results
obtained through the above probability analysis. From Table 1, one can see that in all cases, PM results in
reduced communication latency when compared to LM. Note that since a larger t means a larger penalty for
PM, the improvement ratio decreases with t. In addition, since the success probability of both PM and LM
decreases with H exponentially, and the switching latency of LM alone increases with H linearly, H can
affect the improvement ratios in both positive and negative ways. Our studies have found that in almost all
the cases, I decreases with H as the negative effect dominates. These results are verified by our simulations,
as will be discussed in the next subsection.
L(PM) 2.88 7.80 14.53 22.64 3.76 13.60 27.07 43.29
L(LM) 6.37 16.75 27.82 39.12 6.75 19.51 33.64 48.25
I 54.8% 53.4% 47.7% 42.1% 44.3% 30.2% 19.5% 10.3%

Table

1: Analytic results of connection latency and improvement ratio
4.3 Simulation Study
In order to keep the above analysis simple, we have assumed that the probability of establishing a connection
does not depend on the message length, nor on the message buffer size. In addition, the analysis assumes a
node-symmetric network such as a torus. As a complementary part of our comparative study, simulations
have also been conducted to evaluate the LM and PM approaches in a two dimensional N \Theta N mesh.
The simulation program is written in C using the libraries from the YACSIM [32]. Statistical measures
on the connection latency resulted from PM and LM are collected with a confidence level no less than 90%
and a confidence interval no larger than 0.1. In addition, average distances in hops between a source and a
destination of all the connections established are also collected. These are used for the average values of H
in Eq. 2, which, together with the multiplexing degree K, can be used to determine L(LM) and therefore
the improvement ratio I . For example, we have simulated meshes with different sizes found that the average
value of H in an N \Theta N network is about 0:66N , which is consistent with the analytical result obtained
with the following equation:
The simulation results presented in Figures 11 through 15 are obtained by limiting the message rate r
not to exceed a certain point, beyond which the network will be saturated as indicated by a steady or even
decreasing network throughput. In practice, the actual traffic applied to the network would (and should) not
exceed the saturation point. Our simulation results have indicated that within the range of parameter values
we considered, the PM approach will always result in lower communication latency than the LM approach.
In

Figure

11, both improvement ratio I and communication latency in PM, L(PM), are shown. These
results are obtained using the following parameter values: the network size 100 (N = 10); the multiplexing
degree each message contains packets and each
processor has a message buffer of size 2. Our simulation results indicated that the network is near
saturation when message rate r reaches 0.3. At this point, the improvement ratio and communication
latency in PM approach 60% and 13 time slots, respectively. At a low message rate (e.g.
the improvement ratio is almost 100%. This occurs because at a low message rate, L(PM) is near 0
while L(LM) is dominated by the switching latency, which is about 22 time slots. We also observe that
the improvement ratio decreases with message rate. This is because while the difference in the network
propagation delay LN between PM and LM remains almost constant (e.g. 22 time slots), the difference in
the success probability between PM and LM increases with the network traffic load. Hence, the difference
in the blocking time LB between the two approaches increases with the network traffic load.
In

Figure

12, the effect of the buffer size, b, on both the improvement ratio and the communication
latency in PM is shown. It can be seen that in all cases, the improvement ratio is above 50%, although for a
given message rate, the improvement ratio decreases with b. This is consistent with the previous observation
because a larger value of b translates into a heavier traffic load for the same message rate.

Figure

13 shows that although the improvement ratio decreases with t, it is about 70% at
for the case This is due to the fact that one-time failure probability in establishing a connection is
higher in PM than in LM (see Eqs. 8 and and thus, a larger t penalizes PM more than LM. Put differently,
a larger t magnifies the disadvantage of PM relative to LM when establishing a connection (see Eq. 12).

Figure

14 shows that the improvement ratio increases with K. When is the same as
L(LM), resulting in I = 0 (the horizontal line). Our simulation results have indicated that the network
can tolerate a heavier traffic load with a larger K. In this regard, a larger K helps PM as much as LM in
reducing the blocking time LB . However, a larger K means a larger switching latency and hence a larger
communication latency in LM. The result is a larger improvement ratio I .
In order to investigate the effect of network size independently of the effect of traffic load, we compare
L(PM) and L(LM) when the per-link load is the same for different values of N 2 . One way to fix the
per-link load is to use an r so that the average number of messages generated in a network is R \Delta N for some
R. Specifically, because each message travels an average distance on the order of N from its source to its
destination, and the number of links in the network is of order N 2 , then per link load is fixed if the total
number of messages in the network is proportional to N . Note that, since there are N 2 PEs, each PE will
generate a request with probability
Our simulation results have indicated that although the absolute value of the communication latency
in both PM and LM increases with N 2 , their difference also increases due to the increase in the average
distance between a source and a destination H , which is linear in N . Therefore, as can be seen from

Figure

15, with a given value of R, the improvement ratio in networks of different sizes is about the same.
It is worth noting that because of the finite buffer size b, having the same R in networks of different sizes
can not guarantee that the actual load is also the same.
Finally, in order to investigate the effect of message length m independently of the traffic load, we
obtain the improvement ratio resulted from the same r 0 but with different m and r. In addition, we have
also set the buffer size b so that the same number of packets (instead of messages) can be buffered. As
can be seen from the results shown in Figure 16, the improvement ratio increases slightly with m. This is
because a larger m means that each connection is kept longer and a fewer connections need to be established
to transfer the same number of packets. As a result, the negative effect of the blocking time of PM on the
overall communication latency decreases. Therefore, PM gains more advantages over LM as m, which
is proportional to the temporal locality in the communication, increases. Note that if the message size is
large, then the message transmission time may dominate the communication time (see Section 4), making
the reduction in the communication latency achieved in PM less important. However, in distributed shared-memory
systems, message transfers are triggered by memory references, and the message size is usually
small. In addition, since software latency in these message transfers is low, reducing hardware latency such
as LB and LN via the use of PM becomes important.
To summarize, our comparative study have shown that PM is effective in reducing the communication
latency in a wide range of practical situations. More specifically, as long as a network is not saturated with
heavy traffic, an improvement ratio of at least 10% can be obtained. In particular, the improvement ratio
increases with multiplexing degree and the temporal locality of communications (which is proportional to
the message length), and scales with the network size. We note that in our simulation, uniform message
routing (i.e. random destinations) is assumed. In many applications, spatial locality exists in communication
patterns. For example, a processor may send a message to the processors within certain distance (i.e. number
of hops) with a higher probability than to the other processors [33]. The effect of such non-uniform message
routing on the latency reduction achievable in PM needs to be investigated further.
Concluding Remarks
With the high bandwidth available in optics, it becomes increasingly important to reduce the communication
latency which ultimately limits the performance of the multiprocessor systems that utilize optical
interconnects. In this paper, we have proposed the Path Multiplexing (PM) approach as an alternative to the
conventional Link Multiplexing (LM) approach for establishing connections in TDM networks. We have
studied the issues related to the implementation of both approaches and compared the two in terms of the
resulting communication latency through analysis and simulations.
The conventional LM approach uses switches that are capable of interchanging time slots while the PM
approach does not. Although the LM approach may result in shorter blocking time due to its flexibility
in selecting time slots for establishing a connection, we have found that the proposed PM approach can
reduce the overall communication latency because it eliminates the delay caused by interchanging time
slots. The results we have obtained on blocking probabilities of the two approaches in the TDM networks
agree in principle with those of the two analogous approaches in the WDM networks [34-36], although in
the latter, communication latency issues are quite different as interchanging wavelength incurs little or no
delays. We note that, aside from the issue of communication latency, the hardware and control complexity
of a network using Time-Slot-Interchangers (TSIs) is higher than that using Time-Multiplexed Switches
(TMS). In particular, networks using electronic TSIs are not transparent to data rate and format, and those
using optical TSIs will have a fixed multiplexing degree and thus are incapable of adapting to different
applications for which certain multiplexing degree yields optimal results [13, 14].
In a related work, we have found that PM can be nearly as effective as LM in realizing permutations in a
class of networks including linear arrays, rings, meshes/tori and hypercubes [37]. Further studies focusing
on the cost-effectiveness of LM and PM on the network's capability of establishing random connections,
and supporting general static or compiled communications are underway.

Acknowledgement

The authors would like to acknowledge the partial support from National Science Foundation under contract
number MIP-9409864 and from the Air Force Office of Scientific Research under contract number AFOSR-
89-0469, respectively. The authors would also like to thank the anonymous reviewers for their valuable
comments which helped improve the quality of this paper.



--R

"Comparison between optical and electrical interconnects based on power and speed considerations,"
"Optical interconnections for VLSI systems,"
"Optical interconnects for multiprocessors: cost performance analysis,"
"Optical interconnects in the Touchstone supercomputer program,"
"Optical interconnects for interprocessor communications in the Connection Machine,"
"Deadlock-free message routing in multiprocessor interconnection networks,"
"High performance communications in processor networks,"
"A survey of wormhole routing techniques in direct networks,"
"Array processors with pipelined optical busses,"
"Time multiplexed optical computers,"
"Space multiplexing of waveguides in optically interconnected multiprocessor systems,"
"Time-division optical communications in multiprocessor arrays,"
"Reconfiguration with time-division multiplexed MINs for multiprocessor communications,"
"Dynamic reconfiguration of optically interconnected networks with time division multiplexing,"
"Hierarchical scalable photonic architectures for high performance processor interconnection,"
"A time-wavelength assignment algorithm for a WDM star network,"
"New architectures for optical TDM switching,"
"Serial time slot interchangers and optical implementations,"
"Architectures with improved signal-to-noise ratio in photonic systems with fiber-loop delay lines,"
"Towards high communication performance through compiled communications on a circuit switched interconnection network,"
"Architectural requirements of parallel scientific applications with explicit communication,"
"Gigabit SCI cluster interfaces,"
"Memory channel network for PCI,"
"A new, supercomputer-class system interconnect,"
"Implementation of optical clock distribution in a supercomputer."
Introduction to parallel algorithms and architectures: arrays
"Serial array shuffle-exchange architecture for universal permutation of time slots,"
"A conflict-free memory design for multiprocessor,"
"Experimental modular switching system with a time-multiplexed photonic center stage,"
"The iPSC/2 direct-connect communications technology,"
"Performance analysis of multistage interconnection network configurations and operations,"
version 2.1.

"Lightpath communications: an approach to high-bandwidth optical WANs,"
"A wavelength-convertible optical network,"
"Optimal routing and wavelength assignment in all-optical networks,"
"On the multiplexing degree required to embed permutations in a class of inter-connection networks,"
--TR

--CTR
Praveen Jayachandran , Praveen Bhamidipati , C. Siva Ram Murthy, On providing elastic QoS in optical burst switched networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.4, p.1121-1132, March, 2007
Xin Yuan , Rami Melhem , Rajiv Gupta, Algorithms for Supporting Compiled Communication, IEEE Transactions on Parallel and Distributed Systems, v.14 n.2, p.107-118, February
Xijun Zhang , Chunming Qiao, On scheduling all-to-all personalized connections and cost-effective designs in WDM rings, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.435-445, June 1999
Chunming Qiao , Yousong Mei, Off-line permutation embedding and scheduling in multiplexed optical networks with regular topologies, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.241-250, April 1999
Constantine Katsinis , Bahram Nabet, A Scalable Interconnection Network Architecture for Petaflops Computing, The Journal of Supercomputing, v.27 n.2, p.103-128, February 2004
time division multiplexing;fiber-optical interconnects;communication latency;switching networks;time slot interchangers