20/06/2021 COMP2129 – Assessments
Morning session: Parallel
This assessment is CONFIDENTIAL. © University of Sydney.
Create a thread worker function to count the number of times the sequence 1, 0, 1 appears as consecutive elements in an integer array. Specifically, the sequence is only considered when the first element is at index % 3 == 0 . A global variable stores the total number of times the sequence is found for all threads and is the output of the program.
Copyright By PowCoder代写 加微信 powcoder
The following examples show how 1, 0, 1 can be identified. One example for one array.
Array index
3 4 01 0 1
5 6 7 8 9 10
1 110 1 110 1
00 1 00 0 00 0 10 1
0 1 1 0 1 0 0 0
eg 1 yes, sequence 1,0,1 is found exactly once starting at index 0
eg 2 no, sequence 1,0,1 is not found. (did not start at index % 3 == 0)
eg 3 no, sequence 1,0,1 is not found. (did not start at index % 3 == 0)
eg 4 yes, sequence 1,0,1 is found exactly once starting at index 3
eg 5 yes, sequence 1,0,1 is found exactly twice starting at index 3 and index 6 eg 6 yes, sequence 1,0,1 is found exactly twice starting at index 0 and index 6 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_101_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 1, 0, 1 sequences
found in array
the global variable has a get/set function get_global() and set_global()
https://edstem.org/courses/420/assessments/636
20/06/2021 COMP2129 – Assessments
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 the results array is in the range [0, array_size] . Valid integers for results_size is in the range [0,array_size] .
Sample input:
number_of_threads 2
0 1 2 3 4 5 6 7 8 9 10 11 12 13
——————————————
array memory contents 1 0 1 0 0 1 1 0 1 1 0 1 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.
https://edstem.org/courses/420/assessments/636
20/06/2021 COMP2129 – Assessments
find_101.h
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_101_thread_worker(void *arg);
find_101.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_101_thread_worker(void *arg)
TDATA *tdata = (TDATA *)arg;
// your code here
return tdata;
Threads all working equally
https://edstem.org/courses/420/assessments/636
20/06/2021 COMP2129 – Assessments
Your code must distribute the workload as equally as possible among the threads.
One item of work in this problem is checking if 3 elements of the array contain the values 1, 0, 1 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 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 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
https://edstem.org/courses/420/assessments/636
20/06/2021 COMP2129 – Assessments
Do not write code for the tests. You will fail if you do. Scaffold code
The staff find_101_main.c file is available for you to run the code with the test files. Any changes made to the staff file find_101_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_101_main.c
clang -O0 -Wall -std=gnu11 -Wno-int-to-void-pointer-cast -lpthread find_101.c find_101
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/636
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com