Instruction Sets for Parallel Random Access Machines

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Trahan, Jerry Lee

Contributors dc:contributor

• Loui, Michael C.

• Engineering, Electronics and Electrical
• Computer Science

Identifier

(UMI)AAI8908868

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/69423