Community Hub0 Subscribers
Community hub
Parallel programming model
View on Wikipediafrom Wikipedia
In computing, a parallel programming model is an abstraction of parallel computer architecture, with which it is convenient to express algorithms and their composition in programs. The value of a programming model can be judged on its generality: how well a range of different problems can be expressed for a variety of different architectures, and its performance: how efficiently the compiled programs can execute.[1] The implementation of a parallel programming model can take the form of a library invoked from a programming language, as an extension to an existing languages.
Consensus around a particular programming model is important because it leads to different parallel computers being built with support for the model, thereby facilitating portability of software. In this sense, programming models are referred to as bridging between hardware and software.[2]
Classification of parallel programming models
[edit]Classifications of parallel programming models can be divided broadly into two areas: process interaction and problem decomposition.[3][4][5]
Process interaction
[edit]Process interaction relates to the mechanisms by which parallel processes are able to communicate with each other. The most common forms of interaction are shared memory and message passing, but interaction can also be implicit (invisible to the programmer).
Shared memory
[edit]Shared memory is an efficient means of passing data between processes. In a shared-memory model, parallel processes share a global address space that they read and write to asynchronously. Asynchronous concurrent access can lead to race conditions, and mechanisms such as locks, semaphores and monitors can be used to avoid these. Conventional multi-core processors directly support shared memory, which many parallel programming languages and libraries, such as Cilk, OpenMP and Threading Building Blocks, are designed to exploit.
Message passing
[edit]In a message-passing model, parallel processes exchange data through passing messages to one another. These communications can be asynchronous, where a message can be sent before the receiver is ready, or synchronous, where the receiver must be ready. The Communicating sequential processes (CSP) formalisation of message passing uses synchronous communication channels to connect processes, and led to important languages such as Occam, Limbo and Go. In contrast, the actor model uses asynchronous message passing and has been employed in the design of languages such as D, Scala and SALSA.
Partitioned global address space
[edit]Partitioned Global Address Space (PGAS) models provide a middle ground between shared memory and message passing. PGAS provides a global memory address space abstraction that is logically partitioned, where a portion is local to each process. Parallel processes communicate by asynchronously performing operations (e.g. reads and writes) on the global address space, in a manner reminiscent of shared memory models. However by semantically partitioning the global address space into portions with affinity to a particular processes, they allow programmers to exploit locality of reference and enable efficient implementation on distributed memory parallel computers. PGAS is offered by many parallel programming languages and libraries, such as Fortran 2008, Chapel, UPC++, and SHMEM.
Implicit interaction
[edit]In an implicit model, no process interaction is visible to the programmer and instead the compiler and/or runtime is responsible for performing it. Two examples of implicit parallelism are with domain-specific languages where the concurrency within high-level operations is prescribed, and with functional programming languages because the absence of side-effects allows non-dependent functions to be executed in parallel.[6] However, this kind of parallelism is difficult to manage[7] and functional languages such as Concurrent Haskell and Concurrent ML provide features to manage parallelism explicitly and correctly.
Problem decomposition
[edit]A parallel program is composed of simultaneously executing processes. Problem decomposition relates to the way in which the constituent processes are formulated.[8][5]
Task parallelism
[edit]A task-parallel model focuses on processes, or threads of execution. These processes will often be behaviourally distinct, which emphasises the need for communication. Task parallelism is a natural way to express message-passing communication. In Flynn's taxonomy, task parallelism is usually classified as MIMD/MPMD or MISD.
Data parallelism
[edit]A data-parallel model focuses on performing operations on a data set, typically a regularly structured array. A set of tasks will operate on this data, but independently on disjoint partitions. In Flynn's taxonomy, data parallelism is usually classified as MIMD/SPMD or SIMD.
Stream Parallelism
[edit]Stream parallelism, also known as pipeline parallelism, focuses on dividing a computation into a sequence of stages, where each stage processes a portion of the input data. Each stage operates independently and concurrently, and the output of one stage serves as the input to the next stage. Stream parallelism is particularly suitable for applications with continuous data streams or pipelined computations.
Implicit parallelism
[edit]As with implicit process interaction, an implicit model of parallelism reveals nothing to the programmer as the compiler, the runtime or the hardware is responsible. For example, in compilers, automatic parallelization is the process of converting sequential code into parallel code, and in computer architecture, superscalar execution is a mechanism whereby instruction-level parallelism is exploited to perform operations in parallel.
Terminology
[edit]Parallel programming models are closely related to models of computation. A model of parallel computation is an abstraction used to analyze the cost of computational processes, but it does not necessarily need to be practical, in that it can be implemented efficiently in hardware and/or software. A programming model, in contrast, does specifically imply the practical considerations of hardware and software implementation.[9]
A parallel programming language may be based on one or a combination of programming models. For example, High Performance Fortran is based on shared-memory interactions and data-parallel problem decomposition, and Go provides mechanism for shared-memory and message-passing interaction.
Example parallel programming models
[edit]| Name | Class of interaction | Class of decomposition | Example implementations |
|---|---|---|---|
| Actor model | Asynchronous message passing | Task | D, Erlang, Scala, SALSA |
| Bulk synchronous parallel | Shared memory | Task | Apache Giraph, Apache Hama, BSPlib |
| Communicating sequential processes | Synchronous message passing | Task | Ada, Occam, VerilogCSP, Go |
| Circuits | Message passing | Task | Verilog, VHDL |
| Dataflow | Message passing | Task | Lustre, TensorFlow, Apache Flink |
| Functional | Message passing | Task | Concurrent Haskell, Concurrent ML |
| LogP machine | Synchronous message passing | Not specified | None |
| Parallel random access machine | Shared memory | Data | Cilk, CUDA, OpenMP, Threading Building Blocks, XMTC |
| SPMD PGAS | Partitioned global address space | Data | Fortran 2008, Unified Parallel C, UPC++, SHMEM |
| Global-view Task parallelism | Partitioned global address space | Task | Chapel, X10 |
See also
[edit]References
[edit]- ^ Skillicorn, David B., "Models for practical parallel computation", International Journal of Parallel Programming, 20.2 133–158 (1991), https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf
- ^ Leslie G. Valiant, "A bridging model for parallel computation", Communications of the ACM, Volume 33, Issue 8, August, 1990, pages 103–111.
- ^ John E. Savage, Models of Computation: Exploring the Power of Computing, 2008, Chapter 7 (Parallel Computation), https://cs.brown.edu/~jes/book/ Archived 2016-11-05 at the Wayback Machine
- ^ "1.3 A Parallel Programming Model". www.mcs.anl.gov. Retrieved 2024-03-21.
- ^ a b "Introduction to Parallel Computing Tutorial | HPC @ LLNL". hpc.llnl.gov. Retrieved 2024-03-21.
- ^ Hammond, Kevin. Parallel functional programming: An introduction. In International Symposium on Parallel Symbolic Computation, p. 46. 1994.
- ^ McBurney, D. L., and M. Ronan Sleep. "Transputer-based experiments with the ZAPP architecture." PARLE Parallel Architectures and Languages Europe. Springer Berlin Heidelberg, 1987.
- ^ "2.2 Partitioning". www.mcs.anl.gov. Retrieved 2024-03-21.
- ^ Skillicorn, David B., and Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys, 30.2 123–169 (1998), https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ModelsOfParallelComputation-Skillicorn.pdf
Further reading
[edit]- Blaise Barney, Introduction to Parallel Computing, Lawrence Livermore National Laboratory, archived from the original on 2013-06-10, retrieved 2015-11-22
- Murray I. Cole., Algorithmic Skeletons: Structured Management of Parallel Computation (PDF), University of Glasgow
- J. Darlinton; M. Ghanem; H. W. To (1993). "Structured parallel programming". Proceedings of Workshop on Programming Models for Massively Parallel Computers. pp. 160–169. doi:10.1109/PMMP.1993.315543. ISBN 0-8186-4900-3. S2CID 15265646.
- Ian Foster, Designing and Building Parallel Programs, Argonne National Laboratory
| General | |
|---|---|
| Levels | |
| Multithreading | |
| Theory | |
| Elements | |
| Coordination | |
| Programming | |
| Hardware | |
| APIs | |
| Problems | |
Parallel programming model
View on Grokipediafrom Grokipedia
Fundamentals
Definition and Scope
A parallel programming model is an abstraction that defines how computational tasks are divided into concurrent subtasks, coordinated for synchronization and communication, and executed across multiple processing units to achieve faster problem-solving or greater scalability compared to sequential approaches.[5] This model serves as a bridge between application logic and underlying hardware, enabling developers to express parallelism without directly managing low-level details such as thread scheduling or memory allocation.[6] The scope of parallel programming models spans multiple abstraction levels, from hardware architectures like multi-core CPUs and distributed clusters to software interfaces such as APIs (e.g., OpenMP for shared-memory parallelism) and high-level languages (e.g., Chapel for productivity-oriented parallel coding).[6][7] These models emphasize scalability, particularly in distributed systems where tasks may run on thousands of nodes connected via networks like InfiniBand, allowing applications to handle larger datasets or more complex computations by leveraging increased resources.[6] Parallel programming models enable significant performance benefits, including reduced execution time, as quantified by Amdahl's law, which describes the theoretical speedup limit for a fixed-size problem when parallelized across p processors with a serial fraction f. The speedup S is given bywhere the serial portion f (0 ≤ f ≤ 1) bottlenecks overall gains, even as p grows large; for example, if f = 0.05, S approaches 20 but never exceeds it regardless of p.[8] For scaled problems where problem size increases with available processors, Gustafson's law provides a complementary perspective, showing that efficiency remains high since the parallelizable portion dominates, thus supporting near-linear speedup in many real-world scenarios like scientific simulations.[9] While parallel programming models abstract concurrency, they are distinct from underlying hardware architectures, such as those classified by Flynn's taxonomy into SIMD (single instruction, multiple data streams, e.g., vector processors) and MIMD (multiple instructions, multiple data streams, e.g., multicore systems), which influence model selection but do not dictate implementation details.
Historical Evolution
The roots of parallel programming models trace back to the 1960s, when early efforts in high-performance computing introduced concepts of vector processing and massively parallel architectures as precursors to structured programming paradigms. Vector processors, exemplified by the CDC 6600 supercomputer introduced in 1964, enabled pipelined operations on arrays of data, laying groundwork for SIMD-style parallelism by processing multiple elements simultaneously through hardware instructions.[10] Concurrently, the ILLIAC IV project, initiated in the mid-1960s and becoming operational in 1975, represented one of the first attempts at large-scale parallel computation with up to 256 processing elements organized in a SIMD array, though its programming complexity highlighted early challenges in model design.[11] A foundational contribution came from Michael J. Flynn's 1966 taxonomy, which classified computer architectures into SISD, SIMD, MISD, and MIMD categories based on instruction and data stream multiplicity, providing a theoretical framework that directly influenced the development of subsequent parallel models. The 1980s and 1990s marked the maturation of practical parallel programming models, driven by the proliferation of distributed and shared-memory systems in supercomputing. Shared-memory approaches gained traction with the standardization of POSIX threads (pthreads) in 1995, which provided a portable API for multithreaded programming on symmetric multiprocessors, enabling lightweight task creation and synchronization within a unified address space. In parallel, message-passing models emerged to address distributed-memory architectures, with the Parallel Virtual Machine (PVM) developed in 1989 by Oak Ridge National Laboratory as an early portable library for heterogeneous clusters, facilitating explicit communication via send-receive primitives, and first publicly released in 1991. This was followed by the Message Passing Interface (MPI) standard, formalized in 1994 by the MPI Forum (with roots in 1992 discussions), which became the de facto model for high-performance computing by offering robust collective operations and point-to-point messaging across scalable clusters. Entering the 2000s, parallel programming models adapted to new hardware trends, including GPUs and hybrid systems, while addressing the shift from uniprocessor dominance to ubiquitous multicore processors as of the mid-2000s, prompted by power and thermal constraints that ended traditional clock-speed scaling—a trend that has continued with processors scaling to hundreds of cores into the 2020s, such as AMD's EPYC series reaching 192 cores in 2024. NVIDIA's CUDA framework, launched in 2006, revolutionized GPU computing by introducing a single-instruction multiple-thread (SIMT) model, allowing programmers to write kernels that exploit thousands of cores for data-parallel tasks like scientific simulations and graphics rendering. Hybrid models evolved with OpenMP, first specified in 1997 for shared-memory directives but extended in subsequent versions (e.g., 3.0 in 2008) to support task-based parallelism and accelerators, bridging directive-based simplicity with multicore and heterogeneous environments. The Partitioned Global Address Space (PGAS) paradigm gained prominence through Unified Parallel C (UPC) in 1999, sponsored by DARPA, which enabled one-sided communication in a global address space divided among nodes, and IBM's X10 language released in 2004, which integrated PGAS with object-oriented features for distributed place-based programming. These developments were propelled by broader shifts, including the multicore era post-2005, where processors like Intel's Core Duo emphasized thread-level parallelism to sustain performance gains amid Dennard scaling's collapse. The rise of big data and AI further drove innovations, such as Apache Spark in 2010 from UC Berkeley's AMPLab, which introduced resilient distributed datasets (RDDs) for fault-tolerant data parallelism across clusters, unifying batch, streaming, and iterative workloads in a higher-level abstraction over distributed frameworks.[12] Underpinning these evolutions were challenges from Moore's Law slowdown around 2005, which reduced transistor density improvements and led to "dark silicon"—unused chip areas due to power budgets—necessitating energy-efficient parallel models that prioritize sparsity, locality, and heterogeneous acceleration to maximize utilization without excessive dissipation. Subsequent decades saw further maturation to support exascale computing and diverse workloads. OpenMP advanced with version 4.0 in 2013 adding accelerator offload, 5.0 in 2018 introducing taskloop and SIMD directives, and 6.0 in November 2024 enhancing AI/ML integrations like loop transformations. MPI progressed through 3.0 (2012) with non-blocking collectives and 4.0 (2021) improving fault tolerance and dynamic processes. Exascale systems, such as the U.S. DOE's Frontier supercomputer achieving 1.1 exaFLOPS in 2022, relied on hybrid models combining MPI for inter-node and OpenMP for intra-node parallelism, alongside PGAS languages like Chapel (stable release 2009 onward). Emerging paradigms addressed heterogeneous accelerators and AI, with task-based models in libraries like Intel oneAPI (2020) and Legion/DIMMA (2010s) enabling asynchronous execution for irregular workloads.[13][14][15]Classifications
Interaction Paradigms
Interaction paradigms in parallel programming models refer to the mechanisms by which processes or threads communicate, coordinate, and share data during execution. These paradigms define how parallelism is expressed and managed at the level of inter-process interactions, influencing both programmer productivity and system performance. Common paradigms include shared memory, message passing, partitioned global address space (PGAS), and implicit interaction, each offering distinct approaches to handling concurrency and data access in multiprocessor environments.[16][17] In the shared memory paradigm, multiple processes or threads access a common address space, allowing direct reads and writes to shared variables without explicit data transfer. This model simplifies programming by enabling straightforward data sharing, particularly for complex data structures like graphs or trees, as references can be passed among threads with minimal overhead. However, it introduces challenges such as cache coherence overhead, where maintaining consistent views of shared data across processors requires protocol enforcement, potentially leading to performance bottlenecks in large-scale systems. To ensure safe access, mechanisms like mutexes are commonly used for mutual exclusion, preventing concurrent modifications to critical sections.[18][19][20] The message passing paradigm relies on explicit communication primitives, such as send and receive operations, to exchange data between processes that do not share a memory space. This approach is particularly suited to distributed systems, like clusters of independent machines, where processes operate in isolated address spaces and coordinate solely through messages. Message passing supports both synchronous modes, where sender and receiver rendezvous before proceeding, and asynchronous modes, allowing non-blocking sends and receives for better overlap of computation and communication. Additionally, collective operations, such as broadcasts or reductions involving multiple processes, enable efficient group communications, as standardized in libraries like MPI.[20][21][22] The partitioned global address space (PGAS) paradigm offers a hybrid model, providing each process with a local, fast-access memory region while exposing a global address space for remote access. This design promotes data locality by assigning ownership of data partitions to specific processes, reducing unnecessary data movement and improving performance on heterogeneous architectures. PGAS facilitates one-sided communication, where a process can directly read from or write to another process's memory without involving the remote process in synchronization, enhancing expressiveness for irregular data access patterns. Languages like UPC and Chapel exemplify this model, balancing the ease of shared memory with the control of explicit messaging.[16][23][24] Implicit interaction paradigms abstract communication and coordination from the programmer, relying on runtime systems or compilers to manage parallelism automatically. In these models, the developer writes sequential-like code, and the system infers and enforces parallel execution, often through techniques like automatic thread scheduling or speculative execution. A prominent example is software transactional memory (STM), introduced in 1995, which treats groups of operations as atomic transactions; conflicts are detected at runtime, and transactions are rolled back and retried without explicit locks. This approach simplifies concurrent programming for dynamic data structures but may incur overhead from conflict resolution.[25][26] Comparing these paradigms reveals key trade-offs in scalability and fault tolerance. Shared memory excels in symmetric multiprocessor (SMP) environments due to its programming simplicity but scales poorly beyond a few processors because of contention and coherence costs. Message passing supports better scalability on large clusters by avoiding shared state, though it requires more explicit effort from programmers. PGAS bridges these by offering scalable data distribution with global visibility, while implicit models like STM enhance productivity at the cost of potential runtime overheads. Regarding fault tolerance, message passing inherently supports distributed recovery through isolated processes, whereas shared memory models often assume reliable hardware and struggle with node failures due to centralized state.[20][27]Decomposition Strategies
Decomposition strategies in parallel programming models refer to the methods used to partition a computational problem into concurrent subtasks or data portions, enabling efficient workload distribution across processing units. These strategies determine the granularity of parallelism—ranging from fine-grained (many small tasks) to coarse-grained (fewer larger tasks)—and influence load balancing, scalability, and suitability for specific problem types. Key approaches include task parallelism, data parallelism, stream parallelism, implicit parallelism, and hybrid combinations, each tailored to exploit concurrency in different ways.[28] Task parallelism decomposes a problem into independent tasks that may vary in computational intensity and execution time, allowing dynamic assignment to processors for better load balancing. This strategy is particularly effective for irregular workloads where task dependencies form dynamic graphs, such as in tree traversals or recursive algorithms. Dynamic scheduling techniques, like work-stealing, enable idle processors to "steal" tasks from busy ones, minimizing synchronization overhead and achieving near-optimal load balance. For instance, in the Cilk system, work-stealing schedulers have demonstrated efficient handling of fully strict multithreaded computations on parallel machines, with theoretical guarantees of linear speedup for balanced workloads.[29][30] Data parallelism focuses on dividing data into partitions and applying identical operations across them simultaneously, often resembling single instruction multiple data (SIMD) execution. Partitioning strategies include block decomposition, where contiguous data chunks are assigned to processors, which suits problems with uniform access patterns but can lead to load imbalances if computation varies; cyclic decomposition, distributing data in a round-robin fashion to even out irregular workloads; and block-cyclic, combining both for improved balance in matrix operations or simulations. These methods ensure scalability in regular, data-intensive applications like numerical simulations, with cyclic approaches particularly reducing variance in execution times for non-uniform data. For example, in parallel matrix multiplication, block partitioning minimizes data movement while cyclic variants balance computation across processors with differing loads.[31][32] Stream parallelism organizes computation as a pipeline where data flows through stages, each handled by a separate processing unit in a consumer-producer manner, enabling continuous overlap of operations. This model excels in applications with sequential dependencies but high throughput needs, such as signal processing or multimedia encoding, where stages process unbounded data streams asynchronously. In GPUs, stream parallelism supports pipelined execution of kernels on data batches, allowing multiple stages to run concurrently for latency hiding. Seminal work on on-the-fly pipeline parallelism has shown its efficacy in organizing linear sequences of stages, achieving high utilization in stream-based computations without excessive buffering.[33][6] Implicit parallelism relies on compilers or runtimes to automatically detect and extract concurrent executable regions from sequential code, reducing programmer burden but requiring sophisticated analysis. A classic example is parallelizing independent loop iterations in Fortran using DOALL constructs, where the compiler identifies loops free of data dependencies to distribute across processors. Challenges include accurate dependence analysis to avoid false serialization, privatization of scalar variables, and handling reductions, which can limit extraction to about 10-20% of loops in real codes without transformations. Loop transformation techniques, such as those maximizing DOALL loops through index set splitting, have been pivotal in uncovering hidden parallelism in nested loops for scientific computing.[34][35] Hybrid approaches integrate multiple decomposition strategies to address complex applications requiring both task and data concurrency at varying granularities, often combining fine-grained (e.g., loop-level) and coarse-grained (e.g., function-level) parallelism. For instance, data parallelism within tasks can optimize inner loops, while task parallelism schedules outer dependencies, as seen in hybrid MPI-OpenMP models for distributed shared-memory systems. Fine-grained hybrids suit dense computations with low communication, achieving better cache locality, whereas coarse-grained ones reduce overhead in sparse or irregular problems. These combinations have enabled scalable performance in multi-level parallel environments, such as finite element simulations, by mapping coarse parallelism across nodes and fine within them.[28][36]Core Concepts
Synchronization Mechanisms
Synchronization mechanisms in parallel programming ensure that concurrent executions maintain data consistency and avoid undefined behaviors such as race conditions, by coordinating access to shared resources and controlling the order of operations across threads or processes. These primitives range from simple mutual exclusion tools to more sophisticated hardware-supported operations, each designed to balance correctness with performance in multi-threaded environments. Barriers provide global synchronization points where all participating threads must reach before any can proceed, effectively halting execution until the entire group arrives. This is crucial for phases of parallel computation where all threads need to complete their work before the next stage begins, such as in iterative algorithms. A common efficient implementation uses sense-reversing trees, where threads propagate flags up a tree structure and reverse a shared sense variable to signal completion, reducing contention and achieving logarithmic time complexity in the number of threads.[37][38] Locks and semaphores enforce mutual exclusion for critical sections, preventing multiple threads from simultaneously accessing shared data that could lead to inconsistencies. A lock, often implemented as a binary semaphore, allows only one thread to enter a protected region via acquire (lock) and release (unlock) operations; spinlocks repeatedly poll the lock in a busy-wait loop for low-latency scenarios, while blocking locks suspend the thread to save CPU cycles in longer waits. Semaphores generalize this to counting variants, supporting resource pools where the count represents available units, decremented on wait (P operation) and incremented on signal (V operation). Deadlock prevention in lock-based systems can employ strategies like the Banker's algorithm, which simulates resource allocation to ensure a safe sequence exists where all processes can complete without circular waits.[39][40] Condition variables facilitate signaling between threads, allowing one to wait until a specific condition holds true, typically used in conjunction with a mutex to protect the associated predicate. In the POSIX threads (pthreads) API, a thread calls pthread_cond_wait to atomically release the mutex and block until another thread invokes pthread_cond_signal or pthread_cond_broadcast to wake waiters, ensuring efficient notification without busy-waiting. This mechanism is foundational to higher-level constructs like monitors, enabling producer-consumer patterns where threads synchronize on shared queues.[41] Atomic operations and memory fences provide hardware-supported primitives for lock-free programming, allowing indivisible updates to shared variables without traditional locks. Atomics ensure operations like compare-and-swap (CAS) or fetch-and-add execute as single instructions, preventing interleaving that could corrupt data. Fences enforce memory ordering, such as acquire fences (preventing subsequent reads from moving before the fence) and release fences (preventing prior writes from moving after), to maintain visibility of changes across threads. Memory models define these guarantees; sequential consistency requires all threads to see operations in a total order, while relaxed models like total store order (TSO) in x86 allow optimizations for better performance at the cost of explicit fence usage. Advanced mechanisms include futures and promises for handling asynchronous computations, where a future represents a pending result that threads can query without blocking the entire program, and promises allow setting the value later to fulfill waiting dependents. This decouples task submission from result retrieval, improving parallelism in languages like C++ std::future. Transactional memory offers composable atomicity by executing blocks of code as transactions that either commit fully or abort on conflicts, using hardware support like cache coherence protocols to detect and resolve races without explicit locking.[42][43] Despite their utility, synchronization mechanisms introduce overheads like contention on shared primitives, which can degrade scalability in large systems with thousands of threads, as tree-based barriers or lock queues may bottleneck at root nodes or hot spots. Debugging race conditions remains challenging, often requiring tools like thread sanitizers to detect non-deterministic errors, while high-contention scenarios may necessitate adaptive strategies to switch between locking and lock-free approaches.[44]Performance Considerations
Performance in parallel programming models is evaluated using key metrics that quantify how effectively additional processing resources improve execution time and resource utilization. Speedup measures the reduction in execution time when using $ p $ processors compared to a single processor, with Amdahl's law highlighting the fundamental limit imposed by the serial fraction of the workload, where even small serial portions can cap overall gains. Gustafson's law extends this by considering scaled problem sizes, emphasizing that parallel fractions can yield near-linear speedups for larger workloads on more processors. Efficiency, defined as $ E = S / p $, where $ S $ is speedup, indicates the average utilization of processors, typically decreasing as $ p $ increases due to overheads. Scalability assesses how performance holds with growing processor counts; strong scaling maintains a fixed problem size while increasing processors, often revealing limits from communication and synchronization, whereas weak scaling proportionally increases problem size with processors to sustain efficiency. The isoefficiency function provides a deeper scalability analysis by determining the problem size required to maintain constant efficiency as $ p $ grows, particularly accounting for communication overhead in distributed models; for example, in algorithms with total communication cost proportional to $ p \log p $, the function scales as $ W = K p \log p $, where $ W $ is workload and $ K $ is a constant. Bottlenecks significantly impact these metrics, with communication latency and bandwidth being primary constraints in distributed systems. The LogP model captures this realistically through parameters including latency $ L $ (end-to-end delay for a message), overhead $ o $ (processor busy time sending/receiving), gap $ g $ (minimum time between consecutive sends/receives), and number of processors $ P $, enabling predictions of how network characteristics degrade speedup for communication-intensive tasks. Load imbalance, where processors complete work at uneven rates, exacerbates inefficiencies, while Amdahl's serial fraction amplifies the issue by forcing idle time during non-parallelizable phases, often reducing efficiency below 50% beyond moderate $ p $. Optimization strategies target these bottlenecks to enhance performance. Improving data locality minimizes data transfers between processors or memory levels, reducing communication costs in both shared- and distributed-memory models by aligning data access patterns with hardware topology. Profiling tools such as TAU (Tuning and Analysis Utilities), which supports instrumentation across multiple languages and systems for tracing events and metrics, and Intel VTune Profiler, offering hardware-level counters for CPU, memory, and I/O analysis, enable identification of hotspots and imbalances. In NUMA systems, hybrid scaling combines thread-level parallelism (e.g., OpenMP) within nodes with process-level (e.g., MPI) across nodes to optimize memory affinity and reduce remote access latencies. Energy and power considerations have gained prominence in parallel computing, especially for large-scale systems. Dynamic Voltage and Frequency Scaling (DVFS) adjusts processor voltage and frequency dynamically based on workload demands, reducing power consumption quadratically with frequency while preserving performance for parallel phases with variable intensity. Post-2010 trends in green computing for HPC emphasize energy proportionality, with initiatives like the Green500 list tracking efficiency in gigaflops per watt, showing steady improvements from accelerator integration and software optimizations, though full exascale systems still face challenges in balancing performance and power budgets. Standardized evaluations rely on benchmarks like the NAS Parallel Benchmarks, introduced in the 1990s to assess parallel kernel and application performance across architectures. Research has extended these benchmarks to evaluate exascale features such as heterogeneous computing and fault tolerance, measuring scalability under modern constraints.[45][46]Notable Implementations
Shared Memory Models
Shared memory models enable parallel execution by allowing multiple threads or processes within a single address space to access and modify common data structures, facilitating implicit communication through shared variables. These models are particularly suited for symmetric multiprocessing (SMP) systems and multicore processors, where low-latency access to unified memory simplifies programming compared to explicit message exchanges. Prominent implementations include directive-based approaches like OpenMP, low-level thread libraries such as POSIX Threads, language-integrated concurrency in Java, and higher-level abstractions like Intel Threading Building Blocks (TBB). While effective for exploiting intranode parallelism in high-performance computing (HPC) simulations and multicore applications, shared memory models face scalability limitations beyond a single node due to contention and coherence overheads in distributed environments.[47] OpenMP is a directive-based API for shared memory parallel programming in C, C++, and Fortran, using compiler pragmas to annotate sequential code for automatic parallelization. Key constructs include#pragma omp parallel for for distributing loop iterations across threads and #pragma omp sections for parallel execution of independent code blocks. Introduced in 1997, OpenMP evolved significantly with version 3.0 in May 2008, which added task constructs (#pragma omp task) to support dynamic, irregular workloads by deferring execution of independent units until resources are available.[13][48] Further advancements in version 6.0, released in November 2024, extend support to accelerators like GPUs through target directives (#pragma omp target), enabling offloading of computations to heterogeneous devices while managing data transfers implicitly, alongside features for easier parallel programming in new applications and finer-grained control.[13] In HPC simulations, such as computational fluid dynamics on multicore CPUs, OpenMP simplifies scaling to dozens of threads by handling synchronization via barriers and reductions, though NUMA effects can degrade performance on larger core counts.[47]
POSIX Threads (pthreads) provides a low-level, portable API defined in the POSIX.1-2001 standard for creating and managing threads in C programs on Unix-like systems. Core functions include pthread_create() to spawn a new thread with specified attributes and start routine, pthread_join() to wait for thread completion, and pthread_attr_init()/pthread_attr_setdetachstate() for configuring thread properties like stack size or detachment. A classic use case is the producer-consumer pattern, where a producer thread enqueues data into a shared buffer protected by a mutex (pthread_mutex_lock()) and condition variable (pthread_cond_wait()), while consumers dequeue items upon signaling (pthread_cond_signal()), ensuring thread-safe access to the shared queue. This API is widely used in multicore applications for fine-grained control, such as real-time data processing, but requires explicit synchronization to avoid race conditions, increasing programmer burden compared to higher-level models.[49]
Java's built-in threading support integrates shared memory concurrency directly into the language, with the Thread class extending java.lang.Thread for subclassing or implementing Runnable for task execution, and higher-level abstractions like ExecutorService from the java.util.concurrent package for managing thread pools via submit() and shutdown(). The Java Memory Model (JMM), formalized in JSR-133 and effective from Java 5.0 in 2004, defines visibility guarantees for shared variables, ensuring that writes to volatile fields are immediately visible to other threads and establishing happens-before relationships to prevent reordering issues.[50][51] For instance, in a multicore server application, an ExecutorService can parallelize tasks like image processing across cores, with volatile keywords ensuring consistent cache coherence without full synchronization overhead. This model excels in enterprise software on multicore systems but inherits shared memory limitations, such as potential deadlocks in distributed JVM setups.
Modern extensions like Intel Threading Building Blocks (TBB), first released in 2007 as a C++ template library, abstract shared memory parallelism through high-level patterns, avoiding low-level thread management. TBB supports flow graphs for modeling dataflow dependencies via graph, node, and edge connections, enabling asynchronous execution of task pipelines, and provides concurrent containers like concurrent_queue and concurrent_hash_map for lock-free or fine-grained locked access in multithreaded environments.[52] In HPC simulations on multicore CPUs, TBB's parallel_for and parallel_pipeline algorithms distribute workloads dynamically, achieving near-linear scaling up to hundreds of cores while adapting to load imbalances, though it remains confined to shared address spaces and less suitable for distributed clusters.