  This work provides the first study to explore the interaction of update
propagation with and without fine-grained synchronization (push vs. pull),
emerging coherence protocols (GPU vs. DeNovo coherence), and software-centric
consistency models (DRF0, DRF1, and DRFrlx) for graph workloads on emerging
integrated GPU-CPU systems with native unified shared memory. We study 6 graph
applications with 6 graph inputs for a total of 36 workloads running on 12
system (hardware+software) configurations reflecting the above design space of
update propagation, coherence, and memory consistency. We make three key
contributions. First, we show that there is no single best system configuration
for all workloads, motivating systems with flexible coherence and consistency
support. Second, we develop a model to accurately predict the best system
configuration -- this model can be used by software designers to decide on push
vs. pull and the consistency model and by flexible hardware to invoke the
appropriate coherence and consistency configuration for the given workload.
Third, we show that the design dimensions explored here are inter-dependent,
reinforcing the need for software-hardware co-design in the above design
dimensions. For example, software designers deciding on push vs. pull must
consider the consistency model supported by hardware -- in some cases, push
maybe better if hardware supports DRFrlx while pull may be better if hardware
does not support DRFrlx.
