This paper focuses on cluster-based parallel database systems in which only one of the nodes has the database and the other nodes, which have no initial data, are used for parallel query processing. In such a system, the load of each node changes dynamically depending on the activities of the local users. In addition, in database query processing, data skew exists. Thus, it is very important to develop efficient load balancing/sharing algorithms. This paper proposes a new join algorithm called symmetric chunking hash join (SCHJ) that divides the hash buckets into chunks and uses them for load balancing. The SCHJ algorithm is compared with a dynamic round-robin algorithm and a sampling algorithm. The results show that the SCHJ algorithm is the best among these algorithms when there is data skew and background load variations

Summary form only given. Parallel database systems are capable of providing significant performance gains in terms of transaction processing rates. These gains are realized by running many transactions concurrently. A requirement in real-time transaction scheduling is to complete the transactions within their deadline. Due to its simplicity, two-phase locking (2PL) is one of the most commonly used concurrency control mechanism. Two alternative methods of securing locks in the 2PL protocol are static locking or dynamic locking. We report performance of the two locking variants of the 2PL protocol under various degrees of resource and data contention in a real-time parallel database system.

Cluster computing has come to prominence as a cost-effective parallel processing tool for solving many complex computational problems. The key to making cluster computing work well is the middleware technologies that can manage the policies, protocols, networks, and job scheduling across the interconnected set of computing resources. The research question addressed in this paper is the on-line job scheduling problem for multi-cluster systems. To this end, we propose an on-line dynamic scheduling policy that manages multiple job streams across both single and multiple cluster computing systems with the objectives of improving the mean response time and system utilization. The performance of the proposed scheduling policy is compared against a space-sharing policy and a time-sharing policy. The results of the experiments show that the proposed policy produces significantly better response times than the other two policies.

Traditional multiprocessor scheduling schemes have been one of either space-sharing or time-sharing. Space-sharing schemes perform better than time-sharing at low to moderate system loads. However, they have a disadvantage of wasting processing power within partitions at medium to high system loads. Time sharing schemes tend to perform better at medium to high system loads. Almost all the scheduling schemes proposed so far have been tested under ad hoc workload considerations. In light of recent knowledge about workloads, it is imperative to develop an integrated scheduling scheme that combines the advantages of space- and time-sharing while overcoming their individual drawbacks. We propose such a scheduling scheme, called Hierarchical Scheduling Policy, which is efficient as well as general enough to accommodate multiple workloads. Simulation results indicate that our scheme significantly outperforms the best space- and time-sharing mechanisms at medium to high system loads even in the absence knowledge regarding individual job characteristics.

Networks of workstations (NOWs) are attractive for parallel processing due to their cost advantage. This paper investigates the performance issues in processing join operations and the inherent tradeoff in the networked workstation environment. Specifically, we look at the performance of the nested-loop join algorithm. Since NOWs are heterogeneous in nature, load sharing is important for their performance. We evaluated the performance of three load sharing methods: static equal, static proportional and dynamic scheduling with fixed-chunk size. The three scheduling methods are evaluated on an experimental heterogeneous network of workstations with non-query background loads. Our experimental result suggest that, when there is no background load, dynamic scheduling outperforms static equal scheduling (up to 40%) and marginally better (about 10% better speedup) than the static proportional scheduling. When there is dynamic background load on nodes, dynamic scheduling provides substantial performance improvement over the static proportional scheduling (up to 50%) and static equal scheduling (up to about 100%). In all cases, selection of an appropriate chunk size is important in dynamic scheduling.

Networks of workstations (NOWs) can be used for parallel processing by using public domain software like PVM. However, NOW-based parallel processing suffers from node heterogeneity, background load variations, and high-latency, low-bandwidth communication network. Previous studies on load sharing in NOW-based systems have indicated that, for applications using the work-pile model, a simple load sharing scheme in which the master process gives a fixed amount of work to the slave processes performs as well as any other, more complex schemes. In this paper, we propose a new adaptive load sharing scheme and evaluate its performance using a Pentium-based NOW machine. The communication network used in the system consists of the standard 10 Mbps Ethernet and the 100 Mbps fast Ethernet. We use both these networks to study their impact on the performance of our new policy. The results presented here indicate that the new policy is useful for computation-intensive applications. Copyright © 1999 John Wiley & Sons, Ltd.

Processor scheduling policies for multiprocessor systems can be broadly divided into space-sharing and time-sharing policies. Space-sharing policies divide the system processors into a number of partitions and each partition is exclusively allocated to a single job. In time-sharing policies, processors are temporally shared by jobs. Several space-sharing and time-sharing policies have been proposed for small-scale shared-memory systems and require a central run queue and/or central scheduler. The central queue scheduler poses serious scalability problems for large-scale multiprocessor systems. Furthermore, space-sharing and time-sharing policies have their advantages and disadvantages. In this paper, we propose a new multiprocessor scheduling policy that eliminates contention for the central queue/scheduler. Our hierarchical scheduling policy (HSP) is a self-scheduling policy and uses a hierarchical run queue organization to facilitate processor allocation to jobs. We show that the HSP policy is considerably better than purely space-sharing and purely time-sharing policies over a wide range of system and workload parameters of interest.

Networks of workstations (NOWs) are cost-effective alternatives to multiprocessor systems. Recently, NOWs have been proposed for parallel query processing. Idle CPU cycles of workstations in a NOW-based system can be used to process database query operations. We report on the performance of the hierarchical architecture for parallel query processing on a NOW. We have implemented the hierarchical architecture using PVM on a Pentium-based NOW. The experimental results reported suggest that the hierarchical architecture is successful in achieving good scale-ups and speedups indicating that the idle processor cycles are effectively used for query processing. The hierarchical system can also handle both light and heavy workloads in a load sharing fashion. Our results also suggest that the performance is sensitive to the minimum fragmentation size (chunk size) for partial operations and the structure of queries.

Real-time transactions, in addition to preserving consistency of the database as in traditional transactions, have to meet the deadlines. Scheduling real-time transactions in parallel database systems has not received much attention. This paper focuses on real-time transaction scheduling in shared-nothing parallel database systems. We evaluate the performance of a new priority-based scheduling policy, in which all scheduling decisions are made locally by each node. In contrast, several other algorithms, proposed for the distributed systems, require communication among the nodes to globally synchronize their local block and abort decisions. Such synchronization can deteriorate performance as real-time transactions will have to meet deadlines. We use miss ratio as the performance metric and show that, in general, the new policy provides a superior performance for the workload and system parameters considered in this study.

Processor scheduling policies for distributed memory systems can be divided into space sharing or time sharing policies. In space sharing, the set of processors in the system is partitioned and each partition is assigned for the exclusive use of a job. In time sharing policies, on the other hand, none of the processors is given exclusively to jobs; instead, several jobs share the processors (for example, in a round robin fashion). There are advantages and disadvantages associated with each type of policy. Typically, space sharing policies are good at low to moderate system loads and when job parallelism does not vary much. However, at high system loads and widely varying job parallelism, time sharing policies provide a better performance. We propose a new policy that is based on a hierarchical organization that incorporates the merits of these two types of policies. The new policy is a hybrid policy that uses both space sharing as well as time sharing to achieve better performance. We demonstrate that, at most system loads of interest, the proposed policy outperforms both space sharing and time sharing policies by a wide margin.

Dynamic load sharing policies have been extensively studied. Most of the previous studies have assumed a homogeneous distributed system with a first-come/first-served (FCFS) node scheduling policy. In addition, job service times and inter-arrival times are assumed to be exponentially distributed. In this paper, we study the impact of these assumptions on the performance of sender-initiated and receiver-initiated dynamic load sharing policies in heterogeneous distributed systems. We consider two node scheduling policies-the FCFS and round-robin (RR) policies. Furthermore, the impact of variance in inter-arrival times and job service times is studied. Our results show that, even in heterogeneous distributed systems, when the RR policy is used, sender-initiated policy is better than the receiver-initiated policy unless the variance in job service times is low. This is an important observation, as most workstations use a scheduling policy that is similar to the RR policy considered in this paper.

In dynamic load sharing policies, system state information can be collected in a distributed manner or by a single coordinator node. Two principal policies that belong to the distributed scheme are the sender-initiated and receiver-initiated policies. In the centralized scheme, a central coordinator node is responsible for collecting system state information. Distributed policies do not perform as well as the centralized policy. The performance of distributed policies is sensitive to the variance in job service times and inter-arrival times. Distributed policies, however, are scalable, whereas the centralized policy can cause bottlenecks and fault-tolerance problems for large systems. We propose a hierarchical load sharing policy that minimizes the drawbacks associated with the distributed and centralized policies while retaining their advantages.

Load sharing is a technique to improve the performance of distributed systems by distributing the system workload from heavily loaded nodes, where service is poor, to lightly loaded nodes in the system. Previous studies have considered two adaptive load sharing policies: sender-initiated and receiver-initiated. In the sender-initiated policy, a heavily loaded node attempts to transfer work to a lightly loaded node and in the receiver-initiated policy a lightly loaded node attempts to get work from a heavily loaded node. Almost all the previous studies assumed the first-come/first-served node scheduling policy; furthermore, analysis and simulations in these studies have been done under the assumption that the job service times are exponentially distributed and the job arrivals form a Poisson process (i.e., job inter-arrival times are exponentially distributed). The goal of this paper is to fill the void in the existing literature. We study the impact of these assumptions on the performance of the sender-initiated and receiver initiated policies. We consider three node scheduling policies-first-come/first-served (FCFS), shortest job first (SJF), and round robin (RR) policies. Furthermore, we also look at the impact of variance in the inter-arrival times and in the job service times. Our results show that: (i) When non-preemptive node scheduling policies (FCFS and SJF) are used, the receiver-initiated policy is (substantially) more sensitive to variance in inter-arrival times than the sender-initiated policies and the sender-initiated policies are relatively more sensitive to the variance in job service times; (ii) When the preemptive node scheduling policy (RR) is used, the sender-initiated policy provides a better performance than the receiver-initiated policy.

There are two basic ways in which waiting ready tasks can be organized: centralized organization or distributed organization. In the centralized organization, a single central task queue is maintained. In the latter case, private ready queue of tasks. Ideally, a central ready queue global to all processors is desired over the distributed organization because the centralized organization provides perfect load sharing. However, the centralized organization is not suitable for large parallel systems because the central task queue could become a system bottleneck. The distributed organization, on the other hand, creates the load imbalance problem, which results in performance deterioration, while techniques have been proposed to reduce the ill-effects of task queue contention in the centralized organization and load imbalance in the distributed organization these techniques introduce problems of their own. We propose the use of a hierarchical task queue organization to incorporate the best features of these two organizations. Our study into the performance of this hierarchical organization shows that a properly designed hierarchical organization provides performance very close to that of the centralized organization while eliminating the ready queue contention problem, we also provide an analysis that identifies and provides guidance for designing the hierarchical task queue organization that avoids ready queue access contention. A brief discussion of task scheduling policies is also included.>

A hierarchical task queue organization that avoids the task queue bottleneck associated with the centralized organization and provides performance better than centralized and distributed organizations is proposed. A detailed performance analysis shows that the hierarchical organization is less sensitive to parameters like the branching factor and transfer factor. Therefore, it is suitable for large parallel systems.>

To exploit multiple processors, a job is usually partitioned into several tasks that can be executed concurrently. These tasks wait for processors in task ready queue(s). There are two basic ways in which waiting ready tasks can be organized: centralized organization or distributed organization. In a centralized organization, a single central task queue is maintained. In the latter case, each processor has its own private ready queue of tasks. Ideally, a central ready queue global to all processors is desired over the distributed organization. However, the centralized organization is not suitable for large parallel systems because the global task queue could become a bottleneck. A hierarchical organization has been proposed to incorporate the good features of these two organizations. This paper studies the impact of job and task scheduling policies on the performance of the hierarchical organization.

Consideration is given to the impact of hot-spot contention in distributed-memory multicomputer systems. Since the binary hypercube network offers a reasonable compromise between network cost and performance, two hypercube-based static interconnection networks are considered. One is a standard binary hypercube and the other is a binary hypercube-based hierarchical interconnection network. The impact of hot-spot contention in both these networks is studied.>

The effects of locking granularity in a shared-nothing multiprocessor database system are analyzed. The analysis shows that when the system is lightly loaded fine granularity (one lock per database entity) is needed when transactions access the database randomly. However, when transactions access the database sequentially, coarse granularity is desired. When the system is heavily loaded, coarse granularity is desirable. The results also indicate that horizontal partitioning results in better performance than random partitioning.>

Partial-match search queries form an important class of queries posed to a database system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A partial-match search algorithm, called AORIG, is given in Ref. 5. This paper presents three algorithms – ALOCAL, ACOMP and AGLOBAL – that represent three levels of improvement to AORIG. Each one yields successively more benefit at the cost of more complexity. All the improvements centre on avoiding the exploration of unnecessary OUT branches. It is shown that AGLOBAL is the best partial-match search algorithm in the sense that no other algorithm searches fewer internal and external nodes. The worst-case complexity of performing a partial-match search in BD trees using AGLOBAL is shown to be the same as that for the k-d trees.

A performance analysis of a class of hierarchical interconnection networks is presented. The analysis includes both static analysis (i.e. queueing delays are neglected) and queueing analysis. In both cases, the hierarchical networks are shown to have better cost-benefit ratios. The queueing analysis is also validated by several simulation experiments. The impact of two performance enhancement schemes-replication of links and improved routing algorithms-on hierarchical interconnection network performance is also presented.>

Abstract Database systems are becoming increasingly popular for answering queries. Partial‐match search queries are an important class of queries in such a system. Several storage structures have been proposed to answer these queries efficiently. The BD tree is an example of such a storage structure. A previous study indicated that the k‐d tree performance is better than that of the BD tree for partial‐match search queries. A recent paper reported some improved algorithms. However, it is unclear whether the improved algorithms show the BD tree in a favourable light for partial‐match search queries. This paper explores the performance of these algorithms and compares their performance to that of the k‐d tree. Since the BD tree construction process uses some heuristics to make it a better balanced tree, this paper also evaluates the effect of these heuristics on the partial‐match search algorithms. The major conclusions of this study are that the BD tree performance for partial‐match search is better than that of the k‐d tree when an improved algorithm is used for partial‐match search, and only the DZ expression rearrangement heuristic has substantial effect on partial‐match search performance.

Abstract Database applications often require a sophisticated class of storage structures in order to answer different types of queries efficiently. This often dictates that the file should be organized on multiple keys. Several storage structures have been proposed to satisfy these needs. Most are generalizations of the storage structures used for managing one‐dimensional data. Recently, a new storage structure, called the BD tree, was proposed to manage multidimensional data. This structure has good dynamic characteristics. This paper presents algorithms for the BD tree to perform insertion, deletion, and to answer exact match, partial match and range queries. In addition, some experimental evidence is presented that suggests that BD trees have good dynamic characteristics.