haku: @keyword parallel computing / yhteensä: 13
hakutulos-lista
viite: 4 / 13
« edellinen | seuraava »
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
sulje

Digitaalisten opinnäytteiden lukeminen Aalto-yliopiston Harald Herlin -oppimiskeskuksen suljetussa verkossa

Oppimiskeskuksen 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

  • Aalto-yliopistolaiset kirjautuvat asiakaskoneille Aalto-tunnuksella ja salasanalla.
  • Muut asiakkaat kirjautuvat asiakaskoneille yhteistunnuksilla.

Opinnäytteen avaaminen

  • Asiakaskoneiden työpöydältä löytyy kuvake:

    Aalto Thesis Database

  • Kuvaketta klikkaamalla pääset hakemaan ja avaamaan etsimäsi opinnäytteen Aaltodoc-tietokannasta. Opinnäytetiedosto löytyy klikkaamalla viitetietojen OEV- tai OEVS-kentän linkkiä.

Opinnäytteen lukeminen

  • Opinnäytettä voi lukea asiakaskoneen ruudulta tai sen voi tulostaa paperille.
  • Opinnäytetiedostoa ei voi tallentaa muistitikulle tai lähettää sähköpostilla.
  • Opinnäytetiedoston sisältöä ei voi kopioida.
  • Opinnäytetiedostoa ei voi muokata.

Opinnäytteen tulostus

  • Opinnäytteen voi tulostaa itselleen henkilökohtaiseen opiskelu- ja tutkimuskäyttöön.
  • Aalto-yliopiston opiskelijat ja henkilökunta voivat tulostaa mustavalkotulosteita Oppimiskeskuksen SecurePrint-laitteille, kun tietokoneelle kirjaudutaan omilla Aalto-tunnuksilla. Väritulostus on mahdollista asiakaspalvelupisteen tulostimelle u90203-psc3. Väritulostaminen on maksullista Aalto-yliopiston opiskelijoille ja henkilökunnalle.
  • Ulkopuoliset asiakkaat voivat tulostaa mustavalko- ja väritulosteita Oppimiskeskuksen asiakaspalvelupisteen tulostimelle u90203-psc3. Tulostaminen on maksullista.
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
« edellinen | seuraava »
INSSI