Insight into class lecture of 24th feb 2014

Summary of February 24^th class

 

AMDAHL'S LAW

 

''Amdahl's law, also known as Amdahl's argument, is used to find the maximum expected improvement to an overall system when only part of the system is improved. It is often used In parallel to predict the theoretical maximum speedup using multiple processors."

                                             

 Graph : Speedup vs Number of Processors

  FORMULAE DESCRIBING AMDAHL'S LAW:

 speed up = T(1)/T(n) =  [ I (B+ 1-B)/ rate ]/  [I( B + (1-B)/n ) /rate]

Here I = total no. of instructions,

B = ratio of sequential instructions to total instructions, n = no. of processors

Rate here is considered to be constant and no overheads have been considered in Amdahl's law

Therefore if a more realistic situation is considered the entire process would also include overheads, as a function of

• Size of Network
• Size of problem
• No. of processors

 

 Hence the Speedup in such case would be

 = ∑ work at all modes / ∑ ((W_i / i) [i/n] + O(s,n))

Wi = work at ith mode, i = the i^th mode, { [ ] denotes ceiling }

O(s,n) = function of size of problem and no. of processor

Therefore a graph is plotted for speed up versus B, a hyperbolic graph is obtained which proves that with increase of processors the system losses its parallism on a very fast rate  .

 To overcome this drawback Gustafson Law was introduced .

If the rates of n processors are r1 , r2, r3, r4 ,…..,rn.

Then the average rate is the harmonic mean of the individual rates.

Moreover, the average rate is kind of a weighted harmonic mean.

Rate _{avg  =}  1/[(f1/r1) + (f2/r2) + (f3/r3) + …… + (fn/rn)]

         Where f_i is the number of instructions executed by i^th processor.

** It ws still not clear whether we should multiply the numerator with F or not        where F = total number of instructions.

 

Gustafson Law

 

''Gustafson's Law is a law in computer science which says that computations involving arbitrarily large data sets can be efficiently parallelized'''. Wikipedia

''Thus Gustafson's law seems to rescue parallel processing from Amdahl's law''. Wikipedia

Explore: Amdahl's law

"Gustafsons law states that increasing processors gives linear speed up''. eecis.udel.edu

Explore: Speedup

According to Gustafson Law, proportionality of parallelism can be maintained by increasing the parallelizable workload as the work assigned gets distributed among the increasing no. of processors.

 Wikipidea

The graph shows linear increase and doesn't saturate unlike in case of Amdahl's law.

FORMULAE DESCRIBING Gustafson Law :

SPEEDUP = [B + n(1 -B)] / [B + n(1-B)/n]

Here

B= ratio of sequential instructions to total instructions , n = no. of processors

Efficiency = E = Speedup/ no. of processors

Redundency =R  = O(n) / O (1)

Utilization = E x R

Quality of Parallism = (speedup ) x E/R

 Now if we express the Quality of parallism in terms of time

Quality of parallism = T(1)

 

INSIGHTS PROVIDED:

• FOR MAINTAINING THE PROPORTIONALITY OF PARALLISM ON INCREASING THE NO.OF PROCESSORS MORE WORK SHOULD BE ASSIGNED
• FOR PURELY AMDAHL'S LAW , NOT WIE TO INCREASE PROCESSORS BEYOND A CERTAIN LIMIT.

 

 

Submitted by : Suraj Gupta and Tina Biswas