||||||||||||l||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`USUUG434687B1
`
`(12) [.1111th States Patent
`(10) Patent N0.:
`US 6,434,687 B1
`
`Huppenthal
`(45) Date of Patent:
`Aug. 13, 2002
`
`(54) SYSTEM AND METHOD FOR
`ACCELERATING WEB SITE ACCESS AND
`PROCESSING UTILIZING A COMPUTER
`SYSTEM INCORPORATING
`RECONHGURABLE PROCESSORS
`OPERATING UNDERA SINGLE OPERATING
`SYSTEM IMAGE
`
`(75)
`
`Inventor:
`
`Jon M. Huppenthal, Colorado Springs,
`co (US)
`
`(73) Assignee: SRC Computers, lnc., Colorado
`Springs, (‘0 (U5)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U511, 154(1))hy 0 days.
`
`(a) Notice:
`
`(21) App}, No: 093883.76
`,.
`_
`Plh'd'
`
`(22
`
`Jun. 22’ 2001
`Related U.S. Application Data
`
`OTHER PUBLICATIONS
`_‘
`_
`_
`_
`Albaharna, Osama, Cl 511., "On [116 Vlablllly 0f I‘l‘GA—bascd
`inlegt‘aled
`coprocessors”, © 1996
`IEEE, Publ. N0.
`045186-7548j‘hf96a PP‘ 306-215
`Barthel, Dominique Aug. 25—26, 1997, "FY? a Parallel
`Video coProcessor", IIot Chips IX, pp. 203—210.
`Bitlner, Ray, at al., "Computing kernels implemented with a
`wormhole RTR CCM", ® l997 IEEE,
`Puhl. No.
`0—8186—8159—4197, pp. 98—105.
`l"t' .'t .'1'—
`Bbb.J
`1h
`.11.,“P 111"
`“:1”. ©01399alifififial
`ara e 12mg app “a tons to 0 SI ]
`Berlin, Patrice, et 211., “Programmable active memories: a
`pcrt‘on‘rtance assessment". © 1993 Massachusetts Institute
`of Technology, pp. 88—103
`.
`_
`Culbertson, W. Bruce, el 31., "Explorlng architectures for
`volume visualization on the Tcramae custom computer", (0
`1996 IEEE, Pub]. No. 0—8186—7548—9196, pp. 80—88.
`Culbertson, W. Bruce. e1 31.. "Defect
`tolerance on the
`'l'eramac custom computer”, © 1997 IEEE, Publ. No.
`045186a315‘J—4e’97, pp‘ 116—123-
`
`(63)
`
`Conlinualion—in—part of application No. 091563561, Iilcd on
`May 3, 2000, now Pat. No. 0,339,819. which is a continu—
`alion—in—part of application No. 091481302, filed on Jan. 12,
`2000, now Pat. No. 6,247,110, which is a continuation of
`application No. 081992.703, filed on Dec. 17, 199?, now Pal.
`No. swam.
`
`(LISI Continued on DC)“ page.)
`_
`,
`_
`Primary Exammer-—Kennelh S. Kim
`(74) Army-rage, Agent, or Finn—William J. Kubida; Hogan
`& Hartson I I 1)
`"‘
`
`(51)
`
`Int. Cl.7
`
`(52) U.S. Cl.
`
`(58) Field of Search
`
`GINSF 15106
`
`712132; 70715011; 1073513;
`7093203; 7093219
`
`70715011, 513;
`709,903, 219; 713,132
`
`(56)
`
`References Cited
`U.S. PHI‘EN'I' DOCUMENTS
`.
`_
`{£311,377 A : 909?? meld! e1 al-
`iii??? 2 , 3:35: 3“?" ['"I'm
`v,’,
`y
`_
`artnea......
`5381400 A * 101999 Donohue et a}.
`.
`6,009.4l0 A "‘ 12411999 LeMolc el al.
`6,128,663 A * 1012000 Thomas
`
`
`
`_
`343*:723
`3233:]:
`.
`amsut
`T051114
`7001228
`
`(57)
`
`ABSTRACT
`
`A system and method for accelerating web site access and
`Processing utilizing a multiprocessor computer system
`incorporating reconfigurable and standard microprocessors
`as the web site server. One or more reconfigurable proces—
`SUTS may be utilized, 10F “ample, in accelcmiint; 511“- ViSiwr
`demographic data processing, real time web site content
`updating, database searches and other processing associated
`with e-eomrneree applications. In a particular embodiment
`disclosed, all of the reconfigurable and standard micropro-
`cessors may be controlled by a single system image of the
`operating system, although cluster management software
`may be utilized to cause a cluster of microprocessors to
`,
`,
`,
`-
`.
`-
`.
`t
`'
`,
`“mm“ m m" "S“ as a 5mg“ COW at m" “p“a'mg Symm‘
`
`25 Claims, 14 Drawing Sheets
`
`,-- 332
`
`.
`
`“3006th
`N
`“SE-s
`
`|
`.
`.I.
`..
`.
`J.
`WGCESS
`PROCEfi
`DAM
`DATA
`EIJeIlmll
`new»:
`
`DECK—.555
`MT!
`:Ltwtm
`
`'
`
`3‘RCICIISS
`5“"
`anew
`
`mm.
`
`N—i’l-fl
`
`1
`333:, I
`
`33“.!
`‘
`
`
`
`
`
`
`
`334,
`
`
`Nann-
`
`anodfis‘h‘cngiihi
`
`’4
`
`Hill-I;-
`NEWCCNIENT
`
`f 336
`
`33:. ,J'
`
`IIIFEAIILM
`REDUEEOYU
`”mflhfw
`CON—ENT
`
`SELECTIM
`
`338
`
`:5va -"il
`$15.?
`
`so;
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 1
`Petitioner Microsoft Corporation - EX. 1014, p. 1
`
`

`

