Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing
Reexamination Certificate
1999-09-20
2003-05-20
Rinehart, Mark H. (Department: 2783)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
C712S011000
Reexamination Certificate
active
06567858
ABSTRACT:
FIELD OF THE INVENTION
This application relates to the field of parallel computing and networking, and more specifically to all-to-all personalized exchange in multistage networks.
BACKGROUND OF THE INVENTION
Communication among processors may be a design issue when, for example, a parallel processing system is built, or a parallel procedure is designed. With advances in silicon and Ga—As technologies, processor speed may soon reach the gigahertz (GHz) range. Traditional metal-based communication technology used in parallel computing systems is becoming a potential bottleneck. Progress in the traditional interconnects, or to in the new interconnect technologies, such as optics, would be well received in the parallel computing systems community.
Advances in electro-optic technologies have made optical communication a promising networking choice to meet the increasing demands for high channel bandwidth and low communication latency of high-performance computing/communication applications. Fiber optic communications offer a combination of high bandwidth, low error probability, and gigabit transmission capacity. They have been extensively used in wide-area networks and have received much attention in the parallel processing community as well. In fact, many commercial, massively parallel computers, such as the Cray C90, use optical technology in their communication subsystems.
Using new optical technologies in parallel computers may require us to reexamine the design of interconnection networks, and use of parallel processing procedures. Exploring the capabilities of the optical technology may involve a careful analysis of the properties of optics, a proposal of new performance measures, a design of new interconnection networks and routing procedures, and new parallel processing application procedures.
Multistage interconnection networks (MINs), hereafter also referred to as multistage networks, have been used for interconnecting purposes in parallel computing systems. A MIN can be blocking, such as a Banyan network, rearrangeably non-blocking, such as a Benes network, non-blocking, such as crossbar. Additionally, a MIN may have variably connecting capabilities, from rearrangeable for permutation to non-blocking for multicast, such as in a Clos-network, depending on the number of stages, the number of switches, the switch capability, and the interconnection patterns used between stages.
As optical technology advances, there has been a growing interest in using optical technology for implementing interconnection networks and switches. Although electronic MINs and optical MINs have many similarities, here are some fundamental differences between them. Because of some unique properties of optics, traditional routing procedures and results may not be applicable here. New research addressing optical MINs may be useful.
In the communication pattern known as all-to-all personalized exchange, every processor in a processor group sends a distinct message to every other processor in the group. All-to-all personalized exchange occurs in many important parallel computing
etworking applications, such as matrix transposition and fast Fourier transform (FFT).
The issue of realizing all-to-all personalized exchange in optical multistage networks is examined below. A basic element of optical switching networks is a directional coupler with two inputs and two outputs (hereafter referred to simply as switches). Depending on the control voltage applied to it, an input optical signal is coupled to either of the two outputs, setting the switch to either the parallel or the crossing state. A class of topologies that can be used to construct optical networks is multistage interconnection networks (MINs), which interconnect their inputs and outputs via several stages of switches.
Advances in electro-optic technologies have made optical communication a promising networking choice to meet the increasing demands for high channel bandwidth and low communication latency of high-performance computing/communication applications. Although optical multistage networks hold great promise and have demonstrated advantages over their electronic counterpart, they also introduce new challenges such as how to deal with the unique problem of avoiding crosstalk in the optical switches, which may occur when two signal channels in a switch interact with each other.
There are two ways in which optical signals can interact in a planar switching network. The channels carrying the signals may cross each other in order to embed a particular topology. Alternatively, two paths sharing a switch may experience some undesired coupling from one path to another within a switch. It would be desirable to achieve optical exchange in multistage networks in a manner that reduces crosstalk.
SUMMARY OF THE INVENTION
Methods and systems are presented below involving optical multistage interconnection networks (MiNs). Although optical MINs hold great promise and have demonstrated advantages over their electronic counterparts, they also present their own problems. Due to certain optical properties, crosstalk in optical switches should be avoided if they are to work efficiently. The concept of a semi-permutation is introduced to analyze the permutation capability of optical MINs under the constraint of avoided crosstalk in several types of MINs. In particular, an optimal scheme for realizing crosstalk-free all-to-all personalized exchange in a class of unique-path, self-routing optical multistage networks is presented.
The basic idea of realizing all-to-all personalized exchange in such a multistage network is to transform it to a collection of the above-mentioned semi-permutations. Each of the semi-permutations can be realized crosstalk-free in a single pass (i.e., in a single, concurrent exchange of signals) and can take advantage of pipelined message transmission in consecutive passes.
More specifically, a method for crosstalk-free all-to-all exchange in an optical multistage network having inputs and outputs coupled to processors is presented. The method comprises sending messages between the processors in multiple passes, wherein, in each of the multiple passes, each of the processors transmits, in one-to-one fashion, a message to one of the processors by way of the inputs and outputs, in accord with semi-permutations decomposed from permutations corresponding to rows of a matrix. The optical multistage network may be one of a baseline network, omega network, Banyan network, and their reverse networks.
In each of the multiple passes, each of the processors may transmit, in one-to-one fashion, a message to one of the processors by way of the inputs and outputs, in accord with semi-permutations decomposed from permutations corresponding to rows of a Latin square. The semi-permutations may be obtained by computing two input sets.
A method is also presented for crosstalk-free all-to-all exchange in an optical multistage network having n inputs and n outputs coupled to n processors, where n &egr;{2, 4, 8, 16, . . . } and wherein each of the n processors is connected to one of the n inputs and one of the n outputs, comprising computing a Latin square having n rows and n columns; associating the n rows with n admissible permutations, each of the n admissible permutations being a one-to-one mapping from N={0,1, . . . ,n−1} to itself; for j a member of the set {1, 2, . . . , n}, decomposing a jth permutation, from among the n admissible permutations, into two semi-permutations, one of the two semi-permutations, s
(j)
, being a restriction of said mapping to a subset, S
(j)
, of N having n/2 elements, and another of the two semi-permutations, t
(j)
, being a restriction of said mapping to a subset, T
(j)
, of N where T
(j)
is a complement N\S
(j)
; sending n/2 messages in a (2j−1)th pass, and n/2 messages in a (2j)th pass, each of the messages departing from one of the n processors, traveling through one of the n inputs and one of the n outputs, and arriving at one of the n processors, wherein a kt
Yang Jianchao
Yang Yuan Yuan
Rinehart Mark H.
Suchyta Leonard Charles
Thompson Marc D.
Verizon Laboratories Inc.
Weixel James K.
LandOfFree
Optimal all-to-all personalized exchange in optical... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimal all-to-all personalized exchange in optical..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal all-to-all personalized exchange in optical... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3056567