Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Train Re-scheduling: A Massively Parallel Approach Using CUDA
Blekinge Institute of Technology, Faculty of Computing, Department of Computer Science and Engineering.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Context. Train re-scheduling during disturbances is a time-consuming task. Modified schedules need to be found, so that trains can meet in suitable locations and delays minimized. Domino effects are difficult to manage. Commercial optimization software has been shown to find optimal solutions, but modied schedules need to be found quickly. Therefore, greedy depth-first algorithms have been designed to find solutions within a limited time-frame. Modern GPUs have a high computational capacity, and have become easier to use for computations unrelated to computer graphics with the development of technologies such as CUDA and OpenCL.

Objectives. We explore the feasibility of running a re-scheduling algorithm developed specifically for this problem on a GPU using the CUDA toolkit. The main objective is to find a way of exploiting the computational capacity of modern GPUs to find better re-scheduling solutions within a limited time-frame.

Methods. We develop and adapt a sequential algorithm for use on a GPU and run multiple experiments using 16 disturbance scenarios on the single-tracked iron ore line in northern Sweden.

Results. Our implementation succeeds in finding re-scheduling solutions without conflicts for all 16 scenarios. The algorithm visits on average 7 times more nodes per time unit than the sequential CPU algorithm when branching at depth 50, and 4 times more when branching at depth 200.

Conclusions. The computational performance of our parallel algorithm is promising but the approach is not complete. Our experiments only show that multiple solution branches can be explored fast in parallel, but not how to construct a high level algorithm that systematically searches for better schedules within a certain time limit. Further research is needed for that. We also find that multiple threads explore redundant solutions in our approach.

Place, publisher, year, edition, pages
2015. , 42 p.
Keyword [en]
scheduling algorithms, massively parallel algorithms, combinatorial optimization
National Category
Computer Science
Identifiers
URN: urn:nbn:se:bth-10965OAI: oai:DiVA.org:bth-10965DiVA: diva2:868498
Subject / course
DV2566 Master's Thesis (120 credits) in Computer Science
Educational program
DVACS Master of Science Programme in Computer Science
Presentation
2015-09-21, Karlskrona, 15:00 (English)
Supervisors
Examiners
Available from: 2015-11-11 Created: 2015-11-10 Last updated: 2015-11-11Bibliographically approved

Open Access in DiVA

fulltext(562 kB)175 downloads
File information
File name FULLTEXT01.pdfFile size 562 kBChecksum SHA-512
d824b4347ed5fc74641003c438f1fbab6ba6ea07700d398ed7c3915cbb0536559229d8a43f6ba6b80e294d5ddeb242ade551fb74a1ff41db71aa686502f59012
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Petersson, Anton
By organisation
Department of Computer Science and Engineering
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 175 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 279 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf