Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1999-11-29
2003-09-30
Ngo, Ricky (Department: 2697)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S461000, C370S462000, C710S113000, C710S241000
Reexamination Certificate
active
06628662
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates in general to a multiprocessor data processing system and in particular to an improved method and system for arbitrating data transfers between multiple devices connected via electronically isolated buses at a switch. Still more particularly, the present invention relates to a method and system for multilevel arbitration in a non-blocking crossbar switch for handling arbitration within a multiprocessor data processing system.
2. Description of the Related Art
A conventional symmetric multiprocessor data processing system (SMP) may include a number of processors that are each coupled to a shared system bus. Each processor may include on-board cache that provides local storage for instructions and data, execution circuitry for executing instructions, and a bus interface unit (BIU) that supports communication across the shared system bus according to a predetermined bus communication protocol. Typically, in SMP systems, bus devices (i.e. processors, memory controller or I/O hubs) are connected via electronically isolated buses. When one device has a data transfer request for transferring data to another device, a switch, or other interprocessor interconnection medium routes the data from the source device to the correct destination device.
In a multiprocessor system, the functional characteristics of the interprocessor interconnection medium are a significant constraint on system performance. Characteristics sought in the medium include fast access arbitration, fair arbitration (i.e. no unit is starved for access), independence of connections (i.e. a connection between some units does not constrain connections between other units), deadlock prevention, equal opportunity for a processor to send and receive, and modular growth capability.
It is preferable to utilized a non-blocking medium that allows any interconnection that the processors are capable of handling to be made at any time. Such a medium is most versatile and efficient, in that it does not limit the type and number of interconnections between processors that may be made. Also, because the medium allows a plurality of independent connections to exist at a time, such a medium achieves higher communication bandwidth than other media (e.g. a bus). Furthermore, non-blocking media permit direct communication between a source and a destination, and therefore such media do not suffer from the latency of message or packet-passing arrangements wherein establishment of connections depends on self-routing information that must be picked off, decoded, and acted upon in order to effect proper routing.
Because a non-blocking interconnection medium such as a crossbar switch theoretically allows any desired connection between any processors to be made at any time, arbitration of access to the medium itself is not necessary. This situation is unlike typical bus arbitration. In single bus arbitration, the bus is the resource in demand and the destination unit, e.g. processor, is assumed by the arbiter to be available. Conversely, in the situation of a non-blocking interconnection medium, the medium is assumed to be available and the destination unit, or the link(s) connecting the destination unit to the medium, is the resource in demand.
Contention for the destination units, e.g. processors, or their links to the medium, occurs because the units or links themselves may not be capable of handling simultaneous connections from a plurality of units wishing to be connected thereto. For example, a processor is typically capable of being communicatively connected to only one other processor at any time. Hence, there remains the need to arbitrate conflicting multiple requests for access to a unit or link. Therefore, it would be desirable to provide a non-blocking crossbar switch that arbitrates multiple requests for access to a unit or link within a SMP system.
SUMMARY OF THE INVENTION
In view of the foregoing, it is therefore an object of the present invention to provide an improved multiprocessor data processing system.
It is another object of the present invention to provide an improved method and system for arbitrating data transfers between multiple devices connected via electronically isolated buses at a switch.
It is yet another object of the present invention to provide an improved method and system for multilevel arbitration in a non-blocking crossbar switch for handling arbitration within a multiprocessor data processing system.
In accordance with the method and system of the present invention, multiple arbitration controllers are interposed between devices and a switch to which the devices are connected, wherein each of the multiple arbitration controllers are effective to select a data transfer operation and detect collisions between said selected data transfer operations. The switch is enabled for any selected data transfer operations between which collisions are not detected. The switch is also enabled for only one of the selected data transfer operations between which collisions are detected. Any selected data transfer operations for which the switch is not enabled are deferred. The deferred data transfer operations are prioritized within the multiple arbitration controllers, such that for a subsequent selection of the deferred data transfer operations, the switch is enabled for the deferred data transfer operations.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.
REFERENCES:
patent: 4845722 (1989-07-01), Kent et al.
patent: 5179669 (1993-01-01), Peters
patent: 5561784 (1996-10-01), Chen et al.
patent: 5799209 (1998-08-01), Chatter
patent: 5889969 (1999-03-01), Getzlaff et al.
patent: 5949982 (1999-09-01), Frankeny et al.
patent: 6125429 (2000-09-01), Goodwin et al.
patent: 6292705 (2001-09-01), Wang et al.
patent: 6487621 (2002-11-01), MacLaren
Blackmon Herman Lee
Drehmel Robert Allen
Haselhorst Kent Harold
Marcella James Anthony
International Business Machines - Corporation
Ngo Ricky
Swickhamer Christopher M.
Truelson Roy W.
LandOfFree
Method and system for multilevel arbitration in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for multilevel arbitration in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for multilevel arbitration in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3095749