{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/72090"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/72090","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Compile-Time Analysis of Explicitly Parallel Programs","abstract":"Explicit parallelism not only complicates the semantics of a programming language, but also invalidates most current compiler techniques for program analyses and optimizations. The problem stems from the inadequacy of control flow graphs to describe information flows in a parallel program, and the insufficiency of data dependences and control dependences to describe the constraints for a correct execution. Because of the difficulties in analyzing explicitly parallel programs, most compilers simply side-step the problems either by restricting data sharing among concurrent activities or not optimizing parallel codes. Some even produce wrong codes that violate the program semantics.","abstract_html":"Explicit parallelism not only complicates the semantics of a programming language, but also invalidates most current compiler techniques for program analyses and optimizations. The problem stems from the inadequacy of control flow graphs to describe information flows in a parallel program, and the insufficiency of data dependences and control dependences to describe the constraints for a correct execution. Because of the difficulties in analyzing explicitly parallel programs, most compilers simply side-step the problems either by restricting data sharing among concurrent activities or not optimizing parallel codes. Some even produce wrong codes that violate the program semantics.","abstract_has_math":false,"creators":["Chow, Jyh-Herng"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Harrison, Williams Ludwell, III,"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-17T20:00:43Z","date_published":"2014-12-17T20:00:43Z","updated_at":"2026-07-22T22:26:06Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI9411591"],"render_values":[{"text":"(UMI)AAI9411591","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/72090","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Harrison, Williams Ludwell, III,"]},{"key":"dc:creator","label":"Author","values":["Chow, Jyh-Herng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-17T20:00:43Z","10000-01-01","1993"]},{"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/72090","(UMI)AAI9411591"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Explicit parallelism not only complicates the semantics of a programming language, but also invalidates most current compiler techniques for program analyses and optimizations. The problem stems from the inadequacy of control flow graphs to describe information flows in a parallel program, and the insufficiency of data dependences and control dependences to describe the constraints for a correct execution. Because of the difficulties in analyzing explicitly parallel programs, most compilers simply side-step the problems either by restricting data sharing among concurrent activities or not optimizing parallel codes. Some even produce wrong codes that violate the program semantics.","This work proposes a general framework for analyzing parallel programs where concurrent activities interact through shared variables and presents the analyses of side effects, data dependences, object lifetimes, and concurrent expressions for a language with dynamic allocations, pointers, first-class functions, and cobegin parallelism.","This framework is based on abstract interpretation, a semantics-based analysis technique. We present a formal semantics of the language, based on a labeled transition system. Because every possible interaction between concurrent activities has to be considered, the state space of the analysis must be reduced. We approach this problem in two ways: eliminating redundant interleavings, which do not contribute to final results, and abstract interpretation, which provides systematic methods for combing related states. An iterative algorithm is presented for state space reduction in the presence of pointers and closures. Then, we present the abstract domains and the analyses under these abstract domains. We prove the correctness and termination of this abstract analysis. The results of the analyses can facilitate many applications, such as program optimization, memory management, and race detection. A graph representation of parallel programs useful for general compiler transformation is presented. Finally, implementation of this framework and its preliminary results are described.","Made available in DSpace on 2014-12-17T20:00:43Z (GMT). No. of bitstreams: 1 9411591.pdf: 8810285 bytes, checksum: 26f3685634e13b302fd30f43c0d821dd (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72258 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","226 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."]},{"key":"dc:title","label":"Title","values":["Compile-Time Analysis of Explicitly Parallel Programs"]}]}],"canonical_facts":{"dc:contributor":["Harrison, Williams Ludwell, III,"],"dc:creator":["Chow, Jyh-Herng"],"dc:date":["2014-12-17T20:00:43Z","10000-01-01","1993"],"dc:description":["Explicit parallelism not only complicates the semantics of a programming language, but also invalidates most current compiler techniques for program analyses and optimizations. The problem stems from the inadequacy of control flow graphs to describe information flows in a parallel program, and the insufficiency of data dependences and control dependences to describe the constraints for a correct execution. Because of the difficulties in analyzing explicitly parallel programs, most compilers simply side-step the problems either by restricting data sharing among concurrent activities or not optimizing parallel codes. Some even produce wrong codes that violate the program semantics.","This work proposes a general framework for analyzing parallel programs where concurrent activities interact through shared variables and presents the analyses of side effects, data dependences, object lifetimes, and concurrent expressions for a language with dynamic allocations, pointers, first-class functions, and cobegin parallelism.","This framework is based on abstract interpretation, a semantics-based analysis technique. We present a formal semantics of the language, based on a labeled transition system. Because every possible interaction between concurrent activities has to be considered, the state space of the analysis must be reduced. We approach this problem in two ways: eliminating redundant interleavings, which do not contribute to final results, and abstract interpretation, which provides systematic methods for combing related states. An iterative algorithm is presented for state space reduction in the presence of pointers and closures. Then, we present the abstract domains and the analyses under these abstract domains. We prove the correctness and termination of this abstract analysis. The results of the analyses can facilitate many applications, such as program optimization, memory management, and race detection. A graph representation of parallel programs useful for general compiler transformation is presented. Finally, implementation of this framework and its preliminary results are described.","Made available in DSpace on 2014-12-17T20:00:43Z (GMT). No. of bitstreams: 1 9411591.pdf: 8810285 bytes, checksum: 26f3685634e13b302fd30f43c0d821dd (MD5) Previous issue date: 1993","Embargo set by: Seth Robbins for item 72258 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","226 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1993."],"dc:identifier":["http://hdl.handle.net/2142/72090","(UMI)AAI9411591"],"dc:subject":["Computer Science"],"dc:title":["Compile-Time Analysis of Explicitly 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"}