Deploying processing functions on a many-core grid: Mathematical optimization modelling and methodology

Abstract

When hardware platforms with over 1000 logical cores are used for signal processing, the optimization of latency and core utilization is key for efficient processing. To describe signal processing software, a consistent tool is that of a processing graph, where each node represents a data processing function. The problem of optimally deploying such processing functions from a graph, onto a many-core platform in the form of a grid, is considered in this thesis. A mathematical optimization model in the form of a mixed-binary linear programming model is proposed by decomposing the processing graph using a function sequence framework. A case processing graph is then deployed to two different grids by using the branch-and-bound method to solve the models to optimality. To cope with the computational complexity of branch-and-bound for large grids and processing graphs with many nodes, a column generation approach is taken. To this end, two different Dantzig-Wolfe decompositions of the model are made, each dividing the original model formulation into one master and one subproblem. In the first decomposition, the subproblem constraint matrix is block-diagonal. The second decomposition lacks this property. The column generation method is then applied to each of the two decompositions to search for approximately optimal solutions to the test cases. Column generation is then compared to branch-and-bound in terms of resulting binary solutions, objective values, and computational running time. The results indicate that the column generation can be used to search for improvements in an initial feasible solution. But the improvements were very small for the current proposed model and decompositions. To further develop the method it is suggested that constraints or costs that reduce symmetries within the model, are introduced. Compared to branchand- bound, the running time shows that column generation has the potential to be a viable alternative method to solve the deployment problem.