CS 6235 - Analysis of Parallel Programs

Project

Parallel programs bring in an additional complexity to progam analysis. Here are two groups of interesting problems:

Group 1 (extending classical analysis with MHP).
Many of the serial analysis have to be rewritten in the context of parallel programs. The goal of this project is to identify the impact of parallelism (MHP analysis) on different analysis. Each one of you is expected to choose an analysis and study the impact of MHP analysis on your chosen analysis.

  • Context sensitive constant propagation
  • Context insensitive constant propagation
  • Context sensitive Points-to Analysis
  • Context insensitive Points-to Analysis
  • Context sensitive Escape analysis
  • Context insensitive Escape analysis
  • Dependence analysis for Loop Distribution
  • Loop parallelization
  • Inter-procedural Program Slicing - Java

    Group 2 (interprocedural MHP Analysis)
    As an alternative here are some other interest problems you can consider

  • Context sensitve MHP analysis of X10 programs.
  • Context sensitve MHP analysis of Java programs.
  • Context insensitve MHP analysis of X10 programs.
  • Context insensitve MHP analysis of Java programs.

    Steps to follow:
    1. Step 1.
      1. Make group - max team size = 2.
      2. Choose an analysis from the above set (or find one yourself and inform).
      3. Deadline: 3 days from the start of the project deadline.
    2. Step 2. Write a section about the classical analysis (in case of Group 1), or current state of the art of MHP analysi (in case of Group 2)
      1. Motivate the importance of the analysis.
      2. Explain the algorithm for the analysis.
      3. Show an example illustrating how you apply the analysis.
      4. Deadline: Submit the document (preliminary report) by Mid-eval date.
    3. Step 3. Detais of the new analysis.
      1. Study the impact of parallelism on the chosen analysis (in case of Group 1) or impact of context on MHP (in case of Group 2).
      2. Write two examples that show the impact.
      3. Design a new algorithm to perform the new analysis.
      4. Show how the algorithm fares on the two chosen examples.
      5. Submit the final report (combining preliminary report and this one) by the final submission deadline.