Debugging and performance profiling using control-dataflow graph representations with reconfigurable hardware emulation

Share
Save

Share On Facebook Share On Twitter Share By Email
Save Item
Add to
my lists

Filing Information

  • Patent Number: US7155708
  • Application Number: US10285389
  • Filing date: 10/31/2002
  • Issue date: 12/26/2006
  • Prior Publication Data:
  • Predicted expiration date: 07/06/2023
  • Patent term adjustment: 248
Explore Your Innovation Network™ for an introduction to:

Innovation Network Your First Name:
 Last Name:
  
Already a member? Sign In
16 Claims, 37 Drawings


Abstract

An embodiment of the invention includes a method of simulating a hybrid instruction processor and reconfigurable processor implemented algorithm which utilizes a runtime selectable emulation library that emulates a reconfigurable processor and its resources, and a control-data flow emulator that emulates the reconfigurable logic for the algorithm. Another embodiment of the invention includes a method of simulating a control-dataflow graph that includes building an internal representation of the control-dataflow graph that includes one or more dataflow code blocks, and simulating the control-dataflow graph as a sequence of code block dataflow executions, where control is passed from one code block to another code block based on the output value of the code block until EXIT is reached.

References Cited

U.S. Patent Documents

Document NumberAssigneesInventorsIssue/Pub Date
US5021947* Hughes Aircraft Company Campbell et al. Jun 1991
US5230057 Fujitsu Limited Shido et al. Jul 1993
US5438646* NEC Electronics, Inc. Davidian Aug 1995
US5491640* VLSI Technology, Inc. Sharma et al. Feb 1996
US5570040 Altera Corporation Lytle et al. Oct 1996
US5737766 Hewlett Packard Company Tan Apr 1998
US5831864* Trustees of Princeton University Raghunathan et al. Nov 1998
US5854929* Interuniversitair Micro-Elektronica Centrum (IMEC vzw) Van Praet et al. Dec 1998
US5892962 Lucent Technologies Inc. Cloutier Apr 1999
US5903771 Alacron, Inc. Sgro et al. May 1999
US5978588* Sun Microsystems, Inc. Wallace Nov 1999
US6023755 Virtual Computer Corporation Casselman Feb 2000
US6052773 Massachusetts Institute of Technology DeHon et al. Apr 2000
US6076152 SRC Computers, Inc. Huppenthal et al. Jun 2000
US6192439 Hewlett-Packard Company Grunewald et al. Feb 2001
US6226776 Synetry Corporation Panchul et al. May 2001
US6233540* Interuniversitair Micro-Elektronica Centrum Schaumont et al. May 2001
US6253373* Hewlett-Packard Company Peri Jun 2001
US6286135* Hewlett-Packard Company Santhanam Sep 2001
US6324680* International Business Machines Corporation Barnfield et al. Nov 2001
US6401187* Hitachi, Ltd. Motokawa et al. Jun 2002
US6493863* Matsushita Electric Industrial Co., Ltd. Hamada et al. Dec 2002
US6505328* Magma Design Automation, Inc. Van Ginneken et al. Jan 2003
US6507947* Hewlett-Packard Company Schreiber et al. Jan 2003
US6704914* Sharp Kabushiki Kaisha Nishida et al. Mar 2004
US6782511* Cadence Design Systems, Inc. Frank et al. Aug 2004
* cited by examiner

Other Publications

