*
Quick Links|Home|Worldwide
Microsoft*
Search for
Runtime Analysis and Design

Overview
People
Projects
Publications
Opportunities
Overview

The Runtime Analysis and Design (RAD) research group investigates data-centric program analysis technologies and tools for improving software performance and security. We emphasize data structure and data access analysis since these play a central role in many performance and security problems. We apply program analysis and statistical techniques to efficiently monitor and measure program execution since many data related properties and behaviors are best observed while a program is running. We also investigate static heap analysis techniques, such as shape analysis, to supplement our dynamic observations and analysis. We believe a combination of static and dynamic program analysis techniques are required to address interesting problems in this space. In addition to servers, we are currently taking a close look at the web application and game domains since these appear especially amenable to a data-centric approach.

Current opportunities we are pursuing include:

  • Deep Runtime Analysis. Today, many program analyses are static and existing runtime analyses are either lightweight or offline. We believe the increasing size and complexity of computer systems coupled with hardware support for multiple threads have created an opportunity for more global, online, and heavyweight runtime analyses that still have minimal impact on program execution time.
  • Hybrid Static-Dynamic Frameworks. Runtime analysis offers precision and scalability while static analysis provides strong guarantees. Current attempts at combining the two typically use static analysis as a preprocessor to filter what must be monitored and analyzed at runtime. We are exploring more effective ways to combine these techniques and obtain the best of both worlds.
  • Heap Data. Static techniques have difficulty efficiently analyzing the program heap making it well suited to runtime analyses or hybrid approaches. This presents several opportunities. The processor-memory performance gap combined with the poor inherent locality of heap data makes the heap a prime target for performance optimization. In addition, specification, inference, checking, and enforcement of properties related to heap data has been neglected, despite its importance, since many analyses have a code and control-centric bias.
People

Primary Contact: Trishul Chilimbi


Chilimbi,
Trishul

Gulwani,
Sumit

Livshits,
Ben
 
Projects

Apart from the opportunities listed above, we are also investigating:

  • Precise and Scalable Static Analysis (Sumit Gulwani)
     This project involves designing and developing precise and efficient program analyses based on abstract interpretation using a variety of techniques: constructing abstract interpreters for new domains, developing techniques to combine the power of different abstract interpreters, extending intraprocedural abstract interpreters to an interprocedural setting. We are also interested in random interpretation, which is a form o f abstract interpretation that uses randomized algorithms and data structures.
  • NinjaWare - Low Overhead Software Monitoring and Analysis (Trishul Chilimbi)
     NinjaWare is a new project investigating lightweight continuous monitoring and analysis of software. Our implementation allows us to gather fine-grain temporal information about high frequency events such as program data accesses with very low overhead (< 5%). We are exploring leveraging this infrastructure to build a wide variety of always-on runtime tools ranging from memory leak and data race detectors to program specification/invariant checkers and security monitors.
  • Daedalus - Data Locality Optimization Research (Trishul Chilimbi)
     With the growing processor-memory performance gap, understanding and optimizing a program's data accesses is becoming increasingly important. Recent research has proposed several techniques that improve a program's cache performance by changing its data layout or its data access pattern. This project proposes to build a system that incorporates profile information and combines these techniques into an integrated framework for performing whole program data locality optimizations. It investigates techniques that efficiently analyze a program's data reference stream to identify and isolate data abstractions that can serve as a basis for data locality optimizations. Once identified these data abstractions can be exploited by providing data restructuring recommendations to a programmer, generating specialized allocators, and inserting data prefetches.
Selected Publications


Opportunities

We are actively hiring. If you are interested in seeking job opportunities in the Runtime Analysis and Design research group, please send your resume (Microsoft Word, HTML, PDF, postscript, or ASCII text format) via email to: trishulcATmicrosoft.com. Also, see the Recruiting Web Page for the Programming Languages and Tools area.

We are always looking for exceptional PhD candidates to join us as interns, especially during the summer months. For more information about becoming an intern, please visit our internship website.

Visitors, Collaborators, and Interns
  • Faculty
  • Summer Interns (2000)
  • Summer Interns (2001)
  • Summer Interns (2002)
  • Summer Interns (2003)
  • Summer Interns (2004)
    • Vinod Ganapathy (University of Wisconsin, Madison)
    • A.J. Shankar (University of California, Berkeley)
  • Summer Interns (2005)
    • Stephen McCamant (MIT)
    • Kapil Vaswani (Indian Institute of Science, Bangalore)
    • Ting Yang (University of Massachusetts, Amherst)
    •

©2008 Microsoft Corporation. All rights reserved. Terms of Use |Trademarks |Privacy Statement