Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1998-12-11
2001-11-06
Maung, Zarni (Department: 2154)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C370S351000, C370S389000
Reexamination Certificate
active
06314487
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates to an adaptive routing controller of a crossbar core module used in a crossbar routing switch.
In general, for a parallel processing system to have an excellent performance by concurrently processing tasks in parallel in a plurality of processors by using a plurality of processors, an interconnection network for connecting a plurality of processors plays a very important role. The interconnection network consists of a routing switch, a backplane and a cable. The routing switch is a nucleolus part which performs a function of interconnection network.
Since the function of the routing switch is determined according to a structure and a function of each interconnection network, the routing switch of a particular interconnection network is designed and implemented to be adapted to the particular interconnection network. In addition, a routing controller must be designed to be adapted to a function and characteristics inherent to the routing switch. In other words, the routing controller which well supports the characteristics of the routing switch and provides an excellent performance and function plays a nucleolus role which determines the inherent characteristics, excellent function and performance of the routing switch. Furthermore, since this role leads to the characteristics and function of the interconnection network, the invention of the routing controller which well supports the inherent characteristics and provides the excellent performance and function is very important.
A switching device invented by G. P. Balboni et al. is a switching element for performing a self routing control in a multistage packet switching interconnection network(refer to G. P. Balboni et al., . . . Switching Element for Self-routing Multistage Packet-switching Interconnection Networks”, U.S. Pat. No. 4,890,281, December 1989). The switching device is a unit device having 2X2 switch configuration and is a simple switching device controlled by one bit among a tag portion of a packet. The switching device does not have an arbitration concept. It performs the routing control by the simple tag bit, and has a two port simultaneous transmission function for broadcasting transmission. The switching device does not provide an arbitration and adaptive routing control method.
An interconnection network device proposed by S. B. Kim et al. is a switching device for performing the routing control in an interconnection network of mesh type(refer to S. B. Kim et al. interconnection network device”, KR 66825, October 1993). The switching device can obtain a plurality of routings while avoiding a deadlock state in the interconnection network of mesh type, and has a routing control unit which performs the routing control only to the address determined by the packet tag and perform the arbitration via a simple 3X1 selector. The switching device is implemented with its own packet type and routing control method and provides only a basic routing control method.
A multipath torus switching apparatus invented by Olnowich and Williams is a switching device of Wormhole routing having small delay time in the interconnection network of torus mesh type(refer to H. T. Olnowich and A. R. Williams, . . . Multipath torus switching apparatus”, EP 0588104A2, December 1994). The switching device is invented to determine a routing control port by adding a multipath establishment function to an existing torus switch. The switching device consists of four single routing controller and a multipath controller and selects an output port by using a connection command of packet. However, the switching device does not suggest a scheme of arbitration method, and has different packet type and routing control method. Although the switching device has a multipath control function similar to the adaptive routing control, since the configuration and method thereof are different, it can not be properly used to a crossbar routing switch.
An adaptive routing control method invented by Nugent is a method in which an additional connection path is established by connecting to an interconnection network of mesh type an additional interconnection network of identical type and thereafter performs the routing control via the additional connection path in case that a problem occurs to an existing routing or a transmission is impossible. (refer to Nugent, . . . Adaptive Message Routing for Multi-Dimensional Networks,” U.S. Pat. No. 5,175,733, December 1992). The adaptive routing control method is a method in which when the routing control is impossible to X-direction and Y-direction, the adaptive routing control is performed to Z-direction by establishing an additional connection path to Z-direction. In case of the routing controller, it only performs a simple arbitration for two inputs and it is not appropriate to the adaptive routing control method and a switching device having a plurality of I/O ports.
An adaptive routing control switching device invented by A. H. Frey Jr. et al is a switching device for controlling the routing with a shortest distance up to a destination in a multi-dimension multi-node environment(refer to A. H. Frey Jr. et al., . . . Adaptive Routing in a Parallel Computing System”. U.S. Pat. No. 5,181,017, January 1993). The switching device is a device by which only one packet which arrives fastest is effectively received by retrieving all routing possibly established from a source to a destination and transmitting simultaneously via all the paths. This method performs the adaptive routing control via a packet header, and the switching device provides only a mechanism for transmission and cancellation of the packet. The transmission of packet is terminated by only one time of packet transmission in other interconnection network, while there is a problem in the interconnection network of the switching device described above that a separate packet transmission is necessary for confirmation.
Most of conventional inventions are switching devices or appropriate arbitration methods for the multi-stage interconnection network or the mesh type interconnection network, and in addition, the adaptive routing control methods have many different methods and constitutions, therefore, most of conventional inventions can not provide routing controller adapted to the crossbar routing switch.
SUMMARY OF THE INVENTION
Therefore, the object of the present invention is to provide a priority based round robin arbitration method for offering fairness and preventing starvation in a routing controller which performs the arbitration and routing control function of the crossbar routing switch, and to provide a routing control apparatus for performing the round robin arbitration and adaptive routing control by inventing a Normal Routing Control Unit which performs the priority based round robin arbitration method and by adding an Adaptive Routing Switch Logic to two the Normal Routing Control Units.
The present invention is to provide a crossbar routing switch having a crossbar core module, a plurality of input control module and a plurality of output control module, comprises: a plurality of normal routing control logic for performing a priority based round robin arbitration and controlling an internal logic; an adaptive routing switch logic for receiving a signal of said normal routing control logic and a ready signal and outputting a plurality of corresponding arbitration selection sequential signals, status signals and arbitration selection combinational signals; and a plurality of mask registers for performing the priority based round robin arbitration, wherein said plurality mask registers include a plurality of normal transfer mask registers for connecting, bit by bit, ten bits of the normal arbitration request signal and ten bits driven from said normal routing control logic to the inputs of AND gates and for providing outputs back to said normal routing control logic, and a plurality of emergency transfer mask registers for connecting, bit by bit, ten bits of the emergenc
Hahn Jong Seok
Hahn Woo Jong
Sim Won Sae
Yoon Suk Han
Antonelli Terry Stout & Kraus LLP
Chang Jung-won
Electronics and Telecommunications Research Institute
Maung Zarni
LandOfFree
Adaptive routing controller of a crossbar core module used... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive routing controller of a crossbar core module used..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive routing controller of a crossbar core module used... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2612918