CSE 240 -- Principles in Computer Architecture

• H&P problems 1.2, 1.4, 1.6, 1.7, 1.13

•  H&P problems 2.1, 2.3, 2.8, 2.10, 2.11
• Mini-project #1:

      In this mini-project, you will investigate some DLX programs in regards
to how they use the DLX ISA. You will run two SPEC programs compiled for
the DLX architecture. They can be found in /cse/class/fa98/cse240/simulator/execs,
along with their inputs. The simulators themselves can be found in /cse/class/fa98/cse240/simulator/bin.
There should be enough info in the execs README file to run the simulations.
Some of the files may be large, so you should create a directory with links
to the executables and input files in the execs directory instead of copying
them.

Run two programs, li (xlisp) and compress, unoptimized
versions, the ones without .opt) with the sim-profile simulator and the
-iprof, -amprof, and -brprof options(or more; -h will show you all the
options), to get information on instruction, branch and addressing mode
usage. List the 15 most frequent instructions in the two benchmarks (just
average the frequencies for the two). Based on this data, plus other things
you observe from the output (e.g., branch and addressing usage), postulate
three things you expect to be different when you run the optimized versions.
Run the optimized versions and see if your theories were correct. Explain.
(I don't care if you were right, just whether you do a good job of analyzing
why you were right or wrong). Also note, I expect your theories to be less
obvious than "fewer instructions will be executed."

If you want to theorize about how CPI changes with optimization, you
can also use an alternate simulator (sim-outorder -issue:inorder) to get
timing information on an in-order superscalar machine. These simulations
take quite a bit longer, but are certainly doable.

The following may be useful in your analysis if you are ambitious. Sources
for the programs are in ~cse240/simulator/src. A disassembler is in the
bin directory. You run it with objdump --disassemble objfilename

All of the simulators in the bin directory are from the simplescalar
tools, by Todd Austin and Doug Burger. You may notice that the ISA for
the simulator/executables is actually a superset of DLX, so there may be
some operations you don't recognize.

•  H&P problems 3.1, 3.2c, 3.3abc*e.

*Problem 3.3c. Specify all data forwarding that MIGHT be needed, but not in the format of Figure 3.19. Just use a pipeline figure like is already in Problem 3.3 and draw arrows on it. Do two diagrams, with each of the two instruction types being the last instruction in one of the diagrams; assume all instructions before the last could be either type. Then draw all possible forwarding paths (to ALU inputs) TO the last instruction from other instructions.
• WS1. Surf the web and find the length of the integer pipeline in the following machines: Pentium, Pentium Pro, Alpha 21164, MIPS R10000. Give the full pipeline description (names of all stages) for one of those machines.

• H&P 3.8, 3.9, 4.1, 4.3, 4.4, 4.7
• WS2. Surf the web (or whatever other source you may have) and tell me which of the following processors are dynamically scheduled (issue instructions out-of-order) and which are not (i.e., which have in-order issue): MIPS R10000, Sun UltraSparc, Alpha 21264, Pentium, Pentium Pro.
• Mini-project #2: Branch Evaluation
• Part 1. For this part you will profile our two programs (compress.opt and xlisp.opt) to find the number and percentage of conditional branches that are forward vs. backward branches. And for each of those, find the percentage that are taken vs. not-taken. To do this, you will have to modify the simulator, the code for which can be found in the class directory in the subdirectory simplesim-2.0. You should only have to modify two routines in the file sim-profile.c and 'make sim-profile.' You need simply put a few counters in sim-main(), and put some statements to print (actually, use fprintf(stderr, ...) ) the results in sim_aux_stats(), which will get run after the program completes. Which type of branch is easiest to predict for these programs? Which is more important to predict? In addition to the results and analysis, just turn in your sim-main() routine, with modifications highlighted.
 
• Part 2. Here we will examine the implications of the branch hazard delay (a.k.a. misprediction penalty). For this you will use the sim-outorder simulator unmodified. You specify the branch misprediction penalty with '-fetch:mplat n', where n is an integer. Run the two programs with misprediction penalties of 1, 5, and 15 cycles for each of the following machines: out-of-order superscalar (simulator default), in-order superscalar (-issue:inorder), and an in-order scalar (-issue:inorder -fetch:ifqsize 1). A scalar machine issues one instruction at a time. For which machine is branch misprediction latency most critical to performance? These simulations do take a little while to run. You may want to make a script to run overnight.

• H&P 4.10, 4.14a,c,d, 4.20.
• How many instuctions can the following machines execute in one cycle: Pentium Pro, MIPS R10000, Alpha 21264?

Hennessy & Patterson
• - either 5.3 or 5.2a,b,c,d,h. The latter will be more trouble, but a lot more interesting.
• - 5.4
• - 5.5 -- assume that you do nothing fancy on a miss to a dirty line; the dirty line is written to memory, then the read miss is processed.
• - 5.7 -- assume whatever mechanism you use to avoid the swap does not change the miss rates at all, either to the whole cache, or the fast side.
• - 5.8a

Web Surf -- Tell me the configuration (e.g., size, associativity, block size, write-through/write-back) of all on-chip caches for the following machines: Alpha 21164, Pentium Pro, MIPS R10000

Mini-project #3 -- In this project, I expect you to take over the burden of designing the experiments. That is, I want you to propose hypotheses, design experiments, analyze results, and possibly run more experiments if the analysis/results leave unanswered questions. When you're done you should both give me the answer and some insight into the "why." For each of the two questions, start with the default cache configuration and machine configuration in sim-outorder as the baseline. The two questions, which should be examined separately, are:

1. Does the cache miss latency have a bigger impact on performance in a dynamically scheduled processor, or an in-order processor? (Just consider the L1 data cache miss latency).

2. If a 2-way set-associative cache (first-level data cache) requires a 5% longer cycle time than direct-mapped, and 4-way 10% longer (than DM), which of the three cache configurations gives us better performance, on average, for the two programs for that cache?

If you have comments or suggestions, email me at tullsen@cs.ucsd.edu