Computer Science Thesis Proposal

  • Gates&Hillman Centers
  • Traffic21 Classroom 6501
  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon Universityq
Thesis Proposals

Linear Logic and Coordination for Parallel Programming

Parallel programs are known to be difficult to write and reason about. Programs written in low level parallel constructs commonly available in imperative programming languages tend to be problematic to understand and debug. Declarative programming is a step in the right direction because it moves the details of parallelization from the programmer to the runtime system. However, these paradigms tend to remove most scheduling decisions from the programmer resulting in few opportunities for optimization.

We propose a declarative logic programming language called Linear Meld that is suited to run graph-based programs in parallel. The foundation of our language is linear logic, a powerful logical system where logical facts can be asserted and removed. Linear logic gives the language a structured way to manage state while remaining fully declarative. We envision the program as a communicating graph data structure where each processing unit performs work on a different subset of the graph. Logical rules are constrained to facts in the local node so that computation happens locally.

Although Linear Meld is declarative, it also minimizes the problem of programmer control by introducing coordination directives. Coordination directives in Linear Meld exist in two main forms: (1) as sensing facts with information about the state of the runtime system and (2) as action facts that can be derive in order to inform the scheduling decisions of the system.
The interplay between regular facts, sensing facts and action facts results in faster execution time and improved parallelism because regular facts affect how action facts are derived and, conversely, action facts may affect which regular facts are derived. We have written graph algorithms, search algorithms and machine learning algorithms and have seen good results on multicores, although our runtime system can be easily extended to other distributed architectures.

Thesis Committee:
Seth Goldstein (Co-Chair)
Frank Pfenning (Co-Chair)
Ricardo Rocha (Co-Chair, University of Porto)
Umut Acar
Carlos Guestrin (University of Washington)
Luis Barbosa (University of Minho)

Thesis Summary


For More Information, Please Contact: