Assignment #4 Solution

$30.00

Description

W

defPartition(A, p, r): x = A[r]

i = p – 1

forjinrange(p, r):

hat to submit: One zip file named <studentID>-hw4.zip(replace <studentID> with your own student ID). It should contain four files:

  • one PDF file namedhw4.pdffor Section 1 and Section 3.Write your answersin

English. Check your spelling and grammar. Include your name and student ID.

  • Section 2: Turnin

    • Section 2.1:quicksort.c,typescript1

    • Section 2.2:qsortTh.py,typescript2

    • Section 2.3:qsortTh.c,typescript3

  • Section 3: (part ofhw4.pdf)

  1. [40 points] ProblemSet

    1. [20 points] Under what circumstances does a multithreaded solution using multiple kernel threads provide better performance than a single-threaded solution on a single-processorsystem?

    2. [20 points] Which of the following components of program state are shared across threads in a multithreadedprocess?

      1. Registervalues

      2. Heapmemory

      3. Globalvariables

      4. Stackmemory

  1. [50 points] ProgrammingExercise

QuickSort is a popular algorithm for sorting. Even though its worst-case runtime complexity isO(n2), its average complexity isO(nlgn), and in practice it is very fast because it is

in-place sorting (i.e., does not need a temporary buffer). Also, as a divide-and-conquer algorithm, it does most of the work in the “divide” stage and no work in the “conquer” stage. This makes it nice for parallelizing, because after forking, there is no dependency after joining.

defQuickSort(A, p, r):

ifp < r:

q = Partition(A, p, r) QuickSort(A, p, q-1)

The following is a Python 2 implementation of Quicksort. For Python3, see the comments about changing range(LEN) into list(range(LEN)).

defPartition(A, p, r): x = A[r]

i = p – 1

forjinrange(p, r):

if(A[j] <= x): i = i + 1

A[i], A[j] = A[j], A[i]

A[i+1], A[r] = A[r], A[i+1]

returni + 1

QuickSort(A, q+1, r)
ifname ==main‘: LEN =10

L = range(LEN) # in Python3, do L = list(range(LEN)) instead

importrandom random.shuffle(L) QuickSort(L, 0, len(L)-1)

ifL==range(LEN): #Python3 list(range(LEN)) insteadofrange(LEN) print(“successfullysorted”)

else:

print(“sort failed: %s” % L)

The test case just says to generate numbers 0..LEN-1, shuffle, and sort. If successful, it says so; otherwise, it dumps the list.

    1. [10 points] Convert quicksort.py to C and call itquicksort.c.Turn in the source file and a typescript file namedtypescript1showing how you build and run it.

      1. Since you will need to measure the execution time of the code, you will need a large enough dataset. However, shuffling numbers can take a long time. Instead of shuffling numbers, have the numbers be pre-generated by the following script (genrandom.py) just once before you run your own code any number of times.importrandom

LEN = 20000000

L = range(LEN) random.shuffle(L)

fh =open(“randomInt.txt”, “w”)#first writeis thelength fh.write(str(LEN)+’\n’)

foriinL:

fh.write(str(i)+’\n’) fh.close()

Run this python program and it will create a text file namedrandomInt.txt. The first

line is the number forLEN, followed by the shuffled numbers in the range0..LEN-1.

      1. You can use the following template (quicksort.c) to read in the data into arrayA, or feel free to write your owncode:

#include <stdio.h> #include <stdlib.h> #include <pthread.h>int*A; // array

intPartition(intA[],intp,intr) {

// your code

}

void* QuickSort(int A[],intp,intr) {

// your code

}

