TL;DR
This paper introduces novel programming language constructs that enable modular design in parallel programming. By separating resource management and scheduling from module logic, it allows for reusable parallel components and easier exploration of different execution strategies without code modification.
What Problem Does This Paper Address?
Traditional parallel programming often leads to monolithic, difficult-to-modify code, hindering code reuse and adaptation. Unlike sequential programming, where modularity is well-established, parallel programs struggle to encapsulate concerns like concurrency, communication, process mapping, and data distribution within individual modules. This makes it challenging to reuse components across different contexts or to experiment with different execution strategies (e.g., how to map processes to processors) without extensive code rewrites. The paper aims to bridge this gap by providing language constructs that promote modularity and reusability in parallel programs.
Methods
The core of the paper's contribution lies in the introduction of "virtual computers." These constructs allow programmers to specify process and data mapping relative to an abstract, virtual machine. The actual mapping of this virtual computer to physical processors is then handled externally to the module. This separation is achieved through three key operations on virtual computers:
- Process Mapping: Specifies where a process should execute within the virtual computer.
- Data Distribution: Defines how data structures are distributed across the nodes of a virtual computer.
- Embedding: Defines how virtual computers are structured and how they map onto existing physical or other virtual computers, enabling hierarchical design.
These concepts are integrated into two practical parallel programming languages: PCN (a C-like concurrent logic and imperative language) and Fortran M (a set of extensions to Fortran). The paper emphasizes that these constructs are designed to be consistent with the base languages, simplifying comprehension and compilation.
Datasets
Not discussed in the paper. The paper focuses on language design and its application to existing computational problems rather than introducing new datasets.
Key Insights and Ideas
- Decoupling Resource Management: The most significant insight is the ability to separate decisions about how a module runs (mapping, scheduling) from what the module does. This is achieved by defining modules relative to a "virtual computer."
- Hierarchical Modularity: Virtual computers can be nested, allowing for a hierarchical approach to resource management and locality decisions, akin to stepwise refinement.
- Enabling Code Reuse: By encapsulating design decisions within modules and abstracting away resource specifics, components become truly reusable across different parallel architectures and problem contexts.
- Facilitating Exploration of Alternatives: Programmers can easily explore different mapping strategies (e.g., pipeline vs. parallel execution of algorithm phases) by simply changing the virtual computer's embedding, without altering the core module logic.
- Compositional Programming: The approach aligns with compositional programming principles, where complex programs are built by combining simpler, well-defined components.
Key Results
The paper demonstrates the effectiveness of these constructs through their implementation in PCN and Fortran M and their application to substantial parallel problems. While specific quantitative results are not the primary focus, the paper highlights:
- Successful Reuse: FFT and summation modules developed for one problem were reused directly in another without modification.
- Facilitated Experimentation: The approach enabled easy experimentation with alternative mapping strategies for the parallel convolution algorithm, leading to insights into performance trade-offs.
- Practical Implementation: Compilers for both PCN and Fortran M have been developed, supporting extensive experimentation and application development.
- Educational Value: The languages have been used to teach parallel programming, with students benefiting from module libraries and the ability to modify existing frameworks.
Limitations and Future Work
The authors acknowledge several limitations and suggest future directions:
- PCN Scheduler Preemption: The PCN scheduler lacked preemption, which could lead to delays in remote read operations. Decomposing compute processes into many lightweight processes was a temporary solution, but a more robust preemption mechanism is desired.
- Fortran M Process Overhead: The initial implementation of Fortran M processes as Unix processes incurred significant overhead for interprocess communication. Using lightweight processes (threads) and shared-memory operations shows promise for reducing this overhead.
- General Data Distribution: While PCN supports blocked distributions of arrays, more complex distributions and data structures found in data-parallel languages are not yet fully supported by the current compiler.
- Embedding Cost: The execution of an embedding function can take time proportional to the square of the new virtual computer's size, though this cost is distributed and has not proven excessive on up to 500-processor systems.
- Future Work: The authors are actively constructing libraries of reusable parallel components and envision modules implemented using different underlying technologies (e.g., message-passing libraries, data-parallel languages) as long as they encapsulate mapping or scheduling decisions.
Summary updated