Konvergenca ranga pri dinamičnem programiranju

Grujić, Maja (author), Slivnik, Boštjan (mentor)

Kljub temu, da je vzporedno programiranje v uporabi že dolgo časa, se številni raziskovalci še vedno ukvarjajo s tematiko vzporednega izvajanja dinamičnega programiranja, saj reševanje optimizacijskih problemov vključuje veliko računanja tudi ob uporabi dinamičnega programiranja in je generičnih rešitev za tovrstne probleme zelo malo. V tem delu obravnavamo vzporedno Rang-1 metodo za probleme dinamičnega programiranja, ki spadajo v razred linearnega tropskega dinamičnega programiranja. Metodo najprej preizkusimo na različnih naključno generiranih vhodnih podatkih, nato pa še na Bellman-Fordovem algoritmu in na algoritmu rezanja šivov. Ugotovimo, da v primeru Bellman-Fordovega algoritma in algoritma rezanja šivov vzporedna Rang-1 metoda ne prinese pohitritve v primerjavi z zaporednim izvajanjem algoritma. V primeru naključno izbranih vhodnih podatkov pa ugotovimo, da je pohitritev reševanja problema odvisna od tega, koliko vhodnih matrik je ranga 1. V primeru, da je vsaj ena matrika ranga 1, algoritem že lahko prinese določene pohitritve.

• Language: Slovenian
• Keywords: linearno tropsko dinamično programiranje, konvergenca ranga, paralelizem, tropski polkolobar
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2022
• PID: 20.500.12556/RUL-136952
• COBISS.SI-ID: 110168579
• Publication date in RUL: 26.05.2022

Secondary language

• Language: English
• Title: Rank convergence in dynamic programming

Abstract

Even though parallel programming has been in use for a long time, many researchers are still dealing with the topic of parallel implementation of dynamic programming, as solving optimization problems involves a lot of computing, even using dynamic programming. In this work, we focus on Rank-1 method for problems of dynamic programming that belong to the linear-tropical dynamic programming class of problems. The method is tested on various randomly generated input data and using the Bellman-Ford algorithm and seam carving algorithm. In case of the Bellman-Ford and seam carving algorithms, the parallel Rank-1 method does not show any improvements, compared to the sequential implementation of those algorithms. In case of randomly selected input data, we see that the speed of solving the problem depends on how many input matrices are of rank 1. In case that at least one matrix has rank 1, the algorithm can already bring some improvements.

• Keywords: linear-tropical dynamic programming, rank convergence, parallelism, tropical semiring