High Level Synthesis of Data Flow Graphs Using Integer Linear Programming

This paper seeks to investigate integer linear programming (ILP) methodologies for power optimization during high level synthesis (HLS). There are three basic steps in high level synthesis. They are scheduling, binding and allocation. Here power aware scheduling and binding are considered. Integer linear programming has been widely investigated for solving scheduling and binding problems. The major issues encountered in ILP like scalability and use of heuristics to enhance the computational efficiency will be addressed. To devise the ILP, constraints are specified by means of matrices that are consequential from the data flow graph (DFG) and switching activity information. A data flow graph is given as the input. From that DFG, two matrices are generated based on the intra and inter iteration precedence of the nodes. Another input matrix is also derived from the data flow graph based on the switching activity information. Constraints related to time steps at which nodes in the DFG are to be executed are specified by means of inequalities. All input matrices required for the ILP Formulation are generated using C with the data flow graph as input. FICO Xpress optimization suite is used for executing the ILP.