Process for converting program in high-level programming language into unified executable element in hybrid computing platform
Abstract
Problem to be solved.To compile computer code written in conformity with a high-level language standard in order to generate unified executable elements including support code related to execution management on a hybrid hardware platform. Providing a method. At the compilation stage, a higher level driver translates the generated CFC representation into a hybrid control flow data flow graph representation that represents optimized pipeline logic that can be processed into hardware descriptive representations. The driver generates the netlist file needed to generate a bitstream for a reconfigurable computer. Support for combining all necessary components with each other to obtain output from the compile driver and generate a unified executable that can be run on both the instruction processor and the reconfigurable processor. give. [Selection diagram] Fig. 1

Term
3.3 yearsto projected expiry
Projected expiry 28 December 2029, counted from filing; an application has no term until it is granted.
- Priority
- Filed
- Published
- Today
- Projected expiry
22 claims: 6 independent, 16 dependent
- 1高級言語ソースコードを統一された実行可能要素に変換する方法であって、 当該高級言語ソースコードの再構成可能なハードウェア部分からオブジェクトファイルを生成するステップと、 当該オブジェクトファイルを当該統一された実行可能要素に統合するステップとを含む、方法。
- 2前記方法は、当該高級言語ソースコードを制御フローグラフ表現に変換するステップを含む、請求項1に記載の方法。
- 3前記方法は、当該制御フローグラフ表現を制御データフローグラフ表現に変換するステップを含む、請求項2に記載の方法。
- 4前記方法は、当該制御フローデータグラフを、命令プロセッサ部分および当該再構成可能なハードウェア部分に区分化するステップを含む、請求項3に記載の方法。
- 5前記方法は、当該再構成可能なハードウェア部分をハードウェア定義言語ファイルに変換するステップを含む、請求項1に記載の方法。
- 6前記方法は、当該ハードウェア定義言語ファイルを再構成可能なハードウェアビットストリームファイルに変換するステップを含む、請求項5に記載の方法。
- 7前記方法は、当該再構成可能なハードウェアビットストリームファイルを当該オブジェクトファイルに変換するステップを含む、請求項6に記載の方法。
- 8統一された実行可能要素を形成する方法であって、 高級言語ソースコードを制御フローグラフ表現に変換するステップと、 当該制御フローグラフ表現を制御データフローグラフ表現に変換するステップと、 当該制御データフローグラフを、命令プロセッサ部分および再構成可能なハードウェア部分に区分化するステップと、 当該制御データフローグラフの当該再構成可能なハードウェア部分をハードウェア定義言語部分に、および当該命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換するステップと、 当該ハードウェア定義言語部分を再構成可能なハードウェアビットストリームに変換するステップと、 当該再構成可能なハードウェアビットストリームを、命令プロセッサが読取ることのできるビデオストリームオブジェクトファイルに変換するステップと、 当該統一された実行可能要素を形成するために、当該ビットストリームオブジェクトファイルを当該命令プロセッサオブジェクトファイルに統合するステップとを含む、方法。
- 9統一された実行可能要素を形成するためのシステムであって、 制御データフローグラフデータを、再構成可能なハードウェア部分および命令プロセッサ部分に区分化するための区分化部を含む、システム。
- 10前記システムは、高級言語を制御フローグラフ表現に変換するための高級言語コンバータを含む、請求項9に記載のシステム。
- 11前記システムは、当該制御フローグラフ表現を当該制御データフローグラフデータに変換するための制御データフローグラフコンバータへの制御フローグラフを含む、請求項10に記載のシステム。
- 12前記システムは、当該制御データフローグラフデータの当該再構成可能なハードウェア部分をハードウェア定義言語ファイルに変換するためのハードウェア定義言語コンバータへの制御データフローグラフを含む、請求項9に記載のシステム。
- 13前記システムは、当該ハードウェア定義言語ファイルをビットストリームファイルに変換するためのビットストリームコンバータへのハードウェア定義言語を含む、請求項12に記載のシステム。
- 14前記システムは、当該ビットストリームファイルをビットストリームオブジェクトファイルに変換するためのオブジェクトファイルコンバータへのビットストリームを含む、請求項13に記載のシステム。
- 15前記システムは、当該ビットストリームオブジェクトファイルを当該統一された実行可能要素に統合するためのリンカを含む、請求項14に記載のシステム。
- 16前記システムはサポートハードウェアロジックモジュールを含む、請求項9に記載のシステム。
- 17前記システムはユーザハードウェアロジックモジュールを含む、請求項9に記載のシステム。
- 18前記システムはランタイムライブラリを含む、請求項9に記載のシステム。
- 19前記システムは、命令プロセッサおよび再構成可能なハードウェアを含むハイブリッドコンピュータを含む、請求項9に記載のシステム。
- 20前記再構成可能なハードウェアは、多重適応プロセッサ(MAP)を含む、請求項19に記載のシステム。
- 21ハイブリッドで再構成可能なハードウェア命令プロセッサコンピュータで実行することのできる統一された実行可能要素を形成するためのシステムであって、前記システムは、 高級言語を制御フローグラフ表現に変換するための高級言語コンバータと、 当該制御フローグラフ表現を制御データフローグラフ表現に変換するための制御データフローグラフコンバータへの制御フローグラフと、 当該制御データフローグラフ表現を、再構成可能なハードウェア部分および命令プロセッサ部分に区分化するための区分化部と、 当該制御データフローグラフ表現の当該再構成可能なハードウェア部分を、ハードウェア定義言語ファイルに変換するためのハードウェア定義言語コンバータへの制御データフローグラフと、 当該ハードウェア定義言語ファイルをビットストリームに変換するためのビットストリームコンバータへのハードウェア定義言語と、 当該ビットストリームファイルをビットストリームオブジェクトファイルに変換するためのオブジェクトファイルコンバータへのビットストリームと、 当該ビットストリームオブジェクトファイルを当該統一された実行可能要素に統合するためのリンカとを含む、システム。
- 22統一された実行可能要素の形成を引き起こすために中に実現されたコンピュータ読取可能プログラムコードを有するコンピュータ使用可能媒体を含み、当該コンピュータ読取可能プログラムコードは、 コンピュータに、高級言語ソースコードを制御フローグラフ表現に変換させるためのコンピュータ読取可能プログラムコードと、 当該コンピュータに、当該制御フローグラフを制御データフローグラフに変換させるためのコンピュータ読取可能プログラムコードと、 当該コンピュータに、当該制御データフローグラフを命令プロセッサ部分および再構成可能なハードウェア部分に区分化させるためのコンピュータ読取可能プログラムコードと、 当該コンピュータに、当該制御データフローグラフの当該再構成可能なハードウェア部分をハードウェア定義言語部分に、および当該命令プロセッサ部分を命令プロセッサオブジェクトファイルに変換させるためのコンピュータ読取可能プログラムコードと、 当該コンピュータに、当該ハードウェア定義言語部分を再構成可能なハードウェアビットストリームに変換させるためのコンピュータ読取可能プログラムコードと、 当該コンピュータに、当該再構成可能なハードウェアビットストリームを命令プロセッサが読取ることのできるビットストリームオブジェクトファイルに変換させるためのコンピュータ読取可能プログラムコードと、 当該統一された実行可能要素を形成するために、当該コンピュータに、当該ビットストリームオブジェクトファイルを当該命令プロセッサオブジェクトファイルに統合させるためのコンピュータ読取可能プログラムコードとを含む、コンピュータプログラム製品。
Independent claims22
319 paragraphs, as filed
<u style="single">Copyright notice / permission</u> Part of the disclosure of this patent document includes material subject to copyright protection. The copyright owner does not object to any reproduction of the patent document in the patent disclosure, as it appears in the US Patent and Trademark Office patent file or patent record, but retains all other copyrights. The following indications apply to the software and data described below, including drawings, if applicable. (C) 2002 SRC Computers, Inc.<u style="single">Background of the invention</u><u style="single">Field of invention</u> The present invention generally relates to adapting a high-level language program to operate in the computing environment of a hybrid reconfigurable hardware instruction processor. More specifically, the present invention relates to transforming a high-level language program into a unified executable element that can be executed on a hybrid reconfigurable hardware instruction processor computer.
<u style="single">background</u> As instruction processors continue to increase their processing power rapidly, instruction processors are often used to perform computer-intensive calculations that were once performed solely by supercomputers. However, there are computer-intensive tasks, including image processing of numerical calculations and hydrodynamic simulations, which are not yet practical, for example, to be performed on modern instruction processors.
Reconstructable computation is a technology of increasing interest in computational technology. Traditional general purpose computations feature computer code that is sequentially executed on one or more general purpose processors. Reconfigurable calculations are characterized by programming reconfigurable hardware, such as Field Programmable Gate Arrays (FPGAs), to execute logical routines.
Reconfigurable computations bring significant performance advances in computer-intensive operations. For example, reconfigurable hardware can be programmed with a logical configuration that has high concurrency and pipelined characteristics compared to traditional instruction processors. In addition, reconfigurable hardware can be programmed with custom logical configurations that are highly efficient in performing the tasks assigned by the program. In addition, dividing the processing demands of a program between the instruction processor and reconfigurable hardware can improve the overall processing power of the computer.
A hybrid computing platform has been developed that includes both general purpose processors and reconfigurable hardware. The example hybrid computing platform is the SRC-6E commercially available from SRC Computers, Inc. in Colorado Springs, Colorado, USA. This SRC-6E system architecture includes a number of general purpose instruction processors running standard operating systems such as Linux (registered trademark). Attached to a general-purpose instruction processor are specially configured Multi-Adaptive Processors (MAPs).
<p><patcit num="1"><text>Japanese Unexamined Patent Publication No. 10-320214</text></patcit><patcit num="2"><text>Japanese Unexamined Patent Publication No. 11-250112</text></patcit></p>
<p><nplcit num="1"><text>Bohm, W. et al. Mapping a Single Assignment Programming Language to Reconfigurable Systems, The Journal of Supercomputing, Springer Netherlands, February 2002, Vol.21, No.2, pp.117 ~ 130</text></nplcit></p>
<p> An important obstacle for users who may wish to use reconfigurable computations is the difficulty of programming reconfigurable hardware. Traditional methods of programming reconfigurable hardware include the use of hardware description language (HDL), a lower language that requires explicit processing of digital circuit expertise and timing. Was done. Therefore, the process of accepting a program written in a high-level language and converting it into code that can be executed on a hybrid reconfigurable hardware instruction processor computer with minimal modifications to the original program. is required.</p>
<p><u style="single">Overview</u> An embodiment of the present invention includes a method of converting high-level language software code into a unified executable element, the above method comprising generating an object file from a reconfigurable hardware portion of the high-level language source code. Includes steps to integrate object files into unified executable elements.</p><p> Another embodiment of the present invention includes a method of forming a unified feasible element, wherein the method includes a step of converting a high-level language program into a control flow graph representation and a control flow graph representation of the control data flow graph representation. The step of converting to, the step of dividing the control data flow graph into the instruction processor part and the reconfigurable hardware part, the reconfigurable hardware part of the control data flow graph into the hardware definition language part, and The instruction processor can read the steps of converting the instruction processor part into an instruction processor object file, the step of converting the hardware definition language part into a reconfigurable hardware bitstream, and the reconfigurable hardware bitstream. It includes the steps of converting to a bitstream object file and integrating the bitstream object file with an instruction processor object file to form a unified actionable element.</p><p> Another embodiment of the invention is a system for forming a unified executable element that includes a partition for partitioning a control data flow graph representation into a reconfigurable hardware portion and an instruction processor portion. including.</p><p> Another embodiment of the present invention includes a system for forming a unified executable element that can be executed by a hybrid reconfigurable hardware instruction processor computer, in which the system is a control flow graph representation of a high-level language. A high-level language converter for converting to a control flow graph, a control flow graph to control data flow graph converter for converting a control flow graph representation to a control data flow graph representation, and a hardware that can reconfigure the control data flow graph representation. A division unit for dividing into a ware part and an instruction processor part, and a control computer. Control to convert the reconfigurable hardware part of the data flow graph representation to a hardware definition language file A data flow graph to hardware definition language converter and hardware to convert a hardware definition language file to a bitstream file A ware definition language to bitstream converter, a bitstream to object file converter to convert a bitstream file to a bitstream object file, and a bitstream object file to integrate into a unified executable element. Including with Linker.</p><p> Another embodiment of the invention includes a computer program product, said computer program product comprising a computer-enabled medium having computer-readable program code incorporated to form a unified actionable element. Computer-readable program code is a computer-readable program code that allows a computer to convert a high-level language source code into a control flow graph representation, and a computer-readable program that allows a computer to convert a control flow graph representation into a control data flow graph representation. Code, computer-readable program code to divide the control data flow graph into an instruction processor part and a reconfigurable hardware part to the computer, hardware definition of the reconfigurable hardware part of the control data flow graph to the computer Computer-readable program code for converting the language part and the instruction processor part into an instruction processor object file, computer-readable program code for the computer to convert the hardware-defined language part into a reconfigurable hardware bitstream. , Computer-readable program code for converting a computer-reconfigurable bitstream into a bitstream object file that can be read by the instruction processor, and a computer that integrates the bitstream object file with the instruction processor object file to unify Includes computer-readable program code for forming the made executable elements.</p><p> Further new features will be described in part in the description that follows, and will be partly apparent to those skilled in the art by reviewing the following specification, or will be known by practicing the present invention. The features and advantages of the present invention may be realized and achieved by the means, combinations and methods specifically noted in the claims.</p>
<figref num="1">FIG. 5 illustrates a system for converting a high-level language (HLL) program into a unified executable element, according to an embodiment of the present invention.</figref><figref num="2">FIG. 5 is a flow diagram for converting an HLL program into a unified executable element according to an embodiment of the present invention.</figref><figref num="3">It is a flow diagram for converting a high-level language (HLL) source code into a hardware logic executable element according to the Example of this invention.</figref><figref num="4">FIG. 5 is a flow diagram for converting an instruction processor executable element into a hardware logic executable element according to an embodiment of the present invention.</figref><figref num="5">It is a figure for separating the HLL source according to the Example of this invention.</figref><figref num="6">It is a flow diagram for converting an HLL source code into a control flow graph representation according to the Example of this invention.</figref><figref num="7">It is a figure which shows a part of the control flow graph according to the Example of this invention.</figref><figref num="8">It is a figure which shows the data flow graph according to the Example of this invention.</figref><figref num="9">It is a figure which shows the example of the hybrid CFG-DFG segment according to the Example of this invention.</figref><figref num="10">It is a figure which shows the example of the conditional data flow graph according to the Example of this invention.</figref><figref num="11">It is a figure which shows the example of the parallel code block according to the Example of this invention.</figref><figref num="12">It is a flow diagram for converting a CFG representation into a hybrid control data flow graph according to the Example of this invention.</figref><figref num="13">It is a figure which shows another example of the data flow graph according to the Example of this invention.</figref><figref num="14">It is a figure which shows the example of the memory of a parameter vs. a local variable according to the Example of this invention.</figref><figref num="15">It is a figure which shows the example of the interpretation by the chart of an opcode sequence.</figref><figref num="16">It is a figure which shows the example of the DFG fragment constructed from the operation code sequence of FIG. 10 according to the Example of this invention.</figref><figref num="17">It is a figure which shows the example of the DFG fragment after removing the scalar parameter indirect according to the Example of this invention.</figref><figref num="18">It is a figure which shows the example of the DFG block code according to the Example of this invention.</figref><figref num="19">It is a figure which shows the example of three array references used in the Example of this invention.</figref><figref num="20">It is a figure which shows the operation code structure of the subroutine call and the corresponding block code according to the Example of this invention.</figref><figref num="21">It is a figure which shows the opcode structure of a function call and the corresponding block code according to the Example of this invention.</figref><figref num="22">It is a figure which shows the operation code structure of a branch and a corresponding code block according to the Example of this invention.</figref><figref num="23">FIG. 5 is a diagram showing a portion of a CFG representation having a basic block and logic added to a central block to handle input and output flow control according to an embodiment of the present invention.</figref><figref num="24">It is a figure which shows the basic block which has a selector input connected to the OR node of the block according to the Example of this invention.</figref><figref num="25A">It is a figure which shows the example of the subtree of the opcode used in the Example of this invention.</figref><figref num="25B">It is a figure which shows still another example of the opcode subtree used in the Example of this invention.</figref><figref num="26">It is a figure which shows the example DFG for the loop used in the Example of this invention.</figref><figref num="26A">It is a figure which shows the example DFG for the loop used in the Example of this invention.</figref><figref num="26B">It is a figure which shows the example DFG for the loop used in the Example of this invention.</figref><figref num="27">It is a figure which shows the example of the pipelined DFG without delay according to the Example of this invention.</figref><figref num="28">It is a figure which shows a part of the code block after merging according to the Example of this invention.</figref><figref num="29">It is a flow diagram for dividing a CFG-DFG representation into a reconfigurable hardware part and an instruction processor part according to the Example of this invention.</figref><figref num="30">FIG. 5 is a flow diagram for forming a unified executable element according to an embodiment of the present invention.</figref><figref num="31">It is a figure which shows the example MAP emulator system according to the Example of this invention.</figref><figref num="32">It is a figure which shows another example MAP emulator system according to the Example of this invention.</figref><figref num="33">It is a flow diagram of the data flow simulator according to the Example of this invention.</figref><figref num="34">It is a figure which shows the example of the token flow in the data flow simulation according to the Example of this invention.</figref>
<u style="single">Detailed explanation</u><u style="single">System overview</u> Here, with reference to FIG. 1, an example of a hybrid reconfigurable hardware instruction processor system 100 for converting a program written in a high-level programming language into a unified executable element is shown. In one embodiment, the reconfigurable hardware portion of System 100 may include a Multiple Adaptive Processor (MAP), which integrates the reconfigurable circuit of the Field Programmable Gate Array (FPGA) with logic. , Can control the FPGA and communicate with the instruction processor portion of the system 100. In another embodiment, electronic communication between reconfigurable hardware and the instruction processor in System 100 may include the use of a switch to link a switch / network adapter port and / or multiple MAPs to the instruction processor.
Examples of System 100 include, among other things, MAPs, instruction processors, converters 104 from high level language (HLL) files to unified executable elements, supported hardware logic modules 118, user hardware logic modules 120 and Includes a MAP programming environment that includes the runtime library 122. In the embodiment of system 100, the HLL source code file 102 is input to the converter 104. The HLL source code file 102 may be written, in particular, in traditional high-level languages such as C, C ++, Fortran, COBOL, BASIC, PASCAL and Java®.
The HLL file 102 is input to the converter 104, which can be converted into a unified executable element 124 by the components of the converter 104. Examples of converter 104 particularly include HLL converter 106, CFG to CFG-DFG converter 108, divider 110, CFG-DFG to HDL converter 112, HDL to bitstream converter 114 and linker 116. Can include.
The converter 104 may include an HLL converter 106 that converts a high-level language file into a control flow graph (CFG) representation. In one embodiment, the HLL converter 106 is a software module containing logical instructions for initiating conventional compilation by reading high-level language source code, parsing the source code, and converting the code into internal representations and symbol tables. including. The HLL converter 106 may include logical instructions for syntactic and semantic checking of the source code and for generating appropriate diagnostic messages in response to errors in the source code.
In addition, the HLL converter 106 may include logical instructions for optimizing the internal representation of the source code. In particular, the HLL converter 106 outputs a CFG representation. The CFG representation is further processed by the instruction processor compiler to yield an instruction processor sequence, or from CFG to CFG-DFG for data flow analysis and logic generation for reconfigurable processors (eg MAP). May be passed to another software module such as Converter 108.
In one embodiment, the CFG to CFG-DFG converter 108 is a software module that receives the CFG representation generated by the HLL converter 106 and contains logical instructions for converting the CFG representation to a control data flow graph representation. There may be. Control data flow graphs can be used throughout the rest of the compiler stage. The CFG to CFG-DFG converter 108 can optimize the degree of parallelism in the compiled code. The function of the CFG to CFG-DFG converter 108 is, in particular, the generation of a control data flow graph from the CFG representation passed by the HLL converter 106 and the basic block, which can be used by the remaining components of the converter 104. Conversion to code block in data flow graph, conversion of input / output scalar, change of input / output array In addition, the processing of scalar references in the code block, the processing of array references in the code block, the configuration of loop control, the processing of pointer references, the processing of calls to the instruction processor code, and the system calls to the instruction processor OS. Processing, extension of built-in function calls, extension of external function calls, loop optimization, multithread optimization, data path and logical device data width optimization, and unnecessary structures. It may include structural optimization, including removal.
The divider 110 may be a software module that includes logic instructions for sizing the logic to fit the available resources of the hybrid computing system. The segmentation unit 110 may receive the control data flow graph generated by the CFG to CFG-DFG converter 108 as input and may map the control data flow graph to available resources to optimize performance.
In an exemplary embodiment, the divider 110 uses the following information: the size of the logic processor from the hardware logic module information file, the chip size from the resource file, the interface size and speed from the resource file, and the resource file. Receives input from the programmer for data storage performance and size, pragmas or directives, profiling information from the Control Data Flow Graph (CFG-DFG) emulator, and profiling information from the instruction processor profiling tool. obtain.
In an exemplary embodiment, the segmentation unit 110 may include logical instructions for annotating the CFG-DFG with the above information and estimating performance parameters of the subgraph based on execution in the instruction processor and MAP. The divider 110 may further include logic instructions for evaluating logic sizing and allocating logic based on, for example, integrated circuit and MAP resources.
The partitioning unit 110 may include logical instructions for defining interface logic on the MAP and assigning the MAP proxy code to the instruction processor. The MAP proxy provides the goal of instruction processor code that transitions to a controlled thread on the MAP. The MAP proxy receives the call and begins passing any parameters required by the MAP. The MAP proxy can also receive requests from the MAP.
The output of the divider 110 may include a CFG-DFG that can be realized as logic in the MAP and a CFG-DFG that can be realized by an instruction processor.
The CFG-DFG to HDL converter 112 is a software module that contains logical instructions for converting CFG-DFG into hardware definitions of physical logic instantiated by a reconfigurable processor in MAP. May be good. The CFG-DFG to HDL converter 112 receives the CFG-DFG file from the CFG to CFG-DFG converter 108 as input and converts the CFG-DFG file to an internal representation. Reads the hardware logic module information file to provide node input, output and latency information. Nodes and routes between nodes are checked for their compatibility and bit width consistency.
Some nodes are inlined rather than instantiated. Inlining refers to generating a hardware definition rather than referencing the definition as an instantiated logical module. All nodes in CFG-DFG are checked for proper node dependency and consistent data flow. Each node is then instantiated and all wiring connecting the nodes is declared. Hardware definition An output file containing the words is generated. The output file may be written in a hardware definition language such as Verilog or EDIF.
The HDL to bitstream converter 114 may include traditional synthesis tools for compiling from Verilog to EDIF, and a Place and Route tool for converting EDIF files into MAP-loadable bitstreams. Can be used to process the output of converter 112 from CFG-DFG to HDL.
The linker 116 is a software module that contains logical instructions for accepting object files, including bitstream object files, instruction processor files and other object files, and integrating them to form a unified executable element 124. You may.
In another embodiment, system 100 may include a conventional instruction processor compiler (not shown) that can be used to compile a portion of a high-level language that is not translated into logic to be executed by the MAP.
System 100 may also include a bitstream component (configurator) (not shown) that may contain a software module containing logical instructions to generate a unified executable file. The bitstream file is encapsulated as a compiled C routine, which can be incorporated into an executable file using a compiler and standard linker. Executable elements that include application instruction processor instructions, MAP logical bitstreams, and any required library code may be referred to as unified executable elements.
System 100 may include a binary translator (not shown) that is a comparison tool to converter 104. The converter 104 can accept high-level language source code as input and generate CFG representations and unified executable elements. The binary translator can accept an executable file, convert it to a CFG representation, and give it to the secondary input to converter 104 to avoid the need for source code.
System 100 includes modules 118 and 120 as well as library 122, which may provide a run-time environment for the conversion process from HLL to unified executable elements. The runtime environment may include library routines contained in the instruction processor portion of each application. These library routines provide support services for MAP. This includes resource allocation and deallocation, communication between the instruction processor and MAP, debugging and performance analysis. At least three separate environments: 1) run on MAP hardware, 2) run on emulated MAP and dataflow graph emulation, 3) run on emulated MAP and simulated user logic Can be supported by run-time routines.
<u style="single">Overview of the method</u> Here, with reference to FIG. 2, a method 200 of converting a high-level language (HLL) into a unified executable element is shown according to an embodiment of the present invention. Method 200 can be initiated by converting the HLL program into a control flow graph (CFG) in step 202. In one embodiment, the conversion 202 of the HLL program to the specified CFG format can be done by a conventional HLL compiler. Conversion of an HLL program to CFG 202 may use a compiler to parse the HLL program into a CFG representation and generate an instruction code that can be executed by an instruction processor. The instruction code is then written to an object file, which is the linker loader that solves the address. Both can be linked.
The programming language used in the HLL program may be a conventional high-level language such as C, C ++, Fortran, COBOL, BASIC, Java (registered trademark), PASCAL, etc. The HLL program can include various data entities including scalars, arrays and user-specified aggregates, especially their associated operators. HLL programs can include function calls, subroutines, loops and conditions, especially operations.
In an embodiment of the invention, the next step in method 200 may be the conversion of the CFG representation to a hybrid control data flow graph representation (CFG-DFG) in step 204. Simply put, this transformation 204 separates the CFG representation into the basic blocks of its components, adds load and storage data to the top and bottom of the basic block, and separates the basic block into a CFG-DFG representation. It may include a step of converting to a code block. A more detailed description of conversion 204 is given below.
The next step in Method 200 may be the partitioning of the CFG-DFG representation into a reconfigurable hardware part and an instruction processor part in step 206. In one embodiment, the CFG-DFG representation may be input to a partitioning program, which may scan the data and split it into configurable hardware parts and instruction processor parts. In another embodiment, the partitioning program may receive instructions from a user-inserted partitioning syntax, such as a C pragma or compiler directive, which is the hardware that the CFG-DFG code can reconfigure. It guides whether it is divided into a hardware part and an instruction processor part. For example, the pragma may instruct the partitioning program to put a particular loop operation into the instruction processor portion of the partitioned CFG-DFG representation. The pragma may be included in the source code of the original HLL program or may be given directly to the segmentation program.
At this point in this embodiment of Method 200, the partitioned CFG-DFG representation from partitioning step 206 can be split into separate process steps. The instruction processor portion from division step 106 may be converted to the instruction processor object file 208. In one embodiment, the instruction processor portion of the hybrid CFG-DFG representation can be converted back to the CFG representation and then converted into an instruction code that can be executed by the instruction processor. The opcode can then be written to an object file that can be linked with the linker loader that solves the address. In another embodiment, the instruction processor portion of the hybrid CFG-DFG representation may be considered identical to part of the original CFG representation, and this portion of the original CFG representation may be converted to an object file. ..
Focusing on the reconfigurable hardware part of the CFG-DFG representation from partitioning step 206, this part can be converted from the CFG-DFG representation to HDL (hardware definition language) (210). Hardware definition languages can include traditional HDL, especially Verilog and EDIF.
The hardware definition language file may then be converted to a bitstream data file (212), which can be loaded into individual reconfigurable circuits in reconfigurable hardware. For example, the bitstream data file may be loaded into a field programmable gate array (FPGA) in a multi-adaptive processor (MAP) used in a reconfigurable hardware computer of the hybrid instruction processor of the invention. In an embodiment, a "location and root" program may be used to perform the HDL to bitstream conversion 212. Based on the HDL file, the "location and root" program is instantiated and reconfigurable It may be interconnected with a hardware logic module of capable hardware. The "location and root" program dictates where the modules can physically go and how they are coupled together in reconfigurable hardware.
In the embodiment of Method 200, after the bitstream files have been generated, they can be converted to bitstream object files in step 214. Bitstream to object file conversion 214 converts bitstream data to high-level language source code (for example, placing the bitstream in a C structure) and converts the high-level language file into an object file that can be read by the instruction processor. May include steps to do.
In the embodiment of method 200, after converting the bitstream file to the bitstream object file in step 214 and the instruction processor portion of the CFG-DFG representation to the instruction processor object file in step 208, the object file is in step 216. Can be collected at. Additional object files can be collected along with bitstream object files and instruction processor object files. For example, additional object files may come from the previous iteration of Method 200. Additional object files may be obtained from previous instruction processor compilations and from object libraries.
Once the bitstream object files, microprocessor object instruction processor files, and any additional object files are collected, they are linked together (218) to form a unified executable element 220. In an embodiment, the linking of object file 218 may be done by a linker program. The unified executable element 220 is readable by the instruction processor, which executes the unified executable element 220 and the hybrid reconfigurable hardware microprocessor computer executes the HLL program. Can be configured to.
Here, with reference to FIG. 3, a flow diagram of a method of converting a high-level language source code into a hardware logic executable element according to an embodiment of the present invention is shown. This method can be initiated by the analysis of high-level language (HLL) source code 302 processed in partitioning step 304. If a partition is found in HLL source code 302, this code can be split in steps 306 and 308 and converted into a control flow graph (CFG) representation.
In one embodiment, after the segmented portion of the HLL source code 302 has been converted to a CFG representation in step 308, this CFG representation is used to refer to MAP Proxy 322 (see MAP Proxy Details in the High-Level Language Converter section). ) Can be generated or converted to a CFG-DFG representation for hardware logic in step 316. For the part of the CFG representation that results in the generation of the MAP proxy 322, this part is converted to binary instruction processor code in step 324 and then linked with all other binary files in step 326 to execute the hardware logic. Can be part of element 328. Regarding the part of the CFG representation that was converted to the CFG-DFG representation for hardware logic in step 316, the CFG-DFG representation is the HDL (hardware definition) such as the Verilog code in step 318. It can be converted to logic) code, then converted to hardware logic binaries in step 320, linked with all other binary files in step 326, and become part of hardware executable element 328. The remaining HLL source code 302, which is not part of the partitioned source code, can be converted to a CFG representation in step 306. The CFG representation is then converted to the instruction processor binary code in step 324 and then linked with all other binary files (326), c. It can be part of the software logic executable element 328 (ie, the unified executable element).
For the unpartitioned HLL source code 302, the entire code may be converted to a CFG representation in step 310, or may be divided into reconfigurable hardware and instruction processor parts in step 312. The instruction processor portion can be converted to instruction processor binary code in step 324 and finally formed into hardware logic executable element 328. The reconfigurable hardware part can be partitioned, which will generate a MAP proxy in step 322, while this same part will be converted to a CFG-DFG representation. This segmented portion can eventually become part of the hardware logic executable element 328.
Here, referring to FIG. 4, a flow chart of the calculation method 400 of the binary translator according to the embodiment of the present invention is shown. In one embodiment, the instruction processor executable element 402 may be edited in step 404 so that it becomes part of the hardware logic executable element 426. In another embodiment, the instruction processor executable element 402 may be translated into a CFG representation in step 406.
After the instruction processor executable element 402 is converted to the CFG representation in step 406 and to the CFG-DFG representation, it is then segmented into the reconfigurable hardware and instruction processor parts in step 408. obtain. The instruction processor portion and any remaining portion 420 of the CFG representation can then be converted to instruction processor binary code in step 422. The instruction processor binary code can then be linked with all other binary files in step 424 to become part of the hardware logic executable element 426.
The reconfigurable hardware part can be partitioned, which will generate a MAP proxy in step 416, while this same part will be translated into hardware definition language (HDL) code (eg Verilog) in step 414. This can then be converted to a hardware logic binary in step 418. The hardware logic binary can be linked with all other binary files in step 424 and become part of the hardware logic executable element 426.
The MAP proxy generated by the compartmentalized part is converted to instruction processor binary code in step 422 and then linked with all other binary files in step 424 to be part of the hardware logic executable element 426. Can be.
Figures 2 and 3 show the steps of the method that can be used in the step of transforming an HLL program into a unified executable or hardware logic executable according to an embodiment of the present invention. Figure 4 shows the steps of a method that can be used in the process of converting an instruction processor executable file into a hardware logic executable element. It should be recognized that additional steps and alternative sequences of the indicated steps are considered in the additional embodiments of the present invention.
<u style="single">Map execution selector</u> An exemplary embodiment provides a method for identifying areas of source code written in a high-level language that can be isolated and targeted for hardware logic, while other parts of the code are traditional. Can be compiled to run on a processor. The example method uses a special bracket syntax that indicates which area of the code should be executed in the hardware logic, and the scoping information for the variables contained within the bracket area. Is provided. This information can be used to construct communication and data movement routines that facilitate the execution of areas identified for execution by hardware logic without further intervention by the user.
Many high-level programming languages include language constructs that can be used to specify areas of user code that can be compiled and executed by hardware logic rather than general-purpose processors. For example, in the Fortran language, the syntax "! Dir $" may be used, and in C, the syntax "#pragma" may be used. Using these constructs, the syntax for bracketing a user code copies either the start or stop identifier, the scoping rules for the variables contained within the bracket code, and the privately calculated data. Includes additional syntax for.
For example, consider the following small Fortran procedure.
<maths num="1"><img file="JP2010146577A_D0001.tif" /></maths>
This code segment first declares three arrays (a, b, c), which are used to hold the data used in the computation. This array is declared in a common block, which means that the allocation of these memories is done in the memory of the instruction processor and not in the local stack space associated with this procedure. There is an external call to the procedure, which can be assumed to initialize the data in the array. After this initialization, the call is a do-loop containing the computational part of this procedure.
The portion of the code identified to be executed by the hardware logic is determined to be the loop body enclosed by the do-loop construct. Fortran code may be modified to resemble the following, using a syntax recognized by the compilation system that generates the hardware logic.
<maths num="2"><img file="JP2010146577A_D0002.tif" /></maths>
Here, the do-loop is bracketed with a pair of directives that give the information that the compilation system needs. The compilation system processes this information to build both procedures that run on a general-purpose processor and subprograms that run on hardware logic.
The conversion of this single Fortran procedure to a separately compilable procedure can involve multiple compilation stages. In one step, the compilation system processes the individual source files contained in the program and discards the more reconfigurable hardware logic compilation source files that have no syntax to indicate that hardware compilation is desired. When the compilation system encounters a syntax that indicates that reconfigurable hardware compilation is desired, the compilation system will compile this source file on both the instruction processor and the bracket portion of the hardware logic. Start building the required infrastructure. In addition to generating the source files needed for the instruction processor compilation phase and the hardware logic compilation phase, the mechanisms used to allocate, reserve, and free hardware logic resources are generated.
The bracket syntax may include scoping information for all variables used within the bracket area. This scoping information can be used by the compilation system to build a corrected data transfer statement and ensure that the integrity of the program is exactly the same as if it were executed entirely on the instruction processor. Scorping data and variables as "global" indicate to the compilation system that this data is persistent across call boundaries between the instruction processor and the hardware logic. The mechanism that moves the data to and retrieves the data from the hardware logic can be built into new subprograms generated by the compilation system. Global data is in the same state It can be processed in a similar manner to protect the integrity of the data.
Scorping data and variables labeled "dedicated" indicate to the compilation system that these variables are just local to the hardware logic in scope, and therefore the resulting values are the execution points of the hardware logic. It doesn't have to last beyond. A variant of this syntax is the additional syntax that allows the dedicated data to be "copied" to a local variable in the instruction processor version of the source file.
The compilation system uses this data scoping information to generate two separate source files, each showing a portion of the original source file containing the bracket syntax. One of the new source files is compiled and executed on the instruction processor system. Generate hardware logic using other source files. This process is shown in Figure 5.
<u style="single">High-level language converter</u> The first called component of the compilation system initiates the traditional compilation phase similar to compiling on any instruction processor system. This component takes any programming language code as input and extracts a token that can be next parsed from the source file. Semantic analysis may also be performed during the parsing step to generate an internal representation of the code and symbol table after this step. A semantic error test is performed and an appropriate diagnostic message is issued.
The internal representation of the source code currently generated at this compilation stage is similar to the control flow block of code. The next step is to extend this control flow block to the internal language that the optimizer handles. During this expansion phase, each control flow block can be expanded into units called either basic blocks or extended basic blocks. The flow graph may be a directed graph of the basic blocks of a function, which shows the control flow of the function. Each node in the graph corresponds to a basic block. This flow graph can be updated at compile time if optimizations are made. The major global optimizations performed during this step may include constant code movements, namely inductive variable analysis, global register allocation. Other optimizations may include code block merging and peephole optimization resulting in an optimized control flow code block.
After optimization of global register allocation, routine call parameters are written to an intermediate file, which can be used as input to the next compilation stage. Call parameters are written with that data type, followed by routines and user symbols associated with that data type. After writing out the symbols used in the routine, the next part of the file contains a traversal of the terminal code block, which shows the type of basic block shown and the instructions associated with the code block. Once this control flow representation is generated, the final step is to generate all the instructions generated during the compilation of the routine. These instructions may correspond to the instructions listed in the control flow block.
As with any architecture, a compiler is required to process a program written in a high-level language into a machine language equivalent to run on a computer. System 100 meets the above requirements by its ability to translate programs for conventional instruction processors only, or in combination with reconfigurable processors. The stage of the compiler used to translate this high-level language is based on instruction processor compiler technology. The HLL converter uses a mixed model of compilation with a language-specific front end to generate a common high-level intermediate representation. This first Bell's representation is then input to various basic optimizations, including control flow analysis, so the resulting second-level intermediate representation can be called the control flow representation. The control flow representation is a major component of the control flow information generated by the HLL converter as output. The following text provides more details about the contents of this file and any additional files that can be generated as a result of compiling at this stage.
The input to the HLL converter can consist of two different types of source code. The source code of any high-level language can be used as input to the HLL converter if this code is written to comply with the language representation it indicates. Another input to the HLL converter is the source code that represents the originally expressed high-level language control flow information. Write this control flow information to a well-defined interface specification (as described below) so that you can use the control flow information from a previous compilation, or another microprocessor. Allows control flow information derived from other sources, such as executable elements, to be used.
After the control flow analysis reveals the hierarchical flow of control in each procedure, the representation of the control flow can be generated as an intermediate language. The control flow information file generated at this point includes, but is not limited to, the following: entry symbols, user instructions, in particular symbols, basic blocks and intermediate representations.
The entry symbol represents the symbol generated by the HLL converter, which is a parameter passed in the call routine, which acts as an interface between the instruction processor portion of the executable element and the hardware logic. These symbols can pass the address of the data that the hardware logic and scalar values access for computation.
A user symbol is a symbol that represents a variable in the area of code that is compiled for hardware logic. These symbols correspond to variable names in high-level source code that include constructs such as arrays and structures. The symbol can represent any external routine call. Here the hardware logic module may be visible in the compilation process.
A basic block may be a maximum sequence of instructions, which can be entered only in its first part and can end only in its last part. The basic blocks that point to a given code source are listed here. All basic blocks start with a block information header entry. This entry gives the relative block number, the source line number that indicates this basic block, and the label that this block defines (if any) as shown in the associated symbol table. This information is followed by a list of flags indicating the attributes for these basic blocks. These flags are more about the block, for example, whether this block contains an entry into a procedure, whether this block has some xref, and whether control of this block fails and is passed to the next subsequent point immediately. Give information about. Immediately after this block information header line is a list of instructions indicating terminal nodes. Examples of these types of instructions include storing data in memory, unconditional or conditional branching, or procedure calls. Each terminal node is indicated by its relative number in the base block, the line number pointing to the "tree" of the statement instruction, and a flag that gives more information about this node.
The instructions referenced in this basic block section can be listed in the intermediate representation instructions. This section contains the individual instructions that were generated during compilation and used for optimization up to this point. These instructions are categorized into basic blocks, and their relationship to each other is earlier. Already established in the section. These are here generated in the order they were generated during the compilation process.
The first entry is the relative number of instructions in this instruction list. Next comes the instruction name, followed by each operand of this instruction. Information for the operands may be provided if the operands are labels that point to entries and entry point names in the table of variables. Shows the name from the internally generated compilation. Information about databases loaded or stored from memory may be provided. Further details on the types of instructions that can be referenced in the control flow information file are provided in the Interface Specifications section.
The generation of the control flow information file is based on the options given either on the compile command line or in the source code itself. By adding this option to the compile command, you specify which of the subprograms contained in the subprogram's larger source file should be targeted by the hardware logic. At compile time, only the specified subprogram has its control flow information written to a separate file for subsequent hardware logic compilation. The remaining source code subprograms are compiled to generate instruction processor machine code.
Control flow information files can be generated based on the presence of partitioning or bracketing, syntax recognized and parsed by the compiler. This partitioning syntax is used in connection with language-specific source lines, and if this source code is compiled for a different architecture, the partitioning syntax may be ignored during compilation. Keywords defined for this syntax allow the entire source code area to be extracted and compiled as separate subprograms for hardware logic. As mentioned above for command line options, only this specially bracketed area has its control flow information written to a separate control flow information file for subsequent compilation of hardware logic.
If the partitioning syntax does not exist in the code and there is no command line option to specify the specific subprogram targeted for hardware logic compilation, the compiler will take the default and source it as a candidate for hardware logic. You can compile the entire code. Control flow information for each subprogram is written out and can be passed for subsequent compilation. The next compilation step performs the analysis needed to determine the best point in the control flow for partitioning to generate subset control flow information. This new control flow information file is returned to the HLL converter to generate the required MAP proxy routines.
The compiler used to generate a control flow information file from a high-level language or process a previously generated control flow information file is a variety of other that provides the functionality needed to execute hardware logic. The procedure must also be generated. These procedures provide functionality by supporting an interface between the execution of microprocessor code and the execution of reconfigurable processor code. The functionality of this interface is called the "MAP proxy". Figure 6 shows an example of interface functionality.
The code contained in the control flow information file 610 may include an area of source code executed by the hardware logic. This file continues the compilation process, which makes the FPGA bitstream suitable for executing hardware logic.
The code contained in the MAP proxy 615 may be scheduled to be executed by the instruction processor instead of the area of control flow information segmented to be executed by the hardware logic. This code handles the data movement needed to support the execution of hardware logic by inserting the appropriate data manipulation constructs for the targeted reconfigurable processor. The MAP proxy may also insert run-time library calls that are used when executed to interact with the operating system. This interaction involves allocating hardware logic resources, that is, querying the hardware logic status, releasing the hardware logic resources to the system, and transferring control from the instruction processor process to the hardware logic.
The final step in the HLL converter is to generate the machine code that needs to be executed on the targeted instruction processor. The HLL converter produces control flow information for the entire source code and MAP proxy code. This information is then translated into machine code, and the binary file generated from this compilation can be used as input to the link step, which provides a unified executable element.
<u style="single">Hardware Logic Module Information File: Concepts and Structure</u> Another component of the compilation system is a database that shows the mapping of procedure calls in the source of MAP procedures to operators, built-in function calls, and existing (specified system) hardware logic modules. This database is called the system info file.
Optionally, the user may define an additional hardware logic module, which may be called to call the procedure in the source of the MAP procedure, or the built-in described in the system info file. It may be used to redefine the hardware logic modules defined in the system. In order to compile for MAP using a user-defined hardware logic module, the user must provide a database that maps the names or operators of overloaded procedures to the user-defined hardware module. It doesn't become.
All opcodes in the node of the data flow graph representation of the compiled MAP procedure must be defined in the info file entry.
The hardware logic module information file is used by both the data flow graph generator of the CFG to CFG-DFG converter and the Verilog generation stage of compiling the CFG-DFG to HDL converter.
A hardware logic module information file contains one or more entries that are concatenated into a single file. Each entry represents a unique operation (opcode) shown in the data graph or a function or subroutine instantiated through a call from a compiled MAP procedure. This description includes an interface to a hardware logic module, which is instantiated to perform operations that include its inputs, outputs, any input or output signals to which the module should be connected, and the characteristics of the hardware logic module. It should be. Optionally, the input may contain functionally equal pseudo-code, which is used in the emulating mode of the data flow graph, or in various simulation modes to emulate / simulate the functionality of the module. May be done.
Hardware logic module information file entries are start-def and end-def It is separated by a mosquito and takes the following form.
<maths num="3"><img file="JP2010146577A_D0003.tif" /></maths>
<opcode> is the ASCII string that matches the opcode in the data flow graph that corresponds to the operation, or the name of the procedure called in the source code of the MAP procedure. This <mapping and emulation information> consists of a sequence of inputs, each ending with a semicolon. The order of these sections of the hardware logic module information file entry is not important.
<maths num="4"><img file="JP2010146577A_D0004.tif" /></maths>
<macro_name> is an ASCII string that indicates the name of the hardware logic module that performs the function of the operation or procedure indicated by the hardware logic module information file entry.
<maths num="5"><img file="JP2010146577A_D0005.tif" /></maths>
<num> is an integer value that specifies the number of clock cycles between the availability of the corresponding results for the presentation and output of data to the inputs of the hardware logic module.
<maths num="6"><img file="JP2010146577A_D0006.tif" /></maths>
YES means that the hardware logic module typically holds the state between iterations in the internal registers, and NO means that it does not.
<maths num="7"><img file="JP2010146577A_D0007.tif" /></maths>
YES means that the hardware logic module interacts with an entity outside the code block, and NO means that it does not interact.
<maths num="8"><img file="JP2010146577A_D0008.tif" /></maths>
YES means that the hardware logic module is pipelined so that it can receive new inputs at each clock, and NO means that it is not.
<maths num="9"><img file="JP2010146577A_D0009.tif" /></maths>
<num> is the number of inputs or outputs to the operation or procedure at the source of the MAP procedure, or to the node that indicates it in the data flow graph. There must be a <num> input or output specification specified by the input or output ruler.
Each <input spec> has the following form.
<maths num="10"><img file="JP2010146577A_D0010.tif" /></maths>
Each <output spec> has the following form.
<maths num="11"><img file="JP2010146577A_D0011.tif" /></maths>
<n> specifies the number of zero-based input or output sequences to the operation or procedure call at the source of the MAP procedure or at the node of the data flow graph. Input and output numbering are independent, each starting from zero.
<type> is the input or output data type. It may be INT, FLOAT or ADDRESS (which is extended to include additional types: COMPLEX, LOGICAL, REAL, INTEGER, CHAR, CHARACTER). <input_port_name> and <output_port_name> indicate the corresponding input or output port name of the associated hardware logic module.
<maths num="12"><img file="JP2010146577A_D0012.tif" /></maths>
These show hardware logic module connections that are not visible at the source code or data flow graph level. <nbits> is the number of bits in the input or output signal. <macro_port_name> is the name of the signal (IN_SIGNAL) to or from the hardware logic module (OUT_SIGNAL). <internal_signal_name> is the name of the target (OUT_SIGNAL) signal in the source (IN_SIGNAL) or compiled hardware logic.
Currently three internal source signals are available.
<maths num="13"><img file="JP2010146577A_D0013.tif" /></maths>
CLOCK is the clock source for all hardware logic modules. rst is a one-time global reset. code_blok_reset is a reset signal that is always activated when the code block of the hardware logic module is activated.
No currently targeted signal has been recorded. These include error, overflow, or exception conditions that will be detected during the execution of the hardware logic module in the future.
<maths num="14"><img file="JP2010146577A_D0014.tif" /></maths>
<simcode> is a C code used to functionally define the behavior of a hardware logic module when emulating a data flow.
A syntax extension to the hardware logic module's information file entry is planned to specify changes in these or additional features of the hardware logic module. Changes and additions to these properties allow a new input to be received every n iterations, and to receive an input for n iterations and generate i after a clock period of j. A description of the hardware logic module that can be used, a means of specifying how often the hardware logic module is executed, and a directory path to a file containing HDL code that defines the hardware logic module for actual code or simulation. , And resource request specifications for hardware logic modules, but not limited to these.
<u style="single">Translation of hardware logic module information files</u> In addition to the data flow graph, there is a second input file to the CFG-DFG to HDL converter. This is a CFG-DFG to HDL converter binary file that contains information about the hardware logic modules contained in the interface and hardware logic module information files. In the embodiments of the present invention, a small executable element may be used, which translates the ASCII hardware logic module information file into the internal table of the CFG-DFG to HDL converter and from CFG-DFG to HDL. Executed at compile time before calling the converter of.
This translation program can be called with one mandatory and two selective command line options. The required option, -o outfile, indicates the name of the output file from which the CFG-DFG to HDL converter table should be written. The option -ddeleted_signal indicates the names of the input and output signals in the hardware logic module information file that should be ignored. That is, the translation program skips the processing of the signal called deleted_signal in the hardware logic module information file specified by the ad option. This allows the entry in the hardware logic module information file for the hardware logic module to contain inspection signals or signals used in the simulation that may not be present when generating the actual hardware logic. The second selective command line argument is -r sigval = newsigval. This translation program replaces the occurrence of the pin or wire name specified by sigval in the hardware logic module information file with the resulting string newsigval in the CFG-DFG to HDL converter table. This option allows you to rename the input and output signals of the hardware logic module that should be connected by the CFG-DFG to HDL converter. CFG -The DFG to HDL converter can ignore any connection that should be connected to a wire whose name starts with "unconnected_". By renaming the unconnected_ wires with this option, these can be processed by the CFG-DFG to HDL converter. With respect to the -d option, -r is useful when generating HDL like Verilog, which is used in test benches or simulation environments and is actually in Verilog generated due to the resulting hardware logic. Can have signals that do not exist in. Multiple -d and -r options may be specified.
The translation program can be started by initializing the CFG-DFG to HDL converter table to be built and calling gr_tables_init in the CFG-DFG to HDL converter support library. The command line options can then be processed. An array of character pointers containing the list of deleted signals specified by the -d command line option is constructed. The character pointers of the two parallel arrays are constructed for the renamed signal (-r option). The first array contains the string specified by sigval in the option, and the second array contains the string specified by newsigval in the option. For a given renamed signal in the first array, its corresponding new name is placed in the same index on the second array. The output file name specified with the -o option is inserted into the CFG-DFG to HDL converter OUTPUT_FILES table.
After the table is initialized and the command line is processed, the hardware logic module information file is parsed to form an array of subref data structures. There may be two hardware logic module information files containing any number of entries. One hardware logic module information file is supposed to contain an interface, which maps the opcodes that appear in the data flow graph nodes to a particular hardware logic module known to the compilation system (embedded operations). Is. This hardware logic module information file is called a system hardware logic module information file and is arranged by reading environment variables. An optional second hardware logic module information file is provided for users with hardware logic modules that are not originally known to the compiler, and for any user who has been given a redefinition of either the embedded hardware logic module. Includes interface. The generation of the parsing and subref structure array of the hardware logic module information file is performed by fetch_all_subref, a function shared with the CFG to CFG-DFG converter. The fetch_all_subref parser and semantic routines can be generated by the GNU tools flex and bison.
The subref structure is used to store information in the translation program and the hardware logic module information file inside the CFG to CFG-DFG converter. When the definition of each opcode information file is parsed, the information is stored in the subref structure. Parsing continues until all hardware logic module information files are parsed and an array of subref structures is built. The translator then enters a loop through an array that processes one subref structure at a time, while constructing a CFG-DFG to HDL converter table that holds the hardware logic module interface.
The CFG-DFG to HDL converter tables constructed by processing the subref structure are EQUIV_IN, EQUIV_OUT, EQUIV_IN_PRS, PIN_NAMES, HELD, BEHAV_V and BEHAV_C. The contents of each of these tables are shown in the description of the processing of the subref structure (below). One EQUIV_IN and one EQUIV_OUT table generated for each subref structure to be processed There is a bull entry. The table indexes of the EQUIV_IN and EQUIV_OUT table entries for a given subref are the same.
Processing of the subref structure is started by inspecting the name field of the opcode of the subref structure. If no name is specified in the hardware logic module information file entry, an error is issued and the rest of the current subref structure is skipped. If a name is specified, the CFG-DFG to HDL converter table constructed from the previous subref process is searched for previous subrefs with the same opcode name. If this is found, a warning will be issued and further processing of the duplicate named subref may be skipped. The first hardware logic module information file entry for the operation code name is used. Note that the user's information file entry is the first entry to be parsed, and its corresponding subref structure appears in the subref array with the smallest array index. Therefore, the user can provide their own hardware logic modules for any given opcode known originally compilers, for order of processing of subref array, user info file d for that opcode entry is , Replaces any entry in the system info file.
The index of the first free entry in EQUIV_IN_PRS is saved and later placed in the EQUIV_IN table entry for the current hardware logic module information file entry. Use this to put the first input parameter for the hardware logic module. The hardware logic module wait time is saved for later insertion into the EQUIV_OUT table entry for the current info file entry. If no wait time is specified or it is negative, an error is issued and a value of zero is used for the wait time.
Output parameters can be processed first. An EQUIV_IN_PRS table entry is generated for each output. The bit width of the output and the index to the EQUIV_IN / EQUIV_OUT table entry for this subref are inserted into the EQUIV_IN_PRS table entry. A flag indicating that this is an output is set in the EQUIV_IN_PRS table entry to distinguish it from the input. A PIN_NAMES table entry is then generated for the output parameters. The PIN_NAMES table entry indicates the name of the output parameter, its bit width, its index to the previously generated EQUIV_IN_PRS table entry, the index of the current subref's EQUIV_IN / EQUIV_OUT table entry, and this is the set of output pins. Has a flag. If this is the first PIN_NAMES table entry generated for the current subref (the first output parameter processed for the module), the PIN_NAMES table index will be later inserted into the EQUIV_OUT table for the current subref. Saved for.
The output signal of the operation code is processed after the output parameter. The list of deleted signals specified by the -d command line option is searched to determine whether the output signal should be input to the CFG-DFG to HDL converter HELD and PIN_NAMES tables. If this is found, the signal will be skipped. Otherwise a HELD table entry will be generated. This HELD table entry contains an index to the associated PIN_NAMES table entry for the signal, the bit width of the signal, and the name of the external signal to which the output signal should be connected. You can search the table of renamed signals specified by the -r command line option to see if the signals have been mapped again. If it has been mapped again, the signal name that has been mapped again will be used. Otherwise, the name specified in the hardware logic module information file is used. If no external signal name is specified, an error will be issued. The PIN_NAMES table entry is next Can be generated for the output signal. The PIN_NAMES table entry is the EQUIV_IN / EQUIV_OUT table index for the current subref entry, the bit width of the output signal, the index of the HELD table entry generated for this signal, the signal name inside the hardware logic module, and the signal. Contains two flags indicating that is an output and there is a HELD table entry for the signal. If this is the first signal processed for the subref structure, the index of the PIN_NAMES table entry is saved to be inserted into the EQUIV_OUT table entry for the subref.
After the output signal is processed, the input parameters for the subref are processed. EQUIV_IN_PRS and PIN_NAMES table entries are generated for each input. The contents of the EQUIV_IN_PRS entry may match what was generated for the output parameters, except that no flags were set to indicate the output parameters. The PIN_NAMES table entry contains the same information as the PIN_NAMES table entry for the output parameters, except that it is flagged as an input rather than a flag pointing to the output parameters.
The input signal is processed after the input parameters. A HELD and PIN_NAMES table entries are generated for each input signal. The processing of the input signal and the resulting table entry is the same as that of the output signal, except that a flag indicating that the signal is an input rather than an output is inserted in the PIN_NAMES table entry.
The last PIN_NAMES entry is generated for the subref and the index of the last entry is saved for insertion into the subref's EQUIV_OUT table entry.
Finally, the EQUIV_IN and EQUIV_OUT table entries for the subref are generated. This EQUIV_IN table entry contains the index of the first EQUIV_IN_PRS table entry generated to handle this subref structure. An index is generated for the last EQUIV_IN_PRS table entry for this subref, and this subref defines the name of the opcode for the table flow graph. The EQUIV_OUT table entry contains the latency of the associated hardware logic module, the name of the hardware logic module, the index of the first PIN_NAMES table entry associated with the subref, and the index of the last PIN_NAMES table entry associated with the subref.
This completes the subref processing. info2grf continues until all subref structures have been processed. If no errors are found during processing, the CFG-DFG to DHL converter table is written to the output file and a zero status code is returned. Otherwise, the table will not be printed and a nonzero status code will be returned. Then the translation program can be terminated.
<u style="single">Conversion from CFG to hybrid CFG-DFG</u> Examples for converting the CFG representation to the hybrid CDFG-DFG representation are described here. The original CFG representation may include nodes and directed edges, where each node may be a basic block of code, where each edge goes from the end of one block to the beginning of another. It can indicate a shift in control. The code in a basic block can have a single point at the entrance and a single exit, i.e. a statement of a sequence of straight lines that cannot branch to or from each of the beginning and end, respectively. Can be shown. The sentences in the basic block may be continuous.
The hybrid CFG-DFG representation can have a CFG representation at its higher level, but each It has a data flow graph in the block. In one embodiment, the CFG to CFG-DFG conversion can integrate groups of basic blocks, including groups that form internal loops into flat or pipelined code blocks.
Figure 7 shows some examples of CFGs that correspond to the following code fragments.
<maths num="15"><img file="JP2010146577A_D0015.tif" /></maths>
In this example, a conditional test comparing'a'and'b' can be stored in a register or temporary variable, which may be the last statement in its basic block. Based on the results of the comparison, control can be moved to one of two blocks that indicate the "true" and "false" parts of the conditional construct. Each of these blocks may, after executing its statement, move control to a block containing conditional code. Note that code blocks in CFG can include sequential statements, each of which can be referenced by reading and writing registers or variables. Furthermore, it should be noted that directed edges between blocks can indicate a movement of control that is considered as a 1-bit "trigger" signal.
CFG representations may be used in many compilers, such as internal intermediate representations, but data flow graphs are not usually used. This is because the dataflow execution paradigm is not well suited for traditional von Neumann processors due to the use of many arbitrary functional units and asynchronous execution. However, the data flow model is well suited for reconfigurable hardware. In a data flow graph, a node may represent a functional unit (eg, integer addition). Directed edges between nodes can represent data connections that bring output data items from one functional unit to the inputs of other functional units. Figure 4 shows a data flow graph of the following code fragments.
<maths num="16"><img file="JP2010146577A_D0016.tif" /></maths>
The input values'b'and'c' can be loaded at the top of the graph. These values can flow from the output port (bottom) of the LOAD node. Data flow graphs can reveal instruction-level parallelism. Here, three instructions (two multiplications and one subtraction) can occur at the same time. Note that the'd'variable may not require memory. Because this is a graph It may be local to, or it may exist as a side. In addition, the intermediate value assigned to'a'is not stored in that variable and may simply exist as an edge. This is because the following sequential allocations may produce a final value of'a'. Such a data flow graph can be mapped directly to reconfigurable hardware by initializing the selected functional unit. In this example, one addition, two subtractions, and two multiplications are generated.
Consecutive statements in each basic block of the CFG representation generate a hybrid by being transformed into a data flow graph, in which the higher level nodes are code blocks with single-bit edges and each block. Within, the node may be a functional unit and the side may be a data flow graph with data connections. FIG. 8 shows an example of such a transformation applied to the CFG of FIG.
In an embodiment of the invention, a subset of basic blocks in a CFG representation is merged into a single data flow code block, the condition calculates both sides, and then the appropriate value based on the predicate expression of the condition. Can be processed by selecting. FIG. 9 shows an example of such a code block, in which the code blocks of FIG. 8 are merged.
In addition to scalar and array data types, high-level languages may have a structure of user-specified data types that may be a complex of simpler types. The front end of a traditional compiler can handle CFG representations by providing proper address computations in the basic blocks they generate. When such a structure is in local memory, the address calculation may remain unchanged when converting the graph to a control data flow graph. For structures as local variables, the translation process uses type information along with address offsets to determine which fields in the structure should be referenced.
Pointers can be treated according to the architectural details of the target machine. If the reconfigurable hardware "finds" the same memory space as the processor that passed the address parameter to it, the pointer operation can work unmodified. If this is not found, the coordinator is calculated at runtime. This factor may be the difference between the address in the processor's memory and the location where the data was copied to the reconfigurable hardware OBM. The control data flow graph is generated to include the addition of this factor when referencing the pointer.
Traditional high-level languages can have small pairs of fixed-size arithmetic data types (eg 32-bit and 64-bit integers). This corresponds to the fact that the targeted von Neumann processor can have a fixed size functional unit. On reconfigurable hardware, functional units of any bit width may be instantiable, which achieves space savings by using the amount of precision required for a given program. Can be done. One way to achieve this savings may be to extend the high-level language to include new data types with user-specified bit widths. Another approach may be to allow the user to specify a bit width of a standard type (eg int) for a section of source code.
It may be possible for the compiler to infer the safety of reducing the accuracy of some functional units and the data paths to which they are connected. For example
<maths num="17"><img file="JP2010146577A_D0017.tif" /></maths>
In the code of, it may be safe to change the addition operation to an 8-bit adder. This is because high bit results may be lost when allocating the results.
In another embodiment, the component of the translation of the CFG representation into a control data flow graph may be a database that describes a map of function calls to operators and existing hardware logic modules. This database may be referred to as an "info file" and may be used in various steps during compilation.
Function calls can be handled in different ways, depending on the nature of the routine being called. That is, if routines are associated via an "info file" that has a hardware logic module, a single node can be generated in the data flow graph and shown as a functional unit. If the routine reaches the appropriate criteria, it can be inlined so that it does not require a calling mechanism. If the function is terminal recursive, this can be translated into a loop. If the function does not fit into the above categories, a stack-oriented calling mechanism may be used. In another embodiment, the LIFO stack may be implemented with reconfigurable logic, which can hold various instantiations of local variables when recursion occurs. The stack information can guide the flow of control so that recursive call return occurs appropriately.
The hybrid control data flow graph can be adapted to multiple threads of execution within a subroutine that has itself compiled into reconfigurable hardware. While the meaning of high-level languages specifies sequential execution (one block of code can be active at any given time), concurrency at the code block level is inaccurate for the compiler to execute in parallel. It may be easier to achieve when you can decide not to bring results. This decision can be made in a variety of ways, depending on the language and its possible extensions. For example, if the language contains parallel constructs, parallelism may occur as part of the CFG representation. In addition, sequential languages may be extended by user pragmas, which allow programmers to guide the compiler to produce some parts of code parallelism. Analysis allows the compiler to prove that certain code blocks can be successfully executed in parallel.
FIG. 11 shows an embodiment with a sequential portion of the CFG representation on the left and a modified graph with two code blocks placed side by side on the right. The trigger signal from the preceding block spreads to trigger both parallel blocks, and a "coupling" mechanism called LATCH_AND can be used to merge the "done" signals from the two blocks. LATCH_AND can be designed to latch each input signal when it goes high so that the incoming triggers do not occur at the same time.
The connectivity information in the control data flow graph can be used to improve the logical placement performance in the FPGA. In the current position and root tools, placement issues are seen at a very low level, and the items placed may be very small logical blocks. Compiler benefits If the available hardware logic modules have already been determined to be of the specified shape, the compiler will deploy at a higher, and therefore simpler, level of granularity, potentially significantly speeding up the process. be able to.
Figure 12 shows the process at the highest level for converting the CFG representation of a subroutine into a hybrid control data flow graph. One or more "info files" may be read to obtain information about the available hardware logic macros that may be available for the implementation of data flow graphs as reconfigurable logic. After reading the CFG representation into its internal data structure, the compiler can separate "external" hardware logic module calls into individual blocks. This can be done because an external module can interact with resources outside its block of code and run in parallel, resulting in a turbulent state. The individual blocks can then be combined into larger blocks, as in the example of FIG.
Each block can then be processed. For non-loop blocks, LOAD nodes can be created for the various scalar values referenced. Next, a data flow graph of block calculations can be created. Finally, a STORE node can be created for each scalar variable to store its closing price. The inner loop may require some additional action. Once the head block of the inner loop is found, the rest of the blocks in this loop can be collected and sorted topologically. The LOAD and CIRCULATE nodes can then be built for the scalar in question. The code block of the loop can then be processed in a manner similar to that of the non-loop block.
After each DFG is created, delay nodes can be inserted through the data flow graph to balance the path length (which can be measured in clock increments). Next, various optimizations can be performed on the graph. After all the DFGs have been created, they can be written to a DFG file to create a logic emulated file.
A CFG representation can consist of two parts: an array of opcodes and a sequence of basic blocks. An opcode can be read into an array of structures whose elements consist of one opcode and a reference to the data source of this opcode. Each basic block in the CFG representation can be stored in a structure as shown below.
<maths num="18"><img file="JP2010146577A_D0018.tif" /></maths>
Once a data flow graph is constructed for a block, the nodes can be assigned within the "pool" field of the basic block structure. An example of the data flow node structure is shown below.
<maths num="19"><img file="JP2010146577A_D0019.tif" /></maths>
In one embodiment, two files can be written as output. That is, a data flow graph file and an emulated logic file. The following simple C source functions can be examples of these files.
<maths num="20"><img file="JP2010146577A_D0020.tif" /></maths>
The following code example shows a dataflow graph file that can be generated when the C function example is compiled.
<maths num="21"><img file="JP2010146577A_D0021.tif" /></maths>
The data flow graph example above has two sections. The first is a list of parameters and local variables by name, type and type (parameter or local). )according to. The second section is a list of code blocks. In this example, the code blocks are not merged. Each block has a unique number of IDs and a set of data flow nodes. Each block has an SRC ^ INITIATE (start) node and an SRC ^ OUTPUT (output) node as its start node and end node. There is the following information for each node. That is, its function, its input and output counts, the bit width of each input, the constant value for the input for which the input is specified as a constant, the bit width of each output, the target list of each output (ie other node inputs). Which of the ports is supplied by this output). Input and output ports may also have a unique pseudo-register ID in parentheses.
The end of each block can specify where the control flow goes as it exits the block. When a block ends with a conditional statement, two goal blocks can be designated as TRUE and FALSE goals. Elsewhere, one block can be specified, or if the block is the end of a function, EXIT can be specified. FIG. 13 illustrates this code block set.
An emulated logic file can be written along with the data flow graph file. This can be a simple C routine that can be executed as a thread, emulating the reconfigurable logic part of the program. An example of an emulated logic file for an example of a C function is shown below.
<maths num="22"><img file="JP2010146577A_D0022.tif" /></maths>
In the emulated logic file example above, an infinite loop can act as an FPGA. Therefore, it may follow the same protocol, using flag registers FR2 and FR4 as start and end handshakes in this example, respectively. When it receives the start signal from FR2, the emulate routine can load initial values for the parameters of the user subroutine. Then dfg_simulate can be called and the name of the DFG file to be executed can be passed through. The data flow simulator performs a token-driven simulation and can return when the EXIT code block completes. Then the closing price of the parameter is returned, which can be followed by the FR4 handshake. The routine can then return to the top of the loop and wait for the next signal to execute.
Next, another embodiment of conversion of a basic block in CFG to a code block in DFG will be described. In this example, load / memory can be treated in two different ways, depending on whether it is a scalar reference or an array reference. Scalar references can be converted to DFG edges, where a single load is at the beginning of the block and a single memory is at the end. Array references can be converted to onboard memory (OBM) references.
Scalar variable references for pass-by-reference parameters can differ from local variable references. The CFG output on the front end of the compiler can reflect this. That is, it is possible to put some level of indirectness in such a parameter reference. FIG. 14 illustrates this difference.
As another example, consider the following set of operations.
<maths num="23"><img file="JP2010146577A_D0023.tif" /></maths>
As shown in FIG. 15, the front end may generate a set of opcodes at its CFG output. Since this was a Fortran source, the scalar can be brought in by reference and the LDA (load address) node can perform indirect steps by fetching an address from an address that can be entered into it.
Note that graph sharing may not represent a common subexpression. For example, the output of a node may go to two places and represent two readings for the variable'c' in the code. However, these two readings may not produce the same value, because there may be an intervening memory between them.
In one embodiment, the first step in processing the basic block may be to construct a data flow graph fragment from the operating code. This can be done by a routine that starts with each anchor (bottom) opcode and recursively builds a tree on it. Since sharing between fragments is not possible, the result of this routine may be to construct the fragments shown in FIG.
In one embodiment, after the construction of the DFG fragment, the LDA node can be eliminated from under the ACON (address constant) responsible for the scalar reference passing parameters. This reflects that the MAP compiler (that is, the part of the system that compiles part of the HLL source code into reconfigurable hardware) can treat it as a copy and restore rather than by reference. It is a fact. Along with this, the DFG fragment can be as shown in FIG.
Then, starting from the anchor and looking upwards to find ACON, a list of all referenced variables can be created. An INITIATE node can be created as the head of the DFG, and a layer of LD_SCALAR nodes can be created to bring in the initial scalar values. A temporary array of data structures can be created as a reference for the source of each variable. An example of this structure is shown below.
<maths num="24"><img file="JP2010146577A_D0024.tif" /></maths>
You can initialize this array and let its LD_SCALAR node reference all the variables. DFG fragments can be converted to DFG after subroutine and function calls are processed.
In one embodiment, the CFG to DFG conversion can be a routine that begins at the bottom of each DFG fragment and does the following: That is, scan upwards to find the load node. For each load, look at the ACON above it to determine which variables are loaded. Eliminate the load node and then rewire the target node so that it is fed by the current source of this variable. If the anchor is a scalar memory, look at the input on the right to determine which variable is stored. The storage node can then be eliminated and the source to the left of the node recorded as a new source for that variable.
In this example, once the first anchor is processed, the LDKR nodes for the values'b'and'c' can be found. These can be eliminated and the nodes they supply can be rewired so that they are supplied from the LD_SCALAR node at the top of the DFG. You can then eliminate the STKR node and show the KADD node as a new source for the variable'a' in the temporary array. Once the next anchor is processed, the two LDKR nodes can be found. The source for the'b'value can still be its LD_SCALAR node, but the source for the'a' value can be KADD. The LDKR node can be eliminated and the target can be wired to a suitable source. You can then eliminate the STKR node and show the KSUB node as a new source for the variable'c'. Once the third anchor is processed, the LDKR can be eliminated and the target rewired to the output of the KSUB. Then STKR can be eliminated and KMUL can be shown as a new source for the variable'a'.
After all the anchors have been processed, the closing price of the scalar can be remembered by referencing the last source of these variables by creating a layer of ST_SCALAR nodes. ST_SCALAR has a trigger output that can be collected to the LATCH_AND node, which can supply the OUTPUT node at the bottom of the DFG. Any LD_SCALAR node with unused output can be eliminated by the obsolete code removal pass. The compiler can also look for ST_SCALAR nodes that remember the values that come from the LD_SCALAR node for this variable, and the values for these haven't changed, so you can eliminate them. FIG. 18 shows an example of the resulting DFG code block for this example.
In one embodiment, the DFG generator can distinguish between loading / storing scalar variables and loading / storing array elements. When the DFG generator looks at a load or storage node (eg LDKR or STKR), it can determine the load / storage type by looking at its address input. If you look at something in the form shown in Figure 14, you can use the ACON node to find the name of the variable and examine the internal "variable" data structure to determine if it is a scalar variable.
FIG. 19 shows an example of an array reference. Note that in this example of a hard-coded "1" index, the reference appears structurally like a scalar local variable reference, and by examining the "variable" structure it can be known that it can be an array. I want to. Also note that ACON nodes can have variable names and constant offsets. In the second example in FIG. 19, 48 offsets are derived from the fact that the reference is 6 elements away from the base address and the size of each element is 8 bytes. In the third form, the address is supplied by the representation tree. Here the ACON node for'BB' is given an offset of -8, compensating for the fact that the index of the array starts with 1. Since the address is byte-oriented, the IMUL node can be multiplied by eight.
Load and storage nodes for array references can be left in place, but each storage node can be given additional enable input. For basic blocks, this enable input can be supplied by the block's INITIATE node.
In another example, where the block's CFG is converted to DFG, the anchor can be a subroutine call rather than a memory. Consider the following code fragment.
<maths num="25"><img file="JP2010146577A_D0025.tif" /></maths>
The front-end output for this code is shown on the left in Figure 20. This can be supplied by a linked list of ARGAR nodes, each bringing one argument to the call. After the DFG generator builds a DFG fragment from the opcode, a routine that finds a subroutine call anchor can be called. This eliminates the linked list of ARGAR nodes, one for each, giving multiple call nodes multiple inputs with arguments to which they are wired. This requires some knowledge of subroutines, which can be derived from the'info'file. For nodes with a state, additional inputs may be created for connection to the enable signal. For external nodes, additional inputs and outputs can be given for trigger and done signals (additional indirect for scalar parameters by the time this step is performed). Note that may have already been lost).
The info file can specify for each argument whether it is a value or an address. In addition, you can specify which is the input and which is the output. If the input argument is a value (but not a constant), then a suitable load node can be created. If it is an address, it can be left unchanged. For this example, assume that this is a 2-input, 1-output subroutine. In the center of Figure 20, the DFG code fragment for the subroutine call after the call has been converted to DFGJSR and LDKR nodes have been added for the two inputs is shown.
After the subroutine call is being processed, the DFGJSR node can cause the info file to be examined again. The two inputs can be treated in the same way as the inputs to other nodes. That is, it is possible that the source of the variable is shown, the LDKR node is lost, and the input is wired directly to the source. For output, it is possible that the incoming edge is eliminated, the ACON node is examined to determine which variable is receiving the output value, and this output is shown as a new source for that variable. DFG on the right side of Figure 20 The complete code block after conversion to is shown.
Calls to built-in functions can appear as non-anchor JSR and QJSR nodes in the CFG output. After the subroutine call has been dealt with, the remaining JSR and QJSR nodes can be function calls.
An example of such a function call is shown below.
<maths num="26"><img file="JP2010146577A_D0026.tif" /></maths>
The CFG that this function call results in may have its second assignment shown in Figure 21. As with subroutine calls, their arguments form a linked list. As shown in the center of this figure, the arguments can be flattened to multiple inputs. From this point, the DFG can be constructed by a general method, resulting in the graph shown on the right side of FIG.
Basic blocks may end with a conditional statement. In this case, the second input to the OUTPUT node may be supplied by the result of the comparison. Consider the following code as an example.
<maths num="27"><img file="JP2010146577A_D0027.tif" /></maths>
Note that the a = a + 1 statement is not part of the basic block. This block ends with a conditional check. The final anchor is the ICJMPZ node, the structure above which is shown on the left side of Figure 22. The QJSR, DFRIR and ICJMPZ nodes will be replaced by KCJMP. After this, KCJMP can be KCMP_le. The DFG for the code block is shown on the right, where the KCMP_le node can be fed by the closing price of'a'and its output goes to the second input of the OUTPUT.
As shown in Figures 9 and 10, basic blocks can be merged into a single large block of code. This process may include the steps of computing all routes and using a multiplexer called a SELECTOR node to select the appropriate value to address the conditional statement inside the code block. Consider the following code as an example.
<maths num="28"><img file="JP2010146577A_D0028.tif" /></maths>
In this example, both aa + 1 and aa-1 equations are calculated in each iteration and the'bb'value assigned to the'BL'array is fed by SELECTOR. The job of building a merged code block from various basic blocks is the step of building a DFG segment for each block and the step of wiring them together using control signals and selectors derived from the conditional representation of the conditional statement. And can be included.
In one embodiment, the first step in creating a merged code block may include a step of topologically sorting the merged basic blocks. When a block is processed, the block that supplies control to a given block can be transformed before that block is transformed. In the early steps of the process, each block can be transformed into a DFG similar to the individual blocks. The LD_SCALAR node can be built at the top of the DFG. The code block can then be transformed. Differences between merged code blocks and individual basic blocks can include Boolean control signals and selector node hookups.
As an example, an arbitrary block'B'in a set of blocks to be merged, three blocks can send control to'B', and'B' gives control to two blocks at the end. Consider block'B'to send to one of them (note that any number of blocks can send control to a block, but a given block sends control to two blocks. ). This is shown on the left side of FIG. Suppose there is a 1-bit signal from each of the incoming and outgoing blocks that is high if control is transferred to block'B'. The active signal of block'B'is calculated by ORing the incoming signals. Block'B'can then calculate activation signals for two blocks that it can activate. 'B' ends with a conditional statement because it can activate two blocks. By taking the logical product (AND) of the predicate of this conditional statement and the block start signal, the start signal for the "true" signal is obtained, and the logical product (AND) of the opposite predicate and the block start signal is obtained. This gives an activation signal for the "false" signal. On the right side of FIG. 23, the nodes that calculate these signals at'B'are shown.
The basic block data structure has a feed that stores control information that may include: That is, the "Incoming" field is a linked list of all blocks that have control flow edges to the current block. The "active" field is the ID of a node whose output represents the active signal of the current block, i.e. the output of the OR node sequence. The src_true field is the ID of the node that calculates the true output control signal. The src_false field is the ID of the node that calculates the false output control signal.
After building the control signal, the selector is installed for incoming data values. FIG. 23 shows the selector node added to the example in FIG. 24 for the variable'x'. The output from the OR chain can be supplied by these selectors. One set of selectors for each variable in the loop Can be created.
The conversion of the inner loop to a pipelined DFG can be based on the conversion techniques described above. Consider the loop example shown below.
<maths num="29"><img file="JP2010146577A_D0029.tif" /></maths>
This loop is a single basic block with a conditional branch to itself. Figures 25A and 25B show code fragments for anchors. The first one reads'AL (i)'and stores it in'aa'. The second one calls the subroutine'xyz'. The third one stores'bb'in "BL (i)". The fourth one increments'i'. The fifth one subtracts'.Y0001'. The sixth one checks'.Y0001' and branches back to this block if it is greater than zero.
The code block of this loop can be transformed using the basic block technique. Each time a block is fired, it loads it, calculates its value, and stores it. It then passes control to itself and repeats for the next iteration. There can be some instruction-level parallelism in this execution. In another embodiment, the array values are read and each written at every clock to take advantage of the pipelined implementation for the various functional units.
To achieve pipelined execution, a loop "generator" can be created, which controls the loop by firing iterations at specified intervals. This node can be called LOOP_DRIVER. It can be triggered by the INITIATE node at the head of the code block to initiate the emission of a row of pulses. Each pulse can signal the firing of one iteration of the loop. The LOOP_DRIVER node may not determine when the loop ends. Other parts of the data flow graph can be inspected for termination conditions. The iterations can be fired at each clock tick or slowed down to accommodate loop carry dependencies or multiple OBM accesses. The input to the LOOP_DRIVER node can specify its "duty cycle" (ie, the number of clock ticks that should occur between repeated firings).
Loop carry color dependencies can exist so that there can be a mechanism for managing them in a pipelined loop. The CIRCULATE node (32 or 64-bit format) exists to hold the current value of the scalar variable and can be connected to the output of the LOOP_DRIVER node. CIRCULATE knows that the loop is starting up when it sees its first input go high. An initial value can be taken from that second input, followed by a new value from that third input each time LOOP_DRIVER fires an iteration. This third input is its "circulated" value. If the scalar variable does not change its value within the loop, the output of the CIRCULATE node can be directly connected to its own third input.
In one embodiment, loop termination can be determined by conditional inspection somewhere in the loop body. Since the loop can be pipelined, some additional iterations may have already been made by the time the termination condition is detected. These overflow iterations are not harmful as long as the values are not written to the OBM. Therefore, termination detection can gate the enable signal to OBM storage within the loop. It may also trigger a TERMINATION node, which signals the ST_SCALAR node to capture the current value of the scalar variable.
FIG. 26 shows an example of DFG for the loop of FIGS. 25A and 25B. The top layer of the LD_SCALAR node and the bottom layer of the ST_SCALAR node can be the same as in a simple basic block DFG. Shaded areas indicate loop-specific parts of the graph. There are CIRCULATE nodes for the variables'al','bl','. Y0001' and'i'. The first two of these can be base addresses that do not change. The last two are the down counter and the up counter, respectively. LOOP_DRIVER is the control part of the loop. A zero at its second input indicates that it does not need to insert clock ticks between loop iterations. The CIRCULATE node monitors the output signal of LOOP_DRIVER, and each time it indicates a new loop iteration, the node takes in its circulating input value. The end of the loop can be detected by the IGT node comparing the down counter to zero. If the IGT output is false, LOOP_VALID will detect this and disable the LDKR and STKR nodes, signaling the TERMINATION node. The TERMINATION node then triggers ST_SCALAR, which allows it to capture the closing price from the CIRCULATE node.
In one embodiment, the pipelined logic within each functional unit can be activated at each clock tick. Appropriate "matching" can be done for the values that appear on the input ports of a given functional unit. On the left side of Figure 27 is a DFG fragment that computes the equation C = A- (A + B) * B with some latency next to the node. Below that is a chart showing the value of the signal at each clock step. Due to node latency, the values that appear on the ports of the multiplication and division nodes may not be properly aligned. As shown on the right, a DELAY node, which is a fixed-length FIFO queue, can be inserted. This insertion is done so that for each and every node in the DFG, the path lengths to all its inputs are equal.
Various optimizations can be performed after the construction of the DFG. For example, after creating a control data flow graph code block, several SELECTOR nodes in the graph may have both value inputs sourced from the same source. Such a node may be eliminated because the same value is selected regardless of the predicate value to be supplied. This situation often occurs when basic blocks are merged into one larger code block. FIG. 28 shows some of the code blocks that occur when the following code fragments are merged into the blocks.
<maths num="30"><img file="JP2010146577A_D0030.tif" /></maths>
In this example, the two value inputs in the rightmost SELECTOR are sourced from the same source, because'c'is not assigned in any branch of the conditional statement. This SELECTOR may be eliminated.
In another example, merged code blocks often provide an opportunity for simplification of Boolean arithmetic expressions. FIG. 28 shows an example. The output of the OR node is the Boolean expression'ex + ex', which simplifies to e. OR nodes can be lost. A more prominent opportunity similar to the above arises when nested conditional statements are merged. Pipelined loop cord blocks can also be fused, which feeds the output value directly from one loop to another.
<u style="single">Division</u> Next, with reference to FIG. 29, an embodiment of the segmentation unit element of the present invention is shown. In one embodiment, the segmentation element can determine where part of the algorithm will be executed and thus the goal of the compilation process. The divider can compute the internal representation of the HLL that defines the compiled algorithm for the control data flow graph. The control data flow graph taken by the divider can be a CFG-DFG generated by a CFG to CFG-DFG converter. CFG-DFG is a graph of a set of functions that can be found in a compiled file. The decision process results in part of the instruction-targeted code for the instruction processor and part of the logic in many reconfigurable chips contained within many reconfigurable processors. ..
The partitioning process may take a single control data flow graph as input and generate a set of output control data flow graphs. Each of them depends on a specific targeted realization. The output CFG-DFG can consist of a partition block, which is a subgraph of the original, and edges that represent the connections between the segmented codes.
The division decision is based on several factors, including: That is, factors such as the nature of the input control data flow graph, the available hardware resources, and the size and performance characteristics of the hardware resources.
A large number of segmentation algorithms can be devised and alternative algorithms can be called and evaluated in the decision process. Each such segmentation process aims at targeting hardware resources according to optimization strategies. The input control data flow graph may create a set of connected subgraphs that fit within the available resources of the hybrid computing platform while satisfying a set of optimization criteria. Optimization criteria can be, for example, maximizing the use of reconfigurable resources, minimizing the number of reconfigurable chips, minimizing interconnects, maximizing overall performance, and so on.
From the initial control data flow graph, a new graph that can consist of partition blocks and edges is created. Each compartment block contains a subgraph of the original control data flow graph (ie CFG-DFG) and an assignment to a reconfigurable chip or instruction processor. Each edge in this new graph can represent a physical connection between the allocated resources.
Next, the division task can be reasonably connected to another division block that is a task that meets the optimization criteria and the size limit and creates the division block. One such partitioning technique for achieving optimum performance across hybrid systems is described below.
In one embodiment, the partitioning step is as a subgraph assignment to a partitioning block based on a programmer-supplied partitioning syntax or directive, such as a C-pragma or compiler directive passed to the partitioning section as an annotation in an input control data flow graph. Can be defined.
If any CFG-DFG subgraph remains after working on the programmer-supplied partitioning syntax instructions during partitioning, the compiler-initiated partitioning can proceed as follows. That is, list all remaining CFG-DFG subgraphs as candidate segmented blocks; profiling data from the instruction processor profiler, DFG-emulated profiling, performance estimation based on the degree of parallelism, and each behavior for each block. Hardware Logic Modules for Candidate Partition Blocks Potential Potential Using Information, including Performance Information Found in Information Files and Data Flow Performance Between Candidate Partition Blocks and Adjacent Blocks Order by the order of; Compare the estimated performance of the compartmentalized blocks as reconfigurable logic vs. instruction processor code; Assign candidate compartmentalized blocks to the chip or instruction processor based on the comparison; Proceed through all candidate blocks; Estimated Order the candidate segmented blocks according to their performance; then select the final candidate block that completely covers the CFG-DFG component output CFG-DFG that contains the partitioned blocks.
Once this is done, the set of compartmentalized blocks can define the execution location and the control data flow graph loaded into the resource. The partition block is passed to the HLL converter. Blocks intended to be executed by the instruction processor can continue the compilation process to code generation and object file generation. The block targeted at the reconfigurable chip can be passed to the HLL converter to generate the MAP proxy code, and then the CFG-DFG can be passed to the CGF-to-CFG-DFG converter to continue the logic generation process. Eventually, the compartmentalized block continues the compilation process from the CFG-DFG to the HDL converter, and finally to the generation of the bitstream to be included in the unified executable.
<u style="single">Preparation for HDL conversion</u> One of the outputs of the CFG to CFG-DFG converter is an ASCII text file that represents the transformed data flow graph for the procedure being compiled. The next step in compiling is translating the above file (ie .dfg file) into a format that can be used by the Verilog code generation stage of the CFG-DFG to HDL converter in compilation. The MAP compiler contains logical instructions to translate an ASCII.dfg file into the internal formatting table of the CFG-DFG to HDL converter, which represents a procedure compiled in the CFG-DFG to HDL converter "tuple" format. Realize a software module. The translated table can be written to a binary formatted file (.grf file), which is one of the inputs to the CFG-DFG to HDL converter.
One embodiment of the translator may have the following steps: That is, in the first step, the command line can be parsed. The software module has one non-arbitrary argument that is the input file name (ie .dfg file). If an input file argument is specified, the filename is saved and the file is opened. If the input file cannot be opened, the process ends.
The next step in the conversion is reading and parsing the input file. Pars are generated by flex (scanner generator) and bison (parser generator) It can be executed by calling the routine. When the file is parsed, the software module builds an internal data structure to represent the data flow graph. The internal data structure used to represent the graph is the same structure used by the CFG to CFG-DFG converter. The above two primary structures are an array of structures representing procedural variables and an array of structures representing basic code blocks containing the executable part of the compiled procedure.
The software module can then begin assembling the CFG-DFG to HDL converter table. In one embodiment, this step is performed after building the internal structure for the data flow graph. The output filename can be constructed from the input filename, for example by replacing the .dfg suffix with the .grf suffix. It is possible that the input file name will be put from CFG-DFG to the FILENAME table of the HDL converter and the output file name will be put from CFG-DFG to the OUTPUT_FILES table of the HDL converter.
The symbol table can then be translated into the SCALARS table for the CFG-DFG to HDL converter. In one embodiment, this step is performed after initialization of the CFG-DFG to HDL converter table. The formal parameter for the compiled procedure is customarily the first entry in the SCALARS table for the CFG-DFG to HDL converter. A pass is made through the variable array of the data flow graph to extract formal parameters. For each parameter, a flag can be set in the SCALARS table to indicate that this is a formal parameter for the procedure. One of the two other flags may be set in each entry to indicate whether the parameter is a scalar variable or an array. The .dfg memory storage size for a scalar or single array element is its bit length. It can be converted to byte length and inserted into the SCALARS table entry for each parameter. Finally, the name of the parameter is inserted into the SCALARS table entry and the entry complete parameter entry is inserted into the SCALARS table.
After all formal parameters have been processed, a second pass may be made through the data flow graph symbol table and the remaining entries for non-formal parameters for the procedure in question may be processed. This can be done as described for formal parameters, but the SCALARS table entry is set with a local variable flag in place of the flag indicating that the entry is for a formal parameter.
The translation of the data flow graph basic code block follows the translation of the symbol table. One block in the data flow graph is a sequential list of nodes. A node is an operation performed on one or more input operands with one or more outputs. This operation is expressed as an ASCII string opcode. Operands are represented as integers that represent the number of pseudo-registers that contain input or output values. Instead, the input operand can be a constant. In the translation of the data flow graph block, four CFG-DFG to HDL converter Verilog generator tables are constructed. There is a BLOCKS table that is a list of code blocks. The RAW_NODES table is a sequential list of nodes contained within a block. The PRS table is a list of pseudo-registers defined, constants, and pseudo-registers referenced by each node. The CONSTANTS table contains all the constant values used in the compiled procedure.
The translator passes through the block array of data flow graphs, processing one block at a time. Each new block is from CFG-DFG to HDL Get an entry in the converter BLOCKS table. The CFG-DFG to HDL converter BLOCKS table entry contains an index for the first and last CFG-DFG to HDL converter RAW_NODES table entries for the nodes in the blocks described below. If the block is a terminating block, which means that it is a block containing returns from the compiled procedure, then the BLOCKS table entry cannot contain any more information. If the block is a drop-through block, which means it does not end with a conditional branch, then an index on the BLOCKS table entry for the successor block is put into the BLOCKS table entry of the current block. Otherwise the block will end with a conditional branch. In this case, the BLOCKS table index of the two possible successor blocks (the true block of the branch and the false block of the branch) is put into the current block BLOCKS table entry.
RAW_NODES table entries are assembled by the translator passing through each node in the block. Node processing proceeds as follows. Each output pseudo-register is placed in the PRS table. Since this is an output and is therefore defined by the behavior of the node, the PRS table entry is flagged to indicate that it is defined by that node. In addition, the number of pseudo registers is inserted into the PRS table entry, and the index of the parent node RAW_NODES table entry is inserted into each PRS table entry. The input is processed after the output pseudo-register is processed for the node. The input pseudo-register is placed in the PRS table as well as the output, except that the defined flags are not set in the entry. Input to a node, which is a constant, also gets a PRS table entry. When a constant input appears, the CFG-DFG to HDL converter's CONSTANTS table looks for an entry that matches the current constant. If a match is found, the match index is used, otherwise a new CONSTANTS table entry is created and the new entry index is used. A CONSTANTS table entry is inserted into the PRS table entry for a constant, flagged to indicate that it is a constant and not a pseudo-register reference entry, and the parent node's RAW_NODES table index is inserted into it.
When all inputs and outputs for a node are processed, a RAW_NODES table entry is created for the node. The RAW_NODES table entry contains the node's opcode and the PRS table index of the first and last PRS table entries associated with the node.
Once all the nodes have been translated, the translator writes out the CFG-DFG to HDL converter table constructed by translating the data flow graph into the .grf output file, and the process is complete.
<u style="single">Conversion from CFG-DFG to HDL</u> A component of the compilation system for reconfigurable FPGA chips will be described. This compilation system has the ability to compile higher-level languages such as C and Fortran into constituent bitstreams for FPGAs running within a larger execution framework.
This larger execution framework is unique to the design of SRC MAP products. Theoretically, this compilation system is easily adaptable to any such environment.
The component described here is the "converter from CFG-DFG to HDL". The purpose of the CFG-DFG to HDL converter is to convert the output of the "CFG to CFG-DFG converter" to the Verilog language. Verilog is an FPGA chip manufacturer A hardware description language (HDL) that can be used as an input to a standard toolset provided by a person.
The CFG to CFG-DFG converter is another component of the compilation system. The purpose of this CFG-to-DFG converter is to process the opcodes of traditional high-level language compilers to make them more suitable for pipelined execution in MAP / FPGA systems.
The CFG to CFG-DFG converter output effectively consists of a data flow graph (DFG) created from traditional compiler output, which is rather in the form of a control flow graph (CFG). The CFG-DFG to HDL converter does not require the form of DFG to perform its function. It can be easily activated with CFG style input. However, efficient execution in MAP / FPGA requires the form of DFG.
The overall compilation strategy is to use the Verilog language, created by a combination of traditional compilers / CFG to CFG-DFG converters / CFG-DFG to HDL converters, as a guide for user code FPGAs / Derive a way to interconnect predetermined "hardware" modules to achieve an efficient representation for MAP. Therefore, the CFG-DFG to HDL converter does not "synthesize" opcode constructs into the Verilog language. The CFG-DFG to HDL converter simply selects from a set of known predefined hardware modules that match the functionality required by a particular opcode node and provides interconnection between them. .. Creating, maintaining and managing predefined hardware modules is a major component of the overall compilation process and how to manage the relationships between operating code nodes and predefined hardware modules. I will not discuss it here except for the discussion about.
The CFG-DFG to HDL converter manages a set of internal tables that represent different parts of the information needed for processing while performing its task. Ultimately, these tables have enough information to output a Verilog representation of the user code. The input file for the CFG-DFG to HDL converter consists of a simple file format, which contains some information that has already been preprocessed into the CFG-DFG to HDL converter table format.
Note that the CFG-DFG to HDL converter has only a single table format. Table management is simplified by allowing only additions of table entries, not deletions. The entry can be marked as invalid by the flag and is not simply copied to subsequent stages in table expansion. Also, the table entry has a fixed size, which facilitates table search.
The input of the CFG-DFG to HDL converter consists of a command line switch and two types of input files. Command line switches are used to specify the name of the input file and to control the exact details of the processing of the CFG-DFG to HDL converter. For the purposes of this document, the details of the CFG-DFG to HDL converter process controlled by the above switches are not important. Therefore, only the two types of input files mentioned here are important inputs.
The input operation code file is specified by the "-f" switch. Only one opcode file can be entered. This file is a transformer file called dfg2grf mentioned above. It consists of the data flow graph output of the CFG to CFG-DFG converter converted from the CFG-DFG to the HDL converter file format by the data utility.
Opcode node: An opcode node consists of the name of the node and a list of input and output pseudo-registers. Pseudo-registers are simply a number and are used to correlate the flow of data between nodes.
Block information. Shows how the opcode is divided into basic blocks. Basic blocks have the same definition as in traditional compilers. That is, an instruction sequence having a single entry point and a single exit point.
Constant information. Opcode nodes can refer to constant values as inputs instead of pseudo registers.
"Scalar" information. Information about the arguments passed to the compiled subroutine function.
File name information. Used to generate the output filename of the generated Verilog file.
Any number of "CFG-DFG to HDL converter info" files can be entered by using the "-a" switch. The "CFG-DFG to HDL converter info" file consists of "info" file information converted to the CFG-DFG to HDL converter file / table format by the "info2grf" utility. The input to "info2grf" consists of an ASCII text "info" file, intended to be edited and maintained by the developer / user.
The "info" file is a mechanism for the CFG-DFG to HDL converter to associate the opcode node name with the resulting module name output in the Verilog language file. It can also be used to enter information about user-defined opcode / module relationships.
Input CFG-DFG to HDL Hardware Logic Module Information File The information contained in the "info" file contains all the information about the modules used by the compilation system as a whole. Only the information used by the CFG-DFG to HDL converter is described here. The information used by the CFG-DFG to HDL converter is:
The name of the opcode node. The name of the module that corresponds to the opcode node. The latency in the clock for the time between the input and the corresponding output. A list of inputs, their bit widths and their names (in the order in which the pseudo registers appear in the CFG to CFG-DFG converter output flow graph within the opcode node). A list of outputs, their bit widths and their names (in the order in which the pseudo registers appear in the CFG to CFG-DFG converter output flow graph within the opcode node). Names, bit widths and external signal names for hardware-related module I / O connections that are required for execution but do not appear in the flow graph (for example, a given node within a block) Includes enable / reset or CLOCK signals that can be implicit in the context of the resident location of.
CFG-DFG to HDL converter output: The CFG-DFG to HDL converter output consists of ASCII text Verilog language files. The file name is generated from the information carried by the opcode input file. Generally, the file name is the "base name" of a high-level language file suffixed with ".v". For example, a high-level language file named toto.c results in a Verilog language file named toto.v.
The Verilog language file has three "include" statements that reference "PREAMBLE.v", "AMBLE.v", and "POSTAMBLE.v" "OBM_DR_SET.v" and "FR_SET.v". These three include statements separate the generated Verilog code declaration and instance sections in parentheses. These allow the generated Verilog code to be used unchanged in different execution and simulation environments by providing different files for disassembling the include.
CFG-DFG to HDL converter processing flow: Initialization: CFG-DFG to HDL converter initialization processing consists of validation of the command line switch and reading of the input file. The data in the input file is read directly into the internal CFG-DFG to HDL converter table.
One of the main functions is the creation of a large number of internal tables containing information that should be used through the CFG-DFG to HDL converter process. The two most main tables created are the EQUIV_IN and EQUIV_OUT tables. These tables contain the most important pieces of information contained in the info file. The entries in these two tables have a one-to-one correspondence, and by instructing the CFG-DFG to HDL converter, the opcode node with the given name in the input flow graph is in the output Verilog file. Convert to a given instantiation of a predefined hardware module. A MODEULES table is also created, which has module connection details for the modules indexed by EQUIV_OUT.
At initialization, various tables are also created for special purpose processing. This makes it possible to store information for target hardware-specific processing in one area of source code. All of the special purpose processing specific to the target hardware environment can be controlled, for example, by the various flags and table settings generated during this initialization stage. Therefore, it is possible to retarget the processing of the CFG-DFG to HDL converter to another platform, and to do this, first add as much such functionality as needed elsewhere, and then Select the initialization process that will occur to make this possible. In theory, a simple use of command line switches could support different execution environments.
Target hardware-specific processing in such special cases includes the following support: That is, a list of global signals that the module's non-pseudo-register related connections will connect to. Information about memory banks and how memory-related opcode nodes are connected. Information about the "MIRROR" module (this is the SRC mechanism for connecting parameter inputs to compiled subroutines to the FPGA instantiation design and optionally returning updated values). The connection to "code_block_reset" will actually be connected to the "block_reset" signal of the current block of the resident location for a given module.
Process raw input to internal table: Opcode flow graph node input table is N It is read into the ODE table and the name of the operating code node is searched for in the EQUIV_IN table. If found, the corresponding EQUIV_OUT table entry gives a predetermined hardware module MODULE index. An index to this module information is placed in the NODE table.
Verify Bitwidth Consistency Between Opcode Nodes: Here, every opcode node in the NODES table has an assigned hardware module. Now examine all pseudo-registers to see if there is a consistent bit width match for the pseudo-registers that mark the output going to the input of another module in one module. While this work is being performed, a table containing pseudo-register information is built.
Note that the CFG-DFG to HDL converter has no information or need for the "type" of data flowing between modules. Only the bit width is important.
Mark some shift functions for "inline": The NODES table is examined and several modules representing the "shift" operation are processed. The convention of module names indicates whether and how much the shift is due to a certain amount. If the module is such a shift, this fact and the direction of the shift are marked by flags in the NODES table entry. The shift count for the module is also extracted and placed in the field in the NODES table entry. This information is used during the output of the Verilog code generated to "inline", or directly represents the functionality of the module in Verilog code syntax without actually instantiating the module.
Analyze Opcode Node Dependencies: Now look at the NODES table and its associated pseudo-registers to create a node dependency table (NODE_DEPS). This NODE_DEPS table shows which opcode nodes in the NODES table are prerequisites for other opcode nodes (ie, have data flowing directly through pseudo registers).
The opcode node is issued as follows. That is, the NODE_DEPS table is examined and a total count of the number of predecessors for a given NODE entry is created and stored in the NODE table entry. The "clock counter" in each and every NODE table entry is zeroed. A table (PICT_NODES) is created with a list of each and every NODE entry with a leading element count of zero.
Issue Opcode Nodes as follows: The placement of the index of NODES table entries in the PICT_NODES table is a basic indication that an opcode node has been "issued". When a PICT_NODE entry is made, it is made in a table that lists a particular instance of the module (INSTANCES table). Since there can be many instances of the same module type, it is through the INSTANCES table that a unique name is generated for each instance of a given module type.
After the initialization stage described above, the process of issuing the opcode node continues as follows. That is, it examines the NODE_DEPS table for every new entry in the PICT_NODES table and decrements the predecessor element count in the NODE table entry that has the issued opecode node as the predecessor. Adjust the clock count of each NODE table entry affected by the wait time of the module that was the predecessor To. Create an associated INSTANCES table entry for each node newly added to the PICT_NODES table.
Executes "wiring" the output of the predecessor element INSTANCES table entry to the newly created INSTANCES table entry by constructing the information in the WIRING table. The WIRING table has information about the source and destination INSTANCES table indexes and the number of arguments or parameters.
Now, check the NODES table for the opcode node whose predecessor element count is newly zero. Add these entries to the PICT_NODES table and continue as described above. Continue this process until all opcode nodes have been issued.
Output HDL file: By this time, the process has expanded to the point where the output of the HDL file can be started. There is still some work done during this process, including issuing declarations for all "wiring" connections and wiring basic blocks to connect to each other.
First check if every entry in the INSTANCES table has been "inlined". If so, output the appropriate HDL syntax. Otherwise, it prints an instance declaration of the appropriate module, and the connection of the module's I / O pins to various wires, as described in the WIRING table.
<u style="single">Bitstream configuration</u> Work to include the bitstream files created by the Xilinx tools in the compileable C code that is a component of the compilation system and will eventually be integrated into the user's executable. This component takes as input one or two FPGA bitstream files in a binary file that contains only programming data. The result of this compilation stage is C code, one containing two structures, one for each FPGA bitstream. Each structure is a packed representation of the FPGA bitstream contained within the array; a pointer to an internal location about the bitstream; the number of FPGAs this bitstream represents, of the bitstream array. Contains the length; the starting address of the bitstream array; and a pointer to the C version of the MAP routine used for emulation.
The FPGA bitstream file is read into the buffer as 4096 bytes. This buffer is then packed into 64-bit words and written to a bitstream array contained within the appropriate bitstream structure. The final amount read from the bitstream file is padded to be a complete 64-bit word, and these words are also written to the array. After the entire bitstream file is complete, a check is performed to determine if the last word is the last word in the cache line. If not, do more padding to ensure that the last array word completely fills the 4-word cache line in the microprocessor system.
After the translation of the bitstream file is complete, the remaining information and pointers are inserted into the structure representing the first FPGA bitstream. The same process is repeated to read and translate the second FPGA bitstream. Either one of these bitstreams is present, or neither is present at this compilation stage. The bitstream component is for null or existing FPGA bitstream files Address all cases and build an appropriate data structure to reflect this.
<u style="single">Integration into a unified executable</u> As a result of creating an object file that will be executed against different and therefore non-uniform platforms, the next step in the compilation process is to refer to these various components as "unified executable elements". You have to put it together to build things. The unified executable element then includes both machine code that runs on the instruction processor and machine code that runs on the hardware logic processor.
Since the unified executable element resides in the instruction processor's address space during its execution, the unified executable element format must correspond to the application interface accepted by the instruction processor. A method for encapsulating bitstream data into an acceptable format has been developed to allow FPGA bitstreams to exist within a unified executable.
After the compilation process produces the bitstreams, they are read into the C structure, where one C structure is created for each bitstream accessed within this program. These C structures are unique for each bitstream. This is because the C structure is named to match the internal name created during the control flow information file generation stage. By tagging a separate control flow information file with a unique name, the resulting bitstream can also have a unique identifier when constructed in a C structure. If the bitstream configuration is intended to be used in another compilation process, the C structure can be saved as a binary file at this point.
The bitstream C structure can either reside within a unified executable element or reside in a microprocessor where it is made available during execution. Bitstreams created during the compilation process are embedded in the unified execution by default and are therefore in the address space at the time of execution. If there are many bitstream structures configured for a particular executable, only some or none of the bitstream C structures are embedded within the unified executable. obtain. If not all of the bitstream structure resides in the address space of the executable element at the time of execution, the runtime environment reads the appropriate bitstream structure in that the hardware logic configuration for this bitstream is called. There is a need.
After deciding whether to include the bitstream C structure within a unified executable element, it can be created from an object file using the standard linker available on the microprocessor. All object files have a suitable binary interface, so you don't have to do anything special to be able to contain both the microprocessor machine code and the hardware logic machine code.
As shown in the figure below, a bitstream representing the hardware logic configuration to be executed at the time of execution can be in one of the two locations shown in Figure 30.
<u style="single">Runtime environment</u> The runtime environment in which the unified binaries are executed can be extended beyond the runtime environment in which the instruction processor binaries are executed. The MAP library may include support routines for emulating and simulating data flow graphs. From the user's point of view, the runtime environment has three categories of routines. That is, memory management, MAP resource management, and MAP execution.
Memory management: Due to hardware limitations, blocks of memory transferred between the instruction processor environment and the reconfigurable processor environment may need to start at the cache boundary. Two functions are provided to assist in cache alignment in the presence of such hardware restrictions.
The first function, addr32 (or IADDR32 for Fortran instead), is a logic for accepting arbitrary memory addresses and returning the address of the first cache alignment word in memory that is greater than or equal to the input address argument. A software module that contains instructions. The array to be aligned can be declared padded at the beginning and end of the array approaching the cache line's memory. A pointer to the cache alignment array can be declared. The padded array can be passed as an argument to addr32 and a pointer can be set to the result of this function. References to the aligned array can be made through pointers.
The second function, cache alignment allocation (or instead CACHE_ALIGNED_ALLOCATE for Fortran), is the logic for accepting a single integer argument and generating a pointer to the allocated space starting at the cache alignment boundary. A software module that contains instructions. The argument can be the size of the memory allocation request in bytes. This function can be used to declare a pointer. In addition, the user can call this function to allocate the space needed for the array and set a pointer to the result of this function. References to this array can be made through pointers.
MAP resource management: You can make dynamic changes to the runtime environment and add or remove reconfigurable hardware resources to your job to do this. No MAP resources are required while running on the instruction processor. Reconfigurable hardware resources must be allocated to the job prior to executing the MAP procedure. This may be done at the start of the job or at any time prior to running the MAP. After executing a MAP procedure, executing a unified binary may not require MAP resources for some time, so it may be desirable to free one or more MAP processors until they are needed again. .. Similarly, it may be necessary to add additional MAP resources prior to executing another MAP procedure. Two functions are provided to manage MAP resources.
The first function, map_allocate (MAP_ALLOCATE (N, STAT) for Fortran), is a software module that receives a single input argument that indicates the number of MAP resources to be allocated. A result value of zero (STAT in Fortran) indicates a successful allocation. A non-zero result (STAT) indicates that the request was not successfully satisfied.
The second function, map_free (MAP_FREE (N, STAT) for Fortran), is a software module with a single input argument that indicates the number of MAP resources that should be freed from the job. A return value of zero (STAT for Fortran) indicates that the resource has been successfully released from the job. A non-zero return value (STAT) indicates that an error occurred when trying to free the resource.
MAP resources are identified by the number of MAP IDs. The first MAP assigned to the job has a MAP ID of 0. If n resources are allocated to the job at any given time, they will be identified as 0,1, ... n-1. The MAP resource with the highest number of MAP IDs is first deallocated. For example, 7 MAP resources If assigned to a job, these are identified by the integers 0-6. If three are unassigned, MAP IDs 0-3 will remain assigned to the job. And if two are assigned, the most recently assigned MAP IDs are 4 and 5.
MAP execution: The details of configuring reconfigurable hardware with logic bitstreams and the details of transferring control to reconfigurable hardware and to the instruction processor are hidden from the user in the runtime environment. The MAP proxy code generated by the HLL converter performs these tasks. The routine MAP_Execute called by this proxy code is discussed here.
MAP_Execute and its various runtime entry points perform the following functions: First, the MAP proxy code indicates which MAP resource should be used to execute the MAP procedure. MAP_Execute locks the resource to prevent other execution threads (or user jobs) from accessing the resource during the execution of the MAP procedure. Check if the resource to be used is properly configured in user logic for the MAP procedure to be executed. If not, locate the appropriate logic bitstream and configure the MAP resource. Execution on reconfigurable hardware begins. MAP_Execute waits for execution to complete, unlocks the resource, and then signals completion to the instruction processor or transfers control back.
<u style="single">Embroidery in runtime environment</u> Emulation is an extremely useful debugging tool as well as a tool that enables performance profiling at the data flow graph level. Emulation capabilities are built into the run-time environment of executable elements built by the MAP compilation system.
The runtime library supports three separate environments. That is, 1) execution on MAP hardware, 2) execution on emulated MAP and data flow graph emulation, 3) execution on emulated MAP and simulated user logic. The selection of a specific environment is made at runtime based on the environment variable settings.
<maths num="31"><img file="JP2010146577A_D0031.tif" /></maths>
When emulation mode is used, additional environment variables determine how the logic for MAP is handled.
<maths num="32"><img file="JP2010146577A_D0032.tif" /></maths>
When MAPHW = EMUIII is set, the runtime library routine that manages MAP calls the MAP emulate routine instead of the MAP hardware support routine. Each and every executable element can be executed in hardware or emulated. The MAP emulator replaces the MAP control processor and its resources. That is, communication links, onboard memory, data registers, and flag registers, which provide software-emulated versions of these resources. Figures 31 and 32 show the structure of the MAP emulator.
The MAP emulator runs as a separate pthread from the instruction processor application code and processes. The emulator thread is started when the runtime routine detects that emulation mode has been selected instead of MAP hardware mode. Just as MAP hardware runs asynchronously to the instruction processor, so does the emulator.
The function of the MAP emulator is to emulate communication and control links to instruction processor-based applications, providing an interface to user logic that runs in dataflow emulation or as Verilog simulations.
Data flow emulation is also performed as a separate p-thread that interfaces to the MAP emulator through interface routines used to read or write flag registers, data registers and onboard memory.
If the user logic generated by the MAP compiler is created as Verilog, the user logic can be executed together with the MAP emulator using the Verilog simulator. Verilog simulation is performed as a separate executable element that communicates with the MAP emulator through a shared memory segment. In this case, the simulator provides onboard memory, data registers and flag registers, while the MAP emulator provides a MAP control processor.
Figure 31 shows the MAP emulator with DFG emulation, and Figure 32 shows the Verilog simulator and the MAP emulator.
In another embodiment, the data flow graph emulation can be done as follows. That is, in the CFG to CFG-DFG converter step of the MAP compiler, two files, a data flow graph (text format) of the user's subroutine and an emulated logic file, are created. The data flow graph file can have two purposes. That is, it can be used by a CFG-DFG to HDL converter to generate a Verilog translation of a subroutine, and even when emulated is used to validate the source code or collect performance data. Can be read by rate logic routines.
In one embodiment, the data flow graph can include a node and the indicated edge, where the node can be a functional unit, where the edge takes the output value from one node to the input of another node. A data connection to carry. It may be possible to run a data flow simulator using a data flow graph. Simulation can be useful for: That is, it has functions such as 1) validating both the source code and its translation into the data flow format, 2) printing trace information for debugging, and 3) collecting performance estimates.
In one embodiment, the data simulation can be performed in a "token driven" simulation mode, which is a loosely coupled asynchronous simulation where sequencing can be useful but time is not considered. It can be a thing. In this mode, there is no notion that things happen "at the same time". Any node can be executed at any time as long as its input has a value available. Data values are called "tokens", and tokens can be queued at the node's input port. In another embodiment, the "clock accurate" simulation considers the system clock and the execution latency of the functional unit. In this case, the word "simultaneous" has a meaning.
FIG. 33 shows a flowchart of an embodiment of a token-driven data flow simulator. In one example of an embodiment, the routine dfg_simulate may be called from the emulate logic file to start the simulator. In this example, the simulator can first read the DFG file and build an internal representation. Then the simulation is started and starts at block zero (by definition, the entrance block). Each time you simulate a code block, it first clears the queue and node state, and then triggers the execution of the block by sending a single token to the INITIATE node at the top of the block. Then loop to find a node that can fire. In this example, the "firing rule" for most nodes is that a node can fire if each one of its inputs has an available token. "Ignition" consists of taking tokens from each input queue and using these values to perform a particular function of the node. This feature yields one or more output values, which are sent out as tokens at the node's output. When the output extends to a large number of nodes, value tokens can be delivered to each of the queues of the target node.
FIG. 34 shows an example of a DFG fragment according to an embodiment, where the fragment is stepwise executed with each iteration of the simulator's internal loop. At the start, three values are waiting in the input queue. The two nodes at the top are marked as fireable. They consume one token from each queue and send the resulting token to the queue of nodes supplied by its output. Note that at t = 1, the node at the bottom has a value in the input to the right of it, but has no value in the input to the left of it, so it cannot fire. At t = 2, there are two tokens in the right input queue at the bottom node. After 5 passes of the simulator's inner loop, this fragment no longer has any value that can be processed.
In general, data flow graphs have many correct firing sequences. In the above example, firing the upper node three times and then firing any of the other nodes would have been equally effective. The fact that the tokens arrive in the queue in order ensures that the corresponding values in the output of each node "match up" correctly. The node input queue in the simulator is designed to be extended as needed. That is, whenever a value is sent to the queue and the queue is full, the size of the queue is increased to accommodate new values. In the processing sequence shown in the flowchart, each sweep across the node fires only once, even if the node has more values that could have been processed, but this processing order is the required queue length. Can be selected to minimize.
The various node firing sequences that can occur during an asynchronous dataflow simulation are that the dataflow node is "purely functional", that is, the output token of each node is the input token fetched to compute the output. Produce equivalent results when they can depend. Not all nodes are purely functional. Some nodes are in "state" That is, they may have some memory of what they have done before. Such a node can be called "having a state". Some nodes may interact with the surrounding hardware, i.e. read and write to flag registers, data registers or onboard memory. The data flow simulator can execute these nodes by making calls to the appropriate MAP emulator functions.
In another embodiment, the data flow simulation can be performed in a mode that more closely mimics what happens to reconfigurable hardware. The clock accuracy simulation assumes that the system clock exists, and the functional units are executed synchronously and coordinated by the clock. In hardware, each functional unit may perform operations in every clock cycle, with or without valid data at its input. The data flow graph and the logic circuit generated from the graph can be generated so that the "junk" data from the functional unit is ignored.
Clock accuracy simulations can be extremely wasteful of computation time if each node in the graph operates in a mode of computation in each and every clock cycle. In one embodiment, the simulation is performed in a mode in which a data flow node performs valid calculations and attaches a "timestamp" to the token to capture a synchronous aspect of the system, similar to a token-driven simulation. Is possible. In this simulation, the tokens are queued at the input, and the firing and execution of the node can match up the values in the queue by its timestamp.
Clock accuracy simulations can be more complex than asynchronous token-driven simulations, but can more faithfully reflect the behavior and synchronization that occurs in reconfigurable hardware. Therefore, the clock accuracy simulation has the following advantages. That is, 1) In clock accuracy simulation, an improperly placed delay node generates an error instruction. On the other hand, these appear to be running correctly in asynchronous simulations. 2) Since the clock accuracy simulation simulates the system clock, it is possible to give an accurate predicted execution time. 3) When reading and writing to the same memory bank occurs in an asynchronous simulation, the order in which this occurs may not be specified, so it may not occur in the same order that would occur on reconfigurable hardware. However, clock accuracy simulations can provide a guaranteed execution order that matches what happens in hardware.
In another embodiment, the problem related to the simulation of the data flow graph generated by the MAP compiler is addressed. This includes:
Problem of a node with a state: A node with a state has one or more internal fields in its node structure that are used to track some aspect of what happened in the past. An example of a node with a state is an accumulator that sums the values of the token stream at its input. Accumulator nodes need a place in their node structure to hold the current value of the total to be accumulated. Other node types may require more complex states. The data flow node structure has fields of type "NodeState". This is defined in the following struct.
<maths num="33"><img file="JP2010146577A_D0033.tif" /></maths>
In one embodiment, whenever a code block is inserted, the "initialized" field of the node with that state is set to "false". A node execution routine for a node with a state can examine this field and perform initialization if false. This is typically done by allocating an appropriate data structure for the state of the node type and setting a "state" pointer to point to it. Also, the fields of this structure are set to the appropriate starting state. Then the "initialized" field is set to "true", thus preventing subsequent firing at the node from attempting to reinitialize.
Ignition Rules and Execution Rules: In one embodiment, each node type in the data flow graph has two functions associated with it: "Ignition Rules" and "Execution Rules". The firing rules for most nodes can be simple. That is, the rule is that a node can fire when any of its inputs can have a data value. There can be some exceptions to this in the case of loop control nodes that manage the pipelined behavior for loop data flow graphs. An execution rule for a node is a specification of how its input value is used to generate an output value, that is, an execution rule can be a function of a node. When the simulator reads a data flow graph file and builds an internal node structure, each node has two function pointers that can be used to point to firing and executing functions for this node.
User Macros: In one embodiment, the MAP compiler allows users to reference their own hardware logical units when compiling code into reconfigurable hardware. To perform a dataflow simulation of the compiled code, the user gives an execution function for each referenced unit. This is the "execution rule" for this node. For user macros, this follows "normal" firing rules, i.e. it is assumed that each node can fire when all its outputs have a value. Dataflow simulation routines for user macros are read from the "info" file and then handled internally in the same way that SRC embedded macros are treated. That is, the user's simulation function can be compiled and the associated data flow node is given a pointer to this function.
Although the invention has been described and illustrated with some degree of specificity, this disclosure is merely an example and one of ordinary skill in the art will not deviate from the previously claimed meaning and scope of the invention. It is understood that it is possible to rely on numerous changes in the combination and placement of.
The terms "prepared," "prepared," "included," and "included," as used in this specification and the claims herein, identify the presence of the feature, completeness, component or step described. However, it does not preclude the existence or addition of one or more other features, perfections, components, steps or groups.
100 hardware instruction processor system, 102 HLL source code file, 104 converter, 106 HLL converter, 108 converter, 110 districts Differentiation part, 112 converter, 114 converter, 116 linker.
71 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34 Sheet 35 Sheet 36 Sheet 37 Sheet 38 Sheet 39 Sheet 40 Sheet 41 Sheet 42 Sheet 43 Sheet 44 Sheet 45 Sheet 46 Sheet 47 Sheet 48 Sheet 49 Sheet 50 Sheet 51 Sheet 52 Sheet 53 Sheet 54 Sheet 55 Sheet 56 Sheet 57 Sheet 58 Sheet 59 Sheet 60 Sheet 61 Sheet 62 Sheet 63 Sheet 64 Sheet 65 Sheet 66 Sheet 67 Sheet 68 Sheet 69 Sheet 70 Sheet 71
Every citation, both ways
| Document | Relation | Office | Cited during |
|---|---|---|---|
| US9235672B2 | Cited by | United States of America | Applicant |
| JP2002508102A | Cites | Japan | Examiner |
| JPH10320214A | Cites | Japan | Examiner |
| JPH11250112A | Cites | Japan | Examiner |
24 members in 6 offices
Priority claims5
| Document | Office | Kind | Date |
|---|---|---|---|
| 10285299 | United States of America | – | |
| 28529902 | United States of America | A | |
| 28529902 | United States of America | A | |
| 2002285299 | – | – | – |
| US20020285299 | – | – | – |
Members24
| Document | Office | Kind | |
|---|---|---|---|
| US2004088673A1 | United States of America | A1 | |
| US2004088685A1 | United States of America | A1 | |
| CA2502892A1 | Canada | A1 | |
| WO2004042503A2 | World Intellectual Property Organization (WIPO) | A2 | |
| WO2004042929A2 | World Intellectual Property Organization (WIPO) | A2 | |
| AU2003275340A1 | Australia | A1 | |
| AU2003284288A1 | Australia | A1 | |
| WO2004042929A3 | World Intellectual Property Organization (WIPO) | A3 | |
| CA2498866A1 | Canada | A1 | |
| EP1556758A2 | European Patent Office (EPO) | A2 | |
| EP1573461A2 | European Patent Office (EPO) | A2 | |
| WO2004042503A3 | World Intellectual Property Organization (WIPO) | A3 | |
| US6983456B2 | United States of America | B2 | |
| JP2006505055A | Japan | A | |
| US2006041872A1 | United States of America | A1 | |
| JP2006510125A | Japan | A | |
| EP1573461A4 | European Patent Office (EPO) | A4 | |
| US7134120B2 | United States of America | B2 | |
| EP1556758A4 | European Patent Office (EPO) | A4 | |
| JP4330582B2 | Japan | B2 | |
| US7703085B2 | United States of America | B2 | |
| JP4482454B2 | Japan | B2 | |
| JP2010146577AThis record | Japan | A | |
| JP5036801B2 | Japan | B2 |
19 legal events, as the office reported them to INPADOC
Over the term
Point at a mark for the eventEvents
| Event | Code | |
|---|---|---|
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Written notification of registration of transferJAPANESE INTERMEDIATE CODE: R350R350 | R350 | |
| Request for change of ownership or part of ownershipJAPANESE INTERMEDIATE CODE: R313113S111 | S111 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Receipt of annual feesJAPANESE INTERMEDIATE CODE: R250R250 | R250 | |
| Written notification of registration of transferJAPANESE INTERMEDIATE CODE: R350R350 | R350 | |
| Request for change of ownership or part of ownershipJAPANESE INTERMEDIATE CODE: R313111S111 | S111 | |
| Renewal fee payment (event date is renewal date of database)FPAY | FPAY | |
| Certificate of patent or registration of utility modelJAPANESE INTERMEDIATE CODE: R150R150 | R150 | |
| Certificate of patent or registration of utility modelJAPANESE INTERMEDIATE CODE: R150R150 | R150 | |
| First payment of annual fees (during grant procedure)JAPANESE INTERMEDIATE CODE: A61A61 | A61 | |
| Written decision to grant a patent or to grant a registration (utility model)JAPANESE INTERMEDIATE CODE: A01A01 | A01 | |
| Written decision to grant a patent or to grant a registration (utility model)JAPANESE INTERMEDIATE CODE: A01A01 | A01 | |
| Decision of grant or rejection writtenTRDD | TRDD | |
| Written amendmentJAPANESE INTERMEDIATE CODE: A523A521 | A521 | |
| Notification of reasons for refusalJAPANESE INTERMEDIATE CODE: A131A131 | A131 |
Numbers
- Publication
- 2010146577
- Publication, DOCDB
- 2010146577
- Publication, EPODOC
- JP2010146577
- Application
- 297725
- Application, DOCDB
- 2009297725
- Application, EPODOC
- JP20090297725
Titles2
- Japanese
- 高級プログラミング言語におけるプログラムをハイブリッド計算プラットフォームの統一された実行可能要素に変換するためのプロセス
- English
- The process of transforming a program in a high-level programming language into a unified executable element of a hybrid computing platform
Classification
- CPC, 2
- G06F8/447
- G06F30/30
- IPC, 2
- G06F17 50
- G06F9 45