Research

Motivation:

Program Comprehension

Software Maintenance is an important and complex phase of the Software Development Life Cycle (SDLC). Developers often need to fix bugs, improve performance for existing features, or upgrade (extend / add new features) for already deployed applications. For this they need to comprehend a large code-base in a short span of time. In a large majority of such cases, the documentation (requirements specs, design, system, test plan, code) and change traces are dated and incomplete, and systematic Knowledge Transfer (KT) or direct help from earlier developers are unavailable.

What Programmer usually have?

What is Missing?

Proper Documents

Organised knowledge transfer from core team Control Flow Analysers

Program runtime behaviour analysis tools

Aids to understand low level program design

Consequence

Some Stats

What we aim to build? --- Smart KT to enable smart knowledge transfer based on semantic search

We propose the SmartKT (SmartKnowledge Transfer) framework to address this challenge by extracting software development related as well as application specific knowledge and their inter-relationships in a Knowledge Graph to answer common developer queries like: What are the number of un-synchronized accesses in the program?, Which routine has the maximum execution time?, What are the highly coupled routines?, Is there any data-race?, What is the algorithm in function f1?, What are the static variables?, Which data structures are used by function f1?, What are the access patterns of global data?, and so on. The knowledge graph will be useful for the developers to gain an overall understanding of various aspects of software development and design like memory access, data-structure, algorithm, operation, concurrency, and thread models along with the application specific details for performing a maintenance task. We propose a framework from multiple sources with SmartKT which can be extended with other sources (like software repositories) and aims to reduce the learning overhead by making the process of KT more efficient, accurate, effective, and significantly automated. The knowledge graph can be used by an intelligent natural language query system to convert the process of knowledge transfer into a developer-friendly Google-like search.

To develop SmartKT, we identify reliable and available sources – source code, code comments and runtime-trace to analyze and extract knowledge. Program structure can be analyzed from source code using parsing or static instrumentation to infer def-use chains of variables or static call graphs. Using LLVM (Low level virtual machine) we create our custom syntax tree with information related to type, scope and def-use for all program symbols. Execution-time details for a program can be extracted using runtime profiling methods like dynamic instrumentation or sampling to infer aspects like data race, deadlocks, thread models, and dynamic call sequence. We use PIN, the dynamic instrumentation framework of Intel to build Dcube-ML to discover design models from applications based on runtime traces. We extensively use Machine Learning Algorithms to onfer program models from the sources

Finally, application specific information mostly manifest in code comments and can be extracted using Natural Language Processing (NLP) approaches. We develop Comment-Mine, a metadata analyzer, to extract program (algorithm, design pattern,data structure and the like) and problem domain concepts from code comments and correlate them to program symbols using NLP techniques.

Parallel Programming

Multicore architectures where more than one cores are joined together on a single integrated circuit are on the rise as it provides increased performance and better energy efficiency than using a single processor. Multicores are much more cost effective than further increasing the single-core clock frequencies or depth of the pipeline.

This proliferation on the other side requires that software developers must incorporate parallelism into their programming in order to achieve increased application performance.

In 2006, Saman Amarasinghe, computer science professor at MIT, described this situation as Looming Software crisis due to the Multicore Menance. http://groups.csail.mit.edu/commit/papers/2006/MulticoreMenace.pdf

Intel conducted a survey on October 2011 to measure the awareness and need of parallel programming among the software developers.

Some of the results are tabulated below:

http://www.ece.uprm.edu/~wrivera/ICOM4036/Paper2.pdf

Better and simpler tools and libraries are needed to help programmers parallelize their code and to debug the complex concurrency bugs that parallelism exposes.

Even though the software developers are highly aware of the shifting trend towards parallel programming, the major issue is that programmers are mostly ill-equipped for parallel programming, lacking the requisite training and often relying on primitive development tools.

My research focus is also to develop various tools which could assist programmers to analyse, debug and optimise the parallel applications running on multicore architectures. Also I aim to develop an integrated architecture which can help the programmers to efficiently utilise the support in the relevant phases of SDLC.

The framework should be portable across major operating systems and processor architectures, and be usable with major programming languages and IDE's.

Approach:

I have collated some of the major challenges faced by the parallel programmers are writing programs with optimal parallelism, they are debugging the concurrency bugs, detecting inconsistent states due to out of order execution, understanding the program execution across multiple cores, understanding the internals of every caught and uncaught exceptions during testing phase; comprehending legacy source codes with minimal documentation and redesigning it during maintenance phase; detecting performance bottlenecks of the program to increase the overall efficiency.

Broadly, the challenges can be grouped into Debugging and Comprehension Challenges which directly affect the productivity of the programmers and Analysis and Optimisation Challenges which helps to improvise an existing application and increase its effectiveness by exploiting parallelism.

Debugging and Comprehension Challenges includes debugging the concurrency bugs, understanding the internals of every caught and uncaught exceptions during testing phase, comprehending legacy source codes with minimal documentation and redesigning it during maintenance phase and like the same.

Analysis and Optimisation Challenges mainly focuses on detecting inconsistent states due to out of order execution, understanding the program execution across multiple cores, detecting performance bottlenecks of the program to increase the overall efficiency and like the same.

Debugging and Comprehension Challenges of Parallel Programming: Directly Impacts Productivity

Debugging Issues:

In contrast to single threaded applications, debugging multi-threaded applications is complex because of the non-deterministic nature of concurrent programs. Multiple threads in concurrent programs introduce bugs like datarace, deadlock and livelock. Most popular debuggers like GNU Debugger (GDB), Intel Debugger (IDB) and Microsoft Visual Studio Debugger (MVSD) provide many features to debug single-threaded programs but features dealing with debugging concurrency is limited. Mostly static or compile-time instrumentation is employed by most of the debuggers leading to numerous false positives.

Manifestation of multithreaded applications at runtime is very important due to it's non-deterministic nature. Our approach is based on dynamic instrumentation coupled with compiler instrumentation to provide more accurate detection of concurrency bugs. We also integrate our tool into existing debuggers to reduce the new interface understanding overhead of the programmers. Using PIN (Intel Dynamic Instrumentation Tool), GDB is augmented with support for datarace and deadlock detection with automated breakpoint to GDB. We call it PGDB or PIN-augmented GDB - a multi-threaded debugging platform. We also support an option to selectively enable/disable the detection mechanism to reduce the overhead of dynamic instrumentation during program execution.

To test the behaviour, accuracy and efficiency of PGDB, we have used (with modification) a set of benchmarks of popular dataraces detected by Google’s Thread-Sanitizer and have obtained good results.

Program Comprehension Issues:

Oftentimes when programmers are given to maintain (fix bugs or improve performance for existing features) or upgrade (extend / add new features) legacy software, they need to comprehend a large codebase in a short span of time. Usually the source code and a working software with tested (golden) data sets are available, but proper requirements / design documents, system / code documentation, change traces, organized Knowledge Transfer (KT), and help from earlier developers are inaccessible or scanty.

Reverse engineering has been employed for control-flow analysis of applications but not much work has been done for comprehending concurrent non-deterministic behavior of multi-threaded applications.

Our approach is D-CUBE, built using dynamic instrumentation APIs (mostly from PIN), which plugs in during execution and infers various thread models like concurrency, safety, data access, thread-pool state, exception model etc. for multi-threaded applications at runtime. These thread models are the design models which are extracted, based on which the programmers comprehend the application. We decide on some set of categories (candidates) which are commonly used, for every thread model. The executable is instrumented with PIN so that the various events (at instruction, block and function levels) can be observed during execution. The events are appropriately grouped into features characterizing every category of concurrency models. Finally, the features are fed to a decision tree classifier for the concurrency models of a category. The best matching decision is inferred as the model for that category.

D-CUBE has been tested with 3 Pthreads benchmark suites – In-house Pthreads benchmark from CDAC, Open POSIX Test Suite, and PARSEC 3.0 benchmarks, achieving over 90% accuracy in inferring concurrency models and fulfilling user requirements.

Research Progress:

The prototypes developed for addressing debugging and program comprehension challenges have been converted to full fledged tools PGDB and DCUBE respectively. In the first version, the tools only cater to C and C++ programming languages, Pthread libraries and will run in Linux OS. I am now working on the readme documents, the first version is scheduled to be released by the end of October, 2016. Also as further enhancements, the tool will be extended to other programming languages, thread libraries and OS. I have mentioned the details in the tools section of this site.

Analysis and Optimisation Challenges of Parallel Programming: Impact Program Portability and Performance

Analysis Issues:

At every step reproducing execution sequence becomes very difficult due to non deterministic execution of multi-threaded programs coupled

with inconsistent executions arising out of program order instruction issue employed by modern multi-core processor architectures following relaxed memory models. The major challenge is code portability and programmability as a program behaves and produces different outputs in different computer architectures with different memory consistency models.

Our approach would be based on analysis in compiler code generation and execution events to produce a complete execution and exception model so that atomicity violation bugs can be detected. Also the sequential version of a parallel program needs to be extracted before the compiler reorders few of the instructions to detect out of order instructions at compile and run time and provide a complete execution and exception state model of the program.

Optimisation Issues:

Identification of performance bottlenecks in multicore architectures is very important as it can be the manifestation of in appropriate parallel programming techniques leading to overloading of specific cores .

Our approach would be based on integrating traced CPU core statistics (traced using popular kernel tracers like systemTap, Lttng or DBT frameworks like DynInst) with basic block analysis based on dynamic instrumentation along with assembly code decoding of the compiler for detecting scalability and performance bottlenecks.

Research Progress:

I am now doing extensive literature survey for understanding unaddressed challenges of the parallel program performance and portability, from which I have identified some which I have discussed above. The approaches thought of are the very basic and will be worked upon in

details.

Key Skills:

1. Tools and Interface: PIN (Intel Dynamic Instrumentation Tool); PAPI (Performance Application Programming

interface); Intel X86 Encoder Decoder; Kernel Tracers: SystemTap, Lttng, DynInst; Compiler Tools: Flex, Lex,

Yacc, Bison; IBM Datawarehouse Tools; SAP Datawarehouse Tools

2. Programming Languages: C; C++; Parallel Languages: Intel Cilk++, Intel TBB, Open MP; Query Language:

PL/SQL

3. Scripting: Unix Scripting

4. Operating Systems: Linux, Windows, MacOS

5. Databases: DB2 10.2, Oracle

6. Database Design: Dia, Microsoft Visio

7. Version Management: WinSVN