Search

Objektų išdėliojimas yra klasikinis optimizavimo uždavinys. Šis uždavinys įdomus ne tik teoriškai, bet turi ir daug praktinių pritaikymų: straipsnių išdėliojimas laikraštyje taip, kad reikėtų kuo mažiau lapų; detalių pjaustymas lakštuose taip, kad liktų kuo mažiau nepanaudotų medžiagų. „Nvidia“ ištobulinta CUDA technologija leidžia atlikti didelį kiekį skaičiavimų naudojant grafinį procesorių. Grafinis procesorius pritaikytas atlikti tuos pačius veiksmus su skirtingais duomenimis daug kartų, o objektų išdėliojimo uždavinyje būtent tai ir daroma. Šiame darbe nagrinėjamas dvimatis objektų išdėliojimo atvejis, kai objektai yra orientuoti stačiakampiai, objektų sąrašas žinomas iš anksto, o lakštai yra vienodo dydžio. Taip pat bus panaudojamos CUDA suteikiamos galimybės šiam uždaviniui spręsti lygiagrečiai. Pateikiamas evoliucinis euristinis modifikavimo tipo algoritmas aprašytam uždaviniui spręsti, bei pasiūlytą algoritmą realizuojančios sistemos aprašymas. Galiausiai pateikiamas siūlomo algoritmo greitaveiką ir tikslumą vertinantis eksperimentas bei gauti rezultatai., Bin packing problem is classic optimization problem. This problem is interesting not only theoretically, but also has many practical applications. F. e. placing articles in newspaper so that the amount of papers would be minimal. Or putting boxes in trucks so that the amount of trucks would be minimal. “Nvidia” perfected their CUDA technology which allows to perform a large amount of computation using graphics processing unit. Graphics processing unit is adapted to perform the same actions with different data many times, and that is exactly what bin packing problem is all about. This work is focused on solving two-dimensional bin packing problem where objects cannot be rotated, objects are rectangular shape, objects are given offline and all bins are same dimensions. CUDA will also be used to address this challenge in parallel. An evolutionary heuristic algorithm which applies modifications is presented as well. Finally, experiment for measuring the speed and accuracy of the proposed algorithm are presented, as well as the results obtained.

Susidūrimų paieška - tai dviejų ar daugiau objektų susikirtimo radimas. Praktikoje susidūrimų paieška taikoma šiose srityse: kompiuteriniuose žaidimuose, netiesinėje baigtinių elementų analizėje, dalelių hidrodinamikoje, daugiafunkcinės dinamikos analizėje, įvairiose fizikos simuliacijose ir kt. Egzistuoja daugybė susidūrimų paieškos algoritmų, iš kurių populiariausi yra erdvinio skaidymo, hierarchinio struktūrizavimo ir atrinkimo bei rūšiavimo metodai. Šiame darbe yra tiriamas šių algoritmų veikimas ant CPU (Central processing unit) ir ant GPU (Graphics processing unit), analizuojami susidūrimų paieškos nustatymo būdai bei nagrinėjamos pasirinktų algoritmų veikimo spartinimo galimybės panaudojant CUDA (Compute Unified Device Architecture) technologiją. Ši technologija yra Nvidia sukurta nauja duomenų apdorojimo architektūra išnaudojanti grafinio procesoriaus resursus bendro pobūdžio skaičiavimams. Darbe iškeltų tikslų pasiekimui yra realizuotos kelios bazinės algoritmų versijos, jų pritaikymo lygiagretiems skaičiavimams galimybės ir taip pat atliekami bazinių algoritmų laiko, reikalingo skaičiavimams atlikti, grafinio procesoriaus atminties sąnaudos bei įvairių veikimo laiką įtakojančių faktorių tyrimai. Darbo pabaigoje aptariami lygiagretaus programavimo privalumai pritaikant nagrinėjamai temai. Šiame darbe atlikti tyrimai parodė, jog perduodant skaičiavimus į GPU pasiekiamas 200 kartų didesnis nagrinėjamų algoritmų našumas negu atliekant skaičiavimus naudojant CPU. Collision detection is a well-studied and active research field where the main problem is to determine if one or more objects collide with each other in 3D virtual space. Collision detection is an issue affecting many different fields of study, including computer animation, physical-based simulation, robotics, video games and haptic applications. There is a big variety of collision detection algorithms of witch spatial subdivision, octree and sort and sweep are three of them. In this document we provide a short summary of collision detection algorithms, but the main focus will be on analyzing and increasing their performance working on CPU (orig. Central processing unit) and GPU (orig. Graphics processing unit) separately by making use of CUDA (orig.Compute Unified Device Architecture) technology. This technology is a part of Nvidia, witch helps the use of graphics processor for general-purpose computation. Main goal of this research is achieved by performing analysis of implemented spatial subdivision, octree and sort and sweep algorithms. This analysis consists of both general performance, parallelization performance and various performance affecting factors analyses. At the end of the document, the advantages of parallel programming adapted to the present subject are discussed.

In practice, optimization problems are often multiple criteria. The criteria are usually contradictory, so the final decision depends on a decision maker. When the problem is solved interactively, the decision maker can change his/her preferences in decision process. Moreover, it is important to obtain solutions from the whole Pareto front. A decision support system adapted to the specific of the problem is essential for solving multiple criteria optimization problems interactively. The objects of research are multiple criteria optimization problems, interactive methods for solving these problems, interactive decision support systems, and application of parallel computing in decision support systems. Multiple criteria optimization methods are analyzed in the dissertation. The focus of attention is the methods for a uniform distribution of solutions on the Pareto front as well as the interactive methods. An interactive way for solving multicriteria optimization problems, which finds alternative solutions uniformly distributed on the Pareto front is proposed and investigated in this dissertation. An interactive decision support system which integrates the created interactive solving way, the decision process visualization and parallelization for multiple criteria optimization is developed. The solving strategies, when a multiple criteria optimization problem is solved interactively, using a computer cluster are developed and compared experimentally. The time required for a... [to full text] Praktikoje dažnai tenka spręsti sudėtingus daugiakriterinius optimizavimo uždavinius, kai kriterijai būna prieštaringi, o galutinis apsisprendimas priklauso nuo sprendimų priėmėjo. Kai sprendimų priėmėjas dalyvauja sprendimo procese interaktyviai, tai jis gali koreguoti prioritetus ir siekiamus tikslus uždavinio sprendimo eigoje, kas įgalina spęsti uždavinius, turinčius daug kriterijų ir apribojimų. Be to, sprendimo priėmėjui svarbu gauti sprendinius iš visos Pareto aibės. Interaktyviam uždavinių sprendimui būtina sprendimų paramos sistema, kurios grafinė sąsaja yra pritaikyta sprendžiamam uždaviniui. Šio darbo tyrimų sritis yra interaktyvus daugiakriterinių optimizavimo uždavinių sprendimas bei sprendimų paramos sistemos. Disertacijoje nagrinėjant daugiakriterinio optimizavimo metodus, didesnis dėmesys skirtas metodams, užtikrinantiems gaunamų sprendinių tolygų pasiskirstymą Pareto aibėje bei interaktyviems metodams. Pasiūlytas ir ištirtas daugiakriterinių optimizavimo uždavinių sprendimo būdas, leidžiantis spręsti daugiakriterinius optimizavimo uždavinius interaktyviai ir užtikrinantis gaunamų sprendinių tolygų pasiskirstymą Pareto aibėje. Sukurta ir ištirta interaktyvi daugiakriterinių optimizavimo uždavinių sprendimų paramos sistemą, apjungianti pasiūlytą optimizavimo uždavinių sprendimo būdą, sprendimo proceso vizualizavimą ir jo lygiagretinimą. Taip pat pasiūlyta sprendimo strategija, pagal kurią sprendžiant daugiakriterinį optimizavimo uždavinį pasitelkiamas... [toliau žr. visą tekstą]

Disertacijoje nagrinėjamos mikrobangų įtaisų analizės ir sintezės proble-mos, taikant lygiagrečiąsias kompiuterines sistemas. Pagrindiniai tyrimo objektai yra daugialaidės mikrojuostelinės linijos ir meandrinės mikrojuostelinės vėlinimo linijos. Šie objektai leidžia perduoti, sinchronizuoti bei vėlinti siunčiamus signalus ir yra neatsiejama dalis daugelio mikrobangų prietaisų. Jų operatyvi ir tiksli analizė bei sintezė sąlygoja įtaisų kūrimo spartinimą. Pagrindinis disertacijos tikslas – sukurti lygiagrečiąsias metodikas ir algoritmus, skirtus sparčiai ir tiksliai atlikti minėtų linijų analizę ir sintezę. Sukurtų algoritmų ir metodikų taikymo sritis – mikrobangų įtaisų modeliavimo ir automatizuoto projektavimo progra-minė įranga. An analysis using numerical methods can calculate electrical and construction characteristics parameters of microwave devices quite accurately. However, numerical methods require a lot of computation resources and time for calculations to be made. Rapid perfection of the computer technologies and software with implementation of the numerical methods has laid down the conditions to the rapid design of the microwave devices using computers.

Kelio paieška – tai trumpiausio maršruto tarp dviejų taškų radimas. Praktikoje kelio paieška taikoma šiose srityse: minių judėjimo modeliavimas, infrastruktūros planavimas, procesų modeliavimas, logistika ir kt. Egzistuoja eilė kelio paieškos algoritmų. Tačiau vienas iš labiau žinomų - A* kelio paieškos algoritmas. Šiame darbe yra tiriamas šio algoritmo veikimas skirtingų paskirčių procesoriuose, analizuojami kelio paieškos nustatymo būdai bei nagrinėjamos pasirinkto algoritmo veikimo spartinimo galimybės panaudojus DirectCompute technologiją. Ši technologija yra Microsoft DirectX 11 bibliotekų rinkinio dalis, kuri leidžia panaudoti grafinį procesorių bendro pobūdžio skaičiavimams. Darbe iškeltų tikslų pasiekimui yra realizuotos kelios algoritmo modifikacijos, atliekami modifikuotų versijų veikimo laiko bei įvairių veikimo laiką įtakojančių faktorių tyrimai. Darbo pabaigoje aptariami gauti rezultatai bei pateikiamos išvados., Path finding – it is the search of the shortest route between two points. In practice path finding is used in areas such as: crowd movement modeling, infrastructure planning, process modeling, logistics, etc. There are various path finding algorithms and one of them is A* path finding algorithm. This document contains analysis of A* path finding algorithm operation on different purpose processors. In this document we provide a short summary of path finding algorithms, but its main focus is on improving A* path finding algorithm overall performance by making use of DirectCompute technology. Main research goal is achieved by performing in-depth analysis of implemented A* path finding algorithm modifications. This analysis consists of both general performance and various performance affecting factors analyses. At the end of the document conclusions and recommendations are given based on performed work and overall results.

