United States Patent
`US 6,434,687 Bl
`(10) Patent No.:
`(12)
`Huppenthal
`(45) Date of Patent:
`Aug.13, 2002
`
`
`US006434687B1
`
`(54) SYSTEM AND METHOD FOR
`ACCELERATING WEB SITE ACCESS AND
`PROCESSING UTILIZING A COMPUTER
`SYSTEM INCORPORATING
`RECONFIGURABLE PROCESSORS
`OPERATING UNDERA SINGLE OPERATING
`SYSTEM IMAGE
`
`(75)
`
`Inventor:
`
`Jon M. Huppenthal, Colorado Springs,
`CO (US)
`(73) Assignee: SRC Computers, Inc., Colorado
`Springs, CO (US)
`Subject to any disclaimer, the termofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/888,276
`at
`(22)
`Filed:
`Jum22,2001
`Related U.S. Application Data
`(63) Continuation-in-part of application No. 09/563,561, filed on
`May3, 2000, now Pat. No. 6,339,819, which is a continu-
`ation-in-part of application No. 09/481 ,902,filed on Jan. 12,
`2000, now Pat. No. 6,247,110, which is a continuation of
`application No. 08/992,763, filed on Dec. 17, 1997, now Pal.
`No. 6,076,152.
`
`OTHER PUBLICATIONS
`z
`sas
`Albaharna, Osama,et al., “On the viability of FPGA-based
`integrated coprocessors”, © 1996
`IEEE, Publ. No.
`0-8186-7548-9/96, pp. 206-215.
`Barthel, Dominique Aug. 25-26, 1997, “PVP a Parallel
`Video coProcessor”, Hot Chips IX, pp. 203-210.
`Bittner, Ray, et al., “Computing kernels implemented with a
`wormhole RTR CCM”, © 1997
`JEEE,
`Publ. No.
`0-8186-8159-4/97, pp. 98-105.
`Babb, Jonathan,
`et
`al., “Parallelizi
`lications
`into
`sili-
`ae aaKeeee
`Se cee eee eee ee
`Bertin, Patrice, et al., “Programmable active memories: a
`performance assessment”, © 1993 Massachusetts Institute
`of Technology, pp. 88-102.
`;
`;
`Culbertson, W. Bruce, et al., “Exploring architectures for
`volume visualization on the Teramac custom computer’, ©
`1996 IEEE, Publ. No. 0-8186—7548-9/96, pp. 80-88.
`Culbertson, W. Bruce, et al., “Defect
`tolerance on the
`Teramac custom computer”, © 1997 IEEE, Publ. No.
`0-8186-8159-4/97, pp. 116-123.
`(List continued on next page.)
`.
`:
`;
`Primary Examiner—Kenneth S. Kim
`(74) Attorney, Agent, or Firm—William J. Kubida; Hogan
`& Hartson LLP
`ae
`
`(BQ) Mbconsmicmnawrasacnnansccn GOGE ISG
`
`(52) U.S. Cle ceecssssssssssssssnees 712/32; 707/S01.1; 707/513;
`709/203; 709/219
`
`(57)
`
`(58) Field of Search s.icccccccueca FOT/SOL1, 513;
`709/203, 219; 712/32
`
`(56)
`
`.
`References Cited
`U.S. PATENT DOCUMENTS
`
`ABSTRACT
`7
`i
`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-
`sors may beutilized, for example,in acceleratingsite visitor
`demographic data processing, real time web site content
`updating, database searches and other processing associated
`with e-commerce 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
`5,671,377 A * a? Bleidt et al ........-+----- 345/723
`pea : . mrs rote =e
`os ae may be utilized to cause a cluster of microprocessors to
`ss a Me
`SAS
`TATT
`:
`5,867,706
`¢
`artin et al.
`.....
`it
`i
`SOGTAGO A: #1111909 Donole-etialcacecc 90760.
`“PEtthe wer asa ingle copy of the operating system.
`6,009,410 A * 12/1999 LeMole et al.
`wees 705/14
`...
`6,128,663 A * 10/2000 Thomas.................... 700/228
`
`
`
`25 Claims, 14 Drawing Sheets
`
`on 332
`
`PROCESS
`DATA
`ELEMENT
`N
`
`T
`334u_/
`
`INSTANTIATE fe
`PROCESSING ELEME!
`
`336
`
`ITERATION
`REQUIRED TO
`PROOUCE NEW
`CONTENT
`SELECTION
`
`338
`ro
`
`DISPLAY
`conTeh
`
`230
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 1
`Petitioner Microsoft Corporation - Ex. 1014, p. 1
`
`DEMOGRAPHIC
`Dara
`ELEMENTS:
`
`|
`_
`+
`~
`.
`ie,
`~
`PROCESS,
`PROCESS
`DATA
`TA
`ELEMENT
`ELEMENT
`NAN-2}
`Nene)
`
`PROCESS
`BATA
`ELEMENT
`Naeny
`
`/
`Cal
`
`|
`r
`3342 /
`
`T
`3343 /
`
`_
`NEW CONTENT
`
`
`
`
`
`
`
`
`

