Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited

Guzman, Adolfo and Hermenegildo, Manuel V. (1988). Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited. In: "The 1988 ACM sixteenth annual conference on Computer science", February 23-25, 1988, Atlanta, Georgia, USA. ISBN 0897912608.

Description

Title: Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited
Author/s:
  • Guzman, Adolfo
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: The 1988 ACM sixteenth annual conference on Computer science
Event Dates: February 23-25, 1988
Event Location: Atlanta, Georgia, USA
Title of Book: CSC '88 Proceedings of the 1988 ACM sixteenth annual conference on Computer science
Date: February 1988
ISBN: 0897912608
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 (959kB) | Preview

Abstract

This report addresses speculative parallelism (the assignment of spare processing resources to tasks which are not known to be strictly required for the successful completion of a computation) at the user and application level. At this level, the execution of a program is seen as a (dynamic) tree —a graph, in general. A solution for a problem is a traversal of this graph from the initial state to a node known to be the answer. Speculative parallelism then represents the assignment of resources to múltiple branches of this graph even if they are not positively known to be on the path to a solution. In highly non-deterministic programs the branching factor can be very high and a naive assignment will very soon use up all the resources. This report presents work assignment strategies other than the usual depth-first and breadth-first. Instead, best-first strategies are used. Since their definition is application-dependent, the application language contains primitives that allow the user (or application programmer) to a) indícate when intelligent OR-parallelism should be used; b) provide the functions that define "best," and c) indícate when to use them. An abstract architecture enables those primitives to perform the search in a "speculative" way, using several processors, synchronizing them, killing the siblings of the path leading to the answer, etc. The user is freed from worrying about these interactions. Several search strategies are proposed and their implementation issues are addressed. "Armageddon," a global pruning method, is introduced, together with both a software and a hardware implementation for it. The concepts exposed are applicable to áreas of Artificial Intelligence such as extensive expert systems, planning, game playing, and in general to large search problems. The proposed strategies, although showing promise, have not been evaluated by simulation or experimentation.

More information

Item ID: 14499
DC Identifier: http://oa.upm.es/14499/
OAI Identifier: oai:oa.upm.es:14499
Official URL: http://dl.acm.org/citation.cfm?id=323126
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 15 Feb 2013 07:46
Last Modified: 21 Apr 2016 14: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