Hubbry Logo
Parallel RAMParallel RAMMain
Open search
Parallel RAM
Community hub
Parallel RAM
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Parallel RAM
Parallel RAM
Parallel RAM
View on Wikipedia
from Wikipedia

In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused with random-access memory).[1] In the same way that the RAM is used by sequential-algorithm designers to model algorithmic performance (such as time complexity), the PRAM is 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

[edit]

Read/write conflicts, commonly termed interlocking in accessing the same shared memory location simultaneously are resolved by one of the following strategies:

  1. Exclusive read exclusive write (EREW)—every memory cell can be read or written to by only one processor at a time
  2. Concurrent read exclusive write (CREW)—multiple processors can read a memory cell but only one can write at a time
  3. Exclusive read concurrent write (ERCW)—mostly never considered because it mostly doesn't add more power[2]
  4. Concurrent read concurrent write (CRCW)—multiple processors can read and write. A CRCW PRAM is sometimes called a concurrent random-access machine.[3]

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:

  1. There is no limit on the number of processors in the machine.
  2. Any memory location is uniformly accessible from any processor.
  3. There is no limit on the amount of shared memory in the system.
  4. Resource contention is absent.
  5. The programs written on these machines are, in general, of type SIMD.

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. The introduction of the formal 'P-RAM' model in Wyllie's 1979 thesis[4] had the aim of quantifying analysis of parallel algorithms in a way analogous to the Turing Machine. The analysis focused on a MIMD model of programming using a CREW model but showed that many variants, including implementing a CRCW model and implementing on an SIMD machine, were possible with only constant overhead.

Implementation

[edit]

PRAM algorithms cannot be parallelized with the combination of CPU and dynamic random-access memory (DRAM) because DRAM does not allow concurrent access to a single bank (not even different addresses in the bank); 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. The article Ghanim, Vishkin & Barua (2018) demonstrated that PRAM algorithms as-is can achieve competitive performance even without any additional effort to cast them as multi-threaded programs on XMT.

Example code

[edit]

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

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Parallel RAM

View on Grokipedia
from Grokipedia
The Parallel Random Access Machine (PRAM) is an abstract theoretical model of parallel computation that extends the sequential Random Access Machine (RAM) model by incorporating multiple identical processors that operate synchronously and share a common global memory, allowing for the analysis of parallel algorithms in an idealized shared-memory environment. Introduced by Steven Fortune and James Wyllie in 1978, the PRAM assumes unit-time execution for basic arithmetic and logical operations, memory accesses, and processor synchronization, with processors executing a single program in a SIMD (Single Instruction, Multiple Data) manner unless deactivated by private flags. This model abstracts away hardware details like communication costs and contention, focusing instead on algorithmic efficiency in terms of time and processor utilization. Key characteristics of the PRAM include an unbounded number of processors, each with a unique identifier, an accumulator, local memory, and a program counter, all synchronized by a global clock that advances in discrete steps. Memory is divided into a shared global component accessible by all processors and private local components, with inputs typically loaded into special registers and outputs determined by the halting state of the primary processor. To address concurrent memory accesses, the PRAM is subdivided into variants based on read and write concurrency rules: EREW (Exclusive Read, Exclusive Write), which prohibits simultaneous reads or writes to the same location; CREW (Concurrent Read, Exclusive Write), permitting multiple reads but not writes; and CRCW (Concurrent Read, Concurrent Write), the most permissive, which allows both and includes sub-variants like Common (all writes must match), Arbitrary (one write selected nondeterministically), Priority (lowest-indexed processor wins), and Combining (writes aggregated via operations like sum or max). These variants form a hierarchy of computational power, with EREW being the weakest and CRCW the strongest, though simulations between them ensure polynomial-time equivalence for many problems. The PRAM model has played a foundational role in design and complexity theory, serving as a benchmark for developing efficient solutions to problems such as prefix computation, sorting, , and matrix operations, while highlighting theoretical limits on speedup via tools like Brent's scheduling theorem, which bounds execution time as O(W/p + T) where W is sequential work, p is the number of processors, and T is the parallel time. Despite its idealism—ignoring real-world issues like latency and bandwidth—its simplicity has enabled the creation of a rich body of algorithms in the NC class (problems solvable in polylogarithmic time on a polynomial number of processors), influencing practical parallel programming paradigms and hardware designs.

