Programming systems for safe and accurate parallel programs in the face of uncertainty

Many emerging distributed applications operate on inherently noisy data or produce approximate results. Emerging application domains, including IoT, self-driving cars, and precision agriculture, routinely need to deal with noise from their sensors and unreliable communication mediums. Furthermore, increased volume of data, and the rise of highly parallel and often heterogeneous systems have brought forth new challenges in overcoming bottlenecks in both computation and communication between processing units. Many prominent systems adopted approximation in communication to address these challenges. Developing software in the presence of these novel architectures, optimizations, and approximations can be a challenging task. As these systems get deployed in safety critical situations, it is important to verify that they behave in a predictable and safe manner, even in situations where the outcomes are uncertain. Developers need to ensure that the programs operating with noisy data do not result in unexpected crashes and produce acceptable results with high reliability. In recent years, researchers have designed several analyses for verifying these program properties in the presence of uncertainty. These prior works had stayed away from parallel programming models, in part due to the complexities involved with reasoning about parallel interactions. This dissertation presents an ecosystem of several programming language tools and techniques across the computational stack that provides foundations for safety and accuracy analyses of parallel programs that deal with uncertainty. First, the dissertation will present a software infrastructure that enables simple and efficient use of a novel architecture that speeds up communication in a manycore processor using a wireless network. Next, the dissertation will show how to use programming language techniques to reduce the complexity of verifying the correctness of a subset of asynchronous message passing parallel programs in Parallely. We show how to lift many existing analyses that are designed for sequential programs to the domain of parallel programs. Next, the dissertation presents how to further extend verification to bigger programs and newer error models using runtime monitoring in Diamont. Finally, the dissertation presents several case studies that look at extending runtime verification to recovery mechanisms, algorithmic fairness analysis, and a novel architecture with potentially erroneous wireless communication.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Fernando, Vimuth

Contributors dc:contributor

• Misailovic, Sasa
• Torrellas, Josep
• Mitra, Sayan
• Carbin, Micheal

• distributed programming
• wireless network-on-chip
• reliability and accuracy
• approximate programming

Statement dc:rights

• Copyright 2022 Vimuth Fernando

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/116244

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116244