Polymorphic computational system and method in signals intelligence analysis Number:7,386,833 from the United States Patent and Trademark Office (PTO) owispatent

Title: Polymorphic computational system and method in signals intelligence analysis

Abstract: Configuration software is used for generating hardware-level code and data that may be used with reconfigurable/polymorphic computing platforms, such as logic emulators, and which may be used for conducting signals intelligence analysis, such as encryption/decryption processing, image analysis, etc. A user may use development tools to create visual representations of desired process algorithms, data structures, and interconnections, and system may generate intermediate data from this visual representation. The Intermediate data may be used to consult a database of predefined code segments, and segments may be assembled to generate monolithic block of hardware syhthesizable (RTL, VHDL, etc.) code for implementing the user's process in hardware. Efficiencies may be accounted for to minimize circuit components or processing time. Floating point calculations may be supported by a defined data structure that is readily implemented in hardware.

Patent Number: 7,386,833 Issued on 06/10/2008 to Granny,   et al.

---

Inventors:	Granny; Nicola V. (Bloomington, IN), Brisudova; Martina M. (Bloomington, IN)
Assignee:	Mentor Graphics Corp. (Wilsonville, OR)
Appl. No.:	10/653,998
Filed:	September 4, 2003

---

Related U.S. Patent Documents

---

	Application Number	Filing Date	Patent Number	Issue Date
	60407702	Sep., 2002
	60407703	Sep., 2002

---

Current U.S. Class:	717/109
Field of Search:	717/109

---

References Cited [Referenced By]

---

U.S. Patent Documents

5036473	July 1991	Butts et al.
5109353	April 1992	Sample et al.
5596704	January 1997	Geddes et al.
5596742	January 1997	Agarwal et al.
5684970	November 1997	Asuma et al.
5751286	May 1998	Barber et al.
5854752	December 1998	Agarwal
5870308	February 1999	Dangelo et al.
5946219	August 1999	Mason et al.
6009531	December 1999	Selvidge et al.
6061511	May 2000	Marantz et al.
6223148	April 2001	Stewart et al.
6269467	July 2001	Chang et al.
6279146	August 2001	Evans et al.
6311149	October 2001	Ryan et al.
6326962	December 2001	Szabo
6421817	July 2002	Mohan et al.
6424968	July 2002	Broster et al.
6442732	August 2002	Abramovici et al.
6484304	November 2002	Ussery et al.
6584601	June 2003	Kodosky et al.
6608638	August 2003	Kodosky et al.
6611952	August 2003	Prakash et al.
6651102	November 2003	Baker et al.
6934667	August 2005	Kodosky et al.
6971066	November 2005	Schultz et al.
7085702	August 2006	Hwang et al.
7110936	September 2006	Hiew et al.
7134090	November 2006	Kodosky et al.
2002/0055834	May 2002	Andrade et al.
2002/0133788	September 2002	Waters et al.
2002/0186246	December 2002	Burnette et al.
2003/0033039	February 2003	Gutberlet et al.
2003/0038842	February 2003	Peck et al.
2003/0184580	October 2003	Kodosky et al.

Other References

International Search Report issued Mar. 12, 2004 in Application No. PCT/US03/27467. cited by other . International Search Report issued Dec. 29, 2003 in Application No. PCT/US03/27468. cited by other.

Primary Examiner: Chavis; John
Attorney, Agent or Firm: Banner & Witcoff, Ltd.

---

Parent Case Text

---

The present application claims priority, under 35 U.S.C. 119(e), to U.S. provisional application Ser. No. 60/407,703, entitled "A Device, Methodology and Development Environment for the Modeling of Physical Phenomena Within a Reconfigurable Computational Platform," filed Sep. 4, 2002, and U.S. provisional application Ser. No. 60/407,702, entitled "A Device, Methodology and Application Development for Signals Intelligence Using a Reconfigurable Computational Platform," filed Sep. 4, 2002, the disclosures of which are both hereby incorporated by reference.

---

Claims

---

We hereby claim the following inventions:

1. A signals intelligence analysis method, comprising the steps of: storing a library of iconic representations of image detection solution fragments in a memory, said solution fragments corresponding to different image components; placing a plurality of said iconic representations in a graphical user interface; connecting said iconic representations with one or more data pathways to graphically define flow of data between the solution fragments and to represent a solution, wherein said solution identifies the presence of said plurality of image components in an input image; converting said iconic representations and said one or more data pathways displayed in said graphical user interface into a behavioral representation of said solution; and using said behavioral representation to configure a reconfigurable platform to detect the presence of said plurality of image components in an input image.

2. The method of claim 1, wherein at least one of said one or more data pathways includes event trigger information.

3. The method of claim 1, wherein said step of converting further comprises the steps of preparing, based on said iconic representations and said one or more data pathways, a high-level database corresponding to said solution; and translating said database into said behavioral representation.

4. The method of claim 1, further comprising visually highlighting a detected image component in said input image.

5. The method of claim 4, further comprising sending an event trigger signal when a combination of at least two image components is detected in said input image.

6. The method of claim 5, wherein said event trigger signal is sent based on a proximity between said at least two image components.

7. The method of claim 1, further comprising: sending an output trigger signal in response to detecting said image components in an input image; and in response to said trigger signal, highlighting said detected image components in said input image and forwarding a copy of the input image to a predetermined destination.

8. The method of claim 1, further comprising: viewing said iconic representations in a graphical user interface; replacing one of said iconic representations with a new iconic representation, wherein said new representation corresponds to a solution identifying the presence of a new image component; generating a new behavioral representation using at least said new iconic representation; and using said new behavioral representation to reconfigure said platform to detect the presence of at least said new image component in an input image.

9. A signals intelligence analysis system, comprising: a reconfigurable hardware computing platform, said platform configured to execute a signals intelligence analysis solution; a front end configured to receive input in real time; a data storage medium, communicatively coupled to said front end, and configured to buffer said input, wherein said front end is configured to synchronously pass said input to said reconfigurable hardware computing platform at a frequency based on a complexity of said solution, and wherein said front end is configured to synchronously pass said input to said reconfigurable hardware at a limiting frequency of the most complex solution currently loaded into said hardware.

10. The system of claim 9, wherein said reconfigurable hardware platform is configured to execute using parallel circuitry.

11. The system of claim 9, wherein said front end is an analog front end, and includes a plurality of ports communicatively connected to a plurality of reconfigurable hardware computing platforms.

12. The system of claim 9, wherein said reconfigurable hardware computing platform includes a host computer and a gate array.

13. A signals intelligence analysis solution development system, comprising: a computer having a display; one or more memories storing computer-executable instructions that cause said computer to perform the following steps: receive a user request to display a plurality of icons related by one ore more data pathways and event triggers, said icons corresponding to instructions for detecting the presence of a plurality of image objects in an input image; generate a high-level database based on said icons, one or more pathways and event triggers; and supply said database to a behavior generator, wherein said behavior generator translates said database into behavioral code used to configure a target platform to detect the presence of said plurality of image objects in an input image, and to issue an indication based on a proximity of said detected image objects.

14. The system of claim 13, wherein said behavioral code is in Register Transfer Logic format.

15. The system of claim 13, wherein said behavioral code lacks pre-defined input/output elements to allow downstream combination with other solutions.

16. The system of claim 13, further comprising a solution mixer configured to receive a plurality of sections of behavioral code, each section corresponding to a solution, and to restructure said plurality of sections of behavioral code into a single monolithic code.

17. The system of claim 16, wherein said solution mixer creates one or more input/output elements for said solutions.

18. The system of claim 17, wherein said input/output elements include computer code for communicating with a target reconfigurable hardware computing platform.

19. The system of claim 17, wherein said input/output elements include computer code for communicating with an analog front end.

20. The system of claim 16, wherein said solution mixer creates one or more data pipelines between said solutions.

21. The system of claim 16, wherein said solution mixer adds additional code for preventing unauthorized execution.

22. The system of claim 16, further comprising a reconfigurable hardware computing platform, wherein said monolithic block of code is used to configure said reconfigurable hardware computing platform to execute a solution based on said block of code.

---

Description

---

A portion of the disclosure of this patent document contains material that 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 Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

FIELD OF THE INVENTION

The present invention relates generally to the field of reconfigurable computing platforms. The reconfigurable nature of these platforms indicates that their physical hardware need not be static, and that it may be readily reconfigured after manufacture. Such platforms are typically made up from single devices such as field-programmable gate arrays (FPGAs), collections of FPGA's assembled into a fabric of reconfigurable hardware or highly complex logic emulation systems. Some embodiments are particularly advantageous in logic emulation systems, which may be a large-scale platform with reconfigurable logic such as the V Station family of products offered by Mentor Graphics Corporation. In particular, some embodiments of the present invention relate to user interface systems and methods for simplifying configuration of these reconfigurable platforms. Other aspects relate to software design concepts for configuration of polymorphic computational systems, which broadly refers to systems employing one or more reconfigurable computing platforms or emulation systems that may treat an entire problem holistically, involving not only the reconfigurable platform, but also its related software, methods, and practices. Still further aspects relate to using reconfigurable (and/or polymorphic) computing platforms to provide an easy-to-use, dynamic development environment that may be used by even those unfamiliar with computer programming and/or FPGA or emulation system programming. Some embodiments may be used to facilitate signals intelligence analysis, such as the decryption/encryption of data, or the detection of predefined images in satellite photographs.

BACKGROUND OF THE INVENTION

The power of modern computing can hardly be overstated. Calculations that once took anywhere from hours to months to manually perform can be accomplished literally in the blink of an eye. Calculation-intensive tasks are now accomplished in a mere fraction of the time previously required, and with each passing year computing power is greater than before. These days, the power of computing is even applied to the process of making computers themselves, a self-fulfilling process that will inevitably lead to more powerful computers.

One tool that is often used in the design of integrated circuits is the logic emulation system (emulator). The emulator may be used to simulate hardware circuitry, in real time, prior to the circuit's formal manufacturing process. The circuit's design, once emulated, can be analyzed and tested to identify any design errors. Since the emulator (by design) is reconfigurable, errors in a circuit's design, once detected, may be corrected by reconfiguring the emulator. In this manner, a designer can be confident in a particular design even before a single actual component is manufactured.

Although the emulator has gained wide acceptance in certain fields (specifically electronic design automation), the full potential for this technology has not yet been reached. This is partly due to the complexity and difficulty in writing the programs and download files that are necessary for configuring an emulator--those outside of the circuit design art have, until now, simply avoided using the emulator for tasks other than hardware functional and performance verification.

The inventors of the present application have realized, however, that the emulator possesses great promise in computing power. The emulator can be configured to create dedicated hardware for executing any desired process or algorithm, and this configuration may be optimized such that the process is carried out at hardware speeds--much faster than programs written for general purpose computers. The potential uses are limitless, as emulators may be used by cryptographers, geneticists, mathematicians, image analysis experts, and in any other area where programs are executed on general purpose computers.

To a cryptographer, however, the typical emulator may as well be a ship's anchor. Writing typical computer programs or download files for an emulator takes special skill in computer programming and logic synthesis (such as knowledge of various hardware description languages such as Verilog, Verilog Hardware Description Language (VHDL) and/or Register Transfer Logic (RTL)), and may require significant amounts of time to write. For example, working exclusively in RTL and/or VHDL, a simple circuit might require a skilled semiconductor designer no less than two days to write the code, and another full day to verify its functionality. Many of us, cryptographers included, simply may not have the time or ability to do such coding. Accordingly, there is a general need for improved computing power, and if emulators (or other large scale "fabrics" of reconfigurable logic) are to be used to offer this power, there is a specific need for a simpler, user-friendly way to generate the complex code and download files necessary to program today's reconfigurable platforms.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates an example of a computing environment in which one or more embodiments of the present invention may be implemented.

FIG. 2 illustrates an example of a configuration of a logic element in a reconfigurable computing platform.

FIG. 3 depicts an example of a user interface that may be used in accordance with embodiments of the present invention to create a visual representation of a desired process.

FIG. 4a illustrates an example of an icon for an algorithm according to some embodiments of the present invention.

FIG. 4b illustrates an example of an icon that represents data according to some embodiments of the present invention.

FIG. 5 illustrates an example of how icons may be assembled and interconnected to create a desired process in some embodiments of the present invention.

FIG. 6 depicts an example of a flow diagram showing steps involved in generating computer code corresponding to the user's desired process in some embodiments of the present invention.

FIG. 7 illustrates an example of a process having a data dependency.

FIG. 8 shows a hierarchy diagram illustrating how the user's desired process may be abstracted and analogized to a theater production in some embodiments.

FIG. 9 illustrates a block diagram example of how the FIG. 8 abstractions may be implemented in the final hardware.

FIG. 10 shows a block diagram process flow used in some embodiments of the present invention, and represents a process that is similar to that shown in FIG. 6 above.

FIGS. 11a and 11b illustrate block diagrams showing communications in an example embodiment.

FIGS. 12a and 12b show block diagram examples of how some embodiments of the present invention may interface with target hardware.

FIG. 13 illustrates an example of a model for the distribution of a theater according to some embodiments of the present invention.

FIG. 14 illustrates a block diagram example of a collaborative distribution of theaters according to some embodiments of the present invention.

FIGS. 15a and 15b show examples of block diagrams of hardware and port configurations that may be used in some embodiments of the present invention.

FIG. 16 illustrates a block diagram embodiment of an Algorithm Development Environment (ADE) according to some embodiments of the present invention.

FIG. 17 illustrates a block diagram embodiment of an example of a Behavior Generator according to some embodiments of the present invention.

FIG. 18 illustrates a block diagram example of a Solution Mixer according to some embodiments of the present invention.

FIG. 19 illustrates a flow diagram of an example computational/behavioral modeling processing using one or more embodiments of the present invention.

FIG. 20 illustrates an example of a block diagram showing relationships between various elements used in some embodiments of the present invention.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

FIG. 1 illustrates a computing environment in which one or more embodiments of the present invention may be used. This environment uses a reconfigurable computing device 101, which may be an emulator, although other forms of reconfigurable computing platforms may work equally well. Emulator 101 contains an array of reconfigurable logic elements 102, each of which includes circuitry that allows the particular logic element 102 to perform predefined functions supporting or implementing a portion of the desired algorithm. The emulator 101 may also include circuitry, such as a interconnect 103, that performs interconnections between the various logic elements 102 to form a larger circuit. Other approaches to interconnections are also possible, such as on-chip wiring, circuitry, using logic elements 102 to control interconnectivity, and/or time division multiplexing of the interconnections. Some approaches to such interconnections, and other features that may be pertinent to the disclosure herein, are described in U.S. Pat. Nos. 5,036,473; 5,109,353; 5,596,742; 5,854,752; 6,009,531; 6,061,511; and 6,223,148, the disclosures of which are hereby incorporated by reference. Using reconfigurable computing platforms, one may take advantage of their massively parallel nature in order to partition a problem to be solved into manageable elements with fast and reliable communication pathways, allowing them to be solved by the hardware. Circuits and algorithms may be implemented on the platforms in a parallel fashion and executed at hardware speeds, which may be several orders of magnitude faster than traditional general-purpose computers (depending upon the nature of the application).

A user may configure the logic elements 102 and their interconnections by using computer workstation 104. Workstation 104 may include one or more processors 105, which may execute instructions from software contained in one or more computer-readable memories 106 to perform the various steps and functions described herein. Workstation 104 may also include one or more displays 107, which may be used to provide visual information to a user, as well as one or more input devices 108 to allow user input. Any form of display and input device may be used, although in some embodiments, display 107 is sensitive to a stylus input device 108. For example, display 107 may be touch-sensitive, or may electromagnetically detect the presence of an input device 108, which may be a hand-held stylus, pen, or other type of pointing device. Embodiments of the present invention may be implemented using commercially-available emulation hardware, such as the V-Station/5M, V-Station/15M and V-Station/30M emulation systems offered by Mentor Graphics Corporation, and may be used with system compilers such as the Mentor Graphics VLE 4.0.3 and VLE 4.0.4, also offered by Mentor Graphics Corporation.

FIG. 2 illustrates an example of a logic element 102, which may be referred to as a common logic block (CLB) in some embodiments. As shown in FIG. 2, a particular logic element or CLB 102 may include a number of inputs 201. In some systems, a CLB 102 may receive 32 to 64 inputs. CLB 102 may also include a reconfigurable computational element 202, which may include reconfigurable circuitry for performing a variety of predefined operations on one or more of inputs 201, and may be configured to perform one or more of these operations by downloading binary data files from host workstation 104. CLB 102 may present the output signal or signals as output 203, which in some embodiments may include 32 to 64 outputs. As will be discussed below, some embodiments of the present invention may be used to configure one or more CLB 102s to perform a complex table lookup implementing a behavioral model of a physical behavior.

Logic elements 102 may be implemented in a variety of different configurations, such as having different numbers of inputs or outputs. Similarly, while FIG. 1 depicts a single emulator 101, that emulator 101 may in turn be comprised of a plurality of smaller emulation circuit boards working in concert, and/or may be combined with other emulators in a collaborative arrangement. Other types of reconfigurable computing platforms, besides emulators, may also be used. Embodiments of the present invention may be used in any variety of platforms and configurations.

Before getting into details regarding the example embodiments, it will be helpful to understand the basics of several general steps that may be found in some embodiments of the present invention. In the first such general step, the user uses workstation 104 to access a graphical user interface (described below) to assemble a visual representation of a process using a collection of predefined graphical icons. These icons represent predefined algorithms, software functions, data structures, or the like. The user places these icons in a graphical workspace, and creates a number of interconnections between the icons to represent the transfer of information and/or control signals, thus effectively defining the flow of the desired process. In some embodiments, the user accomplishes this by simply drawing symbols on a display device using a pointing device. When the user has finished preparing the visual representation of the desired process, the system may enter the second general step. In the second step, the system may automatically analyze the various interconnected icons to construct computer code that will carry out the user's desired process. In some embodiments, this code may be a program of human-readable computer code (e.g., in the C, C++, Pascal, Delphi, ADA, Fortran, etc. computer language) that will carry out the user's process. To accomplish this, the system may store one or more databases in memory 106 containing program code segments corresponding to the various icons, as well as additional characteristic (e.g., header) information relating to the algorithms represented by the icons. The system may assemble these code segments according to their orientation in the visual representation. In further embodiments, the system may prepare a machine-readable version of the program code, such as in a Hardware Description Language (HDL) such RTL, Very large scale integration Hardware Description Language (VHDL--an industry standard tool for the description of electronic circuits in structural or behavioral frameworks) and Structural Verilog, or a downloadable binary file, that may be used to configure a reconfigurable computing device, such as emulator 101, to carry out the desired process in hardware. In preparing this machine-readable code, the system may automatically analyze the user's process to determine an efficient hardware configuration for carrying out the user's process. Through this process, a user who is relatively unfamiliar with the technical programming of a reconfigurable computing device may easily create a hardware component custom-tailored to implement the user's desired process. These general steps are discussed below in greater detail.

An Example Graphical User Interface (GUI)

FIG. 3 depicts an example user interface that may be used to create a visual representation of a desired process. This user interface may include an overall workspace 300 through which the user may graphically assemble an iconic representation of a particular process that the user wishes to implement in emulator 101 hardware circuitry. Workspace may include control features, such as menu bar 301, containing a number of control commands that the user may wish to enter. In some embodiments, the particular control features that are available are context sensitive, such that command options are only displayed and/or available for selection when they are contextually appropriate. Example functions are described further below in connection with FIG. 8.

Workspace 300 may include a Library Icon Panel 302 containing a number of library element icons 303 representing predefined algorithms that the user may use as "building blocks" to construct the desired process. Library elements may be any type of predetermined algorithm, such as a known mathematical function, a computer function, or a computer subroutine. The library element may also represent a previously-defined circuit that performs an algorithm or carries out some process.

Workspace 300 may also include a Library Space 304, which allows a user to manage the various icons 303 that are displayed in the Library Icon Panel 302. The various library element icons 303 may be organized by category and/or subject matter to simplify the process of locating a particular element. For example, icons corresponding to mathematical functions may be located together in one library, while other icons corresponding to predefined circuits may be located in another library. In the FIG. 3 example, Library Space 304 includes a pull-down menu of available libraries, and a listing of the various libraries that the user has already opened.

Workspace 300 may include an Abstraction Window 305, which may serve as the area in which the user assembles the visual representation of the desired process. The user does this by placing various icons in the Abstraction Window 305, and by defining relationships, such as data transfer and timing relationships, between the icons.

Workspace 300 may also include a Collaboration Panel 306. Collaboration may allow a number of individuals to simultaneously work on the same project using different computer terminals. In some embodiments, workspace 300 may be displayed on each of those computer terminals. One of the terminals may be given a proverbial "token," and may have control over workspace 300 while others may view the display as it is modified. Alternatively, multiple terminals may be given control over workspace 300, where the terminals simultaneously update the various displays to reflect the collaborators' changes. In some embodiments, different collaborators may work on different aspects of an overall project, and their individual computer terminal workspaces 300 may display different portions of the graphic algorithm. For example, one collaborator's workspace 300 may show an algorithm for calculating a first value, while another collaborator's workspace 300 may show a subsequent algorithm that uses the first value in a further calculation.

Collaboration Panel 306 may include an area identifying the various collaborators who are currently actively working on the workspace 300, and may also include an area identifying the various collaborators who are authorized to work on the same project.

Workspace 300 may also include an area, such as Status Messages Panel 307, in which status messages, context sensitive help, and/or other information may be provided to the user. For example, context-sensitive help messages may be dynamically displayed as the user positions a cursor or pointer over various parts of workspace 300. Such help messages may also be displayed in a pop-up window in proximity to the cursor or pointer, or the messages may be displayed across both the pop-up window and the Status Messages Panel 307. In some embodiments, the Status Messages Panel 307 may display the current status of various collaboration activities. Status Message Panel 307 may also be used to prompt the user for certain types of information.

FIGS. 4a and 4b illustrate example library element icons that may be used in various embodiments. FIG. 4a illustrates an example icon 401 for an algorithm, such as one that performs the following mathematical function:

.times..times..times. ##EQU00001##

This example mathematical function receives three integers as input (x, y and n), and produces an output that is the sum of the function (2n+1) for all integer values of n ranging from x to y. As will be discussed further below, one unique feature of certain embodiments of the invention is that it has the intrinsic capability to perform floating point operations in conformance with ANSI/IEEE Std-754 (IEEE Standard for Binary Floating-Point Arithmetic).

Icon 401 may include one or more input data handles 402 to represent the input data that is to be provided to the algorithm. Using the above example, these inputs would be the values x, y and n. For algorithms that require more than one input, a single input data handle 402 may be used to represent all inputs. In alternate embodiments, there may be multiple data input handles, and each distinct input may have its own handle. Having separate handles increases the complexity of the icon, but allows for an easy way to see each distinct input to an algorithm.

Icon 401 may also include one or more output data handles 403. Similar to input data handles 402, output data handles 403 represent the output of the algorithm. Using the above example, the output would be a single integer value representing the sum of the function (2n+1) for all integer values of n ranging from x to y. An algorithm having multiple outputs may be represented by an icon having a single output data handle 403, or alternatively may be represented by an icon having multiple output data handles 403.

Since icon 401 may represent just one algorithm that is used with other algorithms in an overall desired process, there is often a need to coordinate the timing of when the algorithm will be performed, particularly when several of the algorithms may be asynchronous in nature. Using the above example, the output of the summation function may be needed by another algorithm, and as such, that other algorithm may need to know when the summation algorithm has completed its calculations. This sequencing of algorithms may be accomplished using event trigger signals, which are signals produced by algorithms to indicate their progress. An algorithm may receive one or more input event trigger signals, and may produce one or more output event trigger signals.

These event trigger signals may be represented in icon 401 as well. Icon 401 may include one or more output event handles 404, representing the various event trigger signals that may be produced by the algorithm. Icon 401 may also include one or more input event handles 405, representing the various event trigger signals that may be accepted by the algorithm.

Icon 401 shown in FIG. 4a is merely one example of how an algorithm may be visually represented. Variations may be used in other alternate embodiments, such as the addition or omission of one or more handles discussed above, variation in the shape (e.g., circular, square, trapezoidal, three-dimensional etc.) of the icon or handle, the placement of the handles (e.g., on edges, on corners, external to the rectangle, etc.), the presence or absence of labeling on the icons, etc.

The icon 401 shown in FIG. 4a represents an algorithm, or a kind of active process. Such algorithms and processes will often act upon some type of data, and as such, other types of icons may be used. FIG. 4b shows an example of an icon 406 that represents data. The data represented by the icon 406 may be any data, database and/or data structure stored in a memory or other circuit. Since data, by itself, does not perform any steps, it has no need for input, output, or event trigger signals, and does not need the corresponding handles described above. Connections to and from the data icon 406 may simply be made to the icon itself. The same may be done for algorithm icons 401 as well, although in such alternate embodiments, there would preferably be some manner of differentiating the input data, output data, input event trigger, and/or output event trigger signals for ease of use. Such differentiation may be accomplished by, for example, varying the line width and/or color of the various lines

In addition to placing these icons in the Abstraction Window 305, a user will likely wish to identify how the various algorithms and/or data structures are interrelated for the particular desired process. The user may want to specify that the output of one algorithm is to be the input to another, or that a particular data structure is an input to yet another algorithm. The user may create these relationships by simply drawing a connection line between the various icons and their handles. A line drawn from the output data handle of one algorithm to the input data handle of a second algorithm indicates that the output of the first algorithm is the input of the second. The lines may be given different appearances based on the information they represent. For example, thick lines may be used to represent data, while thin lines may be used to represent event trigger signals. Other variations in format, such as dashed lines, line color, multiple lines, arrows, etc. may also be used to differentiate the lines.

For data structure icon 406, although no explicit handles are shown in that example, connections may still be drawn between the icon 406 and other input/output data handles to indicate when the data is the input/output of an algorithm. These connections may be referred to as data pipelines, where the input/output data may be referred to as data elements, and the input/output event triggers may be referred to as semaphores.

FIG. 5 illustrates an example of how these icons may be assembled and interconnected to create a desired process. In this example process, a circuit (a Multi-Channel Transport circuit) captures an image using a variety of light-sensitive devices and provides it to a first filter. The filter processes the image and produces a filtered image that is then supplied to a second filter. The second filter further processes the image, and provides the twice-filtered image to another circuit (another Multi-Channel Transport circuit) that finishes the process by displaying the filtered image on a monitor.

As shown in FIG. 5, the user has placed the first circuit, MCT Input 501, in the upper-left portion of the Abstraction Window 305. Since the MCT Input 501 circuit receives no external input, and receives no input event trigger, its icon does not show handles for these elements. In alternate embodiments, unused handles may nevertheless be displayed to serve as a reminder to the user of their availability, or to consolidate the types of icons that are displayed.

The MCT Input 501 icon has an output data handle that is connected to Image Data icon 502. The Image Data icon 502 is a data structure icon, and its connection to the output data handle of MCT Input 501 signifies that this data structure is the output of the MCT Input 501 circuit (e.g., the data representing the image that was captured by the MCT Input circuitry). This image data is also connected to the input data handle of the first Pass Filter algorithm 503, meaning that the Image Data 502 is provided as an input to the Pass Filter algorithm 503. Pass Filter algorithm 503 also has an input event trigger handle, which is shown connected to the output event handle of MCT Input 501. This connection may be used to ensure that the Pass Filter algorithm 503 does not begin its filtering until it receives the appropriate trigger signal from MCT Input 501 (e.g., when the MCT Input circuit 501 has captured a complete image).

Through this series of connections, the user can easily define the particular desired process. The first Pass Filter algorithm 503 may produce a filtered image that is output as Image Data 504, and may supply an output event trigger signal to a second Pass Filter algorithm 505. The second Pass Filter algorithm 505 may receive the filtered image from Image Data 504, and upon receipt of the appropriate input event trigger signal, may perform a second filtration on the image. The second Pass Filter algorithm 505 may output the twice-filtered image directly to another algorithm, MCT Output circuit 506, and may also supply it with an output event trigger signal as well. Upon receiving the appropriate trigger event signal, MCT Output circuit 506 may complete the process by displaying the twice-filtered image on a monitor.

When icons are placed in Abstraction Window 305, some embodiments of the present invention will permit users to access help information by right-clicking on the icon. Thus, for example, a user may click on the icon to quickly see the types of input data required for the algorithm represented by the icon, the types of output data produced, and whether any trigger events are produced or used by the algorithm. This help information may also provide contextual information explaining how the algorithm works and/or what the algorithm does. This help information simplifies the user's task of assembling the algorithms necessary for the desired process, and producing a logical graphical representation that can ultimately be converted to working computer code. Additionally, in some embodiments, a user may right-click on a portion of an icon, such as a handle, and obtain help specific to the particular portion or handle that was clicked. For example, a user might click on an icon's output event handle and see a message informing the user that the algorithm represented by the icon produces an output trigger signal, and may inform the user of the characteristics of this output signal (e.g., how many signals are produced, the type of signal, when they are produced, etc.).

Generating Computer Code

The example graphical user interface described above provides an easy way for a user to conceptualize and assemble a visual representation of a desired process. Once this visual representation is completed, however, the user may wish to have an executable computer program to carry out the process and/or format a reconfigurable computing platform to execute the process in hardware. The following description addresses various aspects that may be used for this process.

To help illustrate an example process of preparing such computer code, FIG. 6 depicts an example flow diagram showing steps involved in generating computer code corresponding to the user's desired process. The example process begins with an initialization step 600. The step represents the preparation necessary to support the graphical assembly of code described above.

Several databases may be created during initialization and stored in a computer-readable medium, such as memory 106. One such database, referred to herein as the Code Database 109, may store individual segments of executable program code. Each segment may, when executed, carry out the performance of a predefined algorithm, such as the summation algorithm described above. The segments of code may be written in any computer language, such as C++, and there may be multiple segments for each algorithm. For example, the Code Database 109 may store multiple versions of the summation algorithm, to allow compatibility with a wider variety of software and hardware.

The individual code segments may require a number of input/output arguments and variables. To allow for interchangeability, the code segments may be stored in Code Database 110 with generic placeholder values for these arguments and variables. As will be explained below, these placeholders may be replaced with actual values as the code segments are assembled into a final program.

Another database that may be created is the Header Database 110. The Header Database 110 may specify the header format for each code segment stored in the Code Database. The header format may provide characteristic information regarding the algorithm, such as the number and types of input/output arguments. For example, the Header Database 109 may contain the following header for a C++ code segment implementing the summation algorithm described above, showing that the algorithm receives three integer values (n, x and y) and produces a single integer output: pmc_int summation(int, int, int)

Header Database 110 provides a rapid way for the system to determine what input/output data is appropriate for each given algorithm, and may be used during the compilation process to ensure that the user properly identifies all necessary inputs/outputs. Although Header Database 110 is shown separate from Code Database 109, the header information need not be stored separately. In some embodiments, the header information may simply be stored with the code segments in the Code Database, and Header Database 110 might not even be created. This may save memory space, but may lead to slightly longer compilation times. The Header Database information may also be used by the contextual help facility.

Another initialization task that may occur is the association of the various algorithms with one or more graphical icons. These icons, such as summation icon 401, may be used to visually represent the icon in the workspace 300. In some embodiments, the icons include predefined images, such as the summation symbol (".SIGMA."), that may help the user easily identify the particular algorithm being represented. These various initialization tasks may be performed by a computer program, sometimes referred to herein as a "librarian," that manages the various databases and/or libraries available in the system.

Once the various code segments and databases are prepared, the process may then move to step 601, in which the user graphically assembles the various icons to create the desired process. The user may add icons representing the various algorithms, as well as interconnections showing the flow of input/output data and event trigger signals. As the user adds a connection between two icons in the Abstraction Window 305, the system may consult the database(s) to determine the types and numbers of input/output data required by each icon's respective algorithm, and may inform the user when the user attempts to provide incompatible data variables, such as connecting an icon's output of type "a" with another icon's input of type "b." This check may be performed by comparing the header information for the algorithms. In some situations, an algorithm's output will match precisely another algorithm's input (e.g., one algorithm outputs a single data element of type "a," and the user connects that output to an input of an algorithm that accepts a single input of type "a").

In other situations, there may be a difference in the number and/or types of output/input at either end of the connection. In such situations, the system may prompt the user to supply information regarding how the various arguments are to be distributed. Using the connection between the output data handle of Pass Filter 503 and the input data handle of Pass Filter 504, if Pass Filter 503 outputs three arguments of type "a," and Pass Filter 504 requires only two inputs of type "a," the user may be prompted to identify which of the Pass Filter 503 outputs are to be the Pass Filter 504 inputs. This identification information may be stored in the netlist. As another example, if Pass Filter 504 requires four inputs, the user may be prompted to identify which of the four inputs are provided by Pass Filter 503, and may be reminded that Pass Filter 504 requires a fourth input that has not yet been assigned. To assign this additional input, the user may simply create another connection between Pass Filter 504's input data handle and whatever source is to provide this additional input. Again, this argument information may be stored in netlist.

In some embodiments, the icons are displayed in the Abstraction Window 305 with a unique name to identify that particular instance of the algorithm. For example, the summation icon 401 may be displayed with the following legend: "summation.sub.--01." The user may choose the unique name, and the system may also automatically generate a custom name for the algorithm.

When the user has completed the process of creating the graphical representation of the desired process, the system may then move to step 602, in which the user's graphical representation is analyzed to generate a network description, or netlist, to be used in further processing. This analysis may be performed by a separate software process, referred to herein as the "analyzer." The netlist may contain information identifying the various icons that the user placed in Abstraction Window 305, an identification of the icons' corresponding algorithms and/or data structures, identification of the data and/or event trigger signal transfers that the user specified, and may also store positional data regarding the placement and arrangement of the various icons and lines.

In generating this netlist, the system (or the analyzer) may check to make sure that all of the required data arguments and/or variables are accounted for, and may prompt the user when an error or missing argument has been detected. In some embodiments, the netlist may be a high-level code database containing function prototype calls with blank (or placeholder) argument values for the necessary arguments. An example netlist used in some embodiments appears further below, in connection with the discussion of the thespian analogy.

In some embodiments, the netlist may be generated by a Netlist Builder routine that may be crafted as a compiled PROLOG program. This routine may access the libraries of information corresponding to the various icons in the graphical representation, and retrieve information to generate a netlist "node" data structure. The node data structure may include information necessary to affect an interface of the symbol into the matrix formed by the resulting netlist. This matrix definition may contain grouping, data flow and data type information that is needed for the downstream processing utilities, and may include a symbolic token ID, the number of input ports, the format of the input ports, the number of output ports, the format of the output ports, the time of execution (which may be in a predefined standard time unit, such as nanoseconds), and a pointer to a location of help information for the particular symbol. If the Netlist Builder cannot define an interface between two nodes due to mismatches in data types or parameter counts, the discrepancy may be flagged and presented to the user for resolution. Such resolution may include modification to the original algorithm design or the development of one or more new library entries.

