Engineering Commons^™

Automatically Optimizing Tree Traversal Algorithms, Youngjoon Jo

Open Access Dissertations

Many domains in computer science, from data-mining to graphics to computational astrophysics, focus heavily on irregular applications. In contrast to regular applications, which operate over dense matrices and arrays, irregular programs manipulate and traverse complex data structures like trees and graphs. As irregular applications operate on ever larger datasets, their performance suffers from poor locality and parallelism. Programmers are burdened with the arduous task of manually tuning such applications for better performance. Generally applicable techniques to optimize irregular applications are highly desired, yet scarce.

In this dissertation, we argue that, for an important subset of irregular programs which arises in …