Thursday, March 14, 2013

Concurrency Speed Up Factor : Amdahl's Law

Amdahl's Law or Amdahl's argument defines the Maximum improvement of a collective system when the parts of the system are improved.

In parallelisation or Concurrency domain, it defines the Maximum SpeedUp Factor when then task executed on a single processor is divided into tasks that can be executed by Multiple Processors.

What is Speedup ?

Speed up factor is the ration of  'Time of Execution on a single processor' Vs 'Time of exection on a processor when the task is distributed in parallel across N processors'

Lets assume a Task , task_overall , is executed on a single processor. Let the time of exection = T(task_overall)
Now the nature of the task permits it be divided N number of smaller tasks.
Let each smaller task = task(i) , where i <= n and i = 1, 2,..,N
In order of improve time execution , we decide to execute each task(i) on a separate processor

Since the Time of execution on a single process IS PROPORTIONAL TO amount of task executed.
Let theTime of Execution for a chunk of task, task(i) = T(i) , where task(i) = task(over_all)/N fraction of the complete task.
So the new fractional time on each processor now is T(i) = T(task_overall)/N
Sped Up factor =  T(task_overall)/T(i)
E.g :
Let T(task_overall) = 10 hours. i.e It takes 10 hours to do a task on a single processor.
Let's divide this task into 7 chunks and allow it to processed by 7 processors.
Fractional task executed at each processor now is 1/7
So reduced Time on each processor has changed from 10 hours to 10*(1/7) = 10/7
This ratio of the previous time to this reduced time is the Speed Up Factor.
Speed Up Factor = T(over_all) / T(i) = 10/ (10/7) = 7 
So speed increases seven times by dividing a task in parallel across 7 processors.

Speed up Factor when only a part of task can be parallelised

Let the Task, task_overall consists of  a fraction of task that cannot be parallelised. i.e this fraction of task can be executed only serially , hence no speed up can be gained on this fraction when the number of parallel processes is increased

Task( over_all ) = Task( serial ) + Task( task that can be parallelised )
Task( over_all ) = K percent of Task ( serial )   + ( 1 - K ) percent of Task ( parallel )
Since Time is proportional to task
T( over_all ) = K % T ( over_all )  + ( 1 - K ) % T ( over_all)
T(i) = K % T ( over_all )  + ( 1 - K ) % T ( over_all) / N

So Speed Up Factor = T( over_all ) / T ( i )
Speed Up Factor = 1 / [ f + (1-f)/N ]

Here f = K % T( over_all ) i.e f represents the fraction of task that cannot be parallelized

Amdahl's Law can be used to measure increase in execution time when chunks of serial + parallel tasks is executed in parallel across multiple processors.

This Law can also be used to measure the performance gains on concurrent executions by threads

No comments:

Post a Comment