Miyazaki et al.; “Code Generation By Using Integer-Controlled Dataflow Graph”; IEEE 1997; pp. 703-706.*
Callahan et al. “Adapting Software Pipelining for Reconfigurable Computing”, CASES'00, ACM, Nov. 17-19, 2000, pp. 57-64.*
Khouri et al. “High-Level Synthesis of Low-Power Control-Flow Intensive Circuits”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 18, No. 12, Dec. 1999, pp. 1715-1729.*
Randriamparany et al. “Seamless Integration of Control Flow and Data Flow in a Visual Language”, IEEE, 2001, pp. 428-434.*
Cardoso et al. “Macro-Based Hardware Compilation of JAVA Bytecodes into a Dynamic Reconfigurable Computing System”, INESC, Portugal, 1999, pp. 1-10.*
Agarwal, A., et al., “The Raw Compiler Project”, pp. 1-12, http://cag-www.lcs.mit.edu/raw, Proceedings of the Second SUIF Compiler Workshop, Aug. 21-23, 1997.
Albaharna, Osama, et al., “On the viability of FPGA-based integrated coprocessors”, ©1996 IEEE, Publ. No. 0-8186-7548-9/96, pp. 206-215.
Amerson, Rick, et al., “Teramac—Configurable Custom Computing”, ©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 al., “Programmable active memories: a performance assessment”, © 1993 Massachusetts Institute of Technology, pp. 88-102.
Bittner, Ray, et al., “Computing kernels implemented with a wormhole RTR CCM”, © 1997 IEEE, Publ. No. 0-8186-8159-4/97, pp. 98-105.
Buell, D., et al. “Splash 2: FPGAs in a Custom Computing Machine—Chapter 1—Custom Computing Machines: An Introduction”, pp. 1-11, http://www.computer.org/espress/catalog/bp07413/spls-ch1.html (originally believed published in J. of Supercomputing, vol. IX, 1995, pp. 219-230.
Casselman, Steven, “Virtual Computing and The Virtual Computer”, © 1993 IEEE, Publ. No. 0-8186-3890-7/93, pp. 43-48.
Chan, Pak, et al., “Architectural tradeoffs in field-programmable-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.
Culbertson, W. Bruce, et al., “Exploring architectures for volume visualization on the Teramac custom computer”, © 1996 IEEE, Publ. No. 0-8186-754-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 al., “Matrix A Reconfigurable Computing Device with Configurable Instruction Distribution”, Hot Chips IX, Aug. 25-26, 1997, Stanford, California, MIT Artificial Intelligence Laboratory.
Dhaussy, Philippe, et al., “Global control sysnthesis for an MIMD/FPGA machine”, © 1994 IEEE, Publ. No. 0-8186-5490-2/94, pp. 72-81.
Elliott, Duncan, et al., “Computational Ram: a memory-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.
Gokhale, M., et al., “Processing in Memory: The Terasys Massively Parallel PIM Array” © Apr. 1995, IEEE, pp. 23-31.
Gunther, Bernard, et al., “Assessing Document Relevance with Run-Time Reconfigurable Machines”, © 1996 IEEE, Publ. No. 0-8186-7548-9/96, pp. 10-17.
Hagiwara, Hiroshi, et al., “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-kl.de/papers/paper026-1.html, IEEE 1996 Conference, Austin, TX, Oct. 9-11, 1996.
Hartenstein, Reiner, et al., “A reconfigurable data-driven ALU for Xputers”, © IEEE, Publ. No. 0-8186-5490-2/94, pp. 139-146.
Hauser, John, et al.: “GARP: a MIPS processor with a reconfigurable co-processor”, © 1997 IEEE, Publ. No. 0-08186-8159-4/97, pp. 12-21.
Hayes, John, et al., “A microprocessor-based hypercube, supercomputer”, © 1986 IEEE, Publ. No. 0272-1732/86/1000-0006, pp. 6-17.
Herpel, H.-J., et al., “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 al., “Using MORRPH in an industrial machine vision system”. © 1996 IEEE, Publ. 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.
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.
Mirsky, Ethan A., “Coarse-Grain Reconfigurable Computing”, Massachusetts Institute of Technology, Jun. 1996.
Mirsky, Ethan, et al., “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 al., “A Massively Parallel Systolic Array Processor System”, © 1988 IEEE, Publ. No. CH2603-9/88/0000/0217, pp. 217-225.
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.
Schmit, Herman, “Incremental reconfiguration for pipelined applications,” © 1997 IEEE, Publ. No. 0-8186-8159-4/97, pp. 47-55.
Sitkoff, Nathan, et al., “Implementing a Genetic Algorithm on a Parallel Custom Computing Machine”, Publ. No. 0-8186-7086-X/95, pp. 180-187.
Stone, Harold, “A logic-in-memory computer”, © 1970 IEEE, IEEE Transactions on Computers, pp. 73-78, Jan. 1990.
Tangen, Uwe, et al., “A parallel hardware evolvable computer POLYP extended abstract”, © 1997 IEEE, Publ. No. 0-8186-8159/4/97, pp. 238-239.
Thornburg, Mike, et al., “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 al., “A time-multiplexed FPGA”, © 1997 IEEE, Publ. No. 0-8186-8159-4/97, pp. 22-28.
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.
Villasenor, John, et al., “Configurable computing”, © 1997 Scientific 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 B.L. Hutchings. Configurable computing: The Road Ahead. In Proceedings of the Reconfigurable Architectures Workshop (RAW'97), pp. 81-96, 1997.
Wirthlin, Michael, et al., “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. No. 0-8186-7548-9/96, pp. 126-135.
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.
“Information Brief”, PCI Bus Technology, © IBM Personal Computer Company, 1997, pp. 1-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/050502—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., Böhm, A. P. W., Najjar, W. A., “The SA-C Compiler Dataflow Description”, Colorado 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 Fingerprint 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 Computing: Technology and Applications”, University of Cincinnati and Synopsys Inc., IEEE, April 2000, pp. 39-40.
Dehon, André, “The Density Advantage of Configurable Computing”, 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, University 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, Apr. 2000. pp. 62-69.
Goldstein, Seth Copen, Schmit, Herman, Budiu, Mihai, Cadambi, Srihari, Moe, Matt and Taylor, R. Reed, “PepeRench: A Reconfigurable Architecture and Compiler”, Carnegie Mellon University, IEEE, Apr. 2000, pp. 70-76.
Muchnick, Steven S., “Advanced Compiler Design and Implementation”, Morgan Kaufmann Publishers, pp. 217.
Hammes, Jeffrey P., Dissertation “Compiling SA-C To Reconfigurable Computing Systems”, Colorado State Unversity, Department of Computer Science, Summer 2000, pp. 179.
Automatic Target Recognition, Colorado State University & USAF, http://www.cs.colostate.edu/cameron/applications.html, pp. 1-3.
Chodowiec, Pawel, Khuon, Po, Gaj, Kris, Fast Implementations of Secret-Key Block Ciphers Using Mixed Inner- and Outer-Round Pipelining, Geogre Mason University, Feb. 11-13, 2001, pp. 9.
* cited by examiner

Read Patent

Read patent

Independent Claims | See all claims (16)

  1. 1. A method of simulating a control-dataflow graph comprising: building an internal representation of the control-dataflow graph emulating reconfigurable logic for a reconfigurable processor implemented algorithm comprising a current block; sending a trigger token to the current block, wherein said trigger token initiates execution of the current block in its entirety, wherein execution of the current block progresses from the top of the current block to the bottom of the current block; providing a plurality of LOAD nodes at the top of the current block for loading the current values of an executing program's variables; feeding values from the LOAD nodes into a computational portion of the control-dataflow graph; providing a plurality of STORE nodes at the bottom of the current block for receiving the results of the computational portion of the control-dataflow graph and for storing updated values of the executing program's variables; producing an output value of the current block, wherein the output value determines subsequent block execution, wherein, except for the output value that determines subsequent block execution, the current block and each subsequent block are independent control-dataflow representations that lack any data connection between the respective control-dataflow graph representations; and thereafter terminating the current block.