Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited

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

Descripción

Título: Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited
Autor/es:
  • Guzman, Adolfo
  • Hermenegildo, Manuel V.
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: The 1988 ACM sixteenth annual conference on Computer science
Fechas del Evento: February 23-25, 1988
Lugar del Evento: Atlanta, Georgia, USA
Título del Libro: CSC '88 Proceedings of the 1988 ACM sixteenth annual conference on Computer science
Fecha: Febrero 1988
ISBN: 0897912608
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (959kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 14499
Identificador DC: http://oa.upm.es/14499/
Identificador OAI: oai:oa.upm.es:14499
URL Oficial: http://dl.acm.org/citation.cfm?id=323126
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 15 Feb 2013 07:46
Ultima Modificación: 21 Abr 2016 14:12
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM