Question

In: Computer Science

A friend suggests that the prive sieve problem is embarrassingly parallel and can be completed without...

A friend suggests that the prive sieve problem is embarrassingly parallel and can be completed without using locks, because shared variables are only ever written to as booleans (i.e., set from FALSE to TRUE), so race conditions are not a concern as it matters not how many times a number has been crossed out. You agree. Your friend then suggests that, therefore, using 1000 threads to solve this problem will speed up your program 1000-fold. Argue for or against this statement.

Solutions

Expert Solution

Using 1000 threads to solve this problem will speed up your program 1000-fold is not true.The reasons are as follow-

1=We can divide the problem into completely independent parts, where “completely independent” means I don’t have to wait for an answer to one part before going ahead and working on another part. If the answer is “yes” I can keep adding threads until I have as many threads as there are cores. For this kind of problem, 2 threads will be close to twice as fast as 1 thread, and 4 threads will be close to twice as fast as 2 threads. If the answer is “no” then more threads won’t help.

2=A multithreaded program always has more work to do than a single threaded one: in addition to computing the same result, it also has to do some extra work to coordinate multiple threads.A multithreaded program can still finish faster than a sequential one, because some of the work it does can proceed simultaneously.

3=If you program things where the tasks can’t be run in parallel and threads are waiting on each other frequently then the program will be slower. The threads would simply be taking turns using the CPU, and there is a cost of context switching between the threads, so the program would actually be slower.

4=In most threaded programs, all communication between threads is done via global variables. So even if you consider globals to be evil, they are a necessary evil in threads programming.


Related Solutions

Suppose you and your friend want to start a business, and the friend suggests to start...
Suppose you and your friend want to start a business, and the friend suggests to start a movie dvd rental store in the bronx. Is that an attractive market? Discuss using Porter's Five Forces
The interest rate affects the investment patterns in the economy. A friend of yours suggests a...
The interest rate affects the investment patterns in the economy. A friend of yours suggests a get-rich-quick scheme: Borrow from the nation with the lower nominal interest rate, invest in the nation with the higher nominal interest rate, and profit from the interest-rate differential. Do you see any potential problems with this idea? Explain. What are the cons of the strategy? Consumer spending during holiday seasons affects the aggregate demand (AD) in the economy. AD drastically declines during serious recessions....
oase Theorem suggests one way in which the problem of externalities can be solved. However, the...
oase Theorem suggests one way in which the problem of externalities can be solved. However, the theorem has its practical limitations. From the scenarios given below, which is the best candidate for Coase-like solution? Paul is annoyed by the loud music played by his neighbor. Manufacturing plants in the Midwest emit sulfur dioxide which causes acid rain in Canada. Carbon emissions from coal power plants in China contribute to climate change of the planet. All of the above are equally...
1) A friend of yours suggests that at least 10% of people at your university have...
1) A friend of yours suggests that at least 10% of people at your university have had something stolen from them on campus in the past year. This is your population value. You take a random sample of 100 people in you classes to determine if your friend is correct, you think that they may be wrong. You find that 15% of them have had something stolen. Would you have a one or two tailed test? Two Tailed One tailed...
Problem: Find the speedup and efficiency that can be obtained with parallel computing, given the values...
Problem: Find the speedup and efficiency that can be obtained with parallel computing, given the values of the time needed to complete the sequential part of the task (denoted by Ts), the time needed to complete the parallelizable part of the task with one processor (denoted by Tp), and the number of processors (denoted by N) in the first three columns of the following table, and report them in the last two columns of the table. Tsin seconds Tpin seconds...
Problem 3) A recent study suggests that noise pollution can increase the risk of cardiovascular disease....
Problem 3) A recent study suggests that noise pollution can increase the risk of cardiovascular disease. This theory was investigated in a recent study where a random sample of adults who have lived in the same home for at least five years was obtained. The nighttime noise level (decibels) was measured in each home. Also, an index of cardiovascular risk was measured for each person; this index is called an Agatston score, determined with electron-beam computed tomography. An Agatson score...
Where is the image in a plane mirror formed? Your friend Noelle suggests the following hypothesis:...
Where is the image in a plane mirror formed? Your friend Noelle suggests the following hypothesis: "The image of an object formed by a plane mirror is formed on the surface of the mirror." Design an experiment to test Noelle's hypothesis. Available equipment: Plane mirror, object, masking tape, paper, meter stick. Design and describe the experiment that you plan to perform. Remember that your prediction of the outcome if the expirement must allow from the hypothesis you are testing. Then...
Read and print parallel array - How can this be made to read parallel arrays and...
Read and print parallel array - How can this be made to read parallel arrays and then print them? The program presented here is intended to read from the text file and build parallel arrays. Then it will print as shown. The first line will not be stored in the array. The second line will be stored in firstArray[] and the third line will then be stored in secondArray[] and the arrays will repeat until the file is read. begin...
Your company, Fun with Finance, has just completed a $5 million marketing survey that suggests that...
Your company, Fun with Finance, has just completed a $5 million marketing survey that suggests that your new computer role-playing game: "A day in prison with Mr. Madoff" is going to be a big hit. Producing the game will require an immediate $20 million capital investment in new equipment. At the same time, net working capital will have to increase from $3 million to $4 million, and remain at that level for the life of the project. The game is...
How can this problem be done WITHOUT using R? For the bird egg length data set,...
How can this problem be done WITHOUT using R? For the bird egg length data set, conduct an appropriate test to determine if bird egg length differs among species. Assume that before you conducted this test you hypothesized about 3 contrasts a priori. These were that (1) Meadow Pipits, Wagtails, and Robins would be different than the other 3 bird species, (2) Hedge Sparrows would differ from Wrens, and (3) Tree Pipits would be different than all other birds. Use...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT