misailo@csail.mit.edu

 MIT CSAIL, The Stata Center
 77 Mass Ave, 32-G730
 Cambridge, MA 02139
 Office Phone: (617) 253-7768

  Scholar    LinkedInLinkedIn
  DBLP      Facebook Facebook

 

 Quick Links:     
 News     Projects     Papers

Sasa Misailovic

Pronunciation: /Sa-sha Mee-sail-oveech/

I am a Ph. D. candidate at MIT working with professor Martin Rinard.

My research interests include programming languages, software engineering, and computer systems, with an emphasis on improving performance, energy efficiency, and resilience in the face of software errors and approximation opportunities.

 

News  

 

Projects  

Many approximate applications (such as multimedia processing, machine learning, and big data analytics) have the freedom to produce multiple acceptable results with different levels of accuracy. This gives us an opportunity to explore more aggressive program transformations that change semantics of a program to improve its performance and resilience, while producing acceptably accurate results.


Programming Approximate Hardware

Chisel Future high-performance architectures will have approximate and/or unreliable components that occasionally exhibit soft errors, which silently corrupt the results of computations. Full detection and masking of soft errors is challenging and expensive, but it can be unnecessary for approximate applications, which naturally tolerate such errors. I have built systems for developing applications to run on approximate hardware:

  • Chisel. Chisel is a system for reliability-aware and accuracy-aware optimization of computations that run on approximate hardware. Read More Chisel automatically selects which arithmetic operations and data can be approximated to minimize the computation's energy consumption while satisfying the developer-provided reliability and accuracy specifications. To find the optimized programs, Chisel formulates the placement of approximate instructions and data as an integer linear optimization problem. You can read about Chisel in OOPSLA '14 paper.

  • Rely. Rely is a programming language for computations that execute on unreliable hardware. Read More Rely allows a developer to specify the computation's reliability goal, mark individual arithmetic operations as approximate, and mark data that can be stored in approximate memory. Rely's static analysis can verify that a function that executes on unreliable hardware produces the correct result that satisfies the reliability goal. You can read about Rely in OOPSLA '13 paper.


Transforming Programs to Trade Accuracy for Performance

Code Perforation Accuracy-aware program transformations are compiler-level techniques that automatically generate approximate programs that have improved performance or energy consumption at the expense of the result's accuracy. In contrast to the standard approach to program transformation, which uses discrete logical reasoning to prove that a transformation does not change the observable semantics of the program, I propose novel probabilistic and statistical reasoning techniques that quantify the frequency and magnitude of results' differences:

  • Code Perforation. SpeedPress compiler transforms programs to perform less work by running fewer loop iterations or completely removing loops. Read More To find approximate programs that produce results whose accuracy is within acceptable user-defined bounds, I developed a novel find-analyze-navigate dynamic program optimization technique for exploring accuracy/performance tradeoff space. This optimization technique (1) finds computations in which a program spends most of its time using profiling, (2) analyzes how transforming each such computation affects program's accuracy, execution time, and integrity, and (3) navigates the tradeoff space by testing programs with multiple applied transformations. The generated approximate programs can dynamically respond to a range of increased performance demands while producing acceptable results. You can read about code perforation in ICSE '10, ASPLOS '11, and FSE '11 papers.

  • Probabilistic Accuracy Analysis. Static analyses for accuracy-aware transformations compute the probability of large numerical errors as the consequence of applying accuracy-aware transformations. Read More The SAS '11 paper presents a static analysis of loop perforation for a number of relevant code patterns (with randomness coming from the input). The POPL '12 paper presents a static analysis of map-fold computations transformed by randomized function substitution and sampling (with randomness coming from the computation itself). This paper also presents a tradeoff space exploration strategy based on mathematical optimization, which provides optimality guarantees.

  • Approximate Parallelization. Quickstep parallelization framework improves performance of parallel programs by opportunistically relaxing synchronization primitives, such as locks and barriers. Read More Quickstep uses online statistical testing to ensure (with high confidence) that the program with potentially introduced data races still produces an acceptable result. You can read about Quickstep in RACES '12 and TECS PEC '13 papers.


Escaping Infinite Loops

Bolt Infinite loops can make applications unresponsive, which causes lost work, denied access to application's functionality, and failure to respond to urgent events. Bolt is a system for dynamically detecting and escaping infinite loops in binaries. At the user’s request, Bolt attaches to a running application, monitors its execution, and reports to the user that the application is in an infinite loop when the consecutive loop iterations produce the same state. Bolt can then escape the infinite loop by transferring control to a statement following the loop, allowing the application to continue its productive execution. You can read about Bolt in ECOOP '11 and OOPSLA '12 papers.

 

 

