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.

Kompiuterių moksle, įskaitant fiziškai paremtas simuliacijas, kelio planavime ir lietimo atvaizdavime, kolizijos aptikimas yra fundamentali problema. Per paskutinius dešimtmečius, buvo pasiūlyta daugybė algoritmų kolizijos užklausų pagreitinimui. Tačiau, vis dar yra keletas neužbaigtų iššūkių. Siekiant užtikrinti teisingą skirtingų susidūrimo algoritmų palyginimą, rekomenduoju keletą metodų. Tai, apima teorinio hierarchinės kolizijos aptikimo algoritmų laiko veikimo modelį ir atvirą lyginimo šaltinį, kuris vertina kolizijos atlikimą. Šiame darbe yra tiriamas šių algoritmų veikimas, kurie veikia naudojant CPU (Central processing unit) ir GPU (Graphics processing unit), analizuojami erdvinių objektų kolizijų aptikimo metodai. Darbe iškeltų tikslų pasiekimui yra realizuotos bazinės algoritmų versijos, kurios buvo integruotos į vieną paketą tam, kad tikslingai būtų galima palyginti visų algoritmų veikimo laiką. Šiame darbe atlikti tyrimai parodė, kad nėra vieno įrankio tinkančio visiems scenarijams. Tačiau bendriniu atveju galima būtų siūlyti „Dop-Tree“, kadangi jo atveju derinami glaudūs BV ir greiti BV testai. Taip pat tyrimo rezultatai parodė, kad kartais didinant objekto sudėtingumą, kolizijos aptikimo laikas greitėja, tačiau tai tik išskirtiniai variantai., In computer science, including physically based simulations, road planning and in representing the issues in the collision detection is a fundamental problem. Over the past decades, many algorithms have been proposed to speed up collision detection queries. However, there are still a number of open challenges. In order to ensure a fair, different collision algorithms comparison I recommend several methods. This includes theoretical hierarchical collision detection algorithms time operating model and open source compareing which the performance of the collision detection. In this work has studied the performance of algorithms that operate using the CPU (Central processing unit) and GPU (Graphics processing unit), analyzing spatial objects conflict detection methods. The work objectives achievement is realized in the base version of algorithms have been integrated into a single package in order to specifically allow for comparison all algorithms time. This paper studies have shown that there is no single tool suitable for all scenarios. However, the generic would be readily offer Dop-Tree, as in his case combines close BV and quick BV tests. Another study showed that while increasing the complexity of the subject, the collision detection time is improving, but it's just outstanding options.

Kasmet daugybė žmonių būna sužalojami autoįvykiuose, iš kurių dalis sužalojimų būna rimti arba pasibaigia mirtimi. Dedama vis daugiau pastangų kuriant įvairias sistemas, kurios padėtų mažinti nelaimių skaičių kelyje. Tokios sistemos gebėtų perspėti vairuotojus apie galimus pavojus, atpažindamos eismo dalyvius ir sekdamos jų padėtį kelyje. Eismo dalyvių kelyje atpažinimas iš vaizdo yra pakankamai sudėtinga, daug skaičiavimų reikalaujanti problema. Šiame darbe šiai problemai spręsti pasitelkti stereo vaizdai, nesugretinamumo žemėlapis bei konvoliuciniai neuroniniai tinklai. Konvoliuciniai neuroniniai tinklai reikalauja daug skaičiavimų, todėl jie optimizuoti pasitelkus grafikos procesorių ir OpenCL. Gautas iki 33,4% spartos pagerėjimas lyginant su centriniu procesoriumi. Stereo vaizdai ir nesugretinamumo žemėlapis leidžia atmesti didelius kadro regionus, kurių nereikia klasifikuoti su konvoliuciniu neuroniniu tinklu. Priklausomai nuo scenos vaizde, reikalingų klasifikavimo operacijų skaičius sumažėja vidutiniškai apie 70-95% ir tai leidžia kadrą apdoroti atitinkamai greičiau. Many people are injured during auto accidents each year, some injures are serious or end in death. Many efforts are being put in developing various systems, which could help to reduce accidents on the road. Such systems could warn drivers of a potential danger, while recognizing on-road vehicles and tracking their position on the road. On-road vehicle recognition on image is a complex and computationally very intensive problem. In this paper, to solve this problem, stereo images, disparity map and convolutional neural networks are used. Convolutional neural networks are very computational intensive, so to optimize it GPU and OpenCL are used. 33.4% speed improvement was achieved compared to the central processor. Stereo images and disparity map allows to discard large areas of the image, which are not needed to be classified using convolutional neural networks. Depending on the scene of the image, the number of the required classification operations decreases on average by 70-95% and this allows to process the image accordingly faster.