Fast Parallel Algorithms for the Transitive Closure and the Context-Free-Language (CFL) Reachability Problem

Project

Fast Parallel Algorithms for the Transitive Closure and the Context-Free-Language (CFL) Reachability Problem

Principal Investigator

Jens Dietrich

Massey University

Oracle Principal Investigator

Cristina Cifuentes, Senior Director of Research & Development, Oracle Labs Australia

Summary

Our aim is to find efficient algorithms to compute the transitive closure of directed graphs, and then to generalise this to compute CFL-reachability. In our research, we will explore the problem space consisting of low complexity algorithms, highly efficient data structures, and suitable implementations that utilise modern parallel hardware architectures. There is a large body of research in this area, with many new papers published in the last five years. The aim of this project is to systematically evaluate this research, improve it where appropriate, and find the best algorithms and data structures suitable for the type of graph that is investigated in the points-to analysis of Java programs. Criteria that define the fitness of the evaluated algorithms and data structures are construction time, memory requirements, and query time.