Embodiments of the present invention may also include an Input/Output Definition File to provide information to the Netlist Builder concerning the input-output and memory requirements of the library entry. The file may be formatted as follows:

TABLE-US-00001 // ***** DeltaV_Adder.ios ************************************ // * IO specification file for the DeltaV floating point adder entry * // * Copyright (c) 2003 Mentor Graphics Corporation * // * All rights reserved. * // ********************************************************** // Identity information info_symbol "DeltaV: :adder" // library symbol string info_id "DeltaV: :1001" // library index entry info_version "1.0.1" // version number info_status "RELEASED" // release status info_date "28-Aug-2003" // date of current status info_author "Mentor Graphics Corp." // library entry author info_technology "MGVS" // target technology name // Library security information security PROTECTED // write-delete status encryption NONE // source encryption // Timing information parameter_latency 27 // execution latency 27 nS parameter_setup 2 // minimum setup time 2 nS parameter_hold 2 // minimum hold time 2 nS parameter_min_clock 20 // mimimum clock period 20 nS // Inputs and Outputs parameter_inputs 2 // it has two input ports parameter_outputs 1 // it has one output port parameter_in_width 32 // it accepts 32-bit input parameter_in_width 64 // it accepts 64-bit input parameter_out_width 32 // it outputs 32-bit data parameter_out_width 64 // it outputs 64-bit data parameter_io_format IEEE754 // uses IEEE-754 float data parameter_in_event NONE // it uses no event triggers parameter out_event NONE // it generates no eventsparameter_in_prop NONE // it uses no props. parameter_out_prop NONE // it generates no props. // Memory interface memory_discrete NONE // no external discret mem. memory_shared NONE // no external shared mem.

In some embodiments, the netlist generated by the Netlist Builder may be further optimized using another routine, called a Semantics and Structure Analyzer, which may also be crafted as a compiled PROLOG program. The Semantics and Structure Analyzer (hereafter, SSA) may accept as its input the netlist produced by the Netlist Builder (which may be just a "first pass," or initial, netlist). It may also accept a symbols library and a Semantics and Structure rules library (SSRL). The SSA is an artificial intelligence application that applies the rules found in the SSRL to the first pass netlist and determines the most efficient manner to restructure the netlist for hardware implementation. In particular, the SSA may determine which data paths in the netlist are serially dependent and which are not, and may adjust data type parameters of each netlist node such that information is properly passed among the nodes. The SSA can also ensure that the resulting netlist is compliant with the generally-accepted rules of mathematics.

In some embodiments, serially-dependent data paths may require that their related nodes be clustered together and structured in a pipelined manner for hardware efficiency and fidelity of the algorithm, and the SSA may repartition the netlist such that the serially-dependent sub-sets are isolated from those nodes with no serial dependencies. Non-serially dependent data paths may be instantiated as semi-autonomous hardware blocks that may operate in parallel with each other and with the serially dependent blocks. The ability to restructure the operational elements of the algorithm based upon data dependency ensures maximum possible performance by utilizing parallel hardware and pipelining to the greatest possible extent. The output may be a netlist with pipelined serial segments and parallel non-serial segments

The output of the SSA is a spatially-architectured netlist that embodies the original user algorithm, and may be in a language-independent format. The optimizing feature of the SSA then reviews the resulting netlist to determine if there is any redundant hardware. Based on timing estimates derived from each library elements "execution time" entry (stated in standard time elements) identical hardware instantiations that spend most of their time "waiting" are shared by inserting data multiplexors into the netlist. The result of this optimization is blocks of hardware that are never exercised and are therefore deleted from the netlist.

When the netlist is ready, it may then be passed on to a Distiller/Behavior Generator (DBG) software program in step 603. The DBG analyzes the netlist and the various algorithms identified therein, and extracts the corresponding program code segments from Code Database 109. The DBG may substitute data variable values for placeholders in the code segments (or may leave placeholders as-is, depending on implementation), and then each of these segments may then be passed to a conversion utility that converts the code segments from their current format to a format more suitable for implementing the process in hardware. For example, the PRECISION C program, of Mentor Graphics Corporation, is able to convert computer code from the C programming language to a block of Register Transfer Level (RTL) code that implements the process in digital electronic elements. Other conversion utilities, such as Los Alamos National Laboratory's "Streams-C," Coloxica's "Handle-C," Y-Explorations' "exCite," and Synopsis's "Scenic," may also be used to perform some of the conversion process. At this stage, the code prepared by the DBG program may still include one or more placeholder variables that can be addressed by the Spatial Architect discussed further below. Further details regarding features found in the PRECISION C program may be found in U.S. Pat. No. 6,611,952, entitled "Interactive Memor