Kacsuk Analysis and Improvement of the Variable Binding Scheme in LOGFLOW.pdf

Analysis and Improvement of the Variable Binding Scheme in LOGFLOW* Zsolt Németh Péter Kacsuk KFKI Research Institute for Measurement and Computing Techniques H-1525 Budapest, P.O. Box 49. Phone: (36 1) 395 9220, Fax: (36 1) 395 9027 {zsnemeth, kacsuk}@sunserv.kfki.hu Abstract The handling of variables is a crucial issue in designing a parallel Prolog system. The so called closed binding environment is an excellent candidate for a binding scheme in a distributed system, however, it has several weaknesses when the computation is not migrating. In this paper the closed binding method is analysed, a possible modification is introduced and the implementation and performance measurement of the hybrid binding scheme in LOGFLOW is described. Keywords: distributed Prolog implementation, binding schemes, closed binding environment, performance evaluation 1 Introduction The central question at implementing an OR-parallel Prolog system is how the multiple bindings can be handled consistently in such a way that the resulting binding scheme accomplishes most of these issues: variable access is in constant time, task switching is in constant time, task creation is in constant time. In [GuJa90] it was shown that all the three conditions can not be satisfied. Additionally, low memory consumption must be taken into consideration at designing a binding scheme. There are a number of techniques for treating multiple bindings [KacsWise92][ChassCod94]. In common, they intended to assure a binding environment so that each worker (process) could handle the shared data as if the worker was traversing the search graph alone. All these techniques have a co