language: en

OPTIMAL PROCESSOR ASSIGNMENT FOR PARALLEL DATABASE DESIGN

SHAHRAM GHANDEHARIZADEH , ROBERT R. MEYER , GARY L. SCHULTZ AND JONATHAN YACKEL

Abstract. The computing time benefits of parallelism in database systems (achieved by using multiple processors to execute a query) must be weighed against communication, startup, and termination overhead costs that increase as a function of the number of processors used. We consider problems of minimizing overhead subject to allocating data among the processors according to specified loads. We present lower bounds for these combinatorial problems and demonstrate how processors may be optimally assigned for some problem classes.

1. Introduction. In highly-parallel database machines (e.g., Gamma [2], Bubba