Parallel Programming Using Threads 345
// seq uential .c1
#in clude " subset s um .h "2
int subsetSum ( i n t * setA , i nt sizeA , in t kval )3
{4
unsigned int maxCode = 1;5
unsigned int ind ;6
for ( ind = 0; ind < sizeA ; ind ++)7
{8
maxCode *= 2;9
}10
int total = 0;11
for ( ind = 1; ind < maxCode ; ind ++)12
{13
total += s ubsetEqua l ( setA , sizeA , kval , ind );14
}15
return total ;16
}17
The function subsetEqual determines whether a specific subset sums to the value of k:
// su b setequal . c1
#in clude < stdio .h >2
int subsetE qual ( in t * setA , i nt sizeA , int kval ,3
unsigned int code )4
{5
int sum = 0;6
int ind = 0;7
unsigned int origcode = code ;8
while (( ind < sizeA ) && ( code > 0) )9
{10
i f (( code % 2) == 1)11
{12
sum += setA [ ind ];13
}14
ind ++;15
code >>= 1;16
}17
i f ( sum == kval )18
{19
printf (" equal : sum = %d , code = %X n" ,20
sum , o rigcode ) ;21
return 1;22
}23
return 0;24
}25
21.4.3 Multi-Threaded Solution
The sequential program can be parallelized in a variety of ways. We need to figure out
how to distribute the work evenly across several threads. Each thread can be responsible for
checking the sums of some of the subsets. To be more precise, suppose a set has n elements
346 Intermediate C Programming
and t threads are used to solve the subset sum program (excluding the main thread). One
solution to distribute the work is to have the first thread check the subsets between 1 and
b
2
n
t
c. The second thread simultaneously checks the subsets between b
2
n
t
c + 1 and 2 × b
2
n
t
c.
It is important to handle the last thread with caution. If t is not a factor of 2
n
, then the
program must ensure that the thread includes the last set (value is 2
n
− 1).
The new subsetSum function contains three steps:
1. Create an object as the argument to each thread. This object contains multiple at-
tributes to a function. The attributes are put together into a single structure because
a thread can take only one argument. In this case, each object specifies the range
of subsets checked by the individual thread. The object includes (i) the range of the
subsets to be examined, (ii) the set, (iii) the set’s size, (iv) the value of k, and (v)
the number of subsets whose sums equal to k. It is necessary to give each thread all
relevant information because using global variables is strongly discouraged.
2. Create the threads. Each thread checks some subsets and computes the number of
subsets whose sums equal to k.
3. The main thread waits for every thread to complete and then adds the number subsets
that each thread reports.
The checkRange function is used by each thread, and is an argument of pthread create.
This is a SIMD program because the same function is used in every thread. Below is the
code listing for the subsetSum function using threads:
// thr eaddata .h1
#i f n d e f THREADD ATA_H2
#d ef in e THRE ADDATA_ H3
typedef s t ru ct4
{5
unsigned int minval ;6
unsigned int maxval ;7
int numSol ;8
int * setA ;9
int sizeA ;10
int kval ;11
} Thr e adData ;12
#e ndif13
// paralle l . c1
#in clude < pthread .h >2
#in clude < stdio .h >3
#in clude < stdlib .h >4
#in clude " thre a ddata . h"5
#in clude " subset s um .h "6
#d ef in e NUM B ER_THR EAD 167
void * c heckRange ( void * range )8
{9
ThreadD a ta * thd = ( ThreadD a ta *) range ;10
unsigned int minval = thd -> minval ;11
unsigned int maxval = thd -> maxval ;12
// printf (" minval = %d , maxval = %d n" , minval , maxval );13
unsigned int ind ;14
// caution : need to use <= for max15
for ( ind = minval ; ind <= maxval ; ind ++)16
{17
Parallel Programming Using Threads 347
thd -> numSol +=18
subset Equal ( thd -> setA , thd -> sizeA ,19
thd -> kval , ind );20
}21
return NULL ;22
}23
24
int subsetSum ( i n t * setA , i nt sizeA , in t kval )25
// This function does not allocate memory ( malloc )26
// No need to free memory if failure occurs27
{28
29
pthread_t tid [ N UMBER_T HREAD ];30
ThreadD a ta thd [ NUM B ER_THR EAD ];31
// set the values for the thread data32
unsigned int maxCode = 1;33
unsigned int ind ;34
for ( ind = 0; ind < sizeA ; ind ++)35
{36
maxCode *= 2;37
}38
int total = 0;39
unsigned int minval = 1;40
unsigned int size = maxCode / NUMBE R_THREA D ;41
unsigned int maxval = size ;42
for ( ind = 0; ind < NUMB E R_THRE AD - 1; ind ++)43
{44
thd [ ind ]. minval = minval ;45
thd [ ind ]. maxval = maxval ;46
thd [ ind ]. numSol = 0;47
thd [ ind ]. setA = setA ;48
thd [ ind ]. sizeA = sizeA ;49
thd [ ind ]. kval = kval ;50
minval = maxval + 1;51
maxval += size ;52
}53
// ind should be NU MBER_TH READ - 1 now54
// handle the last thread diff e rently because55
// maxCode may not be a m ultiple of NU M BER_TH R EAD56
thd [ ind ]. minval = minval ;57
thd [ ind ]. maxval = maxCode - 1; // reme m b er -158
thd [ ind ]. numSol = 0;59
thd [ ind ]. setA = setA ;60
thd [ ind ]. sizeA = sizeA ;61
thd [ ind ]. kval = kval ;62
63
// create the threads64
for ( ind = 0; ind < NUMB E R_THRE AD ; ind ++)65
{66
int rtv ;67
rtv = p thread _creat e (& tid [ ind ] , NULL ,68
348 Intermediate C Programming
checkRange , ( void *) & thd [ ind ]) ;69
i f ( rtv != 0)70
{71
printf (" ERROR : pthr ead_cr a te () fail n ");72
}73
}74
75
// wait for the threads to complete76
for ( ind = 0; ind < NUMB E R_THRE AD ; ind ++)77
{78
int rtv ;79
rtv = p thread_ join ( tid [ ind ] , NULL ) ;80
i f ( rtv != 0)81
{82
printf (" ERROR ; pthr ead_join () returns %d n" , rtv ) ;83
return EXIT _FAILUR E ;84
}85
total += thd [ ind ]. numSol ;86
}87
return total ;88
}89
There are a few details worth noting. First, the ranges checked by the threads must be
mutually exclusive. If one subset is checked by two or more threads and this subset’s sum
happens to equal to k, then this subset is counted multiple times and the total is wrong.
Second, the threads combined should check all subsets (excluding the empty set). Also,
checkRange needs to be consistent with the ranges assigned in subsetSum. In particular, if
checkRange uses <= maxval, then the maximum value checked by the last thread must be
maxCode - 1, not maxCode. You may notice that the individual threads share some data.
In each object, the attribute setA is a pointer to an array. This means that every thread
uses the same piece of memory. This is acceptable because the threads do not modify the
array. The other attributes are unique to each thread, because the object stores unshared
attributes (the int and unsigned int data).
21.5 Interleaving the Execution of Threads
The threads in the subset sum program shared a common array setA. Being able to share
memory between different threads is a characteristic of threaded programming; however, it
can sometimes be problematic. In the subset sum case, the threads never modify the shared
memory (i.e., setA), but only read the elements from the array. The only memory that the
threads modify is the attribute numSol, and each thread has a unique copy of this variable.
The main thread waits until all the threads are complete by calling pthread join on each
thread. Then the main thread adds the numSol values. The threads never intend to modify
any piece of shared memory. What happens if threads share memory that may be read and
written? The following listing is a simple and instructive example:
// outsync .c1
#in clude < pthread .h >2
#in clude < stdio .h >3
Parallel Programming Using Threads 349
#in clude < stdlib .h >4
#d ef in e NUM B ER_THR EAD 165
void * t hreadfunc ( void * arg )6
{7
int * intptr = ( in t *) arg ;8
while (1)9
{10
(* intptr ) ++;11
(* intptr ) --;12
i f ((* intptr ) != 0)13
{14
printf (" value is % dn ", * intptr );15
return NULL ;16
}17
}18
return NULL ;19
}20
21
int main ( i n t argc , char * argv [])22
{23
pthread_t tid [ N UMBER_T HREAD ];24
int rtv ; // return value of pth r ead_cr eate25
int ind ;26
int arg = 0;27
for ( ind = 0; ind < NUMB E R_THRE AD ; ind ++)28
{29
rtv = p thread _creat e (& tid [ ind ] , NULL ,30
threadfunc , ( void *) & arg ) ;31
i f ( rtv != 0)32
{33
printf (" pth read_c reate () fail %d n" , rtv ) ;34
return EXIT _FAILUR E ;35
}36
}37
for ( ind = 0; ind < NUMB E R_THRE AD ; ind ++)38
{39
rtv = p thread_ join ( tid [ ind ] , NULL ) ;40
i f ( rtv != 0)41
{42
printf (" pth r ead_joi n () fail %d n" , rtv ) ;43
return EXIT _FAILUR E ;44
}45
}46
return EXIT _SUCCES S ;47
}48
This program creates some threads that share the address of the same integer variable
(arg in main). Each thread increments and decrements the value stored at that address
(i.e., the integer). If a thread finds that the value is not zero, then it prints a message and
terminates. Otherwise the thread will continue indefinitely. Can the threads ever print the
message? Will any thread return NULL and terminate? There is no good way to answer this
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.