A Fast and Efficient Processor Management Scheme fork-aryn-cubes

Job scheduling and processor allocation are two key components of processor management technique in a multiprocessor operating system. We propose a fast and efficient processor management technique, called virtual cube (VC), fork-aryn-cubes in this paper. The proposed scheme supports spatial allocation of jobs to the virtual cubes of the system and multiprograms the virtual cubes in a round-robin fashion. The objective here is to reduce job waiting time and fragmentation. The VC scheme uses a fast subcube allocation algorithm called enhancedk-ary buddy. A novel approach, called paging, is proposed for fast submesh allocation. When used with the first fit algorithm, the paging scheme is shown to be extremely fast and efficient compared to other contemporary submesh allocation algorithms fork-aryn-cubes. We also study the impact of page size on performance and illustrate a methodology to compute optimal page size. Simulation results show that the VC scheme with its multiprogramming capability can boost system performance considerably and outperforms all existing policies while incurring minimal run-time overhead.     

Optimization of parallel execution for multi-join queries

We study the subject of exploiting interoperator parallelism to optimize the execution of multi-join queries. Specifically, we focus on two major issues: (1) scheduling the execution sequence of multiple joins within a query, and (2) determining the number of processors to be allocated for the execution of each join operation obtained in (1). For the first issue, we propose and evaluate by simulation several methods to determine the general join sequences, or bushy trees. Despite their simplicity, the heuristics proposed can lead to the general join sequences that significantly outperform the optimal sequential join sequence. The quality of the join sequences obtained by the proposed heuristics is shown to be fairly close to that of the optimal one. For the second issue, it is shown that the processor allocation for exploiting interoperator parallelism is subject to more constraints-such as execution dependency and system fragmentation-than those in the study of intraoperator parallelism for a single join. The concept of synchronous execution time is proposed to alleviate these constraints. Several heuristics to deal with the processor allocation, categorized by bottom-up and top-down approaches, are derived and are evaluated by simulation. The relationship between issues (1) and (2) is explored. Among all the schemes evaluated, the two-step approach proposed, which first applies the join sequence heuristic to build a bushy tree as if under a single processor system, and then, in light of the concept of synchronous execution time, allocates processors to execute each join in the bushy tree in a top-down manner, emerges as the best solution to minimize the query execution time     

Multiple query scheduling for distributed semantic caches

In distributed query processing systems, load balancing plays an important role in maximizing system throughput. When queries can leverage cached intermediate results, improving the cache hit ratio becomes as important as load balancing in query scheduling, especially when dealing with computationally expensive queries. The scheduling policies must be designed to take into consideration the dynamic contents of the distributed caching infrastructure. In this paper, we propose and discuss several distributed query scheduling policies that directly consider the available cache contents by employing distributed multidimensional indexing structures and an exponential moving average approach to predicting cache contents. These approaches are shown to produce better query plans and faster query response times than traditional scheduling policies that do not predict dynamic contents in distributed caches. We experimentally demonstrate the utility of the scheduling policies using MQO, which is a distributed, Grid-enabled, multiple query processing middleware system we developed to optimize query processing for data analysis and visualization applications.     

HoliAdapt——数据流中一种适应性查询处理策略

针对数据流上连续查询处理的特征,我们从选择率和执行时间的角度出发,考虑内存使用量和输出延迟适应性因素,提出一种适应性的查询处理策略—HoliAdapt。该策略基于查询窗口动态地收集统计信息,利用数学方法不断地优化查询计划,通过核心调度方法,对操作符进行适应性的调度,有效地减少时间延迟和内存使用量,提高系统查询的效率。     

High-throughput query scheduling with spatial clustering based on distributed exponential moving average

In distributed scientific query processing systems, leveraging distributed cached data is becoming more important. In such systems, a front-end query scheduler distributes queries among many application servers rather than processing queries in a few high-performance workstations. Although many query scheduling policies exist such as round-robin and load-monitoring, they are not sophisticated enough to exploit cached results as well as balance the workload. Efforts were made to improve the query processing performance using statistical methods such as exponential moving average. However, existing methods have limitations for certain query patterns: queries with hotspots, or dynamic query distributions. In this paper, we propose novel query scheduling policies that take into account both the contents of distributed caching infrastructure and the load balance among the servers. Our experiments show that the proposed query scheduling policies outperform existing policies by producing better query plans in terms of load balance and cache-hit ratio.     

