# Exercises 2

Deadline 2025-11-03 23:59

All filenames refer to the g0.complang.tuwien.ac.at.  You should
perform your measurements on this machine.

## Submission

Following the Setup below will give you a directory 2 in a working
directory of your git project, containing `Exercises2.txt` and other
files.

Answer the questions by editing `Exercises2.txt` with a text editor,
inserting parts of the transcript where needed.  For answers where the
supporting evidence is longer, put the supporting evidence in a file
(or several) in the same directory.  Don't forget to commit and push
the directory and the relevant files before the deadline.

Please do not just answer the questions, but document how you arrived
at the answers (this is also useful for preparing yourself for the
interview part of the exam later in the semester).  A good way to do
that for some questions is to provide transcripts of your shell
sessions.  You can either cut-and-paste the text from the terminal
session, or use `script -f <filename>` to write the transcript to the
named file (and then copy parts of this transcript into your
`Exercises2.txt`).

## Setup

`cd` into a working directory of your git project for Efficient
Programs on the course machine.  Perform

````
unzip /nfs/a5/anton/pub/anton/lvas/efficient/25/2.zip
git add 2
````

The directory 2 contains `Exercises2.txt` (fill in the answers there)
and the files mentioned below and a `Makefile`.

`make` now measures 100,000,000 iterations of one the loops in each of
the functions in e2work1.c.

For the modifications below, you must not change the source code of
the data structures, the number of iterations, `e2main1.c`, or the
fact that each instance of the data structures is visited once by each
call to the functions in `e2work1.c`.  Your changes may modify the
payload during execution and may change the result of the computation.
You should add code that is executed on each iteration.  You may add
setup code worth up to 20 cycles or 20 instructions in each of the
functions of e2work1.c, but the lion's share of the additional cycles
or instructions should come from the additional code in the loop
bodies.

Note that computations in the C code that are not used (and where the
compiler can determine that) will not result in instructions in the
executable code.

The goal of this exercise is that you get hands-on experience on how
latency and bandwidth (in this case instruction execution bandwidth)
influence performance.

## Q1

Modify `list1()` to execute as many instructions:u as you can manage
without exceeding 600,000,000 cycles:u.  How many instructions:u does
the result execute?

## Q2

Modify `array1()` to perform the computations corresponding to your
new list1()`.  How many cycles:u does your new `array1()` take?

## Q3

Modify `array2()` to consume as many cycles:u as you can manage
without exceeding 810,000,000 instructions:u.  How many cycles:u does
your new `array2()` take?

## Q4

Modify `list2()` to perform the computations corresponding to your new
`array2()`.  How many cycles:u does your new `list2()` take?