Description
Answer the questions below according to the lab specification. Write
your answers directly in this text file and submit it to complete the
lab.
Important: Don’t Run on Vole
============================
Vole is a virtualized environment which means measuring the runtime of
codes will be very unpredictable on it.
Favor a “real” machine like a physical lab machine, laptop, or a
remote login to apollo.cselabs.umn.edu. To run the codes remotely,
log in via the ssh tool as in
,—-
| > ssh kauf0095@apollo.cselabs.umn.edu
`—-
Use your X.500 username/password to get access. All CSE labs machines
share the same home directory so any code you download to Vole or a
physical lab machine will be available on all machines.
Compiling and Timing
====================
IMPORTANT: Use the provided Makefile to compile as in
,—-
| > make
| gcc -Wall -g -Og -c superscalar_main.c
| gcc -Wall -g -Og -c superscalar_funcs.c
| gcc -Wall -g -Og -o superscalar_main superscalar_main.o superscalar_funcs.o
`—-
The compilation uses `-Og’ (debug level optimization) which is
necessary to stop the compiler from modifying some loops.
This will produce the `superscalar_main’ program which has the
following usage:
,—-
| > ./superscalar_main
| usage: ./superscalar_main <ALG> <MULT> <EXP>
| <MULT> and <ALG> are integers, iterates for MULT * 2^{EXP} iterations
| <ALG> is one of
| add1_sep : add 1 times in loop
| add2_sep : add 2 times in same loop; separate destinations
| add3_sep : add 3 times in same loop; separate destinations
| add2_same : add 2 times in same loop; same destinations
| mul1_sep : multiply 1 times in loop
| mul2_sep : multiply 2 times in same loop; separate destinations
| mul3_sep : multiply 3 times in same loop; separate destinations
| mul2_same : multiply 2 times in same loop; same destinations
| add_and_mul_sep : add and multiply in the same loop; separate destinations
| add_and_mul_same : add and multiply in the same loop; same destination
| add_then_mul_sep : add and multiply in different loops; separate destinations
| add_then_mul_same : add and multiply in different loops; same destinations
`—-
Experiment with algorithm `add1_sep’ and parameters `MULT’ and `EXP’
which control the number of iterations run. Experiment until you get a
run time of about 1 second such as MULT=1 and EXP=30 on apollo.
,—-
| apollo> time ./superscalar_main add1_sep 1 30
| add1_sep for 18 * 2^{27} = 2415919104 iterations… complete
|
| real 0m1.071s
| user 0m1.040s
| sys 0m0.008s
`—-
PROBLEM 1: Addition
===================
(A) add1_sep / add2_sep / add3_sep
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Examine the source code in `superscalar_funcs.c’ for the following
algorithms.
– add1_sep : add 1 times in loop
– add2_sep : add 2 times in same loop; separate destinations
– add3_sep : add 3 times in same loop; separate destinations
Note that each does some additions in a loop. Time each of these WITH
THE SAME MULT/EXP parameters and show your timings. Describe how the
timings compare and speculate on why.
Note that all of these involve incrementing a counter (`i++’) so the
number of additions is one greater than the algorithm name suggests.
(B) add2_sep / add2_same
~~~~~~~~~~~~~~~~~~~~~~~~
Compare the source code of the two algorithms below.
– add1_sep : add 1 times in loop
– add2_sep : add 2 times in same loop; separate destinations
– add2_same : add 2 times in same loop; same destinations
Note that the only difference between the add2_X algorithms is that
the destination for the results.
Compare timings for these and speculate on the reasons for any
unexpected results.
PROBLEM 2: Multiplication
=========================
(A) add1_sep / mul1_sep
~~~~~~~~~~~~~~~~~~~~~~~
Compare the following two algorithms.
– add1_sep : add 1 times in loop
– mul1_sep : multiply 1 times in loop
Time them on the same parameters and speculate on the timing
differences.
(B) mul1_sep / mul2_sep / mul3_sep
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Compare the following two algorithms.
– mul1_sep : multiply 1 times in loop
– mul2_sep : multiply 2 times in same loop; separate destinations
– mul3_sep : multiply 3 times in same loop; separate destinations
Time them on the same parameters and speculate on the timing
differences.
(C) mul1_sep / mul2_sep / mul2_same
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Compare the following two algorithms.
– mul1_sep : multiply 1 times in loop
– mul2_sep : multiply 2 times in same loop; separate destinations
– mul2_same : multiply 2 times in same loop; same destinations
Time them on the same parameters and speculate on the timing
differences.
PROBLEM 3: Combined Addition/Multiplication
===========================================
(A) add1_then_mul_sep / add2_and_mul_sep
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Compare the following two algorithms.
– add1_then_mul_sep : add and multiply in different loops; separate
destinations
– add2_and_mul_sep : add twice and multiply in the same loop; separate
destinations
Note that each loop involves incrementing a counter so both of the
above algorithms should do the same number of operations for N
iterations:
———————————————
loop total total
Algorithm incr adds adds mults
———————————————
add1_then_mul_sep 2*N 1*N 3*N N
add2_and_mul_sep 1*N 2*N 3*N N
———————————————
Time these algorithms on the same parameters and speculate on the
timing differences.
Compare the timings to your earlier results for add1_sep and mul1_sep.
(B) add2_and_mul_sep / add2_and_mul_same
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Compare the following two algorithms.
– add_and_mul_sep : add and multiply in the same loop; separate
destinations
– add_and_mul_same : add and multiply in the same loop; same
destination
Time them on the same parameters and speculate on the timing
differences.
(C)
~~~
Part A time the following algorithms which modified SEPARATE memory
locations:
– add1_then_mul_sep : add and multiply in different loops; separate
destinations
– add2_and_mul_sep : add twice and multiply in the same loop; separate
destinations
Time the following two algorithms which modify the SAME memory
location.
– add1_then_mul_same : add and multiply in different loops; same
destinations
– add2_and_mul_same : add twice and multiply in the same loop; same
destination
As before the operation count is the same but in this case the
destination for adds/multiplies is the same.
Explain time similarities or differences between these SAME algorithms
and their SEPARATE equivalents from part A.
PROBLEM 4: Quote Binary Debugging
=================================
This problem continues to review debugging techniques for situations
in which no source code is present. It is relevant to defusing the
binary bomb.
The two files `quote_main.c’ and `quote_data.o’ can be compiled
together to form an executable as in the following.
,—-
| > gcc quote_main.c quote_data.o
|
| > a.out
| Complete this sentence by C++ creator Bjarne Stroustrup:
| C makes it easy to shoot yourself in the foot; …
|
| enter a number from 0 to 15: 2
|
| 2: Java prevents you from shooting yourself in the foot by cutting off all your fingers.
|
| Have a nice tall glass of … NOPE.
`—-
As in a previous exercise, the intention is to use the debugger to
detect the correct response. In this case however, the correct
completion is present in `quote_main.c’. However, one must enter a
number which selects from several responses in an attempt to match the
correct completion. It is possible to “brute force” the solution by
trying all solutions. However, the intent of the activity is to
explore the running code with the debugger to answer the questions
below. This will give insight into some stages of the binary bomb
assignment.
A
~
Use some binary utility programs to print out the symbols that are
present in `quote_data.o’. Review the previous lab if you have
forgotten which programs can print symbols in a binary object file.
Speculate as to which data might pertain to where potential options
are stored.
B
~
The entry point into the assembly code in `quote_data.o’ is the
function `get_it’. Use either the debugger or a disassembly of the
object to trace whether this functions performs the entire computation
or if other functions are also used. Use this along with other
observations of the content of the `quote_data.o’ file to infer what
kind of structure the choices are stored in.
C
~
Use the debugger to step through the functions in `quote_data.o’.
Keep in mind that the parameters to the function follow the standard
convention: 1st param in register `%rdi’, second in `%rsi’, and so
forth. You should be able to identify a loop in a critical function
in which the choices are present. Use `print’ and `x’ commands in gdb
to examine data pointed to be registers to help identify where the
correct response is located.
Recall that you can examine memory addresses pointed to registers with
gdb commands like the following.
,—-
| (gdb) x/d $rax # print memory pointed to by rax as a decimal integer
| (gdb) x/x $rax # print memory pointed to by rax as a hex number
| (gdb) x/s $rax # print memory pointed to by rax as a string
`—-
Include what debugger techniques you used in your answer along with
the index of the correct completion.