`

`US 6,434,687 B1
`
`Page 2
`
`OTHER PUBLICATIONS
`
`Chan, Pak, et al., “Architectural tradeoffs in field—program-
`mable-device—based computing systems”, © 1993 IEEE,
`Publ. No. 0-8186-3890-7/93, pp. 152-161.
`Clark, David, et al., “Supporting FPGA microprocessors
`through retargetable software tools”, © 1996 IEEE, Publ.
`No. 0-8186-7548-9/96, pp. 195-103.
`Cuccaro, Steven, et al., “The CM—2X: a hybrid CM—2/
`Xilink prototype”, © 1993 IEEE, Publ. No, 0-8186-3890-7/
`93, pp. 121-130.
`Dehon, Andre, “DPGA-—Coupled microprocessors: com-
`modity IC for the early 21% century”, © 1994 IEEE, Publ.
`No. 0-8186-5490-2/94, pp. 31-39.
`Dhaussy, Philippe, et al., “Global control synthesis for an
`MIMD/FPGA machine”, © 1994
`IEEE, Pub. No.
`0-8186-5490-2/94, pp. 72-81.
`Deshpande, Deepali, et al., “Hybrid data/configuration cach-
`ing for striped FPGAs” © 1999 TEEE.
`Elliott, Duncan, et al., “Computational Ram: a memo-
`ry-SIMD hybrid and its application to DSP”,© 1992 IEEE,
`Publ. No. 0-7803-0246—X/92, pp. 30.6.1-30.6.4.
`Fortes, Jose, et al., “Systolic arrays, a survey of seven
`projects”, © 1987
`IEEE, Publ. No.
`0018—9162/87/
`0700-0091, pp. 91-103.
`Purna, Karthikeya, et al., “Temporal partitioning and sched-
`uling data How graphs for reconfigurable computers”, ©
`1999 TEEE, Publ, No, 0018—9340/99 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-146.
`Graham, Paul, et al., ““FPGA-based sonar processing”, ©
`1998 ACM 0-89791-978-5/98, pp. 201-208.
`Hauser, John, et al.: “GARP:
`a MIPS processor with a
`reconfigurable co—processor”, © 1997 TEEE, Pub. No.
`0-08 186-8159-4/97, 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
`TEEE,
`Publ. No.
`0-8186-5490-2/94, pp. 139-146.
`Hayes, John, et al., “A microprocessor—based hypercube,
`supercomputer”, © 1986 IEEE, Publ. No. 0272-1732/86/
`1000-0006, pp. 6-17.
`Hagiwara, Hiroshi, et al., “A dynamically microprogram-
`mable computer with low-level parallelism”, © 1980 IEEE,
`Pub. No. 0018-9340/80/07000-0577, pp. 577-594.
`Hasebe, A., et al., “Architecture of SIPS, a real time image
`processing system,” © 1988 IEEE, Publ. No. CH2603—9/
`88/0000/0621, pp. 621-630.
`Jean, Jack, et al., “Dynamic reconfiguration to support
`concurrent
`applications”, © 1999 TEEE, Publ. No.
`0018-9340/99, pp. 591-602.
`Kastrup, Bernardo, et al., “Concise: a compiler—driven
`CPLD-basedinstruction set accelerator”, © 1999 TEEE.
`King, William, et al., “Using MORRPH in an industrial
`machine vision system”, © 1996
`IEEE, Pub. No.
`08186—7548—9/96, pp. 18-26.
`Manohar, Swaminathan, et al., “A pragmatic approach to
`systolic design”, © 1988 IEEE, Publ. No, CH2603—9/
`88—-0000/0463, pp. 463-472.
`
`Motomura, Masato, et al., “An embedded DRAM-FPGA
`chip with instantaneous logic reconfiguration”, © 1998
`IEEE, Publ. No, 0-8186-8900-5/98, pp. 264-266.
`McConnell, Ray, “Massively parallel computing on the
`FUZIONchip”, Aug. 15-17, 1999, Hot Chips 11 Tutorials,
`pp. 83-94.
`McShane, Erik, et al., “Functionally integrated systems on a
`chip:
`technologies, architectures, CAD tools, and applica-
`tions”, © 1998 IEEE, Publ. No, 8-8186-8424—0/98, pp.
`67-75.
`
`Mauduit, Nicolas, et al., “Lneuro 1.0: a piece of hardware
`LEGO for building neural network systems,” © 1992 IEEE,
`Publ. No. 1045—9227/92 pp. 414-422.
`Patterson, David, et al., “A case for intelligent DRAM:
`IRAM”, Hot Chips VIII, Aug. 19-20, 1996, pp. 75-94.
`Peterson, Janes, et al., “Scheduling and partitioning ANSI-C
`programs onto multi-FPGA CCM architectures”, © 1996
`IEEE, Publ. No, 0-8186—7548-9/96, pp. 178-187.
`Rupp, Charley, et al., “The NAPA adaptive processing
`architecture”, © 1998 the Authors, pp. 1-10.
`Saito, Osamu, et al., “A 1M synapse self learning digital
`neural
`network
`chip’, © 1998
`IEEE, Publ. No.
`0-7803—-4344/1/98, pp. 94-95.
`Schott, Brian, et al., “Architectures for system-level appli-
`cations of adaptive computing’, © 1999 TEEE.
`Schmit, Herman, “Incremental reconfiguration for pipelined
`applications,” © 1997 IEEE, Publ. No. 0-8186-8159-4/97,
`pp. 47-55.
`Villasenor, John, et al., “Configurable computing”, © 1997
`Scientific American, Jun. 1997.
`Stone, Harold, “A logic-in-memory computer”, © 1970
`IEEE, IEEE Transactions on Computers, pp. 73-78, Jan.
`1990,
`
`Trimberger, Steve, et al., “A time—multiplexed FPGA”, ©
`1997 IEEE, Publ. No. 0-8186-8159-4/97, pp. 22-28.
`Thornburg, Mike, et al., “Transformable Computers”, ©
`1994 TEEE, Publ. No. 0-8186-5602-6/94, pp. 674-679.
`Tangen, Uwe, et al., “A parallel hardware evolvable com-
`puter POLYP extended abstract”, © 1997 IEEE, Publ. No.
`0-8186-8159/4/97, pp. 238-239.
`Tomita, Shinji, et al., “A computer low-level parallelism
`QA-2”, © 1986 IEEE, No. 0-0384—7495/86/0000/0280,pp.
`280-289.
`
`Ueda, Hirotada, et al., “A multiprocessor system utilizing
`enhanced DSP’s for image processing”, © 1988 IEEE, Publ.
`No. CH2603-—9/88/0000/0611, pp. 611-620.
`Wang, Quiang,et al., “Automated field—-programmable com-
`pute accelerator design using partial evaluation”, © 1997
`IEEE, Publ. No. 0-8186-8159-4/97, pp. 145-154.
`low
`a
`Wirthlin, Michael, et al., “The Nano processor:
`resource reconfigurable processor”, © 1994 IEEE, Publ. No.
`0-8186-5490-2/94, pp. 23-30.
`Wittig, Ralph, et al., “One Chip: An FPGA processor with
`reconfigurable
`logic’, © 1996
`TEEE,
`Publ. No.
`0-8186-7458-9/96, pp. 126-135.
`Wirthlin, Michael, et al., “A dynamic instruction set com-
`puter”, © 1995 IEEE, Publ. No. 0-8186—7086—X/95, pp.
`99-107.
`
`Yamauchi, Tsukasa, et al., “SOP: A reconfigurable massively
`parallel system and its control—data flow based compiling
`method”, © 1996 IEEE, Publ. No, 0-8186—7548-9/96, 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 IEEE,
`Conference
`Paper,
`INSPEC
`Abstract
`Nos.
`B9811—1265B-044, C9811-5210-009,
`Miyamori, Takashi, et al., “A quantitative analysis of recon-
`figurable coprocessors for multimedia applications”, © 1998
`IEEE, Conference
`Paper,
`INSPEC Abstract Nos.
`B9811-1265F-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,
`Mirsky, 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. 3940.
`
`DeHon, 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-57.
`
`Platzner, 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 etal., “PipeRench: 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
`
`

`

`U.S. Patent
`
`Aug. 13, 2002
`
`Sheet 1 of 14
`
`US 6,434,687 BI
`
`160
`
`Memory
`Subsystem
`Bank 0
`
`Memory
`Subsystem
`Bank 1
`
`164
`
`|
`
`|
`|
`
`|
`|
`|
`|
`|
`
`||
`
`14
`
`MEMORY
`
`INTERCONNECT
`
`
`
`120
`
`Processor
`0
`
`MAP
`0
`
`1121
`
`rr4
`|
`
`|
`|
`
`|
`|
`
`12N
`
`|
`|
`i
`
`|
`|
`
`||Processor |
`|
`N
`|
`16m
`|
`
`112N__
`
`—
`
`Memory
`Subsystem
`
`Bank M
`
`10
`
`Fig. 1
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 4
`Petitioner Microsoft Corporation - Ex. 1014, p. 4
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 5¢
`
`d‘pro
`
`U.S. Patent
`
`Aug. 13, 2002
`
`Sheet 2 of 14
`
`US 6,434,687 B1
`
`
`
`iii|iiii!|VOL|b=
`
`
`
`
` "xq-UOTeIOdIO|DJoOsOIOIPYINUIg
`a:O--iVv8ZL|a8Z11|880/1OLL8801!+01
`
`VPELLaW)VPOLL!z90L
`
` dv!(v)2801|souomais|!vVOLL:were!eedv(v)!aszi1|S90L1!'Yb0LmereoHaoe
`aeLLwzZL||azOLLlea.=|StOLLW)L801||SNOLLONYLSNI
`
`
`
`
`
`v8anWw)V9OLL9801|ZLL)i
`vn~)7[we|VECLLVEQLL€d7dv(v)iZyl
`40vdSAMOWSW|WSISTIWuvdGSNANI4!G3NIVYSWIGS[_vw_|:2801=©)NOLLISOdWOO3G
`
`
`
`
`aeSWHLINOOTV
`
`
`
`i¢__SNOIDSY[aww}-——{v)lia)aeetmeet
`
`dv!(v)MSUOSSIOONdMTAT
`dv(v)901=epasz|||
`vz0LL1901
`
` dv(v)iarzi,;SPOlt|801dvi:(os:ra|GECLLiS201}iegoy||SNOILONYLSNI
`
`dv(v)
`
`aezpp|S404:ea|?
`
`liPQOL!
`
`WS|f
`
`:|
`,|SNOILONYLSNI
`
`GANIVeSASYNOod
`NOILISOdWOO3d
`
`VTiveVvd
`
`bNOIDSY
`
`TATIVeVd
`
`@NOISSY
`
`WTWdaVvd
`
`€NOISSY
`
`VaTWavd
`
`¥NOISSY
`
`‘ZOL
`
`2201
`
`&ZOL
`
`"COL
`
`z‘big
`
`
`