`US 6,434,687 B1
`
`Page 2
`
`OTHER PUBLICATIONS
`
`Chan, l’ak, et al., “Architectural tradcoffs in field—program-
`mable—devicc-bascd computing systems",
`if) 1993 IEEE,
`Pub]. No. 0—8186—3890—73‘93, pp. 152—161.
`Clark, David, et al., "Supporting FPGA microprocessors
`through retargetable software tools", © 1996 IEEE, Pub].
`No. 0—8186—7548—9l9fi. pp. 195—103.
`Cuccaro, Steven, el al., "The CM~2X: a hybrid (TM—2r“
`Xilink prototype”, © 1993 IEEE, Pub]. No. 0-8186—3890—7:J
`93, pp. 121-130.
`Dehon, Andre, "DPGA—Couplcd microprocessors: com—
`modity IC for the early 21“ century", © 1994 IEEE, Pub].
`No. 0—8186—5490—2l94, pp. 31—39.
`Dhaussy, Philippe, cl al., “Global control synthesis [or an
`MIMDXFPGA machine”,
`if)
`1994
`IEEE, Pub. No.
`0—8186—5490—394, pp. 72—81.
`Deshpande, Deepali, et al., "Hybrid datai’configuration cach-
`ing for striped FPGAs" © 1999 IEEE.
`Elliott, Duncan, et al., "Computational Ram: a memo—
`ry—SIMD hybrid and its application to DSl’”,® 1992 IEEE,
`Pub]. No. {1—7803—0246—Xl92, pp. 30.61—30.64.
`liorles, Jose, et al., “Systolic arrays, a survey of seven
`projects",
`(6
`[98.7I
`IEEE, Pub]. No.
`(TOW-9162,9879l
`0700—0091, pp. 91—103.
`Purna, Karthikeya, et al., "Temporal partitioning and sched-
`uling data flow graphs for reconfigurable computers", (0
`1999 IEEE, Pub]. No. 0018-9340519 pp. 579—590.
`Gibbs, W. Wayt, “Blitzing bits", © 1999 Scientific American
`Presents, pp. 57—61.
`Gonzalez, Ricardo, “Configurable and extensible processors
`change system design”, Aug. 15—17, 1999, Hot Chips 11
`Tutorials, pp. 135-946.
`Graham, Paul, et al., .“l-‘PGA—based sonar processing", ©
`1998 ACM 0—89791w978—5l98, pp. 201—208.
`llauser, John, et al.: “GARP: a MIPS processor with a
`reconfigurable co—processor“, © 1997 IEEE, Pub. No.
`0—08186—8159—497, pp. 12—21.
`Hammond, Lance, et al., “The Stanford Hydra CMP“, Aug.
`15—17, 1999 Hot Chips 11 Tutorials, pp. 23—31.
`Hartenstein, Reiner, et al., “A reconfigurable data—driven
`ALU for Xputers”, © 1994
`IEEE,
`Pub]. No.
`0—8186—5490—2!94, pp. 139—146.
`Hayes, John, et al., “A microprocessor—based hypercube,
`supercomputer“, © 1986 IEEE, Pub]. No. 0274'2—1732.386:f
`lCKKl—(Kl'tlfi, pp. 6-17.
`Hagiwara, lliroshi, et al., "A dynamically microprograrn-
`mable computer with low-1evelparal]elism", (E) 1980 IEEE,
`Pub. No. m1a—934or80roum—0577, pp. 577—594.
`l-lasebe, A., et al., "Architecture ofSIl’S, a real time image
`processing system," (C) 1988 IEEE, Pub]. No.
`(112603—92f
`SSIOIXJOIGGEI, pp. 621—630.
`Jean, Jack, et al., "Dynamic reconfiguration to support
`concurrent
`applications", © 1999
`IEEE, Pub]. No.
`00184340199, pp. 591—602.
`Kaslrup, Bernardo, et al., "Concise: a compiler—driven
`CPLD—based instruction set accelerator", © 1999 IEEE.
`King, William, et al., “Using MORRPH in an industrial
`machine vision system", Q)
`1996
`IEEE, Pub. No.
`08186—7548—9l96, pp. 18—36.
`Manohar, Swaminalhan, ct al., “A pragmatic approach to
`systolic design", © 1988 IEEE, Pub]. No. CI-lZfiO3—9l
`88—0000l0463, pp. 463—472.
`
`Motolnura, Masato, ct al., “An embedded DRAM—FPGA
`chip with instantaneous logic reconfiguration", © 1998
`IEEE, Pub]. No. (F8186—8900—52’98, pp. 264—266.
`McConnell, Ray, "Massively parallel computing on the
`FUZION chip”, Aug. 15—17, 1999, Hot Chips 1 1 Tutorials,
`pp. 83—94.
`McShane, Erik, el al., “Functionally integrated systems on a
`chip:
`technologies, architectures, CAD tools, and applica-
`tions“, © 1998 IEEE, Publ. No. 8—8'l86—8424—(lf98, pp.
`67—75.
`
`Mauduit, Nicolas, et al., “Lneuro 1.0: a piece of hardware
`LEGO for building neural network systems," (0 1992lEE13,
`Pub]. No. 1045—9227992 pp. 414—422.
`Patterson, David, et al., “A case for intelligent DRAM:
`IRAM“. I-[ot Chips Vin. Aug. 19—20, 1996, pp. 75—94.
`Peterson, Janes, el al., “Scheduling and parlitioningANSI—C
`programs onto mulli—FPGA CCM architectures“, © 1996
`IEEE, Pub]. No. 0—8186«7548—9r’96, pp. 178—187.
`Rupp, Charley, et al., "The NAPA adaptive processing
`architecture”, © 1998 the Authors, pp. 1—10.
`Sailo, Osamu, el al., “A 1M synapse self learning digital
`neural
`network
`chip",
`6)
`1998
`IEEE,
`Pub]. No.
`0—7803—4344/U9S, pp. 94—95.
`Schott, Brian, et al., "Architectures for system—level appli-
`cations of adaptive computing", (0 1999 lEEE.
`Schmit, Herman, "Incremental reconfiguration for pipelincd
`applications," (0 1997 IEEE, Pub]. No. 0—8186—8159—4197,
`pp. 47—55.
`Villasenor, John, et al., “Configurable computing”, © 1997
`Scientific American, J on. 199?.
`Stone, Harold, "A logic—in—memory computer”, (0 1970
`IEEE, [lit-IE 'l'ransaclions on Computers, pp. 73—78, Jan.
`1990.
`
`'l‘rimberger, Steve, et al., “A time—multiplexed FPGA”, ©
`1997 IEEE, Pub]. No. 0—8186—8159-4197, pp. 22—28.
`'l'hornburg, Mike, et al., “'l"ransformable Computers”, 69
`1994 IEEE, Pub]. No. M186-5602—fif94, pp. 674-679.
`Tangcn, Uwc, et al., “A parallel hardware evolvable com-
`puter POLYP extended abstract“, (0 1997 IEEE, Pub]. No.
`0—8186—8159l4l97, pp. 238—239.
`'l‘omita, Shinji, et al., “A computer low—level parallelism
`QA—Z", © 1986 IEEE, No. 0—0384—7495l86l0000l0280, pp.
`280—289.
`
`Ueda, Hirotada, et al., “A multiprocessor system utilizing
`enhanced DSP‘s [or image processing”, © 1988 IEEE, Pub].
`No. CH2603—9l88lm2‘061 1, pp. 611-620.
`Wang, Quiang, ct al., “Automated field—programmable com—
`pute accelerator design using partial evaluation", © 1997
`IEEE, Pub]. No. 0—8186—8159—4r’97, pp. 145—154.
`low
`a
`Wirthlin, Michael, el al., "The Nano processor:
`resource reconfigurable prooessor“, © 1994 IEEE, Pub]. No.
`0-3186—5490—2f94, pp. 23—30.
`Wittig, Ralph, et al., "One Chip: An FI’GA processor with
`reconfigurable
`logic”, © 1996
`IEEE,
`Pub]. No.
`0—8186—7458—9l96, pp. 126—135.
`Wirlhlin, Michael, el al., “A dynamic instruction set corn-
`ptlter", © 1995 IEEE, Pub]. No. D—8186—7086—Xl'95, pp.
`99—107.
`
`Yamauchi, 'l"sukasa, et al., “SOP: Areconfigurable massively
`parallel system and its control—data flow based compiling
`method", © 1996 IEEE, Pub]. No. (1—8186—7548—9l96. pp.
`148—156.
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 2
`Petitioner Microsoft Corporation - Ex. 1014, p. 2
`
`

`

`US 6,434,687 B1
`Page 3
`
`Mencer. Oskar, et al., "PAM—Blox: High Performance
`FPGA Design for Adaptive Computing". © 1998 lEliE,
`Conference
`Paper,
`INSPEC
`Abstract
`Nos.
`B9811—1265B—(I44. C9811—5210—009.
`Miyamori, Takashi. ct al., “A quantitative analysis of recon—
`figurable coprocessors for multimedia applications", (6 1998
`IEEE, Conference
`Paper,
`INSPEC Abstract Nos.
`B9811w1265F—011, C9811—5310—010.
`W.H. Mangione—Smith and B.L. Hutchings. Configurable
`computing: The Road Ahead. In Proceedings of the Recon-
`figurable Architectures Workshop (RAW’97), pp. 81—96,
`1997.
`Minsky, Ethan A., ”Coarse—Grain Reconfigurable Comput-
`ing", Massachusetts Institute of Technology, Jun. 1996.
`Vemuri. Ranga R. et al., “Configurable Computing: Tech-
`nology and Applications", Apr. 2000, Computer, pp. 39—40.
`
`Del-Ion, Andre, "The Density Advantage of Configurable
`Computing”, Apr. 2000, Computer, pp. 41—49.
`
`Haynes, Simon D. et al., "Video Image Processing with the
`Sonic Architecture", Apr. 2000. Computer, pp. 50—51.
`
`Plalzner, Marco, "Reconfigurable Accelerators for Combi-
`natorial Problems”, Apr. 2000. Computer. pp. 58—60.
`
`Callahan. Timothy J. et al., "The Garp Architecture and C
`Compiler”, Apr. 2000, Computer, pp. 62—69.
`
`Goldstein, Seth Copen et al., "PipcRench: A Reconfigurable
`Architecture and Compiler”. Apr. 2000, Computer. pp.
`70—76.
`
`* cited by examiner
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 3
`Petitioner Microsoft Corporation - EX. 1014, p. 3
`
`

`

`US. Patent
`
`Aug. 13, 2002
`
`Sheet 1 of 14
`
`US 6,434,687 B1
`
`14
`
`MEMORY
`INTERCONNECT
`FABmc
`
`
`
`120
`
`Processor
`0
`
`121
`
`12N
`
`1
`
`I
`I
`
`|
`|
`I
`I
`'
`|
`
`Processor
`N
`
`1120
`
`MAP
`0
`
`1121
`
`Mfip
`
`|
`I
`I
`I
`|
`I
`|
`|
`
`MQP
`
`H2~
`
`160
`
`arbZngm
`Bank 0
`
`Memory
`Subsystem
`Bank 1
`
`|
`i
`I
`:
`:
`
`l
`|
`'
`'
`'
`Il
`|
`I
`I
`
`161
`
`16M
`
`Memory
`Subsystem
`Bank M
`
`_L (3
`_
`
`Fig. 1
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 4
`Petitioner Microsoft Corporation - EX. 1014, p. 4
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 5m.
`
`
`
`9“ES.xm-soumuofioo@8822Momentum
`
`
`
`
`
`US. Patent
`
`Aug. 13, 2002
`
`Sheet 2 MM
`
`US 6,434,687 B1
`
`
`
`._WEIFEOOJ<__g0_1|__so:E_5a:_ms:1a___..._%._.m5:e_59_90:0:sz.__Em: fiwzmjééom,.m0szzoEwOanomE325.0555m:"_.N.ge(no:__mow
`
`n22_eImmomwmooglddéi_.
`
`SN:._r?!szOmmIt!
`
`
`
`_wwor_2N:5m:
`a:9__IH«mm:«3:2mm“33mmg_a_.mmo¢awEOE:
`
`«em:$9r01__aH89.__. mam:_e.52mEms:g:.LI_1.12e_mm_._E_m5:___$2_m:_0Km?__ads.__.
`
`
` _.hmowmm20FU:m...m2.__n35_e«no:___s:A.E_I_n25—.___mum:_.m5:6.1&9_fi__Jgm:ad‘s.me«3:£2_m_._awe?_my:
`
`
` Ed:_e«6.“m_N«am:mam:_m5:0:Nwe"«woe_HERE.e._._
`
`
`
`n35.WJ.___
`n32
`._m3:E__
`
`
`
`szEmOmwmDOD
`
`ZOmtwOn—EOOMD
`
`15.3493»..—
`
`r20.0mm
`
`JMJnEM—(n.
`
`N20.0mm
`
`Juan—(Edn—
`
`020.05“.
`
`AMA-Ems".
`
`.w206mm.
`
`FNor
`
`“New
`
`nNow
`
`«Now
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 6o.
`
`
`
`9“ES.xm-soumuofioo@8822Momentum
`
`
`
`
`
`US. Patent
`
`lBH.)86.,4
`
`m,matMflU_.........................................................................................
`.mS:mw__wm_W«I_wmw55:00_.m"Emsmwm<
`
`n35.
`
`
` vmrmS_0.004*_40m+zooU2wxz<mmmz:x235_m_555$_m,Mmmmmggm"u”_><mm<E052mm?mAm___mmmmw
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 7n.
`
`
`
`9“ES.xm-soumuofioo@8822Momentum
`
`
`
`
`
`US. Patent
`
`Aug. 13, 2002
`
`Sheet 4 of 14
`
`US 6,434,687 B1
`
`ZOEQKDOEZOO3F.EEmm
`“WE—ON—MMhmm>zOU
`
`
`mm?vhf
`mgmg
`
`
`
`EON—L-O._..._m_:_.._<m<n:at:mémn
`
`NEEmmawwwmomz
`
`zampk<m
`
`zo:<m:wizoomtm
`
`
`
`20.5mzwmzou02525.00
`
`XDEmun—Down.
`
`at53
`
`mwmmzQEmBEzOor.......mm:
`
`0%rof03“.mtm.55on
`
`azéwao$5.8m
`
`
`
`ME_wewas;__£59m
`
`
`_w_<9:20m“.VAmi_SE3096E
`.rw3F<FwM
`meéisoow__{.353__mz_..m_n:n_
`_m9_mtm:Emo
`
`___$5300MMHmm:mm:“_wzjme
`
`
`
`
`“<01“—_mz_._mn=n_9.5.8”.wo2EOE
`
`m?j
`
`
`
`__....--.....................J.we.
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 8w.
`
`
`
`9“ES.xm-soumuofioo@8822Momentum
`
`
`
`
`
`US. Patent
`
`new
`
`
`
`mDOSmmm20mm.
`
`Q32
`
`S
`
`0
`
`U
`
`lBM
`
`n'mOEmE
`4IE?0
`
`1
`
`
`
` 5o?mmm:Iotgm
`
`(9BE?BEE
`
`><mm<32omomeOEmEN3482,w.«.8885BI<mm<0any'5ng_|Aomw
`
`4.,omm8m368mmmmSXZDEF
`XZDNE.
`Mwm.m..&age
`3ll.._.Xm_zO...
`
`
`
` >¢mm<0>m0§m§mom<omof“la.108331
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 9m.
`
`
`
`9“ES.xm-soumuofioo@8822Momentum
`
`
`
`
`
`US. Patent
`
`UA
`
`a
`
`m
`
`M6mhS
`
`.4
`
`1B7
`
`vmNVow
`
`Z_<IO
`
`.EOn.
`
`«FED
`
`m><mE3m,Em:\$0ng
`
`<20
`
`wlM,S
`
`
`
`mmmmmogwmmmanz
`
`
`
`
`.,mmMIotawUoAmi<55E0522055.8:55E03,;
`
`.65on2055.00
`
`mw
`
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 10S.
`
`
`
`9“ES.xm-:0380950@8822Emerson
`
`
`
`
`
`US. Patent
`
`Aug. 13, 2002
`
`Sheet 7 MM
`
`US 6,434,687 B1
`
`vm
`
`vm
`
`>IOEmE
`
`Pancho
`
`$.45
`
`N.mt
`
`401F200
`
`._.Dn_._.DO
`
`On__n_
`
`m._m_<w50_n_200m_m
`
`><mm<
`
`.Sn_2_
`
`D<mm
`
`Imnfism
`
`SmSo5m;
`
`woz<mmao
`
`wDZdfimQO
`
`2310:25Eom
`
`>EOEm—E
`
`HDQZ.
`
`«CED
`
`mmeoom
`
`
`
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 11S.
`
`
`
`9“ES.xm-:0380950@8822Emerson
`
`
`
`
`
`US. Patent
`
`08KJvmmmpES
`mAQa9‘
`
`mmmm._.Dn_Z_F312—
`ZEIO>m0§m§
`
`[om
`
`1B
`
`,mm
`
`NI.—wm1
`
`mm3.,N1NMymAannl—
`
`eH
`
`7III8:m.mmlM,9mm2.5.6:2
`.8A,F/8omMo_._<>z_<zo40520085969H
`%Amm.avmu«mm
`mw.2
`mwwmmmnzo.Saz_
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 12S.
`
`
`
`9“ES.xm-:0380950@8822Emerson
`
`
`
`
`
`US. Patent
`
`Aug. 13, 2002
`
`Sheet 9 0f 14
`
`US 6,434,687 B1
`
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 13.
`
`
`
`2.9“ES.xm-:0380950@8822Emerson
`
`
`
`
`
`US. Patent
`
`Aug.l3,2002
`
`Sheet10 0f14
`
`US 6,434,687 B1
`
`cow
`
`Wm
`
`Z<Io
`
`hmOa
`
`8m
`
`Z<Io
`
`HmOm
`
`8m
`
`«N
`
`OF
`
`wa2
`
`Q<E
`
`vm
`
`
`
`Nwrili\\
`
`Q<E
`
`Wm
`
`23:0
`
`_.__
`
`
`
`EOa.n_.
`
`HElzlzlnEl
`
`:
`
`305mg"23mzmvm23m29%
`50mmFL
`
`(V‘Odd)
`HEJ'I'IOHLNOO
`AHOWEW
`
`Wadi)
`
`asmoamoo
`AHOWEW
`
`qmNil];
`
`NmNVN
`
`
`
`“movw«mmvm
`
`(VOdj)
`HOLIMS
`
`aossaooad
`
`mmm
`
`mam
`
`mmm
`
`Hawassv
`dHOO3SSOH.
`
`
`
`
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 14E.
`
`
`
`9“ES.xm-:0380950@8822Emerson
`
`
`
`
`
`US. Patent
`
`Aug. 13, 2002
`
`Sheet 11 0f 14
`
`US 6,434,687 B1
`
`q:.9”.
`
` Ema93> IIwearI!
`
`In8211
`
`IImcmIIII.Tnl
`
`mcmé
`
`It...mcmall
`
`£85
`
`motmlmm
`
`$8Sac.
`
`iumzm
`
`vmtmmm.
`
`Etmlwm
`
`3.at
`
`I
`
`1.m5:L1.
`
`
`
`EmaU__m>
`
`ITmcorI!
`
`33.5930
`
`

`

`US. Patent
`
`Aug. 13, 2002
`
`Sheet 12 0f 14
`
`US 6,434,687 B1
`
`USER PC
`
`
`
`
`
`
`
`TYPICAL
`WEB SITE
`SERVER
`
`SRC 6
`RECON FIGURABLE
`SERVER
`
`3 0
`
`Fig. 12
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 15
`Petitioner Microsoft Corporation - EX. 1014, p. 15
`
`

`

`US. Patent
`
`Aug. 13, 2002
`
`Shect13 0f 14
`
`US 6,434,687 B1
`
`
`
`
`
`
`
`N
`DEMOGRAPHIC
`DATA
`ELEMENTS
`
`312
`
`314
`
`N ITERATIONS REQUIRED TO
`PRODUCE NEW CONTENT
`
`/
`
`SELECTION
`
`
`
`PROCESS
`DATA
`ELEMENT
`
`NO
`
` DATA
`
`ELEMENT
`=N
`
`
`YES
`
`318
`
`SELECT
`
`
`NEW CONTENT
`
`
`
` DISPLAY
`
`UPDATED
`CONTENT
`
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 16
`Petitioner Microsoft Corporation - EX. 1014, p. 16
`
`

`

`US. Patent
`
`Aug. 13, 2002
`
`Sheet 14 0f 14
`
`US 6,434,687 B1
`
`332
`
`
`
`
`N
`DEMOGRAPHIC
`DATA
`ELEMENTS
`
`
`
`PROCESS
`
`PROCESS
`
`PROCESS
`
`
`
`DATA
`DATA
`DATA
`ELEMENT
`ELEMENT
`ELEMENT
`N-(N-H
`N-(N-2}
`N-(N-3J
`
`
`.
`
`.
`
`'
`INSTANTIATE N
`PROCESSING ELEMENT-
`
`"
`
`PROCESS
`
`DATA
`ELEMENT
`N
`
`
`
`
`334w
`
`
`
`SELECT
`
`NEw CONTENT
`
`
`
`I.
`
`1 ITERATIDN
`REQUIRED TO
`PRODUCE NEW
`CONTENT
`SELECTION
`
`DISPLAY
`
`
`UPDATED
`CONTENT
`
`
`30
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 17
`Petitioner Microsoft Corporation - EX. 1014, p. 17
`
`

`

`US 6,434,653? B1
`
`1
`SYSTEM AND METHOD FOR
`ACCELERATING WEB SITE ACCESS AND
`PROCESSING UTILIZING A COMPUTER
`SYSTEM INCORPORATING
`RECON IiI GURABIE PROCESSORS
`OPERATING UNDER A SINGLE OPERATING
`SYSTEM IMAGE
`
`CROSS REFERENCE 'IU RELATED PMENT
`APPLICATIONS
`
`The present invention is a continuation-in-part application
`of US. patent application Ser. No. 091563561 tiled May 3,
`2000, now issued US. Pat. No. 6,339,819 Bl, which is a
`continuation-in-part application of US. patent application
`Ser. No. 09r481,t)02 tiled Jan. 12, 2000, now issued US. Pat.
`No. 6,247,110 which is a continuation of US. patent appli—
`cation Ser. No. 082991763 filed Dec. 17, 1997 for: “Mul-
`tiprocessor Computer Architecture Incorporating a Plurality
`of Memory Algorithm Processors in the Memory
`Subsystem”. now issued US. Pat. No. 6,076,152 assigned to
`SRC Computers, Inc., Colorado Springs, Colo, assignee of
`the present
`invention, the disclosures of which are herein
`specifically incorporated by this reference.
`BACKGROUND 01-“ THE INVENTION
`
`in general, to the field of
`The present invention relates,
`computer architectures incorporating multiple processing
`elements such as multi-adaptive processors (“M/\PTW’, is a
`trademark of SRC Computers,
`lnc., Colorado Springs,
`Colo.) . More particularly, the present invention relates to
`systems and methods for accelerating web site access and
`processing utilizing a computer system incorporating recon-
`figurable processors operating under
`a single operating
`system image.
`Presently, many different forms ofelectronic business and
`commerce are transacted by means of individual computers
`coupled to the Internet. By virtue of its computer-based
`nature, many electronic commerce (“e-commerce”) web
`sites employ various methods to allow their content to be
`varied based on the demographics of the particular user.
`This demographic information may be obtained in a
`variety of ways, with some sites simply requesting the site
`visitor respond to one or more questions while others may
`employ more sophisticated techniques such as “click
`stream” processing. In this latter instance, the prospective
`interests of the site visitor are inferred by determination and
`analysis of, for example, the previous sites he has visited. In
`either instance however, this data must be processed by the
`site such that the web page content may be altered in an
`effort to maximize it appeal to thatparticular site visitor with
`a view toward ultimately maximizing site revenue.
`Since studies have shown that the average Internet user
`will wait but a maximum of twenty seconds or so for a web
`page to be updated, it is vitally important that the updating
`of the page contents be completed as rapidly as possible.
`Consequently, a great deal of elfort is placed into maximiz-
`ing the software performance of algorithms that process the
`user demographic data. Currently, all known web servers
`that accomplish this processing employ industry standard
`microprocessor based servers and, as a result, their maxi-
`mum performance is thereby limited by the limitations
`inherent in the standard microprocessor “Ioadlstore” archi—
`IECIUI’C.
`
`SUMMARY 0]3 'l‘I-IE INVENTION
`
`SRC Computers, Inc., assignee ot‘the present invention, is
`an industry leader in the design and development of multi-
`
`It]
`
`IS
`
`30
`
`35
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`55
`
`2
`processor computer systems including those employing
`industry standard processors together with multi-adaptive
`processors (“MAPTM”) utilizing, for example, field program-
`mable gate arrays functioning as the programmable MAP
`elements.
`
`Particularly disclosed herein is a system and method for
`accelerating web site access and processing utilizing a
`multiprocessor computer system incorporating one or more
`micropmcessors and a number of reconfigurable processors
`operating under a single operating system image. In an
`exemplary embodiment, a web site may be serviced with a
`hybrid multiprocessor computer system that contains both
`industry standard microprocessors and one or more reconn
`figurable processors that share all the system’s resources and
`operate under a single operating system image, (although, in
`an alternative embodiment, cluster management software
`may be used to make a cluster of microprocessors appear to
`the user as a single copy of the operating system). In such
`a system, demographic data processing algorithms may be
`loaded into the reconfigurable processors which may be
`provided in the form of specially adapted field program—
`mable gate arrays ("FPGAs"). In this manner, the appropri-
`ate algorithm may be implemented in hardware gates (as
`opposed to software) which can process the data up to 1000
`times faster than a standard microprocessor based server.
`As an exemplary implementation, one particularly eflica-
`cious hybrid computing system is the SRC Computers, Inc.
`SRC-ti incorporating multi-adaptive processors (MAP). In
`such a system, the algorithms loaded into the MAP elements
`to process the data can be completely changed in under 100
`msec. This allows for the possibility of quickly altering even
`the processing algorithm without significantly delaying the
`site visitor. The ability to change the algorithm, coupled with
`highly accelerated processing times allows for more com-
`plex algorithms to be employed leading to even more refined
`web page content adjustment.
`Through the use of such a hybrid system operating under
`a single operating system image,
`a standard operating
`system, such as Solaris"M (trademark of Sun Microsystems,
`Inc., Palo Alto, Calif.) may be employed and can be easily
`administered, a feature which is important
`in such
`e-commerce based applications. Since the MAP elements
`are inherently tightly—coupled into the system and are not an
`attached processor located, for example, on an inputloutput
`("HO”) port, their effectiveness and ease of use is maxi-
`mized.
`
`Demographic data processing is merely an example of
`how the unique capabilities of such reconfigurable process-
`ing systems can be utilized to accelerate e-commcrce, and
`"secure socket" operation is yet another possible applica-
`tion. In this instance. such operations can often consume as
`much as 80% of the typical, traditional site server micro-
`processor cycles. SRC Computers, Inc. has demonstrated
`that reconfigurable processor based systems, such as the
`SRC-o. can perform decryption algorithms up to 1000 times
`faster
`than a conventional microprocessor
`thereby also
`allowing for faster web site access while concomitantly
`allowing more robust data encryption techniques to be
`employed. Similarly significant speed advantages could be
`realized in, for example, implementing database searches
`wherein the search algorithms can be directly implemented
`in the hardware of the reconfigurable system providing two
`to three orders of magnitude execution time improvements
`over conventional microprocessor based solutions.
`In general, the use of hybrid computer systems with a
`single system image of the operating system for web site
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 18
`Petitioner Microsoft Corporation - EX. 1014, p. 18
`
`

`

`US 6,434,653? B1
`
`3
`hosting allows the site to employ user selected hardware
`accelerated versions of software algorithms currently imple-
`mented in a wide array of e-commerce related functions.
`This results in an easy to use system with significantly faster
`processing capability which translates into shorter site visi-
`tor waiting periods.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`4
`invention including a typical web site server as
`present
`would be replaced by an SRC-fi reconfigurable server;
`FIG. 13 is a flowchart illustrating a conventional data
`processing sequence in a conventional application of the
`typical web site server depicted in the preceding figure. and
`FIG. 14 is a corresponding flowchart
`illustrating the
`processing of demographic or other data utilizing a recon-
`tigurable server for implementing the system and method of
`the present
`invention and which results in significantly
`improved access and data processing times.
`
`DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`With reference now to FIG. 1, a multiprocessor computer
`to architecture in accordance with one embodiment of the
`present invention is shown. The multiprocessor computer 10
`incorporates N processors 120 through IZN which are
`bi-directionally coupled to a memory interconnect fabric 14.
`The memory interconnect fabric 14 is then also coupled to
`M memory banks comprising memory bank subsystems 160
`(Bank 0) through 16M (Bank M). N number of multi-
`adaptive processors ("MAW-W) 1120 through 112” are also
`coupled to the memory interconnect fabric 14 as will be
`more fully described hereinafter.
`With reference now to FIG. 2, a representative application
`program decomposition for
`a multiprocessor computer
`architecture 100 incorporating a plurality of multi-adaptive
`processors in accordance with the present
`invention is
`shown. The computer architecture 100 is operative in
`response to user instructions and data which, in a coarse
`grained portion of the decomposition, are selectively
`directed to one of (for purposes of example only) [our
`parallel regions 1021 through 102.: inclusive. The instruc-
`tions and data output from each of the para llcl regions 1021
`through 11124 are respectively input
`to parallel
`regions
`segregated into data areas 1041 through 1044 and instruction
`areas 106] through 1064. Data maintained in the data areas
`104,
`through 10-14 and instructions maintained in the
`instruction areas 1061 through 106_. are then supplied to, for
`example, corresponding pairs of processors 1083, 1082 (P1
`and P2); 1083, 1118,, {P3 and P4); 1085, 108,j (P5 and P6);
`and 1087, 1033 (P7 and P8) as shown. At
`this point, the
`medium grained decomposition of the instructions and data
`has been accomplished.
`A fine grained decomposition, or parallelism. is effectu—
`ated by a further algorithmic decomposition wherein the
`output of each of the processors 1081 through 1088,
`is
`broken up,
`for example,
`into a number of fundamental
`algorithms “OH, 110m, 1102‘, 110:5 through 110,”, as
`shown. Each of the algorithms is then supplied to a corre-
`sponding one of the MAP elements 112M, 112”}, 1122.4,
`112:3, through 11233 which may be located in the memory
`space of the computer architecture 100 for execution therein
`as will be more fully described hereinafter.
`With reference additionally now to FIG. 3, an exemplary
`implementation of a memory bank 120 in a MAP system
`computer architecture 100 of the present invention is shown
`for a representative one of the MAP elements 112 illustrated
`in the preceding figure. Each memory bank 120 includes a
`bank control logic block 122 Iii-directionally coupled to the
`computer system trunk lines, for example, a 72 line bus 124.
`The bank control
`logic block 122 is coupled to a
`bi-dircctional data bus 126 {for example 256 lines) and
`supplies addresses on an address bus 128 (for example 17
`lines) for accessing data at specified locations within a
`memory array 131].
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 19
`Petitioner Microsoft Corporation - EX. 1014, p. 19
`
`in
`
`15
`
`an
`
`35
`
`4t]
`
`The aforementioned and other features and objects of the
`present
`invention and the manner of attaining them will
`become more apparent and the invention itself will be best
`understood by reference to the following description of a
`preferred embodiment taken in conjunction with the accom-
`panying drawings, wherein:
`FIG. 1 is a simplified. high level. functional block dia—
`gram of a multiprocessor computer architecture employing
`multi-adaptive processors ("MAW-“'1 in accordance with
`the disclosure of the aforementioned patent applications in
`an alternative embodiment wherein direct memory access
`(“DMA”) techniques may be utilized to send commands to
`the MAP elements in addition to data;
`FIG. 2 is a simplified logical block diagram of a possible
`computer application program decomposition sequence for
`use in conjunction with a multiprocessor computer archi-
`tecture utilizing a number of MAP elements located, for “
`example. in the computer system memory space, in accor-
`dance with a particular embodiment ofthe present invention;
`110.25 is a more detailed functional block diagram of an
`exemplary individual one of the MAP elements of the
`preceding figures and illustrating the bank control logic,
`memory array and MAP assembly thereof;
`FIG. 4 is a more detailed functional block diagram of the
`control block of the MAP assembly of the preceding illus~
`tration illustrating its interconnection to the user FPGA
`thereof in a particular embodiment;
`FIG. 5 is a functional block diagram of an alternative
`embodiment of the present
`invention wherein individual
`MAP elements are closely associated with individual pro-
`cessor boards and each of the MAP elements comprises
`independent chain ports for coupling the MAP elements
`directly to each other;
`FIG. 6 is a functional block diagram ofan individual MAP
`element wherein each comprises on board memory and a
`control block providing common memory DMA capabili—
`ties;
`FIG. 7 is an additional functional block diagram of an
`individual MAP element illustrating the on board memory
`function as an input butter and output FIFO portions thereof;
`FIG. 8 is a more detailed functional block diagram of an
`individual MAP element as illustrated in FIGS. 6 and 7;
`FIG. 9 is a user array interconnect diagram illustrating. for
`example,
`t‘our user
`lil’GAs interconnected through
`horizontal. vertical and diagonal buses to allow for expan-
`sion in designs that exceed the capacity of a single FPGA,‘
`FIG. 10 is a functional block diagram of another alterna-
`tive embodiment of the present invention wherein individual
`MAP elements are closely associated with individual
`memory arrays and each of the MAP elements comprises
`independent chain ports for coupling the MAP elements
`directly to each other;
`FIGS. 11A and 11B are timing diagrams respectively
`illustrating input and output timing in relationship to the
`system clock (“Sysclk”) signal
`FIG. 12 is a simplified illustration of a representative
`operating environment for the system and method of the
`
`45
`
`50
`
`55
`
`60
`
`55
`
`

`

`US 6,434,653? B1
`
`5
`The data bus 126 and address bus 128 are also coupled to
`a MAP element 112. The MAP element 112 comprises a
`control block 132 coupled to the address bus 128. The
`control block 132 is also bi-directionally coupled to a user
`field programmable gate array (“FPGA”) 134 by mearts ofa
`number of signal lines 136. The user FPGA 134 is coupled
`directly to the data bus 126. In a particular embodiment, the
`FPGA 134 may be provided as a Lucent Technologies
`()RSTSO device.
`
`The computer architecture 100 comprises a multiproces-
`sor system employing uniform memory access across com-
`mon shared memory with one or more MAP elements 112
`which may be located in the memory subsystem, or memory
`space. As previously described, each MAP element 112
`contains at least one relatively large FPGA 134 that is used
`as a reconfigurable functional unit. In addition, a control
`block 132 and a preprogrammed or dynamically program-
`mable configuration RUM (as will be more fully described
`hereinafter) contains the information needed by the recon-
`figurable MAP element 112 to enable it to perform a specific
`algorithm. It is also possible for the user to directly down-
`load a new configuration into the FPGA134 under program
`control, although in some instances this may consume a
`number of memory accesses and might result in an overall
`decrease in system performance if the algorithm was short—
`lived.
`
`l-‘PGAs have particular advantages in the application
`shown for several reasons. First, commercially available
`F PGAs now contain sufficient internal logic cells to perform
`meaningful computational
`functions. Secondly,
`they can
`operate at speeds comparable to microprocessors, which
`eliminates the need for speed matching buffers. Still further,
`the internal programmable routing resources of FPGAs are
`now extensive enough that mean