Ulllted States Patent [19]
`Arimilli et al.
`
`US006029217A
`[11] Patent Number:
`[45] Date of Patent:
`
`6,029,217
`*Feb. 22, 2000
`
`[54] QUEUEI) ARBITRATION MECHANISM FOR
`DATA PROCESSING SYSTEM
`
`5,276,887
`5,335,335
`5,345,578
`
`[75] Inventors: Ravi Kumar Arimilli, Round Rock;
`?gs/[while] Kalser’ Cedar Park’ both
`
`-
`
`-
`
`,
`
`,
`
`5,448,701
`
`1/1994 Haynie .................................. .. 395/294
`8/1994 Jackson et al.
`. 395/473
`9/1994 Manasse ........ ..
`.. 395/473
`lsfoyer ettal-l ------------------------- -
`9/1995 M611, Jr. et al.
`
`evens e a .
`
`....................... ..
`
`395/849
`
`'
`
`5,473,762 12/1995 Krein et al. . . . . .
`
`. . . .. 395/298
`
`_
`[*l Nome:
`
`_
`_
`_
`_
`[73] Ass1gnee: International Business Machines
`COFPOFatIOILAImOHk, NY-
`_
`_
`_
`Thls patent 15511991 00 a Con?rmed pros-
`ecution application ?led under 37 CFR
`1.53(d), and is subject to the twenty year
`11);?“ 2mm provlslons of 35 U30
`(ax
`
`[21] Appl. No.: 08/317,006
`
`Oct‘ 3’ 1994
`
`Flled:
`[22]
`........... .. G06F 13/20
`Int. Cl.7
`[51]
`10/107; 710/113; 710/116
`[52] US. Cl. .......... ..
`........... .. 395/290, 293_29s,
`[58] Field of Search .
`395/287, 849, 859, 865; 710/107, 110,
`113—118, 29, 39, 45
`
`[56l
`
`_
`References Clted
`U'S' PATENT DOCUMENTS
`
`4,481,572 11/1984 Ochsner et al. ...................... .. 395/297
`395/860
`4,482,949 11/1984 Gates ---------- -
`395/291
`479537081
`8/1990 Feal et a1~
`5906982 4/1991 Ebersole et a1‘ "
`395/736
`5,050,066
`9/1991 Myers et al. . . . . . .
`. . . . . .. 395/775
`5,103,393
`4/1992 Harris et al. ..
`395/20056
`5,202,966
`4/1993 Woodson .... ..
`395/297
`5,210,741
`5/1993 Grochmal .............................. .. 370/362
`
`5,485,586
`575067971
`5,506,995
`5,557,528
`5,623,628
`
`1/1996 Brash et al. .
`395/293
`4/1996 Gullette et a1‘ '
`395/473
`4/1996 Yoshimoto e161.
`395/287
`9/1996 Munro et al. ..... ..
`364/478.02
`4/1997 Brayton et al. ....................... .. 711/141
`
`FOREIGN PATENT DOCUMENTS
`0 488 771
`6/1992 European Pat. on. .... .. G06F 13/364
`O 488 771 A2 6/1992 European Pat. Off. .... .. GO6F 13/364
`WO 91/20041 12/1991 WIPO ........................ .. G06F 13/14
`WO91/20041 12/1991 WIPO ........................... .. G06F 13/14
`
`Primary Examiner—Glenn A. Auve
`Assistant Examiner—Ario Etienne
`Attorney, Agent, or Firm—K911y K- Kordzik; Winstead
`Sechrest & Minick PC; Anthony V- 8 England
`[57]
`ABSTRACT
`
`A queued arbitration mechanism transfers all queued pro
`cessor bus requests to a centralized system controller/ arbiter
`in a descriptive and pipelined manner. Transferring these
`descriptive and pipelined bus requests to the system con
`troller allows the system controller to optimize the system
`bus utilization via prioritization of all of the requested bus
`operations and pipelining appropriate bus grants. Intelligent
`bus request information is transferred to the system control
`ler Via encodin and Serialization techni ues
`g
`q
`'
`
`5 Claims, 3 Drawing Sheets
`
`102
`
`/104—___-
`
`/1D6
`
`CPU 8-
`CACHE
`
`CPU &
`CACHE
`
`CPU 8‘
`CACHE
`
`/12()
`
`HIGH PEHF.
`l/O DEVICE
`
`{
`Q
`
`108
`
`— — — - -
`
`CONTROL BUS
`
`132
`
`134
`
`SYSTEM
`BUS [
`
`K >136
`
`ADDHEQES) BUS
`(32/40 BITS)
`
`DATA BUS
`(64/128 BITS)
`
`__
`
`1
`l
`SYSTEM
`CON-
`TROLLER
`
`146
`
`146
`
`150
`
`13°
`
`11,,
`
`11a
`
`11a
`
`MEMORY
`CON_
`TROLLER
`
`V0
`CHANNEL
`CON-
`TROLLEFI
`
`V0
`CHANNEL
`cow,
`TROLLER
`
`14o
`
`‘ 44
`
`11o
`
`112
`
`SYSTEM
`MEMORY
`
`_ _ _
`
`___
`
`|/o
`CHANNEL
`CON
`TROLLEH
`
`/15O _
`
`SYSTEM _
`v0 AND
`NATIVE —
`
`l/O _
`
`_
`
`_
`_
`——
`
`_
`
`I/O BUS
`
`l/Q BUS
`(MICRO CHANNEL BUS)
`
`HTS
`
`Apple Exhibit 1008
`Page 1 of 8
`
`

`
`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 1 0f 3
`
`6,029,217
`
`/102
`
`/1o4
`
`CPU &
`CACHE
`
`CPU &
`CACHE
`
`'
`
`/1os
`
`CPU &
`CACHE
`
`10o
`
`/
`
`/120
`
`HIGH PERF.
`l/o DEVICE
`
`132
`/
`
`_ _ _ _ .
`
`SYSTEM
`BUS L
`
`CONTROL BUS
`
`AND
`ADDRESS BUS
`(32/48 DDS)
`
`V
`
`108
`
`134 \
`
`‘36 \
`
`+
`'
`SYSTEM
`CON-
`/ TROLLER
`
`14s
`/
`
`DATA BUS
`(64/128 ans)
`
`/14a
`
`0
`
`15°
`
`114
`/
`
`116
`
`118
`
`/_ _ _ -
`
`V0
`CHANNEL
`CON-
`TROLLER
`
`_ _ __ _
`
`/
`
`V0
`CHANNEL
`CON
`TROLLER
`
`130
`
`MEMORY
`CON
`TROLLER
`
`V0
`CHANNEL
`CON-
`THOLLEH
`
`14o
`
`144
`
`\
`
`110
`
`/112
`
`SYSTEM
`MEMORY
`
`_
`
`/ 160
`
`SYSTEM
`00 AND
`NATIVE
`V0
`
`V0 BUS
`
`l/O BUS
`(MICRO CHANNEL BUS)
`
`l/O BUS
`
`Apple Exhibit 1008
`Page 2 of 8
`
`

`
`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 2 of3
`
`6,029a217
`
`Apple Exhibit 1008
`Page 3 of8
`
`»z<mwmam
`
`
`
`0.004zo:<mmzmo
`
`
`
`.....numa
`
`0.00..ZO_._.<N_._._mO_mn_
`
`
`
`BmaommQMDMDOZD
`
`ma
`
`E.
`
`o _
`
`.m
`
`IMDOOMO
`
`mom
`
`doz<o
`
`
`
`.Nm_.
`
`
`
`
`
`om_..9:63.3....9:69.32.
`
`Apple Exhibit 1008
`Page 3 of 8
`
`
`
`
`
`

`
`U.S. Patent
`
`Feb. 22, 2000
`
`Sheet 3 of3
`
`6,029,217
`
`EEEEEEJ
`___3.3,.EE____om._._moz<om|||L”___
`
`D
`
`
`
`”om»z<mwZO_._.<mmn_O
`
`m.0_n_
`
`rialgalaflflgflalEmmmnwmm
`
`Em5<s_
`
`
`
`>:mo_mn_>>O._
`
`,||.J1|‘L
`
`mam
`
`<om<
`
`
`
`_om_»z<mozo:<mmmo
`
`Apple Exhibit 1008
`Page 4 of8
`
`Apple Exhibit 1008
`Page 4 of 8
`
`

`
`1
`QUEUED ARBITRATION MECHANISM FOR
`DATA PROCESSING SYSTEM
`
`2
`requests. Thus, there is a need in the art for a more ef?cient
`arbitration mechanism for granting access to the system bus.
`
`6,029,217
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application for patent is related to the following
`applications for patent ?led concurrently hereWith:
`EFFICIENT ADDRESS TRANSFER TECHNIQUE
`FOR A DATA PROCESSING SYSTEM, Ser. No. 08/317,
`007;
`DUAL LATENCY STATUS AND COHERENCY
`REPORTING FOR A MULTIPROCESSING SYSTEM,
`Ser. No. 08/316,980;
`SYSTEM AND METHOD FOR DETERMINING
`SOURCE OF DATA IN A SYSTEM WITH INTERVEN
`ING CACHES, Ser. No. 08/317,256;
`METHOD AND APPARATUS FOR REMOTE RETRY
`INADATA PROCESSING SYSTEM, Ser. No. 08/316,978;
`ARRAY CLOCKING METHOD AND APPARATUS
`FOR INPUT/OUTPUT SUBSYSTEMS, Ser. No. 08/316,
`976;
`DATA PROCESSING SYSTEM HAVING DEMAND
`BASED WRITE THROUGH CACHE WITH ENFORCED
`ORDERING, Ser. No. 08/316,979;
`COHERENCY AND SYNCHRONIZATION MECHA
`NISMS FOR I/O CHANNEL CONTROLLERS INADATA
`PROCESSING SYSTEM, Ser. No. 08/316,977;
`ALTERNATING DATA VALID CONTROL SIGNALS
`FOR HIGH PERFORMANCE DATA TRANSFER, Ser. No.
`08/326,190;
`LOW LATENCY ERROR REPORTING FOR HIGH
`PERFORMANCE BUS, Ser. No. 08/326,203.
`Each of such cross-referenced applications are hereby
`incorporated by reference into this Application as though
`fully set forth herein.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`TECHNICAL FIELD OF THE INVENTION
`
`The present invention relates in general to data processing
`systems and, in particular, to a system and method for
`intelligent communication of bus requests and bus grants
`Within a data processing system.
`
`BACKGROUND OF THE INVENTION
`Conventional data processing systems, especially multi
`processor systems, allocate access to the shared system bus
`coupling the various bus devices to system memory through
`a mechanism Whereby individual bus devices each control
`access to the system bus. Typically, each bus device Will
`queue it’s individual bus requests for various operations
`internally. Then, each bus device makes the determination of
`Which of the various operations it Wishes to perform on the
`system bus by sending the appropriate corresponding bus
`request to the system controller. Thus, each individual bus
`device determines internally Which of its bus requests has
`higher priority. The system controller is then required to
`arbitrate betWeen the received bus requests from the indi
`vidual bus devices.
`One disadvantage of this arbitration mechanism is that a
`portion of the decision process for accessing the various
`resources coupled to the system bus is delegated to each of
`the bus devices. As a result, the system controller is only
`able to vieW a portion of all of the various requests from the
`individual bus devices, since each of the individual bus
`devices retains and queues a signi?cant number of bus
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`SUMMARY OF THE INVENTION
`
`It is an object of the present invention to centraliZe the
`decision-making process for granting access to the system
`bus. In an attainment of this object, the present invention
`provides a mechanism of transferring all of the queued bus
`requests from the individual bus devices to the system
`controller, Which has a centraliZed knoWledge of the avail
`ability of all of the system resources coupled to the system
`bus.
`The system controller samples the bus devices’ requests
`on a cycle-by-cycle basis. The requests are encoded, Which
`alloWs each of the bus devices to precisely communicate to
`the system controller each of their internally “queued”
`operations. Quickly transferring these “descriptive and pipe
`lined” bus requests from each of the bus devices to a
`centraliZed control point, alloWs the system controller to
`“optimize” the system bus utiliZation by prioritiZing all of
`the requested bus operations and pipelining the appropriate
`bus grants.
`One advantage of the present invention is that it provides
`an ability to transfer “intelligent” bus request information
`from each bus device to the system controller, and provides
`the ability to transfer multiple packets of bus requests
`information (via encoding and serialiZation techniques).
`Another advantage of the present invention is that the bus
`requests are compact and can be issued in a pipelined
`manner and that bus grants may be pipelined to either the
`same bus device or different bus devices.
`Yet another advantage of the present invention is that it
`supports latch-to-latch or non-latch-to-latch implementa
`tions. Those skilled in the art Will appreciate the bene?t of
`accommodating both implementations. (Latch-to-latch
`implementations alloW higher system bus clock rates, While
`non-latch-to-latch implementations provides loWer system
`bus latencies.)
`Yet still another advantage of the present invention is that
`the queuing of descriptive bus requests alloWs the system
`controller to efficiently control, distribute, and allocate sys
`tem bus resources.
`And, yet still another advantage of the present invention
`is that the system controller may resolve system level
`multiprocessor problems such as deadlocks and livelocks.
`Unlike traditional arbitration techniques, the present inven
`tion bus does not require bus devices to adhere to any
`arbitration “fairness” protocols.
`Another advantage of the present invention is that the bus
`devices may support speculative bus requests and the system
`controller may support speculative bus grants.
`The foregoing has outlined rather broadly the features and
`technical advantages of the present invention in order that
`the detailed description of the invention that folloWs may be
`better understood. Additional features and advantages of the
`invention Will be described hereinafter Which form the
`subject of the claims of the invention.
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`For a more complete understanding of the present
`invention, and the advantages thereof, reference is noW
`made to the folloWing descriptions taken in conjunction With
`the accompanying draWings, in Which:
`FIG. 1 illustrates a block diagram of a data processing
`system in accordance With the present invention;
`
`Apple Exhibit 1008
`Page 5 of 8
`
`

`
`6,029,217
`
`3
`FIG. 2 illustrates a block diagram of the system controller
`illustrated in FIG. 1; and
`FIG. 3 illustrates an exemplary protocol for granting bus
`grants for bus requests from one of the bus devices illus
`trated in FIG. 1.
`
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT OF THE INVENTION
`With the foregoing hardWare in mind, it is possible to
`eXplain the process-related features of the present invention.
`To more clearly describe these features of the present
`invention, discussion of other conventional features is omit
`ted as being apparent to those skilled in the art. It is assumed
`that those skilled in the art are familiar With a multiuser,
`multiprocessor operating system, and in particular With the
`requirements of such an operating system for memory
`management including virtual memory, processor
`scheduling, synchroniZation facilities for both processes and
`
`10
`
`15
`
`4
`The present invention may be implemented With a clock
`synchronous system bus and separate address and data
`buses. Furthermore, as illustrated in FIG. 1, bus requests and
`bus grants are transferred, in a preferred embodiment, point
`to-point (unidirectionally or bidirectionally) betWeen the bus
`devices and system controller 130. This unidirectional point
`to-point topology is capable of supporting totally indepen
`dent and concurrent address and data bus requests and
`address and data bus grants. Additionally, it provides for
`system scalability Without affecting the request-to-grant
`speed, and is capable of supporting a “private” communi
`cation protocol betWeen the various bus devices and system
`controller 130.
`
`Some of the possible encoded bus requests may be as
`folloWs:
`
`Cancel
`Data
`Address
`Queued Queued Request Typical Bus
`Bus
`Bus
`XBR —ABR —DBR Code Request Request Request Requests Priority Operation
`
`0
`
`O
`
`O
`
`(A)
`
`Yes
`
`Yes
`
`Yes
`
`No
`
`0
`
`O
`
`1
`
`(B)
`
`Yes
`
`No
`
`Yes
`
`No
`
`0
`
`0
`1
`1
`1
`
`1
`
`1
`
`1
`O
`O
`1
`
`1
`
`O
`
`1
`O
`1
`O
`
`1
`
`(C)
`
`No
`
`Yes
`
`Yes
`
`NULL
`(D)
`
`No
`Yes
`Yes
`No
`
`No
`Yes
`No
`Yes
`
`No
`No
`No
`No
`
`No
`
`No
`Yes
`Yes
`Yes
`
`CNCL
`
`No
`
`No
`
`No
`
`Yes
`
`High Store/Push
`LoW Retried Store,
`Cast Out,
`Speculative Store
`High Load/Address Only
`LoW Retried Load/
`Address Only,
`Speculative Load/
`Address Only
`High Load
`Reply/Intervention
`— NULL
`High Store/Push
`High Load/Address Only
`High Load Reply/
`Intervention
`— CANCEL ALL
`REQUESTS
`
`45
`
`processors, message passing, ordinary device drivers, ter-
`minal and netWork support, system initialiZation, interrupt
`management, system call facilities, and administrative
`facilities.
`Referring noW to FIG. 1, a data processing system Which
`advantageously embodies the present invention Will be
`.
`.
`.
`described. Multiprocessor system 100 includes a number of
`processing units 102, 104, 106 operatively connected to a
`system bus 108. Also connected to the system bus 108 is a 50
`-
`memory controller 110, WhlCh controls access to system
`memory 112, and I/O channel controllers 114, 116, and 118.
`Additionally, a high performance I/O device 120 may be
`connected to the system bus 108. Each of the system
`elements described 102—120, inclusive, operate under the 55
`control of system controller 130 Which communicates With
`each unit Connected to the system bus 108 by point to point
`lines such as 132 to processor 102, 134 to processor 104, 136
`I0 Processor 106, 140 to memory Controller 110, 144 IO U0
`channel controller
`1O
`channel controller
`148 I0 U0 Channel Controller 118, and 150 to high PfIIfOI-
`IIlaIlCe I/O deVlCe 120- Requests and grants 0f bllS access are
`all Controlled by system COIltrOller 130-
`I/0 channel controller 114 controls and is connected to
`system I/O subsystem and native I/O subsystem 160.
`Each processor unit 102, 104, 106 may include a proces
`sor and a cache storage device.
`
`Possible bus grants may be encoded as folloWs:
`
`.
`.
`-ABG —DBG CODE D
`escnpnon
`(AD) Address and
`Data Bus Grant
`(A0) Address only
`Bus Grant
`(DO) Data Only
`Bus Grant
`(NG) NO Grant
`
`0
`
`1
`
`0
`
`1
`
`0
`
`0
`
`1
`
`1
`
`1 B
`(ita?tgo T _
`W m us yplca. us
`R
`0
`equests
`peranon
`Aor D Store or
`gush Sr
`ast ut
`B OrE Load of
`Address only
`C or F Load Reply or
`Intervention
`— —
`
`In the above tables, XBR represents a control bit, While
`_ABR and -DBR represent address bus requests and data bus
`requests, respectively. —ABG and —DBG represent address
`60 bus grant and data bus grant, respectively As may be noted
`in the above bus request table, a “1” in the XBR portion of
`the bus request code represents that a particular bus device
`is sending a request that is not to be queued and Which
`cancels all previously queued requests from that particular
`65 bus device.
`Note that the terms “Cast Out”, “Store”, “Push”, “Load”,
`“Address Only”, “Load Reply”, “Intervention”, “Specula
`
`Apple Exhibit 1008
`Page 6 of 8
`
`

`
`6,029,217
`
`5
`tive Load”, “Speculative Store”, “Retried Store”, “Load
`Reply”, “Retried Load” are all terms for operations Well
`knoWn in the art and are to be interpreted according to their
`traditional references in the art.
`Referring neXt to FIG. 2, there is illustrated a block
`diagram of system controller 130. System controller 130, as
`previously illustrated in FIG. 1, is coupled to the various bus
`devices via lines 132, 134, 136, 140, 144, 146, 148 and 150.
`These lines carry the encoded bus requests and transmit the
`encoded bus grant information to and from the bus devices.
`In the folloWing discussion, reference Will only be made
`to input latch 201, decoder 203, reset request latches 205 and
`request latches 207—209; Which are coupled to processor 102
`via connection 132. Components 202, 204, 206, 210, 211,
`212 operate in a similar manner, and may be coupled to I/O
`channel controller 118 via connection 148.
`When a bus device, such as processor 102 sends a bus
`request to system controller 130 via line 132, it is received
`by input latch 201. Latches 201, 202, 216 and 217 assist in
`implementing system controller 130 With the bus devices in
`system 100 Within a latch-to-latch implementation.
`As bus requests are sent from processor 102 to system
`controller 130, they are latched into input latch 201 and
`decoded by decoder 203. If the bus requests are to be queued
`requests, they are then latched in succession into request
`latches 207—209. In a preferred embodiment of the present
`invention, system controller 130 implements a 3-deep
`queue. Of course, system controller 130 could be designed
`by one skilled in the art to implement various other N-deep
`queues, Where N>0. Note that at the same time that proces
`sor 102 is sending queued requests to system controller 130
`as described above, other bus devices, such as I/0 channel
`controller 118 may also be sending bus requests, Whether
`queued or not queued, to be latched into request latches
`210—212.
`Queued request prioritiZation logic 213 then observes all
`latched requests from all bus devices via latches 207—212,
`and prioritiZes their requests to determine Which are to be
`given bus grants ?rst. For eXample, by reference to the bus
`request table above, high priority requests Will be granted
`access to system bus 108 before loW priority requests.
`Furthermore, logic 213 may be designed for a particular
`system 100 to grant bus 108 for a load bus request before a
`store bus request. One skilled in the art may easily imple
`ment any desired priorities for determining Which requests
`are to receive granting of bus 108 and in What order for
`implementation Within logic 213.
`As logic 213 determines Which queued request to grant
`the bus to neXt, it then signals bus grant generation logic 215
`of Which encoded grant to generate and to Which bus device.
`If decoder 203 receives one of the bus requests from the
`bus request table that requires previously queued requests to
`be cancelled, decoder 203 Will signal reset request latch 205,
`Which resets request latches 207—209, cancelling previous
`requests from processor 102. Decoder 203 also sends these
`unqueued requests to unqueued request prioritiZation logic
`214, Which also performs a prioritiZation process betWeen
`the unqueued requests received by logic 214. Logic 214,
`upon determining Which of the unqueued requests is to be
`granted access to system bus 108 neXt, signals logic 215 of
`such a decision. Again, one skilled in the art may easily
`implement any desired priorities for determining Which
`unqueued requests are to receive granting of bus 108. Logic
`215 receives a prioritiZed queued request and a prioritiZed
`unqueued request, and determines Which of these is to be
`granted access to system bus 108 neXt. Generally, since
`unqueued requests have a high priority, they Will be granted
`access to system bus 108 before queued requests.
`Bus grant generation logic 215 generates the encoded bus
`grants illustrated in the table above. These bus grants are
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`latched out of system controller 130 by output latches
`216—217. Thus, if logic 213 determines that a queued request
`from processor 102 is to receive the neXt bus grant, bus grant
`generation logic 215 Will produce the appropriate encoded
`grant, Which Will be latched from latch 216 to processor 102,
`Which Will then utiliZe system bus 108 in the requested
`manner.
`Also, the encoded grant from bus grant generation logic
`215 Will be used by reset request latches 205 to reset the
`appropriate queued request latch 207, 208, or 209.
`Referring neXt to FIG. 3, there is illustrated an exemplary
`protocol of bus requests and bus grants for one of the bus
`devices, such as processor 102. The bus requests are pipe
`lined and sent from processor 102 via line 132 to system
`controller 130 as indicated. Through the above-described
`process, system controller produces the pipeline of bus
`grants as indicated in FIG. 3. Note the numerous “no grants”
`(“NGs”) Within the pipeline of grants, Which may indicate
`that one or more of the other bus devices in system 100 is
`currently being served by system controller 130. The “null”
`notations indicate that processor 102 is currently not trans
`mitting a bus request.
`Since a queued bus request may have previously been
`transmitted by processor 102, a “null” request does not
`imply that processor 102 does not need access to the system
`bus 108.
`The eXample shoWs that processor 102 is ?rst in need of
`a store or push bus operation (noted by code A) and is neXt
`in need of a load or address only operation (noted by code
`B). At some time later, system controller 130 grants the
`address and data bus for the code Arequested operation and
`then later grants the address bus only in response to the code
`B request.
`The eXample bus request pipeline also indicates a serial
`iZation technique Whereby tWo consecutive encoded
`requests from a particular bus device indicate to system
`controller 130 that the bus request is a loW priority request.
`Such a loW priority request may be in response to a previ
`ously “retried” bus operation from one of the other bus
`devices. Retries on the system bus 108 often result in
`prolonged livelocks and maybe even a deadlock. Adeadlock
`may be de?ned as an in?nite livelock. A livelock may be
`de?ned as a condition on the system bus 108 in Which a bus
`device “A” retries an operation by bus device “B” and bus
`device “B” retries an operation by bus device “A” and this
`cyclical pattern continues until another condition “alters”
`this pattern. Livelock conditions are Well knoWn in the art.
`Livelock conditions severely degrade system performance
`due to the inef?cient usage of the system bus resources.
`Therefore, it is advantageous to differentiate a bus request
`from a previously retried bus request. Furthermore, retried
`bus requests often get retried again due to “busy” system
`resources. Thus, it is also advantageous to have these retried
`bus requests contain a loW priority in order to more ef?
`ciently utiliZe the system bus resources. It may further be
`preferable, then, to grant access to the bus for loW priority
`requests in a randomiZed fashion and high priority requests
`in a prioritiZed fashion. The random generation of grant to
`loW priority requests avoids the cyclical system bus retries,
`thus avoiding livelocks and deadlocks. The prioritiZed gen
`eration of grant to high and loW priority requests ef?ciently
`realiZes the system bus bandWidth.
`As indicated Within FIG. 3, the bus request encoded as a
`load reply or intervention, is given a data only bus grant
`before the address and data bus grant in response to the loW
`priority requests (encoded With an A). This illustrates hoW
`system controller 130 granted access to bus 108 to a higher
`priority request instead of a loW priority request.
`Also illustrated is hoW the second bus request B is
`cancelled by bus request D, Which as indicated in the bus
`
`Apple Exhibit 1008
`Page 7 of 8
`
`

`
`10
`
`7
`request table is not intended to be a queued request, and
`Which informs system controller 130 to cancel all previous
`requests from processor 102. Since bus request D is not
`queued inside controller 130, bus request D remains active
`until it receives a grant. Such a situation is decoded by
`decoder 203 and transferred to unqueued request prioritiZa
`tion logic 214, Which informs bus grant generation logic 215
`of the unqueued request. Furthermore, decoder 203 informs
`reset request latches 205 to cancel all previous requests
`Within the queued request latches 207—209.
`In the above bus request and bus grant tables, intervention
`refers to a situation Where another bus device has snooped
`a bus request and has determined that it contains Within its
`internal cache a “dirty,” or modi?ed version of the requested
`data. A mechanism is then set in motion Whereby the
`requesting bus device is informed that data is to be received
`15
`from the other bus device instead of system memory. A
`further discussion of “intervention” is supplied Within cross
`referenced US. patent application Ser. No. (HQ9-94-034),
`Which is hereby incorporated by reference herein.
`Note that the XBR bus request signal need not be imple
`mented in all systems. For loW cost systems, the XBR
`information may be con?gured to a speci?c value in system
`controller 130 for certain bus devices.
`Note that there is capacity for other encoded requests and
`grants via serialiZation techniques or the addition of bus
`request and bus grant signals. Furthermore, other types of
`requests and other protocols may be designed into the
`system of the present invention as desired.
`Although the present invention and its advantages have
`been described in detail, it should be understood that various
`changes, substitutions and alterations can be made herein
`Without departing from the spirit and scope of the invention
`as de?ned by the appended claims.
`What is claimed is:
`1. A computer system, comprising:
`a plurality of bus devices including one or more proces
`sors and one or more storage devices;
`a system controller;
`a bus architecture coupling said plurality of bus devices
`and said system controller;
`?rst means adaptable for transferring each address and
`data bus request from said plurality of bus devices to
`said system controller as said each address and data bus
`request is generated by said plurality of bus devices;
`second means adaptable for transferring, from said system
`controller to said plurality of bus devices, responses to
`said each address and data bus request, and Wherein at
`least one of said each address and data bus request is a
`speculative bus request; and
`means for issuing a bus grant to a non-speculative bus
`request before issuing a bus grant to said speculative
`bus request even though said speculative bus request
`Was received by said system controller before said
`non-speculative bus request Was received by said sys
`tem controller.
`2. A computer system, comprising:
`a plurality of bus devices including one or more proces
`sors and one or more storage devices;
`a system controller;
`a bus architecture coupling said plurality of bus devices
`and said system controller;
`?rst means adaptable for transferring each address and
`data bus request from said plurality of bus devices to
`said system controller as said each address and data bus
`request is generated by said plurality of bus devices;
`and
`
`45
`
`55
`
`25
`
`35
`
`6,029,217
`
`8
`second means adaptable for transferring, from said system
`controller to said plurality of bus devices, responses to
`said each address and data bus request, and Wherein an
`issue of one of said each address and data bus request
`on at least tWo consecutive bus cycles is treated as a
`loW priority bus request by said system controller,
`Wherein said system controller may issue a bus grant in
`response to a bus request received subsequent to said
`issue of said one of said each address and data bus
`request on at least tWo consecutive bus cycles before
`issuing a bus grant in response to said issue of said one
`of said each address and data bus request on at least tWo
`consecutive bus cycles.
`3. The computer system as recited in claim 2, Wherein said
`issue of one of said each address and data bus request on at
`least tWo consecutive bus cycles is an issue of a ?rst one of
`said each address and data bus request on a ?rst one of said
`at least tWo consecutive bus cycles and an issue of a second
`one of said each address and data bus request on a second
`one of said at least tWo consecutive bus cycles, Wherein said
`?rst one and said second one of said each address and data
`bus requests are separate address and data bus requests from
`a same one of said plurality of bus devices.
`4. The computer system as recited in claim 2, Wherein said
`loW priority bus request is an issue of tWo separate address
`and data bus requests on said at least tWo consecutive bus
`cycles from a same one of said plurality of bus devices.
`5. A multiprocessor system comprising a plurality of bus
`devices coupled to a storage device via a system bus, and
`coupled to a system controller via a point-to-point bus
`architecture, Wherein said system controller further com
`prises:
`?rst means for receiving a ?rst bus request from a ?rst one
`of said plurality of bus devices;
`a ?rst decoder coupled to said ?rst receiving means for
`decoding said ?rst bus request;
`a ?rst plurality of bus request latches coupled to said ?rst
`decoder for temporarily storing said ?rst bus request
`received from said ?rst one of said plurality of said bus
`devices;
`second means for receiving a second bus request from a
`second one of said plurality of bus devices;
`a second decoder coupled to said second receiving means
`for decoding said second bus request;
`a second plurality of bus request latches coupled to said
`second decoder for temporarily storing said second bus
`request received from said second one of said plurality
`of said bus devices;
`queued request prioritiZation logic coupled to an output of
`each one of said ?rst and second plurality of bus request
`latches for determining Which one of said bus requests
`from said ?rst and second one of said plurality of said
`bus devices to grant the bus to;
`unqueued request prioritiZation logic coupled to outputs
`of said ?rst and second decoders;
`bus grant generation logic coupled to an output of said
`queued request prioritiZation logic and coupled to an
`output of said unqueued prioritiZation logic;
`?rst and second output means coupled to outputs of said
`bus grant generation logic for outputting a bus grant to
`said plurality of bus devices.
`
`*
`
`*
`
`*
`
`*
`
`*
`
`Apple Exhibit 1008
`Page 8 of 8