`

`
`
`
`
`ANOWSWN9717<]|||||L| SANITMNNUL|=|WSLSAS|e:ssayaav:sh3AVYYV
`_——eegeceecorvetemerenareereetnettwnumtmaemepearrieerenCe,.
`
`t™GOS+*€‘Big<Oer~Be|!vel:||||=||an||a|IOYLNOD|g:ATGWASSVdvyZl3a:JID07|JOYNLNOD|a|yNVa
`
`
`
`IouONIg
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 69‘
`
`
`
`d‘plOl‘xq-UoReIodI0ZDYosoIoIPy
`
`U.S. Patent
`
`—eo
`
`
`

`

`Petitioner Microsoft Corporation - Ex. 1014, p. 7L
`
`‘d‘piol
`
`U.S. Patent
`
`Aug.13, 2002
`
`Sheet 4 of 14
`
`US 6,434,687 B1
`
`Q/L
`
`c8l
`
`SWOU
`
`||
`
`[
`
`Lig-952
`
`WIdaS
`
`YaLyYsANOo
`
`NYALLWd
`
`SZ
`
`OGNVAWOS
`
`y¥5q003d
`
`SANMadld
`
`YSLNNOD
`
`SNINAdld
`
`ALdWaA
`
`OV1d
`
`ZSL;
`
`YslLsiosdd
`
`
`
`
`"xq-UOTeIOdIO|DJoOsOIOIPYINUIg
`
`VOd4d NOILWHNDISGNOOSr
`
`Yasn7OV14OlGNVYadO
`NOILVYNDSISNOD|9+
`
`WOUSey
`OLLisv1
`;!pbiziI|
`NOILVHYNDISZNOD
`F114|QSL
`
`“OL-1ST1IVeVdib
`NOLLVYNDSISNODSLI
`wasnssaydav
`peEecaeTFpeel4
`
`SNLVLSSNLVLS
`
`
`9S1IgdHLd3d
`
`INdLNOGYOM
`SLIGJONLNOD
`
` SNLVLS!|oy—991|SYaLSIDayWOdwSs
`
`ALITWNDA
`
`YOLVEVdWOD
`
`SANMsdld
`
`9EL
`
`
`
`V9d4WOUYS
`
`
`
`
`
`

`

`
`
`
`
`d‘plOl‘xq-UoneIodi0ZDyososoIPyJouONIg
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 8g
`
`
`
`
`
`U.S. Patent
`
`SNOIASYdWOuSs
`
`008
`
`dvW
`
`DT
`
`aSsA>
`
`AVEzs2AYOWAWO=O€t2auvog
`:pswOss390udaaeOohena<O€l VOL
`=pa%es.;G‘blydv
`-RewSo=Oe}3agHOLIMS
`éaeOO
`O€t=yOssa900ud
`AVY-AUOINAINS:aquvog
`
`
`

`

`
`
`
`
`d‘PIOL‘xq-UoNRIOdIO|DosoIOIPYI9UONIg
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 96
`
`
`
`
`
`U.S. Patent
`
`Aug. 13, 2002
`
`Sheet 6 of 14
`
`US 6,434,687 BI
`
`NIVHO
`
`AYOWSW LyOd
`v2cyOv
`
`my
`
`
`
`SSayqdqvSSaYddv
`
`™N—
`—
`
`
`
`
`°TONLNOONOWWOO
`
`
`
`
` HOLIMS9‘blyVAGAYOWAWNOWWOSHLIMAXOWAW
`
`92
`
`
`
`

`

`
`
`
`eSunginoLNNI=avayLNdLNOAEVYNOI4NOOSY
`
`
`
`Ld‘pIOL“xq-UoNeIodi0|yososopyJoUONI
`co6@ZrSie2)-TOYLNOD
`rcZ‘bly
`_pe‘
`bzNIVHODNIVHODvzOS
`
`SOGNVYsdOZpSONVdsdOAYOWSW
`O4l4AVYwading
`INdLNoOINdNI
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 10O
`
`LNdNI
`
`Viva
`
`U.S. Patent
`
`eb=2r6
`
`=S™3a
`
`
`
`

`

`
`
`
`
`l4‘vIOL“Xa-UoNeiodio|yososo1pyJOUONIg
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 11I
`
`
`
`
`
`DN_
`
`ss\9g
`
`—viva5LMANI=AYOWSW
`
`A)7O}v9o—£===W2oOvYeaa«yS>S_16=2el>==:e55
`
`Op
`
`
`Z6+—\\.0609aGNANIVHOa78InowD07)mnvse‘ie5ssayaayOINdNIZ|LNdLNO
`
` =aa5ram9‘big+GvauyNIVHObLSa
`
`
`

`

`14‘vIlOLXa-UoNeIodi0|yososo1pyJoUONOg
`
`eel‘[79:00]ziy<
`
`/ZINve|Ppex|SeTaeSlzejeqjndu|
`
` wT——oaZ[79:00]3ynduyureyo
`=a36[9:00]i0zzyndjno
`=v=o6‘bi4[9:00]
`SsLog
`
`U.S. Patent
`
`9L¢e
`
`90Z
`
`dol
`
`[p9:00]
`
`cl
`
`Wwpee502
`
`11
`
`[79:00]
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 12Z
`
`
`
`
`
`
`
`
`

`

`
` ~.ve~eg>2Sa2OB08aee=Orm2O08|eeeO3m=m5LuOdSIatROsesasmiSO”woYeNIVHO!3<9|a8866==z2si=oog
`22S|=1uYOd=as|!<NIVHOa||vz||Zez=dVVQCZ!5SNOIASYd|WHpZpeOPTWOpPZ|>WOUSsL=~aoaoeK=)
` =a™SpeONSspretye020ve+dV~.
`
`LXANSQmnOLO~ega2
`008©©9LYOd~aeNIVHO
`ye)
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 13€1
`
`
`
`
`
`4‘PLO‘Xq-uoryes0d10_5yososo1fyIou0TOg
`
`
`
`
`
`
`
`
`
`

`

`
`
`
`
`l4d‘pIOl“xq-UoneIodiogyososspyJoUONOg
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 14v
`
`
`
`
`
`3=uF
`
`VLL‘big—ae2ejegjndy|aeyeqpileo3bwe—SUOQOL—_<S9olldSd
`
`
`=>SUG~«~y4JOSAS
`
`—eo~‘SGLL‘big—ae
`
`_
`
`
`
` N_——- SUQL—p:
`
`
`
`SeaSsE}eqPIleA
`
`
`
`oSB}eqyndjno
`
`yOLIGSd
`
`yZlidSd
`
`U.S. Patent
`
`—eSUG~«ea
`
`SUG*|
`
`yJOSAS
`
`

`

`U.S. Patent
`
`Aug. 13, 2002
`
`Sheet 12 of 14
`
`US 6,434,687 BI
`
`USER PC
`
`308
`
`
`
`
`
`
`
`TYPICAL
`WEB SITE
`SERVER
`
`SRC 6
`RECONFIGURABLE
`SERVER
`
`300
`
`Fig. 12
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 15
`Petitioner Microsoft Corporation - Ex. 1014, p. 15
`
`

