PERDICE: Towards Discovering Software Inefficiencies Leading to Cache Misses and Branch Mispredictions

Ting Chen, Wanyu Huang, Muhui Jiang, Xiapu Luo, Lei Xue, Ying Wang, Xiaosong Zhang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

CPU cache misses and branch mispredictions waste CPU cycles and affect program performance. Such software inefficiencies could be neither eliminated by existing compilers nor avoided by developers. In this paper, we propose a novel approach, named PERDICE, to automatically discover such performance bugs by leveraging concolic execution. PERDICE adopts a new path exploration algorithm to discover such software inefficiencies. In particular, we measure performance losses in the granularity of program locations (e.g., instructions, source code lines) instead of paths to avoid getting stuck into the code without software inefficiencies. Moreover, when scoring test inputs, our new approach prefers the test inputs incurring increments in performance losses. This strategy allows PERDICE to avoid getting stuck into the software inefficiencies that have been found. We have implemented PERDICE for both PC (X86 instructions) and Android smartphones (ARM instructions). The experimental results with real-world desktop software and Android native code show that PERDICE outperforms the other four popular algorithms and PROFs (a multi-path performance profiler) in terms of the speed to discover software inefficiencies and the severity (i.e, amount of wasted CPU cycles) of inefficiencies.

Original languageEnglish
Title of host publicationProceedings - 2018 IEEE 42nd Annual Computer Software and Applications Conference, COMPSAC 2018
EditorsChung-Horng Lung, Ling Liu, Sorel Reisman, Hiroki Takakura, Claudio Demartini, Toyokazu Akiyama, Kamrul Hasan, Zhiyong Zhang, Sheikh Iqbal Ahamed, Ji-Jiang Yang, Motonori Nakamura, Thomas Conte, Stelvio Cimato, Edmundo Tovar, William Claycomb
PublisherIEEE Computer Society
Pages276-285
Number of pages10
ISBN (Electronic)9781538626665
DOIs
Publication statusPublished - 8 Jun 2018
Event42nd IEEE Computer Software and Applications Conference, COMPSAC 2018 - Tokyo, Japan
Duration: 23 Jul 201827 Jul 2018

Publication series

NameProceedings - International Computer Software and Applications Conference
Volume1
ISSN (Print)0730-3157

Conference

Conference42nd IEEE Computer Software and Applications Conference, COMPSAC 2018
CountryJapan
CityTokyo
Period23/07/1827/07/18

Keywords

  • Branch misprediction
  • Cache miss
  • Concolic execution
  • Path exploration
  • Software inefficiency

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Cite this