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

Visa enkel post
dc.contributor.authorFredrikson, Nils
dc.contributor.departmentChalmers tekniska högskola / Institutionen för matematiska vetenskapersv
dc.contributor.examinerStrömberg, Ann-Brith
dc.date.accessioned2019-11-21T13:21:09Z
dc.date.available2019-11-21T13:21:09Z
dc.date.issued2019sv
dc.date.submitted2019
dc.description.abstractWhen 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.sv
dc.identifier.coursecodeMPENMsv
dc.identifier.urihttps://hdl.handle.net/20.500.12380/300555
dc.language.isoengsv
dc.setspec.uppsokPhysicsChemistryMaths
dc.subjectsignal processing, processing graph, mixed-integer linear optimization, mathematical modelling, branch-and-bound, column generation, Dantzig-Wolfe decomposition.sv
dc.titleDeploying processing functions on a many-core grid: Mathematical optimization modelling and methodologysv
dc.type.degreeExamensarbete för masterexamensv
dc.type.uppsokH
local.programmeEngineering mathematics and computational science (MPENM), MSc
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
Nils_Fredrikson_master_thesis_report_final.pdf
Storlek:
1.09 MB
Format:
Adobe Portable Document Format
Beskrivning:
Ladda ner
License bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
license.txt
Storlek:
1.14 KB
Format:
Item-specific license agreed upon to submission
Beskrivning:
Ladda ner
Samling
Examensarbeten för masterexamen