Speed up - metrics for performance evaluation, Computer Engineering

Assignment Help:

Q. Speed Up - metrics for performance evaluation?

Speed up is ratio of time needed to execute a given program employing a specific algorithm on a machine with single processor (It implies that T (1) (where n=1)) to time needed to execute same program using a particular algorithm on a machine with multiple processors (It implies that T (n)). Fundamentally speed up factor helps us in knowing relative gain achieved in shifting from a sequential machine to a parallel computer. It can be noted the term T(1) denotes amount of time taken to execute a program employing the best sequential algorithm It implies that the algorithm with least time complexity. 

2366_Speed Up - metrics for performance evaluation.png

Let's take an illustration and explain practical use of speedup. Suppose we have a problem of multiplying n numbers. Time complexity of sequential algorithm for a machine with single processor is O(n) because we require one loop for reading and computing output. But in the parallel computer let every number is assigned to specific processor and computation model being used being a hypercube. In such a condition the total number of steps essential to compute result is log n it implies that time complexity is O(log n). Figure below explains the steps to be followed for achieving the required output in a parallel hypercube computer model.

As number of steps followed is equivalent to 3 it implies that log 8 where n is number of processors. Therefore complexity is O(log n). 

In view of fact sequential algorithm takes 8 steps whereas above mentioned parallel algorithm takes 3 steps speed up is as under:

1715_Speed Up - metrics for performance evaluation1.png

Because value of S(n) is inversely proportional to time needed to calculate output on a parallel number that in turn is dependent on number of processors used for performing the computation. The relation amid S(n) versus Number of processors is displayed in Figure. The speedup is directly proportional to number of processors so a linear arc is portrayed. But in situations where there is parallel overhead the arc is sub-linear.

716_Speed Up - metrics for performance evaluation3.png

Figure: Steps followed for multiplying n numbers stored on n processors

295_Speed Up - metrics for performance evaluation2.png

Figure: Speed-up vs. Number of Processors


Related Discussions:- Speed up - metrics for performance evaluation

Discuss about fourth generation electronic computers, Fourth Generation (19...

Fourth Generation (1972-1984) The next generation of computer systems used the large scale integration (LSI -1000 devices per chip) and very large scale integration (VLSI - 100

Explain the concept of process, The Concept of Process Unofficially a p...

The Concept of Process Unofficially a process is a program in execution subsequent to the program has been loaded in the main memory. Though a process is more than just a progr

Give an example of shortest job next scheduling, Consider the following set...

Consider the following set of jobs with their arrival  times, execution time (in minutes), and deadlines. Job Ids Ar r ival Time E xecuti

Explain the disadvantages of random scan display, Disadvantages of random s...

Disadvantages of random scan display - Just by wire-frame, it is almost impossible to create images with shaded objects or areas filled with a given colour. - In case

Show matrix multiplication problem, Q. Show Matrix Multiplication Problem? ...

Q. Show Matrix Multiplication Problem? Let there be 2 matrices M1 and M2 of sizes a x b and b x c correspondingly. If we multiply M1 and M2 product matrix O will be of size a x

Evaluate expression by using convention , Evaluate x = A ‾.B + C ( ) usin...

Evaluate x = A ‾.B + C ( ) using the convention A = True and B = False. Ans. Simplify given expression x = A ‾ .B + C ( ) as = A ‾ B + C (A ‾ + D ‾ ) (As = A ‾ +D ‾ usin

Comparison between motorola processors and intel processors, Comparison bet...

Comparison between Motorola processors and INTEL processors: Intel/AMD processors are really about the same thing.  They run the same software and operate in a very similar ma

What do you mean by segment numbers, Q. What do you mean by Segment numbers...

Q. What do you mean by Segment numbers? There is a good reason for not leaving determination of segment numbers up to assembler. It permits programs written in 8086 assembly

What is shared memory programming, Q. What is Shared Memory Programming? ...

Q. What is Shared Memory Programming? We know all processors share a common memory in shared memory model. Every processor can be assigned a separate portion of program stored

Computer graphics, explain area sub division method algorithm

explain area sub division method algorithm

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd