Threading and parallelization for the given snippets

Question

1.00/5 (1 vote)

See more:

I have given the following 2 snippets:
snippet(1):

int i=0;
while(i < n - 1){
 A[i] += A[i+1] + f(i);
 i++;
}

snippet(2):

for(inti= 0;i < n; i++){
 for(int j = 0; j < n; j++)
 A[i] += g(j,i);
}

so an array A of length n is defined and filled with some values assuming that there exists two functions f(.) and g(.,.) where f(.) is a thread safe function, and g(.,.) is not a thread safe function.
Every call of function g(.,.) access a memory location determined by its first
argument (i.e. g(i,j) and g(i,k) access the same memory location while the calls g(i,j)
and g(m,j) are thread safe for all 𝑖≠𝑚)

what is required is to rewrite each one of these snippets to parallelize it using threads, such that each program has 4 threads (changing the program as long as the values in the array A at the end of the threaded execution are equal to that of the serial execution)

so I need help to solve this problem or sources because I do not know how to solve such problems using threads and I cannot understand the idea fully.

What I have tried:

I searched around about threads and ways to rewrite these kind of code but without a solid answer.

Posted 25-Oct-21 8:49am

Member 15407141

Updated 26-Oct-21 4:50am

Add a Solution

Comments

Greg Utas 25-Oct-21 15:17pm

I think you need to clarify a couple of things:
1. During serial execution, is snippet #1 supposed to finish before snippet #2 runs?
2. You talk about "each program" having 4 threads, but my guess is that you mean one program with 4 threads. Correct?

Member 15407141 25-Oct-21 16:15pm

1-the 2 snippets are separated and are not in the same program even though the description apply to both arrays in the 2 snippets. For each one, the final output should be similar to that of the serial execution.
2-it's specified in the question that each modified snippet should have 4 threads.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Richard MacCutchan · Answer 1 · 2021-10-25T09:18:00

Solution 1

There is not space or time here to teach you how to modify that code so it uses threads. See std::thread - cppreference.com[^].

Posted 25-Oct-21 9:18am

Richard MacCutchan

Comments

k5054 25-Oct-21 16:04pm

Unless, of course the OP is using plain C rather than C++. In that case there's a whole lot of understanding to make sure that the non tread-safe function behaves correctly. It probably involves mutexes and/or condition variables to control access to the non-thread safe sections of the g() --- assuming the OP has access to g() and permission to modify the source.

Richard MacCutchan 26-Oct-21 3:57am

True, but the questioner, as so often, does not understand the subject but seems to think it just needs a few lines of code to fix it.

Member 15407141 25-Oct-21 16:07pm

but I didn't ask for teaching all I wanted is to get some guidance on the matter from some experts and thank you for your response.

Richard MacCutchan 26-Oct-21 3:56am

"I do not know how to solve such problems using threads and I cannot understand the idea fully."
If you do not understand how to use threads then there is not much more we can offer other than links to documentation where you can learn about them.

Member 15407141 26-Oct-21 11:37am

I meant the idea of the question with its requirements and the rewriting of code not the multithreading concept. thank you

Richard MacCutchan 26-Oct-21 11:48am

Then you need to provide a much better description of what you are trying to do. Just saying, "rewrite this code to use threads or parallelisation", is not enough.

Greg Utas · Answer 2 · 2021-10-26T04:50:00

The right side of this page contains links to "Related Questions". You may find some useful information there.

It isn't even obvious to me, depending on what f() and g() do, that parallel execution will produce the same result as serial execution.

Your answer to my comment indicates that you need 2 programs (each an independent .exe), each running 4 threads. Protecting critical sections between programs is more expensive than protecting them between threads. Even if you limit this to one program with multiple threads, my guess is that the throughput would be less than it would be for one program with one thread. In other words, the exercise is artificial if not outright silly, though I could be wrong if f() and g() are sufficiently expensive.

Snippet 1 can run in parallel if no two threads operate on the same value of i or i+1. Snippet 2 can run in parallel if no two threads operate on the same value of i or j. I don't see a simple solution other than to use a separate lock for each index in the range 0 to n-1. These locks must be shared by the two processes, and there will also be deadlock issues because a thread must obtain two locks to proceed.

EDIT: The addition of A[i+1] to A[i] must be in a critical section that protects i and i+1. The call to f(i) need not be in a critical section. The call to g(j,i) must be in a critical section that protects j, which I believe needs to be in a critical section that protects i when planning to add g's result to A[i].

I hope this is of some help.