CS 5513 Fall 2011, Topics for Class Projects

• Branch prediction contest. This project is available only to individuals, not groups. For this project you will write C++ code to simulate a conditional branch predictor. The individual with the most accurate branch qualifying predictor will receive a special award to be determined later. You will work within a coding framework provided by the professor. This framework includes your code and tests your predictor against benchmarks traces, measuring accuracy as the number of incorrectly predicted conditional branches per 1000 instructions (MPKI). The entry with the lowest MPKI and code that meets the specifications of the contest will win. Choose a conditional branch predictor paper from the recent computer architecture literature, i.e. no earlier than 2000, and in a good venue like ISCA, MICRO, HPCA, ASPLOS, PACT, or ICS. Working within the framework provided by the professor, code a simulator for this branch predictor. Do not use code you find on the Internet; design your own code from the specifications in the technical papers. You may make additional enhancements to the predictor design, but the basic predictor must be recognizable as having come from the paper you have chosen. There will be constraints on your code in terms of resource usage: you may not use more than a certain amount of storage and the code must be reasonably efficient so that we can run it on a large set of traces quickly; more details about this will come soon. For this project, the final product that you will turn in will be a writeup, in your own words, describing in detail the predictor and the steps you took to implement the simulator. You will also turn in your well-documented C++ code, which should compile under the distributed framework. Your code will be tested to determine the accuracy of your predictor. See this page for details of the competition as well as code you can use to get started.
• Characterize the static and dynamic behavior of a significant benchmark suite based on compiler optimization levels. Obtain the SPEC CPU benchmarks and compile them with three or more different levels of optimization, preferably with two or more different compiler infrastructure (e.g. gcc vs. icc). For each combination of compiler and optimization level, give the following statistics:
  • The size of the program executable.
  • The amount of time it takes to execute a program.
  • The speedup over a baseline optimization (e.g. -O0).
  • The number of page faults incurred.
  • The number of basic blocks in the program.
  • The number of basic blocks actually reached in the program.
  • The number of basic blocks that were executed more than 1000 times.
  • The depth of the call graph, i.e., the maximum number of procedure calls active simultaneously.
  • Other information that has an impact on program behavior that you might think would be interesting to study.
  For some of these statistics you will need to compile the benchmarks using profiling instrumentation, e.g. gcc -pg. Your writeup should give the numbers in an easy-to-read format e.g. bar charts, and explore interesting features of the numbers. Your writeup should have the format of a conference-quality paper and give recommendations for compilers and compiler options for particular benchmarks or groups of benchmarks. One benefit of this project is that you will gain experience in working with a benchmark suite and all the details that go into that.
• Explore the effect of adding a new instruction to an existing ISA. Find a cycle-accurate microarchitectural simulator, such as SimpleScalar, on the Internet. Add a new instruction to the simulator. Find a compiler on the Internet, such as GCC. Get the compiler to use the new instruction. Alternately, write a post-processing pass that modifies the output of the compiler to use the new instruction. Explore the effect of the new instruction on performance (or some other interesting metric) using a set of benchmarks.
• Choose some paper from a recent architecture conference and reproduce the results. You should choose a paper from one of MICRO, ISCA, ASPLOS, PACT, HPCA, or ICS. Choose a paper from no earlier than 1995. You needn't use the same exact methodology (i.e., simulator, benchmark suite, etc.), but try to be as faithful as possible to the methodology outlined in the paper. Are your results consistent with those in the paper? If you like, explore your own ideas to improve the results. For this topic, you must discuss the paper with the professor and receive his approval before turning in the proposal.
• Propose your own topic; discuss this with the Professor.