1
$\begingroup$

On my homework the question asks:

A program executes serially in 200 seconds. If it is parallelized, 7 seconds of overhead are required for synchronization, locking, and communication. Compute the execution time, ideal speedup (if there were no overhead required), actual speedup, and the percentage of the ideal speedup that is obtained for 1, 2, 4, 8, 16, 32, 64, and 128 processors.

How do I calculate the answer to this? It is not something that has been covered in class yet and the homework is due before the next time the class meets.

My guess is that I divide 200 seconds by the number of cores and then add 7 * # cores to get the total response time. I don't think it is that simple.

Edit:
Amdahl's law says: T(n) = T(1)[B + 1/n(1-B)] where B is the percentage of the algorithm that is not parallelized and n is the number of cores. If I assume that the 7 seconds mentioned is the part of the algorithm that is not parallelized, I can get the percentage by saying:

      7sec * n
B  =  --------
       200sec 

Then I plug the value for B into Amdahl's equation. Coencidentally, this gives me the same answers as I got before when I did my own formula:

 200                   
 ---  +  [7 * (n - 1)] 
  n     

After doing a little bit of algebra, I discovered that my formula is a simplified version of Amdahl's formula. Of course all of this assumes I am correct when I read the question as if the 7 seconds are the part of the algorithm that is not parallelized.

Thanks for looking,

Zach

$\endgroup$
  • $\begingroup$ Take a look at the Amdahl's law $\endgroup$ – francis Jan 23 '15 at 20:41
  • $\begingroup$ I did look at amdahl's law and I am not sure how to use it. The part I am not sure about is the part that is not parallelized. The question does not say what percentage of the algorithm is not parallelized. $\endgroup$ – zkirkland Jan 23 '15 at 20:49
  • $\begingroup$ I would say that @MahdiDolati is right : the 7 seconds are to be counted only once. The sequential run takes 200s, two processes would take 107s, hence the speed up is 200/107=1.86 : not too far from the optimal situation (2). With 100 processes, the wall clock time would be 2+7=9s and the speed up would be 200/9=22.2, which is not very close to the ideal speed up (100). $\endgroup$ – francis Jan 23 '15 at 20:55
  • $\begingroup$ There is a problem in your approach. B is a fraction number and should be less than 1. But, say, n equals to 30 or more, then your formula for B will be greater than 1. $\endgroup$ – Mahdi Dolati Jan 25 '15 at 5:52
1
$\begingroup$

I think you don't need to add (7*number of cores) to the total response time. The overall execution time requires just 7 more seconds, because each piece of code is running in parallel with others. So just divide 200 by the number of cores and add 7 to it. Obviously in the ideal case you don't need to add anything. Also look at the Amdahl's law in the Wikipedia... It also states a law about speedup with parallelism and these problems share the same concept.

$\endgroup$
  • $\begingroup$ The problem that was posed is actually unclear and requires guessing. Your guess "seven seconds per core" is very reasonable, but it might be just "seven seconds". Blame the person who posed an unclear problem. $\endgroup$ – gnasher729 Jul 17 '18 at 9:02
0
$\begingroup$

I guess this type of optimization is calculate based on SpeedUp measurement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.