Model Fundamentals

Definition and Purpose

The Parallel Random Access Machine (PRAM) is an abstract shared-memory model of parallel computation consisting of multiple processors that operate in parallel and access a common global . In this model, processors execute instructions synchronously, sharing a single without the constraints of physical hardware limitations such as interconnect topologies or cache hierarchies. Introduced in 1978 by Steven Fortune and James Wyllie as an extension of the sequential (RAM) model, the PRAM provides a foundational framework for exploring parallelism in computation. Their work, presented at the 10th ACM Symposium on Theory of Computing, aimed to bridge sequential and parallel paradigms by defining a simple yet powerful model that captures the essence of concurrent processing. The primary purpose of the PRAM is to serve as a theoretical benchmark for designing and analyzing parallel algorithms, abstracting away low-level architectural details like communication delays, memory hierarchies, or synchronization overheads inherent in real machines. This abstraction enables researchers to focus on algorithmic efficiency in terms of time and work, facilitating the development of scalable solutions that can later be mapped to practical architectures. Key assumptions underlying the PRAM include synchronous execution governed by a global clock, where all active processors perform one operation per time step; uniform constant-time (O(1)) access to any location; and an idealized whose size is unbounded but typically considered in the input size for realistic . These assumptions idealize parallelism to emphasize conceptual clarity over fidelity.

Core Components

The Parallel Random Access Machine (PRAM) model features a set of pp identical processors, each equipped with a , an accumulator for holding values, private local memory, local registers for temporary storage, and a . These processors execute instructions either in a synchronized manner, akin to single-instruction multiple-data (SIMD) operation, or independently in a multiple-instruction multiple-data (MIMD) style, depending on the specific variant considered. The processors are indexed from 1 to pp, with pp typically chosen as O(n)O(n) or n/log⁡nn / \log n, where nn is the input size, to balance parallelism and efficiency in algorithm design. At the heart of the PRAM is a global organized as a single array of mm words, where m≥nm \geq n, and each word stores a fixed-size or value. All processors access this memory concurrently, with each read or write operation being atomic and completing in unit time, abstracting away lower-level hardware details for theoretical analysis. Input data is conventionally pre-loaded into the initial nn locations of the shared memory (typically indexed from 1 to nn), while output is produced by writing results back to designated memory cells, such as location 1 for a single aggregate value. The model assumes no dedicated processors, with all data preparation handled externally to focus on computational aspects. The execution environment in the PRAM is fully deterministic, with every basic operation—such as arithmetic, logical computations, or memory access—incurring a , and all processors advancing in synchronized steps governed by a global clock. This synchronous structure ensures predictable behavior, serving as an abstraction for designing and analyzing parallel algorithms.

Memory Access Rules

Concurrent Read and Write Operations

In the Parallel Random Access Machine (PRAM) model, concurrent reads allow multiple processors to access the same shared memory location simultaneously without interference, with each processor receiving the identical current value stored there. This feature facilitates efficient broadcasting and data dissemination among processors, as the read operation does not alter the memory content and is unaffected by parallel accesses. The original formulation of the PRAM, which permits such concurrent reads, was introduced to model parallelism in shared-memory systems where information sharing is a key advantage. Concurrent writes in PRAM enable processors to update distinct memory locations in parallel without conflict, promoting scalability in algorithms that distribute data modifications across processors. However, when multiple processors attempt to write to the same location in the same step, a conflict occurs, and the outcome varies by PRAM variant: for instance, exclusive-write models reject or halt on such attempts, while concurrent-write models resolve them through predefined rules such as selecting an arbitrary value or requiring identical inputs from all writers. This distinction ensures that while writes to separate locations proceed unimpeded, shared-location access is managed to maintain model consistency. Each read or write operation in PRAM is atomic, executing indivisibly and completing within a single unit time step, thereby preventing partial observations or incomplete updates that could arise in non-atomic settings. This atomicity assumes ideal hardware where access latency is uniform and negligible, allowing all operations in a step to be resolved coherently. in PRAM is governed by an implicit global clock that orchestrates parallel execution, ensuring all processors advance in synchronized steps without explicit per-operation coordination. This mechanism simplifies algorithm design by eliminating timing discrepancies, though programmers may employ barriers—implemented via flags—for explicit when dependencies require it. The processor- structure, with unbounded processors connected to a global , underpins these operations by providing uniform unit-time access to any location.

