Efficient Directed Acyclic Graph Pattern Matching To Enable Code Partitioning and Execution On Heterogeneous Processor Cores

摘要

Methods, devices, and systems for automatically determining how an application program may be partitioned and offloaded for execution by a general purpose applications processor and an auxiliary processor (e.g., a DSP, GPU, etc.) within a mobile device. The mobile device may determine the portions of the application code that are best suited for execution on the auxiliary processor based on pattern-matching of directed acyclic graphs (DAGS). In particular, the mobile device may identify one or more patterns in the code, particularly in a data flow graph of the code, comparing each identified code pattern to predefined graph patterns known to have a certain benefit when executed on the auxiliary processor (e.g., a DSP). The mobile device may determine the costs and/or benefits of executing the potions of code on the auxiliary processor, and may offload portions that have low costs and/or high benefits related to the auxiliary processor.

主权项

1. A method for a computing device to offload portions of an input code from a first processor for execution on an auxiliary processor when the portions are automatically determined to be well-suited for the auxiliary processor, comprising:
generating a graph-based intermediate representation of the input code, wherein the graph-based intermediate representation of the input code contains directed acyclic graphs (DAGs); comparing each node or combination of nodes to one or more patterns in a predefined grammar, wherein each pattern is a DAG pattern and is associated with a cost metric; identifying a set of patterns that partially cover the graph-based intermediate representation of the input code based on the comparisons of the each node or the combination of nodes to the one or more patterns in the predefined grammar; and offloading from the first processor to the auxiliary processor segments of the input code associated with a combination of grammar patterns of the identified set of patterns having a best cumulative effect.