Software systems and methods for advanced output-affecting linear pathways
OwnerKevin D. HOWARDinventor
Life of this patent
Estimating the term…
Abstract
Unlike conventional or otherwise known decomposition methods like standard functional decomposition, time-affecting linear pathway (TALP) decomposition, or output-affecting linear pathways (OALPs) from the decomposition of TALPs, advanced output-affecting linear pathway (A-OALP) decomposition from algorithms separate the output variables of each execution pathway such that there is only one output variable per A-OALP, converting an algorithm into a set of process groups. A-OALPs extend parallelization by combining task-like parallelism with dynamic loop parallelism. The lightweight nature of A-OALPs allows for persistent thread and code management.
Claims20
A method for optimization of software or one or more algorithms, comprising:
- receiving the software or the one or more algorithms;
- decomposing the software or the one or more algorithms into one or more analyzable advanced output-affecting linear pathways (A-OALPs);
- executing the one or more analyzable A-OALPs;
- detecting loop boundaries at runtime based on input path selection variables and temporal conditions;
- expanding each loop of one or more loops into multiple execution blocks, wherein the multiple execution blocks include iteration limits determined by input data;
- distributing the multiple execution blocks across multiple persistent threads managed by an A-OALP controller to achieve task-level parallelism and loop-level parallelism;
- adaptively modifying loop-unrolling iteration count per thread and thread allocation based on runtime feedback of at least one of energy use, processing time, and memory allocation;
- combining inner loop and outer loop iterations into a product of hierarchical loop iteration counts;
- managing application of combined loop iterations to allow for combined iteration distribution applied across multiple processing elements;
- removing or eliminating one or more loop control conditions based on the combined iteration distribution applied across the multiple processing elements to allow for removal of hierarchical loops;
- and
- executing one or more code blocks having the removed hierarchical loops.
A system for optimization of software or one or more algorithms, comprising:
- a memory;
- and
- a processor operatively coupled with the memory, wherein the processor is configured to execute program code to:
- receive the software or the one or more algorithms;
- decompose the software or the one or more algorithms into one or more analyzable advanced output-affecting linear pathways (A-OALPs);
- execute the one or more analyzable A-OALPs;
- detect loop boundaries at runtime based on input path selection variables and temporal conditions;
- expand each loop of one or more loops into multiple execution blocks, wherein the multiple execution blocks include iteration limits determined by input data;
- distribute the multiple execution blocks across multiple persistent threads managed by an A-OALP controller to achieve task-level parallelism and loop-level parallelism;
- modify, adaptively, loop-unrolling iteration count per thread and thread allocation based on runtime feedback of at least one of energy use, processing time, and memory allocation;
- combine inner loop and outer loop iterations into a product of hierarchical loop iteration counts;
- manage application of combined loop iterations to allow for combined iteration distribution applied across multiple processing elements;
- remove or eliminate one or more loop control conditions based on the combined iteration distribution applied across the multiple processing elements to allow for removal of hierarchical loops;
- and
- execute one or more code blocks having the removed hierarchical loops.
Dependencies are inferred from the claim text.