Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, Parallel Random Access Machine (PRAM) is a shared memory
Shared memory
In computing, shared memory is memory that may be simultaneously accessed by multiple programs with an intent to provide communication among them or avoid redundant copies. Depending on context, programs may run on a single processor or on multiple separate processors...
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
. As its name indicates, the PRAM was intended as the parallel computing analogy to the random access machine
Random access machine
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
(RAM). In the same way, that the RAM is used by sequential algorithm designers to model algorithmic performance (such as time complexity), the PRAM used by parallel algorithm designers to model parallel algorithmic performance (such as time complexity, where the number of processors assumed is typically also stated). Similar to the way in which the RAM model neglects practical issues, such as access time to cache memory versus main memory, the PRAM model neglects such issues as synchronization
Synchronization (computer science)
In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
Communication is the activity of conveying meaningful information. Communication requires a sender, a message, and an intended recipient, although the receiver need not be present or aware of the sender's intent to communicate at the time of communication; thus communication can occur across vast...
, but provides any (problem size-dependent) number of processors. Algorithm cost, for instance, is estimated using two parameters O(time) and O(time x processor_number).
Read/write conflicts
Read/write conflicts in accessing the same shared memory location simultaneously are resolved by one of the following strategies:
Exclusive Read Exclusive Write (EREW)—every memory cell can be read or written to by only one processor at a time
Concurrent Read Exclusive Write (CREW)—multiple processors can read a memory cell but only one can write at a time
Exclusive Read Concurrent Write (ERCW)—never considered
Concurrent Read Concurrent Write (CRCW)—multiple processors can read and write. A CRCW PRAM is sometimes called a concurrent random access machine.
Here, E and C stand for 'exclusive' and 'concurrent' correspondingly. The read causes no discrepancies while the concurrent write is further defined as:
Common—all processors write the same value; otherwise is illegal
Arbitrary—only one arbitrary attempt is successful, others retire
Priority—processor rank indicates who gets to write
Another kind of array Reduction operation like SUM, Logical AND or MAX.
Several simplifying assumptions are made while considering the development of algorithms for PRAM. They are :
There is no limit on the number of processors in the machine.
Any memory location is uniformly accessible from any processor.
There is no limit on the amount of shared memory in the system.
Resource contention is absent.
The programs written on these machines are, in general, of type MIMD
MIMD
In computing, MIMD is a technique employed to achieve parallelism. Machines using MIMD have a number of processors that function asynchronously and independently. At any time, different processors may be executing different instructions on different pieces of data...
Single instruction, multiple data , is a class of parallel computers in Flynn's taxonomy. It describes computers with multiple processing elements that perform the same operation on multiple data simultaneously...
may also be handled in such a framework.
These kinds of algorithms are useful for understanding the exploitation of concurrency, dividing the original problem into similar sub-problems and solving them in parallel.
Implementation
You cannot implement these algorithms with the combination of CPU
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
and DRAM because DRAM does not allow concurrent access, but if you implement it by hardware or read/write to the internal memory (SRAM) of FPGA
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...
, you can use CRCW algorithm.
However, the test for practical relevance of PRAM (or RAM) algorithms depends on whether their cost model provides an effective abstraction of some computer; the structure of that computer can be quite different than the abstract model. The knowledge of the layers of software and hardware that need to be inserted is beyond the scope of this article. But, articles such as demonstrate how a PRAM-like abstraction can be supported by the Explicit multi-threading
Explicit multi-threading
Explicit Multi-Threading is a computer science paradigm for building and programming parallel computers designed around the Parallel Random Access Machine parallel computational model...
(XMT) paradigm and articles such as demonstrate that a PRAM algorithm for the maximum flow problem
Maximum flow problem
In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....
can provide strong speedups relative to the fastest serial program for the same problem.
In the semiconductor and electronic design industry, SystemVerilog is a combined Hardware Description Language and Hardware Verification Language based on extensions to Verilog.-History:...
code which finds the maximum value in the array in only 2 clock cycles. It compares all the combinations of the elements in the array at the first clock, and merges the result at the second clock. It uses CRCW memory; m[i] <= 1 and maxNo <= data[i] are written concurrently. The concurrency causes no conflicts because the algorithm guarantees that the same value is written to the same memory. This code can be run on FPGA
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...
hardware.
module FindMax #(parameter int len = 8)
(input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);
typedef enum bit[1:0] {COMPARE, MERGE, DONE} State;
State state;
bit m[len];
int i, j;
always_ff @(posedge clock, negedge resetN) begin
if (!resetN) begin
for (i = 0; i < len; i++) m[i] <= 0;
state <= COMPARE;
end else begin
case (state)
COMPARE: begin
for (i = 0; i < len; i++) begin
for (j = 0; j < len; j++) begin
if (data[i] < data[j]) m[i] <= 1;
end
end
state <= MERGE;
end
MERGE: begin
for (i = 0; i < len; i++) begin
if (m[i]
0) maxNo <= data[i];
end
state <= DONE;
end
endcase
end
end
endmodule
Flynn's taxonomy is a classification of computer architectures, proposed by Michael J. Flynn in 1966.-Classifications:The four classifications defined by Flynn are based upon the number of concurrent instruction and data streams available in the architecture:Single Instruction, Single Data stream...
In computer science, random access machine is an abstract machine in the general class of register machines. The RAM is very similar to the counter machine but with the added capability of 'indirect addressing' of its registers...
XMTC is a shared-memory parallel programming language. It is an extension of the C programming language which strives to enable easy PRAM-like programming based on the explicit multi-threading paradigm. It is developed as part of the by a research team at the University of Maryland, College...
