# US 10,372,429 B2 · Method and system for generating accelerator program > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,429 B2 - Document ID: US10372429B2 - Status: Granted - Kind: B2 - Application number: 15/988,225 - Filed: 2018-05-24 - Published: 2018-09-20 - Granted: 2019-08-06 - Earliest claimed: 2015-11-25 - Assignees: Huawei Technologies Co., Ltd. - Applicants: Huawei Technologies Co.,Ltd. - Inventors: Tao Wang; Fenglong Song; Jun Yao - Web page: https://patentgrep.com/patent/US10372429B2 ## CPC - G06F 8/433: {Dependency analysis; Data or control flow analysis} - G06F 8/42: {Syntactic analysis} - G06F 9/4498: {Finite state machines} - G06F 8/4452: {Software pipelining} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for generating an accelerator program is disclosed, to help increase utilization of an accelerator and increase program development efficiency. In some feasible implementations of the present invention, the method includes: obtaining an accelerator program description that is based on a state machine, where the accelerator program description includes multiple state machines separately configured to implement an application program, and the multiple state machines form a pipeline according to a data dependency in a directed acyclic graph DAG corresponding to the application program; and performing state machine splicing on the state machines in the accelerator program description by using an accelerator compilation tool, to generate an accelerator program. ## Claims ### Claim 1 A method for generating an accelerator program, comprising: obtaining, by a computer device, an accelerator program description, wherein the accelerator program description comprises multiple state machines configured to implement an application program, and the multiple state machines form a pipeline according to a data dependency in a directed acyclic graph (DAG) corresponding to the application program; and Performing state machine splicing on the multiple state machines in the accelerator program description by using an accelerator compilation tool of the computer device, to generate an accelerator program. ### Claim 2 (depends on 1) The method according to claim 1, wherein the performing state machine splicing on the state machines in the accelerator program description by using the accelerator compilation tool of the computer device, to generate the accelerator program comprises: establishing an intermediate expression of each state machine in the accelerator program description, and splicing intermediate expressions that have a same structure and that are of different state machines, to generate a combined state machine and obtain the accelerator program. ### Claim 3 (depends on 2) The method according to claim 2, wherein the establishing the intermediate expression of each state machine in the accelerator program description comprises: Analyzing a basic structure of each state machine in the accelerator program description by using the accelerator program description as basic input and based on an accelerator microarchitecture characteristic, and converting each state machine into the intermediate expression, wherein the intermediate expression comprises one or more of a sequential block, a cyclical block, or a repetitive block. ### Claim 4 (depends on 3) The method according to claim 3, wherein the splicing intermediate expressions that have the same structure and that are of different state machines comprises: Splicing sequential blocks in the different state machines, splicing cyclical blocks in the different state machines, or splicing repetitive blocks in the different state machines. ### Claim 5 (depends on 3) The method according to claim 3, wherein the splicing intermediate expressions that have the same structure and that are of different state machines comprises: determining, according to a timing constraint relationship between the different state machines, intermediate expressions that are of the different state machines and that have the same structure and that can be concurrently executed; splicing the intermediate expressions so as to concurrently execute instructions in the different state machines. ### Claim 6 (depends on 1) The method according to claim 1, further comprising: Performing program correctness detection on the generated accelerator program. ### Claim 7 (depends on 6) The method according to claim 6, wherein the performing program correctness detection on the generated accelerator program comprises: performing program correctness detection on the accelerator program by detecting whether the generated accelerator program satisfies a constraint of an accelerator instruction set. ### Claim 8 (depends on 7) The method according to claim 7, wherein the performing correctness detection on the accelerator program by detecting whether the generated accelerator program satisfies the constraint of the accelerator instruction set comprises: performing syntax structure detection, resource conflict detection, and data correlation detection on the generated accelerator program. ### Claim 9 (depends on 1) The method according to claim 1, wherein the obtaining an accelerator program description comprises: describing a data flow diagram of the application program by using the DAG, creating a state machine of each node in the DAG by using the accelerator instruction set, and establishing the pipeline between the state machines according to a time delay indicated by a side in the DAG, to obtain the accelerator program description. ### Claim 10 (depends on 9) The method according to claim 9, wherein each node in the DAG represents a functional component of a processor or an accelerator that executes the application program. ### Claim 11 A system for generating an accelerator program, comprising: at least one processor; and a non-transitory computer-readable storage medium coupled to the at least one processor and storing programming instructions for execution by the at least one processor, wherein the programming instructions instruct the at least one processor to: obtain an accelerator program description, wherein the accelerator program description comprises multiple state machines configured to implement an application program, and the multiple state machines form a pipeline according to a data dependency in a directed acyclic graph DAG corresponding to the application program; and perform state machine splicing on the multiple state machines in the accelerator program description by using an accelerator compilation tool, to generate an accelerator program. ### Claim 12 (depends on 11) The system according to claim 11, wherein the programming instructions instruct the at least one processor to: establish an intermediate expression of each state machine in the accelerator program description, and splice intermediate expressions that have a same structure and that are of different state machines, to generate a combined state machine and obtain the accelerator program. ### Claim 13 (depends on 12) The system according to claim 12, wherein the programming instructions instruct the at least one processor to: analyze a basic structure of each state machine in the accelerator program description by using the accelerator program description as basic input and based on an accelerator microarchitecture characteristic, and convert each state machine into the intermediate expression, wherein the intermediate expression comprises one or more of a sequential block, a cyclical block, or a repetitive block. ### Claim 14 (depends on 13) The system according to claim 13, wherein the programming instructions instruct the at least one processor to: splice sequential blocks in the different state machines, splice cyclical blocks in the different state machines, or splice repetitive blocks in the different state machines. ### Claim 15 (depends on 14) The system according to claim 14, wherein the programming instructions instruct the at least one processor to: determine, according to a timing constraint relationship between the different state machines, intermediate expressions that are of the different state machines and that have the same structure and that can be concurrently executed; splice, the intermediate expressions so as to concurrently execute instructions in the different state machines. ### Claim 16 (depends on 11) The system according to claim 11, wherein the programming instructions instruct the at least one processor to: perform program correctness detection on the generated accelerator program. ### Claim 17 (depends on 16) The system according to claim 16, wherein the programming instructions instruct the at least one processor to: perform correctness detection on the accelerator program by detecting whether the generated accelerator program satisfies a constraint of an accelerator instruction set. ### Claim 18 (depends on 17) The system according to claim 17, wherein the programming instructions instruct the at least one processor to: perform syntax structure detection, resource conflict detection, and data correlation detection on the generated accelerator program. ### Claim 19 (depends on 11) The system according to claim 11, further comprising: the programming instructions instruct the at least one processor to: describe a data flow diagram of the application program by using the DAG, create a state machine of each node in the DAG by using the accelerator instruction set, and establish the pipeline between the state machines according to a time delay indicated by a side in the DAG, to obtain the accelerator program description. ### Claim 20 (depends on 19) The system according to claim 19, wherein each node in the DAG represents a functional component of a processor or an accelerator that executes the application program. ### Claim 21 (depends on 1) A computer device, wherein the computer device comprises a processor and a memory, wherein the memory is configured to store a program, and when the computer device runs, the processor executes the program stored in the memory, so that the computer device performs the method for generating an accelerator program according to claim 1.