(12) United States Patent
`Batchelor et al.
`
`USOO6286O74B1
`(10) Patent No.:
`US 6,286,074 B1
`(45) Date of Patent:
`Sep. 4, 2001
`
`(54) METHOD AND SYSTEM FOR READING
`PREFETCHED DATA ACROSSA BRIDGE
`SYSTEM
`
`(75) Inventors: Gary William Batchelor; Brent
`Cameron Beardsley; Matthew Joseph
`Kalos; Forrest Lee Wade, all of
`Tucson, AZ (US)
`(73) Assignee: International Business Machines
`Corporation, Armonk, NY (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/275,610
`(22) Filed:
`Mar. 24, 1999
`(51) Int. Cl." .................................................. G06F 13/14
`(52) U.S. Cl. .............................................................. 710/129
`(58) Field of Search ............................. 711/137; 710/100,
`710/107, 126, 127, 128, 129, 130
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,490,788
`4,947,366
`
`12/1984 Rasmussen.
`8/1990 Johnson.
`(List continued on next page.)
`OTHER PUBLICATIONS
`PCI to PCI Bridge Architecture Specification; PCI Local
`Bus, Revision 1.0, Apr. 5, 1994.
`PCI Local Bus Specification: PCI Local Bus, Revision 2.1,
`Jun. 1, 1995 (Chapter 3.0, Appendix E).
`
`PCI-to-PCI Bridge Architecture Specification, PCI Local
`Bus, Revision 1.1, Dec. 18, 1998 (Chapter 3, 4, 5).
`PCI Local Bus Specification; PCI Local Bus, Revision 2.2,
`Dec. 18, 1998 (Chapter 1, 2, 3).
`U.S. application No. 09/275,857 (TU9–98–072 1842).
`U.S. application No. 09/275,603 (TU9–98-073 1843).
`U.S. application No. 09/275,470 (TU9–98–075 18.45).
`
`* cited by examiner
`
`Primary Examiner-Glenn A. Auve
`(74) Attorney, Agent, or Firm-David W. Victor; Konrad
`Raynes & Victor
`ABSTRACT
`(57)
`Disclosed is a bridge System for processing read transactions
`over a bus in which in a preferred embodiment prefetched
`data stored in a buffer is not discarded if the address of the
`requested read does not match the beginning address of the
`prefetched data. Instead, the bridge System skips to the next
`address of the prefetched data stored in the buffer and
`compares that address to the address of the read request to
`determine if a match exists. If the requested read address
`does match the next prefetched data address, the prefetched
`data Starting at that next address is read out and forwarded
`to the requesting agent. Alternatively, if there is not a match,
`the bridge skips again to the next address and continues
`checking for a match until either the prefetched data is
`exhausted or another predetermined limit has been reached.
`In this manner, many unnecessary data reads of data already
`prefetched in the buffer may be avoided.
`
`41 Claims, 14 Drawing Sheets
`
`800 Initialize Sawed
`Address value;
`Initialize Max
`Address value.
`
`Does
`Read Address
`match Saved
`Address?
`
`Unsatisfied
`Read Request
`
`814
`21 is
`return FIFC
`empty?
`
`813 -
`Y is
`read queue
`empty?
`
`Yes
`
`Increment Saved
`Address and
`Read Address
`
`Read Data
`byte from
`return FIFO
`and serid data
`byte. Clear
`Unsatisfied
`Read Reguest
`Flag.
`
`Yes
`
`
`
`
`
`Store Saved
`Address
`with Read
`Address
`
`No
`
`Read data
`byte from A
`return FIFO A
`and discard A
`databyte
`
`No
`
`l
`
`does
`Saved Address
`walue exceed Max
`Address
`walue?
`
`
`
`f
`
`Execute read f
`operation in
`queue and
`store prefetched A
`data in return
`O.
`
`Send read
`request for
`Sawed Address.
`Reset return a
`FIFO. Set
`Unsatisfied
`Read Request
`Flag.
`
`RETURN
`
`gif
`
`Lenovo
`Ex. 1027 - Page 1
`
`

`

`US 6,286,074 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`McGarvey.
`Spaniol et al. .
`Amini et al. .
`Elazar et al. .
`Stager.
`Amini et al. .
`Shibata et al. .
`Chelava, Jr. et al. .
`Potter.
`Jennings et al. .
`Stewart et al. .
`Amini et al. .
`Andrade et al. .
`Shah et al. .
`Katz et al. .
`Fenwick et al. .
`Guthrie et al. .
`Powell et al. .
`Kobayashi.
`
`4/1995
`9/1995
`5/1996
`9/1996
`11/1996
`12/1996
`1/1997
`2/1997
`3/1997
`5/1997
`5/1997
`7/1997
`7/1997
`9/1997
`9/1997
`9/1997
`9/1997
`12/1997
`1/1998
`
`5,404,463
`5,448,704
`5,522,050
`5,555,383
`5,574,944
`5,581,714
`5,594,878
`5,603,052
`5,608,884
`5,632,021
`5,634,033
`5,644,729
`5,649,161
`5,664,117
`5,664,124
`5,666,551
`5,673,399
`5,699,529
`5,706,469
`
`1/1998
`5,712,986
`2/1998
`5,721,839
`2/1998
`5,721,841
`3/1998
`5,724,528
`3/1998
`5,734,841
`3/1998
`5,734,847
`4/1998
`5,737,744
`4/1998
`5,740,376
`4/1998
`5,740,385
`5/1998
`5,748.920
`5/1998
`5,748.921
`5/1998
`5,758,166
`6/1998
`5,761,450
`6/1998
`5,761,462
`6/1998
`5,761,725
`6/1998
`5,764,924
`6/1998
`5,768,548
`5,815,677 * 9/1998
`5,915,104 * 6/1999
`6,138,192 * 10/2000
`
`Vo.
`Callison et al. .
`Szczepanek.
`Kulik et al. .
`Shin et al. .
`Garbus et al. .
`Callison et al. .
`Carson et al. .
`Hayek et al..
`Mills et al. .
`Lambrecht et al. .
`Ajanovic.
`Shah .
`Neal et al. .
`Zeller et al. .
`Hong .
`Young et al. .
`Goodrum ............................. 710/126
`Miller .......
`710/129
`Hausauer ............................. 710/100
`
`
`
`Lenovo
`Ex. 1027 - Page 2
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 1 of 14
`
`US 6,286,074 B1
`
`
`
`Channel
`Adaptor
`
`Processor 10
`Logical
`Control
`Unit "A"
`36
`
`Control
`All
`Unit A
`38
`
`Processor 12
`Logical
`Control
`Unit "B"
`40
`
`Control
`Unit B
`42
`
`Lenovo
`Ex. 1027 - Page 3
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 2 of 14
`
`US 6,286,074 B1
`
`Channel
`Adaptor
`14-A
`
`Channel
`Adaptor
`14-B
`
`Channel
`Adaptor
`14-C
`
`Channel
`Adaptor
`14-D
`
`Remote
`PC Bus 44
`
`Remote
`
`Remote PC
`
`Bridge 18 SE.56" |Magger
`
`SRAM
`74
`
`RemoteAddress
`Translator 54
`Transaction
`Control 55
`
`Remote
`Bus
`
`Remote PC
`
`5:55,
`
`RemoteAddress
`Translator 56
`Transaction
`Control 57
`
`FFO BufferS 80
`
`FIFO Buffers 82
`
`Remote Distance
`interface 58
`
`Remote Distance
`Interface 60
`
`
`
`59
`Local Distance
`local
`Bridge 22 Interface 62
`
`
`
`f
`Local Distance
`local
`Bridge 26 Interface 64
`
`FIFO BufferS 84
`
`LOCal Address
`Translator 66
`Transaction
`Control 67
`
`Local PC
`Bridge 70
`
`
`
`
`
`Processor
`10
`
`
`
`FIFO BufferS 86
`
`Local Address
`Translator 68
`Transaction
`Control 69
`
`PrOCeSSOr
`12
`
`NVS Unit
`34
`
`88
`NVS Unit
`32
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Lenovo
`Ex. 1027 - Page 4
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 3 of 14
`
`US 6,286,074 B1
`
`
`
`Transaction
`from Channel
`Adaptor
`
`Transaction
`from Channel
`Adaptor
`14-B
`
`Transaction
`from Channel
`Adaptor
`4-C
`
`Write
`Request
`FIFO
`102b
`
`Request
`FIFO
`
`Read
`Return
`106a
`
`Read
`Return
`106b
`
`Read
`Request
`FIFO
`110a
`
`Read
`Return
`112b
`
`Lenovo
`Ex. 1027 - Page 5
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 4 of 14
`
`US 6,286,074 B1
`
`
`
`Transaction
`from Channel
`Adaptor
`
`Request
`FIFO
`102d
`Read
`Request
`FIFO
`
`Read/Write
`Request
`FIFO
`
`Read/Write
`Request
`FIFO
`108f
`
`Transaction
`from ProCeSSOr
`10
`
`Transaction
`from Processor
`12
`
`Lenovo
`Ex. 1027 - Page 6
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 5 of 14
`
`US 6,286,074 B1
`
`120
`
`2iy. Aa
`
`Remote bus
`Manager waits
`for adaptor to request
`aCCeSS to
`remote buS
`
`
`
`132
`
`Remote bridge latches
`information from
`transaction and transfers
`transaction to remote
`transaction Control.
`
`Remote bus manager
`grants access to
`adaptor to assert
`transaction on bus
`
`
`
`
`
`122
`
`136
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Remote bus manager
`notifies remote transaction
`control of adaptor
`driving transaction.
`
`
`
`
`
`
`
`
`
`ls
`transaction
`Write
`op?
`
`No
`
`138
`
`Yes
`
`(42)
`
`Remote transaction Control
`generates a header to add to
`transaction indicationg
`originating device (adaptor)
`and write address.
`
`Queue Write request,
`including header into of
`where to Write and data to
`write in write request FIFO
`for originationg adaptor.
`
`
`
`
`
`
`
`
`
`
`
`
`
`140
`
`128
`
`144
`
`
`
`
`
`
`
`
`
`Discard
`transaction and
`terminate With
`retry to adaptor.
`
`134
`
`Remote bridges
`Snoop remote bus
`for address and
`transaction.
`
`asserted Within
`range handled
`by Snooping
`bridge?
`
`Yes
`
`124
`
`
`
`
`
`126
`
`
`
`
`
`
`
`
`
`
`
`Remote Bridge decodes
`adddress and asserts
`DEVSEL to take Control
`of transaction.
`
`there space
`in write request
`FIFO for adaptor for
`received Write
`
`130
`
`Yes ->(32)
`
`Lenovo
`Ex. 1027 - Page 7
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 6 of 14
`
`US 6,286,074 B1
`
`
`
`Discard request;
`return With
`retry to adaptor.
`
`
`
`
`
`read request
`for address in
`read request
`FIFO?
`
`
`
`
`
`NO
`
`149
`
`156
`
`ls
`return
`Yes
`->K data in FIFO
`dueue?
`
`Determine
`amount to
`prefetch from
`preset amount.
`
`152
`
`Transaction logic retrieves
`requested data from read
`return FIFO for originating
`adaptor, transfers to remote
`PCI bridge, which transfers
`to requesting adaptor; reset
`unsatisfied flag to satisfied.
`
`
`
`(42)
`
`142
`
`
`
`
`
`ls there
`transaction queued
`in read request FIFO
`for adaptor.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NO
`
`Within data
`indow?
`WinCOW
`
`
`
`
`
`
`
`PrOCeSS SRAM
`to determine
`amount of data
`to prefetch.
`
`Transaction logic
`generates a header
`indicating originating
`adaptor, start of read
`address, amount
`of data to read
`
`
`
`
`
`
`
`
`
`Transaction logic queues read request, including
`header information in read request FIFO for
`originating adaptor; flushes the read return FIFO;
`terminates transaction with retry to originating
`adaptor, and reset unsatisfied flag to unsatisfied.
`
`Lenovo
`Ex. 1027 - Page 8
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 7 of 14
`
`US 6,286,074 B1
`
`
`
`176
`
`Local distance interface
`aCCeSSes read return
`FIFO and transferS data
`in FIFO to remote distance
`interface which places
`return data in return data
`FIFO for originating adaptor.
`
`(2
`47. Ac
`
`Remote distance interface
`goes to FIFO dueues and
`transferS queued request to
`local distance interface, which
`places request in appropriate
`queue based on header info.
`
`
`
`
`
`
`
`
`
`Local transaction Control
`processes FIFO buffers 84
`and transfers transaction
`to local PCI bridge.
`
`164 Local bridge places
`transaction On local
`buS.
`
`
`
`166
`
`ls
`operation a
`read?
`
`168
`
`Yes
`
`Save header
`info, wait for
`read data
`
`
`
`17O
`
`Determine header info for read
`data, transfer read data and
`header info to transaction Control.
`
`
`
`
`
`Transaction Control
`processes header information
`to determine FIFO read return
`queue to place return data.
`
`f74
`
`
`
`
`
`
`
`
`
`
`
`Lenovo
`Ex. 1027 - Page 9
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 8 of 14
`
`US 6,286,074 B1
`
`
`
`
`
`
`
`200
`
`Local PCI bridge
`Snoops transaction from
`processor to the other
`processor.
`
`Local bridge latches
`information from transaction,
`terminates transaction with
`retry, and transfers transaction
`to local transaction Control.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Local bridge notifies local
`transaction control identity
`of processor driving
`transaction.
`
`
`
`
`
`
`
`
`
`
`
`
`
`ls
`transaction
`Write
`op?
`
`Yes
`
`ls
`there space
`in read/write request
`FIFO for processor for
`received Write
`request?
`
`
`
`212
`
`Yes
`
`Local transaction Control
`generates a header to add
`to transaction indicating
`Originating processor and
`Write address.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Queue Write request,
`including header info of
`where to Write and data
`to Write in read/write
`request FIFO for
`Originating processor.
`
`
`
`
`
`
`
`
`
`LOCal distance interface
`goes to read/write FIFO
`queues and transfers
`queued request to remote
`distance interface, which
`places request in read/write
`FIFO buffer at remote end.
`
`
`
`204
`
`Remote transaction Control
`processes read/write FIFO
`buffers and transfers
`220-N in transaction to remote PC
`bridge.
`
`
`
`
`
`Remote bridge
`places transaction
`On remote buS.
`
`
`
`
`
`
`
`NO
`
`Discard
`transaction
`and terminate
`with retry to
`the processor.
`
`224
`
`
`
`Transaction transferred
`from remote PCI bridge to
`remote buS 44, and
`handled by other remote
`PCI bridge as discussed
`with respect to FIGs. 4a, b.
`
`Lenovo
`Ex. 1027 - Page 10
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 9 of 14
`
`US 6,286,074 B1
`
`pueOSIC]
`
`ON
`
`öjenenb
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`922
`
`
`
`u? penenb ?senbau
`
`O N8ZZ
`
`
`
`peau ?uÐ??
`
`SI
`
`0 || ?
`
`Lenovo
`Ex. 1027 - Page 11
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 10 of 14
`
`US 6,286,074 B1
`
`
`
`(ego)-No
`
`276
`
`286
`
`ls the
`Start address
`of the requested data
`naturally aligned
`to prefetch
`size?
`
`
`
`
`
`Processor retrieves
`data from storage
`and stores in host
`NO ->
`processor memory in
`Contiguous address
`Space.
`
`
`
`
`
`288
`
`5
`Divide amount of requested
`data in host processor
`memory by prefetch size to
`determine number of prefetch
`Operations for track i.
`
`Set Counter for track i to
`duotient of division operation.
`
`270
`
`Wait to receive
`read request from
`Originating agent
`
`272
`
`ls
`data
`in processor
`memory?
`
`
`
`
`
`Determine the n
`tracks in processor
`memory including
`requested data.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`For tracks i= 1 ... n in
`processor memory do:
`
`-280
`
`
`
`
`
`
`
`Determine Counter
`in SCRAM for ith
`track
`
`Determine amount
`of requested data
`in track i.
`
`282
`
`294
`
`
`
`
`
`COUnter =
`counter 1.
`
`
`
`No
`
`remainder >
`
`295 Yes
`
`
`
`293
`
`Return to agent address
`range of requested data
`in processor memory.
`
`Lenovo
`Ex. 1027 - Page 12
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 11 of 14
`
`US 6,286,074 B1
`
`Set Counter
`
`
`
`3OO
`
`
`
`
`
`3O2
`
`
`
`
`
`3O4
`
`Determine number to prefetch
`in first group to reach aligned
`boundary; indicate first prefetch
`group as this number.
`
`Determine bytes to read after first
`group by subtracting first prefetch
`group from total bytes to read.
`
`Divide: (bytes to read after first
`group)/prefetch size.
`
`
`
`
`
`Set Counter = Counter +
`306 - (quotient of division operation)
`
`
`
`remainder >
`O?
`
`3O8
`
`Lenovo
`Ex. 1027 - Page 13
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 12 of 14
`
`US 6,286,074 B1
`
`32O
`
`
`
`
`
`322
`
`324
`
`Wait to receive
`first component
`read request after
`COUnterS Set.
`
`Terminate with retry.
`
`Place maximum number of read
`requests in read request FIFO.
`330
`LOCal distance interface Waits
`to receive read request.
`
`
`
`
`
`
`
`Remote distance
`interface processes
`read request FIFO
`
`326
`
`Remote distance interface
`transfers first queued read
`request in FIFO to
`local distance interface.
`
`328
`
`Remote distance
`interface Waits to receive
`return data from local
`distance interface.
`
`338
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Local distance interface places
`request in read request FIFO; local
`transaction control transfers queued
`request to local PCI bridge
`
`
`
`
`
`Remote interface
`places returned data
`in read return FIFO.
`
`340
`
`Local PCI bridge obtains
`data and returns to local
`transaction Control to Store
`in read return FIFO.
`
`334
`
`336
`
`
`
`
`
`Local distance interface
`processes read return FIFO
`and transfers to remote
`distance interface.
`
`
`
`
`
`
`
`341
`
`Remote transaction
`COntrol returns
`prefetched data in read
`return FIFO to adaptor.
`
`348
`
`
`
`End
`Queuing
`prefetch
`OpS.
`
`NO
`
`344
`?
`Counter value
`minus number of
`requests in read
`FIFO > 0?
`
`2e2. 7
`
`
`
`Yes
`346
`Add request for next prefetch
`to read request FIFO.
`
`Lenovo
`Ex. 1027 - Page 14
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 13 of 14
`
`US 6,286,074 B1
`US 6,286,074 B1
`
`90
`
`
`
`jsenbeypeey
`
`"Beis
`
`
`
`P8ARSJUSWaIOU]
`
`puessalppy
`
`SSoJpPpYPeay
`
`eyeqpeoyS|
`
`608v9bit,
`
`Jea|D‘ajAq
`
`peysivesun
`
`ejeppuespue
`
`OdldUNjoséAida
`
`
`
`
`
`Wo.a1AqOsisusnjes
`
`SOA
`
`
`
`ssalppypeoy
`
`
`
`peaesyoyew
`
`
`
`‘anjeassouppy
`
`XBWazi/eNiu|
`
`
`
`‘ONn[eASSoJppY
`
`p
`
`
`
`BABSSZIelu|
`
`008g
`
`
`
`
`
`
`
`
`
`… - - - - - => • • - - *- - - - -- - - - - -
`
`SOA
`
`peysiesun
`
`
`
`jsonbeypesay
`
`glesBes
`
`Lenovo
`
`Ex. 1027 - Page 15
`
`Lenovo
`Ex. 1027 - Page 15
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 4, 2001
`
`Sheet 14 of 14
`
`US 6,286,074 B1
`
`enenbpeaS|
`
`éAidwe
`
`SOA
`
`
`
`pacesa0lS
`
`ssolppy
`
`PeSYYIM
`
`ssalppy
`
`ON
`
`bceat
`pueosippue
`
`9}hqByep
`
`WO}a}Aq
`
`Odl4UsN}el
`
`
`
`eyeppesy918
`
`Ue19Oty
`
`OLgjsenbeypeey
`
`
`
`
`
`UINJalJaSeYpeyojejeidasojsPSABSJUBWAIOU|
`(wunsae)=A
`
`‘SsouppyPpaAespueenanb
`
`
`
`18S“OdAlsUINedUlByep‘anjeassaippy
`
`
`pealpuespeasaynoexy
`40}jsonbauluol}e1edo
`
`‘Be|4
`
`poysiesuny
`
`‘Odlas
`
`
`
`ssalJppypares
`
`
`
`XBpeeoxeonjeA
`
`s90q
`
`ssaJppy
`
`Zanjea
`
`cc8
`
`Lenovo
`
`Ex. 1027 - Page 16
`
`Lenovo
`Ex. 1027 - Page 16
`
`
`
`
`
`
`
`
`

`

`1
`METHOD AND SYSTEM FOR READING
`PREFETCHED DATA ACROSSA BRIDGE
`SYSTEM
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`This application is related to the following co-pending
`and commonly-assigned patent applications, which applica
`tions were filed on the same date herewith, and which
`applications are incorporated herein by reference in their
`entirety:
`“Method And System For Prefetching Data in a Bridge
`System,” to Gary W. Batchelor, Carl E. Jones, Forrest
`Lee Wade, U.S. patent application Ser. No. 09/275,857;
`“Read Gather on Delayed Read Requests and Write
`Gather on Posted Write Operations for PCI Agents,” to
`Gary W. Batchelor, Carl E. Jones, Dell P. Leabo, Robert
`E. Medlin, and Forrest Lee Wade, U.S. patent applica
`tion Ser. No. 09/275,603; and
`“Method and System for Multiple Read/Write Transac
`tions across a Bridge System' to Gary W. Batchelor,
`Russell L. Ellison, Carl E. Jones, Robert E. Medlin,
`Belayneh Tafesse, Forrest Lee Wade, and Juan A.
`Yanes, U.S. patent application Ser. No. 09/275,470.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`The present invention relates to a method and System for
`processing read transactions acroSS a bridge System using
`prefetched data.
`2. Description of the Related Art
`The Peripheral Component Interconnect (PCI) bus is a
`high-performance expansion bus architecture that was
`designed to replace the traditional ISA (Industry Standard
`Architecture) bus. A processor bus master communicates
`with the PCI local bus and devices connected thereto via a
`PCI Bridge. This bridge provides a low latency path through
`which the processor may directly access PCI devices
`mapped anywhere in the memory or I/O address Space. The
`bridge may optionally include Such functions as data
`buffering/posting and PCI central functions Such as arbitra
`tion. The architecture and operation of the PCI local bus is
`described in “PCI Local Bus Specification,” Revisions 2.0
`(April 1993) and Revision 2.1s, published by the PCI
`Special Interest Group, 5200 Elam Young Parkway,
`Hillsboro, Oreg., which publication is incorporated herein
`by reference in its entirety.
`A PCI to PCI bridge provides a connection path between
`two independent PCI local busses. The primary function of
`the bridge is to allow transactions between a master on one
`PCI bus and a target device on another PCI bus. The PCI
`Special Interest Group has published a Specification on the
`architecture of a PCI to PCI bridge in “PCI to PCI Bridge
`Architecture Specification,” Revision 1.0 (Apr. 10, 1994),
`which publication is incorporated herein by reference in its
`entirety. This Specification defines the following terms and
`definitions:
`initiating bus-the master of a transaction that crosses a
`PCI to PCI bridge is said to reside on the initiating bus.
`target bus-the target of a transaction that crosses a PCI
`to PCI bridge is said to reside on the target bus.
`primary interface-the PCI interface of the PCI to PCI
`bridge that is connected to the PCI bus closest to the
`CPU is referred to as the primary PCI interface.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,286,074 B1
`
`2
`secondary interface-the PCI interface of the PCI to PCI
`bridge that is connected to the PCI bus farthest from the
`CPU is referred to as the secondary PCI interface.
`downstream-transactions that are forwarded from the
`primary interface to the secondary interface of a PCI to
`PCI bridge are said to be flowing downstream.
`upstream-transactions forwarded from the Secondary
`interface to the primary interface of a PCI to PCI bridge
`are Said to be flowing upstream.
`The basic transfer mechanism on a PCI bus is a burst. A
`burst is comprised of an address phase and one or more data
`phases. When a master or agent initiates a transaction, each
`potential bridge "Snoops' or reads the address of the
`requested transaction to determine if the address is within
`the range of addresses handled by the bridge. If the bridge
`determines that the requested transaction is within the
`bridge's address range, then the bridge asserts a DEVSELif
`on the bus to claim access to the transaction.
`There are two types of write transactions, posted and
`non-posted. Posting means that the write transaction is
`captured by an intermediate agent, Such as a PCI bridge, So
`that the transaction completes at the originating agent before
`it completes at the intended destination, e.g., the data is
`written to the target device. This allows the originating agent
`to proceed with the next transaction while the requested
`transaction is working its way to the ultimate destination.
`Thus, the master bus initiating a write operation may pro
`ceed to another transaction before the written data reaches
`the target recipient. Non-posted transactions reach their
`ultimate destination before completing at the originating
`device. With non-posted transactions, the master cannot
`proceed with other work until the transaction has completed
`at the ultimate destination.
`All transactions that must complete on the destination
`bus, i.e., Secondary bus, before completing on the primary
`buS may be completed as delayed transactions. With a
`delayed transaction, the master generates a transaction on
`the primary bus, which the bridge decodes. The bridge then
`ascertains the information needed to complete the request
`and terminates the request with a retry command back to the
`master. After receiving the retry, the master reissues the
`request until it completes. The bridge then completes the
`delayed read or write request at the target device, receives a
`delayed completion Status from the target device, and returns
`the delayed completion Status to the master that the request
`was completed. A PCI to PCI bridge may handle multiple
`delayed transactions.
`With a delayed read request, the read request from the
`master is posted into a delayed transaction queue in the PCI
`to PCI bridge. The bridge uses the request to perform a read
`transaction on the target PCI bus and places the read data in
`its read data queue. When the master retries the operation,
`the PCI to PCI bridge satisfies the request for read data with
`data from its read data queue.
`With a delayed write request, the PCI to PCI bridge
`captures both the address and the first word of data from the
`buS and terminates the request with a retry. The bridge then
`uses this information to write the word to the target on the
`target bus. After the write to the target has been completed
`when the master retries the write, the bridge will Signal that
`it accepts the data with TRDY# thereby notifying the master
`that the write has completed.
`The PCI specification provides that a certain ordering of
`operations must be preserved on bridges that handle multiple
`operations to prevent deadlock. These rules are on a per
`agent basis. Thus, for a particular agent communicating on
`a bus and acroSS a PCI bridge, the agent's reads should not
`
`Lenovo
`Ex. 1027 - Page 17
`
`

`

`3
`pass their writes and a later posted write should not pass an
`earlier write. However, with current bridge architecture,
`only a Single agent can communicate through the PCI bridge
`architecture at a time. If the PCI bridge is handling a delayed
`request operation and a request from another agent is
`attempted, then the PCI bridge will terminate the Subsequent
`transaction from another agent with a retry command. Thus,
`a write operation from one agent that is delayed may delay
`read and write operations from other agents that communi
`cate on the same bus and PCI bridge. Such delays are
`referred to as latency problems as one agent can delay the
`processing of transactions from other agents until the agent
`currently controlling the bus completes its operations.
`Further, with a delayed read request, a delayed read request
`from one agent must be completed before other agents can
`assert their delayed read requests.
`Current Systems attempt to achieve a balance between the
`desire for low latency between agents and high throughput
`for any given agent. High throughput is achieved by allow
`ing longer burst transfers, i.e., the time an agent or master is
`on the bus. However, increasing burst transferS to improve
`throughput also increases latency because other agents must
`wait for the agent currently using the longer bursting to
`complete. Current Systems employ a latency timer which is
`a clock that limits the amount of time any one agent can
`function as a master and control access to the bus. After the
`latency time expires, the master may be required to termi
`nate its operation on the bus to allow another master agent
`to assert its transaction on the bus. In other words, the
`latency timer represents a minimum number of clockS
`guaranteed to the master. Although Such a latency timer
`places an upper bound on latency, the timer may prematurely
`terminate a master's tenure on the bus before the transaction
`terminates, thereby providing an upper bound on through
`put.
`One current method for reducing latency is the prefetch
`operation. Prefetch refers to the situation where a PCI bridge
`reads data from a target device in anticipation that the master
`agent will need the data. Prefetching reduces the latency of
`a burst read transaction because the bridge returns the data
`before the master actually requests the data, thereby reduc
`ing the time the master agent controls access to the bus to
`complete its requested operation. A prefetchable read trans
`action may be comprised of multiple prefetchable transac
`tions. A prefetchable transaction will occur if the read
`request is a memory read within the prefetchable Space, a
`memory read line, and memory read multiple. The amount
`of data prefetched depends on the type of transaction and the
`amount of free buffer space to buffer prefetched data.
`Disconnect refers to a termination requested with or after
`data was transferred on the initial data phase when the target
`is unable to respond within the target Subsequent latency
`requirement and, therefore, is temporarily unable to continue
`bursting. A disconnect may occur because the burst crosses
`a resource boundary or a resource conflict occurs. Discon
`nect differs from retry in that retry is always on the initial
`data phase, and no data transferS. Disconnect may also occur
`on the initial data phase because the target is not capable of
`doing a burst. In current PCI art, if a read is disconnected and
`another agent issues an intervening read request, then any
`prefetched data maintained in the PCI buffer for the discon
`nected agent is discarded. Thus, when the read disconnected
`agent retries the read request, the PCI bridge will have to
`again prefetch the data because any prefetched data that was
`not previously returned to the agent prior to the disconnect
`would have been discarded as a result of the intervening read
`request from another agent.
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,286,074 B1
`
`4
`Following a read of prefetched data, the bridge typically
`Saves the beginning address of any remaining prefetched
`data stored in the PCI buffer. On the next read request, the
`beginning address of the requested data is compared to the
`Saved prefetched data beginning address. If there is a match,
`additional prefetched data from the PCI buffer is returned to
`the requesting agent to Satisfy the read request. On the other
`hand, if the beginning address of the requested data does not
`match the Saved prefetched data beginning address, the PCI
`buffer is typically flushed to discard all the prefetched data
`and then additional data is read from the target to Satisfy the
`agent's read request. Thus, as long as the agent requests data
`from a Sequential address location which matches the pre
`viously Saved prefetched data address, the need to fetch
`additional data may often be avoided.
`However, in many Systems, data is often wrapped in a
`header which provides certain information about that data.
`For example, in some SCSI systems, a 512 byte block of
`data is preceded by header bytes which identify the logical
`block address and Sequence number and are followed by
`LRC error correcting bytes for data integrity. These 12
`additional bytes of information wrap the 512 bytes of data to
`provide a 524 byte unit of data. If the prefetched data stored
`in the PCI buffer has such header bytes in each block of data,
`the beginning address of any remaining prefetched data
`stored in the PCI buffer will typically point to the beginning
`header bytes rather than the beginning bytes of the 512 bytes
`of actual data. Thus, if the agent attempts to Skip the header
`bytes and read only the 512 bytes of actual data, the read
`request addresses will not be continuous and the beginning
`address of the requested data typically will not match the
`Saved prefetched data beginning address. As a result, the PCI
`buffer will be flushed and the requested data will be read
`from the target device even though the PCI buffer may have
`already possessed prefetched data which includes the data
`being requested by the agent.
`SUMMARY OF THE PREFERRED
`EMBODIMENTS
`To provide an improved bridge System for processing
`requests from multiple agents, the present invention dis
`closes a method and System comprising a bridge System for
`processing read transactions over a bus in which prefetched
`data stored in a buffer is not discarded if the address of the
`requested read does not match the beginning address of the
`prefetched data. Instead, as explained in greater detail below,
`the bridge System skips to the next address of the prefetched
`data Stored in the buffer and compares that address to the
`address of the read request to determine if a match exists. If
`the requested read address does match the next prefetched
`data address, the prefetched data Starting at that next address
`is read out and forwarded to the requesting agent.
`Alternatively, if there is not a match, the bridge skips again
`to the next address and continues checking for a match until
`either the buffer is exhausted or another predetermined limit
`has been reached. In this manner, many unnecessary data
`reads of data already prefetched in the buffer may be
`avoided.
`Preferred bridge embodiments include a read return buffer
`for each transacting agent. In this way data prefetched in
`anticipation of a read transaction is Stored in a read return
`buffer corresponding to the agent. Thus, each transacting
`agent may concurrently maintain prefetched read data in the
`bridge System of the preferred embodiments. These pre
`ferred bridge embodiments provide further improvements
`over the PCI art because if an agent disconnects before
`reading returned data maintained in the read return buffer for
`
`Lenovo
`Ex. 1027 - Page 18
`
`

`

`S
`that agent, the disconnecting agent may retry the read and
`read the data previously stored in the read return buffer. With
`the preferred bridge embodiments, an intervening read
`request from a different agent would not flush the discon
`necting agent's read return buffer as the intervening read
`request would utilize the return read buffer for the agent
`originating the intervening read transaction. The preferred
`bridge embodiments do not have to re-assert the read
`transaction to the target device because read or prefetched
`data is maintained in the read return buffer until read by the
`originating agent or upon the disconnecting agent providing
`an intervening read request.
`
`BRIEF DESCRIPTION OF THE FIGURES
`Referring now to the drawings in which like reference
`numbers represent corresponding parts throughout:
`FIG. 1 illustrates a preferred embodiment of the hardware
`configuration of the bridge and failover Subsystems in
`accordance with the present invention;
`FIG. 2 illustrates a preferred embodiment of the hardware
`configuration of a portion of the bridge Subsystem illustrated
`in FIG. 1;
`FIG. 3 illustrates FIFO buffers used to queue and process
`in parallel transactions and return data for the transactions
`originating from different agents in accordance with pre
`ferred embodiments of the present invention; and
`FIGS. 4a, b, and c illustrate logic implemented in the
`bridge Subsystem to process transactions from multiple
`agents in accordance with preferred