{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/34100"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/34100","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Synchronization issues of the parallel A Star Search","abstract":"An experimental study was carried out on the performance of synchronous and asynchronous implementations of the A* Search on a multiprocessor network. Master-Slave parallelism was used to distribute the Search among the 8 processor nodes of a transputer network. The test programs were run on 4 different types of maps. Measurements were taken in the form of percentages of time spent in computation and communication in each cycle of the search as an artificial delay in the computation phase was increased. The results from the map tests showed that the asynchronous implementation spent a larger percentage of each cycle performing calculations rather than communicating or waiting for communications as the artificial delay was increased. This means that the efficiency of the asynchronous approach increases more rapidly than the efficiency of the synchronous approach as the computational complexity of a parallel program is increased. This was found to be true for all artificial delays on all test maps for the Master-Slave A* Search. The results might vary with different implementations and search methodologies.","abstract_html":"An experimental study was carried out on the performance of synchronous and asynchronous implementations of the A* Search on a multiprocessor network. Master-Slave parallelism was used to distribute the Search among the 8 processor nodes of a transputer network. The test programs were run on 4 different types of maps. Measurements were taken in the form of percentages of time spent in computation and communication in each cycle of the search as an artificial delay in the computation phase was increased. The results from the map tests showed that the asynchronous implementation spent a larger percentage of each cycle performing calculations rather than communicating or waiting for communications as the artificial delay was increased. This means that the efficiency of the asynchronous approach increases more rapidly than the efficiency of the synchronous approach as the computational complexity of a parallel program is increased. This was found to be true for all artificial delays on all test maps for the Master-Slave A* Search. The results might vary with different implementations and search methodologies.","abstract_has_math":false,"creators":["Daly, Daniel Cameron"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Dimitri P. Bertsekas and Ed. Leung."],"committee_chairs":[],"committee_members":[],"year":1994,"date_issued":"1994","date_published":"1994","updated_at":"2026-07-22T22:21:55Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/34100","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Dimitri P. Bertsekas and Ed. Leung."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Daly, Daniel Cameron"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-09-28T15:02:38Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-09-28T15:02:38Z"]},{"key":"dc:date.issued","label":"Date","values":["1994"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/34100"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (B.S. and M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 1994.","Includes bibliographical references (leaf 29)."]},{"key":"dc:description.abstract","label":"Abstract","values":["An experimental study was carried out on the performance of synchronous and asynchronous implementations of the A* Search on a multiprocessor network. Master-Slave parallelism was used to distribute the Search among the 8 processor nodes of a transputer network. The test programs were run on 4 different types of maps. Measurements were taken in the form of percentages of time spent in computation and communication in each cycle of the search as an artificial delay in the computation phase was increased. The results from the map tests showed that the asynchronous implementation spent a larger percentage of each cycle performing calculations rather than communicating or waiting for communications as the artificial delay was increased. This means that the efficiency of the asynchronous approach increases more rapidly than the efficiency of the synchronous approach as the computational complexity of a parallel program is increased. This was found to be true for all artificial delays on all test maps for the Master-Slave A* Search. The results might vary with different implementations and search methodologies."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["B.S.and M.S."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Synchronization issues of the parallel A Star Search"]}]}],"canonical_facts":{"dc:contributor.advisor":["Dimitri P. Bertsekas and Ed. Leung."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Daly, Daniel Cameron"],"dc:date.accessioned":["2006-09-28T15:02:38Z"],"dc:date.available":["2006-09-28T15:02:38Z"],"dc:date.issued":["1994"],"dc:description":["Thesis (B.S. and M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, February 1994.","Includes bibliographical references (leaf 29)."],"dc:description.abstract":["An experimental study was carried out on the performance of synchronous and asynchronous implementations of the A* Search on a multiprocessor network. Master-Slave parallelism was used to distribute the Search among the 8 processor nodes of a transputer network. The test programs were run on 4 different types of maps. Measurements were taken in the form of percentages of time spent in computation and communication in each cycle of the search as an artificial delay in the computation phase was increased. The results from the map tests showed that the asynchronous implementation spent a larger percentage of each cycle performing calculations rather than communicating or waiting for communications as the artificial delay was increased. This means that the efficiency of the asynchronous approach increases more rapidly than the efficiency of the synchronous approach as the computational complexity of a parallel program is increased. This was found to be true for all artificial delays on all test maps for the Master-Slave A* Search. The results might vary with different implementations and search methodologies."],"dc:description.degree":["B.S.and M.S."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/34100"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Synchronization issues of the parallel A Star Search"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:55Z"}