CS740: Computer Architecture, Fall 2000

Prefetching Set Hints

Project Milestone Report

Group Info:

Project Webpage:

Major Changes:

While the main goal of our project is still to explore the placement of prefetched data lines into set-associative cache, our implementation approach is slightly shifted since the initial project proposal. Originally we planned to:
  • modify the simulator to accomodate for cache partitioning
  • implement logic to determine whether a piece of data has good or bad locality
  • add the hardware to remember the type of data for future predictions
  • show whether this is useful by running SPEC benchmark suite and real applications
After reviewing the above strategy with Todd, we found out that there already exists a simulator that implements the prefetch set hint (cello); we thus decided to focus our attention on finding applications (or general categories of applications/algorithms) that may exploit the benefit of prefetch set hints. As a result of this shift in implementation approach, our milestone has been appropriately adjusted to reflect the change. See the "meeting milestone" section below for details.

Accomplishments:

So far we have been able to:

  • Literature search on MIPS R10000 processor (see resources section below)
  • Literature search on MPEG-1 and MPEG-2 video (see resources section below)
  • Obtain the simulator (Cello), figure out how to set cache options, and compile it
  • Obtain an open-source MPEG-1/MPEG-2 video decoder program (mpeg2play), familiarize with the code, and compile it
  • Identify how set hints may be useful in MPEG video decoding: how to partition data into streamed and retained sets
  • Determine the prefetch distance to be between 
    memory latency (T) / CPI ~ 2 * memory latency (T) / CPI
  • Modify mpeg2play C source to produce three versions of assembly code that contains:
    • No prefetch instructions
    • Prefetch instructions without set hints
    • Prefetch instructions with set hints

Meeting Milestone:

As mentioned above, our milestone has been adjusted to reflect the new implementation approach. The new milestone is to research on an application that may benefit from the prefetch set hint, and simulate it to get cache behavior details. We simulated a mpeg-2 decoder program (mpeg2play) on an MIPS simulator (cello), but obtained some perplexing results (see surprises section below).

Surprises:

The cache miss rates for the three versions of mpeg2play (no prefetches, prefetches without hints, and prefetches with hints) come out to be exactly the same. We have confirmed that the prefetch instructions are indeed in the binary executable; however, they are ignored by the simulator for some reason.

Revised Schedule:

- SoYoung Brenda
11/20-12/1
  • Literature search on mp3 audio format as possibly another application that could exploit set hints
  • Apply the same method to insert prefetch instructions into the decoder
  • Investigate mpeg2play result
  • Simulate mpeg2play with different parameters and evaluate results
12/1-12/4 Work on report
12/4 Project due
12/4-12/11 Work on poster
12/11 Poster session

Resources Needed:

Papers:
  • MIPS R10000 Microprocessor User's Manual (Version 2.0). SGI. October 1996.
  • Peter Soderquist and Miriam Leeser. Optimizing the Data Cache Performance of a Software MPEG-2 Video Decoder. In ACM Multimedia, 1997
  • Didier Le Gall. MPEG: A Video Compression Standard for Multimedia Applications. In Communications of the ACM Vol. 34, No. 4, April 1991
  • T. Sikora. MPEG Digital Video Coding Standards. In Digital Electronics Consumer Handbook McGraw Hill Company, 1997
Programs:
  • Stefan Eckart (stefan@lis.e-technik.tu-muenchen.de). mpeg2play (Version 1.1b), July 13, 1994.
  • Cello (Revision 2.23), October 18, 2000.
  • Mint (Version 4), SandCraft Inc., 1998
 1