{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19356"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19356","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Machine-independent parallel execution of speculative computations","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Saletore, Vikram A."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Kale, Laxmikant V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"10000-01-01","date_published":"10000-01-01","updated_at":"2026-07-22T22:25:12Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Saletore, Vikram A."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9136721","(UMI)AAI9136721"],"render_values":[{"text":"AAI9136721","href":null,"code":true},{"text":"(UMI)AAI9136721","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19356","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kale, Laxmikant V."]},{"key":"dc:creator","label":"Author","values":["Saletore, Vikram A."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["10000-01-01","1991","2011-05-07T12:04:59Z"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical","Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Saletore, Vikram A."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9136721","(UMI)AAI9136721","http://hdl.handle.net/2142/19356"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T12:04:59Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9136721.pdf: 8020549 bytes, checksum: 3ad79e0bfdcc91d0764dbf132de8e2e5 (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:36:24Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:14:40-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Machine-independent parallel execution of speculative computations"]}]}],"canonical_facts":{"dc:contributor":["Kale, Laxmikant V."],"dc:creator":["Saletore, Vikram A."],"dc:date":["10000-01-01","1991","2011-05-07T12:04:59Z"],"dc:description":["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.","Made available in DSpace on 2011-05-07T12:04:59Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9136721.pdf: 8020549 bytes, checksum: 3ad79e0bfdcc91d0764dbf132de8e2e5 (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:36:24Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:14:40-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9136721","(UMI)AAI9136721","http://hdl.handle.net/2142/19356"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Saletore, Vikram A."],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Machine-independent parallel execution of speculative computations"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:12Z"}