Constructs and evaluation strategies for intelligent speculative parallelism - armageddon revisited


Autoria(s): Guzman, Adolfo; Hermenegildo, Manuel V.
Data(s)

01/02/1988

Resumo

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.

Formato

application/pdf

Identificador

http://oa.upm.es/14499/

Idioma(s)

eng

Publicador

Facultad de Informática (UPM)

Relação

http://oa.upm.es/14499/1/HERME_ARC_1988-1.pdf

http://dl.acm.org/citation.cfm?id=323126

Direitos

http://creativecommons.org/licenses/by-nc-nd/3.0/es/

info:eu-repo/semantics/openAccess

Fonte

CSC '88 Proceedings of the 1988 ACM sixteenth annual conference on Computer science | The 1988 ACM sixteenth annual conference on Computer science | February 23-25, 1988 | Atlanta, Georgia, USA

Palavras-Chave #Informática
Tipo

info:eu-repo/semantics/conferenceObject

Ponencia en Congreso o Jornada

PeerReviewed