Technologies of parallel database systems for hierarchical multiprocessor environments

For the multiprocessor systems of the hierarchical-architecture relational databases, a new approach to data layout and load balancing was proposed. Described was a database multiprocessor model enabling simulation and examination of arbitrary multiprocessor hierarchical configurations in the context of the on-line transaction processing applications. An important subclass of the symmetrical multiprocessor hierarchies was considered, and a new data layout strategy based on the method of partial mirroring was proposed for them. The disk space used to replicate the data was evaluated analytically. For the symmetrical hierarchies having certain regularity, theorems estimating the laboriousness of replica formation were proved. An efficient method of load balancing on the basis of the partial mirroring technique was proposed. The methods described are oriented to the clusters and Grid-systems.     

Bandwidth availability of m-level hierarchical multiprocessor systems

In previous work, we proposed an m-level hierarchical multiprocessor system. The proposed system reduces the network complexity by employing m levels of hierarchy. The system performance was analyzed, and the results showed that, for a higher rate of local requests, the system performed close to the crossbar system, and better than a typical multiple-bus system (with the number of buses equal to half the number of processors). In this paper, we study the effect of failures on the performance of the m-level hierarchical multiprocessor systems. We develop analytical modeling techniques to compute the reliability and the bandwidth availability of the m-levelsystem, for hierarchically nonuniform reference (HNR) and uniform reference (UR) models. The results obtained for the m-level system are compared with those of the crossbar and multiple-bus systems.     

Approximate performance/cost analysis of m-level hierarchical multiprocessor systems

In previous work, we introduced and analyzed a generalized class of m-level hierarchical multiprocessor systems [1]. The m levels of hierarchy employed by these systems allowed the use of relatively smaller crossbar switches to support processor-memory communication at the local, nonlocal, and global levels. The analysis showed that, for high rate of local requests the m-level system offers a BandWidth (BW) close to that of a crossbar system and better than that of a typical multiple-bus system (with the number of buses equal to half the number of processors). In this paper, the cost effectiveness of the m-level hierarchical multiprocessor system is evaluated in terms of a cost-related performance measure (BW/Cost). Based on an approximate cost analysis, the bandwidth-to-cost ratio of both the m-level and the crossbar multiprocessor systems has been determined, for hierarchically nonuniform reference model. It has been observed that the m-level system is more effective than the crossbar system for medium and large scale multiprocessor systems.     

EMMA2: a high-performance hierarchical multiprocessor

The development of a parallel system providing high computational power at a reasonable cost using inexpensive processors is described. The original motivation for the work, which led to the EMMA (Elaborate Multi-Mini Associativo) multicomputer, was the mechanization of mail sorting. The need for a system that could be the basis for a wider range of applications spurred the study and development of a new system, the EMMA2. The discussion covers EMMA2's characteristics, architecture, buses, standard modules, I/O, approach to coprocessors, and operating system     

Physical datarepresentation in a multiprocessor database machine

By using a multiprocessor to implement the lowest level of a relational database we want to achieve fast execution of database operations such as join, find, and update. But the potential speed improvements provided by a multiprocessor can only be achieved if one can construct algorithms and corresponding physical data representations that can utilize the potential. By choosing a particular representation, the grid file, and analyzing its behaviour, we want to point out the difficulties encountered in trying to achieve speed improvements from a multiprocessor.     

Comparison of five multiprocessor systems

This paper generalizes the traditional dataflow model of computation and defines the essential problems in multiprocessing: control implementation, program partitioning, scheduling, synchronization, and memory access. The paper assumes that these essential problems are axes of a multiprocessor design space and that the solutions to these problems are values on the axes. Each point in the space represents a multiprocessor including a computational paradigm that a user must follow to achieve high performance and efficiency on the particular machine. Thus, a classification of machines from the user's point of view is introduced naturally. Five well-known multiprocessors are compared using this classification scheme.     

Dynamic partitioning of multiprocessor systems

