Machine-independent parallel execution of speculative computations
Saletore, Vikram A.
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19356
Description
Title
Machine-independent parallel execution of speculative computations
Author(s)
Saletore, Vikram A.
Issue Date
1991
Doctoral Committee Chair(s)
Kale, Laxmikant V.
Department of Study
Electrical and Computer Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Computer Science
Language
eng
Abstract
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.
A technique employing bit-vector priorities to reduce the time to the first solution in parallel execution of AND/OR speculative computations is presented. The scheme is further developed to obtain consistent and linear speedups to the first solution in these computations. We also investigate the problem of queue contention in large shared-memory machines. A technique to address this has been developed using dense graphs for processor-memory interconnection that has better scalability and performance. Priority balancing strategies in conjunction with load balancing strategies are also developed for large shared-memory and nonshared-memory multiprocessors to ensure that the processing effort is focused towards the first solution.
A machine independent parallel software package called SearchPack has been developed which embodies these ideas. SearchPack can be used with the Chare-Kernel II, the run time support system for machine independent parallel programming to run search algorithms across multiprocessors without change. Performance studies have been conducted on several shared-memory and nonshared-memory machines such as the Sequent Symmetry, Alliant FX/8, Encore Multimax, and Intel iPSC/2 Hypercube.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
