(12) United States Patent
`Strongin et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,546,439 B1
`Apr. 8, 2003
`
`US006546439l31
`
`(54) METHOD AND SYSTEM FOR IMPROVED
`DATA ACCESS
`
`(75)
`
`Inventors: Geoffrey S. Strongin, Austin, TX (US);
`Qadeer A. Qureshi, Round Rock, TX
`(US)
`
`(73) Assignee: Advanced Micro Devices, Ine.,
`Sunnyvale’ CA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(1)) by 0 days.
`
`( * ) Notice:
`
`(21) Appl‘ NO’: 09/207370
`(22)
`Filed;
`Dec, 9, 1998
`
`Int. Cl.7 .............................................. .. G061? 12/00
`(51)
`(52) U.S. Cl.
`....................... ., 710/52; 711/147; 711/154;
`711,167
`,_
`_
`,
`’
`(58) held 01 5ea1‘7c1h1
`,
`,
`,
`’
`,
`,
`,
`,
`«
`155, 157, 159, 217, 218; 710/5, 5, 35, 39,
`52
`
`(56,)
`
`References Cited
`,
`U~S- PAH’-‘NT DOCUMENTS
`.305], 89
`4,796,232 A
`1/1989
`V,
`_ 395/485
`,
`5,440,713 A
`8/1995 Lin et al,
`_ 395/478
`5,509,135 A
`4/1996
`(0,-ekata et at
`. 395/481
`5,630,096 A
`5/1997 Zuravleif et al.
`- 395/481
`5,565,494 A
`9/1997 M013, -I11
`> 711/ 05
`5,745,913 A
`4/1998 1,3111“ 9‘ “L
`'
`5,751,700 It
`55551‘: ‘’‘1]‘,‘1
`’
`" /
`’,
`,,
`5’76.1’708 I
`’ C“ 5””
`5,7<,s,53n A
`6/ 1998 Sandorh
`_ 7“/. 5.1
`5 781927 A ,,
`7/.1998 Wu
`, 395/2./,7
`5:784:582 A
`7/1998 wghes
`,711/ 51
`5,360,117 A
`1/1999 C1161-abuddi,
`.711,’ 67
`5,920,898 A
`7/1999 Bolyn etal.
`. 711/5
`0,020,464 A
`2/2000 Cohen ..
`
`- 370/428
`4/2900 <9“ 913-
`5,047,001 A
`- 711/: 3;
`5,065,291 A *
`7/2000 119193‘ 31-
`' 711’,
`4.1
`6iU”2‘156 A
`7’,2000 schllmlgel et a1’
`6’092’l58 A
`7/2000 hnmfln 91 M’ """"" " 711’ 31
`0,104,417 A
`8/2000 Nielsen et al.
`............ .. 345/521
`6,112,265 A '
`8/2000 Iarriinan el al.
`710/40
`. 711/ 63
`6,173,375 B1 *
`1/2001
`lozario ....... ..
`
`
`
`
`_
`.
`
`
`
`--
`
`1/12001 Rozario ct al.
`6,173,378 B1 "
`6/‘Z001 Rozario et al.
`6,233,262 B1 :
`<)/2001
`Jeddeloh ..... ..
`5,295,592 B1 "
`OTHER PUBLICATIONS
`
`.,
`.. 711/163
`
`/10/39
`.. 711/16‘)
`
`Intel Corporation, Accelerated Graphics Part Interface
`Specification, Revision 1.0 (Jul. 31, 1996), pp.
`ii—x and
`_
`1”,151~
`,
`Mike Johnson, Superscalar iM1,cr0pr0ces,§nr Design, 1991,
`pp. 87, 233—235.
`Random House, Inc., Webstefs American Dictianay—Cal—
`,
`.
`_
`[egg Edman’ 1997’ P’ 863‘
`* cited by examiner
`Primary Exanziner—Matthew Kim
`Assistant Exa/niner—C. P. Chace
`(74) Attorney, Agent, or Firm—R. Noel Kivlin
`
`(57)
`
`ABSTRACT
`
`A method and system which will increase the ability of
`memory controllers to intelligently schedule accesses to
`systemumemoiry. The methjod and system proviie pfmemory
`contro er an
`a requeste memory operation u or struc-
`tured so that at least one source attribute of a requested
`memory operation can be identified. In one instance, the
`requested memory operation buffer has queues, associated
`with data buses, which can be utilized to identify source
`attributes of requested memory operations. Examples of
`such queues are an Accelerated Graphics Port Interconnect
`queue associated Vs’iI1l’)1 an Accelerated dGrap1hics Port
`interconnect, asysteni us queue associate wit
`a system
`bus, and a Peripheral Component Interconnect bus queue
`associated with :1 Peripheral Component Interconnect bus
`where the queues can be utilized by a memory controller to
`identify the specific bus from which a requested memory
`operation originated. In another instance, the queues, asso-
`ciated with data buses, are structured such that one or more
`fu h
`.b
`h
`h .d
`.
`,
`f h
`,
`rt, er source attri utes—suc ast ei entity 0 t e request
`initiator, ‘the priority ot the request, whether the request is
`speculative, etcetera—0t particular queued requested
`memory operations can be identified.
`In yet another
`instance, the requested memory operation butler is struc-
`tured such that one or more source attribiites—siich as the
`identity of the request initiator, the priority of the request,
`Whether the request is speculative, etcetera—of particular
`ueued re uested meiiior o erations can be identified
`“1
`‘1
`Y P ‘
`*
`~
`32 Claims, 6 Drawing Sheets
`
`.
`1;‘
`
`‘
`
`J*°"ie°1,
`:3
`ta.../v.._,...«a
`
`Memcry.yeva|K/r
`comm;-ls
`zw?
`
`: ‘,
`114 W
`115 '
`can \Aen
`A.”,P—EnahledNonhtfldqz14
`ge
`"""”"“
`“WE,
`“‘”““"”“'*“
`
`-
`
`mp.
`fifi
`
`M223
`Mer1a'v0psr.~1tto1
`,
`fig“
`tso
`
`I52
`
`W
`_”t;lE?,‘,”i!L‘2i§§“‘
`M,,,0,yg,,,,,,m
`c".‘,‘*t”m",”v “SW
`
`154
`
`’»‘iL‘S“,2“2ZliiJ§’
`ME,,.,,,,o,.,mn
`'éi“‘lu’
`
`t
`64 c”,::':;:.i Mmvvm-vim
`,,
`,
`'~'=u= MEESW %
`”"‘M°“‘¥.
`:ai'"m1’s
`t-§$°2"a’
`t,..m,n,.,,m.,, fl /»cnecs2
`-300
`L3 -959‘
`Cnljmnl Rowzu
`302 Mammy
`‘goo
`recwmagez
`um,_ Memory m,
`cm
`war
`“
`Merrnry pernttor — Amesaz
`Fmm“
`m
`zmm 7
`~02
`w»=:_a«
`::;::g:?
`;Gr:,;=.:* K 1,,
`C'§L§Cf°7I§§§Z7, M,” 1 7””
`Paw
`“E
`Mamnrycpelztkm
`V
`-
`,-zoo
`134
`imn'
`=
`Em)’
`em:
`,3,
`emcv
`‘
`dflifi/Efifiiwfinifiél
`"M5-‘
`may
`ilaillllé M§$L,”l’
`73:9;
`r‘~?3.
`‘S00
`N vtumrycmam 2 i¢?l=1”,’z
`g
`Sou\h|7llda?T N315,“
`ruéfiitlzliisa
`C/l;l:'r‘7-»'iA::c:E:idst
`-125
`Vletnrvfinrwtltnn
`Memnryopavaton
`12
`my
`-'27
`'?§,'“t’4'
`c,i°."m‘Zys
`R1'“w“Q
`
`0001
`
`Volkswagen 1001
`
`0001
`
`Volkswagen 1001
`
`

`
`U.S. Patent
`
`Apr. 8, 2003
`
`f.ee.hS
`
`6fl0.1
`
`US 6,546,439 B1
`
`
`
`
`
`
`
`
`
`cozswao>.oEm_>_:o_§8o.coEm_2coasmao.3522:o_§&o3252cozfimao.coEm_2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EEEEEIcozflmao.¢oEm_2zozsmaoroam:cozflmaoboEws_
`
`
`I.oN;omF=E:_oooN_sommceaoooNz5mmEs_oo
`
`
`
`
`
`
`
`om2___ofig>_oEw_2FBE22bogs..coEms_boEm_>_boEm_>__2<mn_
`
`
`
`
`
`
`
`
`
`a:beam:seam.B_%__m-n5<F$m8<Nm$8<mwwm8<
`
`:oEm_>_DuoboEm_2DuoboemzP6
`
`Illllg
`
`lg-13
`
`. umzmcm
`
`
`
`.\.2 .__§_.§m__.__n_fi.59co
`
`
`
`
`
`mommnssom_mFw=Fmmm%m___.F338$RamNE35.ummmmfioauomummm2.mm_._cow_ummmmommn_;>om
`
`
`coaemqom___&ms_ b.oEo_>_am
`
`
`
`
`
`
`
`
`
`
`.Fmmmmuso.I|5oEm_>_.¢oEms_boEms_hoses._coEm_>_roEo_>_
`
`
`
`
`
`
`
`
`
`
`
`.Fmmmniso.cozsmao.coEms_cozflmaoboemzcozmcmqo.coEms_
`
`
`
`
`
`
`
`%“IE
`
`NNF
`
`8_>oo
`
`E
`F.\
`
`xazozSF838gm_on_NB8_5oam_on_EF838gm_on_
`
`
`
`Emu¢mmFmmu_._e=:owFw$8<boEms_Nmmm8<aoEm_2mmm8o<>552).
`
`
`
`
`
`
`
`Eco£0202285%:8_>on_$2SE53?8_>mo$2
`
`
`
`
`
`€222roEm_>_roEm_2>_oEm_2.coEm_2EoEm_>_boEm_2boEm_>_boEm_>_.:oEm_2Nmmm8<
`
`
`
`
`
`
`msommcE=_oomsomm:E=_oovsomv:E:_oOYsomm=E=_ooF;>omN:E=_oo
`
`
`
`
`>_oEm_>_Fm$8<boEm_>_mmmw8<boEo_2Nmw8o<.coEm_>_Fmmm8<boEm_2
`
`mNFcozflmaoboemzcozfimaoEQE22cozfimaoboEm_>_NgemF=E=_ooow25¢m:E=_oowNaomF:E=_oo
`
`
`
`
`
`
`
`NNF.coEo_2toe»:.¢oEms_boEm_>_FBE22:25:
`
`
`
`
`
`0002
`
`

`
`U.S. Patent
`
`Apr. 8,2003
`
`Sheet 2 of 6
`
`US 6,546,439 B1
`
`._8._8Elfl
`
`o.-
`O
`
`
`
`8:930.coEm_>_m_mu%m_w_,_m>..__%__am_Un_»q_.V
`
`
`
`
`
`
`
`
`
`.oI_..—.boEm_2Emiw.m__m%mooa5.5m_a_§8o
`
`
`
`826¢Ncsaoom$823&5s_<«_o>._oEo_2boEm_2boEu_2Duo
`
`boeozaoEm_>_uofiozcmm
`
`
`
`
`
`m%__£Ez8_%.m.n_o<
`
`wmmn=26m5:230
`
`
`
`
`
`.¢oEm_>_Nmmmntzomm25¢N:=s_oo_wmmmiomboEm_>_boEms_:o_.E8oboEms_
`
`
`
`
`
`
`
`Illil
`
`
`
`.Vm.mmn_=so.=o_§8o
`
`III
`I-I
`I:I
`-I
`
`
`
`
`
`.Fmmmnfiso.boEos_.¢oEms_
`
`.._mmmn=>>om_vBoamcE:_oO
`
`
`
`:o_.Eon_oroam:
`
`
`
`boEms_boemz
`
`
`
`=o_.S.naorose).
`
`m:
`
`
`
`
`
`
`
`boEms_>_oEm2boEm_220,52boEm_2.¢oEm_>_mm?¢.w.m>mwrn_mN_boEms_ Nmmm8<
`
`
`
`
`
`
`
`cozfimqo>._oEms_cosmaao.¢oEm_>_=o_Hm_8oEoEw_>_mm_.couemqo>_oEm_>_=o_§8oboEo_2mgemo=E=_oowgemmE.s_oo¢aomw:E=_ooowaommcE=_oowN251Nceaoo
`
`
`
`
`
`
`
`
`.¢oEms__.w$8<.¢oEo2mmmm8<boEms_ mmu_5£_5mNwmw8<eoemémwm8o<beam:
`
`28Eémz28E5283839V_EzNm_.8_>on_mam_on_3.8_>8as_on_
`
`
`
`
`boEm_2Pomanfiso. SE30.coEms_cozmaqoboEms_
`
`
`
`
`
`
`35:0.>._oEms_.coEms_momwmzfi>_:o:.__.:m_.._».\_..moacwmz&_o:._==m_w._w,_u
`
`
`
`
`
`
`
`
`ommmiom.¢oEm_>_.¢oEm_2
`
`oamméomNaom_E.s_oo8__aEo11/_.o_
`
`
`mmm%so~_=o_§8otoEm_>_$%~m_u<N9N9
`
`
`
`
`
`
`
`
`
`
`%mn_EoxboEo_>_teem:m=_&m_>_.|
`
`
`ismNceaooosflRamn_O<ummmn_o<mmmmxaom8:930roams.addmmmzém2am:ammmmasom
`
`0003
`
`

`
`U.S. Patent
`
`Apr. 8, 2003
`
`Sheet 3 of 6
`
`US 6,546,439 B1
`
`__8._8ooannual
`
`lllllg
`
`Illllg
`
`Illllg
`
`Illllg
`
`IllllgEIIIIIE
`
`IIIIIE
`
`IIIIIE
`
`Illllg
`
`IIIIIE
`
`IIIIIE
`
`IIIIIE
`
`meeboEw_2E296
`
`omZ_._o_>_<E
`
`Emo5252
`
`
`
`Nmmw8<boEms_
`
`28E232
`
`
`
`Fm88<boEms_
`
`8_>mo32
`
`
`
`mmwm8<.:oEm_>_
`
`
`lllllg %
`boEms_mroam:omcE:_ooNw88<cozmmao
`
`
`
`838E?
`
`
`
`beams.:n_o
`
`..m88<
`
`umomn_o<
`
`roam:O3
`
`Fmmouo<
`
`8_>852
`
`boEm_2
`
`_....wm8<
`
`.:oEm_2Duo
`
`amN882
`
`8%n_o<
`
`
`
`coafimaoboEm_2
`
`
`
`cozfimaoboEm_2
`
`
`
`boEms_>._oEm2
`
`
`
`cozfimgo>._oEms_
`
`
`
`coafimaoboEms_
`
`
`
`.coEw_>_boEm_2
`
`Nuozcmmagemm:E=_oo
`
`
`
`
`
`
`
`flkwtsmcozfimqo.coEms_ugmmscmm
`
`
`
`
`
`
`
`
`
`zoEm_>_ boEm_>_ roam: RFEmum.nV.m..>morn_NN_,:oEa_>_boEm_2beam:boemz
`
`
`
`m.%__e_sow
`
`
`
`
`
`Nmmm8<EoEm_2mmwm8<boEw_2
`
`
`
`roEm_2boEm_>_
`
`ON261N:E=_oo
`
`
`
`boEm_>_bosmz
`
`maomNcE=_oo
`
`Nsom_=E=_oo
`
`
`
`roams.coEm_>_
`
`«sexN:E:_oo
`
`
`
`bozo:boEm._>_
`
`boEms_8Exms_s_8
`.2230
`
`8:590
`
`w$_uu<
`
`.01
`
`m=_&m_>_.
`
`2.5
`
`we
`
`
`
`am%_§_EzB_%:m.n_o<
`
`N9
`
`N9
`
`4/x:
`
`
`
`boemz>_oEws_roam:roam:m.$_a&Rom
`
`2$2.81ummm
`
`
`
`
`
`
`
`
`
`:o_§8o.coE¢s_
`
`
`
`=o_§8obeams.
`
`
`
`mzomF=E=_oo...mzomm:E:_oo
`
`m:
`
`N9838gm.8E838am_on_
`
`
`
`
`
`
`
`
`
`
`
`cosfloqoboEm_2cozmaaoboEm_>_=o_§mn_oroEm_>_mm_\:o_.Emao5oEos_cozsmqobeam:
`
`
`
`
`
`
`
`
`
`
`
`0004
`
`

`
`U.S. Patent
`
`r.pA
`
`30028:
`
`Sheet 4 of 6
`
`US 6,546,439 B1
`
`5%:E0
`
`Fmmm8<
`
`=o_.umm:E._.B559:
`
`$90
`
`2;%mE%__
`
`$m8<9:2
`
`om>__m_83m
`
`8%n_o<
`
`?.$_..c$.._
`
`cozommcmfiS.6=m93
`
`.590
`
`2;%m:8E_
`
`883.me.u._
`
`m.o>_§=8qw
`
`o3833aman.
`.6Same:
`
`
`
`_m$8<boEm_>_
`
`cozommcmfi
`
`EEO
`
`2;%§8e_
`
`wmm8<ms2
`
`n..m>=m_:ooam
`
`8_>mn_$9
`
`
`
`Fmmw8<boEm_>_
`
`zozommcmfiB.G:mm5
`
`._mv._O
`
`2;%s_aE_
`
`m$8<me2
`
`%>_a_=o8m
`
`35;.2%
`
`Nm$oo<
`
`_o.G:om._:
`
`cofimmcmfi
`
`$90
`
`z;%mEaE_
`
`mwm8<9:m_
`
`mw>_.m_=umam
`
`83852
`
`
`
`wmmw8<>._oEa_2
`
`:o_.o$cS._.B.8cmm5
`
`EEO
`
`2;%mc8E_
`
`mwm8<9:m_
`
`%>__m_:o8m
`
`cozommcmc.B>o:mm5
`
`.85
`
`z;...=§§_e_
`
`$83.2:m_
`
`A_.w>__m_33w
`
`
`
`omsomboEm_>_N:E=_oobeam:
`
`
`
`coamaaoaoEm_>_
`
`
`
`cozmaaoroam:
`
`
`
`asex.coEm_>_N:E:_oo.¢oEm._>_
`
`
`
`co_.E8o50:55.
`
`
`
`Naom.¢oEms_FcE:_ooboEm_>_
`
`
`
`:o_§8oaoEo_>_
`
`
`
`VBoxboemzN:E:_ooboEms_
`
`
`
`om26m2253.m55.00aoEms_
`
`
`
`cozfimaoboEm_>_
`
`
`
`cozmaaoboEm_>_
`
`maom>._oEm._>_m::5_oo2955.
`
`
`
`:o_§8oaoEm_>_
`
`
`
`v26¢.¢oEos_mcE=_ooboEms_
`
`
`
`m.mm.£.5mcozfimaoaoEm_>_uewmzcmm
`
`
`
`
`
`0005
`
`

`
`U.S. Patent
`
`Apr. 8,2003
`
`Sheet 5 of 6
`
`US 6,546,439 B1
`
`I
`IIIIIIIIIII
`I'll...
`I'll...
`I'll...
`II...
`
`OE
`
`
`
`
`
`I:mmmnzzo.:o=m.maOboEm_>_...cozmsaoboEws_
`
`
`
`
`
`maom_:E=_oomzoxm:E_.._oo
`
`
`
`
`._o__ooo_o|o8_§8o.coEm_>_:o_.Emaohose:5Q20_2<momb._n_.::_oo»._NSexm.m..E:_oo~m._N25m
`
`
`
`
`Nmmmnfisomcozsmao.coEos_EHI52E2
`
`
`
`l9.5252:0E09.—aoEm_2Emiw.22m_>_mm8o<2
`
`
`
`N3%u_a£az8_nsm_.n_o<282,.2%
`
`m:
`
`.mm_Newmmmmaiom$9%<N?I0énséam?¥_,:._m_.m,.s_,_§m_.__fi..__.fiwIVmmisomcynmcm
`mmmmnzgomfFor.n_o<
`
`
`
`
`
`
`
`
`>._oEws_mmmmnssomaoEm_>_.¢oEm_>_o_nm._.ummmn_o<cmmmao<Em___&§IINmn:omco_§on.o
`
`
`
`
`
`
`
`
`
`
`
`boEw_>_.coEms_5%:roe»:22.5220:5232roams.28.2).boEo_>_>._oEo_2
`m25¢o:E=_oom261m:E=_oovaomV:E2ooKr8_>mn_N3owgemm:E:_oowNgemN:E=_oo
`
`
`
`
`
`
`
`
`cozemao.¢oEo_2coaemao>_oEms_cozfimaoboEms_mN_8:980beam:co_§$oboEm_>_
`
`
`
`
`Nw$8<rose:_,$m8<boEms_mmmm.8<boEos_v_._w.v._>mMzmmu_5£=owNmmm8<.coEm_2mmmw8<teem:
`
`
`28E20228eosmz83832N28_>mn_2m6;v2838maman.
`
`
`
`roam:boEm_2
`
`
`
`
`
`_._o_§8o.¢oEo_2co__«m.mn_oBose:
`
`
`
`
`
`
`boEm_>_aoemzaoEms_2255.
`VzamN=E:_ooNaom_:c.s_oo
`
`
`
`cozfimaoroam:
`
`v26¢mcE:_ooNE
`
`0006
`
`

`
`U.S. Patent
`
`Apr. 8, 2003
`
`fl06teehS
`
`/0
`
`US 6,546,439 B1
`
`musmo
`
`oEw_2
`
`
`
`
`
`f%mwo_\.«=o_§8oboEm_>_fm%%_%«E=o_§m._oboEm_>_
`8_>ma+.25xN:E:_oOom?Ngem«=E=_oo
`
`
`32base:roam:am_on_5252beam:
`
`mmm._.
`
`oom
`
`
`
`
`
`
`
`
`
`boemzboEms_boEm_>_.¢oEms_boEms_.:oEws_$2.boemzboEo_2boEos_boEos_
`
`
`
`
`mzomm:E:_oomzsmm:E=_oovaomv:E=_ooNNF8_>ooNNFQisomm=E=_oomN2,om_Nceaoo
`
`
`
`Nm$8<>_oEo_2.$82beam:mm$8<.coEms_v___nu..>m_nmzomn_5£=owNmmm8<.coEm_>_mmwm8<29$:
`
`
`Emuv_._o>B0ZEMU¥_o>ZwZ8_>mo$2N9.mo_>mDSm_Un_«Ewo_>oDmam_On_
`
`
`
`
`
`m—.F
`
`
`
`
`
`
`
`cozfimaoboEm_2:o__Son_oboemz
`
`
`
`roams.oNzomNcE=_oo
`
`
`
`Eoteem:>_oEm_>_
`
`N$82§_m§_o35.2.%<
`
`_8_§m_
`
`8_%_m._o
`
`_m__9Eoo
`
`
`
`
`
`
`
`:$=$m..o_2amm25¢N:E=_oommm:U_o<
`
`ummm10¢..CoEwEboEos_moEqm5NS
`
`
`
`ummmn_o<boEms_.coEo_>_m3m._.mfiwaummz.323
`
`
`
`Nmm:mmm25¢m=E=_oo%roam:.5522teem:>._oEm_>_
`
`co_E8boeom:_%_ms_3%%<Ewmn_o<
`
`
`
`
`
`Nmmm8<coaemaoaoemz
`
`
`
`
`
`_coEms_oNaomm=E=_oo:o_§3o>_oEms_
`
`IIa382
`
`V3m%__e.Ez8_§m-%<rose:30
`
`
`
`
`
`boEm_>_.¢oEm_>_
`
`
`
`
`
`
`
`
`
`co_§m._oboEws_cozewaobeam:cozemaoroam:mme:o_.Em._oboemzcozmmaoboEo_>_
`
`
`
`
`
`
`
`
`
`0007
`
`

`
`US 6,546,439 B1
`
`1
`METHOD AND SYSTEM FOR IMPROVED
`DATA ACCESS
`
`CROSS-RI:'l~'EREN CE
`
`The present invention is related to subject matter dis-
`closed in the following co-pending applications:
`1. United States patent application entitled “Method And
`Sys em For Origin-Sensitive Memory Control And
`Access In Data Processing Systems”, Ser. No. 09/208,
`305 filed Dec. 9, 1998, naming Geoffrey S. Strongin
`and Qadeer A. Qureshi as inventors;
`. Uni ed States patent application entitled, “Method And
`Sys em For Generating And Utilizing Speculative
`Memory Access Requests In Data Processing
`Sys ems”, Ser. No. 09/208,569 filed Dec. 9, 1998,
`naming Geoffrey S. Strongin and Qadeer A. Qureshi as
`inventors;
`. Uni ed States patent application entitled, “Method And
`Sys em For Destination—Sensitive Memory Control
`Anc Access In Data Processing Systems”, Ser. No.
`09/208,522 filed Dec. 9, 1998, naming Geoffrey S.
`Strongin and Qadeer A. Qureshi as inventors;
`. Uni ed States patent application entitled, “Method And
`Sys em For Page-State Sensitive Memory Control And
`Access In Data Processing Systems”, Ser. No. 09/207,
`971 filed Dec. 9, 1998, naming Geoffrey S. Strongin
`and Qadeer A. Qureshi as inventors; and
`. United States patent application entitled, “Method And
`System For Memory Control And Access I11 Data
`Processing Systems”, Ser. No. 09/208,570 filed Dec. 9,
`1998, naming Geoffrey S. Strongin and Qadeer A.
`Qureshi as inventors.
`In accordance with 37 CFR §1.121(b)(1)(iii), Appendix B
`contains marked up versions of the replacement paragraphs
`illustrating the newly introduced changes in the specifica-
`tion.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates, in general, to a method and
`system to be utilized in data processing systems.
`In
`particular,
`the present invention relates to a method and
`system to be utilized in data processing systems wherein, for
`non-limiting example, a memory controller is utilized.
`2. Description of the Related Art
`Data processing systems are systems that manipulate,
`process, and store data and are notorious within the art.
`Personal computer systems, and their associated
`subsystems, constitute well known species of data process-
`ing systems. Personal computer systems in general and IBM
`compatible personal computer systems in particular have
`attained widespread use for providing computer power to
`many segments of today’s modern society. Apersonal com-
`puter system can usually be defined as a desk top, floor
`standing, or portable microcomputer that includes a system
`unit including but not limited to a system processor and
`associated volatile and non-volatile memory, a display
`device, a keyboard, one or more diskette drives, one or more
`fixed disk storage devices, and one or more data buses for
`communications between devices. One of the distinguishing
`characteristics of these systems is the use of a system board
`to electrically connect these components together. These
`personal computer systems are information handling sys-
`tems which are designed primarily to give independent
`computing power to a single user (or a relatively small group
`
`2
`of users in the case of personal computers which serve as
`computer server systems) and are inexpensively priced for
`purchase by individuals or sn1all businesses.
`A computer system or data-processing system typically
`includes a system bus. Attached to the system bus are
`various devices that may communicate locally with each
`other over the system bus. For example, a typical computer
`system includes a system bus to which a central processing
`unit (CPU) is attached and over which the CPU communi-
`cates directly with a system memory that is also attached to
`the system bus.
`In addition, the computer system may include a peripheral
`bus for connecting certain highly integrated peripheral com-
`ponents to the CPU. One such peripheral bus is known as the
`Peripheral Component Interconnect (PCI) bus. Under the
`PCI bus standard, peripheral components can directly con-
`nect to a PCI bus without the need for glue logic. Thus, PCI
`is designed to provide a bus standard on which high-
`performance peripheral devices, such as graphics devices
`and hard disk drives, can be coupled to the CPU, thereby
`permitting these high-performance peripheral devices to
`avoid the general access latency and the band-width con-
`straints that would have occurred if these peripheral devices
`were connected to a low speed peripheral bus. Details on the
`PCI local bus standard can be obtained under the PCI Bus
`Specification, Revision 2.1, from the PCI Special Interest
`Group, which is hereby incorporated by reference in its
`entirety.
`Two relatively high-bandwidth types of traffic that are
`communicated to and from system memory are 1394 device
`traffic and networking traffic. The 1394 device traffic origi-
`nates within a high speed serial device which communicates
`with the system through and over a Southbridge. The
`networking traffic originates within a network card which is
`reading network traflic information, regarding one or more
`networks of which the data processing system is a part, from
`a network buffer.
`
`techniques for rendering three-
`Relatively recently,
`dimensional (3D) co11tinuo11s-animation graphics have been
`implemented within PCs which have exposed limitations in
`the originally high performance of the PCI bus. The AGP
`interface standard l1as been developed to both (1) reduce the
`load on the PCI bus systems, and (2) extend the capabilities
`of systems to include the ability to provide 3D continuous-
`animation graphics with a level of quality previously found
`only on high-end computer workstations. The AGP interface
`standard adds an additional bus to data processing systems:
`the AGP Interconnect. The AGP interface standard is defined
`by the following document: Intel Corporation, Accelerated
`Graphics Port Interface Speczfication, Revision 1.0 Jul. 31,
`1996).
`The AGP interface standard reduces the load on PCI bus
`systems and extends the capabilities of systems to include
`the ability to provide 3D continuous-animation graphics via
`a rather indirect process. Under the AGP interface standard,
`a CPU independently processes the geometric and texturing
`data (geometric and texturing data are data necessary to
`properly define an object to be displayed) associated with
`each object
`to be displayed in a scene. Subsequent
`to
`processing the geometric and texturing data, the CPU writes
`the geometric and texturing data back into system memory.
`Thereafter, the CPU informs a graphics processor that the
`information is ready, and the graphics processor retrieves the
`information from the system memory.
`In current
`industry architectures, each preceding dis-
`cussed bus (e.g., the system bus, the AGP interconnect, and
`
`0008
`
`

`
`US 6,546,439 B1
`
`3
`independently articulate with the system
`the PCI bus)
`memory through a device known as the Northbridge. The
`various communications with, or accesses of, system
`memory are generally controlled by a device within the
`Northbridge known as a “memory controller.”
`A memory controller controls system memory which is
`typically a collection of Direct Random Access Memory
`chips (DRAMs). The computer system memory, composed
`of DRAMs, can store data, but there is conventionally no
`intelligence in the system memory. The intelligence con-
`cerning how data is going to be stored, where the data is
`going to be stored, how the data is going to be read or
`written, etc., is provided by the “memory controller.”
`The memory controller controls access to system
`memory, which as has been noted is typically composed of
`DRAMs. ADRAM can be thought of as a collection of cells,
`or storage locations, wherein data is stored. For simplicity it
`will be assumed here that each cell stores a byte, but those
`skilled in the art will recognize that other storage sizes are
`possible.
`When a memory access, such as a read cycle, is engaged
`in, the memory controller is given an address by another
`device, such as a graphics controller. That address needs to
`correctly specify one of the cells where data is actually
`stored. Ordinarily, cells within DRAMs are arranged in row
`and column format (i.e., the cells are arranged like a matrix).
`Consequently, an address, which for sake of illustration
`will be assumed to be 16 bits long, customarily is conceived
`of as being composed of two parts: a first 8-bit portion of the
`address which is associated with a row address, and a second
`8-bit portion which is associated with a column address
`(again, the bit lengths are hypothetical and merely utilized
`here for illustrative purposes). This fragmentation of the
`address into row and column portions allows the address to
`correctly specify a storage location, or cell, by its row and
`column.
`
`Conventionally, a DRAM has at least two buses, or at
`least hypothetically what can be treated as two buses: a data
`bus, and an address bus. To minimize DRAM hardware, it is
`customary that the address bus be only half as wide as the
`address bits required to uniquely identify a data cell. The
`foregoing is done in order to minimize the number of pins
`on the DRAM, which those skilled in the art will recognize
`is a major constraint or limiting factor on how small one can
`make a DRAM chip. Due to this limitation on the width of
`the address bus, memory access is typically achieved by first
`placing the row portion of the address on the address bus,
`which will select the appropriate row, and second, a short
`time later, placing the column portion of the address on the
`address bus, which will select the appropriate column. This
`then correctly specifies the row and column location of the
`storage location that is desired. At some time after the row
`and column information have both been specified, the data
`from the memory location specified by the row and column
`address appears on the DRAM data bus.
`From the foregoing, it can be seen that in order to make
`a single memory read access there are three phases: a row
`address phase, a column address phase, and a data retrieval
`phase. In the past, it was noticed that typical programs tend
`to operate sequentially, so if there is a memory address
`accessed, it is likely that the next memory address accessed
`will be the very next cell, which means that the column
`address is likely to change, while the row address is not
`likely to change. Consequently, typical DRAMs are struc-
`tured such that once the row address has been driven,
`thereafter the DRAM responds to new addresses on the
`
`4
`address bus as if those addresses are column indicators, and
`thus will use such addresses as column addresses within a
`current row 11ntil the DRAM is notified that a new row
`address will be appearing on the address bus. DRAM
`devices using this scheme (driving the row once and then
`operating upon columns within the row) are known in the art
`as “page mode” DRAMs.
`in the event that a memory
`In light of the foregoing,
`controller has several memory accesses to be done
`sequentially, then once a page is open it makes sense from
`an efficiency standpoint
`to examine pending as well as
`current memory accesses in order to determine which of
`those pending memory accesses will be to memory locations
`that are within a currently open page (that is, the row of the
`request
`is the row from which a memory controller is
`currently reading within a DRAM). In other words, assum-
`ing a page X is open, if there are four memory accesses A,
`B, C, and D, waiting to be performed, and assuming the first
`access A is to page Z, the second access R is to page X, the
`third access C is to page Y, and the fourth access D is to page
`W, it is preferable from a memory efficiency standpoint that
`the data access (i.e., access B) appropriate to the page that
`is open (i.e., page X) be made first.
`Current memory controllers already “look ahead” to see if
`pending memory accesses are destined for currently open
`pages. Furthermore, at any given time, typically more than
`one page of memory is generally open. For example under
`the Direct RDRAM scheme (expected to be available in the
`near future), it is expected that up to 8 pages per RDRAM
`chip will be open simultaneously. Thus, if a system has eight
`RDRAM chips (a reasonable assumption), it will be possible
`to have up to 64 pages open simultaneously. Thus, when
`multiple memory accesses are to be sequentially executed,
`an efficient strategy which may be employed by the memory
`controller is that
`it selects which ones of the memory
`accesses to be executed are intended for pages which are
`already open, completes those accesses first, and subse-
`quently proceeds with the memory accesses which will
`require opening new pages. This greatly increases memory
`efliciency.
`Controlling memory access via the use of “look ahead” is
`undeniably valuable. Furthermore, as the foregoing has
`shown, the ability of the memory controller to schedule
`memory access is currently becoming more important as
`both current and future system memories are likely to be
`able to provide a very large number of open pages of
`memory simultaneously. It is therefore apparent that a need
`exists in the art for a method and system which will increase
`the ability of memory controllers to intelligently schedule
`accesses to system memory.
`
`SUMMARY OF THE INVENTION
`
`It has been discovered that a method and system can be
`produced which will increase the ability of memory con-
`trollers to intelligently schedule accesses to system memory.
`The method and system provide a memory controller and a
`requested memory operation buffer structured so that at least
`one source attribute of a requested memory operation can be
`identified. In one instance, the requested memory operation
`buffer has queues, associated with data buses, which can be
`utilized to identify source attributes of requested memory
`operations. Examples of such queues are an Accelerated
`Graphics Port Interconnect queue associated with an Accel-
`erated Graphics Port
`interconnect, a system bus queue
`associated with a system bus, and a Peripheral Component
`Interconnect bus queue associated with a Peripheral Com-
`
`0009
`
`

`
`US 6,546,439 B1
`
`5
`ponent Interconnect bus where the queues can be utilized by
`a memory controller to identify the specific bus from which
`a
`requested memory operation originated.
`In another
`instance, the queues, associated with data buses, are struc-
`tured such that one or r11ore further source attrib11tes—sucl1
`as the identity of the request initiator, the priority of the
`request, whether the request
`is speculative, etcetera—of
`particular queued requested memory operations can be iden-
`tified. In yet another instance, the requested memory opera-
`tion buffer is structured such that one or more source
`attributes—such as the identity of the request initiator, the
`priority of the request, whether the request is speculative,
`etcetera—of particular queued requested memory operations
`can be identified.
`
`The foregoing is a summary and thus contains, by
`necessity, simplifications, generalizations and omissions of
`detail; consequently, those skilled in the art will appreciate
`that the summary is illustrative only and is not intended to
`be in any way limiting. Other aspects, inventive features,
`and advantages of the present invention, as defined solely by
`the claims, will become apparent in the non-limiting detailed
`description set forth below.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The present invention may be better understood, and its
`numerous objects, features, and advantages made apparent
`to those skilled in the art by referencing the accompanying
`drawings.
`FIG. 1 shows a high—level component diagram depicting
`a related art AGP-enabled data processing system which
`forms an environment wherein one or more embodiments of
`the present invention may be practiced.
`FIG. 2 depicts a high—level block diagram illustrating in
`broad overview how the AGP-enabled system of FIG. 1,
`which forms an environment wherein one or more embodi-
`ments of the present invention may be practiced, accesses
`memory and manipulates data within the memory locations
`specified by the memory access requests illustrated in FIG.
`1.
`
`FIG. 3 illustrates pictographically an embodiment of the
`present invention wherein information available at various
`system interfaces is carried all
`the way to the memory
`controller.
`
`FIG. 4 shows pictographically another embodiment of the
`present invention which depicts non-exclusive examples of
`information that may be contained within tags.
`FIG. 5 depicts an embodiment of the present invention
`which utilizes queues dedicated to each bus wherein the
`queues serve to transmit information related to the identity
`of the bus upon which the queued memory transactions
`originate.
`FIG. 6 illustrates another embodiment of the present
`invention wherein dedicated queues and tags are combined
`to provide source attribute information.
`The use of the same reference symbols in different draw-
`ings indicates similar or identical items.
`DE'1'AlLl:D DESCRIPTION
`
`The following sets forth a detailed description of the best
`contemplated mode for carrying out
`the invention. The
`description is intended to be illustrative and should not be
`taken to be limiting.
`Referring now to FIG. 1, shown is a high—level component
`diagram depicting an AGP-enabled data processing system
`101 which forms an environment wherein one or more
`
`6
`embodiments of the present invention may be practiced.
`Shown are three building blocks of AGP: AGP-enabled
`graphics controller 100, AGP interconnect 102 (a data bus),
`and AGP-enabled Northbridge 104. Not shown, but deemed
`present is a fourth building block of AGP: an AGP-enabled
`operating system. The term AGP-enabled is intended to
`mean that the so-referenced components are engineered such
`that they interface and function under the standards defined
`within the AGP interface specification, referenced above.
`Further depicted are display device 110, local frame buffer
`112, Central Processing Unit (CPU) 114, CPU bus 115,
`system memory 116, Peripheral Component Interconnect
`(PCI) bus 118, various PCI Input—Output (I/O) devices 150,
`152, and 154, Southbridge 122, 1394 Device 125, and
`network card 127.
`
`The foregoing components and devices are used herein as
`examples for sake of conceptual clarity. As for non-
`exclusive example, CPU 114 is utilized as an exemplar of
`any general processing unit, including but not limited to
`multiprocessor units; CPU bus 115 is utilized as an exemplar
`of any processing bus, including but not limited to multi-
`processor buses; PCI bus 118 is utilized as an exemplar of
`any input—output device attached to an I/O bus; Northbridge
`104 and Southbridge 122 are utilized as exemplars of any
`type of bridge; 1394 device 125 is utilized as an exemplar of
`any type of isochronous source , and network card 127 is an
`exemplar of any type of network devices. Consequently, as
`used herein these specific exemplars are intended to be
`representative of their more general classes. Furthermore, in
`general, use of any specific exemplar herein is also intended
`to be representative of its class and the riori-iriclusiori of such
`specific devices in the foregoing list should not be taken as
`indicating that limitation is desired.
`Generally, each bus utilizes an independent set of proto-
`cols (or rules) to conduct data (e.g.,
`the PCI local bus
`specification and the AGP interface specification). These
`protocols are designed into a bus directly and such protocols
`are commonly referred to as the “architecture” of the bus. In
`a data transfer between different bus architectures, data
`being transferred from the first bus architecture may not be
`in a form that is usable or intelligible by the receiving second
`bus architecture. Accordingly, communication problems
`may occur when data must be transferred between different
`types of buses, such as transferring data from a PCI device
`on a PCI bus to a CPU on a CPU bus. Thus, a mechanism
`is developed for “translating” data that are required to be
`transferred from one bus architecture to another. This trans-
`lation mechanism is normally contained in a hardware
`device in the form of a bus-to-bus bridge (or interface)
`through which the two different types of buses are con-
`nected. This is one of the functions of AGP-enabled North-
`bridge 104, in that it is to be understood that it translates and
`coordinates between the various data buses which commu-
`nicate through AGP-enabled Northbridge 104.
`Those skilled in the art will recognize that under the AGP
`interface standard a graphics controller is free to issue
`pipelined requests for data. Shown is that AGP-enabled
`graphics controller issues N (where N is some positive
`integer) read requests to read data from a particular cell, or
`row and column location, from DRAM chip 130 in system
`memory 116 prior to any of the N—1 outstanding read
`requests being answered. It should be noted that although for
`conceptual clarity the read requests are shown in FIG. 1 as
`labeled requests 1 through N, under the AGP standard there
`is no such labeling, and under the AGP standard such
`ordering is merely denoted by transmission order of the
`requests. Further illustrated is that within DRAM chip 130
`each row can be conceptualized as a “page” in memory.
`
`0010
`
`

`
`US 6,546,439 B1
`
`7
`the AGP
`Those skilled i