Parallel Computing

The goal here is to optimize software programs for parallel execution. The first projects explores several ways to parallelize a linux kernel module on a multi-core processor. The second project shows how the control flow in a piece of code can limit the level of parallelism that can be achieved. Following is the list of projects in this page,

• Exploiting Data Parallelism in SELinux Using a Multicore Processor

• Limits of Control Flow on Parallelism - A Graphical Visualization

Exploiting Data Parallelism in SELinux Using a Multicore Processor

This project was done at IIITB during Spring 2010 as part of the operating systems class under the guidance of Prof. Shrisha Rao.

Project Abstract:

Security Enhanced Linux, popularly known as SELinux [1], is a Linux operating system feature that provides fine-grained access control over system resources. Our goal is to optimize the performance of SELinux for a multicore processor and analyze the efficacy of our approach. We study the architecture of SELinux to identify specific components that cause

performance bottlenecks, and empirically validate our claims. We propose various techniques to delegate processor-intensive computations to multiple cores. We perform several experiments to evaluate the performance of our approach under different conditions, and discuss the intricacies of our implementation. Our results show that software applications with security validations have an inherent data parallelism which can be exploited for concurrent execution, but the gain in efficiency depends on design of the application and the hardware platform. In addition, we find that the gain in efficiency is also influenced by the optimization technique and the system configuration.We use a Cell Broadband Engine (CBE) processor running SELinux for our experiments, but our approach can be easily adapted to applications with a similar security validation framework running on other multicore platforms.

Downloads: Source Code  Paper  User Manual  Project Report  Presentation

Figure: Control flow of our approach

Figure: Poster presented at the Open House 2010 event held at IIIT-B.

Click here to access the original file. 

Limits of Control Flow on Parallelism - A Graphical Visualization

This project aims to implement the different abstract machine models given in the paper - Limits of Control Flow on Parallelism by Monica S. Lam and Robert P. Wilson. Each model  uses a combination of three different techniques - branch prediction, control dependence analysis and execution of multiple control flows. Our work provides a graphical illustration of the execution instance for a control flow graph which can be given as a text input. The key idea is that even with infinite processing units, the level of parallelism that can be achieved is limited by the control flow in the code. Hence this could be used to analyze a piece of code to find the extent to which it can be parallelized, before any attempt to modify it for parallel execution it is made.

Downloads: Source Code

Following are some of the screen shots of the tool in action,

Figure: User Interface

Figure: Minimum 3 clock cycles required using an SP abstract machine(circled indicates mis-predicted branches)

Figure: Minimum 2 clock cycles required using an SP-CD-MF abstract machine.

Figure: Minimum 5 clock cycles required using a CD-MF abstract machine.