國立虎尾科技大學 |

Hardware-Software Implementations of High Performance Graph Algorithms.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Hardware-Software Implementations of High Performance Graph Algorithms./
Author:	Blanco, Maia P.
Description:	1 online resource (138 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 84-10, Section: B.
Contained By:	Dissertations Abstracts International84-10B.
Subject:	Computer engineering. -
Online resource:	click for full text (PQDT)
ISBN:	9798379425135

Hardware-Software Implementations of High Performance Graph Algorithms.
Blanco, Maia P.

Hardware-Software Implementations of High Performance Graph Algorithms. - 1 online resource (138 pages)

Source: Dissertations Abstracts International, Volume: 84-10, Section: B.

Thesis (Ph.D.)--Carnegie Mellon University, 2023.

Includes bibliographical references

Graph analytics have seen increased attention in science and industry as a tool to gain useful insights from relational data. However, techniques and principles for high performance computing have traditionally focused on dense, regular problems. As a result, graph algorithms have retained a reputation for being 'irregular' and difficult for which to design implementations that perform well, i.e., that make efficient use of existing architectures. In this dissertation, we demonstrate that careful analysis and co-design of graph algorithm implementations for modern processor architectures provides improvements in performance whose underlying principles and techniques can be understood and explained at the level of the hardware and software interacting.Through algorithms across two families of graph processing workloads, we demonstrate that careful attention to the mapping of graph operations on functional units, cores, and memory hierarchy improves performance and understanding of how future algorithms, compilers, and architectures should be designed. In our work on motif-finding algorithms such as Triangle Counting and K-Truss, we demonstrate 1) the performance-improving mechanism of graph sorting and why superficially inefficient use of SIMD for set intersections still improves performance, and 2) the effect of careful task sizing and granularity of parallelism on many-thread processors. In graph traversal workloads such as Page Rank, Single Source Shortest Paths (SSSP), and Breadth First Search (BFS), we demonstrate that 1) graph traversal primitives in the form of matrixvector operations have a large capacity for memory level parallelism, but only if designed to overlap functional unit and memory latency and 2) inter-core cache coherence penalties in asynchronous parallel implementations can be mitigated by intentionally delaying those asynchronous updates. The application of our co-design methodology across two families of graph processing workloads enables better performance in existing graph processing frameworks and provides increased insight to the designers of future algorithms, compilers, and architectures.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798379425135Subjects--Topical Terms:

569006
Computer engineering.
Subjects--Index Terms:

AlgorithmsIndex Terms--Genre/Form:

554714
Electronic books.

Hardware-Software Implementations of High Performance Graph Algorithms.
LDR:03482ntm a22003857 4500 001 1143733
005 20240517104938.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798379425135
035 $a (MiAaPQ)AAI30313704
035 $a AAI30313704
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Blanco, Maia P. $3 1468515
245 1 0 $a Hardware-Software Implementations of High Performance Graph Algorithms.
264 0 $c 2023
300 $a 1 online resource (138 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 84-10, Section: B.
500 $a Advisor: Low, Tze Meng.
502 $a Thesis (Ph.D.)--Carnegie Mellon University, 2023.
504 $a Includes bibliographical references
520 $a Graph analytics have seen increased attention in science and industry as a tool to gain useful insights from relational data. However, techniques and principles for high performance computing have traditionally focused on dense, regular problems. As a result, graph algorithms have retained a reputation for being 'irregular' and difficult for which to design implementations that perform well, i.e., that make efficient use of existing architectures. In this dissertation, we demonstrate that careful analysis and co-design of graph algorithm implementations for modern processor architectures provides improvements in performance whose underlying principles and techniques can be understood and explained at the level of the hardware and software interacting.Through algorithms across two families of graph processing workloads, we demonstrate that careful attention to the mapping of graph operations on functional units, cores, and memory hierarchy improves performance and understanding of how future algorithms, compilers, and architectures should be designed. In our work on motif-finding algorithms such as Triangle Counting and K-Truss, we demonstrate 1) the performance-improving mechanism of graph sorting and why superficially inefficient use of SIMD for set intersections still improves performance, and 2) the effect of careful task sizing and granularity of parallelism on many-thread processors. In graph traversal workloads such as Page Rank, Single Source Shortest Paths (SSSP), and Breadth First Search (BFS), we demonstrate that 1) graph traversal primitives in the form of matrixvector operations have a large capacity for memory level parallelism, but only if designed to overlap functional unit and memory latency and 2) inter-core cache coherence penalties in asynchronous parallel implementations can be mitigated by intentionally delaying those asynchronous updates. The application of our co-design methodology across two families of graph processing workloads enables better performance in existing graph processing frameworks and provides increased insight to the designers of future algorithms, compilers, and architectures.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Computer engineering. $3 569006
650 4 $a Computer science. $3 573171
653 $a Algorithms
653 $a Architecture
653 $a Codesign
653 $a Graphs
653 $a Asynchronous parallel
655 7 $a Electronic books. $2 local $3 554714
690 $a 0464
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a Carnegie Mellon University. $b Electrical and Computer Engineering. $3 1182305
773 0 $t Dissertations Abstracts International $g 84-10B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30313704 $z click for full text (PQDT)