Distributed Control: The Benefits of Eliminating Global Synchronization via Effective Scheduling - In the Context of Graph Applications

摘要

In distributed computing, parallel overheads such as synchronization overhead may hinder performance. We introduce the idea of Distributed Control (DC) where global synchronization is reduced to termination detection and each worker proceeds ahead optimistically, based on the local knowledge of the global computation. To avoid "wasted" work, DC relies on local work prioritization. However, the work order obtained by local prioritization is susceptible to interference from the runtime. We show that employing effective scheduling policies and optimizations in the runtime, in conjunction with eliminating global barriers, improves performance in two graph applications: single-source shortest paths and connected components.