Symmetrical hopping: A scalable scheduling algorithm for irregular problems

A run-time support is necessary for parallel computations with irregular and dynamic structures. One important component in the support system is the run-time scheduler which balances the working load in the system. We present a new algorithm, Symmetrical Hopping, for dynamic scheduling of ultra-lightweight processes. It is a dynamic, distributed, adaptive and scalable scheduling algorithm. This algorithm is described and compared to four other algorithms that have been proposed in this context, namely the randomized allocation, the sender-initiated scheduling, the receiver-initiated scheduling, and the gradient model. The performance of these algorithms on Intel Touchstone Delta is presented. The experimental results show that the Symmetrical Hopping algorithm achieves much better performance due to its adaptiveness.     

Multiclass query scheduling in real-time database systems

In recent years, a demand for real-time systems that can manipulate large amounts of shared data has led to the emergence of real-time database systems (RTDBS) as a research area. This paper focuses on the problem of scheduling queries in RTDBSs. We introduce and evaluate a new algorithm called Priority Adaptation Query Resource Scheduling (PAQRS) for handling both single class and multiclass query workloads. The performance objective of the algorithm is to minimize the number of missed deadlines, while at the same time ensuring that any deadline misses are scattered across the different classes according to an administratively-defined miss distribution. This objective is achieved by dynamically adapting the system's admission, memory allocation, and priority assignment policies according to its current resource configuration and workload characteristics. A series of experiments confirms that PAQRS is very effective for real-time query scheduling     

CubiST++: Evaluating Ad-Hoc CUBE Queries Using Statistics Trees

We report on a new, efficient encoding for the data cube, which results in a drastic speed-up of OLAP queries that aggregate along any combination of dimensions over numerical and categorical attributes. We are focusing on a class of queries called cube queries, which return aggregated values rather than sets of tuples. Our approach, termed CubiST⁺⁺ (Cubing with Statistics Trees Plus Families), represents a drastic departure from existing relational (ROLAP) and multi-dimensional (MOLAP) approaches in that it does not use the view lattice to compute and materialize new views from existing views in some heuristic fashion. Instead, CubiST⁺⁺ encodes all possible aggregate views in the leaves of a new data structure called statistics tree (ST) during a one-time scan of the detailed data. In order to optimize the queries involving constraints on hierarchy levels of the underlying dimensions, we select andmaterialize a family of candidate trees, which represent superviews over the different hierarchical levels of the dimensions. Given a query, our query evaluation algorithm selects the smallest tree in the family, which can provide the answer. Extensive evaluations of our prototype implementation have demonstrated its superior run-time performance and scalability when compared with existing MOLAP and ROLAP systems.     

A simulation test-bed for mobile adaptive architectures

Existing mobile systems are typically highly constrained with regards to their run-time resources: CPU, memory, communication bandwidth, screen real-estate, battery, and so forth. In current mobile systems, resource allocation decisions are almost always fixed at the time of system creation. However, this situation is arguably changing as mobile systems are becoming more powerful and as the demands being placed upon them are also increasing dramatically. For this reason, such systems need effective methods to manage and control their resources at run-time, particularly in the face of changing environmental conditions and user needs. This paper presents a simulation test-bed for experimenting with architectural design decisions such as communication and negotiation strategies among components, scheduling algorithms, and usability considerations. One significant area that we have begun to experiment with is the use of user-defined “utility” as a means of making dynamic resource allocation decisions. We will discuss the use of utility as a guide for scheduling, describe the test-bed, and present some examples of the results that we have derived, comparing utility-based scheduling with traditional scheduling methods.     

数据流处理中确定性QoS的保证方法

与以往尽最大努力的查询服务提供方式不同,讨论了数据流处理中确定性QoS的保证问题以网络演算为理论基础,提出了一种数据流处理中的QoS建模和QoS保证方法.系统运行前验证所有查询在满足各自的QoS前提下的可调度性.在运行时为通过QoS可调度性验证的每个查询分配代表其QoS需求的服务曲线,从而保证各查询期望的QoS.为了提高查询处理效率,还讨论了保证QoS的批调度和查询共享.实验结果表明,该QoS保证方法能够有效地为数据流上的连续查询提供确定性的QoS保证.     

Communication cost effective scheduling policies of nonclairvoyant jobs with load balancing in a grid

Effective load distribution is of great importance at grids, which are complex heterogeneous distributed systems. In this paper we study site allocation scheduling of nonclairvoyant jobs in a 2-level heterogeneous grid architecture. Three scheduling policies at grid level which utilize site load information are examined. The aim is the reduction of site load information traffic, while at the same time mean response time of jobs and fairness in utilization between the heterogeneous sites are of great interest. A simulation model is used to evaluate performance under various conditions. Simulation results show that considerable decrement in site load information traffic and utilization fairness can be achieved at the expense of a slight increase in response time.     

Synchronization and communication costs of loop partitioning onshared-memory multiprocessor systems

The author presents strategies for static loop decomposition and scheduling as well as computer-assisted run-time scheduling that take into account, in addition to the cost of performing operations, the overhead costs associated with a decomposition and schedule. An algorithm for static decomposition of multidimensional loops based on the operation execution costs, communication costs, and synchronization costs is discussed. Synchronization instructions are introduced to ensure correct program execution following program decomposition. An algorithm for determining the explicit synchronization instruction that should be introduced to ensure correct execution of a program with arbitrarily nested loops is presented. Techniques for reducing run-time scheduling and communication and synchronization costs due to self-scheduling of multidimensional loops are also presented. Experiments performed on the Encore multiprocessor system demonstrate that the techniques developed can reduce overhead costs     

Volcano-an extensible and parallel query evaluation system

To investigate the interactions of extensibility and parallelism in database query processing, we have developed a new dataflow query execution system called Volcano. The Volcano effort provides a rich environment for research and education in database systems design, heuristics for query optimization, parallel query execution, and resource allocation. Volcano uses a standard interface between algebra operators, allowing easy addition of new operators and operator implementations. Operations on individual items, e.g., predicates, are imported into the query processing operators using support functions. The semantics of support functions is not prescribed; any data type including complex objects and any operation can be realized. Thus, Volcano is extensible with new operators, algorithms, data types, and type-specific methods. Volcano includes two novel meta-operators. The choose-plan meta-operator supports dynamic query evaluation plans that allow delaying selected optimization decisions until run-time, e.g., for embedded queries with free variables. The exchange meta-operator supports intra-operator parallelism on partitioned datasets and both vertical and horizontal inter-operator parallelism, translating between demand-driven dataflow within processes and data-driven dataflow between processes. All operators, with the exception of the exchange operator, have been designed and implemented in a single-process environment, and parallelized using the exchange operator. Even operators not yet designed can be parallelized using this new operator if they use and provide the interator interface. Thus, the issues of data manipulation and parallelism have become orthogonal, making Volcano the first implemented query execution engine that effectively combines extensibility and parallelism     

Compile-time techniques for improving scalar access performance inparallel memories

Compile-time techniques for storage allocation of scalar values into memory modules that limit run-time memory-access conflicts are presented. The allocation approach is applicable to those operands in instructions that can be predicted at compile-time, where an instruction is composed of the multiple operations and corresponding operands that execute in parallel. Algorithms to schedule data transfers among memory modules to avoid conflicts that cannot be eliminated by the distribution of values alone are developed. The techniques have been implemented as part of a compiler for a reconfigurable long instruction word architecture. Results of experiments are presented demonstrating that a very high percentage of memory access conflicts can be avoided by scheduling a very low number of data transfers     

Security enforcement aware software development

In the domain of security policy enforcement, the concerns of application developers are almost completely ignored. As a consequence, it is hard to develop useful and reliable applications that will function properly under a variety of policies. This paper addresses this issue for application security policies specified as security automata, and enforced through run-time monitoring. Our solution consists of three elements: the definition of an abstract interface to the policy that is being enforced, a sound construct to query that policy, and a static verification algorithm that guarantees absence of security policy violations in critical blocks of code.     

A Probe-Based Technique to Optimize Join Queries in Distributed Internet Databases

