Monday, November 25, 2013

Scaleup and Speedup


Scaleup in Parallel (Systems) Database

Scaleup is the ability to keep the same performance levels (response time) when both workload (transactions) and resources (CPU, memory) increase proportionally.

Scaleup = (Small system small problem elapsed time[single machine])/(large system large problem elapsed time[parallel machine])

For example, if 50 users consume close to 100 percent of the CPU during normal processing, then adding more users would cause the system to slow down due to contention for limited CPU cycles. However, by adding more CPUs, we can support extra users without degrading performance.

Scaleup increases the Throughput, i.e, number of tasks completed in a given time increased.

Scale Up

Linear Scaleup 

Scaleup is linear if the resources increase in proportional with the problem size (it is very rare). According to the equation given above, if small system small problem elapsed time is equal to large system large problem elapsed time, then Scaleup = 1 which is linear.

Sub-linear Scaleup 

Scaleup is sub-linear if large system large problem elapsed time is greater than small system small problem elapsed time, then the scaleup is sub-linear.

Further useful discussions:

  • If scaleup is 1, i.e Linear, then performance of the system is excellent.
  • If scaleup is Sub-linear and the value falls between 0 and 1, then we need extra care to choose our plan for parallel execution. For example, if small system small problem elapsed time is 5 seconds, and large system large problem elapsed time is 5 seconds. This clearly shows Linear. That is, 5/5 = 1. For other values of denominator, especially low values (not possible beyond a limit), we would say that the system performance is excellent. But, for higher values of the denominator, say 6, 7, 8 and so on, the scale up value falls below 1 which needs much attention for better workload redistribution.

Speedup in Parallel (Systems) Database

Speedup is the effect of applying an increasing number of resources to a fixed amount of work to achieve a proportional reduction in execution times:
Speedup = (Small system elapsed time[single machine])/(large system elapsed time[parallel machine])
Speedup results in resource availability for other tasks. For example, if queries usually take ten minutes to process in one CPU and running in parallel in more CPUs reduces the time, then additional queries can run without introducing the contention that might occur were they to run concurrently.

Speedup reduces the Response Time, i.e, the time to complete a task is reduced.

Speed Up

Linear Speedup 

Speedup is linear if the speedup is N. That is, the small system elapsed time is N times larger than the large system elapsed time (N is number of resources, say CPU). For example, if single machine does the job in 10 seconds and if parallel machine (10 single machines) does the same job in 1 second, then the speedup is (10/1)=10 (refer to the equation above) which is equal to N which is the size of larger system. The speedup is achieved due to the 10 times powerful system.

Sub-Linear Speedup 

Speedup is sub-linear if speedup is less than N (which is usual in most of the parallel systems).

Further useful discussions:

  • If the Speedup is N, i.e Linear, then it means the expected performance is achieved.
  • If the Speedup is not equal to N, then following two cases possible;
    • Case 1: If Speedup > N, then it means the system performs more than it is designed for. The Speedup value in this case would be less than 1.
    • Case 2: If Speedup < N, then it is Sub-linear. In this case, the denominator (large system elapsed time) is more than the single machine's elapsed time. In such case, the value would vary between 0 and 1, where we need to fix a threshold value such that the value below threshold should not be accepted as parallel operation. Such a system needs extra care to redistribute the workload among processors.

What are the reasons for Sub-linear performance of speedup and scaleup


Following are the major factors which affect the efficient parallel operation and can reduce both speedup and scaleup.

Startup costs. 

For every single operation which is to be done in parallel, there is an associated cost involved in starting the process. That is, breaking a given big process into many small processes consumes some amount of time or resources. For example, a query which tries to sort the data of a table need to partition the table as well as instructing various parallel processors to execute the query before any parallel operation begins.
Example:
SELECT * FROM Emp ORDER BY Salary;

This query sorts the records of Emp table on Salary attribute. Let us assume that there are 1 million employees, so one million records. It will consume some time to execute in a computer with minimal resources. If we would like to execute the query in parallel, we need to distribute (or redistribute) the data into several processors (in case of Shared Nothing Architecture), also, we need to instruct all the processors to execute the query. These two operations need some amount of time well before any parallel execution happens.

Interference. 

Since processes executing in a parallel system often access shared resources, a slowdown may result from the interference of each new process as it competes with existing processes for commonly held resources, such as a system bus, or shared disks, or even locks. Both speedup and scaleup are affected by this phenomenon.

Skew. 

When breaking down a single task into number of parallel small tasks, it is very hard to make them equal in size. Hence, the performance of the system depends on the slowest CPU which processes the larger sub-task. This type of uneven distribution of a job is called skew. For example, if a task of size 100 is divided into 10 parts, and the division is skewed, there may be some tasks of size less than 10 and some tasks of size more than 10; if even one task happens to be of size 20, the speedup obtained by running the tasks in parallel is only five, instead of ten as we would have hoped.

2 comments:

  1. Speedup increases the Response Time, i.e, the time to complete a task is reduced.
    this is wrong thing! speed up decreases the response time

    ReplyDelete

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery