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 inter-dependent communicating operators while exploiting both inter-operator and intra-operator parallelism. We develop algorithms for the specific 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 different 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.
Original language | English (US) |
---|---|
Pages | 255-265 |
Number of pages | 11 |
DOIs | |
State | Published - 1995 |
Externally published | Yes |
Event | Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - San Jose, CA, USA Duration: May 22 1995 → May 25 1995 |
Other
Other | Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems |
---|---|
City | San Jose, CA, USA |
Period | 5/22/95 → 5/25/95 |
ASJC Scopus subject areas
- Software
- Information Systems
- Hardware and Architecture