Conference Papers  


  • Software Engineering Meets Control Theory
    Antonio Filieri, Martina Maggio, Konstantinos Angelopoulos, Nicolas D'Ippolito, Ilias Gerostathopoulos, Andreas Hempel, Henry Hoffmann, Pooyan Jamshidi, Evangelia Kalyvianaki, Cristian Klein, Filip Krikava, Sasa Misailovic, Alessandro Papadopoulos, Suprio Ray, Amir Molzam Sharifloo, Stepan Shevtsov, Mateusz Ujma, Thomas Vogel.
    10th International Symposium on Software Engineering for Adaptive and Self-Managing Systems
    (SEAMS 2015), Firenze, Italy, May 2015. Acceptance rate 29% (16/55 papers)
    abstract     full text    

  • Chisel: Reliability- and Accuracy-Aware Optimization of Approximate Computational Kernels
    Sasa Misailovic, Michael Carbin, Sara Achour, Zichao Qi, Martin C. Rinard
    29th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications
    (OOPSLA/SPLASH 2014), Portland, OR, USA, October 2014. Acceptance rate 28% (52/185 papers)
    (Best Paper Award)
    abstract     full text    

  • Verifying Quantitative Reliability for Programs that Execute on Unreliable Hardware
    Michael Carbin, Sasa Misailovic, Martin C. Rinard
    28th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications
    (OOPSLA/SPLASH 2013), Indianapolis, IN, USA, October 2013. Acceptance rate 26% (50/189 papers)
    (Best Paper Award)
    abstract    full text     MIT News article     Slashdot article

  • Bolt: On-Demand Infinite Loop Escape in Unmodified Binaries
    Michael Kling, Sasa Misailovic, Michael Carbin, Martin C. Rinard
    27th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications
    (OOPSLA/SPLASH 2012), Tucson, AZ, USA, October 2012. Acceptance rate 26% (59/228 papers)
    abstract    full text    

  • Proving Acceptability Properties of Relaxed Nondeterministic Approximate Programs
    Michael Carbin, Deokhwan Kim, Sasa Misailovic, Martin C. Rinard
    33rd ACM SIGPLAN Conference on Programming Language Design and Implementation
    (PLDI 2012), Beijing, China, June 2012. Acceptance rate 19% (48/255 papers)
    abstract    full text     MIT News Article

  • Randomized Accuracy-Aware Program Transformations for Efficient Approximate Computations
    Zeyuan Allen Zhu, Sasa Misailovic, Jonathan Kelner, Martin C. Rinard
    39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.
    (POPL 2012), Philadelphia, PA, USA, January 2012. Acceptance rate 21% (44/205 papers)
    abstract    full text

  • Probabilistically Accurate Program Transformations
    Sasa Misailovic, Daniel M. Roy, Martin C. Rinard
    18th International Static Analysis Symposium.
    (SAS 2011), Venice, Italy, September 2011. Acceptance rate 33% (22/67 papers)
    abstract    full text

  • Managing Performance vs. Accuracy Trade-offs With Loop Perforation
    Stelios Sidiroglou, Sasa Misailovic, Henry Hoffmann, Martin C. Rinard
    8th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering
    (ESEC/FSE 2011), Szeged, Hungary, September 2011. Acceptance rate 17% (34/203 papers)
    abstract    full text    

  • Detecting and Escaping Infinite Loops with Jolt
    Michael Carbin, Sasa Misailovic, Michael Kling, Martin C. Rinard
    25th European Conference on Object-Oriented Programming.
    (ECOOP 2011), Lancaster, UK, July 2011. Acceptance rate 26% (26/100 papers)
    abstract    full text     MIT News article     Slashdot article

  • Dynamic Knobs for Responsive Power-Aware Computing
    Henry Hoffmann, Stelios Sidiroglou, Michael Carbin, Sasa Misailovic, Anant Agarwal, Martin C. Rinard
    15th International Conference on Architectural Support for Programming Languages and Operating Systems.
    (ASPLOS 2011), Newport Beach, CA, USA, March 2011. Acceptance rate 21% (32/152 papers)
    abstract    full text    

  • Patterns and Statistical Analysis for Understanding Reduced Resource Computing
    Martin C. Rinard, Henry Hoffmann, Sasa Misailovic, Stelios Sidiroglou
    Onward! 2010 Conference
    (Onward! 2010), Reno-Tahoe, NV, USA, October 2010. Acceptance rate 25% (9/36 papers)
    abstract    full text    

  • Quality of Service Profiling
    Sasa Misailovic, Stelios Sidiroglou, Henry Hoffmann, Martin C. Rinard
    32nd International Conference on Software Engineering
    (ICSE 2010), Cape Town, South Africa, May 2010. Acceptance rate 14% (54/380 papers)
    abstract    full text     MIT News article

  • Parallel Test Generation and Execution with Korat
    Sasa Misailovic, Aleksandar Milicevic, Nemanja Petrovic, Sarfraz Khurshid, Darko Marinov
    6th joint meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering
    (ESEC/FSE 2007), Dubrovnik, Croatia, September 2007. Acceptance rate 17% (43/251 papers)
    abstract    full text    

 

