Errata

"Execution" should be "Extension". Thus, the sentence should start with...

Streaming SIMD Extension (SSE) technology adds...

The functions listed as "pthread_lock()" and "pthread_unlock()" should be "pthread_mutex_lock()" and "pthread_mutex_unlock()", respectively.

The example code in example 5-3 does not compile, as the function threadFunction is defined as returning a void *, which it then fails to do.

Note from the Author or Editor:
I'd swear that it compiled as is when I last tried it before publication. Now, I get the problem noted.

To fix, simply add "pthread_exit(NULL);" where the return statement would be.

Use of the combination of new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to code in Example 6-4 using the latter fix would be...

void *Summation (void *pArg)
{
int tNum = *((int *) pArg);
int lSum = 0;
int start, end;

start = (N/NUM_THREADS) * tNum;
end = (N/NUM_THREADS) * (tNum+1);
if (tNum == (NUM_THREADS-1)) end = N;
for (int i = start; i < end; i++)
lSum += X[i];
gSum[tNum] = lSum;
delete (int *)pArg;
}

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to the top of the prefixScan() function code in Example 6-8 using the latter fix would be...

unsigned __stdcall prefixSum(LPVOID pArg)
{
int tNum = *((int *) pArg);
int start, end, i;
int lPrefixTotal;

delete (int *)pArg;
start = (N / NUM_THREADS) * tNum;
end = (N / NUM_THREADS) * (tNum + 1);
if (tNum == (NUM_THREADS-1)) end = N;

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to code in Example 6-10 using the latter fix would be...

int SequentialSelect(int *S, int num, int k)
{
if (num <= Q) return SortLessThanQ(S, num, k);

int cNum = num/Q + 1;
int *Medians = new int[cNum];
int i = 0;
for (int j = 0; j < num/Q; j++) {
Medians[j] = SortSelect5(&S[i], 3); // find medians of subsequences
i += Q;
}
int lastNum = num - (Q * (num / Q));
if (lastNum) {
int lastQ = Q * (num / Q);
Medians[cNum-1] = SortLessThanQ(&S[lastQ], lastNum, (lastNum+1)/2);
}
else cNum--;

int M = SequentialSelect(Medians, cNum, (cNum+1)/2);
delete Medians;

int leg[3] = {0,0,0};
int *markS = new int[num];
CountAndMark(S, markS, num, M, leg);

if (leg[0] >= k) {
int *sPack = new int[leg[0]];
ArrayPack(S, sPack, num, markS, 0);
delete markS;
M = SequentialSelect(sPack, leg[0], k);
delete sPack;
return M;
}
else if ((leg[0] + leg[1]) >= k) {
delete markS;
return M;
}
else {
int *sPack = new int[leg[2]];
ArrayPack(S, sPack, num, markS, 2);
delete markS;
M = SequentialSelect(sPack, leg[2], k-(leg[0]+leg[1]));
delete sPack;
return M;
}
}

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to code in Example 6-12 using the latter fix would be...

int ParallelSelect(int *S, int num, int k)
{
if (num <= Q) return SortLessThanQ(S, num, k);

int cNum = num/Q + 1;
int *Medians = new int[cNum];

parallel_for(blocked_range<int>(0, num/Q), FindMedians(S, Medians), auto_partitioner());

int lastNum = num - (Q * (num / Q));
if (lastNum) {
int lastQ = Q * (num / Q);
Medians[cNum-1] = SortLessThanQ(&S[lastQ], lastNum, (lastNum+1)/2);
}
else cNum--;

int M = ParallelSelect(Medians, cNum, (cNum+1)/2);
delete Medians;

int *markS = new int[num];
CountAndMark camBody(S, markS, M);
parallel_reduce(blocked_range<size_t>(0,num), camBody, auto_partitioner());

int numLessEqual = camBody.leg.less + camBody.leg.equal;
if (camBody.leg.less >= k) {
int *sPack = new int[camBody.leg.less];
ArrayPack(S, sPack, num, markS, 0);
delete markS;
M = ParallelSelect(sPack, camBody.leg.less, k);
delete sPack;
return M;
}
else if ((numLessEqual) >= k) {
delete markS;
return M;
}
else {
int *sPack = new int[camBody.leg.greater];
ArrayPack(S, sPack, num, markS, 2);
delete markS;
M = ParallelSelect(sPack, camBody.leg.greater, k-(numLessEqual));
delete sPack;
return M;
}
}

There will be a memory leak in Example 6-15 without a delete of the new memory allocation. The better ArrayPack() function code would be...

void ArrayPack(int S[], int sPack[], int num, int Marks[], int scanSym)
{
int *scanIdx = new int[num];
PackingScan body(scanIdx, Marks, scanSym);

parallel_scan(blocked_range<int>(0,num), body, auto_partitioner());

if (scanIdx[0]) sPack[0] = S[0]; // move if first element is marked
parallel_for(blocked_range<int>(1,num), PackingMove(scanIdx,sPack,S), auto_partitioner());
delete[] scanIdx;
}

The function SumByReduction is defined as returning a void *, which it fails to do. A strict compiler will not allow this to build.

Note from the Author or Editor:
Add "pthread_exit(NULL);" where a 'return' statement would be.

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to the last executable line of code in the SumByReduction() function in Example 7-2 using the latter fix would be...

delete (int *)pArg;

The broadcast in the "else" clause is better executed after the update of the barrier fields. The mutex unlock after the if-then-else will ensure that no threads that have been awakened have access to the barrier object before these values are set. The code for this clause should be...

else { // last thread
b->count = b->numThreads;
b->color = !b->color;
pthread_cond_broadcast(&b->c);
}

There will be a memory leak in Example 7-3 without a delete of the new memory allocations. The last two lines at the end of the code segment (end of the FriendlyNumbers() function) should be expanded to be...

} // end parallel region
delete[] the_num;
delete[] num;
delete[] den;
}

