文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > and Hewlett-Packard Laboratories
侵权投诉

and Hewlett-Packard Laboratories

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].

第1页

你可能喜欢

热门文档

相关文档

  • Hewlett-Packard Laboratories

    ICC Color Management and CIECAM02 Ingeborg Tastl, Miheer Bhachech, Nathan Moroney and Jack Holm Hewlett-Packard Laboratories Palo Alto, CA/USA Abstract The...

  • Hewlett-Packard Laboratories

    Kohl University of California, Berkeley and Digital Equipment Corporation Carl Staelin Hewlett-Packard Laboratories Michael Stonebraker University of California, ...

  • Hewlett-Packard Laboratories,

    Transactional Exactly-Once Svend Fr lund and Rachid Guerraoui Hewlett-Packard Laboratories, 1501 Page Mill Road, Palo Alto, CA 94304 July 14, 1999 Abstract...

  • Hewlett-Packard Laboratories

    Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks Sung-Ju Lee Internet & Mobile Systems Labs Hewlett-Packard Laboratories Palo Alto, ...

  • Hewlett-Packard Laboratories

    and Xiaodong Zhang3 1 2 3 Streaming Media Systems Group Hewlett-Packard Laboratories Palo Alto, CA 94304 Department of Computer Science George Mason Universi...

  • Hewlett-Packard Laboratories

    Division, University of California, Berkeley and International Computer Science Institute Berkeley, CA 94720 1 2 Hewlett-Packard Laboratories 1501 Page Mill Rd...

  • Hewlett-Packard Laboratories

    A Logic-Based Approach to Automated System Management Along Lin Hewlett-Packard Laboratories Filton Road, Stoke Gifford Bristol BS34 8QZ, U.K. Email: alin...

  • Laboratories

    Scott Marovich and John Wilkes Computer Systems Laboratory Hewlett-Packard Laboratories, Palo Alto, CA HPL–95–86 July 1995 HP Laboratories Technical Report...

  • [Aharonov-Bohm force and impulse]

    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 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email