LAB 12 QUESTIONS SOLUTION

$35.00 $30.80

Description

– Name: Tanner Hobbs

– NetID: Hobbs131

 

Answer the questions below according to the lab specification. Write

your answers directly in this text file and submit it to complete the

lab.

 

 

PROBLEM 1: Timing Benchmarks

============================

 

The code in `reversal.c’ implements two functions which reverse the

elements of an array. They take markedly different approaches.

,—-

| void reverse_arr1(int *arr, long size){

|   int *tmp = malloc(sizeof(int)*size);

|   for(long i=0; i<size; i++){

|     tmp[i] = arr[size-i-1];

|   }

|   for(long i=0; i<size; i++){

|     arr[i] = tmp[i];

|   }

|   free(tmp);

| }

|

| void reverse_arr2(int *arr, long size){

|   for(long i=0; i<size/2; i++){

|     int tmp = arr[i];

|     arr[i] = arr[size-i-1];

|     arr[size-i-1] = tmp;

|   }

| }

`—-

 

 

(A) Predictions

~~~~~~~~~~~~~~~

 

Predict which of these two functions will run faster based on their

code characteristics.

 

Function reverse_arr2 will run faster because less instructions are required. Two for loops are ran through at n iterations in the first method whereas in the second only one for loop is ran for n/2 iterations

(B) Timing

~~~~~~~~~~

 

Modify the provided `reversal.c’ file to perform timing calculations

on the two functions as they are called on different sizes of arrays.

Print runtimes in a tabular format.

 

Paste the C code you wrote below to show you how you timed the

function runs.

 

clock_t begin, end;

double cpu_time1;

double cpu_time2;

begin = clock();

reverse_arr1(arr1,size);

end = clock();

cpu_time1 = ((double) (end – begin)) / CLOCKS_PER_SEC;

printf(“cpu time reverse_arr1: %.4e   “, cpu_time1);

 

 

begin = clock();

reverse_arr2(arr2,size);

end = clock();

cpu_time2 = ((double) (end – begin)) / CLOCKS_PER_SEC;

printf(“cpu time reverse_arr2: %.4e   \n”, cpu_time2);

 

 

(C) Analysis

~~~~~~~~~~~~

 

Paste the table of numbers your code produced for timing the two

reversal functions. Describe if the one you predicted would be faster

actually was measured to be faster.

 

cpu time reverse_arr1: 2.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 2.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 1.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 2.0000e-06   cpu time reverse_arr2: 1.0000e-06

cpu time reverse_arr1: 1.0000e-05   cpu time reverse_arr2: 2.0000e-06

cpu time reverse_arr1: 7.0000e-06   cpu time reverse_arr2: 2.0000e-06

cpu time reverse_arr1: 9.0000e-06   cpu time reverse_arr2: 4.0000e-06

 

The one I predicted to be faster seems to be faster

 

 

PROBLEM 2: ax then xpy VS axpy

==============================

 

Examine the timing code in `axpy.c’. Consider the 3 functions `ax()’,

`xpy()’, and `axpy()’.  Note that these are timed in `main()’ as

follows.

,—-

| // start timing 1

|     ax(a,x1,size);

|     xpy(x1,y,size);

| // stop timing

|

| // start timing 2

|     axpy(a,x2,y,size);

| // stop timing

`—-

This is because the first two functions together do what `axpy()’

does.

 

Note also that `axpy()’ has two “fairness” loops which do affect the

results but compensate for the fact that the previous two functions

combined have two loops.

 

Time these functions using the provided code. Explain the results you

observe and if one appears to be faster than the other, describe what

features of the processor and memory architecture might be affecting

the timings.

 

axpy seems to be slightly faster than ax and xpy together. This may be because the scaling of the array and the addition of arrays operations are done simultaneously in the for loops thus reducing the amount of instructions handled.

 

 

PROBLEM 3 (OPTIONAL): Profiler

==============================

 

This problem demonstrates the utility of a performance *profiler* to

help locate “hot spots” in code which take most of the run time

associated with it.

 

Change into the directory `warsim’ that is part of the lab code

distribution.  The code contained within it implements a simple

simulation of the card game War.  The details of the game are not

important except that the program simulates playing of the game then

reports statistics on it.

 

First compile the program by using the provided Makefile.

,—-

| > make

| gcc -Og -g -pg -no-pie -c libwar.c

| gcc -Og -g -pg -no-pie -c libcardlist.c

| gcc -Og -g -pg -no-pie -o warsim warsim.c libwar.o libcardlist.o

`—-

Notice that the option `-pg’ is passed in which will enable

/profiling/ of the code. The `-no-pie’ option is present in case a

buggy version of `gcc’ is present and has no significant effect.

 

Run the resulting `warsim’ program as follows.

 

,—-

| # show usage

| > ./warsim

| usage: ./warsim cardfile ngames [logfile]

|

| # simulate 10 games

| > ./warsim full.deck 10

| ———————-

| Final stats

|   0.60 P1 Win Ratio

| 408.50 Avg battles per game

|  30.30 Avg wars per game

|

| # simulate 100 games

| > ./warsim full.deck 100

| ———————-

| Final stats

|   0.54 P1 Win Ratio

| 301.56 Avg battles per game

|  22.94 Avg wars per game

|

| # simulate 2000 games

| > ./warsim full.deck 2000

| ———————-

| Final stats

|   0.54 P1 Win Ratio

| 298.48 Avg battles per game

|  22.79 Avg wars per game

`—-

 

This last run might take a few seconds as 2000 games are simulated.

 

After the runs are finished, the file `gmon.out’ appears. This is an

output file that is generated on running programs with profiling

enabled.

,—-

| > ls gmon.out

| gmon.out

| > file gmon.out

| gmon.out: GNU prof performance data – version 1

`—-

 

The contents of the file are binary and must be interpreted by the

program `gprof’.  Use the `-b’ option to show “brief” output and pass

in the name of the program that was run.

,—-

| > gprof -b warsim

| Flat profile:

|

| Each sample counts as 0.01 seconds.

|   %   cumulative   self              self     total

|  time   seconds   seconds    calls  ms/call  ms/call  name

|  50.11      0.06     0.06  2387860     0.00     0.00  print_list

|  25.06      0.09     0.03 32507650     0.00     0.00  card2str

|   8.35      0.10     0.01   596965     0.00     0.00  end_battle

|   8.35      0.11     0.01     4000     0.00     0.00  new_stack

|   8.35      0.12     0.01       52     0.19     0.19  str2card

|   0.00      0.12     0.00  8073378     0.00     0.00  stack_empty

|   0.00      0.12     0.00  6656812     0.00     0.00  queue_empty

|   0.00      0.12     0.00  3944508     0.00     0.00  stack_top

|   0.00      0.12     0.00  1675522     0.00     0.00  queue_add

|   0.00      0.12     0.00  1675522     0.00     0.00  queue_remove

|   0.00      0.12     0.00  1571470     0.00     0.00  queue_front

|   0.00      0.12     0.00  1465470     0.00     0.00  stack_pop

|   0.00      0.12     0.00  1465470     0.00     0.00  stack_push

|   0.00      0.12     0.00   596965     0.00     0.00  start_battle

|   0.00      0.12     0.00     6001     0.00     0.00  new_queue

|   0.00      0.12     0.00     6001     0.00     0.00  queue_free

|   0.00      0.12     0.00     4000     0.00     0.00  stack_free

|   0.00      0.12     0.00     2000     0.00     0.00  deal2

|   0.00      0.12     0.00     2000     0.00     0.06  playwar

|   0.00      0.12     0.00     2000     0.00     0.00  queue_copy

|   0.00      0.12     0.00     2000     0.00     0.00  queue_rotate

|   0.00      0.12     0.00        1     0.00    10.02  read_deck

| …

`—-

 

The first part of the output shows a breakdown of how much time was

spent in each function associated the most recent run of the program.

 

Analyze this breakdown and make suggestions as to where optimization

effort might best be spent to increase the speed of warsim.