Journal Papers  


  • Parallelizing Sequential Programs With Statistical Accuracy Tests
    Sasa Misailovic, Deokhwan Kim, Martin C. Rinard
    ACM Transactions on Embedded Computing Systems - Special Section on Probabilistic Embedded Computing.
    (ACM TECS PEC), May 2013. Submitted September 2011. Invited paper.
    abstract    full text     (Copyright 2013 by ACM, Inc.)

 

Workshop Papers  


  • Accuracy-Aware Program Transformations
    Sasa Misailovic
    First SIGPLAN Workshop on Probabilistic and Approximate Computing (Collocated with PLDI 2014)
    (APPROX 2014), Edinburgh, UK, June 2014. Invited Position Paper

  • Synthesis of Randomized Accuracy-Aware Map-Fold Programs
    Sasa Misailovic, Martin C. Rinard
    Workshop on Approximate Computing Across the System Stack (Collocated with ASPLOS 2014)
    (WACAS 2014), Salt Lake City, UT, February 2014
    full text    

  • Verified Integrity Properties for Safe Approximate Program Transformations
    Michael Carbin, Deokhwan Kim, Sasa Misailovic, Martin C. Rinard
    Workshop on Partial Evaluation and Program Manipulation (Collocated with POPL 2013)
    (PEPM 2013), Rome, Italy, January 2013
    full text    

  • Dancing With Uncertainty
    Sasa Misailovic, Stelios Sidiroglou, Martin C. Rinard
    ACM Workshop on Relaxing Synchronization for Multicore and Manycore Scalability (Collocated with OOPSLA 2012)
    (RACES 2012), Tucson, AZ, October 2012
    full text    

  • Generating Test Inputs for Fault-Tree Analyzers using Imperative Predicates
    Sasa Misailovic, Aleksandar Milicevic, Sarfraz Khurshid, Darko Marinov
    Workshop on Advances and Innovations in Systems Testing
    (STEP 2007), Memphis, TN, May 2007. Invited paper
    full text    

  • Korat: A Tool for Generating Structurally Complex Test Inputs
    Aleksandar Milicevic, Sasa Misailovic, Darko Marinov, Sarfraz Khurshid
    Formal research demonstration at the 29th International Conference on Software Engineering
    (ICSE Demo 2007), Minneapolis, MN, May 2007. Acceptance rate: 22% (12/56 papers)
    abstract    full text    

 

Technical Reports  


  • Reliability-Aware Optimization of Approximate Computational Kernels with Rely
    Sasa Misailovic, Michael Carbin, Sara Achour, Zichao Qi, Martin Rinard
    MIT-CSAIL-TR-2014-001, January 2014.
    full text

  • Synthesis of Randomized Accuracy-Aware Map-Fold Programs
    Sasa Misailovic, Martin C. Rinard
    MIT-CSAIL-TR-2013-031, December 2013.
    full text

  • Verifying Quantitative Reliability of Programs That Execute on Unreliable Hardware
    Michael Carbin, Sasa Misailovic, Martin C. Rinard
    MIT-CSAIL-TR-2013-014, June 2013.
    full text

  • Reasoning about Relaxed Programs
    Michael Carbin, Deokhwan Kim, Sasa Misailovic, Martin C. Rinard
    MIT-CSAIL-TR-2011-050, December 2011.
    full text

  • Probabilistic and Statistical Analysis of Perforated Patterns
    Sasa Misailovic, Daniel M. Roy, Martin C. Rinard
    MIT-CSAIL-TR-2011-003, January 2011.
    full text

  • Parallelizing Sequential Programs With Statistical Accuracy Tests
    Sasa Misailovic, Deokhwan Kim, Martin C. Rinard
    MIT-CSAIL-TR-2010-038, August 2010.
    full text

  • Using Code Perforation to Improve Performance, Reduce Energy Consumption, and Respond to Failures
    Henry Hoffmann, Sasa Misailovic, Stelios Sidiroglou, Anant Agarwal, Martin C. Rinard
    MIT-CSAIL-TR-2009-042, September 2009
    full text