DESCRIPTION

Students:  Please note instructions in paper copy of quiz.  Save your
files often, make sure OMSI fills your entire screen at all times, etc.

A question may not fully fit into your OMSI question box, which is not
scrollable.  You can try adjusting the relative size of the question and
answer boxes, but remember that clicking CopyQtoA will copy the entire
question box to the answer box.

In questions involving code which will partially be given to you in the
question specs, you may need add new lines.  

QUESTION

Fill in the blanks:  The code on p.115 will be compiled to
_________________ machine language, while that on p.114 will be compiled
to __________________ machine language.

QUESTION 

Consider the example in Sec. 4.11 of our book. (This question is
independent of the next one.) As noted in class, the code in that
example is valid only if the function is monotonic.  State the specific
modifications that would be needed to allow it to be nonmonotonic but
still continuous, in which case it may have multiple roots.

QUESTION

Consider the example in Sec. 4.11 of our book. (This question is
independent of the previous one.)  Suppose someone is considering adding the
line

#pragma omp for

just before line 38.  Would this be helpful, harmful or neither?
EXPLAIN.

QUESTION -ext .c -com gcc -flags '-fopenmp' -run ./omsi_answer4

The program partially given below has the same goal as the example in Sec.
4.13 of our book, except that now we do not require lexicographic order.
Complete the code.


// takes a graph adjacency matrix for a directed graph, and converts it
// to a 2-column matrix of pairs (i,j), meaning an edge from vertex i to
// vertex j; the rows of the output matrix can be in any order

#include <omp.h>
#include <stdlib.h>
#include <stdio.h>

// arguments:
//    adjm:  the adjacency matrix (NOT assumed symmetric), 1 for edge, 0
//           otherwise; note: matrix is overwritten by the function
//    n:  number of rows and columns of adjm
//    nout:  output, number of rows in returned matrix actually used
// return value: 
//    pointer to the converted matrix

int *transgraph(int *adjm, int n, int *nout)
{  
   int *outm = malloc(2 * n*n * sizeof(int));  // worst-case size
   // outm to become the output matrix
   int nextoutmrow = 0;  // number of next row to be written to outm
   #pragma omp parallel
   {  int i,j;
      int me = omp_get_thread_num(),
          nth = omp_get_num_threads();
      int myrows[2];  // range of input rows for my thread to process
      int myoutmrow;  // current row in outm that I will writ
      findmyrange(n,nth,me,myrows); 
      // I will write a row to outm for each input 1 in my range of rows;
      // but first, how many rows will I write?
      int mynum1s = 0;

      // now write my rows of outm
      for (i = myrows[0]; i <= myrows[1]; i++) {
         for (j = 0; j < n; j++) 
            if (adjm[n*i+j] == 1) {
               outm[2*myoutmrow] = i;
               outm[2*myoutmrow+1] = j;
               myoutmrow++;
            }
      }
      #pragma omp barrier
   }
   *nout =    ;
   // give back the unused part of outm
   realloc(outm,2*nextoutmrow*sizeof(int));
   return outm;
}

int main()
{  int i,j;
   int *adjm;
   int n = 4;
   int nout;
   int *outm;
   omp_set_num_threads(2);
   // random test input
   adjm = malloc(n*n*sizeof(int));
   for (i = 0; i < n; i++)  {
      for (j = 0; j < n; j++) {
         adjm[n*i+j] = (i*j*j+1) % 2;
         printf("%d ",adjm[n*i+j]);
      }
      printf("\n");
   }

   outm = transgraph(adjm,n,&nout);

   // check results
   for (i = 0; i < nout; i++) 
      printf("%d %d\n",outm[2*i],outm[2*i+1]);
}

// finds chunk among 0,...,n-1 to assign to thread number me among nth
// threads
void findmyrange(int n,int nth,int me,int *myrange)
{  int chunksize = n / nth;
   myrange[0] = me * chunksize;
   if (me < nth-1) myrange[1] = (me+1) * chunksize - 1;
   else myrange[1] = n - 1;
}