摘要: This paper presents and develops a generalized concept of Non-Strict Independent And Parallelism (NSIAP). NSIAP extends the applicability And- (IAP) by enlarging class goals which are eligible for parallel execution. At same time it maintains IAP's ability to run non-deterministic in preserve computational complexity expected execution program programmer. First, framework is defined some fundamental correctness results, sense equivalence solutions with sequential model, discussed this framework. The issue efficiency then considered. Two new definitions NSI given cases pure impure respectively results provided programs parallelized under these include treatment case goal failure: not only reduction guaranteed (modulo run-time overheads) absence failure but also shown that worst of failure no speed-down will occur. In addition applying NSI, carry over complete previous context IAP did deal failure. Finally, practical examples application parallelization set presented performance showing advantage using given.
参考文章(15)
Jung-Herng Chang, Doug DeGroot, Alvin M. Despain, AND-Parallelism of Logic Programs Based on a Static Data Dependency Analysis. COMPCON. pp. 218- 226 ,(1985)
Annika Wærn, William H. Winsborough, Transparent And-Parallelism in the Presence of Shared Free Variables. international conference on lightning protection. pp. 749- 764 ,(1988)
Philippe Robert, Jean-Claude Syre, Harald Westphal, Jacques Chassin de Kergommeaux, The PEPSys Model: Combining Backtracking, AND- and OR-Parallelism. SLP. pp. 436- 448 ,(1987)
Doug DeGroot, Restricted AND-Parallelism. Future Generation Computer Systems. pp. 471- 478 ,(1984)
Shyh-Chang Su, David Y. Y. Yun, Prasenjit Biswas, A Scalable Abstract Machine Model to Support Limited-OR (LOR) / Restricted-AND Parallelism (RAP) in Logic Programs. international conference on lightning protection. pp. 1160- 1179 ,(1988)
Yow-Jian Lin, A parallel implementation of logic programs University of Texas at Austin. ,(1988)
Saumya K. Debray, Manuel V. Hermenegildo, Richard Warren, On the practicality of global flow analysis of logic programs international conference on lightning protection. pp. 684- 699 ,(1988)
David H. D. Warren, Or-parallel execution models of prolog TAPSOFT '87 Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 2: Advanced Seminar on Foundations of Innovative Software Development II and Colloquium on Functional and Logic Programming and Specifications (CFLP). pp. 243- 259 ,(1987) , 10.1007/BFB0014984
M. V. Hermenegildo, K. J. Greene, Prolog and its performance: exploiting independent and-parallelism international conference on lightning protection. pp. 253- 268 ,(1990)
M. V. Hermenegildo, R. I. Nasr, Efficient management of backtracking in AND-parallelism international conference on logic programming. pp. 40- 54 ,(1986) , 10.1007/3-540-16492-8_63