Tekijä: | Hätälä, Antti |
Työn nimi: | Parallel shortest path search on GPU hardware |
Rinnakkainen lyhimmän polun etsintä GPU-suorittimella | |
Julkaisutyyppi: | Diplomityö |
Julkaisuvuosi: | 2010 |
Sivut: | [9+] 66 Kieli: eng |
Koulu/Laitos/Osasto: | Informaatio- ja luonnontieteiden tiedekunta |
Oppiaine: | Vuorovaikutteinen digitaalinen media (T-111) |
Valvoja: | Savioja, Lauri |
Ohjaaja: | Aila, Timo |
OEVS: | Sähköinen arkistokappale on luettavissa Aalto Thesis Databasen kautta.
Ohje Digitaalisten opinnäytteiden lukeminen Aalto-yliopiston Harald Herlin -oppimiskeskuksen suljetussa verkossaOppimiskeskuksen suljetussa verkossa voi lukea sellaisia digitaalisia ja digitoituja opinnäytteitä, joille ei ole saatu julkaisulupaa avoimessa verkossa. Oppimiskeskuksen yhteystiedot ja aukioloajat: https://learningcentre.aalto.fi/fi/harald-herlin-oppimiskeskus/ Opinnäytteitä voi lukea Oppimiskeskuksen asiakaskoneilla, joita löytyy kaikista kerroksista.
Kirjautuminen asiakaskoneille
Opinnäytteen avaaminen
Opinnäytteen lukeminen
Opinnäytteen tulostus
|
Sijainti: | P1 Ark Aalto | Arkisto |
Avainsanat: | shortest path problem heuristic search parallel computing A* CUDA 15-puzzle lyhimmän polun etsintä heuristinen haku A* CUDA 15-palapeli |
Tiivistelmä (fin): | Tämän diplomityön tarkoituksena on osoittaa että A* -verkkoalgoritmia lyhimmän polun etsintään on mahdollista nopeuttaa nykyaikaisella GPU-prosessorilla. Rinnakkaisia toteutuksia A* -algoritmista on tutkittu paljonkin erityisesti supertietokonearkkitehtuureilla, mutta kirjoittajien parhaan tietämyksen mukaan tämä työ on ensimmäinen laatuaan yrityksenä kiihdyttää yksittäisen lyhimmän polun ongelman ratkaisua hyödyntämällä GPU:n massiivista rinnakkaisuutta. Perinteisen "paras ensin" A* -algoritmin hajauttaminen usealle suorittimelle asettaa haasteita ajonaikaisen muistinkäytön sekä rinnakkaislaskentaan sisältyvien tehottomuuksien osalta. Näiden voittamiseksi tässä työssä valitaan toteutuksen lähtökohdaksi iteratiivisesti syvenevä A* periodisella kuorman tasauksella. Toteutus koostuu kompaktista "syvin ensin" verkkohakua rinnakkaisesti suorittavasta CUDA-ytimestä, keskussuorittimella ajettavasti kontrollilogiikasta iteraatioiden käynnistämiseen ja ratkaisun löytymisen toteamiseen, globaalista kuormantasausrutiinista keskussuorittimella sekä menetelmästä säielohkojen sisäiseen kuormantasaukseen CUDA-ytimessä. Työn empiirisessä osuudessa toteutetaan ohjelma joka tuottaa optimaalisia ratkaisuja liukuvalle 15-palapelille, analysoidaan rinnakkaisella toteutuksella saavutettua kiihdytystä ja tehokkuutta sekä vertaillaan tuloksia vastaavaan optimoituun CPU-toteutukseen. Käytettäessä standardoitua sadan palapelin testiaineistoa saavutetaan 34-kertainen kiihdytys CPU-toteutukseen verrattuna. |
Tiivistelmä (eng): | The aim of this thesis is to show that a modern GPU can he leveraged for accelerating the A* heuristic graph search algorithm for solving a single-pair shortest path problem. While a lot of prior research has been done in A* parallelization for supercomputer architectures, to the best knowledge of the authors this is the first reported attempt at speeding up the solving of a single shortest path problem by GPU massive parallel processing. To overcome the large runtime memory requirements and the parallel processing overhead inefficiencies associated with traditional best-first parallel A*, a scheme of iterative-deepening A* with fixed node iteration count based periodic load balancing is chosen. The implementation consists of a compact parallel depth-first search CUDA kernel, CPU control logic for iteration launch and termination detection, a global load balancing routine on the CPU and a parallel per-block load balancing method in the CUDA kernel. The empirical study involves implementing a solver for the 15-puzzle optimal solution problem, analyzing the parallel speedup obtained from GPU massive parallelism and comparing the results against an optimized CPU solver. For a standard test set of a hundred 15-puzzle start configurations a 34-fold performance improvement over the CPU implementation is achieved. |
ED: | 2010-05-10 |
INSSI tietueen numero: 39579
+ lisää koriin
INSSI