Conflict Types and Resolution

In the Parallel Random Access Machine (PRAM) model, read conflicts arise when multiple processors attempt to access the same memory location simultaneously for reading. Generally, concurrent reads are allowed, enabling processors to retrieve the same value without interference, as the model assumes uniform and instantaneous access to . However, in exclusive-read variants, such as the Exclusive-Read Exclusive-Write (EREW) PRAM, multiple reads from the same location in a single step are prohibited, requiring algorithms to schedule accesses to avoid such conflicts. This restriction simplifies theoretical analysis but may impose additional coordination overhead. Write conflicts occur when two or more processors attempt to write to the same location during the same parallel step, which is undefined or leads to computation rejection in the basic PRAM model without specified resolution. In the foundational definition, simultaneous writes to the same cell cause the machine to halt, emphasizing the need for algorithms to ensure exclusive writes in non-conflicting scenarios. Such conflicts highlight the model's abstraction of , where unresolved writes can invalidate parallel execution. To handle write conflicts in models permitting concurrent writes, several resolution strategies are employed. In priority-based schemes, a predefined ordering, such as the lowest-indexed processor, determines which write succeeds, while others are ignored. Aggregation methods, or associative combining functions, resolve conflicts by applying an operation like , maximum, or logical OR to all attempted values, preserving useful information from multiple writes. In exclusive-write models, conflicts are avoided entirely through algorithmic , such as processor scheduling or partitioning, rather than runtime resolution. These approaches, introduced in early analyses of concurrent-write PRAMs, allow for greater parallelism but require careful selection based on the computation's needs. The presence of conflicts and their resolutions significantly impacts achievable parallelism in PRAM algorithms. Unresolved or frequent conflicts limit by necessitating of accesses, increasing the critical path length and potentially raising from O(1) to Ω(log n) for certain operations. Resolution mechanisms introduce overhead, such as additional steps for priority checks or combining computations, or require more processors to maintain , as seen in simulations where stronger enables constant-time execution but at the cost of work . Overall, effective conflict management is crucial for realizing theoretical , influencing the design of parallel algorithms across PRAM variants.

PRAM Variants

Exclusive Access Models

Exclusive access models in the Parallel Random Access Machine (PRAM) framework impose strict restrictions on memory access to eliminate conflicts, prioritizing deterministic behavior and analytical simplicity over maximum concurrency. These models, which emerged as refinements to the original PRAM introduced by Fortune and Wyllie in , ensure that no two processors attempt to read or write the same memory location simultaneously in certain ways, facilitating easier proof of correctness and simulation on sequential hardware. Among them, the Exclusive Read, Exclusive Write (EREW) PRAM represents the strictest variant, where no simultaneous reads or writes to the same cell are permitted; each processor must access unique locations in every step. This constraint avoids all concurrency issues at the memory level, making EREW algorithms inherently conflict-free and suitable for environments requiring guaranteed exclusivity. The Concurrent Read, Exclusive Write (CREW) PRAM relaxes the read restriction of EREW while maintaining exclusivity for writes, allowing multiple processors to read the same memory cell simultaneously but prohibiting concurrent writes to any single cell. In CREW, concurrent reads return the same value to all accessing processors, enabling efficient dissemination without additional . This variant proves particularly useful for pointer-based algorithms, such as list ranking or tree traversals, where multiple processors often need to inspect shared pointers or node concurrently but update structures individually. Snir demonstrated in 1985 that CREW is strictly more powerful than EREW by showing that searching a sorted table requires Ω(log n / log p) time on CREW but at least Ω(log n - log p) on EREW with p processors and n elements, highlighting CREW's advantage in read-intensive computations. These models offer key advantages in theoretical analysis and implementation. Their deterministic outcomes eliminate the need for complex logic, simplifying proofs of algorithm correctness and enabling straightforward simulations on sequential machines, often with polylogarithmic overhead. For instance, EREW's total exclusion facilitates direct mapping to hardware with limited concurrency support, while CREW's read allowance boosts parallelism in algorithms like parallel prefix computations without introducing nondeterminism. However, these restrictions demand careful processor scheduling to maximize utilization, as violations halt execution, leading to lower overall concurrency compared to models permitting concurrent writes. This can result in serialized operations for write-heavy tasks, potentially underutilizing available processors and increasing runtime for certain problems.

