Dynamic programming in optimization theory

Paper focuses on adapting the technique of dynamic programming for multicore computers, equipped with two or more processing units. Proposed by R. Bellman method of solving problems, which exibits optimal substructure property and overlapping subproblems property, based on sequential algorithms are modified to fully exploit the available computing power. The first part discusses the basic definitions and information about dynamic programming and defines the problem, which was used to present the results of parallelization. Next section presents parallel dynamic programming algorithms and discuses measurement of the performance gain. 16-core server equipped with Java Virtual Machine with Solaris operating system was selected as the test platform.In this work special Java language framework was prepared, which simplifies implementation of the parallel dynamic programming algorithms by providing a generic mechanism which automatically separates task management and synchronization issues from framework client. The last chapter present the results obtained for two examples of optimization problems - the minimization of certain functionals. Work shows that parallel processing in dynamic programming can be at least four times faster than sequential solutions, and that these techniques can be successfully applied in other optimization problems.

Praca skupia się na przystosowaniu techniki programowania dynamicznego do komputerów wielordzeniowych, zaopatrzonych w dwie lub więcej jednostek obliczeniowych. Zaproponowane przez R. Bellmana metody rozwiązywania problemów posiadających własność optymalnej podstruktury oraz własność wspólnych podproblemów oparte o sekwencyjne algorytmy zostają w pracy zmodyfikowane, aby w pełni wykorzystać dostępną moc obliczeniową. W pierwszej części omówione zostały podstawowe definicje i informacje dotyczące dynamicznego programowania oraz zdefiniowany został problem, który posłużył do prezentacji wyników zrównoleglenia. W kolejnej części przedstawione zostały równoległe algorytmy programowania dynamicznego oraz omówione zostały sposoby oceny wzrostu wydajności algorytmów równoległych, uzyskanej dzięki równoległemu przetwarzaniu. Jako platforma do testów wybrany został język Java uruchomiony na serwerze posiadającym 16 procesorów pracujących pod kontrolą systemu operacyjnego Solaris. W ramach pracy został utworzony framework w języku Java, ułatwiający implementację równoległego rozwiązywania problemów programowania dynamicznego poprzez dostarczenie ogólnych mechanizmów zajmujących się rozdzieleniem pracy na poszczególne jednostki obliczeniowe oraz zajmujący się synchronizacją wykonywania poszczególnych podzadań. Ostatnie rozdziały prezentują wyniki uzyskane dla dwóch przykładowych problemów optymalizacyjnych polegających na minimalizacji określonych funkcjonałów. Praca wskazuje, że zastosowanie równoległego przetwarzania pozwala na conajmniej czterokrotne zmniejszenie czasu potrzebnego na odnalezienie optymalnego rozwiązania dla opisanych problemów programowania dynamicznego oraz że podane techniki mogą zostać z powodzeniem zastosowane w innych problemach optymalizacyjnych.