Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 1 of 32 PageID# 86
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 1 of 32 Page|D# 86
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT C
`EXHIBIT C
`
`
`
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 2 of 32 PageID# 87
`Case 2:17-cv-00547-RAJ-RJK Document III”IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIMIIIIIIIIIII 87
`
`US007225324B2
`
`United States Patent
`(12)
`(10) Patent No.:
`US 7,225,324 B2
`
`Huppenthal et a].
`(45) Date of Patent:
`May 29, 2007
`
`5,570,040 A
`5,640,586 A *
`5737766 A
`5,784,108 A *
`5,892,962 A
`g’ggg’gé :
`,
`,
`5,956,518 A
`6,023,755 A
`6,052,773 A
`6,061,706 A *
`6,076,152 A
`6,192,439 B1
`6,215,898 B1 *
`6,226,776 Bl
`6,289,440 B1*
`6,385,757 B1*
`
`(54) MULTI-ADAPTIVE PROCESSING SYSTEMS
`AND TECHNIQUES FOR ENHANCING
`PARALLELISM AND PERFORMANCE OF
`COMPUTATIONAL FUNCTIONS
`
`(75)
`
`Inventors: Jon M. Huppenthal, Colorado Springs,
`,
`,
`COWS); DaVId E- Callga, C010rad0
`Springs, CO (US)
`
`(73) Assigneei SRC Computers, Inca Colorado
`Springs, CO (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term ofthjs
`patent is extended or adjusted under 35
`U.S.C. 15403) by 550 days.
`
`(21) Appl. No.. 10/285,318
`
`(22)
`
`Filed:
`
`OCt- 31: 2002
`
`(65)
`
`Prior Publication Data
`
`US 2004/0088527 A1
`
`May 6, 2004
`
`(51)
`
`Int. Cl,
`(2006.01)
`G06F 17/00
`(52) US. Cl.
`...................................................... 712/226
`(58) Field of Classification Search .................. 712/15,
`712/19, 226,215
`See application file for complete search history.
`
`(56)
`
`References Cited
`U. S. PATENT DOCUMENTS
`
`2/1988 McWhiIter
`4,727,503 A
`10/ 1989 Leeland ...................... 708/509
`4,872,133 A *
`4,962,381 A * 10/1990 Helbig, Sr.
`................. 342/372
`5,0205059 A
`5/1991 Gorin et 3L
`57072371 A * ”“991 Belmer et 31' """""""" 712/11
`5,230,057 A
`7/1993 Shldo et al.
`5,274,832 A * 12/1993 Khan ......................... 708/424
`5,471,627 A
`11/1995 Means et al.
`5,477,221 A
`12/1995 Chang et a1.
`
`............. 712/ 13
`
`..... 375/240.15
`
`10/1996 Lytle et a1.
`6/1997 Pechanek et al.
`4/1998 Tan
`7/1998 Skaletzky et a1.
`4/1999 Cloutier
`31333 Ego et al'
`1rsky et a1.
`9/1999 DeHon et a1.
`2/2000 Casselman
`4/2000 DeHon et al.
`5/2000 Gai et a1.
`................... 708/491
`6/2000 Huppenthal et a1.
`2/2001 Grunewald et a1.
`4/2001 Woodfill et a1.
`............ 382/154
`5/2001 Pandllfl et 31~
`9/2001 Casselman .................. 712/227
`5/2002 Gupta et al.
`................... 716/1
`
`................ 712/16
`................ 712/15
`
`OTHER PUBLICATIONS
`
`Rosenberg, J. M., Dictionary of Computers , Information Processing
`&Telecommunicati0ns, 1984, John Wiley&S0ns, 2ed, pp. 496*
`.
`(Cont1nued)
`
`Primary ExamineriEric Coleman
`(74) Attorney, Agent, or Firm7William J. Kubida; Michael
`C. Martensen; Hogan & Hartson LLP
`
`(57)
`
`ABSTRACT
`.
`.
`.
`.
`for
`Mult1-adapt1ve processmg systems and techn1ques.
`enhanc1ng parallehsm and performance of computatlonal
`functions are disclosed which can be employed in a myriad
`of appllcatlons .1nclud1ng .multl-dlmens1onal p1pe11ne .com-
`putat1ons for selsmlc appl1catlons, search algorithms, 1nfor-
`mation security, chemical and biological applications, fil-
`tering and the like as well as for systolic wavefront
`computations for fluid flow and structures analysisa bioin-
`formatics etc. Some applications may also employ both the
`multi-dimensional pipeline and systolic wavefront method-
`ologies disclosed
`'
`
`52 Claims, 20 Drawing Sheets
`
`
`
`
`
`
`
`
`c9o9'9c
`
`
`’9';0%.:’9‘:.3”:’e‘:’3”:09.,0‘...
`
`
`
`
`
`
`
`
`
`3”:0:00:0:00:9:00:
`
`e
`
`
`
`ADDITIONAL
`ADAPTIVE
`PROCESSOR
`
`CHIPS
`
`
`
`
`
`
`206
`
`MEMORY
`
`
`
`o9¢.9.99
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INTERCONNECT
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 3 of 32 PageID# 88
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 3 of 32 Page|D# 88
`
`US 7,225,324 B2
`Page 2
`
`OTHER PUBLICATIONS
`
`Agarwal, A., et a1., “The Raw Compiler Project”, pp. 1-12, http://
`cag-www.lcs.mit.edu/raw, Proceedings of the Second SUIF Com-
`piler Workshop, Aug. 21-23, 1997.
`Albaharna, Osama, et a1., “On the viability of FPGA-based inte-
`grated coprocessors”, © 1996 IEEE, Publ. No. 0-8186-7548-9/96,
`pp. 206-215.
`Amerson, Rick, et a1., “Teramac4Configurable Custom Comput-
`ing”, © 1995 IEEE, Publ. No. 0-8186-7086-X/95, pp. 32-38.
`Barthel, Dominique Aug. 25-26, 1997, “PVP a Parallel Video
`coProcessor”, Hot Chips IX, pp. 203-210.
`Bertin, Patrice, et a1., “Programmable active memories: a perfor-
`mance assessment”, © 1993 Massachusetts Institute of Technology,
`pp. 88-102.
`Bittner, Ray, et a1., “Computing kernels implemented with a worm-
`hole RTR CCM”, © 1997 IEEE, Publ. No. 0-8186-8159-4/97, pp.
`98-105.
`Buell, D., et a1. “Splash 2: FPGAs in a Custom Computing
`MachineiChapter liCustom Computing Machines: An Introduc-
`tion”, pp. 1-11, http://www.computer.org/espress/catalog/bp07413/
`spls-chl.htm1 (originally believed published in J. of Supercomput-
`ing, vol. IX, 1995, pp. 219-230.
`Casselman, Steven, “Virtual Computing and The Virtual Com-
`puter”, © 1993 IEEE, Publ. No. 0-8186-3890-7/93, pp. 43-48.
`Chan, Pak, et a1., “Architectural tradeoffs in field-programmable-
`device-based computing systems”, © 1993 IEEE, Publ. No. 0-8186-
`3890-7/93, pp. 152-161.
`Clark, David, et a1., “Supporting FPGA microprocessors through
`retargetable software tools”, © 1996 IEEE, Publ. No. 0-8186-7548-
`9/96, pp. 195-103.
`Cuccaro, Steven, et a1., “The CM-2X: a hybrid CM-2/Xi1ink pro-
`totype”, © 1993 IEEE, Publ. No. 0-8186-3890-7/93, pp. 121-130.
`Culbertson, W. Bruce, et al., “Exploring architectures for volume
`visualization on the Teramac custom computer”, © 1996 IEEE, Pub.
`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.
`
`Dehon, Andre, “DPGA-Coupled microprocessors: commodity IC
`for the early 21St century”, © 1994 IEEE, Publ. No. 0-8186-5490-
`2/94, pp. 31-39.
`Dehon, A., et a1., “MATRIX A Reconfigurable Computing Device
`with Configurable Instruction Distribution”, Hot Chips IX, Aug.
`25-26, 1997, Stanford, California, MIT Artificial Intelligence Labo-
`ratory.
`Dhaussy, Philippe, et a1., “Global control synthesis for an MIMD/
`FPGA machine”, © 1994 IEEE, Publ. No. 0-8186-5490-2/94, pp.
`72-81.
`
`Elliott, Duncan, et a1., “Computational Ram: a memory-SIMD
`hybrid and its application to DSP”, © 1992 IEEE, Publ. No.
`0-7803-0246-X/92, pp. 30.61-30.64.
`Fortes, Jose, et al., “Systolic arrays, a survey of seven projects”, ©
`1987 IEEE, Publ. No. 0018-9162/87/0700-0091, pp. 91-103.
`Gokhale, M., et a1., “Processing in Memory: The Terasys Massively
`Parallel PIM Array” © Apr. 1995, IEEE, pp. 23-31.
`Gunther, Bernard, et a1., “Assessing Document Relevance with
`Run-Time Reconfigurable Machines”, © 1996 IEEE, Publ. No.
`0-8186-7548-9/96, pp. 10-17.
`Hagiwara, Hiroshi, et a1., “A dynamically microprogrammable
`computer with low-level parallelism”, © 1980 IEEE, Publ. No.
`0018-9340/80/07000-0577, pp. 577-594.
`Hartenstein, R. W., et al. “A General Approach in System Design
`Integrating Reconfigurable Accelerators,” http://Xputers.informatik.
`uni-k1.de/papers/paper026-l.htrnl, IEEE 1996 Conference, Austin,
`TX, Oct. 9-11, 1996.
`Hartenstein, Reiner, et a1., “A reconfigurable data-driven ALU for
`Xputers”, © 1994 IEEE, Publ. No. 0-8186-5490-2/94, pp. 139-146.
`Hauser,
`John,
`et
`a1.:
`“GARP:
`a MIPS processor with a
`reconfigurable co-processor”, © 1997 IEEE, Publ. No. 0-08186-
`8159-4/97, pp. 12-21.
`
`“A microprocessor-based hypercube,
`a1.,
`et
`John,
`Hayes,
`supercomputer”, © 1986 IEEE, Publ. No. 0272-1732/86/1000-
`0006, pp. 6-17.
`Herpel, H.-J., et a1., “A Reconfigurable Computer for Embedded
`Control Applications”, © 1993 IEEE, Publ. No. 0-8186-3890-7/93,
`pp. 111-120.
`Hogl, H., et al., “Enable++: A second generation FPGA processor”,
`© 1995 IEEE, Publ. No. 0-8186-7086-X/95, pp. 45-53.
`King, William, et a1., “Using MORRPH in an industrial machine
`vision system”, © 1996 IEEE, Publ. No. 08186-7548-9/96, pp.
`18-26.
`Manohar, Swaminathan, et a1., “A pragmatic approach to systolic
`design”, © 1988 IEEE, Publ. No. CH2603-9/88/0000/0463, pp.
`463-472.
`Mauduit, Nicolas, et a1., “Lneuro 1.0: a piece of hardware LEGO for
`building neural network systems,” © 1992 IEEE, Publ. No. 1045-
`9227/92, pp. 414-422.
`Mirsky, Ethan A., “Coarse-Grain Reconfigurable Computing”, Mas-
`sachusetts Institute of Technology, Jun. 1996.
`Mirsky, Ethan, et a1., “MATRIX: A Reconfigurable Computing
`Architecture with Configurable
`Instruction Distribution and
`Deployable Resources”, © 1996 IEEE, Publ. No. 0-8186-7548-9/
`96, pp. 157-166.
`Morley, Robert E., Jr., et a1., “A Massively Parallel Systolic Array
`Processor System”, © 1988 IEEE, Publ. No. CH2603-9/88/0000/
`0217, pp. 217-225.
`Patterson, David, et a1., “A case for intelligent DRAM: IRAM”, Hot
`Chips VIII, Aug. 19-20, 1996, pp. 75-94.
`Peterson, Janes, et a1., “Scheduling and partitioning ANSI-C pro-
`grams onto multi-FPGA CCM architectures”, © 1996 IEEE, Publ.
`No. 0-8186-7548-9/96, pp. 178-187.
`Schmit, Herman, “Incremental reconfiguration for pipelined appli-
`cations,” © 1997 IEEE, Publ. No. 0-8186-8159-4/97, pp. 47-55.
`Sitkoff, Nathan, et a1., “Implementing a Genetic Algorithm on a
`Parallel Custom Computing Machine”, Publ. No. 0-8186-7086-X/
`95, pp. 180-187.
`Stone, Harold, “Alogic-in-memory computer”, © 1970 IEEE, IEEE
`Transactions on Computers, pp. 73-78, Jan. 1990.
`Tangen, Uwe, et a1., “A parallel hardware evolvable computer
`POLYP extended abstract”, © 1997 IEEE, Publ. No. 0-8186-8159/
`4/97, pp. 238-239.
`Thornburg, Mike, et a1., “Transformable Computers”, © 1994 IEEE,
`Publ. No. 0-8186-5602-6/94, pp. 674-679.
`Tomita, Shinji, et al., “A computer low-level parallelism QA-2”, ©
`1986 IEEE, Publ. No. 0-0384-7495/86/0000/0280, pp. 280-289.
`Trimberger, Steve, et a1., “A time-multiplexed FPGA”, © 1997
`IEEE, Publ. No. 0-8186-8159-4/97, pp. 22-28.
`Ueda, Hirotada, et a1., “A multiprocessor system utilizing enhanced
`DSP’s for image processing”, © 1988 IEEE, Publ. No. CH2603-9/
`88/0000/0611, pp. 611-620.
`Villasenor, John, et al., “Configurable computing”, © 1997 Scien-
`tific American, Jun. 1997.
`Wang, Quiang, et al., “Automated field-programmable compute
`accelerator design using partial evaluation”, © 1997 IEEE, Publ.
`No. 0-8186-8159-4/97. pp. 145-154.
`W.H. Manglone-Smith and BL. Hutchings. Configurable comput-
`ing: The Road Ahead. In Proceedings of the Reconfigurable Archi-
`tectures Workshop (RAW’97), pp. 81-96, 1997.
`Wirthlin, Michael, et a1., “The Nano processor: a low resource
`reconfigurable processor”, © 1994 IEEE, Publ. No. 0-8186-5490-
`2/94, pp. 23-30.
`Wirthlin, Michael, et al., “A dynamic instruction set computer”, ©
`1995 IEEE, Publ. No. 0-8186-7086-X/95, pp. 99-107.
`Wittig, Ralph, et al., “One Chip: An FPGA processor with
`reconfigurable logic”, © 1996 IEEE, Publ. 0-8186-7548-9/96, pp.
`126-135.
`
`Yamauchi, Tsukasa, et a1., “SOP: A reconfigurable massively par-
`allel system and its control-data flow based compiling method”, ©
`1996 IEEE, Publ. No. 0-8186-7548-9/96, pp. 148-156.
`“Information Brief”, PCI Bus Technology, © IBM Personal Com-
`puter Company, 1997, pp. 1-3.
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 4 of 32 PageID# 89
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 4 of 32 Page|D# 89
`
`US 7,225,324 B2
`Page 3
`
`Yun, Hyun-Kyu and Silverman, H. F.; “A distributed memory
`MIMD multi-computer with reconfigurable custom computing
`capabilities”, Brown University, Dec. 10-13, 1997, pp. 7-13.
`Hoover, Chris and Hart, David; “San Diego Supercomputer Center,
`Timelogic and Sun Validate Ultra-Fast Hidden Markov Model
`Analysis-One DeCypher-accelerated Sun Fire 6800 beats 2,600
`CPUs running Linux-”, San Diego Supercomputer Center, http://
`www.sdsc.edu/Press/02/050802,markovmodel.html, May 8, 2002,
`pp. 1-3.
`Caliga, David and Barker, David Peter, “Delivering Acceleration:
`The Potential for Increased HPC Application Performance Using
`Reconfigurable Logic”, SRC Computers, Inc., Nov. 2001, pp. 20.
`Hammes, J.P., Rinker, R. E.; McClure, D, M., Bohm, A. P. W.,
`Najjar, W. A., “The SA-C Compiler Dataflow Description”, Colo-
`rado State University, Jun. 21, 2001, pp. 1-25.
`Callahan, Timothy J. and Wawrzynek, John, “Adapting Software
`Pipelining for Reconfigurable Computing”, University of California
`at Berkeley, Nov. 17-19, 2000, pp. 8.
`Ratha, Nalini K., Jain, Anil K. and Rover, Diane T., “An FPGA-
`based Point Pattern Matching Processor with Application to Fin-
`gerprint Matching”, Michigan State University, Department of
`Computer Science, pp. 8.
`Dehon, André, “Comparing Computing Machines”, University of
`California at Berkeley, Proceedings of SPIE vol. 3526, Nov. 2-3,
`1998, pp. 11.
`Vemuri, Ranga R. and Harr, Randolph E., “Configurable Comput-
`ing: Technology and Applications”, University of Cincinnati and
`Synopsys Inc., IEEE, Apr. 2000, pp. 39-40.
`Dehon, André, “The Density Advantage of Configurable Comput-
`ing”, California Institute of Technology, IEEE, Apr. 2000. pp. 41-49.
`Haynes, Simon D., Stone, John, Cheung, Peter Y.K. and Luk,
`Wayne, “Video Image Processing with the Sonic Architecture”,
`Sony Broadcast & Professional Europe, Imperial College, Univer-
`sity of London, IEEE, Apr. 2000, pp. 50-57.
`Platzner , Marco, “Reconfigurable Accelerators for Combinatorial
`Problems”, Swiss Federal Institute of Technology (ETH) Zurich,
`IEEE, Apr. 2000, pp. 58-60.
`Callahan, Timothy J., Hauser, John R. And Wawrzynek, John, “The
`Garp Architecture and C Compiler”, University of California,
`Berkeley, IEEE, April 2000, pp. 62-69.
`Goldstein, Seth Copen, Schmit, Herman, Budiu , Mihai, Cadambi,
`Srihari, Moe, Matt
`and Taylor, R. Reed,
`“PipeRench: A
`Reconfigurable Architecture and Compiler”, Carnegie Mellon Uni-
`versity, IEEE, Apr. 2000, pp. 70-76.
`Muchnick, Steven S., “Advanced Compiler Design and Implemen-
`tation”, Morgan Kaufmann Publishers, pp. 217.
`
`SA-C To
`“Compiling
`P., Dissertation
`Jeffrey
`Hammes,
`Reconfigurable Computing Systems”, Colorado State University,
`Department of Computer Science, Summer 2000, pp. 179.
`Automatic Target Recognition, Colorado State University & USAF,
`http://www.cs.colostate.edu/cameron/applications.htrnl, pp. 1-3.
`Chodowiec, Pawel, Khuon, Po, Gaj, Kris, Fast Implementations of
`Secret-Key Block Ciphers Using Mixed Inner- and Outer-Round
`Pipelining, George Mason University, Feb. 11-13, 2001, pp. 9.
`Miyamori, Takashi, “REMARC: Reconfigurable Multimedia Array
`Coprocessor”, IEICE Transactions on Information and Systems,
`Information & Systems Society, Tokyo, JP, vol. E82-D, No. 2, Feb.
`1999, pp. 389-397, XP000821922.
`Gross Thomas, et a1., “Compilation for a High-performance Systolic
`Array”, Sigplan Notices USA, vol. 21, No. 7, Jul. 1986, pp. 27-38,
`XP002418625.
`
`Rauchwerger, Lawrence, et al., “The LRPD Test: Speculative Run-
`Time Parallelization of Loops with Privatization and Reduction
`Parallelization”, IEEE Transaction on Parallel and Distributed Sys-
`tems, IEEE Service Center, Los Alamitos, CA, vol. 10, No. 2, Feb.
`1999, pp. 160-180, XP000908318.
`Arnold Jeffrey M. et al., “The Splash 2 Processor and Applications”,
`Computer Design: VLSI in Computers and Processors, 1993, ICCD
`’93 Proceedings, 1993 IEEE International Conference on Cam-
`bridge, MA, Oct. 3-6 1993, Los Alamitos, CA, IEEE Comput. Soc.,
`Oct. 3, 1993, pp. 482-485, XP010134571.
`Hwang, Kai, “Computer Architecture and Parallel Processing”,
`Data Flow Computers and VLSI Computations, 1985, McGraw
`Hill, Chapter 10, pp. 732-807, XP-002418655.
`Hartenstein, Reiner W., et al. “A Synthesis System for Bus-based
`Wavefront Array Architectures”, Proceedings, International Confer-
`ence on Application-Specific Systems, Architecture and Processors,
`1996, pp. 274-283, XP002132819.
`Alexander, Thomas, et al. “A Reconfigurable Approach To A
`Systolic Sorting Architecture”, ISCAS 89, May 8, 1989, pp. 1178-
`1182, XP010084477.
`Wu, Youfeng, et a1. “Better Exploration of Region-Level Value
`Locality with Integrated Computation Reuse and Value Prediction”,
`Proceedings of the 28th International Symposium on Computer
`Architecture, ISCA 2001, Goteberg, Sweden, Jun. 30-Ju1. 4, 2001,
`International Symposium on Computer Architecture, (ISCA), Los
`Alamitos, CA, IEEE Comp. Soc, US, Jun. 30, 2001, pp. 93-103,
`XP010552866.
`
`* cited by examiner
`
`

