{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72065"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72065","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs","abstract":"Parallel programs are significantly different from sequential programs in the sense that they can exhibit timing-dependent behaviour. The same program with the same input data can produce different results on different executions. This is unacceptable for a large number of programs. The main focus of this thesis is techniques to automatically detect such situations. Since nondeterminacy is intimately related to the ordering between operations executed by the program, the main problem studied is that of computing ordering between operations. The ordering is determined by the synchronization operations used.","abstract_html":"Parallel programs are significantly different from sequential programs in the sense that they can exhibit timing-dependent behaviour. The same program with the same input data can produce different results on different executions. This is unacceptable for a large number of programs. The main focus of this thesis is techniques to automatically detect such situations. Since nondeterminacy is intimately related to the ordering between operations executed by the program, the main problem studied is that of computing ordering between operations. The ordering is determined by the synchronization operations used.","abstract_has_math":false,"creators":["Ghosh, Sanjoy"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Padua, D.A.","Emrath, P.A.,"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:24Z","date_published":"2014-12-17T20:00:24Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9305536"],"render_values":[{"text":"(UMI)AAI9305536","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72065","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Padua, D.A.","Emrath, P.A.,"]},{"key":"dc:creator","label":"Author","values":["Ghosh, Sanjoy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:24Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"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":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/72065","(UMI)AAI9305536"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Parallel programs are significantly different from sequential programs in the sense that they can exhibit timing-dependent behaviour. The same program with the same input data can produce different results on different executions. This is unacceptable for a large number of programs. The main focus of this thesis is techniques to automatically detect such situations. Since nondeterminacy is intimately related to the ordering between operations executed by the program, the main problem studied is that of computing ordering between operations. The ordering is determined by the synchronization operations used.","The computation of ordering can be done either at compile time, or execution time and later. We describe techniques for both. Static analysis is applicable to every input data set, but is approximate due to the incompleteness of information available at compile time. Execution time analysis, on the other hand, has complete information about the execution, but may be applicable only for the input data set used on that execution. The approach advocated is a combination of compile time and execution time analysis.","The feasibility of these ideas is demonstrated by the implementation of a tool that detects nondeterminacy in the parallel programs available to us. Detection is practical with a combination of aggressive compile time analysis and execution time checking.","As an extension of the work on detecting ordering, a technique is described to perform dataflow analysis of parallel programs in order to effect scalar optimizations such as conditional constant propagation. The new dataflow framework reflects the fact that in parallel programs a number of threads can execute simultaneously.","Made available in DSpace on 2014-12-17T20:00:24Z (GMT). No. of bitstreams: 1 9305536.pdf: 7450735 bytes, checksum: 24a957e7789c8599e5315c0566b58031 (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72233 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","150 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."]},{"key":"dc:title","label":"Title","values":["Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs"]}]}],"canonical_facts":{"dc:contributor":["Padua, D.A.","Emrath, P.A.,"],"dc:creator":["Ghosh, Sanjoy"],"dc:date":["2014-12-17T20:00:24Z","10000-01-01","1992"],"dc:description":["Parallel programs are significantly different from sequential programs in the sense that they can exhibit timing-dependent behaviour. The same program with the same input data can produce different results on different executions. This is unacceptable for a large number of programs. The main focus of this thesis is techniques to automatically detect such situations. Since nondeterminacy is intimately related to the ordering between operations executed by the program, the main problem studied is that of computing ordering between operations. The ordering is determined by the synchronization operations used.","The computation of ordering can be done either at compile time, or execution time and later. We describe techniques for both. Static analysis is applicable to every input data set, but is approximate due to the incompleteness of information available at compile time. Execution time analysis, on the other hand, has complete information about the execution, but may be applicable only for the input data set used on that execution. The approach advocated is a combination of compile time and execution time analysis.","The feasibility of these ideas is demonstrated by the implementation of a tool that detects nondeterminacy in the parallel programs available to us. Detection is practical with a combination of aggressive compile time analysis and execution time checking.","As an extension of the work on detecting ordering, a technique is described to perform dataflow analysis of parallel programs in order to effect scalar optimizations such as conditional constant propagation. The new dataflow framework reflects the fact that in parallel programs a number of threads can execute simultaneously.","Made available in DSpace on 2014-12-17T20:00:24Z (GMT). No. of bitstreams: 1 9305536.pdf: 7450735 bytes, checksum: 24a957e7789c8599e5315c0566b58031 (MD5) Previous issue date: 1992","Embargo set by: Seth Robbins for item 72233 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","150 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992."],"dc:identifier":["http://hdl.handle.net/2142/72065","(UMI)AAI9305536"],"dc:subject":["Computer Science"],"dc:title":["Automatic Detection of Nondeterminancy, and Scalar Optimizations in Parallel Programs"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:06Z"}