# Rathish Das, PhD Thesis Proposal Defense, Algorithmic Foundation of Parallel Paging and Scheduling under Memory Constraints

Dates:
Friday, November 6, 2020 - 12:00pm to 2:00pm
Location:
Zoom - contact events@cs.stonybrook.edu for Zoom info.
Event Description:

Title: Algorithmic Foundation of Parallel Paging and Scheduling under Memory Constraints

Abstract:

Efficient management of memory shared by multiple machines is critical to achieving good performance in parallel computation. The contribution of this dissertation is two-fold: (1) we develop an algorithmic foundation for the problem of automated management of shared-memory in multilevel-memory systems, also known as the parallel paging problem, and (2) we give provably good algorithms that schedule space/memory in a parallel computation to achieve optimal or near-optimal span (parallel running time) in many parallel computation models.

The first problem we consider is parallel paging. In the parallel paging problem there are $p$ processors that share a memory of size $k$. The goal of the problem is to partition the memory among the processors over time to minimize the average completion time. We resolve this long-standing open problem by designing online algorithms with tight upper and lower bounds of $\Theta(\log p)$ on the competitive ratio with $O(1)$ resource augmentation.

We further extend the parallel paging problem to a new kind of multilevel-memory system where there are bandwidth differences among the memory levels. This new kind of memory is called high-bandwidth memory (HBM), and is common in new supercomputers. Systems equipped with HBM do not fit in the classical memory-hierarchy models due to HBM’s atypical characteristics, and hence natural and classical paging policies perform poorly. We present a simple but counterintuitive constant-competitive online algorithm for HBM management.

The second problem we consider is memory-constrained scheduling.

In parallel computation, race conditions often lead to reduced parallelism. While locks mitigate races, they serialize the update operations. One can instead use reducers, which allow parallel race-free updates at the expense of using some extra space. This gives rise to the following question: given a fixed budget of extra memory/space for mitigating the cost of races in a parallel program, how should space be used or scheduled in order to minimize the overall running time? We provide NP-hardness results and constant factor single and bicriteria approximation algorithms for this problem.

We also investigate space-parallelism tradeoffs for many important problems in the binary-forking model. We design efficient parallel algorithms in the binary-forking model for fundamental problems such as Strassen's matrix multiplication and Strassen-like algorithms that achieve near-optimal span and total work for a given amount of memory.

Computed Event Type:
Mis
Event Title:
Rathish Das, PhD Thesis Proposal Defense, Algorithmic Foundation of Parallel Paging and Scheduling under Memory Constraints