Beating in-order stalls with "Flea-Flicker" two-pass pipelining

Ronald D. Barnes, John W. Sias, Erik M. Nystrom, Sanjay J. Patel, Jose Navarro, Wen Mei W. Hwu

Research output: Contribution to journalArticlepeer-review


While compilers have generally proven adept at planning useful static instruction-level parallelism for in-order microarchitectures, the efficient accommodation of unanticipable latencies, like those of load instructions, remains a vexing problem. Traditional out-of-order execution hides some of these latencies, but repeats scheduling work already done by the compiler and adds additional pipeline overhead. Other techniques, such as prefetching and multithreading, can hide some anticipable, long-latency misses, but not the shorter, more diffuse stalls due to difficult-to-anticipate, first or second-level misses. Our work proposes a microarchitectural technique, two-pass pipelining, whereby the program executes on two in-order back-end pipelines coupled by a queue. The "advance" pipeline often defers instructions dispatching with unready operands rather than stalling. The "backup" pipeline allows concurrent resolution of instructions deferred by the first pipeline allowing overlapping of useful "advanced" execution with miss resolution. An accompanying compiler technique and instruction marking further enhance the handling of miss latencies. Applying our technique to an Itanium 2-like design achieves a speedup of 1.38x in mcf, the most memory-intensive SPECint2000 benchmark, and an average of 1.12x across other selected benchmarks, yielding between 32 percent and 67 percent of an idealized out-of-order design's speedup at a much lower design cost and complexity.

Original languageEnglish (US)
Pages (from-to)18-33
Number of pages16
JournalIEEE Transactions on Computers
Issue number1
StatePublished - Jan 2006


  • Cache-miss tolerance
  • Out-of-order execution
  • Prefetching
  • Runahead execution

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Beating in-order stalls with "Flea-Flicker" two-pass pipelining'. Together they form a unique fingerprint.

Cite this