Partitioning of processors on a multiprocessor system involves logically dividing the system into processor partitions. Programs can be executed in the different partitions in parallel. Optimally setting the partition size can significantly improve the throughput of multiprocessor systems. The speedup characteristics of parallel programs can be defined by execution signatures. The execution signature of a parallel program on a multiprocessor system is the rate at which the program executes in the absence of other programs and depends upon the number of allocated processors, the specific architecture, and the specific program implementation. Based on the execution signatures, this paper analyzes simple Markovian models of dynamic partitioning. From the analysis, when there are at most two multiprocessor partitions, the optimal dynamic partition size can be found which maximizes throughput. Compared against other partitioning schemes, the dynamic partitioning scheme is shown to be the best in terms of throughput when thereconfiguration overhead is low. If the reconfiguration overhead is high, dynamic partitioning is to be avoided. An expression for the reconfiguration overhead threshold is derived. A general iterative partitioning technique is presented. It is shown that the technique gives maximum throughput forn partions.     

A hierarchical multiprocessor bandwidth reservation scheme with timing guarantees

A multiprocessor scheduling scheme is presented for supporting hierarchical containers that encapsulate sporadic soft and hard real-time tasks. In this scheme, each container is allocated a specified bandwidth, which it uses to schedule its children (some of which may also be containers). This scheme is novel in that, with only soft real-time tasks, no utilization loss is incurred when provisioning containers, even in arbitrarily deep hierarchies. Presented experiments show that the proposed scheme performs well compared to conventional real-time scheduling techniques that do not provide container isolation.

MDARTS: a multiprocessor database architecture for hard real-timesystems

Complex real time systems need databases to support concurrent data access and provide well defined interfaces between software modules. However, conventional database systems and prior real time database systems do not provide the performance or predictability needed by high speed, hard real time applications. The authors designed, implemented, and evaluated an object oriented database system called MDARTS (Multiprocessor Database Architecture for Real Time Systems). MDARTS avoids the client server overhead of most prior real time database systems and object oriented, real time systems by moving transaction execution into application tasks. By eliminating these sources of overhead and focusing on basic data management services for control systems (data sharing, serializable transactions, and multiprocessor support), the MDARTS prototype provides hard real time transaction times approximately three orders of magnitude faster than prior real time database systems. MDARTS ensures bounded locking delay by disabling preemption when a transaction is waiting for a lock, and hence, allows for the estimation of worst case transaction execution times. Another contribution of MDARTS is that it supports explicit declarations of real time requirements and semantic constraints within application code. The MDARTS library examines these declarations at application initialization time and attempts to construct objects that are compatible with the requirements. Besides local shared memory transactions with hard real time response time guarantees, MDARTS also supports remote transactions that use remote procedure calls for data access with less stringent timing constraints. The MDARTS prototype is implemented in C++ and it runs on VME based multiprocessors and Sun workstations     

Tuning a parallel database algorithm on a shared-memory multiprocessor

Database query processing can benefit significantly from parallelism. Parallel database algorithms combine substantial CPU and I/O activity, memory requirements, and massive data exchange between processes, all of which must be considered to obtain optimal performance. Since parallel external sorting is a very typical example, we have focused on sorting to tune Volcano, a new query processing system. The purpose of the Volcano project is to provide efficient, extensible tools for query and request processing in novel application domains, particularly in object-oriented and scientific database systems, and for experimental database performance research. It includes all query processing algorithms conventionally used in relational database systems as well as several new ones, and can execute all of them in parallel. In this article, we present Volcano's parallel external sorting algorithm and a sequence of enhancements to improve its performance. We obtained very good absolute performance, 84 seconds for 100 MB of data, as well as near-linear speedup with sixteen CPUs and disks. Furthermore, these results were achieved on a shared-memory machine despite the common belief that parallel query processing is best implemented on distributed-memory systems. We detail our tuning measures and report on their effectiveness.     

Queuing simulation model for multiprocessor systems

The processor queuing model provides memory-hierarchy and system-design evaluation of memory-intensive commercial online-transaction-processing workloads on large multiprocessor systems. It differs from detailed cycle-accurate and direct-execution simulations in that it does not simulate instruction execution. Instead, as in analytical models, the authors build processor and workload characteristics that are easy to collect and estimate. Because the authors believe that the processor model's function is to accurately generate memory traffic to the rest of the system, they model a minimal set of processor and workload characteristics that captures the important interactions between a complex processor and the system-memory hierarchy.     

Optimal fault-tolerant computing on multiprocessor systems

Suppose identical processors, each subject to random failures, are available for running a single job of given duration . The failure law is operative only while a processor is active. To guard against the loss of accrued work due to a failure, checkpoints can be made, each requiring time ; a successful checkpoint saves the state of the computation, but failures can also occur during checkpoints. The problem is to determine how best to schedule checkpoints if the goal is to maximize the probability that the job finishes before all processors fail. We solve this problem first for and an exponential failure law. For given and we show how to determine an integer and time intervals such that an optimal procedure is to run the job on one processor, checkpointing at the end of each interval , until either the job is done or a failure occurs. In the latter case, the remaining processor resumes the job starting in the state saved by the last successful checkpoint; the job then runs until it completes or until the second processor also fails. We give an explicit formula for the maximum achievable probability of completing the job for any fixed . An explicit result for , the optimum value of , seems out of reach; however, we give upper and lower bounds on that are remarkably tight; they show that only a few values of need to be tested in order to find . With the failure rate normalized to 1, we also derive the asymptotic estimate and calculate conditional expected job completion times. For the more difficult problem with processors, we formulate a computational approach based on a discretized model in which the failure law is the analogous geometric distribution. By proving a unimodality property of the optimal completion probability, we are able to describe a computation of this optimum that requires time, where is the job running time. Several examples bring out behavioral details. Received: 29 September 1995 / 29 January 1997     

Resource reclaiming in multiprocessor real-time systems

Most real-time scheduling algorithms schedule tasks with regard to their worst case computation times. Resources reclaiming refers to the problem of utilizing the resources left unused by a task when it executes in less than its worst case computation time, or when a task is deleted from the current schedule. Dynamic resource reclaiming algorithms that are effective, avoid any run time anomalies, and have bounded overhead costs that are independent of the number of tasks in the schedule are presented. Each task is assumed to have a worst case computation time, a deadline, and a set of resource requirements. The algorithms utilize the information given in a multiprocessor task schedule and perform online local optimization. The effectiveness of the algorithms is demonstrated through simulation studies     

Routing in modular fault-tolerant multiprocessor systems

In this paper, we consider a class of modular multiprocessor architectures in which spares are added to each module to cover for faulty nodes within that module, thus forming a fault-tolerant basic block (FTBB). In contrast to reconfiguration techniques that preserve the physical adjacency between active nodes in the system, our goal is to preserve the logical adjacency between active nodes by means of a routing algorithm which delivers messages successfully to their destinations. We introduce two-phase routing strategies that route messages first to their destination FTBB, and then to the destination nodes within the destination FTBB. Such a strategy may be applied to a variety of architectures including binary hypercubes and three-dimensional tori. In the presence of f faults in hypercubes and tori, we show that the worst case length of the message route is min {σ+f, (K+1)σ}+c where σ is the shortest path in the absence of faults, K is the number of spare nodes in an FTBB, and c is a small constant. The average routing overhead is much lower than the worst case overhead     

Fault diagnosis in hypercube multiprocessor systems

Hypercubes are viewed as good candidates for parallel processing, because a number of topologies, such as rings, trees, and meshes, can be mapped onto the hypercubes. In this paper, we study a system level diagnosis method for clustered faults in hypercube systems. We investigate the local and global performance of the method under the Bernoulli failur distribution. We demonstrate that the diagnosis scheme can identify almost all processors successfully even if the percentage of fault-free processors is low (much lower than 50%) while almost all processors are guaranteed to be correctly identified.