An adaptive probe-based optimization technique is developed and demonstrated in the context of an Internet-based distributed database environment. More and more common are database systems which are distributed across servers communicating via the Internet where a query at a given site might require data from remote sites. Optimizing the response time of such queries is a challenging task due to the unpredictability of server performance and network traffic at the time of data shipment; this may result in the selection of an expensive query plan using a static query optimizer. We constructed an experimental setup consisting of two servers running the same database management system connected via the Internet. Concentrating on join queries, we demonstrate how a static query optimizer might choose an expensive plan by mistake. This is due to the lack of a priori knowledge of the run-time environment, inaccurate statistical assumptions in size estimation, and neglecting the cost of remote method invocation. These shortcomings are addressed collectively by proposing a probing mechanism. An implementation of our run-time optimization technique for join queries was constructed in the Java language and incorporated into an experimental setup. The results demonstrate the superiority of our probe-based optimization over a static optimization. Received 6 February 1999 / Revised 15 February 2000 / Accepted 10 May 2000     

Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time

The results of data cube will occupy huge amount of disk space when the base table is of a large number of attributes. A new type of data cube, compact data cube like condensed cube and quotient cube, was proposed to solve the problem. It compresses data cube dramatically. However, its query cost is so high that it cannot be used in most applications. This paper introduces the semi-closed cube to reduce the size of data cube and achieve almost the same query response time as the data cube does. Semi-closed cube is a generalization of condensed cube and quotient cube and is constructed from a quotient cube. When the query cost of quotient cube is higher than a given threshold, semi-closed cube selects some views and picks a fellow for each of them. All the tuples of those views are materialized except those closed by their fellows. To find a tuple of those views, users only need to scan the view and its fellow. Thus, their query performance is improved. Experiments were conducted using a real-world data set. The results show that semi-closed cube is an effective approach of data cube.     

Multi-armed bandits with switching penalties

The multi-armed bandit problem with switching penalties (switching cost and switching delays) is investigated. It is shown that under an optimal policy, decisions about the processor allocation need to be made only at stopping times that achieve an appropriate index, the well-known “Gittins index” or a “switching index” that is defined for switching cost and switching delays. An algorithm for the computation of the “switching index” is presented. Furthermore, sufficient conditions for optimality of allocation strategies, based on limited look-ahead techniques, are established. These conditions together with the above-mentioned feature of optimal scheduling policies simplify the search for an optimal allocation policy. For a special class of multi-armed bandits (scheduling of parallel queues with switching penalties and no arrivals), it is shown that the aforementioned property of optimal policies is sufficient to determine an optimal allocation strategy. In general, the determination of optimal allocation policies remains a difficult and challenging task     

A Lazy Scheduling Scheme for Hypercube Computers

Processor allocation and job scheduling are two complementary techniques for improving the performance of multiprocessors. It has been observed that all the hypercube allocation policies with the FCFS scheduling provide only incremental performance improvement. A greater impact on the performance can be obtained by efficient job scheduling. This paper presents an effort in that direction by introducing a new scheduling algorithm called lazy scheduling for hypercubes, The motivation of this scheme is to eliminate the limitations of the FCFS scheduling. This is done by maintaining separate queues for different job sizes and delaying the allocation of a job if any other job(s) of the same dimension is(are) running in the system. Processor allocation is done using the buddy strategy. The scheduling and allocation complexity is O(n) for an n-cube. Simulation studies show that the performance is dramatically enhanced by using the lazy scheduling scheme as compared to the FCFS scheduling. Comparison with a recently proposed scheme called scan indicates that the lazy scheme performs better than the scan scheduling under a wide range of workloads.     

Embedded simulation on a multiprocessor job scheduling system with inspection

This paper first develops architecture for a multiprocessor job scheduling system with an embedded simulation technique. The architecture provides a shell for applications that are characterized by two scheduling policies, a heuristic algorithm policy and a First-In-First-Out (FIFO) policy. These policies are implemented in the simulation model by using the embedded technique. The paper evaluates these two policies using the queue length, waiting time and flow time as the criteria to compare the performance of these two scheduling policies. Next we designed two simulation situations using two different real world applications. The purpose is to examine the performances of multiprocessor systems with and without inspection operations and two different scheduling policies. The two applications, berth allocation for the container terminal operations and production scheduling arrangement in an Original Equipment Manufacturer (OEM) power supply factory, are studied. The final results show that a proper scheduling policy will perform better than the traditional FIFO approach for a multiprocessor system. Our study also provides guidelines on balancing a system with the addition of a final inspection activity.