`

`8
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 5 of 32 PageID# 90
`m
`R
`C
`m
`09
`m
`
`nmF.3le3nNS
`
`.m7,5S
`
`
`mmm5:ozimfimao
`
`m.U£8.2652%:me
`
`
`mmw.M.t<3.2m
`
`eomU
`
`0eWtCa_mm2w.P2::v825of?2::3::5::8v?
`
`mt
`
`1..M
`
`%nn3n3n31:n3n3n3
`
`Ft
`
`W012
`
`
`
`B$53.65530
`
`d,m59%92in...............I39%0.2m1O:o:O:o:
`
`
`
`e2oeo:H«Mmoo_mm-mmkz_zmormwemmémpz.omoro:
`
`2
`
`
`
`m.Wmammew,EoEzmormammamhzoEomor
`
`D9,E055:$0.52
`
`
`
`u7mmjomkzoommjoEzoommo:oz<.E05529.oz<5.05me
`
`m2N9AmSEEIEOZV0N9meoEmIEoé
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 6 of 32 PageID# 91
`C
`
`W.PMQM%U
`
`mmm.mN.51%
`
` ...I29O7Mmmom%n=IUmOmmmoomam>_._.n_<n_<mm9N
`
`wm9
`mm,J<ZO_H_DD<...Kw9.50.3049macccMMmaaaam0.0‘ootoo‘f‘fMtas...............@3333
`
`
`

`