intmain(intargc,char*argv[]) {

FILE* fh = fopen(“randomInt.txt”, “r”);

intlen;

fscanf(fh, “%d”, &len);

A = calloc(len, sizeof(int));

for(inti = 0; i < len; i++) { fscanf(fh, “%d”, A+i);

}

fclose(fh); QuickSort(A,0,len-1);

// check if they are sorted

for(inti = 0; i < len; i++) {

if(A[i] != i) {

fprintf(stderr, “error A[%d]=%d\n”, i, A[i]);

}

}

}

      1. compile and run your program. Compile by$ ccquicksort.c-oquicksortso it generates the executable file namedquicksort.Run it andtype

$time./quicksort to see how much time it takes. Capture this intypescript.

    1. [20 points] Convertquicksort.pyto threaded version (name itqsortTh.py)using Python’sthreadingpackage. Good places to convert to threads is one of the recursive calls in QuickSort, since the two work on two disjoint parts of the array and are therefore independent of each other. The stepsare

      1. Create a new thread for one of the two recursive calls by callingthreading.Thread(),and assign it to a variable. Thetargetparameter is the functionforthethreadtocall,andtheargsparameteristhetupleofparametersto pass.

      2. Unlike POSIX threads, instantiating a thread does not start running it; you have to explicitly call the.start()method on the thread to start running it. The parent thread itself can do the other recursive call concurrently. (The parent could create twothreadsbutitwouldbewasteful,sincetheparentwouldhavenothingelsetodo).

      3. (parent) wait for the (child) thread to complete by calling the.join()method on it.

      4. When the data size is small (e.g., 10), it probably does not hurt to create threads for recursive calls, but when the data size is large (e.g., 20 million), then you want to limit the number of threads you create. Add code to limit thread creation based on the number of threads currently running. If it exceeds the (self-imposed) maximum number of threads (that you allow), then don’t make a new thread for recursive call; instead, just call QuickSort normally. Otherwise, make a new thread, start it, and join it.

Turn in the python source file (qsortTh.py) and a typescript file namedtypescript2

showing that you run it successfully. Then show thetimeresult (Section 2.1.3)

    1. [20 points] ConvertqsortTh.pyfrom Part 2.2 to C (and name itqsortTh.c)using Pthreads. Note that the idea is similar to the Python version but slightly different. Here is a template: forqsortTh.c

#include <stdio.h> #include <stdlib.h> #include <pthread.h>int*A; // array

intPartition(intp,intr) {

// your code from Sec. 2.1 except array param is now global A

}

void* QuickSort(void*arg) {

// your code

}

intmain(intargc,char*argv[]) {

// read randomInt.txt into array A

// same as Sec 2.1.

intargs[2] = { 0, len-1 }; QuickSort(args);

//checkiftheyaresorted. This partissameas Sec2.1

for(inti = 0; i < len; i++) {

}

}

      1. Declareavariableoftypepthread_tandcallpthread_create()bypassingthe pointerofthepthread_tvariableasfirstparam;youcanuseNULLasthe2nd parameter;thenameofthefunctionforthethreadtocallasthe3rdparameter;

      2. The fourth parameter topthread_create()is a pointer to the arguments. This meansyourQuickSortfunctioncannottake(intA[],intp,intr)asits argument list; instead, they have to be a pointer to some array or struct where the value of these parameters are found. (see templatecode)

      3. Note that unlike Python, as soon as you callpthread_create(),the thread starts running right away. However, thread creation could fail, so you should check the return value and report an error if the thread cannot be created andexit.

      4. You can usepthread_join()to join the threads before returning.

      5. Compile your code by$ cc-pthreadqsortTh.c-oqsortTh — note the

-pthreadflag to make sure it is linked properly.

Turn in the C source file (qsortTh.c) and a typescript file namedtypescript3

showing that you run it successfully, and then show thetimeresult (Sec. 2.1.3).

  1. [10 points] PerformanceAnalysis

Present a table of runtime that you measured using the time command for running

    • time python3 quicksort.py #provided

    • time python3 qsortTh.py #from section2.2

    • time ./quicksort #from section2.1

    • time ./qsortTh #from section2.3

Is the threaded version faster or slower than the unthreaded version in C? in Python? Explain why in each case.