USOO5841967A Ulllted States Patent [19] [11] Patent Number: 5,841,967 Sample et al. [45] Date of Patent: Nov. 24, 1998 [54] METHOD AND APPARATUS FOR DESIGN FOREIGN PATENT DOCUMENTS USING EMULATION AND 0217291 9/1986 European Pat. Off. ...... .. G06F 15/60 O453171A2 10/1991 European Pat. Off. . _ _ 58-205870 11/1983 Japan .............................. .. 395/183.09 [75] Inventors: Stephen P-SamPle>Sarat°ga;M1lFha1l 59-161839 9/1984 Japan ............... .. 395/183.09 Bershteyll, Campbell, both of Cahf- 1444084 7/1976 United Kingdom 395/183.09 _ _ _ 2182220 9/1986 United Kingdom 395/183.09 [73] Assignee: Qulckturn Design Systems, Inc-, 2180382 3/1987 United Kingdom ............ .. 395/183.09 M t ' V' C l'f. on“ m 16W’ M OTHER PUBLICATIONS [21] Appl.No.: 733,352 Hou, et al., “A High Level Synthesis Tool for Systolic _ Designs,” IEEE, 1988, pp. 665—673. [22] Flled: Oct‘ 17’ 1996 “Gate Station Reference Manual,” Mentor Graphics Corp., [51] Int. Cl? .................................................. .. G06F 11/263 1987 (excerpts); _ _ _ [52] US. Cl. ................ .. 395/183.09; 364/578; 364/2323 gus§aulj>zetlatl~b A,H1g£LIeVe1IS_YmheS1fST°°1foig‘gfiggg’ [58] Field Of Search ....................... .. 395/18309, 183.04, esgggléglj 651g“ ‘1 Oma 1°“ CO“ erence’ ’ ’ 395/18313, 500, 183.05; 364/2323, 933.8, M" ' 488, 489, 578; 371/274 (List continued on next page.) - Primary Examiner—Robert W. Beausoliel Jr. 56 R f Ct d ’ [ 1 e erences l e Assistant Examiner—Scott T. Baderman U.S. PATENT DOCUMENTS Attorney, Agent, or Firm—Lyon & Lyon LLP. 3,106,698 10/1963 Unger ............................... .. 395/183.09 [57] ABSTRACT 3,287,702 11/1966 Borck, Jr. et al. .. 395/183.09 3,287,703 11/1966 Slotnick ........................... .. 395/183.09 A method and apparatus for combining emulation and 3,473,160 10/1969 Wahlstrom ....................... .. 395/183.09 simulation of a logic design. The method and apparatus can 3,928,730 12/1975 Agaard etal 379/275 be used With a logic design that includes gate-level 4,020,469 4/1977 Manning - - - - - - - - - - - ~~ 326/40 descriptions, behavioral representations, structural 1g; JCCHILY ettall' " representations, or a combination thereof. The emulation 4,, 315,, 315 2/1982 Ko0s0s iea keo ffa . ...................................................... .... 395/140 and.slf- nulagl- ont.port}- onst are fcotflb- mgdt H- I‘) i‘ manttl?r that 4,357,678 11/1982 Davis .......... .. 364/DIG. 2 Hummus _ e “P6 F” fans emng a a e Ween 6. WO 43867403 5/1983 Hsieh et aI 364/491 portions. Simulation is performed by one‘ or more micro 474047635 9/1983 Flaker _________ __ 364/580 processors While emulation is performed in recon?gurable 4,459,694 7/1984 Ueno et a], 365/201 hardware such as ?eld programmable gate arrays. When 4,488,354 12/1984 Chan et a1. . . . . . . . . . . .. 29/830 multiple microprocessors are employed, independent por 4,503,386 3/1985 DasGupta et al- -- 371/22-3 tions of the logic design are selected to be executed on the 4,510,602 4/1985 Engdahl et a1~ -~ -~ 371/22-2 multiple synchronized microprocessors. Recon?gurable itock ct aII-I ~~~~ ~~ " 1375/6585?) hardware also performs event detecting and scheduling 47, 5277, 115 7/1985 Meehmrpoetrr ae CIa .a1 ‘ I “ 371/222 pperati~ ons to ai~ d the si~ mulati~ on, and to reduce processi- ng 4,539,564 9/1985 Smithson ......................... .. 340/825.79 lme' (List continued on next page.) 70 Claims, 11 Drawing Sheets 7 6 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ / l 54 FPGA ' | — f l 22 EVENT /56 I/ 76’ l DETECT. I / | —" EVENT I CPU ' [54 ENCODER I ' EVENT I I 0ETE0T. I ' 36 ' | / 42 58 I | | / I | OPER. I | \ DECODER I I 34 I | H l 38 | 5,841,967 Page 2 U.S. PATENT DOCUMENTS 4,949,275 8/1990 Nonaka ................................. .. 364/490 4,951,220 8/1990 Ramacher et a1. .. 364/488 4,541,071 9/1985 0hm9ri --------------------------------- -- 395/775 4,958,324 9/1990 Devin .................................... .. 365/201 4,577,276 3/1986 Dunlop 6161. ........................ .. 364/491 4,965,739 10/1990 Ng ......................................... .. 364/491 4,578,761 3/1986 G16y ............. .. .. 364/481 4,972,372 11/1990 U6n6 ..... .. .. 365/201 4,593,363 6/1986 B1116161n 6161. .. 364/491 5,003,487 3/1991 Drumm 61 61. 364/489 4,600,846 7/1986 Burrows ....... .. 326/39 5,023,775 6/1991 Poret ........ .. 395/800 4,612,618 9/1986 P1y616161. ........................... .. 364/490 5,036,473 7/1991 Butts etal- 364/488 4,613,940 9/1986 s116n16n 6161. ....................... .. 364/490 5,041,986 8/1991 Tanishita 364/489 4,621,339 11/1986 W6gn616161. .. 364/490 560466017 9/1991 Yuyama eta- 364/491 4,642,487 2/1987 (361161 .......... .. 326/41 510516938 9/1991 Hyduke ---- -- 395/500 4,656,580 4/1987 11116116661181.6161. . 395/500 510531980 10/1991 Kanalawa ~~ 364/578 4,656,592 4/1987 sp66n6nb111g 6161. ............... .. 364/490 210811602 1/1992 6110"“ ---- ~~i 364/578 4,674,089 6/1987 P61616161. ...................... .. 395/183.04 518221222 ?zz; E'AY‘“ 61”- 33761124293 / 4,675,832 6/1987 Robinson 6161. .. 395/141 1 1 / am eta 4,695,740 9/1987 (:61161 ...................................... .. 326/86 510931920 3/1992 Agrawal 6‘ a1~ 395/800 364/580 4695 950 9/1987 B16n1116161. ......................... .. 364/200 511091353 4/1992 Sample etal 476957999 9/1987 Lebizay 379/58 1 5,126,966 6/1992 Hafeman et a1. . 364/490 4’6 97 ’ 241 9 1987 L - ......".".. .". ........................... .' . 364 48' 8 511 28 1 871 7/1992 s6111n11Z .......... .. 364/490 4’700’187 “$1987 340/82/5 83 5,140,526 8/1992 M6D611n1111 6161 .. 364/488 4’7O6’216 11/1987 Cami """""""""""""" " 365,94 5,172,011 12/1992 L61111161d 6116. .. 307/2722 477137557 12/1987 (:61161 ...................................... .. 326/86 512241055 6/1993 Grundy 6‘ al- - 364/488 4722084 1/1988 M6116n ................................... .. 371/9.1 512241056 6/1993 Chem 6‘ a1~ ~~ 364/490 4,725,835 2/1988 s611161n616161. 340/825.83 512311588 7/1993 Agrawal etal- -- 364/489 4736 338 4/1988 SaXe 6161. ............................ .. 364/578 512311589 7/1993 “Oh 6‘ a1~ ~~ 364/490 4740919 4/1988 E11n61 .................................... .. 365/104 512331539 8/1993 Agrawal etal 364/489 4’744’O84 5/1988 Beck etal' " 364/578 5,253,363 10/1993 Hy1n6n . 340/825.83 4747102 5/1988 Fnn616n ................................... .. 371/23 512591006 11/1993 Price 6‘ a1~ - 375/107 4,752,887 6/1988 Knw611616 ............................. .. 364/491 512801826 1/1994 Kond" 6‘ al- -- -- 395/500 4,758,745 7/1988 E1G61n61 6161 326/16 513291470 7/1994 Sample 6‘ a1~ - ~~ 364/578 4758 985 7/1988 T111n616161. ......................... .. 365/201 513291471 7/1994 SWObOda etal- - -- 364/578 4766569 8/1988 T111n616161. .................... .. 365/185.11 513391262 8/1994 Rostokeretal- - -- 364/578 4768196 8/1988 Jou 6161. 371/22.2 513521123 10/1994 Sample 6‘ a1~ - 439/61 477777606 10/1988 F6111n161 ................................ .. 364/491 513861550 1/1995 YumiOka etal- - 395/183-9 21/23 4,782,440 11/1988 N61n1Z11 6161. ....................... .. 364/578 214251036 6/1992 Luwjtl‘lil 4,786,904 11/1988 G161161n 6161. .. 364/488 14371037 7/199 Fun“ 1 -- -- 39 /700 364/489 4,787,061 11/1988 N616161. .............................. .. 395/500 514481496 9/1995 Bunsetal 4,787,062 11/1988 N616161. .............................. .. 364/900 514481522 9/1995 Huang ------ -- 36718904 4,791,602 12/1988 RCSIliCk ........ .. .. 514521231 9/1995 BuFtsetal- -- 364/488 4,803,636 2/1989 Nlshlyama 6161. .................. .. 364/491 214551239 9/1992 D21 6‘ a1~ ~~ 362/278 478117214 3/1989 Nosenchuck et aL ~~~~~~~~~~~~~~~~ N 395500 ,47 ,830 12/199 (3 6n ..................................... .. 39 / 00 4,815,003 3/1989 P6161nn116 6161. 364/491 15/1332 gamit’le eta1~t~~i ~~~~~~~~~~~~~~~~~~ ~~é~953£gg5g§ 4,823,276 4/1989 HlWataShl .... .. 364/491 1 1 Orsmanne a- - 4827 427 5/1989 Hyduke 364/489 5,544,069 8/1996 MOhSCIl ................................. .. 364/489 478297202 5/1989 Austin ~~~~~~ “ 3O7/465 5,551,013 8/1996 Beausoleil et al. ................... .. 395/500 4,835,705 5/1989 Fujino etal' " 364/491 5,563,829 10/1996 Huang ......... .. .365/189.04 4,845,633 7/1989 Furtek _____________ __ 364/490 5,572,710 11/1996 Asano 6161. .......................... .. 395/100 478497904 7/1989 Aipperspach etal' 364/489 5,574,388 11/1996 1361111616161. .......................... .. 326/41 4849928 7/1989 11611611 .......... .. 395/500 515811738 12/1996 Dombmwskl- -- 395/500 ’ ’ 5 596 742 1/1997 Agarwal et al. ...................... .. 395/500 44’885545’ 063699 8Q11998899 WMz ?o11n1 ey 3. 7219/ 282332 5,1 604,1 888 2/1997 K16n1-s116116616116161. ......... .. 395/500 4’862’347 8/1989 Rudy __ 395560 5,612,891 3/1997 1311116 6161. ........ .. .. 364/189 478647165 9/1989 Hoberman et a‘ 340/825'84 5,633,813 5/1997 Sr1n1~vasan ............................. .. 364/578 478687419 9/1989 Austin _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ “ 3O7/44O 5,649,176 7/1997 Selv1dge et al. ...................... .. 395/551 4870 302 9/1989 F1661n6n ...... .. 340/825.83 516591716 8/1997 Selvidge 6‘ al- -- -- 395/500 4,873,459 @1989 E1 Gamal et a1 340/825_84 5,699,283 12/1997 0116161116161. ...................... .. 364/578 4,876,466 10/1989 Kondou et a1. 364/716 OTHER PUBLICATIONS 4,882,690 11/1989 ShlIlSha 6161. 364/490 419011259 2/1990 Watkms """" " 364/488 DeMicheli, et al., “Hercules—A System for High Level 4901260 2/1990 Lubachevsky ' 364/578 Synthesis,” 25th ACM/IEEE Design Automation Confer 4,908,772 3/1990 c111 ........... .. .. 364/491 ence 1988 483488 4,914,612 4/1990 136666 6161. 364/578 ’ ’pp' ' _ _ _ 479187440 21/1990 Furtek ______ __ 340/825_83 J.Babb, A.AgarWal “More Virtual Wires”, article from 4,918,594 4/1990 on1Zn116 ...... .. .. 364/578 W9bmast9r@Caglcs-mit-edu Feb- 3, 1995 4,922,432 5/1990 Kobayashi et al- -- 364/490 R.Tessier “More Virtual Pictures”, article from 4,924,429 5/1990 Kllfflshita et a1~ ~~ 364/578 [email protected] Feb. 3, 1995. 4931946 6/1990 Ravllldra et a1‘ ' " 364/490 Varghese et al., “An Ef?cient Logic Emulation Systern”, 4,935,734 6/1990 AllStlIl .......... .. 340/825.83 IEEE P b1. t. 171_174 1993 4,937,827 6/1990 1366116161. 371/23 ‘1 lea 1on1 PP'_ 1 _ ' _ _ 479427536 7/199O Watanabe et al_ 364/490 BroWn et al., “Issues in the Design of a Logic S1rnulator: 4,942,615 7/1990 Hirose __________ __ __ 364/578 Elernent Modelling for E?iciency”, IEEE Publication, pp. 4,945,503 7/1990 Takasaki ............................... .. 364/578 21—27, Feb. 1996. 5,841,967 Page 3 AgraWal, “Mixed Behavior—Logic Simulation in a Hardware Beece et al., “The IBM Engineering Veri?cation Engine,” Accelerator”, IEEE Pub., pp. 9.2.1—9.2.4, 1990. 25th ACM/IEEE Design Automation Conference, Paper “The Homogenous Computational Medium; NeW Technol 17.1, 1988, pp. 218—224. ogy For Computation”, Concurrent Logic Inc., Jan. 26, P?ster, “The YorktoWn Simulation Engine: Introduction,” 1987. 19th Design Automation conference, Paper 7.1 1982, pp. Spandorfer, “Synthesis of Logic Functions on an Array of 51—54. Integrated Circuits”, Contract Report AFCRI—6—6—298, Oct. Denneau, “The YorktoWn Simulation Engine,” 19th Design 31, 1965. Automation conference, Paper 7.2, 1982, pp. 55—59. J .Babb, R.Tessier, A.AgarWal, Virtual Wires; Overcoming Kronstadt, et al., “SoftWare Support for the YorktoWn Simu Pin Limitations in FPGA—based Logic Emulators, IEEE lation Engine,” 19th Design Automation conference, Paper Workshop on FPGAs for Custom Computing Machines ’93 7.3, 1982, pp. 60—64. (FCCM ’93), Apr. 1993. Koike, et al., “HAL: A High—Speed Logic Simulation T.Payne; Automated Partitioning of Hierarchically Speci?ed Machine,” IEEE Design & Test, Oct. 1985, pp. 61—73. Digital Systems; May 1981. Shear, “Tools help you retain the advantages of using Tham, “Parallel Processing CAD Applications”, IEEE breadboards in gate—array design,” EDN, Mar. 18, 1987, pp. Design & Test of Computer, Oct. 1987, pp. 13—17. 81—88. AgraWal, et al. “MARS: A Multiprocessor—Based Program McClure, “PLD Broadboarding of Gate Array Designs,” mable Accelerator”, IEEE Design & Test of Computers, Oct. VLSI Systems Design, Feb. 1987, pp. 36—41. 1987, pp. 28—36. Anderson, “Restructurable VLSI Program” Report No. R.Tessier,J.Babb,M.Dahl,S.Hanono and A.AgarWal, “The ESD—TR—80—192 (DARPA Contract No. Virtual Wires Emulation Syste; A Gate Ef?cient ASIC Pro F19628—80—C—0002), Mar. 31, 1980. totyping Environment”, ACM Workshop on FPGA’s (FPGA Xilinx, First Edition, “The Programmable Gate Array ’94) Feb. 94. Manning, “An Approach to Highly Integratred, Computer Design Handbook,” 1986, pp. 1—1 to 4—33. OdaWara, “Partitioning and Placement Technique for CMOS —Maintained Cellular Arrays”, IEEE Transactions on Com Gate Arays,”IEEE Transactions on Computer Aided Design, puters, vol. C—26, Jun. 1977, pp. 536—552. Manning, “Automatic Test, Con?guration, and Repair of May 1987, pp. 355—363. Cellular Arrays”, Doctoral Thesis MAC TR—151 (MIT), Jun. Beresford, “An Emulator for CMOS ASICS,” VLSI Systems 1975. Design, May 4, 1987, p. 8. M.Dahl,J.Babb,R.Tessier,S.Hanono,D.Hoki and A.AgarWal, Mentor Graphics Corp., “Gate Station User’s Manual,” “Emulation of a Sparc Microprocessor With the Massachu 1987, (excerpts). sette Institute of Technology, Virtual Wires Emulation Sys Mentor Graphics Corp., “Technology De?nition Format tem”, IEEE Workshop on FPGAs for Custom Computing Reference Manual,” 1987, (excerpts). Machines ’94 (FCCM ’94), Apr. 1994. Chen, “Fault—Tolerant Wafer Scale Architectures Using Ravenscroft, Function Language Extractor and Boolean Large Crossbar SWitch Arrays,” excerpt from Jesshope, et Generator IEEE 1986, pp. 120—123. al., Wafer Scale Integration, A.Hilger, 1986, pp. 113—124. Shoup, “Programmable Cellular Logic Arrays,” Doctoral Kung, “Why Systolic Architectures!,” Computer, Jan. 1982, Thesis (Carnegie—Mellon University; DARPA contract No. pp. 37—46. F44620—67—C—0058), Mar. 1970. Hedlund, “Wafer Scale Integration of Parrallel Processors, Shoup, “Programmable Cellular Logic,” undated, pp. 27—28. ”Doctoral Thesis (Purdue University; Office of Naval Wynn, “In—Circuit Emulation for ASIC—Based Designs” Research Contracts N00014—80—K—0816 and VLSI Systems Design, Oct. 1986, pp. 38—45. N00014—81—K—0360 1982. Minnick, “Survey of Microcellular Research,” Stanford Fiduccia, et al. “A Linear—Time Heuristic For Improving Research Institute Project 5876 (Contract AF NetWork Partitions,” IEEE Design Automation Conference, 19(628)—5828), Jul. 1966. 1982, pp. 175—181. Siegel “The Design of a Logic Simulation Accelerator”, Oct. Trickey, “Flamel: AHigh—Level HardWare Compiler,” IEEE 1985 pp. 76—86 VLSI Systems Design. Transactions on Computer—Aided Design, Mar., 1987, pp. Minnick, “A Programmable Cellular Array,” undated, pp. 259—269. 25—26. SchWeikert, “A Proper Model for the Partitioning of Elec Minnick, “Cutpoint Cellular Logic,” IEEE Transactions on trical Circuits,” Bell Telephone Laboratories, Inc. Murray Electronic Computers, Dec. 1964, pp. 685—698. Hill, N.J., pp. 57—62. Jump, et al. “Microprogrammed Arrays,” IEEE Transactions “Partitioning of PLA Logic,” IBM TDM, vol. 28, No. 6, on Computers, vol. C—21, No. 9, Sep. 1972, pp. 974—984. Nov. 1985, pp. 2332—2333. J .W.Babb, “Virtual Wires: Overcomming Pin Limitations in Goossens, et al., “A Computer—Aided Design Methodology FPGA—based Logic Emulation”, Masters Thesis, Massachu sette Institute of Technoogy, Department of Electrical Engi for Mapping DSP—Algorithms Onto Custom Multi—Proces neering and Computer Science, Nov. 1993; Also available as sor Architectures,” IEEE 1986, pp. 924—925. MIT/LCS Technical Report TR—586. Hedlund et al., “Systolic Architectures—A Wafer Scale Gentile, et al. “Design of SWitches for Self—Recon?guring Approach,” IEEE, 1984, pp. 604—610. VLSI Array Structures,” Microprocessing and Micropro Choi et al., “Fault Diagnosis of SWitches in Wafer—Scale gramming, North—Holland, 1984, pp. 99—108. Arrays,” AIEEE, 1986, pp. 292—295. Sami, et al. “Recon?gurable Architectures for VLSI Pro Runner, “SynthesiZing Ada’s Ideal Machine Mate,” VLSI cessing Arrays,” AFIPS Conference Proceedings, 1983 Systems Design, Oct., 1988, pp. 30—39. National Computer Conference, May 16—19, 1983, pp. Wagner, “The Boolean Vector Machine,” ACM SIGARCH, 565—577. 1983, pp. 59—66. 5,841,967 Page 4 Preparata, “The Cube—Connected Cycles: A Versatile Net Prathima Agrawal, “A Hardware Logic Simulation System,” work for Parallel Computation,” Communications of the Jan. 1980, pp. 19—29, IEEE Transactions on Computer ACM, May, 1981, pp. 300—309. Aided Design, vol. 9, No. 1. Clos,“A Study of Non—Blocking Switching Networks,” The MunoZ, et al., “Automatic Partitioning of Programmable Bell System Technical Journal, Mar. 1953, pp. 406—424. Logic Devices,” VLSI Systems Design, Oct. 1987, pp. Masson, “A Sampler of Circuit Switching Networks” Com 74—86. puter, Jun. 1979, pp. 32—48. Feng, “A Survey of Interconnection Networks,” Computer, “Plus Logic FPGA2020 Field Programmable Gate Array” Dec. 1981, pp. 12—27. Brochure by Plus Logic, San Jose, CA, pp. 1—13. Chapter 36, “Switching Networks and Traf?c Concepts,” SchmitZ, “Emulation of VLSI Devices using LCAs,” VLSI Reference Data for Radio Engineers, Howard W. Sams & Systems Design, May 20, 1987, pp. 54—62. Co., 1981, pp. 36—1 to 36—16. Abramovici, et al., “A Logic Simulation Machine,” 19th S.Hanono, “Inner View Hardware Debugger; A Logic Design Automation Conference, Paper 7.4, 1982, pp. 65—73. Analysis Tool for the Virtual Wires Emulation System”, Hennessy, “Partitioning Programmable Logic Arrays,” Masters Thesis, Massachusette Institute of Technoogy, undated, pp. 180—181. Department of Electrical Engineering and Computer Sci DeMicheli, et al., “Topological Partitioning of Program ence, Jan. 1995; Also available as MIT/LCS Technical mable Logic Arrays,” undated, pp. 182—183. Report. Donnell, “Crosspoint Switch:; A PLD Approach,” Digital Alfred E. Dunlop, et al., “A Procedure for Placement of Design, Jul. 1986 pp. 40—44. Standard—Cell VLSI Circuits,” 1985 IEEE, pp. 92—98. Beresford, “Hard Facts, Soft ASICS,” VLSI Systems Ching—Wei Yeh, et al., “A General Purpose Multiple Way Design, Dec. 1986, p. 8. Partitioning Algorithm,” pp. Q15400—Q15405. “ERA60100 Electrically Recon?gurable Array—ERA,” Bro Balakrishnan Krishnamurthy, “An Improved Min—Cut Algo chure by Plessey Semiconductors, Apr. 1989. rithm for Partitioning VLSI Networks,” May 1984, pp. Snyder, “Introduction to the Con?gurable, Highly Parallel 438—446, IEEE Transactions on Computers, vol. c—33, No. Computer,” Report CSD—TR—35 1, Of?ce of Navel Research 5. Contracts N00014—80—K—0816 and N00014—8—1—K—0360, Andrew B. Kahng, “Fast Hypergraph Partition,” pp. Nov. 1980. 662—666, 26th ACM/IEEE Design Automation Conference. Palesko, et al., “Logic Partitioning for MinimiZing Gate Jorn Garbers, et al., “Finding Clusters in VLSI Circuits,” Arrays,” IEEE Transactions on Computer—Aided Design of 1990 IEEE, pp. 520—523. Integrated Circuits and Systems, vol. CAD—2, No. 2, Apr. Mark R. Hartoog, “Analysis of Placement Procedures for 1983. VLSI Standard Cell Layout,” pp. 314—319, 23rd Design Chin, et al. A Dynamically Recon?gurable Interconnect Automation Conference. Chip; IEEE International Solid State Circuits conference, Yen—Chuen Wei, et al. “Towards Efficient Hierarchial 1987; pp. 276—277 & 425. Designs by Ratio Cut Partitioning,” 1989 IEEE. Geoffrey Mott, et al. “The Utility of Hardware Accelerators Yen—Chuen Wei, et al., “Ratio Cut Partitioning for Hierar in the Design Environment,” Oct. 1985, pp. 62—71, VLSI chial Designs,” pp. 1—24. Systems Design. Wolfgang Rosenstiel, “Optimizations in High Level Synthe McCarthy, “Partitioning Adapts Large State Machines to sis,” 1986, pp. 347—352, Microprocessing and Micropro PLDs,” EDN, Sep. 17, 1987, pp. 163—166. gramming. “The Programmable Gate Array Data Book”; XilinX Inc. Malik, Sharad, et al., “Combining Multi—Level Decompo 1988. sition and Topological Partitioning for PLAS,” IEEE 1987, KautZ, et al. “Cellular Interconnection Arrays,” IEEE Trans pp. 112—115. actions on Computers, vol. C—17, No. 5, May 1968, pp. Bradsma, et al. “The Hardware Simulator: A Tool for 443—451. Evaluating Computer Systems,” IEEE Transactions on KautZ et al. “Cellular Logic—in—memory Arrays,” IEEE Computers, Jan. 1977, pp. 68—72. Transactions on Computers, vol. C—18, No. 8, Aug. 1969, Horstmann, “Macro Test Circuit Generation,” IBM TDM pp. 719—727. vol. 18, No. 12, May 1976 pp. 4023—4029. M.Dahl, “An Implementation of the Virtual Wires Intercon IBM TDM, “Testing Multiple Discrete Software Compo nect Scheme”, Masters Thesis, Massachusette Institute of Technoogy, Department of Electrical Engineering and Com nents by Connecting Real and Simulated Hardware Com ponents,” vol. 30, No. 4, Sep., 1987, pp. 1844—1845. puter Science, Feb. 1994; Also available as MIT/LCS Tech nical Report. Gotaro Odawara, et al., “Partitioning and Placement Tech nique for CMOS Gate Arrays,”1987 IEEE, pp. T.J.Bauer, “The Design of an Efficient Hardware Subroutine Protocol for FPGAs”, Masters Thesis, Massachusette Insti Q—15485—Q15491. tute of Technoogy, Department of Electrical Engineering William S. Carter, et al., “A User Programmable Recon?g and Computer Science, May 1994; Also available as MIT/ urable Logic Array,” 1986 IEEE, pp. 233—235, Custom LCS Technical Report. Integrated Circuits Conference. Wirbel, “Plus Logic Rethinks PLD Approach,” newspaper R. Ayres, “Silicon Compilation a Hierarchical Use of article, not dated, one page. PL ”, Xerox Corporation, pp. 314—326. Pardner Wynn, “In—Circuit Emulation for ASIC—Based Borriello; “High—Level Synthesis: Current Status and Future Designs,”Oct. 1986, pp. 38—46, VLSI Systems Design. Directions” IEEE 1988, pp. 477—482. Nick Schmits, “Emulation of VLSI Devices Using LACs,” McFarland; “Tutorial on High—Level Synthesis” 25th ACM/ May 20, 1987, pp. 54—63, VLSI Systems Design. IEEE Design Automation Conference, 1988, pp. 330—336. 5,841,967 Page 5 J .Babb, R.Tessier, Virtual Wires; Overcoming Pin Limita R.Tessier,J.Babb,M.Dahl,S.Hanono and D.Hoki, “The Vir tions in FPGA—based Logic Emulators, Massachusette Insti tual Wires Emulation System: A Gate—Ef?cient ASIC Pro tute of Technoogy, Student Workshop on Scalable Comput totyping Environment”, MIT, Student Workshop on Scalable ing, Aug. 4, 1993. Computing Jul. 21—22 1994S. U.S. Patent Nov. 24, 1998 Sheet 1 0f 11 5,841,967 PROGRAMMABLE INTERCONNECT FPGA CONTROLLER FIG. 1 PROGRAMMABLE INTERCONNECT FIG. 2 32 U.S. Patent Nov. 24, 1998 Sheet 2 0f 11 5,841,967 FPGA : | | RI g| VARIABLE | 4 | SELECTOR | £1 | | | | ___________________J FIG. 3 FIG. 4 U.S. Patent Nov. 24, 1998 Sheet 4 0f 11 5,841,967 1ST GROUP 2ND GROUP FIG. 7 66 FIG. 8