ÍslenskaenEnglish

Aðilar að Skemmunni

Leit eftir:


LokaverkefniHáskólinn í Reykjavík>Tækni- og verkfræðideild>MSc verkefni>

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/7683

Titlar
  • en

    Meta-Heuristics in Multi-core Environments

  • Upplýstar leitaraðferðir í fjölkjarna umhverfum

Útgáfa
Nóvember 2010
Útdrættir
  • Mörg raunveruleg vandamál eru stór NP-hard vandamál og fyrir öll stærri tilvik er nánast ógerlegt að finna bestu lausnina á þeim á ásættanlegum tíma. Upplýstar leitaraðferðir eru oft notaðar til að fá góða lausn á vandamálum á ásættanlegum tíma en þau gefa ekki endilega bestu lausn. Í þessari grein verður farið yfir það hvernig má auka afköst upplýstra leitaraðferða með fjölkjarna vélum og finna út hvað ber að varast. Til að gera það voru valin þrjú reiknirit og þrjú vandamál. Reikniritin eru Aimulated Annealing, Ant Colony og Tabu Search en vandamálin eru Ackley fallið, Traveling Salesman vandamálið og Vehicle Routing vandamálið.
    Með því að keyra Simulated Annealing reikniritið á hverjum kjarna sem eyju fengum við út að hraðinn jókst um 1.6 þátt við hvern kjarna sem var bætt við.
    Einnig kom í ljós, að með því að skipta verkefninu upp í hluta sem tekur langan tíma að reikna og ekki þarf að nota mikið af sameiginlegum auðlindum er góð útfærsla fyrir fjölkjarna umhverfi, gefið að örgjörvin sé hraður. Með þess konar reikniriti fyrir Ant Colony fengum við hraðaaukningu upp á 3.7 þætti fyrir vél með fjóra kjarna.
    Aftur á móti kom í ljós að með því að skipta verkefninu upp í hluta sem tekur stuttan tíma að reikna og nota mikið sameiginlegar auðlindir milli reikninga, er ekki góð útfærsla fyrir fjölkjarna umhverfi. Það á sérstaklega við um hraða örgjörva. Með þess konar reikniriti fyrir Tabu Search minkaði hraðinn um 1.4 þátt fyrir vél með fjóra kjarna.
    Það má bæta hraða upplýstra leitaraðferða með því að forrita sérstaklega fyrir fjölkjarna umhverfi án mikilla vandræða. Hversu mikla hraðaaukningu má vænta fer algjörlega eftir reikniritinu, útfærslunni (hvort notaðar séu sameiginlegar auðlindir eða lásar) og tölvunni sem notast skal við. Til að fá nokkuð örugga hraðaaukningu má keyra reikniritin sem eyju á hverjum kjarna en best er að velja rétt reiknirit og vélbúnað fyrir hvert vandamál fyrir sig.

  • en

    Many real life problems are large NP-hard problems and thus for nontrivial instances it is almost impossible to find the best solution in a reasonable amount of time. Meta-heuristic algorithms are often used to get a good solution in a decent amount of time but they do not guarantee an optimal solution. In this paper we will take a look at how to increase the performance of meta-heuristic algorithms using multi core architectures and try to identify potential pitfalls along the way, to do that we will use three meta-heuristic algorithms and three different problems. The algorithms are Simulated Annealing, Ant Colony and Tabu Search and the problems are the Ackley function, Traveling Salesman problem and the Vehicle Routing problem.
    We found that by using a delightfully parallel algorithm, where the whole algorithm can be run on a single thread with no dependence on other threads, for Simulated Annealing the average gain for a new core is a factor of 1.6.
    We found that an implementation characterized by heavy calculations on each core with heavy reading and light writing in a shared memory is an ideal implementation for the multi core environment given that the CPU is both fast and has a large integrated cache memory. With such an algorithm we got a performance increase by a factor of around 3.7 for a quad core system using Ant colony meta-heuristics.
    We found that an implementation characterized by relatively light computations on each core and the use of shared resources between computations is not a good implementation for the multi core environment. This was especially evident with a fast CPU. With such an algorithm we got a performance decrease by a factor of around 1.4 for a quad core system using Tabu search meta-heuristics.
    By programming especially for multi core processors the performance of meta-heuristic algorithms can be improved without much additional cost or effort. The results depend on the algorithm chosen, the implementation (sharing memory structures, locks) and the system architecture. To get a solid performance gain, a delightfully parallel implementation is a very good choice but ideally one should select the correct algorithm and hardware for each problem and tune the algorithm for the selected hardware.

Athugasemdir

Ákvarðanaverkfræði

Birting
10.3.2011


Skrár
NafnRaðanlegtStærðRaðanlegtAðgangurRaðanlegtLýsingRaðanlegtSkráartegund
Meta-Heuristics in... . Ragnarsson).pdf1,39MBOpinn Heildartexti PDF Skoða/Opna