Heavy Tails in Program Structure

Hiroshi Sasaki, Fang Hsiang Su, Teruo Tanimoto, Simha Sethumadhavan

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Designing and optimizing computer systems require deep understanding of the underlying system behavior. Historically many important observations that led to the development of essential hardware and software optimizations were driven by empirical observations about program behavior. In this paper, we report an interesting property of program structures by viewing dynamic program execution as a changing network. By analyzing the communication network created as a result of dynamic program execution, we find that communication patterns follow heavy-tailed distributions. In other words, a few instructions have consumers that are orders of magnitude larger than most instructions in a program. Surprisingly, these heavy-tailed distributions follow the iconic power law previously seen in man-made and natural networks. We provide empirical measurements based on the SPEC CPU2006 benchmarks to validate our findings as well as perform semantic analysis of the source code to reveal the causes of such behavior.

Original languageEnglish
Article number7480837
Pages (from-to)34-37
Number of pages4
JournalIEEE Computer Architecture Letters
Issue number1
Publication statusPublished - Jan 1 2017

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


Dive into the research topics of 'Heavy Tails in Program Structure'. Together they form a unique fingerprint.

Cite this