A proposal for a flexible scheduling and memory management scheme for non-deterministic, andparallel execution of logic programs

Shen, Kish and Hermenegildo, Manuel V. (1994). A proposal for a flexible scheduling and memory management scheme for non-deterministic, andparallel execution of logic programs. Monografía (Technical Report). Facultad de Informática (UPM), Madrid, Spain.

Description

Title: A proposal for a flexible scheduling and memory management scheme for non-deterministic, andparallel execution of logic programs
Author/s:
  • Shen, Kish
  • Hermenegildo, Manuel V.
Item Type: Monograph (Technical Report)
Date: June 1994
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

Abstract

In this paper, we examine the issue of memory management in the parallel execution of logic programs. We concentrate on non-deterministic and-parallel schemes which we believe present a relatively general set of problems to be solved, including most of those encountered in the memory management of or-parallel systems. We present a distributed stack memory management model which allows flexible scheduling of goals. Previously proposed models (based on the "Marker model") are lacking in that they impose restrictions on the selection of goals to be executed or they may require consume a large amount of virtual memory. This paper first presents results which imply that the above mentioned shortcomings can have significant performance impacts. An extension of the Marker Model is then proposed which allows flexible scheduling of goals while keeping (virtual) memory consumption down. Measurements are presented which show the advantage of this solution. Methods for handling forward and backward execution, cut and roll back are discussed in the context of the proposed scheme. In addition, the paper shows how the same mechanism for flexible scheduling can be applied to allow the efficient handling of the very general form of suspension that can occur in systems which combine several types of and-parallelism and more sophisticated methods of executing logic programs. We believe that the results are applicable to many and- and or-parallel systems.

More information

Item ID: 15211
DC Identifier: http://oa.upm.es/15211/
OAI Identifier: oai:oa.upm.es:15211
Official URL: ftp://clip.dia.fi.upm.es/pub/papers/PARFORCE/first_review/DIRECTORY.html
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 08 May 2013 07:27
Last Modified: 21 Apr 2016 15:12
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM