Machine-independent parallel execution of speculative computations

Many problems in Artificial Intelligence involve traversing large search-spaces. Such problems typically have irregular structures that can be readily exploited for parallel execution. A class of such problems has multiple solutions where any one solution is acceptable. Parallel execution of such computations leads to speculative computations. We investigate schemes for parallel execution of such speculative computations to obtain consistent and good linear speedups to a first solution that increase monotonically with the addition of processors. The memory usage of these search techniques does not increase proportionately with the increase in the number of processors. A parallel execution scheme for speculative computations in pure state-space search that associates bit-vector priorities with computations is described. The bit-vector priorities ensure that the resources are focused towards the first solution. A technique called delayed-release is developed which ensures that the memory usage of parallel execution schemes is reduced and does not increase with the addition of processors.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering

Grantor

University of Illinois at Urbana-Champaign

Date dc:date

10000-01-01

Author dc:creator

• Saletore, Vikram A.

Contributors dc:contributor

• Kale, Laxmikant V.

• Engineering, Electronics and Electrical
• Computer Science

Statement dc:rights

• Copyright 1991 Saletore, Vikram A.

Language dc:language

eng

Identifier

AAI9136721
(UMI)AAI9136721

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/19356