Entry Kim:2006:ERI from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Kim:2006:ERI,
  author =       "Seon Wook Kim and Chong-Liang Ooi and Rudolf Eigenmann
                 and Babak Falsafi and T. N. Vijaykumar",
  title =        "Exploiting reference idempotency to reduce speculative
                 storage overflow",
  journal =      j-TOPLAS,
  volume =       "28",
  number =       "5",
  pages =        "942--965",
  month =        sep,
  year =         "2006",
  CODEN =        "ATPSDT",
  DOI =          "http://doi.acm.org/10.1145/1152649.1152653",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Wed Sep 6 07:13:55 MDT 2006",
  bibsource =    "http://www.acm.org/pubs/contents/journals/toplas/;
                 http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  abstract =     "Recent proposals for multithreaded architectures
                 employ speculative execution to allow threads with
                 unknown dependences to execute speculatively in
                 parallel. The architectures use hardware speculative
                 storage to buffer speculative data, track data
                 dependences and correct incorrect executions through
                 roll-backs. Because all memory references access the
                 speculative storage, current proposals implement
                 speculative storage using small memory structures to
                 achieve fast access. The limited capacity of the
                 speculative storage causes considerable performance
                 loss due to speculative storage overflow whenever a
                 thread's speculative state exceeds the speculative
                 storage capacity. Larger threads exacerbate the
                 overflow problem but are preferable to smaller threads,
                 as larger threads uncover more parallelism. In this
                 article, we discover a new program property called
                 memory reference idempotency. Idempotent references are
                 guaranteed to be eventually corrected, though the
                 references may be temporarily incorrect in the process
                 of speculation. Therefore, idempotent references, even
                 from nonparallelizable program sections, need not be
                 tracked in the speculative storage, and instead can
                 directly access nonspeculative storage (i.e.,
                 conventional memory hierarchy). Thus, we reduce the
                 demand for speculative storage space in large threads.
                 We define a formal framework for reference idempotency
                 and present a novel compiler-assisted speculative
                 execution model. We prove the necessary and sufficient
                 conditions for reference idempotency using our model.
                 We present a compiler algorithm to label idempotent
                 memory references for the hardware. Experimental
                 results show that for our benchmarks, over 60\% of the
                 references in nonparallelizable program sections are
                 idempotent.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
}

Related entries