{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69423"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69423","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Instruction Sets for Parallel Random Access Machines","abstract":"In this thesis, we compare the computational power of time bounded Parallel Random Access Machines (PRAMs) with different instruction sets. A basic PRAM can perform the following operations in unit-time: addition, subtraction, Boolean operations, comparisons, and indirect addressing. Multiple processors may concurrently read and concurrently write a single cell. Let PRAM$\\lbrack op\\rbrack$ denote the class of PRAMs with the basic instruction set augmented with the set $op$ of instructions. Let $\\uparrow$ and $\\downarrow$ denote unrestricted left and right shift, respectively.","abstract_html":"In this thesis, we compare the computational power of time bounded Parallel Random Access Machines (PRAMs) with different instruction sets. A basic PRAM can perform the following operations in unit-time: addition, subtraction, Boolean operations, comparisons, and indirect addressing. Multiple processors may concurrently read and concurrently write a single cell. Let PRAM$\\lbrack op\\rbrack$ denote the class of PRAMs with the basic instruction set augmented with the set $op$ of instructions. Let $\\uparrow$ and $\\downarrow$ denote unrestricted left and right shift, respectively.","abstract_has_math":true,"creators":["Trahan, Jerry Lee"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Loui, Michael C."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:05:43Z","date_published":"2014-12-15T19:05:43Z","updated_at":"2026-07-22T22:26:00Z","subjects":["Engineering, Electronics and Electrical","Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8908868"],"render_values":[{"text":"(UMI)AAI8908868","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69423","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Loui, Michael C."]},{"key":"dc:creator","label":"Author","values":["Trahan, Jerry Lee"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:05:43Z","10000-01-01","1988"]},{"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":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69423","(UMI)AAI8908868"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we compare the computational power of time bounded Parallel Random Access Machines (PRAMs) with different instruction sets. A basic PRAM can perform the following operations in unit-time: addition, subtraction, Boolean operations, comparisons, and indirect addressing. Multiple processors may concurrently read and concurrently write a single cell. Let PRAM$\\lbrack op\\rbrack$ denote the class of PRAMs with the basic instruction set augmented with the set $op$ of instructions. Let $\\uparrow$ and $\\downarrow$ denote unrestricted left and right shift, respectively.","We prove that polynomial time on a PRAM(*) or on a PRAM(*,$\\div\\rbrack$ or on a PRAM$\\lbrack\\uparrow,\\downarrow\\rbrack$ is equivalent to polynomial space on a Turing machine (PSPACE). This extends the result that polynomial time on a basic PRAM is equivalent to PSPACE (Fortune and Wyllie, 1978) to hold when the PRAM is allowed unit-time multiplication or division or unrestricted shifts. It also extends to the PRAM the results that polynomial time on a random access machine (RAM) with multiplication is equivalent to PSPACE (Hartmanis and Simon, 1974) and that polynomial time on a RAM with shifts (that is, a vector machine) is equivalent to PSPACE (Pratt and Stockmeyer, 1976; Simon, 1977).","This thesis establishes that the class of languages accepted in polynomial time on a PRAM (*,$\\uparrow,\\downarrow$) contains the class of languages accepted in exponential time on a nondeterministic Turing machine (NEXPTIME) and is contained in the class of languages accepted in exponential space on a Turing machine. This result is notable because if, as has been conjectured, NEXPTIME properly contains PSPACE, then a PRAM (*,$\\uparrow,\\downarrow$) is more powerful, to within a polynomial factor in time, than a PRAM with one of the other instruction sets.","We present efficient simulations of PRAMs with enhanced instruction sets by sequential RAMs with the same instruction sets. This thesis presents simulations of probabilistic PRAMs by deterministic PRAMs, using parallelism to replace randomness. We also give simulations of PRAM (op) s by PRAMs, where both the simulated machine and the simulating machine are exlusive read, exclusive write machines.","Made available in DSpace on 2014-12-15T19:05:43Z (GMT). No. of bitstreams: 1 8908868.pdf: 6542399 bytes, checksum: 61e5a47eb42dc9f2c40bbf15c267956e (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69589 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","170 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."]},{"key":"dc:title","label":"Title","values":["Instruction Sets for Parallel Random Access Machines"]}]}],"canonical_facts":{"dc:contributor":["Loui, Michael C."],"dc:creator":["Trahan, Jerry Lee"],"dc:date":["2014-12-15T19:05:43Z","10000-01-01","1988"],"dc:description":["In this thesis, we compare the computational power of time bounded Parallel Random Access Machines (PRAMs) with different instruction sets. A basic PRAM can perform the following operations in unit-time: addition, subtraction, Boolean operations, comparisons, and indirect addressing. Multiple processors may concurrently read and concurrently write a single cell. Let PRAM$\\lbrack op\\rbrack$ denote the class of PRAMs with the basic instruction set augmented with the set $op$ of instructions. Let $\\uparrow$ and $\\downarrow$ denote unrestricted left and right shift, respectively.","We prove that polynomial time on a PRAM(*) or on a PRAM(*,$\\div\\rbrack$ or on a PRAM$\\lbrack\\uparrow,\\downarrow\\rbrack$ is equivalent to polynomial space on a Turing machine (PSPACE). This extends the result that polynomial time on a basic PRAM is equivalent to PSPACE (Fortune and Wyllie, 1978) to hold when the PRAM is allowed unit-time multiplication or division or unrestricted shifts. It also extends to the PRAM the results that polynomial time on a random access machine (RAM) with multiplication is equivalent to PSPACE (Hartmanis and Simon, 1974) and that polynomial time on a RAM with shifts (that is, a vector machine) is equivalent to PSPACE (Pratt and Stockmeyer, 1976; Simon, 1977).","This thesis establishes that the class of languages accepted in polynomial time on a PRAM (*,$\\uparrow,\\downarrow$) contains the class of languages accepted in exponential time on a nondeterministic Turing machine (NEXPTIME) and is contained in the class of languages accepted in exponential space on a Turing machine. This result is notable because if, as has been conjectured, NEXPTIME properly contains PSPACE, then a PRAM (*,$\\uparrow,\\downarrow$) is more powerful, to within a polynomial factor in time, than a PRAM with one of the other instruction sets.","We present efficient simulations of PRAMs with enhanced instruction sets by sequential RAMs with the same instruction sets. This thesis presents simulations of probabilistic PRAMs by deterministic PRAMs, using parallelism to replace randomness. We also give simulations of PRAM (op) s by PRAMs, where both the simulated machine and the simulating machine are exlusive read, exclusive write machines.","Made available in DSpace on 2014-12-15T19:05:43Z (GMT). No. of bitstreams: 1 8908868.pdf: 6542399 bytes, checksum: 61e5a47eb42dc9f2c40bbf15c267956e (MD5) Previous issue date: 1988","Embargo set by: Seth Robbins for item 69589 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","170 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1988."],"dc:identifier":["http://hdl.handle.net/2142/69423","(UMI)AAI8908868"],"dc:subject":["Engineering, Electronics and Electrical","Computer Science"],"dc:title":["Instruction Sets for Parallel Random Access Machines"],"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:26:00Z"}