One-size-fits-all memory recycling algorithm for parallel programming

PEBR (Pointer- and Epoch-Based Reclamation) is a new memory recycling algorithm for parallel programming that satisfies all the desired properties for the first time: it is fast, robust, compact, self-contained, and widely applicable.

Article | Fall 2021

Multi-core processors are widely deployed in modern computers, not only in supercomputers but also in laptops and even mobile phones. Multi-core processors are best utilized when the parallel cores are being efficiently synchronized with each other.

At the heart of such parallel synchronization of multi-core processors is the art of memory reclamation. Memory reclamation is the process of recycling datum used by computer programs. Each datum takes place in DRAM – a precious resource in computer systems – so un-reclaimed data may use up DRAM and freeze the system. Therefore, proper memory reclamation is at the heart of writing correct and efficient programs.

Memory reclamation is a difficult task because programmers need to achieve soundness and completeness. Soundness means a datum is no longer used after it is reclaimed, and completeness means every datum is reclaimed someday. Memory reclamation becomes even more difficult in parallel programming because programmers need to ensure soundness and completeness in the presence of multiple parallel cores. For example, for soundness, programmers now need to make sure a reclaimed datum is no longer used by every core, which involves deliberate synchronization of multiple cores.

To ease the burden of programmers, various memory reclamation algorithms have been proposed. These algorithms take care of memory reclamation as far as a few rules are observed by programs. However, “None of the existing algorithms are entirely satisfactory,” says Prof. Kang.

A new, innovative memory reclamation algorithm for parallel programming was designed by Prof. Jeehoon Kang at the School of Computing and his research team. “By combining the key ideas of the two representative algorithms, which are hazard pointers and epoch-based reclamation,” says Jaehwang Jung, a graduate student in Prof. Kang’s research team, “we could design the best-in-the-class reclamation algorithm.”

 

Indeed, the two prior algorithms are not entirely satisfactory. On the one hand, the hazard pointer is robust in that it reclaims datum in any situation. Even when a core’s program is broken or ill-behaving, the other cores collaborate to reclaim their data. However, this algorithm is slow because each pointer-chasing requires an expensive synchronization instruction. On the other hand, epoch-based reclamation is fast in that the expensive instruction is required only once in a while. However, this algorithm is not robust in that the reclamation of the entire memory may be blocked if a core’s program is a poorly written.

The new algorithm – dubbed PEBR (Pointer- and Epoch-Based Reclamation) – designed by Prof. Kang and his research team is a hybrid of hazard pointers and epoch-based reclamation that takes the benefits of both. “We designed a new algorithm on epoch-based reclamation that kicks out bad cores to hazard pointers when they start to block reclamations,” says Jung. “By doing so, our algorithm can be fast and robust at the same time.”

 

In addition, their algorithm is compact (does not take place much more space in DRAM than necessary), self-contained (supports various architectures and platforms), and widely-applicable (supports various parallel programs). Since PEBR is the first algorithm that satisfies all the desired properties, it can be widely used in parallel computing whenever memory reclamation is necessary.

A downside of the new algorithm is its complexity. “We already extensively tested this complex algorithm, but to have an extra degree of confidence, we are currently formally verifying the algorithm,” says Prof. Kang. “Formal verification means proving the algorithm’s correctness with a machine-checked proof so that everyone can use the algorithm without concerns about its correctness.”