Arbitration of packet switched busses, including busses for shared memory multiprocessors

• US 5,440,698 A
• Filed: 04/29/1994
• Issued: 08/08/1995
• Est. Priority Date: 11/30/1990
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Sindhu, Pradeep S., Frailong, Jean-Marc, Gastinel, Jean A.
• Primary Examiner(s): Ray, Gopal C.
• Application Number:
  US08/236,883
• Time in Patent Office: 466 Days
• Field of Search: 395/325, 395/725, 395/425, 395/200, 395/275, 370/60, 370/85.2, 370/85.6, 370/94.1, 370/94.2, 370/60.1, 340/825.5, 340/825.51
• US Class Current: 709/225
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines

Abstract

An arbiter is provided for resolving contention on synchronous packet switched busses, including busses composed of a plurality of pipelined segments, to ensure that all devices serviced by such a bus are given fair, bounded time access to the bus and to permit such devices to fill all available bus cycles with packets. Flow control for shared memory multiprocessors is readily implemented with this arbiter because the arbiter supports different types of arbitration requests and the prioritization of such arbitration requests by type.

Claims

1. An arbiter for resolving bus contention in a system having a synchronous packet switched bus, and a plurality of client devices that are interfaced with said bus;

said client devices being synchronously clocked at a predetermined frequency for synchronously exchanging packets of information via said bus on a contention basis;

each of said packets having a duration spanning a plurality of consecutive clock cycles on said bus, such that each packet has an initial cycle and a final cycle;

said arbiter comprising;

a plurality of ports, each of said client devices being coupled to a respective one of said ports for registering arbitration requests with said arbiter and for receiving corresponding bus grants from said arbiter;

said arbitration requests having a plurality of permissible encodings that said arbiter recognizes as representing requests for bus grants of differing durations, with at least some of said client devices having provision for registering arbitration requests with said arbiter for grants of different predetermined lengths to acquire control of said bus for packets spanning different numbers of clock cycles on said bus; and

logic coupled to said ports for arbitrating said arbitration requests, in advance of each of said bus grants, in accordance with predetermined arbitration rules to provide bus grants spanning an appropriate number of clock cycles on said bus in response to one after another of said arbitration requests;

each of said bus grants being time limited to give the client device to which a particular grant is communicated exclusive control of said bus for the duration of a single packet, with said control commencing and terminating concurrently with the initial cycle and the final cycle, respectively, of said packet;

said arbitration requests being arbitrated sufficiently in advance of each of said bus grants based on control information provided by said logic that enables the client devices to anticipate and discriminate between bus grants for said different request types to enable said client devices to pack packets into consecutive clock cycles on said bus.

2. The arbiter of claim 1 wherein said bus comprises a plurality of pipelined segments, including unidirectional input and output segments that are interfaced with said client devices, and an intermediate bidirectional segment located between said input and output segments;

said intermediate segment being the only bidirectional segment of said bus.

3. The arbiter of claim 1 wherein each of said client devices is coupled to said arbiter by a plurality of request lines for encoding said arbitration requests to register a plurality of different, predetermined types of arbitration requests with said arbiter.

4. The arbiter of claim 3 wherein

at least some of said client devices register arbitration requests of varying priority with said arbiter;

and

said arbiter interprets said arbitration requests in accordance with said arbitration rules to prioritize said bus grants.

5. The arbiter of claim 4 wherein

at least some of said client devices register arbitration requests with said arbiter for grants of different predetermined lengths to acquire control of said bus for packets having lengths spanning different numbers of bus cycles;

and

said arbiter further interprets said arbitration requests to provide bus grants spanning an appropriate number of bus cycles for each of said requests.

6. The arbiter of any of claims 1-3, 4 or 5, inclusive, wherein

said bus is a memory bus of a computer system having a plurality of bus client devices, including a main memory, that are coupled to said bus for performing memory transactions within a memory space, said transactions being composed of request packets that are issued by bus client devices functioning as requestors and reply packets that are issued by bus client devices functioning as responders;

said arbiter assigns a higher arbitration priority to arbitration requests for said reply packets than to arbitration requests for said request packets; and

said arbiter reserves an even higher arbitration priority for permitting at least certain of said client devices to demand a modified behavior of said arbiter for flow control purposes.