Compiler optimization of dataflow applications using mixed integer equations

Abstract

A method comprises a compiler generating a MI (mixed integer) model to determine mapping decisions to map a dataflow application to hardware of a computing system to execute the application. The MI model comprises MI equations to solve by an MI solver. The MI equations include equations of an objective function corresponding to an optimization objective. The MI equations can comprise decision variables and equations and constraint variables and equations. The compiler outputs the MI model to the MI solver and invokes the MI solver to compute an MI solution comprising solutions to equations among the equations included in the MI model. The compiler receives the MI solution and generates a globally optimized mapping decision based on the MI solution. The MI solver can comprise a commercial program to solve MI linear equations. A computer program product and a computing system can implement the method.

What is claimed is: 
     
         1 . A method, the method comprising:
 generating, by a compiler included in a first computing system, a MI (mixed integer) model to determine mapping decisions to map a dataflow application to hardware resources of a second computing system for the second computing system to execute the dataflow application, the MI model comprising MI equations to solve by an MI solver, the MI equations including equations of an objective function corresponding to an optimization objective;   outputting, by the compiler, the MI model to the MI solver;   invoking, by the compiler, the MI solver to compute an MI solution comprising solutions to equations among the equations included in the MI model;   receiving, by the compiler, the MI solution; and,   generating, by the compiler, a globally optimized mapping decision based on the MI solution.   
     
     
         2 . The method of  claim 1 , wherein the objective function is expressed as a computation comprising an MI linear equation. 
     
     
         3 . The method of  claim 1 , wherein equations among the MI equations comprise MI decision variables and MI decision equations. 
     
     
         4 . The method of  claim 1 , wherein equations among the MI equations comprise MI constraint variables and MI constraint equations to include in the MI model. 
     
     
         5 . The method of  claim 4 , wherein the MI constraint equations comprise equations selected from a group consisting of: node equations, bounds equations, data dependency equations, hardware usage equations; transfer size equations, and latency equations. 
     
     
         6 . The method of  claim 1 , wherein the optimization objective is selected from a group consisting of: maximizing a processing throughput to execute the dataflow application by the second computing system; maximizing a number of processors to execute the dataflow application by the second computing system; maximizing a number of parallel operations to execute the dataflow application by the second computing system; minimizing a latency to execute the dataflow application by the second computing system; minimizing an amount of memory to execute the dataflow application by the second computing system; and, minimizing a number of data transfers to execute the dataflow application by the second computing system. 
     
     
         7 . The method of  claim 1 , wherein the second computing system comprises a coarse grain reconfigurable system. 
     
     
         8 . The method of  claim 1 , wherein the method further comprises generating, by the compiler, a human readable representation of the globally optimized mapping decision. 
     
     
         9 . The method of  claim 1 , wherein the MI Solver comprises a commercially available MI Solver. 
     
     
         10 . A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the program instructions are executable by at least one processor of a first computing system to cause the at least one processor to:
 generate a MI (mixed integer) model to determine mapping decisions to map a dataflow application to hardware resources of a computing system to execute the dataflow application, the MI model comprising MI equations to solve by an MI solver, the MI equations including equations of an objective function corresponding to an optimization objective;   output the MI model to the MI solver;   invoke the MI solver to compute an MI solution comprising solutions to equations among the equations included in the MI model;   receive the MI solution; and,   generate a globally optimized mapping decision based on the MI solution.   
     
     
         11 . The computer program product of  claim 10 , wherein the program instructions are executable by the at least one processor to further cause the at least one processor to generate a human readable representation of the globally optimized mapping decision. 
     
     
         12 . A first computing system comprising:
 a graph corresponding to a dataflow application;   a hardware specification describing hardware of a second computing system for executing the dataflow application;   a first processor and a second processor;   an MI (Mixed Integer) Solver; and,   a compiler, wherein the compiler is configured to execute on the first processor to:   generate an MI model to determine mapping decisions to map the dataflow application to hardware resources of the second computing system to execute the dataflow application, the MI model comprising MI equations to solve by the MI solver, the MI equations including equations of an objective function corresponding to an optimization objective;   output the MI model to the MI solver;   invoke the MI solver to compute an MI solution comprising solutions to equations among the equations included in the MI model;   receive the MI solution; and,   generate a globally optimized mapping decision based on the MI solution; and,   wherein the MI Solver is configured to execute on the second processor to:   access the MI model;   solve equations among the MI equations; and,   output the MI solution.   
     
     
         13 . The first computing system of  claim 12 , wherein the objective function is expressed as a computation comprising an MI linear equation. 
     
     
         14 . The first computing system of  claim 12 , wherein equations among the MI equations comprise MI decision variables and MI decision equations. 
     
     
         15 . The first computing system of  claim 12 , wherein equations among the MI equations comprise MI constraint variables and MI constraint equations to include in the MI model. 
     
     
         16 . The first computing system of  claim 15 , wherein the MI constraint equations comprise equations selected from a group consisting of: node equations, bounds equations, data dependency equations, hardware usage equations; transfer size equations, and latency equations. 
     
     
         17 . The first computing system of  claim 12 , wherein the optimization objective is selected from a group consisting of: maximizing a processing throughput to execute the dataflow application by the second computing system; maximizing a number of processors to execute the dataflow application by the second computing system; maximizing a number of parallel operations to execute the dataflow application by the second computing system; minimizing a latency to execute the dataflow application by the second computing system; minimizing an amount of memory to execute the dataflow application by the second computing system; and, minimizing a number of data transfers to execute the dataflow application by the second computing system. 
     
     
         18 . The first computing system of  claim 12 , wherein the second computing system comprises a coarse grain reconfigurable system. 
     
     
         19 . The first computing system of  claim 12 , wherein the compiler is further configured to execute on the first processor to generate a human readable representation of the globally optimized mapping decision. 
     
     
         20 . The first computing system of  claim 12 , wherein the MI Solver comprises a commercially available MI Solver.