The bounds of the for-loop are incorrect. The termination condition should be "N-1" not "N", as it is given in the first algorithm attempt in Example 8-4. Thus, the correct line should be...

for (i = start; i < N-1; i += 2) {

The bounds of the for-loop are incorrect. The termination condition should be "N-1" not "N", as it is given in the serial algorithm (Example 8-3). Thus, the correct line should be...<p>

for (i = start; i < N-1; i += 2) {

The third parameter of WaitForMultipleObjects() was left out. The correct third parameter should be "TRUE". The correct line should be...

WaitForMultipleObjects(2, tH, TRUE, INFINTE);

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The first few lines of the while-loop code in Example 8-14 using the latter fix would be...

while (notEmpty(Q)) {
dequeue(Q, d); //pull out next index pair
p = d->lo;
r = d->hi;
delete d;

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The first few lines of the while-loop code in Example 8-17 using the latter fix would be...

while (1) {
WaitForSingleObject(hSem, INFINITE);
if (Done) break; // external signal to terminate threads
dequeue(Q, d);
p = d->lo;
r = d->hi;
delete d;

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The first few lines of the while-loop code in the RadixExchangeSort() function in Example 8-19 using the latter fix would be...<

while (notEmpty(Q)) {
dequeue(Q, d); //pull out next index pair, unless queue is empty
p = d->lo;
r = d->hi;
bPos = d->bitPosition-1;
delete d;

Use of pointers will not work if an odd number of iterations within the given function are executed. Better, more general code for the example would be:

#define mbits 4
#define M 16

void StraightRadixSort(int **A, int N, int b)
{
int i, j, pass, tBits;
int count[M];
int *tA = new int[N];
int *tempPtr;

for (pass = 0; pass < (b / mbits); pass++) {
for (j = 0; j < M; j++) count[j] = 0;
for (i = 0; i < N; i++) {
count[bits((*A)[i], pass*mbits, mbits)]++;
}
count[0]--;
for (j = 1; j < M; j++) count[j] += count[j-1]; // prefix sum on counts
for (i = N-1; i >= 0; i--) {
tBits = bits((*A)[i], pass*mbits, mbits);
tA[count[tBits]] = (*A)[i];
count[tBits]--;
}

// swap pointers to swap arrays to sort in next pass
tempPtr = tA; tA = *A; *A = tempPtr;
}
delete[] tA;
}

The last sentence of the note begins "This scheme is only scalable to the number of different bit patterns used (mbits squared) and requires all ...."

The number of distinct bit patterns for mbits is 2 to the mbits.

Note from the Author or Editor:
D'oh! You're right, I had my "2" in the wrong place. The proper phrase in the parenthesis of that sentence should be "2 raised to the power of mbits".

Use of pointers will not work if an odd number of iterations within the given function are executed. Better, more general code for the example would be:

#define mbits 4
#define M 16

void SerialStraightRadixSort(int **A, int N, int b)
{
int i, j, pass;
int offset, rank;
int count;
int *tA = new int[N];
int *tempPtr;

for (pass = 0; pass < (b / mbits); pass++) {
offset = -1; //for 0-base index
for (j = 0; j < M; j++) {
count = 0;
for (i = 0; i < N; i++) {
if (bits((*A)[i], pass*mbits, mbits) == j) count++;
}
rank = offset + count;
for (i = N-1; i >= 0; i--) {
if (bits((*A)[i], pass*mbits, mbits) == j)
tA[rank--] = (*A)[i];
}
offset += count;
}

// swap pointers to swap arrays to sort in next pass
tempPtr = tA; tA = *A; *A = tempPtr;
}
delete[] tA;
}

The variable "offset" is not used in the function; the declaration can be removed. The final declaration line should be...

int start, end;

The function ParallelStraightRadixSort is defined as returning a void *, which it fails to do. A strict compiler will not allow this to build.

Note from the Author or Editor:
Add "pthread_exit(NULL);" where a 'return' statement would be.

The function pSearch is defined as returning a function, but it does not do so. A strict compiler will not allow this code to build.

ExitThread is used in this example, which is acceptable in C code, but not recommended in C++ code. It would work in this particular piece of code even if built as C++, but is not a good habit to pick up, as if the code were modified to construct any objects, their destructors would not get called when ExitThread was called.

Note from the Author or Editor:
All codes are written in C -- with a dash of C++ when needed (classes for TBB) or convenient ('new' for allocation). This is mentioned in the Preface at the top of page ix. If you are using C++ (or Java or C# or something else) there may be required changes to the example codes.

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The changes to to the last few lines of code in the pSearch() function in Example 9-4 using the latter fix would be...


LinearPSearch(A, start, end, key, &pos);
delete (sParam *)pArg;
ExitThread(pos);
}

There will be a memory leak in Example 9-7 without a delete of the new memory allocations. The last few lines of the NarySearch() function code would be...


if (locate[Ntrvl] != locate[Ntrvl+1]) lo = mid[Ntrvl] + 1;
}
delete[] locate;
delete[] mid;
}

There will be a memory leak in Example 9-8 without a delete of the new memory allocations. The last few lines of the NarySearch() function code would be...


if (locate[Ntrvl] != locate[Ntrvl+1]) lo = mid[Ntrvl] + 1;
} // end single
}
} // end parallel region
delete[] locate;
delete[] mid;
}

The phrase "edge pairs" makes no sense. The first line should read...

A graph is directed if all node pairs (representing edges) are ordered.

The original code is not wrong. As it is, the call to ReleaseSemaphore() is done each time the "if" condition is true. The idea was to keep a count and then call this function once. This can be done by the following change to the relevant conditional code given in Example 10-5:

if (iWillVisit) {
/*
Do something to VISIT node k
*/
long semCount = 0;
for (i = V-1; i >= 0; i--)
if (adj[k][i]) {
push(S, i);
semCount++;
}
if (semCount) ReleaseSemaphore(hSem, semCount, NULL);
iWillVisit = 0;
if (gCount == V) SetEvent(tSignal);
}

Since the count declaration is now in the (WillVisit) test, the extra braces (from the for-loop) aren't needed.

Use of the combination new/free to allocate and deallocate dynamic memory is not a good idea. To correct, either replace the use of "new" with "malloc" or replace "free" with "delete". The last few lines of the Prims() function code in Example 10-9 using the latter fix would be...

} // for i
delete[] nearNode;
delete[] minDist;
return;
}

There will be a memory leak in Example 10-11 without a delete of the new memory allocations. To fix this, the last few lines of the cPrims() function code in Example 10-11 should be...

} // for i
delete[] nearNode;
delete[] minDist;
return;
}