uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
Parallel graph coloring: Parallel graph coloring on multi-core CPUs
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Scientific Computing.
2014 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

In recent times an evident trend in hardware is to opt for multi-core CPUs. This has lead to a situation where an increasing number of sequential algorithms are parallelized to fit these new multi-core environments. The greedy Multi-Coloring algorithm is a strictly sequential algorithm that is used in a wide range of applications. The application in focus is on decomposition by graph coloring for preconditioning techniques suitable for iterative solvers like the and methods. In order to perform all phases of these iterative solvers in parallel the graph analysis phase needs to be parallelized. Albeit many attempts have been made to parallelize graph coloring non of these attempts have successfully put the greedy Multi-Coloring algorithm into obsolescence.

In this work techniques for parallel graph coloring are proposed and studied. Quantitative results, which represent the number of colors, confirm that the best new algorithm, the Normann algorithm, is performing on the same level as the greedy Multi-Coloring algorithm. Furthermore, in multi-core environments the parallel Normann algorithm fully outperforms the classical greedy Multi-Coloring algorithm for all large test matrices.

With the features of the Normann algorithm quantified and presented in this work it is now possible to perform all phases of iterative solvers like and methods in parallel.

Place, publisher, year, edition, pages
2014. , 45 p.
Series
UPTEC F, ISSN 1401-5757 ; 14029
Keyword [en]
Parallel graph coloring multi coloring
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:uu:diva-227656OAI: oai:DiVA.org:uu-227656DiVA: diva2:730761
Educational program
Master Programme in Engineering Physics
Presentation
2014-06-12, Ångström 2001, 09:59 (English)
Supervisors
Examiners
Available from: 2014-08-04 Created: 2014-06-30 Last updated: 2014-08-04Bibliographically approved

Open Access in DiVA

paragraphcoloring(1139 kB)806 downloads
File information
File name FULLTEXT01.pdfFile size 1139 kBChecksum SHA-512
951a0cdd5aba662506a95a6e218af2bedbfe29eaf089529546b15b74f81c552ca6043d3ba491a707a00779d0e24ac7b86acb239de3da84908ec8041111dc7257
Type fulltextMimetype application/pdf

By organisation
Division of Scientific Computing
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 806 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: 4982 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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