Sasa Misailovic
ABSTRACT
Many computations exhibit a trade off between execution time and quality of service. A video encoder, for example, can often encode frames more quickly if it is given the freedom to produce slightly lower quality video. A developer attempting to optimize such computations must navigate a complex trade-off space to find optimizations that appropriately balance quality of service and performance.
We present a new quality of service profiler that is designed to help developers identify promising optimization opportunities in such computations. In contrast to standard profilers, which simply identify time-consuming parts of the computation, a quality of service profiler is designed to identify subcomputations that can be replaced with new (and potentially less accurate) subcomputations that deliver significantly increased performance in return for acceptably small quality of service losses.
Our quality of service profiler uses loop perforation (which transforms loops to perform fewer iterations than the original loop) to obtain implementations that occupy different points in the performance/quality of service trade-off space. The rationale is that optimizable computations often contain loops that perform extra iterations, and that removing iterations, then observing the resulting effect on the quality of service, is an effective way to identify such optimizable subcomputations. Our experimental results from applying our implemented quality of service profiler to a challenging set of benchmark applications show that it can enable developers to identify promising optimization opportunities and deliver successful optimizations that substantially increase the performance with only small quality of service losses.
- prof. Digital Unix man page.Google Scholar
- UCI Machine Learning Repository. http://archive.ics.uci.edu/ml/.Google Scholar
- VTune Performance Analyser, Intel Corp.Google Scholar
- E. Amigo, J. Gonzalo, and J. Artiles. A comparison of extrinsic clustering evaluation metrics based on formal constraints. In Information Retrieval Journal. Springer Netherlands, July 2008. Google ScholarDigital Library
- J. Anderson, L. Berc, J. Dean, S. Ghemawat, M. Henzinger, S. Leung, R. Sites, M. Vandevoorde, C. Waldspurger, and W. Weihl. Continuous profiling: where have all the cycles gone? ACM Transactions on Computer Systems, 15(4):357--390, 1997. Google ScholarDigital Library
- J. Ansel, C. Chan, Y. Wong, M. Olszewski, Q. Zhao, A. Edelman, and S. Amarasinghe. PetaBricks: a language and compiler for algorithmic choice. In PLDI '09. Google ScholarDigital Library
- W. Baek and T. Chilimbi. Green: A system for supporting energy-conscious programming using principled approximation. Technical Report TR-2009-089, Microsoft Research, Aug. 2009.Google Scholar
- E. Berger and B. Zorn. DieHard: probabilistic memory safety for unsafe languages. In PLDI, June 2006. Google ScholarDigital Library
- C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC benchmark suite: Characterization and architectural implications. In PACT '08. Google ScholarDigital Library
- B. Demsky, M. Ernst, P. Guo, S. McCamant, J. Perkins, and M. Rinard. Inference and enforcement of data structure consistency specifications. In ISSTA '06. Google ScholarDigital Library
- B. Demsky and M. Rinard. Data structure repair using goal-directed reasoning. In ICSE '05, 2005. Google ScholarDigital Library
- B. Furht, J. Greenberg, and R. Westwater. Motion Estimation Algorithms for Video Compression. Kluwer Academic Publishers, Norwell, MA, USA, 1996. Google ScholarDigital Library
- S. Graham, P. Kessler, and M. Mckusick. Gprof: A call graph execution profiler. In SCC '82. Google ScholarDigital Library
- H. Hoffmann, S. Misailovic, S. Sidiroglou, A. Agarwal, and M. Rinard. Using Code Perforation to Improve Performance, Reduce Energy Consumption, and Respond to Failures. Technical Report MIT-CSAIL-TR-2009-042, MIT, Sept. 2009.Google Scholar
- C. Lattner and V. Adve. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In CGO'04. Google ScholarDigital Library
- D. Le Gall. MPEG: A video compression standard for multimedia applications. CACM, Apr. 1991. Google ScholarDigital Library
- S. Misailovic, D. Kim, and M. Rinard. Automatic Parallelization with Automatic Accuracy Bounds. Technical Report MIT-CSAIL-TR-2010-007, 2010.Google Scholar
- H. Nguyen and M. Rinard. Detecting and eliminating memory leaks using cyclic memory allocation. In ISMM '07. Google ScholarDigital Library
- G. Pennington and R. Watson. jProf - a JVMPI based profiler, 2000.Google Scholar
- J. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach, M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W. Wong, Y. Zibin, M. Ernst, and M. Rinard. Automatically patching errors in deployed software. In SOSP '09. Google ScholarDigital Library
- M. Rinard. Probabilistic accuracy bounds for fault-tolerant computations that discard tasks. In ICS '06. Google ScholarDigital Library
- M. Rinard. Using early phase termination to eliminate load imbalancess at barrier synchronization points. In OOPSLA '07. Google ScholarDigital Library
- M. Rinard, C. Cadar, D. Dumitran, D. M. Roy, T. Leu, and J. William S. Beebee. Enhancing Server Availability and Security Through Failure-Oblivious Computing. In OSDI '04. Google ScholarDigital Library
- S. Sidiroglou, O. Laadan, C. Perez, N. Viennot, J. Nieh, and A. D. Keromytis. Assure: automatic software self-healing using rescue points. In ASPLOS '09. Google ScholarDigital Library
- S. Sidiroglou, M. E. Locasto, S. W. Boyd, and A. D. Keromytis. Building a reactive immune system for software services. In USENIX '05. Google ScholarDigital Library
- D. Viswanathan and S. Liang. Java virtual machine profiler interface. IBM Systems Journal, 39(1), 2000. Google ScholarDigital Library
Recommendations
A quality of service architecture
For applications relying on the transfer of multimedia, and in particular continuous media, it is essential that quality of service (QoS) is guaranteed system-wide, including end-systems, communications systems and networks. Although researchers have ...
Managing performance vs. accuracy trade-offs with loop perforation
ESEC/FSE '11: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineeringMany modern computations (such as video and audio encoders, Monte Carlo simulations, and machine learning algorithms) are designed to trade off accuracy in return for increased performance. To date, such computations typically use ad-hoc, domain-...
Quality of service based routing: a performance perspective
SIGCOMM '98: Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communicationRecent studies provide evidence that Quality of Service (QoS) routing can provide increased network utilization compared to routing that is not sensitive to QoS requirements of traffic. However, there are still strong concerns about the increased cost of ...
Comments