Disertacijoje nagrinėjamos mikrobangų įtaisų analizės ir sintezės proble-mos, taikant lygiagrečiąsias kompiuterines sistemas. Pagrindiniai tyrimo objektai yra daugialaidės mikrojuostelinės linijos (DML) ir meandrinės mikrojuostelinės vėlinimo linijos (MMVL). Šie objektai leidžia perduoti, sinchronizuoti bei vėlinti siunčiamus signalus ir yra neatsiejama dalis daugelio mikrobangų prietaisų. Jų operatyvi ir tiksli analizė bei sintezė sąlygoja įtaisų kūrimo spartinimą. Pagrindinis disertacijos tikslas – sukurti lygiagrečiąsias metodikas ir algoritmus, skirtus sparčiai ir tiksliai atlikti minėtų linijų analizę ir sintezę. Sukurtų algoritmų ir metodikų taikymo sritis – mikrobangų įtaisų modeliavimo ir automatizuoto projektavimo progra-minė įranga. Disertaciją sudaro įvadas, penki skyriai, rezultatų apibendrinimas, naudotos literatūros ir autoriaus publikacijų disertacijos tematika sąrašai bei du priedai. Įvadiniame skyriuje aptariama tiriamoji problema, darbo aktualumas, aprašomi tyrimų objektai, formuluojamas darbo tikslas ir uždaviniai, aprašoma tyrimų metodika, darbo mokslinis naujumas, darbo rezultatų praktinė reikšmė, ginamieji teiginiai. Įvado pabaigoje pristatomos disertacijos tema, autoriaus paskelbtos publikacijos ir pranešimai konferencijose bei disertacijos sandara. Pirmasis skyrius skirtas literatūros apžvalgai. Jame pateiktos DML ir MMVL analizės ir sintezės problemos, be to apžvelgtos lygiagrečiosios skaičiavimo sistemos ir jų taikymas elektrodinamikos uždaviniams spręsti. Skyriaus pabaigoje formuluojamos išvados ir tikslinami disertacijos uždaviniai. Antrajame skyriuje siūlomi du DML modeliai, leidžiantys skaitiniais metodais apskaičiuoti DML elektrinius parametrus, pateikti siūlomų modelių patikros rezultatai, atitinkantys elektromagnetinius procesus baigtinio dydžio DML. Trečiajame skyriuje plačiau nagrinėjama DML analizė ir sintezė, pasiūlyti lygiagretieji DML analizės ir sintezės algoritmai, atlikta jų patikra. Įgyvendinti algoritmai leidžia sparčiau apskaičiuoti elektrinius ir surasti konstrukcinius DML parametrus. Ketvirtajame skyriuje pateikiama lygiagrečioji MMVL dispersinės charakte-ristikos apskaičiavimo metodika. MMVL dispersinė charakteristika gaunama skaitiniais metodais sprendžiant dispersinę lygtį. Lygties sprendiniui rasti buvo sudaryti ir įgyvendinti keturi algoritmai. Remiantis šiais algoritmais pasiūlyta ir išbandyta lygiagrečioji MMVL dispersinės charakteristikos apskaičiavimo metodika. Penktasis skyrius skirtas MMVL sintezei. Pasiūlyti ir įgyvendinti skiltinio artėjimo ir Monte Karlo metodais grįsti lygiagretieji MMVL sintezės algoritmai, atlikti pasiūlytų algoritmų sintezės tikslumo ir našumo tyrimai. Disertacijos tematika paskelbti 5 straipsniai, iš kurių 3 straipsniai paskelbti recenzuojamuose mokslo žurnaluose. Rezultatai viešinti 9 mokslinėse konferencijose Lietuvoje ir užsienyje.

The principles of parallel computing, the MPI program parcel, which was used in this work, allow to adapt them to solve tasks using computer nets and peculiarities of implanting this package. The specific character of multiple criteria tasks of optimization and way of solutions using computer nets were cleared up. The decision theory, basic methods of making decisions were described in this work.

Modern computers are capable of completing most of the tasks in fairly short time, however there are areas in what calculations can last for months and even years. Parallel algorithms are one of the ways to accelerate long-lasting calculations. In the thesis we analyze parallel computing technologies OpenMP (shared memory) and MPI (distributed memory), cons and pros of their architecture. We identify potential parts of program code of Curonian lagoon model for parallelizing, in which chosen parallel computing technologies OpenMP and MPI is applied. Also we make the runtime speedup analysis.