Deploying processing functions on a many-core grid: Mathematical optimization modelling and methodology
Typ
Examensarbete för masterexamen
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2019
Författare
Fredrikson, Nils
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
signal processing, processing graph, mixed-integer linear optimization, mathematical modelling, branch-and-bound, column generation, Dantzig-Wolfe decomposition.