Errata for Principles of Parallel Programming

Corrections Solicited

The list below contains all of the errors found to date for first printing of the First Edition of Principles of Parallel Programming. These errors have been corrected in the second printing of the first edition; to check whether you have the second printing, check the last line of page ii, which should end with the letters "V0CR--13 12 11". If you discover an error that is not in this list, please send it to

lin AT cs DOT utexas DOT edu
    and/or
snyder AT cs DOT washington DOT edu
We will be very appreciative, as will your fellow readers.

Acknowledgments

We wish to express our sincere gratitude to the following readers for their contributions: Greg Byrd, William Gardner, Evan Herbst, Edin Hodzic, David Jefferson, Vincent Liu, Anton Lokhmotov, Jeff Lowney, Rami Melhem, Vlad Roubtsov, Vivek Sarkar, and Julia Schwarz.

Errata

  • p. 23 In Figure 1.14, line 17 should read:
    17    private_count[id].value++;

  • p. 45 Figure 2.9 (b) lines 8-12 should read:
     8 {
     9   location=mid;
    10   break;
    11 }
    12 if(A[mid]>searchee)
    13   hi=mid;
    14 else
    15   lo=mid+1;

  • p. 82 The equation for E2 should have TS/T2 as the numerator.

  • p. 93 In the code example, the third line in the forall loop should read:
    int locData[size] = localize (allData[]);

  • p. 94 The third sentence should read:
    For example, threads might make protected global references and then call localize to make local references.

  • p. 94 The second sentence of the second paragraph should read:
    The mySize(global, i) function returns the size of the ith dimension of the localized portion of the global array.

  • p. 94 The code fragment should read:
    size = mySize(allData[], 0); Size of first dimension of local allocation

  • p. 98 Line 4 of the code fragment should read:
    4    count =+/(array[i]==3?1:0);

  • p. 98 Line 6 of Figure 4.2 should read:
    6  for(i=j*seg; i<min(length, j*(seg+1)); i++)

  • p. 103 Line 2 of Figure 4.5 should read:
    2 forall (index in (0..25))

  • p. 103 Line 26 of Figure 4.5 should read:
    26 for(i=0; i<myLet; i++)

  • p. 103 On line 5 of the text, the reference to +-scan should refer to line 24, not line 23.

  • p. 106 The footnote should read:
    See Knuth, vol III.

  • p. 107 Lines 5 and 6 should red:
    5 key BufK[t][size];
    6 bool free'[t] = false; ready'[t];

  • p. 107 Line 23 should read:
    23 for (p=d-1; p>=0; p--)

  • p. 114 Figure 5.2 caption: Change line reference "8" to "7" and "14" to "13"

  • p. 116 The inline code should read:
    topEdge = max/Pt.y;     Find smallest y field of the Pt array
    botEdge = min/Pt.y;     Find largest y field of the Pt array
    rightEdge = max/Pt.x;   Find largest x field of the Pt array
    leftEdge = min/Pt.x;    Find smallest x field of the Pt array

  • p. 116 In the Note describing "Two Kinds of Scan," the result of the exclusive scan should be A={0, 2, 6} not A={0, 2, 4}.

  • p. 120 Line 8 of Figure 5.4 should have a semicolon:
    8 tally = init();

  • p. 121 Line 17 of Figure 5.5 should read:
    17 if (t.smallest1>elem)

  • p. 121 In Figure 5.5, the return statement of the accum() procedure should be outside of the else clause, so lines 28 and 29 should read:
    28 }
    29 return t;

  • p. 124 Figure 5.7: See a version with fixes (and improvements). Included is a version of Figure 5.8 compatible with the revised 5.7.

  • p. 142 In Exercise 5, the reference to Figure 5.5 should be to Figure 5.10.

  • p. 146 Line 11 of the code fragment should include a typecast for the last argument, so it should read as follows:
    11   err=pthread_create(&tid[i], NULL, count3s_thread, (void *)i);

  • p. 146 On line 16 of the code fragment, pthread_join_ should be pthread_join

  • p. 146 The second to last sentence should read:
    If the parent thread does not call pthread_exit(), then the child threads will terminate when main() finishes, because the entire process will have terminated.

  • p. 150 On Line 9 of the first code fragment, the typecast is wrong. The line should read:
    9   pthread_join(tid, (void **)&status);

  • p. 152 On Line 2 of Code Spec 6.9, the typecast should be of type (pthread_mutex_t) instead of (pthread_mutex_lock_t).

  • p. 154 The second bullet of Code Spec 6.11 should read:
    "pthread_cond_signal() wakes up at least one waiting thread. If multiple threads are awakened, only one will hold the protecting mutex."

  • p. 156 In Figure 6.3, lines 11 and 12 should be replaced by the following:
    11   while ((put+1)%SIZE == get)

  • p. 158 Line 3 of the caption should refer to Figure 6.4.

  • p. 158 In Figure 6.5 the eight instances of pthread_cond_signal(&nonempty) should be pthread_cond_wait(&nonempty, &mutex)

    Also, the four instances of insert(item); should be replaced with /* insert item */, which refers to lines 16-17 of Figure 6.3; similarly the four instances of remove(item); should be replaced with /* remove item */, which refers to lines 30-31 of Figure 6.3.

  • p. 159 Line 7 of the code fragment should be preceded by a new line that checks whether there are any oranges:
    6.5   if(oranges==0)

  • p. 160 Line 5 of the lower code fragment should include a typecast for the last argument, so it should read as follows:
    5   err=pthread_create(&tid[i], NULL, start_function, (void *)i);

  • p. 160 Line 8 of the lower code fragment should have a space in the parameter's declaration:
    8 void* start_function(void* index)

  • p. 160 Line 10 of the lower code fragment should include a typecast:
    10   private_count[(int)index]=0;

  • p. 161 The macro in Code Spec 6.13 needs a space after index:
    #define index (pthread_getspecific(my_index))

  • p. 161 In Code Spec 6.13, the call to pthread_key_create() should read:
    pthread_key_create(my_index, 0);

  • p. 161 In Code Spec 6.13, the call to pthread_set_specific requires a cast:
    pthread_setspecific(my_index, (void*)id);

  • p. 162 In Code Spec 6.14, the declaration of key should have a space:
      pthread_key_t* key;

  • p. 162 In Code Spec 6.14, the Notes: should read:
    The desctructor is invoked at thread exit if the data associated with this key is not NULL.

  • p. 162 The second line of the function signature in Code Spec 6.15 should read:
    pthread_key_t key,           // Key to delete

  • p. 162 The second line of the function signature in Code Spec 6.16 should read:
    pthread_key_t key,           // Key to value

  • p. 163 The function signature in Code Spec 6.17 should read:
    void * pthread_getspecific(
    pthread_key_t key);           // Key to value

  • p. 168 Figure 6.11: Line 18 should read:
    18   while (in==out)

  • p. 169 Figure 6.12: See a version with fixes and a correct version

    The equivalent changes are:

    Line 19 should be deleted, and
    Line 24 should be changed to:
    24   readers++;

    Line 41 should add the missing closing parenthesis:
    41 ReleaseShared()

    Additionally, the following lines should be inserted:
    1.5  int readWaiters = 0;
    21.5 readWaiters++;
    22.5 readWaiters--;
    31.5 if (readWaiters==0)                // If no waiting readers
    31.6    pthread_cond_signal(&wBusy);    // Wake up a writer
    31.7 else
    32      pthread_cond_broadcast(&rBusy); // Wake up all readers

  • p. 171 Figure 6.13: See a version with fixes and a correct version

    The equivalent changes are

    The following lines should be inserted:
    1.5  int readWaiters = 0;
    20.5 readWaiters++;
    21.5 readWaiters--;
    30.5 if (readWaiters==0)                // If no waiting readers
    30.6    pthread_cond_signal(&wBusy);    // Wake up a writer
    30.7 else
    31      pthread_cond_broadcast(&rBusy); // Wake up all readers

  • p. 178 Figure 6.16: Line 103 should read:
    103   } while(delta > threshold);

  • p. 179 Figure 6.16: Lines 119-126 should read:
    119 for (i=0; i<n+2; i++)
    120 {
    121         val[i][0] = 1.0;
    122         new[i][0] = 1.0;
    123 }
    124 for (i=0; i<n+2; i++)
    125 {
    126         for (j=1; j<n+2; j++)

  • p. 181 Figure 6.20: Line 14 should read:
    14   for(int i=0; i<iterations; i++)

  • p. 181 Figure 6.21: Line 12 should read:
    12 int start=index*n_per_thread + 1;

  • p. 183 Figure 6.22: Line 51 should read:
    51 pthread_mutex_unlock(&lock);

  • p. 186 Figure 6.25: Line 9 should read:
    9 int start=index*n_per_thread + 1;

  • p. 195 Figure 6.28: Line 9 should be
    9 #pragma omp for schedule(static) private(i)

  • p. 196 Code Spec 6.21: The body of the <body> should be surrounded by curly braces:
    { <body> }

  • p. 197 In Code Spec 6.22, the syntax for the reduction operator should read as follows:
    reduction(<op >,<list >)

  • p. 203 In Figure 7.1, line 6 should read: 6 int *argc;

  • p. 204 In Figure 7.1, line 66 is missing a semicolon.

  • p. 205 In Code Spec 7.1, line four should read: chart **argv;

  • p. 207 In Code Spec 7.5 the last argument is wrong; it should be as follows:
    MPI_Comm comm // An MPI communicator

  • p. 209 In Code Spec 7.7 the first four lines should be
    void *sendBuffer,      // Address of data to send
    void *recvBuffer,      // Address at which to receive data
    int count,             // Number of elements to receive
    MPI_Datatype datatype, // Type of each element

  • p. 209 Code Spec 7.8: int destbuffer should be void *destbuffer

  • p. 211 Code Spec 7.9: int recvbuffer should be void *recvbuffer

  • p. 211 Code Spec 7.9: In the "notes" MPI_Gcatterv should be MPI_Gatherv

  • p. 216 The last phrase of the page should read:
    The routine selects a set of groups, as specified by the ranks[][] array, from the globalGroup, where the size of the group is numCols, and the new group is named newGroup (see Code Spec 7.15).

  • p. 217 Figure 7.4, line 11 should read:
    11  MPI_Comm newComm;

  • p. 217 Figure 7.4, line 23 should read:
    23  MPI_Group_incl(globalGroup, numCols, ranks[rowNumber], &newGroup);

  • p. 217 Figure 7.4, line 31 should read:
    31  MPI_Bcast(&random, 1, MPI_INT, rowNumber, newComm);

  • p. 221 Figure 7.6, line 158: The first argument to MPI_Recv should be
    &val[Height-1][1]

  • p. 222 Figure 7.6, line 185: The fifth argument to MPI_Reduce should be MPI_MAX

  • p. 222 Figure 7.6, line 188 should read:
    while (globalDelta >= THRESHOLD)

  • p. 224 Figure 7.8: See a version with fixes and a correct version

    The equivalent changes are

    All instances of MPI_ISend should be spelled MPI_Isend. All instances of MPI_IRecv should be spelled MPI_Irecv.

    On lines 115 and 117, references to buffer should instead refer to buffer1, and on lines 131 and 133, references to buffer should instead refer to buffer2.

    On p. 225, Figure 7.8 lines 148 and 152, references to buffer should instead refer to buffer3, and on lines 164 and 168, references to buffer should instead refer to buffer4.

    Lines 150-153 and lines 166-169 should be moved (along with copies of their guarding conditionals on lines 146 and 162, respectively) to line 184, so that they appear after the call to MPI_Waitall().

    Line 183 should read:
    MPI_Waitall(num_requests, requests, status);
    where num_requests is an integer that should be initialized to 0 and incremented after each of the calls to MPI_Isend() on lines 107, 117, 123, and 133 and after each of the calls to MPI_Irecv() on lines 142, 148, 158, and 164.

    Line 158: The first argument to MPI_IRecv should be
    &val[Height-1][1]

    On p. 226, Figure 7.8, line 217: The fifth argument to MPI_Reduce should be MPI_MAX

    Line 220 should read:
    while (globalDelta >= THRESHOLD)

  • p. 240 The last line of the Code Spec 8.2 should read "indicated" rather than "indicted"

  • p. 250 in the middle of the page, the left hand side of the in text example should read:
    [1..3, 1..4] 12 12 12 12
                               16 16 16 16
                                 0   0   0   0

  • p. 252 In the last code fragment, the fourth line had an extraneous right parenthesis and should read:
    [1..m,1..n] D :=D/Score;

  • p. 255 In Code Spec 8.5, the inline code should read:
    [1, 1..5] ... +<<[1..3, 1..5] A ... // reduce
    [1..3,1..5] ... >>[1, 1..5] A ...   // flood

  • p. 257 The second indented line should read:
    C <=> e r e r d d o

  • p. 260 Figure 8.3: on the fourth line of the main body of code, the variable ran should be rank

  • p. 266 Footnote: The reference to "Canon's" algorithm should be "Cannon's" algorithm

  • p. 273 line 1: Replace "blocking receive" with "synchronous send"

Last Updated

March 29, 2011