notes.pdf

Bernstein’s Conditions Bernstein’s conditions are a set of conditions which must exist if two processes can execute in parallel. Notation Ii is the set of all input variables for a process Pi. Ii is also called the read set or domain of Pi. Oi is the set of all output variables for a process Pi.Oi i...

Bernstein’s Conditions Bernstein’s conditions are a set of conditions which must exist if two processes can execute in parallel. Notation Ii is the set of all input variables for a process Pi. Ii is also called the read set or domain of Pi. Oi is the set of all output variables for a process Pi.Oi is also called write set. If P1 and P2 can execute in parallel (which is written as P1 || P2) then we should have-: In terms of data dependencies, Bernstein’s conditions imply that two processes can execute in parallel if they are flow-independent, antiindependent, and output-independent. The parallelism relation || is commutative (Pi || Pj implies Pj || Pi ), but not transitive (Pi || Pj and Pj || Pk does not imply Pi || Pk ) Implicit parallelism is simpler for the programmer but provides less control over how parallelism is achieved. It is often used in environments where automatic parallelization is sufficient, such as high-level programming languages or hardware that supports parallel execution. Explicit parallelism requires more effort from the programmer but offers the potential for better performance and resource management. It is useful in scenarios where fine-tuning and control over parallel execution are critical for performance optimization. Network Topologies: Bisection Bandwidth and Diameter Let's first define the key metrics before calculating them for each of the topologies: Bisection Bandwidth: This is the minimum number of links (communication channels) that must be cut to divide the network into two equal halves. It gives an idea of how much data can flow between the two largest sections of the network. Diameter: This is the longest shortest path between any two nodes in the network. It indicates the worst-case communication delay in the network. 1. Array (Linear Array) Topology: In an array (or linear array) topology, processors are arranged in a single line, and each processor is connected to its immediate neighbors. Bisection Bandwidth: The array can be bisected by cutting a single link, as there’s only one connection between any two adjacent nodes. Bisection Bandwidth = 1 (since cutting one link separates the array into two equal halves). Diameter: The diameter of a linear array with PPP processors is the distance between the two processors at the ends of the array. Diameter = P - 1 (the distance from one end to the other). 2. Mesh (2D) Topology: In a 2D mesh, processors are arranged in a grid, and each processor is connected to its adjacent processors (north, south, east, and west neighbors). Bisection Bandwidth: To bisect a P×P\sqrt{P} \times \sqrt{P}P​×P​2D mesh (assuming PPP processors), we need to cut the vertical or horizontal links that cross the middle of the grid. The bisection bandwidth is proportional to the number of links cut, which equals the number of processors on one side of the cut. Bisection Bandwidth = P\sqrt{P}P​(the number of links along one side of the mesh). Diameter: The diameter of a 2D mesh is the longest distance between any two nodes, which is the sum of the distances across the width and height of the grid. Diameter = 2 \times (\sqrt{P} - 1). 3. Tree  Topology: In a tree topology, processors are arranged in a hierarchical structure. Each node (except the root and leaves) is connected to one parent and a number of children. Bisection Bandwidth: The tree can be bisected by cutting the link at the middle level (near the root). The number of links cut is proportional to the number of links between the two halves of the tree. For a balanced binary tree, the bisection bandwidth is 1 (cutting one link divides the tree into two halves). Diameter: The diameter of a balanced binary tree with PPP processors is the distance from one leaf to another leaf through the root. Diameter = 2 \times \log_2(P) (for a binary tree). 4. Hypercube Topology: A hypercube is a network where each node has connections to other nodes based on binary representations of their IDs. A ddd-dimensional hypercube has 2d2^d2d nodes, and each node is connected to ddd other nodes. Bisection Bandwidth: The hypercube can be bisected by cutting 2d−12^{d-1}2d−1 links, where ddd is the dimension of the hypercube. This is because a hypercube of dimension ddd has 2d−12^{d-1}2d−1 links connecting two equal halves. Bisection Bandwidth = 2d−12^{d-1}2d−1, where P=2dP = 2^dP=2d. Diameter: The diameter of a hypercube is the minimum number of hops between the two farthest nodes, which is equal to the dimension ddd. Diameter = \log_2(P) (since the distance between any two nodes is at most the number of differing bits in their binary representations). Cost: Array: Has the lowest cost in terms of links, but also the lowest bisection bandwidth and highest diameter. Mesh: Offers better bisection bandwidth than the array and lower diameter, but requires more links, especially in large grids. Tree: The cost is low, but the bisection bandwidth is poor. Trees are great for broadcasting but not efficient for high-volume communication. Hypercube: Has the highest cost (in terms of the number of links), but it also offers the best bisection bandwidth and the smallest diameter, making it highly scalable and efficient for parallel applications. Performance: Array: Due to its poor bisection bandwidth and large diameter, it is only suitable for applications with limited communication requirements. Mesh: Offers a balance between cost and performance, suitable for applications with moderate communication demands. Tree: Performs well for applications that rely on hierarchical communication (e.g., aggregation, broadcast), but for general communication, its bisection bandwidth is a bottleneck. Hypercube: Provides the best performance due to its high bisection bandwidth and small diameter, making it ideal for communication-intensive parallel applications. Which Network is Better in Cost and Performance Trade-Off? Mesh: For many practical applications, a 2D or 3D mesh offers a good balance between cost and performance. It is widely used in multiprocessor systems due to its relatively low complexity and decent communication performance. Hypercube: If performance is the top priority and the application involves heavy inter-processor communication, a hypercube is the best choice despite its higher cost in terms of links and connections. UMA (Uniform Memory Access), NUMA (Non-Uniform Memory Access), and COMA (Cache-Only Memory Architecture) are different memory architectures used in multiprocessor systems. The primary difference between these architectures lies in how they organize memory and how memory is accessed by processors. Here’s a detailed comparison of each architecture with examples: 1. UMA (Uniform Memory Access) Definition: In UMA systems, all processors share a single, unified memory with uniform access time. This means that the time it takes for any processor to access any memory location is the same, regardless of where the memory or processor is located. Key Characteristics: Memory access time is uniform for all processors. A single, global memory is used, and all processors have equal access to it. Used primarily in SMP (Symmetric Multiprocessing) systems, where all processors share the same physical memory and have equal access rights. Typically used in systems with a small number of processors due to memory access contention. Example:  A multicore desktop computer where all cores (processors) share the same physical RAM. In such a system, any core can access any part of the memory in the same amount of time. Advantages: Simple to program and manage. Good for systems with a small number of processors. Disadvantages: Scalability is limited due to contention on the shared memory bus. As the number of processors increases, the memory access bandwidth can become a bottleneck. 2. NUMA (Non-Uniform Memory Access) Definition: In NUMA systems, memory is physically distributed across multiple nodes, and memory access times are non-uniform. Each processor has faster access to its local memory and slower access to remote memory (memory local to another processor or node). Key Characteristics: Memory is divided into local and remote memory, with processors accessing local memory faster than remote memory. Reduces memory access contention because each processor can primarily use its own local memory. Common in large-scale multiprocessor systems (e.g., many-core servers, high-performance computing systems). Uses a NUMA-aware operating system to optimize memory access patterns (e.g., Linux with NUMA support). Example: A high-performance server with multiple processor sockets. Each socket has its own memory bank, but all the sockets (processors) can access any memory location, with local memory being faster than remote memory. For instance, in a 4-socket server, each socket might have direct access to its own 32 GB of memory with very low latency, but accessing another socket’s memory will take longer due to the need to go through the interconnect (e.g., via Intel’s QPI or AMD’s Infinity Fabric). Advantages: Scalable for large systems with many processors. Local memory access is faster, improving performance for memory-bound applications. Disadvantages: Programming complexity: Developers need to be aware of memory locality to maximize performance, especially for workloads that frequently access remote memory. Non-uniform memory access can introduce latency issues if data is not well-localized to the processors. 3. COMA (Cache-Only Memory Architecture) Definition: In COMA systems, there is no distinct main memory. Instead, all memory is treated as a large cache. Data is dynamically moved and stored in the cache of the processor that needs it, and memory accesses are essentially cache accesses. Key Characteristics: No fixed main memory for any processor; all memory acts as a cache. The system is designed to automatically move data to where it is needed, dynamically balancing memory usage across processors. Each processor has a large local cache, and memory coherence protocols ensure that data is synchronized across caches. Good for applications with unpredictable memory access patterns because the system dynamically adapts to where the data is needed. Example: KSR1 (Kendall Square Research) was one of the early systems that implemented COMA. It treated all memory as a large, shared cache, and data was moved to where it was needed. In a COMA system, if processor P1P1P1 needs data stored in memory near processor P2P2P2, the data will be automatically moved to P1P1P1’s cache. This way, processors essentially only work with cache, and the system dynamically manages data placement. Advantages: High flexibility: Data dynamically migrates to where it is needed, reducing remote memory access times. Good for applications where the memory access pattern is irregular or difficult to predict. Disadvantages: Complex hardware and memory management. Cache coherence management is critical to ensure that all processors see the most recent data, which can introduce overhead.