We introduce a class of novel multiprocessor scheduling problems that arise in the optimization of SQL queries for parallel machines. These consist of scheduling a tree of interdependent communicating operators while exploiting both inter-operator and intr
Scheduling Problems in Parallel Query Optimization Department of Computer Science Stanford University Stanford, CA 94305-2140
Chandra Chekuri
Department of Computer Science Stanford University Stanford, CA 94305-2140 and Hewlett-Packard Laboratories
Waqar Hasany
Department of Computer Science Stanford University Stanford, CA 94305-2140
Rajeev Motwaniz
Abstract
We introduce a class of novel multiprocessor scheduling problems that arise in the optimization of SQL queries for parallel machines. These consist of scheduling a tree of interdependent communicating operators while exploiting both inter-operator and intra-operator parallelism. We develop algorithms for the speci c problem of scheduling a Pipelined Operator Tree in which all operators run in parallel using inter-operator parallelism. Weights associated with nodes and edges represent respectively the cost of operators and communication. Communication cost is incurred only if adjacent operators are assigned di erent processors. The optimization problem is to assign operators to processors so as to minimize the maximum processor load. We develop two approximation algorithms for this NP-hard problem. The faster algorithm has a performance ratio of 3.56 while the slower algorithm has a ratio of 2.87.
1 Introduction
Exploiting parallel execution DG92, Val93] to speed up database queries presents a parallelism-communication trade-o . While work is divided among processors, the concomitant communication increases total work itself Gra88, PMC+ 90]. We can represent the task to be scheduled as a weighted operator tree Hon92, Sch90, HM94a] in which nodes represent atomic units of execution (operators) and directed edges represent the ow of data as well as timing constraints between operators. E-mail: . Supported by an OTL grant and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. y E-mail: z E-mail: . Supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, an OTL grant, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. chekuri@cs.stanford.edu hasan@cs.stanford.edu rajeev@cs.stanford.edu
Weights associated with nodes and edges represent respectively the cost of operators and communication between them. Scheduling a weighted operator tree on a parallel machine poses a class of novel multi-processor scheduling problems that di er from the classical GLLK79] in several ways. Firstly, edges represent two kinds of timing constraints| parallel and precedence. Secondly, since data is transmitted in long streams, the important aspect of communication is the CPU overhead of sending/receiving messages and not the delay for signal propagation (see PU87, PY88] for models of communication as delay). Thirdly, the set oriented nature of queries has led to intra-operator parallelism (relations are h
orizontally partitioned and a clone of the operator applied to each partition) in addition to inter-operator parallelism DG92]. Finally, operators may have distinct weights since parallel database systems exploit coarsegrained parallelism. We introduce several problems and focus on the speci c problem of scheduling a Pipelined Operator Tree (POT scheduling). All edges in such a tree represent parallel constraints, i.e., all operators run in parallel. A schedule assigns operators to processors. Since edge weights represent the cost of remote communication, this cost is saved if adjacent operators share a processor. Given a schedule, the load on a processor is the sum of the weights of nodes assigned to it plus the weights of all edges that connect nodes on the processor to nodes on other processors. The response time (makespan) of a schedule is the maximum processor load. The optimization problem is to nd a schedule with minimal response time. POT scheduling is NP-hard since the special case in which all communication costs are zero is classical multiprocessor scheduling GJ79]. We will measure the quality of algorithms by their performance ratio which is the ratio of the response time of the generated schedule to that of the optimal. Since the problem is intractable, our goal is to develop approximation algorithms that run in polynomial time and guarantee small bounds on the performance ratio Mot92].
ICC Color Management and CIECAM02 Ingeborg Tastl, Miheer Bhachech, Nathan Moroney and Jack Holm Hewlett-Packard Laboratories Palo Alto, CA/USA Abstract The...
Kohl University of California, Berkeley and Digital Equipment Corporation Carl Staelin Hewlett-Packard Laboratories Michael Stonebraker University of California, ...
Transactional Exactly-Once Svend Fr lund and Rachid Guerraoui Hewlett-Packard Laboratories, 1501 Page Mill Road, Palo Alto, CA 94304 July 14, 1999 Abstract...
Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks Sung-Ju Lee Internet & Mobile Systems Labs Hewlett-Packard Laboratories Palo Alto, ...
and Xiaodong Zhang3 1 2 3 Streaming Media Systems Group Hewlett-Packard Laboratories Palo Alto, CA 94304 Department of Computer Science George Mason Universi...
Division, University of California, Berkeley and International Computer Science Institute Berkeley, CA 94720 1 2 Hewlett-Packard Laboratories 1501 Page Mill Rd...
A Logic-Based Approach to Automated System Management Along Lin Hewlett-Packard Laboratories Filton Road, Stoke Gifford Bristol BS34 8QZ, U.K. Email: alin...
Scott Marovich and John Wilkes Computer Systems Laboratory Hewlett-Packard Laboratories, Palo Alto, CA HPL–95–86 July 1995 HP Laboratories Technical Report...
e Publ ion icat Force and impulse from an Aharonov-Bohm ux line Aharonov-Bohm force and impulse] BRIMS, Hewlett-Packard Laboratories, Filton Road, ...
Dave Cliff,a researcher at Hewlett-Packard Laboratories in Bristol,England,has been creating trading robots for seven years.In computer simulations he lets ...
热门文档