Project 4: Instruction selection

Project 4
Objective:
~~~~~~~~~~

Learn how to reason about the impact of instruction selection on performance


Deliverables:
~~~~~~~~~~~~~

You're asked to make an educated guess about the expected performance of
a program, finish its implementation, then explain the actual performance.

- edit the file named GUESS and try to guess the missing information. Your
score will not depend on your guess.

- finish the implementation

- edit the file named EXPLAIN and do your best to explain the actual results.

Assignment:
~~~~~~~~~~~

You need to finish the implementation of two x86-32 assembly functions:
"count1" and "count2"

int count1(int array[], int size, int limit);
int count2(int array[], int size, int limit);

Where:

array is an array of integers
size specifies the number of integers in the array
limit is some integer value

Both count1 and count2 return the number of array elements that are less
than the given limit.

Restrictions:
~~~~~~~~~~~~~

count1 is not allowed to use the "cmov" family of instructions

count2 can have a maximum of one conditional jump in its implementation and
is required to use a "cmov" instruction in its implementation


The test driver
~~~~~~~~~~~~~~~

The test program fills a large array with random values between 0 and 9 then
calls your test functions with limits of 0, 1, 2, ..., 10.

It then prints a table that shows:

- the limit
- ratio of array elements that are less than limit
- an estimate for the number of nano-seconds per iteration in your
implementation


To compile:
~~~~~~~~~~~

make

To run test:
~~~~~~~~~~~~

make clean test

To make the output less noisy:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

make -s clean test

To run by hand
~~~~~~~~~~~~~~

make
./main


Correct output:
~~~~~~~~~~~~~~~

A correct implementation will produce output similar to the following. The
question marks will have values specific to your imlpementation.

without cmov
value ratio ns/iteration
0 0.00 ?
1 0.10 ?
2 0.20 ?
3 0.30 ?
4 0.40 ?
5 0.50 ?
6 0.60 ?
7 0.70 ?
8 0.80 ?
9 0.90 ?
10 1.00 ?

with cmov
value ratio ns/iteration
0 0.00 ?
1 0.10 ?
2 0.20 ?
3 0.30 ?
4 0.40 ?
5 0.50 ?
6 0.60 ?
7 0.70 ?
8 0.80 ?
9 0.90 ?
10 1.00 ?