  Irregular applications comprise an increasingly important workload domain for
many fields, including bioinformatics, chemistry, physics, social sciences and
machine learning. Therefore, achieving high performance and energy efficiency
in the execution of emerging irregular applications is of vital importance.
This dissertation studies the root causes of inefficiency of irregular
applications in modern computing systems, and fundamentally addresses such
inefficiencies, by proposing low-overhead synchronization techniques among
parallel threads in cooperation with well-crafted data access policies.
  We make four major contributions to accelerating irregular applications in
different contexts including CPU and Near-Data-Processing (NDP) (or
Processing-In-Memory (PIM)) systems. First, we design ColorTM, a novel parallel
graph coloring algorithm for CPU systems that trades off using synchronization
with lower data access costs. Second, we propose SmartPQ, an adaptive priority
queue that achieves high performance under all various contention scenarios in
Non-Uniform Memory Access CPU systems. Third, we introduce SynCron, the first
practical hardware synchronization mechanism tailored for NDP systems. Fourth,
we design SparseP, the first library for high-performance Sparse Matrix Vector
Multiplication on real PIM systems.
  We demonstrate that the execution of irregular applications in CPU and
NDP/PIM architectures can be significantly accelerated by co-designing
lightweight synchronization approaches along with well-crafted data access
policies. This dissertation bridges the gap between processor-centric CPU
systems and memory-centric PIM systems in the critically-important area of
irregular applications. We hope that this dissertation inspires future work in
co-designing software algorithms with cutting-edge computing platforms to
significantly accelerate emerging irregular applications.
