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

Direct link
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.
UPTEC F, ISSN 1401-5757 ; 14029
Keyword [en]
Parallel graph coloring multi coloring
National Category
Computer and Information Science
URN: urn:nbn:se:uu:diva-227656OAI: oai:DiVA.org:uu-227656DiVA: diva2:730761
Educational program
Master Programme in Engineering Physics
2014-06-12, Ångström 2001, 09:59 (English)
Available from: 2014-08-04 Created: 2014-06-30 Last updated: 2014-08-04Bibliographically approved

Open Access in DiVA

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

By organisation
Division of Scientific Computing
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 586 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

Total: 4700 hits
ReferencesLink to record
Permanent link

Direct link