In computer science, a parallel random-access machine (PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM was intended as the parallel-computing analogy to the random-access machine (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 and communication, but provides any (problem-size-dependent) number of processors. Algorithm cost, for instance, is estimated using two parameters O(time) and O(time × 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.[1]
Here, E and C stand for 'exclusive' and 'concurrent' respectively. 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. Certain special cases such as SIMD 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
PRAM algorithms cannot be parallelized with the combination of CPU and dynamic random-access memory (DRAM) because DRAM does not allow concurrent access; but they can be implemented in hardware or read/write to the internal static random-access memory (SRAM) blocks of a field-programmable gate array (FPGA), it can be done using a 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 Vishkin (2011) demonstrate how a PRAM-like abstraction can be supported by the explicit multi-threading (XMT) paradigm and articles such as Caragea & Vishkin (2011) demonstrate that a PRAM algorithm for the maximum flow problem can provide strong speedups relative to the fastest serial program for the same problem.
Example code
This is an example of SystemVerilog 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 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
See also
External links
- Saarland University's prototype PRAM
- University Of Maryland's PRAM-On-Chip prototype. This prototype seeks to put many parallel processors and the fabric for inter-connecting them on a single chip
- XMTC: PRAM-like Programming - Software release
Unbounded collection of numbered RAM processors P0, P1, P2,... (without tapes). Unbounded collection of shared memory cells M[0], M[1], M[2],.... Each Pi has its own (unbounded) local memory (registers) and knows its index i. Each processor can access any shared memory cell (unless there is an access conflict, see further) in unit time. Input af a PRAM algorithm consists of n items stored in (usually the first) n shared memory cells. Output of a PRAM algorithm consists of n' items stored in n' shared memory cells. PRAM instructions execute in 3-phase cycles. Read (if any) from a shared memory cell. Local computation (if any). Write (if any) to a shared memory cell. Processors execute these 3-phase PRAM instructions synchronously. Special assumptions have to be made about R-R and W-W shared memory access conflicts. The only way processors can exchange data is by writing into and reading from memory cells. P0 has a special activation register specifying the maximum index of an active processor. Initially, only P0 is active, it computes the number of required active processors and loads this register, and then the other corresponding processors start executing their programs. Computation proceeds until P0 halts, at which time all other active processors are halted. Parallel time complexity = the time elapsed for P0's computation. Space complexity = the number of shared memory cells accessed.
- ^ Neil Immerman, Expressibility and parallel complexity. Siam Journal on Computing, vol. 18, no. 3, pp. 625-638, 1989.