Optimization of a Search Function in a Large Software Product

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Olli, Iikka
dc.contributor.author Haikola, Ville
dc.date.accessioned 2016-06-17T12:41:38Z
dc.date.available 2016-06-17T12:41:38Z
dc.date.issued 2016-06-14
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/20975
dc.description.abstract In this work we studied the Building information modelling software Tekla Structures. Our goal was to improve the performance of a specific functionality in the case study software: the filtering of model objects. Filters are a set of rules customizable by the user. By applying filters user is able to filter model objects by their properties, for example by name, length or construction date. Filters are used in many key processes in Tekla Structures such as drawing creation, selection and how objects are visualized. We started by investigating the current implementation of filtering and where the performance could be improved. In our methods we are partly restricted by the large size of the software product, which makes high level changes difficult to implement. After investigation we were able to find more efficient algorithms and data structures to significantly improve the equation processing related to filtering. We found significant differences in the calculation times of properties, which lead us to investigate ways to optimize the evaluation order of the rules in the filter. Finding the optimal evaluation plan is in its general form a NP-hard combinatorial optimization problem. We then reimplemented the equation processing related to filtering. This included implementation of several algorithms to optimize the evaluation order of rules in the filter. These algorithms included a full exhaustive search of all evaluation plans and computationally less expensive methods such as an algorithm based on boolean differential algebra. The performance improvement was then calculated with user created structural models and in more controlled simulations. The reimplementation of the equation processing alone improved the performance of the filtering by more than 50% in our tests without the optimization of the evaluation order. The evaluation order optimization also gave significant improvement to the performance, which is more apparent in filters with a large number of rules. All the implemented algorithms were able to improve the performance and the computationally less expensive methods were almost as effective as the full exhaustive search of all evaluation plans. en
dc.description.abstract Tässä työssä tutkittiin rakennusten mallinnukseen käytettävää Tekla Structures -ohjelmistoa. Tavoitteena oli parantaa mallikappaleiden suodatukseen liittyvää toimintoa. Suodatin Tekla Structures -ohjelmistossa koostuu säännöistä, joiden perusteella voi rajoittaa mallikappaleiden joukkoa. Rajoitus tapahtuu kappaleiden ominaisuuksien kuten nimen, pituuden tai rakennuspäivämäärän perusteella. Suodattimia käytetään useassa eri tärkeässä prosessissa, kuten esimerkiksi piirustusten luonnissa ja kappaleiden visualisoinnissa kolmiulotteisissa malleissa. Aluksi tutustuttiin suodattimen nykyiseen toteutukseen. Tehokkuusanalyysin perusteella löydettiin algoritmeja ja tietorakenteita, joiden perusteella tehokkuutta voitiin parantaa. Ohjelmiston laajamittaisessa muokkaamisessa on haasteena sen suuri koko, monia miljoonia koodirivejä. Mallikappaleiden ominaisuuksien laskenta-ajoissa havaittiin isoa vaihtelua. Tämän vuoksi tutkimme voisiko suodattimen sääntöjen laskujärjestystä optimoimalla vaikuttaa sen suoritusaikaan. Optimaalisen laskujärjestyksen löytäminen on NP-täydellinen optimointiongelma. Tutkimme vastaaviin ongelmiin, kuten tietokantojen taulujen yhdistämisjärjestykseen käytettyjä algoritmeja. Tutkimusten perusteella päätimme toteuttaa suodattimeen liittyvän yhtälönratkaisijan uudelleen. Toteutimme algoritmeja, joilla pystyimme vaikuttamaan sääntöjen suoritusjärjestykseen. Toteutettuja algoritmeja olivat yksinkertainen säännön hintaan perustuva uudelleenjärjestys, boolean differentiaalialgebraan perustuva menetelmä sekä kaikki mahdolliset suoritusjärjestykset läpikäyvä haku. Uuden yhtälönratkaisijan tehokkuutta mitattiin testeissä, joita tehtiin aidoilla asiakasmalleilla sekä simuloidulla datalla. Toteutettujen muutosten myötä suodattimen suoritusaika pieneni yli 50 % testeissä jo ilman suoritusjärjestyksen optimointia. Suoritusjärjestyksen optimointi paransi suoritusaikaa merkittävästi kaikilla toteutetuilla algoritmeilla. Laskennallisesti vähemmän vaativat algoritmit olivat lähes yhtä tehokkaita kuin kaikki mahdolliset suoritusjärjestykset läpikäyvä haku. fi
dc.format.extent 60
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title Optimization of a Search Function in a Large Software Product en
dc.title Hakutoiminnon optimointi suuressa ohjelmistotuotteessa fi
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword BIM en
dc.subject.keyword filtering en
dc.subject.keyword performance analysis en
dc.subject.keyword boolean difference en
dc.subject.keyword JOP en
dc.identifier.urn URN:NBN:fi:aalto-201606172583
dc.programme.major Tietojenkäsittelytiede fi
dc.programme.mcode IL3010 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Karhunen, Juha
dc.programme Teknillisen fysiikan ja matematiikan koulutusohjelma fi
dc.ethesisid Aalto 4209
dc.location P1


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account