`0012dfmmHaeowh1S
`
`3nf9O77Sm.U
`
`g4a2pm
`
`#2mB
`
`Onomwa7P2Se0aU
`
`t
`
`n22
`
`zoEoEnZ
`
`m7cw02D9,K2JWR.M
`moz<§m0mmmm
`
`Egmfigm
`
`\\
`
`Dwm<wmoz_
`
`\
`
`\
`
`._.Om_n_mm_n_
`
`>.._._.__m<._<om
`
`e
`tne
`aP71/8l/
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 7 of 32 PageID# 9229
`5
`.JARM
`C
`2
`
`>._._.:m<._<o.w
`
`ZO_.r<O_._n_n_<\
`
`mm.mt
`
`«a.mi
`
`
`
`55‘105E
`
`
`
`memmmoomm.oz
`
`
`
`mmowmmOOma.oz
`
`iNEIWEIAOHleI EIONVWHOdHEId
`
`.\
`
`\
`
`ZOF<OZnE<
`
`tj_m<._<0m
`
`._.Om_n_mm_n.
`
`>._._.=m<._<om
`
`iNElWEIAOEIdWI EONVWHOleEd
`
`
`
`
`
`
`

`

`e
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 8 of 32 PageID# 9339#
`C
`
`g4mmm
`
`mm
`
`wa7.P1O2Se0aU
`
`aw.5.BE2nm7,9.8smukSatm.U......................................mnmmm73|mm00mmnuuum8nuu.Muun._00_u__.12u.u.fzo_mzm_>__o"uuumManuw¥10>>
`>EE3Uon>95Mmmmwmoszzszmm__m>_5<z_._mn69-mmm20wxmoz,mmoo;-mm_m_>_5<__<n59-mn0).,rZO_WZM_>:Dmmwwm<In_m<@004mm«W20mxmog<109-m<n_OO._mmmRWFmmsi“mmmM.mmumR.wN;MWNewmMtunuu5unu::.---:-:mm.mn.....................................................
`m_1004-mmQ00:—m..m>;0<..mn_OO._-mmn_OO|_mE.amzo_mzm_>__o
`__m_>_5<z_._<mmmhnwm3m20$53559-mmNmmuSNmm<IamEvmmvowmn.uuumASmn
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 9 of 32 PageID# 94
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 10 of 32 PageID# 95
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 10 of 32 Page|D# 95
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 6 of 20
`
`US 7,225,324 B2
`
`V
`N
`LO
`
`(0
`N
`LO
`
`'0
`
`.97
`LL
`
`:3
`E
`
`
`
`15'
`E
`
`E
`
` a-é\\ a-<(
`
`(D
`UJ
`0')
`<1:
`I
`D.
`9
`l—
`E
`2)
`CL
`E
`8
`
`|
`
`.—
`[l
`g
`
`___
`
`m
`S
`
`Q g
`
`><|
`E
`[L
`<
`E
`
`LU
`
`502
`
`ZI
`
`— D O[
`
`I
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 11 of 32 PageID# 96
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 11 of 32 Page|D# 96
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 7 of 20
`
`US 7,225,324 B2
`
`
`
`DJmEmm>_m_0m_mum
`
`
`
`D:_m__u_momDOmnw
`
`mmo
`
`n_E
`
`qmw
`
`
`
`wFOImmw>On_OO._
`
`
`
`
`
`
`
`35132
`
`N;
`
`Nm0<_>__
`
` >._._OO._m>n>
`
`rlltANCNEAENEr]
` H
`
`AMEN;9mm
`+u|EE<§I]
`-u|_En_<_>_j
`55%:I]
`Nmeg):1]
`
`0%
`
`NS
`
`#Nm
`
`vmm
`
`omm
`
`
`
`
`
`
`
`
`
`35$).
`
`+u1_E<_>_
`
`
`
`omm
`
`Nmm
`
`fvmm
`
`omm
`
`+35%J
`
`
`
`
`
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 12 of 32 PageID# 97
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 12 of 32 Page|D# 97
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 8 of 20
`
`US 7,225,324 B2
`
`dd:Eb
`
`NNm
`
`omm
`
`
`
`
`
`
`
`39r51mEEwrnmfimn_<_>_
`
`kaImmw>O@004
`
`www
`
`mmw
`
`
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 13 of 32 PageID# 98
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 13 of 32 Page|D# 98
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 9 of 20
`
`US 7,225,324 B2
`
`8
`
`I
`O)
`"-
`LL
`
`NLL]
`<9
`<
`2
`
`I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`oo
`
`5
`
`NNU
`
`)
`
`O
`8
`
`E(
`
`O
`
`
`
`
`
`LOOPOVERDEPTHSLICES
`
`
`
`
`
`
`
`
`
`
`
`
`MAPTRId-
`
`
`
`
`
`MAPTRId+
`
`
`
`
`622
`
`612
`
`MAPSTEP2STARTSHOT2(82)
`
`
`
`
`
`LOOPOVERSHOTS
`
`624
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 14 of 32 PageID# 99
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 14 of 32 Page|D# 99
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 10 of 20
`
`US 7,225,324 B2
`
`Lu
`Q
`
`I
`O)
`I §
`LL
`
`NLU
`o
`<
`E
`
`11,
`_I
`E
`
`E
`
`a
`1*
`
`,
`
`}
`
`l
`
`:V |
`”7
`
`.13
`
`£151
`
`n»
`
`II
`
`__
`
`o
`g
`
`8
`LO
`
`81
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LOOPOVERDEPTHSLICES
`
`S(an)'R(an)
`MAPTRIx
`
`
`00
`5
`
`NNL
`
`o
`
`o
`8
`
`‘r
`5 A N
`E
`”3
`u
`>
`a
`
`0:
`
`m
`co
`
`U)
`I—
`
`OI(
`
`n
`n:
`
`_l
`
`m >O n
`
`. O O_
`
`
`
`CONTINUE81AND82THROUGHCOMPUTE
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 15 of 32 PageID# 100
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 15 of 32 Page|D# 100
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 11 of 20
`
`US 7,225,324 B2
`
`O
`N
`
`(O
`
`NL
`
`O
`
`‘-
`‘0
`
`$
`
`
`
`00
`
`a
`
`N
`
`$
`
`8
`no
`
`v
`
`E
`
`FE
`5
`2
`w
`‘1
`
`fl
`0 E9 A 8
`j (.0
`g
`ID
`
`a)
`E
`n.
`L1J
`D
`0:
`LIJ
`
`5
`92
`E
`N
`co
`
`N
`“J
`(D
`<
`2
`
`>~
`El
`E
`‘2‘
`
`x
`
`El
`2
`%
`E
`
`> O n
`
`. O O.
`
`J
`
`m
`
`(0'
`
`V
`0.
`UJ
`*—
`
`(D
`
`624
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`LOOPOVERSHOTS
`
`
`%
`n
`O)
`"-
`LL
`
`.
`i
`
`
`
`
`
`
`W
`':
`Hum:
`E
`fig
`1‘
`
`
`
`
`
`
`
`
`

`

`aC
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 16 of 32 PageID# 101
`P
`1
`1m.
`
`
`
`amwEN;04mm
`
`Fe
`
`nomm.8mmmB0m:>ImmNmos):
`EEK:mmEmmg0%
`
`
`
`
`
`
`
`mme4mn,wn
`
`
`
`mn,Dmm1|:mNwtmmflaw.Hg+un_mE<_2
`
`
`
`
`
`
`
`
`2.mU
`
`mm_a
`
`mP.«mm1s.mn_m_._.m
`
`mw
`
`
`D.“MwmofimIhmmoMIH“5._._<mm>OmmQz<FmW“.0ZO_._.<OOn_ON_n_
`Qm<>>z>>ODNIHm32_._.ZOOwm90%$5$9
`
`mowlEmmm
`
`mm,80%Emma$5109D3mg
`
`
`
`

`

`aC
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 17 of 32 PageID# 102
`1m
`D
`m.R7
`m2
`201
`
`w0
`
`m2,Jmym:
`
`e3%4/
`
`mmOE
`
`KamM
`
`mmmm
`
`mU
`
`_a.wPkk\.NEw..m:EN;
`
`m.m
`
`#2
`
`mm
`
`
`
`m.Mv32_
`
`
`d3mjmo0218:szb150m“.m._.3n__>_ouE.3sz
`
`._HaME;0mm:83%
`
`2mn,E7K1S.wUEatmNSnKDIM
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 18 of 32 PageID# 103
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 18 of 32 Page|D# 103
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 14 of 20
`
`US 7,225,324 B2
`
`0 I
`
`\
`
`.9
`LL
`
`N I
`
`:
`
`
`
`TIMESET1
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 19 of 32 PageID# 104
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 19 of 32 Page|D# 104
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 15 of 20
`
`US 7,225,324 B2
`
`
`
`V‘-
`”\L
`
`
`
` TIMESET2
`
`
`
`
`
`
`
`712
`
`TIMESET1
`
`
`
`(—
`
`
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 20 of 32 PageID# 105
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 20 of 32 Page|D# 105
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 16 of 20
`
`US 7,225,324 B2
`
`>.:ZEZ_-nm34<
`
`HIE?E714"
`
`
` IIEIEWIIEVIn,
`
`IIIIMEa/III—IlaIla
`
`III—"EMA!«a..
`
`IIIIV45%-3
`
`Iain/IlaIIHIWWI.
`
`.IIIHAWIfH|
`
`IIEWIIIIIWV...III?IIIIVAB1,
`
`III?!IIIIIfif...
`_IIIWIIIIVAl/IIIIaW
`
`
`IIEIV{IngaIIIIWJw/IIEWWWI
`
`
`
`
`IIISIIwil/IIMIIII,IIIIHI;
`..mi
`II-E-EI
`
`
`
`
`I
`
`
`
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 21 of 32 PageID# 106
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 21 of 32 Page|D# 106
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 17 of 20
`
`US 7,225,324 B2
`
`
`
`MFDQEOOMIFZ_DmmDmm34<>
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 22 of 32 PageID# 107
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 22 of 32 Page|D# 107
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 18 of 20
`
`US 7,225,324 B2
`
`:1me5,36
`
`
`
`6%0%.m..&Ola6%j\:meu:mem.5m:52%;§mxu:+__m_xm.5EEmokma
`
`
`
`
`
`m__>:._.
`
`€416
`
` :1me
`
`
`
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 23 of 32 PageID# 108
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 23 of 32 Page|D# 108
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 19 of 20
`
`US 7,225,324 B2
`
`0)
`
`.9
`LL
`
`0|O
`
`0')
`
`11+%
`:11:
`+1++
`:11:
`
`NO0
`
`')
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 24 of 32 PageID# 109
`Case 2:17-cv-00547—RAJ-RJK Document 1-3 Filed 10/18/17 Page 24 of 32 Page|D# 109
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 20 of 20
`
`US 7,225,324 B2
`
`TIMESET2r—9101
`
`% % 7F %
`
`» —>
`
`—> »
`
`»
`
`» —>
`
`94 t2I: t3 —>7‘ t4|C Fig9C
`90141::W14#14#14
`
`K,t
`
`912
`
`K»
`
`914
`
`K,
`
`916
`
`\n»
`
`918
`
`% 7'4 7% 714
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 25 of 32 PageID# 110
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 25 of 32 Page|D# 110
`
`US 7,225,324 B2
`
`1
`MULTI-ADAPTIVE PROCESSING SYSTEMS
`AND TECHNIQUES FOR ENHANCING
`PARALLELISM AND PERFORMANCE OF
`COMPUTATIONAL FUNCTIONS
`
`CROSS REFERENCE TO RELATED PATENT
`APPLICATIONS
`
`The present invention is related to the subject matter of
`US. patent application Ser. No. 09/755,744 filed Jan. 5,
`2001 for: “Multiprocessor Computer Architecture Incorpo-
`rating a Plurality of Memory Algorithm Processors in the
`Memory Subsystem” and is further related to the subject
`matter of US. Pat. No. 6,434,687 for: “System and Method
`for Accelerating Web Site Access and Processing Utilizing a
`Computer System Incorporating Reconfigurable Processors
`Operating Under a Single Operating System Image”, all of
`which are assigned to SRC Computers,
`Inc., Colorado
`Springs, C010. and the disclosures of which are herein
`specifically incorporated in their entirety by this reference.
`
`COPYRIGHT NOTICE/PERMISSION
`
`A portion of the disclosure of this patent document may
`contain material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the United States Patent and
`Trademark Office patent file or records, but otherwise,
`reserves all copyright rights whatsoever. The following
`notice applies to the software and data and described below,
`inclusive of the drawing figures where applicable: Copy-
`right© 2000, SRC Computers, Inc.
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates, in general, to the field of
`computing systems and techniques. More particularly, the
`present invention relates to multi-adaptive processing sys-
`tems and techniques for enhancing parallelism and perfor-
`mance of computational functions.
`Currently, most large software applications achieve high
`performance operation through the use of parallel process-
`ing. This technique allows multiple processors to work
`simultaneously on the same problem to achieve a solution in
`a fraction of the time required for a single processor to
`accomplish the same result. The processors in use may be
`performing many copies of the same operation, or may be
`performing totally different operations, but in either case all
`processors are working simultaneously.
`The use of such parallel processing has led to the prolif-
`eration of both multi-processor boards and large scale clus-
`tered systems. However, as more and more performance is
`required, so is more parallelism, resulting in ever larger
`systems. Clusters exist today that have tens of thousands of
`processors and can occupy football fields of space. Systems
`of such a large physical size present many obvious down-
`sides, including, among other factors, facility requirements,
`power, heat generation and reliability.
`
`SUMMARY OF THE INVENTION
`
`However, if a processor technology could be employed
`that offers orders of magnitude more parallelism per pro-
`cessor, these systems could be reduced in size by a compa-
`rable factor. Such a processor or processing element
`is
`possible through the use of a reconfigurable processor.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`Reconfigurable processors instantiate only the functional
`units needed to solve a particular application, and as a result,
`have available space to instantiate as many functional units
`as may be required to solve the problem up to the total
`capacity of the integrated circuit chips they employ.
`At present, reconfigurable processors, such as multi-
`adaptive processor elements (MAPTM, a trademark of SRC
`Computers, Inc.) can achieve two to three orders of magni-
`tude more parallelism and performance than state-of-the-art
`microprocessors. Through the advantageous application of
`adaptive processing techniques as disclosed herein, this type
`of reconfigurable processing parallelism may be employed
`in a variety of applications resulting in significantly higher
`performance than that which can now be achieved while
`using significantly smaller and less expensive computer
`systems.
`However, in addition to these benefits, there is an addi-
`tional much less obvious one that can have even greater
`impact on certain applications and has only become avail-
`able with the advent of multi-million gate reconfigurable
`chips. Performance gains are also realized by reconfigurable
`processors due to the much tighter coupling of the parallel
`functional units within each chip than can be accomplished
`in a microprocessor based computing system.
`In a multi-processor, microprocessor-based system, each
`processor is allocated but a relatively small portion of the
`total problem called a cell. However,
`to solve the total
`problem, results of one processor are often required by many
`adjacent cells because their cells interact at the boundary and
`upwards of six or more cells, all having to interact to
`compute results, would not be uncommon. Consequently,
`intermediate results must be passed around the system in
`order to complete the computation of the total problem. This,
`of necessity, involves numerous other chips and busses that
`run at much slower speeds than the microprocessor thus
`resulting in system performance often many orders of mag-
`nitude lower than the raw computation time.
`On the other hand, in the use of an adaptive processor-
`based system, since ten to one thousand times more com-
`putations can be performed within a single chip, any bound-
`ary data that is shared between these functional units need
`never leave a single integrated circuit chip. Therefore, data
`moving around the system, and its impact on reducing
`overall system performance, can also be reduced by two or
`three orders of magnitude. This will allow both significant
`improvements in performance in certain applications as well
`as enabling certain applications to be performed in a prac-
`tical timeframe that could not previously be accomplished.
`Particularly disclosed herein is a method for data process-
`ing in a reconfigurable computing system comprising a
`plurality of functional units. The method comprises: defin-
`ing a calculation for the reconfigurable computing system;
`instantiating at least two of the functional units to perform
`the calculation; utilizing a first of the functional units to
`operate upon a subsequent data dimension of the calculation
`and substantially concurrently utilizing a second of the
`functional units to operate upon a previous data dimension
`of the calculation.
`
`Further disclosed herein is a method for data processing
`in a reconfigurable computing system comprising a plurality
`of functional units. The method comprises: defining a first
`systolic wall comprising rows of cells forming a subset of
`the plurality of functional units; computing a value at each
`of the cells in at least a first row of the first systolic wall;
`communicating the values between cells in the first row of
`the cells to produce updated values; communicating the
`updated values to a second row of the first systolic wall; and
`
`

`

`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 26 of 32 PageID# 111
`Case 2:17-cv-00547-RAJ-RJK Document 1-3 Filed 10/18/17 Page 26 of 32 Page|D# 111
`
`US 7,225,324 B2
`
`3
`substantially concurrently providing the updated values to a
`first row of a second systolic wall of rows of cells in the
`subset of the plurality of functional units.
`Also disclosed herein is a method for data processing in
`a reconfigurable processing system which includes setting
`up a systolic processing form employing a speculative
`processing strategy.
`
`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 functional block diagram of typical
`clustered inter-processor communications path in a conven-
`tional multi-processor computing system;
`FIG. 2 is a functional block diagram of an adaptive
`processor communications path illustrating the many func-
`tional units (“FU”) interconnected by reconfigurable routing
`resources within the adaptive processor chip;
`FIG. 3A is a graph of the actual performance improve-
`ment versus the number of processors utilized and illustrat-
`ing the deviation from perfect scalability of a particular
`application utilizing a conventional multi-processor com-
`puting system such as that illustrated in FIG. 1;
`FIG. 3B is a corresponding gr