Specialization-based parallel Processing without Memo-trees

Authors: Hidemi Ogasawara, Kiyoshi Akama, Hiroshi Mabuchi

Abstract:

The purpose of this paper is to propose a framework for constructing correct parallel processing programs based on Equivalent Transformation Framework (ETF). ETF regards computation as In the framework, a problem-s domain knowledge and a query are described in definite clauses, and computation is regarded as transformation of the definite clauses. Its meaning is defined by a model of the set of definite clauses, and the transformation rules generated must preserve meaning. We have proposed a parallel processing method based on “specialization", a part of operation in the transformations, which resembles substitution in logic programming. The method requires “Memo-tree", a history of specialization to maintain correctness. In this paper we proposes the new method for the specialization-base parallel processing without Memo-tree.

Keywords: Parallel processing, Program correctness, Equivalent transformation, Specializer generation rule

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072375

References:

[1] K. Akama, E. Nantajeewarawat, and H. Ogasawara, "Generation of correct parallel programs based on specializer generation transformations," in Proceedings of the 7th international conference on intelligent technologies, 2006.
[2] H. Ogasawara, K. Akama, and H. Mabuchi, "Parallel processing framework based on distributed computation of specialization," International Journal of Innovative Computing, Information and Control, vol. 6, no. 5, pp. 2371-2381, 2010.
[3] K. Akama and E. Nantajeewarawat, "Formalization of the equivalent transformation computation models," Journal of Advanced Computational Intelligence and Intelligent Informatics, vol. 10, no. 3, pp. 245-259, 2006.
[4] Conceptis-Limited. (2005) Pic-a-pix help.
[Online]. Available: http://www.conceptispuzzles.com/online/pap/help.htm
[5] Nikoli. (2010) Sudoku outline.
[Online]. Available: http://www.nikoli.co.jp/en/puzzles/sudoku/index text.htm
[6] W.-J. van Hoeve and I. Katriel, "Global constraints," in Handbook of Constraint Programming, F. Rossi, P. van Beek, and T. Walsh, Eds. ELSEVIER, 2006, ch. 6, pp. 169-208.
[7] J. C. de Kergommeaux, "Parallel logic programming systems," ACM Computing Surveys, vol. 26, no. 3, 1994.
[8] G. Gupta, E. Pontelli, K. A. M. Ali, M. Carlsson, and M. V. Hermenegildo, "Parallel execution of prolog programs: a survey," Programming Languages and Systems, vol. 23, no. 4, pp. 472-602, 2001.
[9] B. Ramkumar and L. V. Kal'e, "Machine independent and and or parallel execution of logic programs: Part i-the binding environment," IEEE Trans. Parallel Distrib. Syst., vol. 5, no. 2, pp. 170-180, 1994.