Pages
Showing posts with label Parallel and Distributed Database. Show all posts
Showing posts with label Parallel and Distributed Database. Show all posts

Load Balancing

 
    Load balancing is an art or a way of distributing load units (jobs or tasks) across a set of processors that are connected to a network and may be distributed across the globe. Depending on the threshold value or hold the excess load from a process is migrated to other processors. The term threshold load is defined as the amount of load to a processor so that any load may not come further to that processors.
    In every system, there is always a possibility that some nodes are heavily loaded while some are having fewer loads. In such a case, processors in a system can be identified according to their present load. Based on this, they are termed as heavily loaded processors where enough jobs are waiting for execution, lightly loaded processors where fewer jobs are waiting and idle processors which have no job to execute. The basic aim is to make every processor equally busy and to finish the works approximately at the same time.
    In the load balancing operation, we have three rules: location rule, distribution rule and selection rule. The selection rule will work either in pre-emptive or in a non-pre-emptive way. The newly generated process is always picked up the non pre-emptive rule while the running process may be picked by the pre-emptive rule.

Benefits of Load Balancing:
  1. Load balancing improves the performance of each node and hence the overall system performance.
  2. It reduces the job idle time.
  3. Here, small jobs do not suffer from long starvation.
  4. It makes maximum utilization of resources.
  5. Response time becomes shorter.
  6. It gives higher throughput.
  7. It gives higher reliability.
  8. It has a low cost but high gain.
  9. It gives extensibility and incremental growth.
The taxonomy for the load balancing is shown below:
1) Static Load Balancing
        In static load balancing (SLB) procedure, the process is assigned to the processors at the compile time depending on the performance of the nodes. After the assignment of processes, no change or reassignment is possible at the runtime. The total number of jobs in each node is fixed in SLB algorithm. The information about the node is not collected by a static algorithm. The assignment job is done to the processing noded on the basis of following factors.
  1. Incoming Time
  2. The extent of resource needed.
  3. Mean execution time.
  4. Inter-process communication
2) Dynamic Load Balancing
        In the static load balancing, too much information about the system and jobs must be known before the execution. This particular information may not be available in advance. An in-depth and thorough study of the system state and the job associated is a quite tedious approach. To remove all the above ambiguity dynamic load balancing (DLB) algorithm came into existence.
    The assignment of jobs is done at runtime. In DLB, jobs are reassigned at the runtime depending upon the situation i.e, the load will be transferred from heavily loaded noded to lightly loaded nodes. In this case, communication overhead occurs and becomes more when the number of processors increases.

Desirable features of Global Scheduling Algorithm

 

The features of Global Scheduling Algorithm are as follows;

1) No apriori knowledge about the processes:

        The working of scheduling algorithm is based on the information about the characteristics and resource requirements of the processes. These pose extra burden on the users who must provide this information while submitting their processes for execution. No such information is required for global scheduling algorithm.


2) Dynamic in Nature:

        The decision regarding the assignment of process should be dynamic, which means that it should based on the current load of the system and not on the some static policy. The flexibility to migrate the process more than once should be the property of algorithm. The process should be placed on a particular node which can be changed afterwords, based on the initial decision in order to adapt to the change in system load.

3) Decision - making capabilities:

        If we think about the heuristic methods, they require less computational efforts that result in less time requirement for the output. This will provide a near optimal result and has decision - making capability.

4) Balancing System performance and Scheduling overhead:

        Here we require algorithm that will provide us near optimal system performance. It is desirable to collect minimum of global state information, such as CPU load. Such information is crucial because as the amount of global state information collected increases, the overhead also increases. This will have an impact on the result of the cost of gathering and processing the extra information  so there is a need to improve the system performance by minimizing scheduling overhead.

5) Stability:

        Processors thrashing ( due to the fruitless migration of processes) must be prevented. For example, if nodes n1 and n2 are loaded with processes and it is observed that node n3 is idle, then we can offload a portion of their work to n3 without being aware of the offloading decision made by some of the other nodes. In case n3 become overloaded due to this, it may again start transferring its processes to other nodes. The main reason for this is that scheduling decisions are being made at each node independently of decisions made by other nodes.

6) Scalability:

        The scheduling algorithm should be able to scale as the number of nodes increases. An algorithm can be termed as having poor scalability if it makes a scheduling decisions by first inquiring the workload from all the nodes and then selecting the most lightly loaded node. This concept will work fine only when we have few nodes in the system. This will happen because the inquirer receives a flood of replies simultaneously, and the time required to process the reply messages for making a node selection is too long. As the number of nodes (N) increases, the network traffic consumes network bandwidth quickly.

7) Fault Tolerance:

        In case one or more nodes of the system crash, good scheduling algorithm should not be disabled by this and mechanism to handle this should be available. The algorithm should be capable of functioning properly within the nodes if it is observed that the nodes are partitioned into two or more groups due to link failures. In order to have better fault tolerance capability, algorithms should decentralize the decision - making capability and must consider only available nodes in their decision - making and have better fault tolerance capability.

8) Fairness of Service:

        If the global scheduling policy blindly attempts to balance the load on all the nodes of the system, then they are not good if viewed in terms of fairness of service. This is because in any load -  balancing scheme, heavily nodes will obtain all benefits while lightly loaded nodes will suffer poor response time than in a stand alone configuration. Thus, we say that load balancing needs should be replaced by load sharing. That is, a node will share some of its resources as long as it users are not significantly affected.

State and prove Amdahl's Law to compute speedup of parallel computers.

 
    Amdahl's law is related to the speedup of a parallel computer. When a program is run on a parallel computer then the computation may be serial, parallel or both. At times, there will be a certain part of the program which has to run serially. This part is termed to be a sequential fraction of computing. Consider the sequential fraction of the program to be F. Then the parallel computation of the program will be 1-F. Based on this, Amdahl's  law states that the speedup of parallel computer is given by the relation.
S(p)≤1F+1−Fp
where 'p' is the number of processors. To prove the above relation, let us take an example of execution of a task on a computer with a single processor and p number of processors. We already know that the speedup is given by the relation,
S(p)=T(s)T(p)  ...(1)

Consider that the execution time required to complete the given task on a computer with single processor is T. When the same task is executed on parallel computer with p processors, then the time required will depend upon sequential computing time and parallel computing time that is,

T(p) = Sequential computing Time + Parallel Computing Time
T(p)=(F).(T)+(1−F).Tp        
4444

where 'p' is the number of processors. Therefore, by equation 1

S(p)=T(F).(T)+(1−F).Tp=1F+1−Fp       ...(2)

From equation (2), we can say that S(p) will always be ≤ 1, that is

S(p)≤1F+1−Fp
© Copyright 2015 TechBlogMU. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates.Powered by Blogger.