Concurrent Access Models

The Concurrent Read Concurrent Write (CRCW) PRAM represents the most permissive variant of the Parallel model, allowing multiple processors to simultaneously read from or write to the same location in constant time. Introduced as an extension of the foundational PRAM framework, this model maximizes concurrency by not restricting simultaneous accesses, thereby enabling algorithms that exploit aggressive parallelism but at the cost of defined conflict resolution mechanisms. Write conflicts in CRCW arise when multiple processors target the same location, and resolution varies across sub-variants to ensure deterministic or combinable outcomes. CRCW PRAM sub-variants differ primarily in their write strategies. In the common CRCW model, concurrent writes succeed only if all processors attempt to write the identical value, which that value is then stored; otherwise, the operation may fail or signal an . The arbitrary CRCW variant selects one processor's value nondeterministically to store, introducing potential non-determinism that simplifies some implementations but complicates . Priority CRCW resolves conflicts by favoring the processor with the highest (or lowest) predefined priority, such as the minimum processor ID, ensuring a consistent winner among contenders. The combining CRCW variant, also known as associative or CRCW, applies a commutative and associative operation (e.g., or maximum) to merge conflicting writes into a single result, making it suitable for reduction operations. Additionally, some CRCW implementations incorporate , where processors can identify write conflicts in O(1) time, often by returning a special indicator value without completing the write. These models offer significant advantages in harnessing parallelism for computationally intensive tasks. For instance, in the combining CRCW variant, finding the maximum in an unsorted of n elements can be done in O(1) time using n processors, by having all processors concurrently write their values to a shared location, where the model applies the maximum operation to resolve the writes, far outperforming sequential approaches. Similarly, merging two sorted lists can leverage concurrent writes for efficient parallel integration, achieving near-optimal work-time trade-offs in problems like string matching or . CRCW variants can also efficiently simulate weaker PRAM models, such as or EREW, with logarithmic slowdowns, allowing algorithms designed for restricted access to run on more powerful hardware abstractions. However, trade-offs include the non-determinism of arbitrary CRCW, which may require additional verification steps, and the need for robust —such as those outlined in concurrent read and write operations—to maintain algorithm correctness.

Theoretical Analysis

Time and Work Complexity

