Intermediate C Programming

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

unsigned int maxCode = 1;5

unsigned int ind ;6

for ( ind = 0; ind < sizeA ; ind ++)7

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 speciﬁc 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

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 ﬁgure 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 ﬁrst thread check the subsets between 1 and

c. The second thread simultaneously checks the subsets between b

c + 1 and 2 × b

It is important to handle the last thread with caution. If t is not a factor of 2

, then the

program must ensure that the thread includes the last set (value is 2

− 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 speciﬁes 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

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

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

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

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

// 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

// 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 diﬀerent 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

int * intptr = ( in t *) arg ;8

while (1)9

{10

(* intptr ) ++;11

(* intptr ) --;12

i f ((* intptr ) != 0)13

{14

printf (" value is % d\n ", * intptr );15

return NULL ;16

}17

}18

return NULL ;19

}20

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 ﬁnds that the value is not zero, then it prints a message and

terminates. Otherwise the thread will continue indeﬁnitely. Can the threads ever print the

message? Will any thread return NULL and terminate? There is no good way to answer this

Previous Chapter

21. Parallel Programming Using Threads (2/5)

Next Chapter

21. Parallel Programming Using Threads (4/5)

Table of Contents for Intermediate C Programming

Table of Contents for
Intermediate C Programming