| TR#: | CS0516 |
| Class: | CS |
| Title: | Logic Programs and a New Approach to Parallelism |
| Authors: | Ouri Wolfson |
| CS0516.pdf | |
| Abstract: | We propose a method of parallelizing bottom-up-evaluation of logic programs. The method is distinguished by the fact that it is pure i.e., does not require interprocessor communication, or synchronization overhead The method cannot be used to parallelize every logic program, but we syntactically characterize several classes pf logic programs to which the method can be applied (e.g., the class of linear single rule programs). We also provide a characterization for a class of prograrns to which the parallelization method cannot be applied, and show that in general, determining applicability is undecidable. Then, we generalize the concepts beyond the proposed method, and lay the foundations for a theory of logic programs and parallelization. It demonstrates that the logic programs have an interesting hierarchical classstructure, with respect to pure parallelization. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1988/CS/CS0516), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1988
To the main CS technical reports page