In the Parallel Random Access Machine (PRAM) model, T(p)T(p) is defined as the number of synchronous parallel steps required to solve a problem using pp processors, where each step consists of local , access, and across all active processors. This measure captures the depth of the parallel , with the ideal goal for efficient algorithms being T(p)=O(T(1)log⁡p)T(p) = O\left( \frac{T(1)}{\log p} \right), where T(1)T(1) denotes the sequential ; this bound accounts for the logarithmic overhead in parallel primitives like prefix sums or , enabling near-linear in polylogarithmic time. Work complexity W(p)W(p) quantifies the total computational effort expended by the algorithm, computed as the product W(p)=p⋅T(p)W(p) = p \cdot T(p), representing the aggregate number of processor operations. For work-efficiency, a hallmark of optimal parallel algorithms in PRAM, W(p)W(p) should equal O(T(1))O(T(1)), ensuring that parallelism does not inflate the overall computational cost beyond the sequential baseline and preserving resources for large-scale problems. S(p)=T(1)T(p)S(p) = \frac{T(1)}{T(p)} evaluates the absolute performance gain from parallelism, while E(p)=S(p)p=T(1)p⋅T(p)E(p) = \frac{S(p)}{p} = \frac{T(1)}{p \cdot T(p)} assesses utilization, with values approaching 1 indicating ideal processor exploitation. Brent's theorem establishes a key theoretical foundation for PRAM performance analysis, stating that any parallel computation requiring total work WW and critical path length (depth) DD can be scheduled on pp processors to execute in time at most Wp+D\frac{W}{p} + D. This result, derived from scheduling strategies for arithmetic expression evaluation, implies that PRAM algorithms with bounded depth achieve practical time bounds even when processor counts vary, facilitating simulations and bounding overhead in concurrent access models. Isoefficiency further refines assessment by relating problem size nn to pp such that EE remains constant, derived from the overhead To=pT(p)−T(1)T_o = p T(p) - T(1), where sustained requires To=O(T(1))T_o = O(T(1)). In PRAM's idealized setting with negligible communication costs, the isoefficiency function often permits n=Θ(p)n = \Theta(p) for algorithms exhibiting linear concurrency, though variants with may impose polylogarithmic scaling to offset overheads.

Algorithm Examples

The prefix sum operation, also known as scan, computes an where each element is the cumulative sum of all preceding elements in the input , enabling efficient parallel implementations of sequential algorithms like . In the EREW PRAM model, a canonical algorithm for on an of n elements runs in O(log n) time using n processors, consisting of an up-sweep phase that builds partial sums in a fashion followed by a down-sweep phase that propagates the results back to compute the final prefixes. This approach, adapted from parallel prefix computation techniques, ensures no concurrent reads or writes to the same memory location by structuring the computation hierarchically. Parallel merging of two sorted lists, each of size n/2, into a single sorted list of size n exemplifies the use of concurrent reads in PRAM models. On a PRAM with n processors, this can be achieved in O(log n) time by having each processor perform a binary search to determine the insertion position for elements from one list into the other, followed by concurrent writes to disjoint output positions to avoid write conflicts. This method leverages the model's allowance for multiple reads from the same location while ensuring exclusive writes, making it a building block for parallel sorting networks. Finding the maximum value among n elements highlights the power of concurrent writes in relaxed PRAM variants. In the CRCW PRAM model, this can be achieved in O(log n) time using n processors via a tournament method where processors pairwise compare values and propagate winners toward a root in a . In the combining sub-variant of CRCW, where concurrent writes to the same are aggregated using an operation like max, the maximum can be computed in O(1) time with n processors by having all processors concurrently write their values to a shared , with the memory performing the max aggregation. Such techniques rely on the CRCW model's tolerance for concurrent access to enable efficient decisions. Key techniques in PRAM algorithm design include the Ladner-Fischer parallel prefix method, which computes associative operations like sums across n elements in O(log n) time but with fewer than n processors (specifically n / log n) to optimize resource usage, serving as a foundation for more efficient variants. Work-efficient implementations, such as the EREW prefix sum, achieve O(n) total operations while maintaining low parallelism depth, balancing processor count with time bounds. To avoid conflicts, processor partitioning assigns disjoint groups of processors to independent regions, ensuring compliance with EREW or constraints without additional synchronization overhead. These algorithms are evaluated using time and work complexity measures as defined in the theoretical analysis section.

Practical Aspects

Simulation Techniques

