Seminar: Paralelizacija dinamičnega programiranja z uporabo konvergence ranga v tropskih polkolobarjih / Parallelising Dynamic Programming Using Rank Convergence in Tropical Semirings
by
Zoom
https://uni-lj-si.zoom.us/j/97427737697?pwd=eS9Zd3pZaEVmU243cDNMNXIvblcxQT09
SLO
Na predavanju bo predstavljena zanimiva paralelizacija algoritma za reševanje problemov dinamičnega programiranja, ki jo je razvila skupina raziskovalcev z University of Illinois at Urbana Campaign in Microsoft Researcha. Drugače kot mnoge druge metode paralelizacije se ta ne osredotoči na razbitje algoritma na razmeroma neodvisne izračune in na pravilno porazdelitvi podatkov, da se zmanjša potrebno komunikacijo. Nova metoda se osredotoči na spremembo izračuna, pri čemer uporabi lastnosti osnovnih operacij, ki veljajo v tropskih polkolobarjih. Sprememba omogoči dodatno paralelizacijo, pri kateri je mogoče istočasno izvesti medsebojno odvisne dele izračuna. Paralelizacija in pospešitev izračuna sta odvisna od konvergence ranga matrik, ki nastopajo med izračunom. Pristop deluje dobro za številne optimizacijske probleme, ki se jih rešuje z dinamičnim programiranjem, a kot bomo videli, obstajajo tudi primeri, kjer pristop odpove.
ENG
This lecture will present an innovative parallelisation of an algorithm for solving a class of dynamic programming problems introduced by a group of researchers from University of Illinois at Urbana Campaign and Microsoft Research. Unlike many other parallelisation methods, this one does not concentrate on splitting the computation into semiautonomous tasks and on proper distribution of data to minimise communication. Instead, it focuses on how to modify the computation fundamentally by applying laws regarding basic operations as found in tropical semirings. The modification introduces additional parallelism which permits several otherwise dependent stages to be computed in parallel. The parallelisation and the speedup depend on how fast the rank of matrices converges to 1 during the computation. The approach works well for a number of optimisation problems usually solved using dynamic programming, but, as it will be shown, not for all. Dogodek organizira Fakulteta za računalništvo in informatiko Univerze v Ljubljani v sklopu projekta EuroCC. / Seminar is organized by University of Ljubljana, Faculty of Computer and information science, Slovenia as a EuroCC event.
Projekt EuroCC je financiran s sredstvi Skupnega podjetja za visoko zmogljivo računalništvo (EuroHPC JU) v skladu s sporazumom o dodelitvi sredstev št. 951732. EuroHPC JU je prejelo finančno podporo iz EU programa Obzorje 2020 ter Nemčije, Bolgarije, Avstrije, Hrvaške, Cipra, Češke, Danske, Estonije, Finske, Grčije, Madžarske, Irske, Italije, Litve, Latvije, Poljske, Portugalske, Romunije, Slovenije, Španije, Švedske, Združenega kraljestva, Francije, Nizozemske, Belgije, Luksemburga, Slovaške, Norveške, Švice, Turčije, Republike Severne Makedonije, Islandije in Črne gore.
UL FRI
