{"id":{"repo_id":"montana-tech","oai_identifier":"oai:scholarworks.umt.edu:etd-1145"},"canonical_url":"https://search.dev.ndltd.org/etd/montana-tech/oai:scholarworks.umt.edu:etd-1145","repository":{"repo_id":"montana-tech","name":"Montana Technology","base_url":"https://scholarworks.umt.edu/do/oai/"},"display":{"title":"AN EQUIVALENT CLASS SOLUTION FOR A COMPLETE TEST OF A PARALLEL PROGRAM","abstract":"With the advent of multi-core chips (multiple CPUs on a single chip) a fundamental shift in the design of programs is taking place. Previous use of parallel code in programs was limited to servers that contained multiple CPUs on separate chips. This idea is starting to change, with the majority of chips sold today containing multiple CPUs which require parallel code in software programs. The use of parallel code is not without problems. Non-parallel code executes programming statements in the same order, every time the same inputs are used. This result contrasts parallel code in the extreme. Identical inputs and conditions in no way to guarantee that parallel code will result in the same order of execution. For that reason testing parallel code is dramatically more difficult. It is because of this difficulty that I propose a solution that will allow a tester to guarantee a complete coverage of the shared memory parallel code through a series of non-exhaustive tests. This solution relies on the fact that the majority of the lines of code in the different threads don’t access the shared memory of program. This concept is what allows the creation of equivalent execution classes. Two execution schedules are equivalent if the critical sections that conflict with previously executed sections are in the same order in the schedule and the grouping of code between these sections are simply permutations of legal execution ordering.","abstract_html":"With the advent of multi-core chips (multiple CPUs on a single chip) a fundamental shift in the design of programs is taking place. Previous use of parallel code in programs was limited to servers that contained multiple CPUs on separate chips. This idea is starting to change, with the majority of chips sold today containing multiple CPUs which require parallel code in software programs. The use of parallel code is not without problems. Non-parallel code executes programming statements in the same order, every time the same inputs are used. This result contrasts parallel code in the extreme. Identical inputs and conditions in no way to guarantee that parallel code will result in the same order of execution. For that reason testing parallel code is dramatically more difficult. It is because of this difficulty that I propose a solution that will allow a tester to guarantee a complete coverage of the shared memory parallel code through a series of non-exhaustive tests. This solution relies on the fact that the majority of the lines of code in the different threads don’t access the shared memory of program. This concept is what allows the creation of equivalent execution classes. Two execution schedules are equivalent if the critical sections that conflict with previously executed sections are in the same order in the schedule and the grouping of code between these sections are simply permutations of legal execution ordering.","abstract_has_math":false,"creators":["Wolf, Peter Michael"],"institution":"University of Montana","degree_name":"Master of Science (MS)","degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-01-01T08:00:00Z","date_published":"2011-01-01T08:00:00Z","updated_at":"2026-07-24T03:12:42Z","subjects":["Algorithms","Parallel Software","Software Quality Assurance"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarworks.umt.edu/etd/126","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Wolf, Peter Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:publisher","label":"Institution","values":["University of Montana"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Algorithms","Parallel Software","Software Quality Assurance"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarworks.umt.edu/etd/126"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["With the advent of multi-core chips (multiple CPUs on a single chip) a fundamental shift in the design of programs is taking place. Previous use of parallel code in programs was limited to servers that contained multiple CPUs on separate chips. This idea is starting to change, with the majority of chips sold today containing multiple CPUs which require parallel code in software programs. The use of parallel code is not without problems. Non-parallel code executes programming statements in the same order, every time the same inputs are used. This result contrasts parallel code in the extreme. Identical inputs and conditions in no way to guarantee that parallel code will result in the same order of execution. For that reason testing parallel code is dramatically more difficult. It is because of this difficulty that I propose a solution that will allow a tester to guarantee a complete coverage of the shared memory parallel code through a series of non-exhaustive tests. This solution relies on the fact that the majority of the lines of code in the different threads don’t access the shared memory of program. This concept is what allows the creation of equivalent execution classes. Two execution schedules are equivalent if the critical sections that conflict with previously executed sections are in the same order in the schedule and the grouping of code between these sections are simply permutations of legal execution ordering."]},{"key":"dc:title","label":"Title","values":["AN EQUIVALENT CLASS SOLUTION FOR A COMPLETE TEST OF A PARALLEL PROGRAM"]}]}],"canonical_facts":{"dc:creator":["Wolf, Peter Michael"],"dc:description.abstract":["With the advent of multi-core chips (multiple CPUs on a single chip) a fundamental shift in the design of programs is taking place. Previous use of parallel code in programs was limited to servers that contained multiple CPUs on separate chips. This idea is starting to change, with the majority of chips sold today containing multiple CPUs which require parallel code in software programs. The use of parallel code is not without problems. Non-parallel code executes programming statements in the same order, every time the same inputs are used. This result contrasts parallel code in the extreme. Identical inputs and conditions in no way to guarantee that parallel code will result in the same order of execution. For that reason testing parallel code is dramatically more difficult. It is because of this difficulty that I propose a solution that will allow a tester to guarantee a complete coverage of the shared memory parallel code through a series of non-exhaustive tests. This solution relies on the fact that the majority of the lines of code in the different threads don’t access the shared memory of program. This concept is what allows the creation of equivalent execution classes. Two execution schedules are equivalent if the critical sections that conflict with previously executed sections are in the same order in the schedule and the grouping of code between these sections are simply permutations of legal execution ordering."],"dc:identifier":["https://scholarworks.umt.edu/etd/126"],"dc:publisher":["University of Montana"],"dc:subject":["Algorithms","Parallel Software","Software Quality Assurance"],"dc:title":["AN EQUIVALENT CLASS SOLUTION FOR A COMPLETE TEST OF A PARALLEL PROGRAM"],"dc:type":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-07-24T03:12:42Z"}