Talk on "A lower bound technique for Radio k-Coloring"
Speaker: Professor Sagnik Sen Department of Mathematics
Title: A lower bound technique for Radio k-Coloring
Abstract:Dynamic Programming (DP) algorithms are common targets for parallelization, and, as these algorithms are applied to larger inputs, distributed implementations become necessary. However, creating distributed-memory solutions involves the challenges of task creation, program and data partitioning, communication optimization, and task scheduling. In this work we present D2P, an end-to-end system for automatically transforming a specification of any recursive DP algorithm into distributed-memory implementation of the algorithm. When given a pseudo-code of a recursive DP algorithm, D2P automatically generates the corresponding MPI-based implementation. Our evaluation of the generated distributed implementations shows that they are efficient and scalable. Moreover, D2P-generated implementations are faster than implementations generated by recent general distributed DP frameworks, and are competitive with (and often faster than) hand-written implementations.
Event Date: 20th March, 2019(Wednesday)
Event Time: 04:30 PM
Venue: Room 23
IIT Dharwad, Karnataka