Academic Commons

Reports

Why a Single Parallelization Strategy Is Not Enough in Knowledge Bases

Cohen, Simona Rabinovici; Wolfson, Ouri

We address the problem of parallelizing the evaluation of logic programs in data intensive applications. We argue that the appropriate parallelization strategy for logic-program evaluation depends on the program being evaluated. Therefore, this paper is concerned with the issues of program classification and parallelization strategies. We propose several parallelization strategies based on the concept of data reduction—the original logic program is evaluated by several processors working in parallel, each using only a subset of the database. The strategies differ on the evaluation cost, the overhead of communication and synchronization among processors, and the programs to which they are applicable. In particular, we start our study with pure parallelization, i.e., parallelization without overhead. An interesting class structure of logic programs is demonstrated, when considering amenability to pure parallelization. The relationship to the NC complexity class is demonstrated. Then we propose strategies that do incur an overhead, but are optimal in a sense that will be precisely defined. This paper makes the initial steps towards a theory of parallel logic programming.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-015-90
Published Here
March 8, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.