On the specification and verification of the PCR parallel programming pattern in TLA+

Abstract

Physical limitations in processor design have made computer industry shift from improving the speed of a single processor to increasing the number of processing core units. But the design of software to exploit parallel processing power in a correct and cost-effective way is a challenging task requiring a high degree of expertise. In 2017, Pérez and Yovineproposed a platform-agnostic parallel programming pattern called PCR, that eases writing parallel code. In this thesis, we formalize the PCR pattern in terms of TLA+ —a formal specification language for concurrent systems that is being used at places suchas Intel, Amazon and Microsoft. We seek to provide a formal framework mainly for (1) expressing high level PCR designs and prove their functional correctness in the sense that their parallel computation computes a given mathematical function, and (2) being able to formally relate different PCR designs. In this way, we contribute to the state of the art in formal verification of parallel programs by leveraging TLA+-related tools to proving properties about high-level PCR-based algorithms such as their functional correctness and refinement.

Keywords

• Parallel algorithms
• Design patterns
• Formal Methods
• TLA