Simulation techniques for the Parallel Random Access Machine (PRAM) enable the emulation of its idealized concurrent access on sequential machines or less concurrent parallel architectures, facilitating testing and analysis without dedicated hardware. Sequential simulation involves a single processor executing PRAM steps by sequentially operations from all virtual processors, resolving conflicts using data structures such as priority queues for concurrent writes in CRCW PRAM variants, where writes are prioritized and serialized based on processor IDs or timestamps. For concurrent reads, segment trees or similar balanced structures allow efficient aggregation of multiple accesses to the same location, ensuring correctness while incurring an O(p) time cost per PRAM step for a p-processor CRCW PRAM, as all p operations and resolving conflicts (up to p per location) using data structures like hash tables or sorting requires linear time in p, though expected O(p) with hashing. This approach, detailed in surveys of emulation methods, processes reads and writes in a round-robin fashion across virtual processors but scales poorly for high concurrency due to the need to scan and sort access lists. Parallel simulation leverages a host parallel machine to emulate PRAM steps more efficiently, such as simulating an EREW PRAM on a CRCW PRAM host with constant or logarithmic overhead by partitioning memory accesses and using prefix-sum computations to resolve conflicts in parallel. Advanced emulation theorems, including those building on Cole's parallel merging techniques, achieve O(log p / log log p) time per step for simulating CRCW on EREW PRAM with p processors, by hierarchically grouping processors and accesses to minimize contention. These methods ensure work-efficient emulation, preserving the PRAM algorithm's total work while distributing resolution tasks across host processors. Tools and frameworks for PRAM simulation are typically abstract software implementations independent of specific hardware, such as the PRAMsim sequential simulator in the parallel programming environment, which supports SB-PRAM (strong Byzantine fault-tolerant variant) emulation through round-robin processing and parallel extensions like C-PRAMsim for shared-memory hosts. In C++, libraries like the Oxford BSP Toolset provide PRAM simulators that map PRAM instructions to executions, enabling succinct PRAM-like programming for algorithm prototyping. Python-based frameworks, while less specialized, can implement custom PRAM emulators using libraries like for vectorized memory operations or for coarse-grained parallelism, though they often trade performance for ease of use in educational settings. Limitations of these techniques include growing overhead with increasing processor count p and memory contention levels, as conflict resolution via sorting or tree operations scales logarithmically but accumulates to dominate simulation time for dense concurrent accesses, rendering them unsuitable for large-scale or real-time computations beyond theoretical validation. For instance, simulations of algorithms with high concurrency, such as parallel prefix computations, may exhibit slowdowns exceeding an on sequential hosts due to fine-grained needs.

Real-World Approximations

Shared-memory multiprocessors, such as multi-core CPUs, provide practical approximations of the Concurrent Read, Exclusive Write () PRAM variant through hardware mechanisms that maintain data consistency across processors. protocols like MESI (Modified, Exclusive, Shared, Invalid) ensure that multiple cores can read from concurrently while serializing writes to avoid conflicts, mimicking CREW behavior at a hardware level. However, these systems deviate from ideal PRAM assumptions due to (NUMA) architectures, where latency for remote memory accesses can be 50-100% higher than local ones, depending on the system architecture, introducing delays not present in the uniform-access PRAM model. Graphics processing units (GPUs) approximate PRAM concepts through programming models like NVIDIA's or , which enable SIMD-style parallel execution resembling exclusive-read variants, while atomic operations simulate Concurrent Read, Concurrent Write (CRCW) behavior for updates. In , atomic functions such as atomicAdd allow multiple threads to perform concurrent writes to the same location, resolving conflicts by serializing operations and selecting a "winner" thread based on execution order, though this incurs contention slowdowns under high parallelism. These approximations draw inspiration from CRCW PRAM variants, enabling efficient implementation of algorithms like on GPUs, but performance degrades with increasing thread contention compared to the idealized unit-time writes of PRAM. Recent work as of 2023 has developed practical GPU algorithms inspired by PRAM models for tasks like large-scale polygon clipping, demonstrating continued application in modern hardware. A simple example of PRAM-inspired in a real-world setting is the parallel computation of a sum using on multi-core CPUs, where a reduction handles concurrent reads and exclusive accumulation to avoid race conditions:

c

#include <omp.h> double sum = 0.0; #pragma omp parallel for reduction(+:sum) for (int i = 0; i < n; i++) { sum += array[i]; }

#include <omp.h> double sum = 0.0; #pragma omp parallel for reduction(+:sum) for (int i = 0; i < n; i++) { sum += array[i]; }

This directive approximates CREW-style access by privatizing local computations and merging results atomically at the end, ensuring correctness across threads. Despite these advancements, approximating PRAM in modern hardware faces significant challenges, including non-uniform memory access times that amplify latency in NUMA systems and limited atomicity, where operations are not truly concurrent but serialized, leading to scalability bottlenecks for fine-grained parallelism. As a result, PRAM serves primarily as an inspirational theoretical framework rather than a directly implementable model, requiring algorithmic adaptations to account for hardware constraints like contention and overheads.

References

  1. https://dl.acm.org/doi/pdf/10.1145/800133.804339
  2. https://homes.cs.washington.edu/~arvind/cs424/readings/pram.pdf
  3. https://web.njit.edu/~alexg/courses/cis485/S1999/l2-485.pdf
  4. https://dl.acm.org/doi/fullHtml/10.1145/3458744.3474041
  5. https://www.cs.cornell.edu/courses/cs6820/2022fa/Handouts/NC.pdf
  6. https://dl.acm.org/doi/10.1145/800133.804339
  7. https://www.csd.uwo.ca/~mmorenom/HPC-Slides/The_PRAM_model.pdf
  8. http://www.cs.cmu.edu/~bryantl/VCL_TR06.pdf
  9. https://dl.acm.org/doi/10.1145/176979.176984
  10. https://www.cs.unc.edu/~prins/Classes/633/Readings/pram.pdf
  11. https://www.cs.rice.edu/~vs3/comp422/lecture-notes/comp422-lec20-s08-v1.pdf
  12. https://dl.acm.org/doi/10.1145/800222.806745
  13. https://www.cs.umd.edu/~gasarch/TOPICS/ramsey/parasearch.pdf
  14. https://epubs.siam.org/doi/10.1137/0214051
  15. https://web.eecs.umich.edu/~qstout/abs/IEEETC88a.html
  16. https://dl.acm.org/doi/10.1145/195058.195202
  17. https://ranger.uta.edu/~weems/NOTES4351/harris.pdf
  18. https://www.cs.umd.edu/class/fall2019/cmsc714/readings/Grama-isoefficiency.pdf
  19. https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf
  20. https://www.cs.cmu.edu/~guyb/paralg/papers/Cole88.pdf
  21. https://www.cs.unc.edu/~prins/Classes/633/Slides/05-pram4.pdf
  22. https://pages.cs.wisc.edu/~tvrdik/2/html/Section2.html
  23. https://www.fernuni-hagen.de/pv/docs/97-08/ppramsim_1_.pdf
  24. https://ieeexplore.ieee.org/document/647194/
  25. https://stackoverflow.com/questions/5922883/pram-pararell-random-access-machine-simulator
  26. https://www.sciencedirect.com/science/article/pii/S0022000010000966
  27. https://developer.arm.com/documentation/den0013/latest/Multi-core-processors/Cache-coherency/MESI-and-MOESI-protocols
  28. https://queue.acm.org/detail.cfm?id=2852078
  29. https://www.umiacs.umd.edu/users/vishkin/XMT/ICPP08version.pdf
  30. https://www.osti.gov/servlets/purl/1856720
  31. https://www.researchgate.net/publication/372262143_Efficient_PRAM_and_Practical_GPU_Algorithms_for_Large_Polygon_Clipping_with_Degenerate_Cases
  32. https://extremecomputingtraining.anl.gov/wp-content/uploads/sites/96/2022/11/ATPESC-2022-Track-2a-Talk-1-Mattson-openmp.pdf
  33. http://www.ijnc.org/index.php/ijnc/article/viewFile/11/8
Add your contribution
Related Hubs
User Avatar
No comments yet.