`

`U.S. Patent
`
`Aug.13, 2002
`
`Sheet 13 of 14
`
`US 6,434,687 BI
`
`312
`
`314
`
`N ITERATIONS REQUIRED TO
`PRODUCE NEW CONTENT
`SELECTION
`
`
`
`N
`DEMOGRAPHIC
`DATA
`ELEMENTS
`
`
`
`
`
`PROCESS
`DATA
`ELEMENT
`
`NO
`
`
` DATA
`ELEMENT
`
`=N
`
`Yes
`
`318
`
`
`SELECT
`NEW CONTENT
`
`
`
`
` DISPLAY
`UPDATED
`CONTENT
`
`
`31
`
`Fig. 13
`Prior Art
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 16
`Petitioner Microsoft Corporation - Ex. 1014, p. 16
`
`

`

`U.S. Patent
`
`Aug. 13, 2002
`
`Sheet 14 of 14
`
`US 6,434,687 B1
`
`332
`
`
`
`
`N
`DEMOGRAPHIC
`DATA
`ELEMENTS
`
`
`
`.
`
`.
`
`.
`INSTANTIATE N
`PROCESSING ELEMENTS
`
`
`
`PROCESS
`DATA
`ELEMENT
`N
`
`i
`
`
`
`PROCESS
`DATA
`ELEMENT
`N-(N-1)
`
`PROCESS
`DATA
`ELEMENT
`N-(N-2)
`
`PROCESS
`DATA
`ELEMENT
`N-(N-3)
`
`
`
`3344
`
`
`334n
`336
`
`os
`
`SELECT
`NEW CONTENT
`
`
`
`DISPLAY
`UPDATED
`CONTENT
`
`
`
`
`\
`
`i
`
`‘TERIOR
`REQUIRED TO
`PRODUCE NEW
`CONTENT
`SELECTION
`
`30
`
`Fig. 14
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 17
`Petitioner Microsoft Corporation - Ex. 1014, p. 17
`
`

`

`US 6,434,687 B1
`
`1
`SYSTEM AND METHOD FOR
`ACCELERATING WEB SITE ACCESS AND
`PROCESSING UTILIZING A COMPUTER
`SYSTEM INCORPORATING
`RECONFIGURABLE PROCESSORS
`OPERATING UNDER A SINGLE OPERATING
`SYSTEM IMAGE
`
`CROSS REFERENCE TO RELATED PATENT
`APPLICATIONS
`
`The present invention is a continuation-in-part application
`of U.S. patent application Ser. No. 09/563,561 filed May 3,
`2000, now issued U.S. Pat. No. 6,339,819 B1, which is a
`continuation-in-part application of U.S. patent application
`Ser. No. 09/481,902 filed Jan. 12, 2000, now issued U.S. Pat.
`No. 6,247,110 which is a continuation of U.S. patent appli-
`cation Ser. No, 08/992,763 filed Dec. 17, 1997 for: “Mul-
`tiprocessor Computer Architecture Incorporating a Plurality
`of Memory Algorithm Processors in the Memory
`Subsystem”, now issued U.S. 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 OF THE INVENTION
`
`in general, to the field of
`The present invention relates,
`computer architectures incorporating multiple processing
`elements such as multi-adaptive processors (*“MAP™”,is a
`trademark of SRC Computers,
`Inc., 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 of electronic 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 somesites 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 previoussites 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 that particular 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 effort is placed into maximiz-
`ing the software performance of algorithmsthat process the
`user demographic data. Currently, all known webservers
`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 “load/store” archi-
`tecture.
`
`SUMMARY OF THE INVENTION
`
`SRC Computers, Inc., assignee ofthe present invention, is
`an industry leader in the design and development of multi-
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`processor computer systems including those employing
`industry standard processors together with multi-adaptive
`processors (“MAP™”)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
`microprocessors and a number ofreconfigurable 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 recon-
`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 L000
`times faster than a standard microprocessor based server.
`As an exemplary implementation, one particularly effica-
`cious hybrid computing system is the SRC Computers, Inc.
`SRC-6 incorporating multi-adaptive processors (MAP). In
`such a system, the algorithms loaded into the MAPelements
`to process the data can be completely changed in under 100
`msec. This allows forthe 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™ (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 input/output
`(“I/O”) 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-commerce, 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-6, 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 website
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 18
`Petitioner Microsoft Corporation - Ex. 1014, p. 18
`
`

`

`US 6,434,687 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
`
`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 (*“MAP™”) 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 MAPelements located, for
`example, in the computer system memory space, in accor-
`dance with a particular embodiment of the present invention;
`FIG. 3 is a more detailed functional block diagram ofan
`exemplary individual one of the MAP elements of the
`preceding figures and illustrating the bank control logic,
`memory array and MAPassembly thereof;
`FIG. 4 is a more detailed functional block diagram of the
`control block of the MAPassembly 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
`MAPelements 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 buffer 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,
`four user FPGAs interconnected through
`horizontal, vertical and diagonal buses to allow for expan-
`sion in designs that exceed the capacity of a single FPGA;
`FIG. 10is 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. LIA and UB 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
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`invention including a typical web site server as
`present
`would be replaced by an SRC-6 reconfigurable server;
`FIG. 13 is a flowchartillustrating a conventional data
`processing sequence in a conventional application of the
`typical website server depicted in the preceding figure. and
`FIG, 14 is a corresponding flowchart
`illustrating the
`processing of demographic or other data utilizing a recon-
`figurable 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
`10 architecture in accordance with one embodimentof the
`present invention is shown. The multiprocessor computer 10
`incorporates N processors 12,
`through 12,, which are
`bi-directionally coupled to a memory interconnectfabric 14.
`The memory interconnect fabric 14 is then also coupled to
`M memory banks comprising memory bank subsystems 16,
`(Bank 0) through 16M (Bank M). N number of multi-
`adaptive processors (*MAP™”) 112, 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) four
`parallel regions 102, through 102, inclusive. The instruc-
`tions and data output from each ofthe parallel regions 102,
`through 102, are respectively input
`to parallel
`regions
`segregatedinto data areas 104, through 104, and instruction
`areas 106, through 106,. Data maintained in the data areas
`104,
`through 104, and instructions maintained in the
`instruction areas 106, through 106, are then suppliedto, for
`example, corresponding pairs of processors 108,, 108, (P1
`and P2); 108,, 108, (P3 and P4); 108., 108, (PS and P6);
`and 108,, 108, (P7 and P8) as shown. Atthis 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 108,
`through 108,,
`is
`broken up,
`for example,
`into a number of fundamental
`algorithms “°,,, 110,,, 110,,, 110,,
`through 110,, as
`shown. Each of the algorithms is then supplied to a corre-
`sponding one of the MAP elements 112,,, 112,,, 112.,,
`112,,,, through 112,,, 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 112illustrated
`in the preceding figure. Each memory bank 120 includes a
`bank control logic block 122 bi-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-directional 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 130.
`
`Petitioner Microsoft Corporation - Ex. 1014, p. 19
`Petitioner Microsoft Corporation - Ex. 1014, p. 19
`
`

`

`US 6,434,687 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 means of a
`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
`OR3T80 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 ROM (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 FPGA 134 under program
`control, although in some instances this may consume a
`number of memory accesses and mightresult in an overall
`decrease in system performance if the algorithm wasshort-
`lived.
`
`FPGAs have particular advantages in the application
`shown for several reasons. First, commercially available
`FPGAsnow contain sufficient internal logic cells to perform
`meaningful computational
`functions. Secondly,
`they can
`operate al 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 meaningful algorithms can now
`be programmedwithout the need to reassign the locations of
`the input/output ("1/0")