Methods for reducing memory space in sequential operations using directed acyclic graphs

摘要

Various disclosed embodiments are directed to methods and systems for reducing memory space in sequential computer-implemented operations. The method includes generating a directed acyclic graph (DAG) having a plurality of vertices and directed edges, wherein each edge connects a predecessor vertex to a successor vertex. Each vertex represents one of the computer-implemented operations and each directed edge represents output data generated by the operations. The method includes merging one of the predecessor vertex with one of the successor vertex by combining the operations of the predecessor vertex and the successor vertex if the predecessor and successor vertices are connected by a directed edge and there is only one directed edge originating from the predecessor vertex. The merger of the predecessor and the successor vertices reduces the number of directed edges in the DAG, resulting in a reduction of intermediate buffer memory required to store the output data.

主权项

1. A method for reducing memory space in sequential computer-implemented operations, comprising:
(a) generating a directed acyclic graph (DAG) having a plurality of vertices and directed edges, each edge connecting a predecessor vertex to a successor vertex, each vertex representing one of the computer-implemented operations and each directed edge representing output data generated by the operations, and wherein the output data from the predecessor vertices are received as input data by the successor vertices; (b) merging one of the predecessor vertex with one of the successor vertex by combining the operations of the predecessor vertex and the successor vertex into an operation in a merged vertex if the predecessor and successor vertices are connected by a directed edge, and there is only one directed edge out of the predecessor vertex; (c) generating a modified DAG by replacing the predecessor and successor vertices with the merged vertex, wherein the merger of the predecessor and the successor vertices reduces the number of directed edges in the DAG; (d) repeating steps (a) through (c) until there are no predecessor and successor vertices that can be merged; and (e) allocating memory space for the output data represented by the directed edges; and (f) storing the output data in the allocated memory space.