Cs.uku.fi

Report A/2003/3
Department of Computer Science and Applied Mathematics Abstract. In this paper we present an all-optical network architecture and a systolic
routing protocol for it. The   -dimensional optical butterfly ( of  ✞✝✠✟ nodes and  ✡✝☛✟✌☞✎✍ edges. Processors are deployed at the level 0 (identical to level   ) nodes of the network. Routing is based on the use of a cyclic control bit sequence and scheduling. The systolic routing protocol ensures that no electro- optical conversion is needed in the intermediate routing nodes and all the packets injected into the routing machinery will reach their target without collisions. A work- optimal routing of an -relation is achieved with a reasonable size of ✏✒✑✔✓✖✕✘✗✖✙✛✚✡✜✢✗✎✣ Introduction
Optics offers a possibility to increase the bandwidth of intercommunication networks.
Optical communication offers several advantages in comparison with its electronic coun- terpart, for example, a possibility to use broader bandwidth and insensitivity to external interferences. These advantages have been covered, e.g., by Saleh and Teich in their book Our work is motivated by another kind of communication problem, namely the em- ulation of shared memory with distributed memory modules [6]. If a parallel computation has enough parallel slackness, the implementation of shared memory can be reduced to -relation is a routing problem where each packets to send and it is the target of at most -relation is said to be work-optimal at cost , if all the packets . A precondition for work-optimality is that is the diameter of the network, and that the network can move is the number of processors. Otherwise slackness cannot be used to "hide" latency influenced by the diameter [6]. For an -dimensional optical but- Butterfly networks are widely used in intercommunication machineries. There are several reasons to the popularity of butterfly networks. Firstly, they have a simple recur- sive structure. Secondly, in an -dimensional butterfly any input [7]. Most of implementations of butterfly based networks use packet switching as the routing strategy [7, 9, 13]. A drawback of packet switching is that routing decisions must be done in electronic form. Liu and Gu have presented an all-optical implementation based on wavelength-division multiplexing (WDM) [8]. An advantage of their implementation is that electro-optic conversions are avoided. A disad- vantage is that a number of wavelengths and wavelength converters are needed to realize In this work we present an all-optical network architecture and a systolic routing pro- tocol for it. The -dimensional optical butterfly network consists of edges. Processors are deployed at the level 0 nodes of the network. Routing nodes are connected to each other by optical links. In this paper we present a novel packet routing protocol, called the systolic routing protocol. Additionally, when a packet is injected into the routing machinery, neither electro-optic conversions are needed during its path from source to target processor nor any collisions may happen between two distinct packets.
✦✢✜✒✪✍ ✏✎✒✑✔✓✣  2 presents the internal structure of routing nodes and the structure of an In Section 3 we introduce the systolic routing protocol. Section 4 presents the analysis of our construction. Section 5 sketches conclusions and future work.
Optical Butterfly with Systolic Routers
We study on the -dimensional structure of processing nodes. We represent the structure of routing nodes in Section 2.1. Section 2.2 . Section 2.3 discusses the feasibility of our construc- Systolic Routers for  ✂✁☎✄
has two incoming and two outgoing links. A routing node can be in two states. When a routing node routes incoming packets from input links ✆  ✞✝✠✟ respectively, it is said to be in the invert state and when it routes incoming signals from input links respectively, it is said to be in the push state. The two possible states of routing nodes are presented in Figure 1.
Figure 1: Two possible states of routing nodes.
The basic component of routing nodes is the electrically controlled all-optical 2 2 switch. Switches can be implemented by LiNbO technology [12]. The construction of routing nodes ensures that signals never collide and routing of the packets works correctly if we can arrange a situation that both incoming packets never prefer the same output link.
We will show that this kind of situation is arrangeable.
Construction of Optical Butterfly
denoting the row number of the node. Levels are connected by an edge (optical link) if and only if differ in precisely the th bit (cross edges).
sented in Figure 2. In Figure 2, a circle indicates a processing node, a rounded square relabeling of processing nodes and levels.
indicates a routing node, and an arrow between two nodes indicates a link between the nodes. Two attachable subnetworks are called blocks of the network. Straight edges are ’th level input (in the same block), and cross edges are always connected from the Our construction has two characteristics. Firstly, straight edges are always lead- ing to the same block and cross edges are always leading to the adjacent block of the (sub)butterfly. Secondly, treatment of packets can be arranged uniformly at each router of the network because of uniform connections between routers.
are considered identical processing nodes. A useful prop- erty of the -dimensional butterfly is that for any source/destination processing node pairs the packets can be routed by a unique path of length .
Feasibility of
as a Systolic Router
The switching time of LiNbO switches lies in the range of 10–15 ps [12]. The length of is the link bandwidth. Assuming the bandwidth to be In order to estimate the feasibility of a 6-dimensional nodes) let us assume the link bandwidth to be b. The corresponding length of a packet in a fiber is ns. Assuming the length of clock cycle of processing nodes ns (corresponding the frequency of 1 GHz), it will take 1.3 clock cycles for a packet to travel between two adjacent routing nodes. The overall amount of fibers is consider the requested parameters to be reasonable and the architecture to be feasible to Routing in Optical Butterfly
We have developed a routing algorithm for . In Section 3.1 we present properties of routing information and transitions between blocks. Section 3.2 introduces preprocessing phase. Preprocessing phase consists of determining of the control sequence and deter- mining the routing table that will control the routing. Section 3.3 introduces the routing algorithm for the optical butterfly.
Properties of Routing
Determining the Routing Information.
) be a bit sequence indicating the edges used by a packet on its path from the source to the target in an -dimensional the packet should be routed from router on level using a cross edge leading to the adjacent block. Correspondingly, if the packet should be routed from router on level leading to the same block. Clearly, we can construct an -ary routing bit sequence for any source/destination pair so that it leads correctly the packet through the notice this, let us assume that in a bit sequence the edge leading to the wrong subnetwork. We just substitute the initial bit sequence by The routing information for packets can be evaluated by the bitwise XOR-operation Figure 3: Example of transitions between blocks.
must be routed from the sender to the first level router using a cross edge, from the first level router to the second level router using a straight edge, and from the second level router to the destination using a straight edge.
Determining Transitions Between Blocks.
levels of routers. According to the recursive contruction and our definition every routing node at level by two outgoing links. Additionally it is a target of two incoming links from two subnetworks (blocks) whose dimension is at level 1 that are targets of processors. Figure 3 clarifies the idea of blocks.
Routers can be considered to be an interface between blocks. Let us assume that a ’th and ’th bit positions of routing information. The router responsible to route this packet (at the ’th level) receives the packet from adjacent input and it should route the packet to the same block of the According to our construction the router should be in the invert state. Correspondence between two-bit routing information, transitions between blocks, and required state of Because all the routers have two incoming and two outgoing links, each router can Table 1: Correspondence between two-bit routing information, transitions betweenblocks, and required state of router.
route two packets at the same time, if the packets do not prefer the same outgoing link.
According to Table 1 this is fulfilled if the incoming packets have either 00 and 11 or 01 ’th and ’th bit position of routing information when they reach a router at level . Clearly we can see that using these two states it is possible to route any combination of transitions between blocks. Precondition of correct routing is that arrival of packets and the state of router are synchronized correctly.
The transition information for packets can be evaluated by the bitwise XOR- denote the routing information of a packet from processor to determine a unique transition bit sequence Initialization Phase
In our contruction injected packets have no routing information. When a packet arrives a routing node it is routed into an adjacent or the same block according to the state of the router. Anyway we are able to arrange a control system so that every packet injected reaches its target. We will use a cyclic control bit sequence and timing of Determining the Control Sequence.
levels of routing nodes. Packet routing in an - can be implemented by constructing a long control bit sequence the state corresponding to the value of bit position , and synchronizing injections of packets so that they reach every routing node in the correct state. Precondition of all-to-all routing is that the bit sequence includes (cyclically) all bit sequences of would be to construct the control bit sequence of all -ary bit combinations. The length of bits appears once, including wraparound [7].
our purpose. All sixteen 4-bit sequences occur exactly once as subsequence of ✟ .
Fredricksen has presented an algorithm to construct a de Bruijn sequence [2]. The algorithm is Prefer one and it can be presented as follows: Algorithm Prefer one
if the newly formed -tuple has not previously
appeared in the sequence then ✙✌☞ ✟
if the newly formed -tuple has not previously appeared
in the sequence then
else stop;
all the routers are set in push state if ✟ length of de Bruijn sequence, and in invert states otherwise. Determining of the control sequence is necessary to do only once at the initialization phase of the Determining the Routing Table.
The optical butterfly has a number of properties. Firstly, structure of routers and connec- tions between them are uniform. Secondly, it is possible to determine a unique routing bit sequence for any packet from a source Thirdly, determination of unique transitions between blocks is possible as well because of and uniqueness of the routing bit sequences.
is controlled by the static control bit sequence ✟ . For these reasons we are able to determine a routing table for every connection at the initialization phase.
tion the length of routing bit sequence is , the length of transition bit sequence is , and the length of the control sequence is is routed correctly if it is injected at time step into output link ing to the same block and during the next . At the same time the sending processor can inject another packet . For these two packets destined to processors At the initialization phase every processor denote the value of ’th row of the routing table. The algorithm determining routing table is Routing table and it can be presented as follows: Algorithm Routing table
Algorithm Routing table is necessary to execute only once at the initialization phase Routing Algorithm for the Optical Butterfly
At the initialization phase each processor determines the control sequence and the routing table. This must be done when the system is set up. At the beginning of routing each has a number of packets to send. In the preprocessing phase each )’th position in the routing table. The packet is injected into the outgoing link sending buffer ✄ ✜ is picked up as well and injected into the outgoing link Analysis of Systolic Routing
ing buffers according to their target. Clearly, all of the packets have been routed after time is the maximum size of all buffers. According to Mitzenmacher et al.
bins with each ball choosing a bin indepen- dently and uniformly at random, then the maximum load is approximately ✎✒✑✔✓✣ ✂✁✣✎ ✑✔✓✣✎✒✑✙✓✞  with high probability1. Maximum load means the largest number of balls in any bin. Cor- step, then the maximum load of sending buffers is approximately The overall routing time of those packets is optimal according to the definition of work-optimality.
. A work-optimal result is achieved according to the definition implies work-optimality. We ran some experiments to get an idea about the cost. We ran 5 simulation rounds for each occurrence using a visualizator programmed with Java [4]. Packets were randomly put into output buffers and the average value of the routing time over all the 5 simulation rounds were evaluated.
The average cost was evaluated using equation time. Figure 4 gives support to the idea that does not need to be extremely high to get a Conclusions and Future Work
We have presented a systolic routing protocol for optical butterfly. No electro-optical conversion is needed during the transfer and all the packets injected into the routing ma- chinery are guaranteed to reach their destination. The simple structure presented and the systolic routing protocol are useful and realistic and offer work-optimal routing of An advantage of our construction is that the overall number of links is Honkanen presented the systolic routing protocol for Sparse Optical Torus ( 1We use whp, with high probability to mean with probability at least ✏✒✑✔✓✖✕✗✏✙✘✛✚✢✜✤✣ Figure 4: Routing costs, when the size of -relation varies. (1) However, a drawback arise, when the systems are scaled up. Putting in the physical space requires at least a volume of size wires between routing nodes increase with respect to the physical space required.
References
[1] Adler, M., Byers, J.W., Karp, R.M.: Scheduling Parallel Communication: The relation Problem. Proceedings of Mathematical Foundations of Computer Science (MFCS). Prague Czech Republic (1995) 1–20.
[2] Fredricksen, H.: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms.
SIAM Review 24,2 (1982) 195–221.
[3] Golomb, S.W.: Shift Register Sequences. Aegean Park Press, Laguna Hills California network. Special project, University of Kuo- pio, Kuopio. URL: http://www.cs.uku.fi/ rthonkan/OBF/ (March 30, 2005).
[5] Honkanen, R.T.: Systolic Routing in Sparse Optical Torus. Proceedings of the 8th Symposium on Programming Languages and Programming Tools (SPLST’03). Kuopio [6] Honkanen, R., Leppänen, V., Penttonen M.: Hot-Potato routing Algorithms for Sparse Optical Torus. Proceedings of the 2001 ICPP Workshops. Valencia Spain (2001) [7] Leighton, F.T.: Introduction to parallel algorithms and architectures: arrays, trees, hypercubes. Morgan Kaufmann Publishers Inc., California (1992).
[8] Liu, X., Gu, Q.-P.: Multicasts on WDM All-Optical Butterfly Networks. Journal of Information Science and Engineering 18 (2002) 1049–1058.
[9] Maggs, B.M., Sitaraman, R.K.: Simple Algorithms for Routing on Butterfly Net- works with Bounded Queues. SIAM J. Comput. 28,3 (1999) 984–1003.
[10] Mitzenmacher, M., Richa, A.W., Sitaraman, R.: The power of randomized choices: A survey of techniques and results. In: Handbook of Randomized Computing. Eds.
[11] Raab, M., Steger, A.: "Balls into Bins"—A Simple and Tight Analysis. Proceedings of 2nd Workshop on Randomize and Approximation Techniques in Computer Science (RANDOM’98). Barcelona Spain (1998) 159–170.
[12] Saleh, B.E.A., Teich, M.C.: Fundamentals of Photonics. John Wiley & Sons Inc., [13] Upfal, E., Felperin, S., Snir, M.: Randomized Routing with Shorter Paths. IEEE Transactions on Parallel and Distributed Systems 7,4 (1996) 356–362.
[14] Valiant L.G.: General Purpose Parallel Architectures. In Algorithms and Complex- ity. Handbook of Theoretical Computer Science vol. A. Elsevier and MIT press (1990) [15] Vitányi P.B.M., 1988: Locality, Communication, and Interconnect Length in Multi- computers. SIAM Journal of Computing 17,4 (1988) 659–672.
[16] Vitányi P.B.M., 1994: Multiprocessor Architectures and Physical Law. Proceedings of 2nd Workshop on Physics and Computation (PhysComp’94). Dallas Texas (1994)

Source: http://www.cs.uku.fi/research/publications/reports/A-2003-3.pdf