A Hierarchical Approach to Parallel Multiquery Scheduling Export

@article{citeulike:1778734, abstract = {There has been a good deal of progress made recently toward the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper we devise and experimentally evaluate a number of scheduling algorithms designed to handle multiple parallel queries. (Scheduling in this context implies the determination of both processor allotments and temporal processor assignments to individual queries and query phases.) One of these algorithms performs the best in our experiments. This algorithm is hierarchical in nature: In the first phase, a good quality precedence-based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the first phase are used to create an overall schedule of the full set of queries. This component is based on previously published work on nonprecedence-based malleable scheduling. Even though the problem we are considering is NP-hard in the strong sense, the multiple query schedules generated by our hierarchical algorithm are seen experimentally to achieve high quality results.}, address = {Piscataway, NJ, USA}, author = {Wolf, Joel L. and Turek, John and Chen, Ming-Syan and Yu, Philip S.}, citeulike-article-id = {1778734}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=206335}, citeulike-linkout-1 = {http://dx.doi.org/10.1109/71.388035}, comment = {* Cons: They do not explicitly model memory, disk or other resource contention.}, doi = {10.1109/71.388035}, issn = {1045-9219}, journal = {IEEE Trans. Parallel Distrib. Syst.}, keywords = {3, binpacking, dbms, journal, np-hard, optimization, parallel, query-processing, sched}, month = {June}, number = {6}, pages = {578--590}, posted-at = {2007-10-17 08:54:17}, priority = {4}, publisher = {IEEE Press}, title = {A Hierarchical Approach to Parallel Multiquery Scheduling}, url = {http://dx.doi.org/10.1109/71.388035}, volume = {6}, year = {1995} }

TY - JOUR ID - citeulike:1778734 L3 - citeulike-article-id:1778734 N2 - There has been a good deal of progress made recently toward the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper we devise and experimentally evaluate a number of scheduling algorithms designed to handle multiple parallel queries. (Scheduling in this context implies the determination of both processor allotments and temporal processor assignments to individual queries and query phases.) One of these algorithms performs the best in our experiments. This algorithm is hierarchical in nature: In the first phase, a good quality precedence-based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the first phase are used to create an overall schedule of the full set of queries. This component is based on previously published work on nonprecedence-based malleable scheduling. Even though the problem we are considering is NP-hard in the strong sense, the multiple query schedules generated by our hierarchical algorithm are seen experimentally to achieve high quality results. IS - 6 JF - IEEE Trans. Parallel Distrib. Syst. SN - 1045-9219 AD - Piscataway, NJ, USA EP - 590 TI - A Hierarchical Approach to Parallel Multiquery Scheduling PB - IEEE Press VL - 6 SP - 578 KW - 3 KW - binpacking KW - dbms KW - journal KW - np-hard KW - optimization KW - parallel KW - query-processing KW - sched N1 - * Cons: They do not explicitly model memory, disk or other resource contention. AU - Wolf, Joel AU - Turek, John AU - Chen, Ming-Syan AU - Yu, Philip PY - 1995/06// UR - http://dx.doi.org/10.1109/71.388035 ER -