20/06/2021 COMP2129 – Assessments
Afternoon session: Parallel
This assessment is CONFIDENTIAL. © University of Sydney.
Create a thread worker function to count the number of times the sequence x , x+1 , x+2 appears as consecutive elements in an integer array, where x can be any number. We will call these triplets. Specifically, the triplet must begin the sequence when the index % 3 == 0 for it to be counted.
Copyright By PowCoder代写 加微信 powcoder
The following examples show how to identify a triplet. One example for one array.
Array index
3 4 91 2 3
5 6 7 8 9 10
3 345 6 134 5
99 1 99 9 00 0 23 4
2 3 1 2 1 2 0 0
eg 1 yes, 1,2,3 is found exactly once starting at index 0
eg 2 no, 1,2,3 is not found. (did not start at index % 3 == 0)
eg 3 no, 1,2,3 is not found. (did not start at index % 3 == 0)
eg 4 yes, 1,2,3 is found exactly once starting at index 3
eg 5 yes, 2 items. 1,2,3 and 4,5,6 are found starting at index 3 and index 6 respectively eg 6 yes, 2 items. 2,3,4 and 3,4,5 are found starting at index 0 and index 6 respectively The input is the following:
array of int16_t, called array
number of elements in the array, called array_size
number of worker threads that will execute the function find_triplet_thread_worker() , called number_of_threads
one pthread mutex lock, initially unlocked, called global_lock
as an argument for each thread worker, the address of a thread structure called arg
The output is the following:
defined externally. Set the global variable to represent the total number of triplets found in array
the global variable has a get/set function get_global() and set_global()
as a return value for each thread worker, an address of the thread’s own struct result will be returned. The struct will contain all the indices that have been found by this thread in a results array. The results_size will also be set to the number of indices stored there. Valid integers in
https://edstem.org/courses/420/assessments/637
20/06/2021 COMP2129 – Assessments
the array is in the range . Valid integers for is in the range [0,array_size] .
Sample input:
[0, array_size]
results_size
number_of_threads 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13
——————————————
array memory contents 1 2 3 0 0 1 4 5 6 7 8 9 0 0
——————————————
array_size 14
get_global() is -1
Sample possible output (depends on your implementation):
Thread 0 struct
thread_id 0
results memory content 0 6
results_size 2
Thread 1 struct
thread_id 1
results memory content 9
results_size 1
get_global() is 3
Sample possible output (depends on your implementation):
Thread 0 struct
thread_id 0
results memory content 0
results_size 1
Thread 1 struct
thread_id 1
results memory content 6 9
results_size 2
get_global() is 3
The thread worker function can be executed by 1 or more threads simultaneously and you must ensure the correct result is calculated.
find_triplet.h
https://edstem.org/courses/420/assessments/637
20/06/2021 COMP2129 – Assessments
typedef struct thread_data {
int thread_id;
int16_t *results;
int results_size;
// assume > number_of_threads
extern int array_size;
// assume already allocated with data
extern int *array;
// assume > 0
extern int number_of_threads;
// assume global initially -1
// read the value from the global variable
extern int get_global();
// write a value to the global variable
extern void set_global(int val);
// assume PTHREAD_MUTEX_INITIALIZER
extern pthread_mutex_t global_lock;
// what you must implement
extern void *find_triplet_thread_worker(void *arg);
find_triplet.c
* The parameter is the address of the struct thread data TDATA.
* Within the struct, the initial state is:
* thread_id is set for the thread. It is in range [0, number_of_threads-1 ]
* results is allocated to be as large as array
* results_size is -1
* The return value is the address this thread’s own TDATA.
void *find_triplet_thread_worker(void *arg)
TDATA *tdata = (TDATA *)arg;
// your code here
return NULL;
Threads all working equally
Your code must distribute the workload as equally as possible among the threads.
https://edstem.org/courses/420/assessments/637
20/06/2021 COMP2129 – Assessments
One item of work in this problem is checking if the triplet is found in the array, containing the values x , x+1 , x+2 , where x is any number.
Hence, the number of work items is the array_size / 3 When there are more items than threads
For example if there are 19 items and 2 threads.
Thread 0 must process approximately 9 items
Thread 1 must process approximately 9 items
For example if there are 3 items and 2 threads.
Thread 0 must process approximately 1 item
Thread 1 must process approximately 1 item
For example if there are 100 items and 4 threads.
Thread 0 must process approximately 25 items
Thread 1 must process approximately 25 items
Thread 2 must process approximately 25 items
Thread 3 must process approximately 25 items
When there are more threads than items, the processing can be sequential For example if there are 10 threads and
1 item: any one thread 0-9 can process 1 item
2 items: any one thread 0-9 can process all 2 items
9 items: any one thread 0-9 can process all 9 items
Extra Notes
The array_size tested will not exceed value of signed int
You do not have to consider the case of overflow in the triplet where x+1 < x .The value for any element in the array x is always smaller than 32000 .
About the tests
4 tests for single threaded correctness
4 tests for two threads alternating (serialised) correctness.
12 tests for more data cases with multiple threads
Hidden test cases will apply after the exam using different data
https://edstem.org/courses/420/assessments/637
20/06/2021 COMP2129 – Assessments
There are no tests for each thread structure results during the exam
Sample data for the small test cases are provided. You should test these with 1 to many threads before proceeding to larger
Test files begin with one number to indicate how many elements are to be read by the scaffold
t01.in has 9 elements, the file appears as:
9 12 3 45 6 99 9
Do not write code for the tests. You will fail if you do. Scaffold code
The staff find_triplet_main.c file is available for you to run the code with the test files. Any changes made to the staff file find_triplet_main.c will not influence a grading. You can use it for debugging the output of each thread or provisioning your own test data. if you change this file to pass all tests, it does not mean you have passed all tests.
A copy of original scaffold is here:
Compiler and flags used
find_triplet_main.c
FLAGS="-O0 -Wall -std=gnu11 -Wno-int-to-void-pointer-cast -lpthread"
clang $FLAGS find_triplet.c find_triplet_main.c -o find_triplet
Submit often
We recommend you make regular submissions
you do not lose any unsaved work
to continuously check for errors in compilation
to continuously check you have passed the basic single/dual threaded tests
Warning: Any attempts to deceive or disrupt the marking system will result in an immediate zero for the entire assessment. Negative marks can be assigned if you do not properly follow the specification, or your code is unnecessarily or deliberately obfuscated. Note the multithreading will be tested after submission to ensure that the workload is distributed correctly.
https://edstem.org/courses/420/assessments/637
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com