Parallel Computing MODULE-1 Sem 7

Parallel Computing (BCS702) Dr Sreeja Rajesh Associate Professor Dept. of IS&E Parallel Computing (BCS702) Course outcomes (Course Skill Set): At the end of the course, the student will be able to: 1. Explain the need for parallel programming 2. Demonstrate parallelism in MIMD system. 3. Apply MPI library to parallelize the code to solve the given problem. 4. Apply OpenMP pragma and directives to parallelize the code to solve the given problem 5. Design a CUDA program for the given problem. Syllabus: MODULE-1 Introduction to parallel programming, Parallel hardware and parallel software – Classifications of parallel computers, SIMD systems, MIMD systems, Interconnection networks, Cache coherence, Shared-memory vs. distributed-memory, Coordinating the processes/threads, Shared-memory, Distributed-memory. MODULE-2 GPU programming, Programming hybrid systems, MIMD systems, GPUs, Performance – Speedup and efficiency in MIMD systems, Amdahl’s law, Scalability in MIMD systems, Taking timings of MIMD programs, GPU performance. MODULE-3 Distributed memory programming with MPI – MPI functions, The trapezoidal rule in MPI, Dealing with I/O, Collective communication, MPI-derived datatypes, Performance evaluation of MPI programs, A parallel sorting algorithm. Syllabus: MODULE-4 Shared-memory programming with OpenMP – openmp pragmas and directives, The trapezoidal rule, Scope of variables, The reduction clause, loop carried dependency, scheduling, producers and consumers, Caches, cache coherence and false sharing in openmp, tasking, tasking, thread safety. MODULE-5 GPU programming with CUDA - GPUs and GPGPU, GPU architectures, Heterogeneous computing, Threads, blocks, and grids Nvidia compute capabilities and device architectures, Vector addition, Returning results from CUDA kernels, CUDA trapezoidal rule I, CUDA trapezoidal rule II: improving performance, CUDA trapezoidal rule III: blocks with more than one warp. Text-Books Textbook: 1. Peter S Pacheco, Matthew Malensek – An Introduction to Parallel Programming, second edition, Morgan Kauffman. 2. Michael J Quinn – Parallel Programming in C with MPI and OpenMp, McGrawHill. Module-1 Introduction to parallel programming, Parallel hardware and parallel software Classifications of parallel computers, SIMD systems, MIMD systems, Interconnection networks, Cache coherence, Sharedmemory vs. distributed-memory, Coordinating the processes/threads, Shared-memory, Distributed-memory. Introduction to parallel programming • Parallel programming is a computing technique that enables multiple computations to be carried out at the same time. • The central idea is to divide a problem into parts that can be solved concurrently, allowing programs to utilize multiple processors or cores simultaneously. • This is in contrast to traditional serial programming, where tasks are performed one after another, regardless of how many processors are available. Why Parallel Programming? The motivation arises from a key limitation in computing: • Earlier, computer performance used to improve just by making processors run faster. • But now, we can’t keep increasing the speed because it would cause too much heat and use too much power. • So, instead of making one processor faster, manufacturers put many processors (cores) together in a single chip. • To take advantage of all these cores and make programs run faster, we now need parallel programming, which means making the computer do many tasks at the same time. Key Concepts in Parallel Programming a) Speedup and Efficiency Speedup is the ratio of the time taken to solve a problem on a single processor to the time taken on multiple processors. Efficiency measures how effectively the processors are utilized and is given by: Key Concepts in Parallel Programming • Ideal speedup is linear (i.e., using 4 processors makes the program 4 times faster), but in practice, communication overhead, synchronization, and load imbalance reduce performance. • Example: If a task takes 100 seconds on 1 processor and 25 seconds on 4 processors: Speedup = 100 / 25 = 4 Efficiency = 4 / 4 = 1 (or 100%) — this is ideal, but rare in real scenarios. Key Concepts in Parallel Programming b) Scalability Scalability is the ability of a parallel system to increase performance as the number of processors increases. A scalable program continues to perform efficiently as we add more processing elements. Limited scalability is often due to: • Amdahl’s Law: even a small serial portion of code limits speedup. • Communication overhead: more processors mean more data exchange. • Synchronization costs: coordinating between threads or processes takes time. Key Concepts in Parallel Programming c) Granularity Granularity means how big or small the work is when we split a big job into smaller parts. Fine-grained: The work is broken into very small pieces. These pieces need to talk to each other a lot, which takes time and slows things down. Coarse-grained: The work is split into bigger pieces. They work mostly on their own, so it’s faster and easier to manage. Example cooking a big meal: Fine-grained: Many people each cutting one vegetable they keep asking what to do next. Coarse-grained: One person makes the salad, one makes rice, one cooks the curry everyone works on their part without much talking. Challenges in Parallel Programming 1. Decomposition: Breaking a problem into tasks that can be performed concurrently. 2. Load balancing: Ensuring all processors are utilized equally. 3. Communication: Exchanging data between tasks efficiently. 4. Synchronization: Making sure tasks are coordinated correctly (e.g., waiting for others to finish). 5. Debugging: Errors in parallel code can be non-deterministic and hard to reproduce. The von Neumann architecture • Single memory is used to store both data and instructions. • The CPU fetches instructions and data one at a time through the same path (bus). • Simpler design but can cause bottlenecks because data and instructions share the same bus. • Most general-purpose computers use this model. • Example: Laptops, desktops. The von Neumann architecture The classical von Neumann architecture is the basic design of most computers. It includes three main parts: Main memory – stores both the program (instructions) and the data. CPU (Central Processing Unit) – the brain of the computer, which runs the instructions. Connection (Interconnect) – a path (like a highway) that allows data and instructions to move between memory and CPU. Each memory location has an address (like a house number) and stores either a piece of data or an instruction. The von Neumann architecture The CPU is split into two parts: 1. The control unit decides which instruction to run. 2. The datapath actually runs (executes) the instruction. • Inside the CPU, there are small, fast storage units called registers. One special register is the program counter, which keeps track of which instruction is next. • When the CPU needs data or instructions, it fetches them from memory using the interconnect. • Traditionally, this connection was a bus (a group of wires), but modern systems use faster and more advanced connections. The von Neumann architecture • A big problem with the von Neumann design is called the von Neumann bottleneck. • It happens because the CPU works very fast, but it has to wait for data and instructions to come from memory through the same path. • Since this path is slower, the CPU ends up sitting idle, and the whole system becomes slower. • Imagine a chef (CPU) cooking in a kitchen, but all the ingredients and tools (data and instructions) are kept in a pantry down the hall (memory). Every time the chef needs something like salt or a knife they have to walk to the pantry, get it, and come back. • Even though the chef is very skilled and fast at cooking, they spend a lot of time just walking back and forth, which slows down the cooking. Processes, multitasking, and threads What is an Operating System (OS)? • The Operating System (OS) is a big software program that controls the computer. It decides: • Which programs run and when • How memory is given to programs • Who can use hardware like disk drives or internet connections Processes, multitasking, and threads What is a Process? • When you run a program (like a game or browser), the OS creates a process which is like a live version of the program running on your computer. A process includes: • The program's code (instructions to run) • Memory (for current tasks and data) • Files it's using (like images, videos, etc.) • Security info (what the process is allowed to do) • Status info (whether it's running or waiting) Processes, multitasking, and threads What is Multitasking? • Modern computers can run many programs at the same time this is called multitasking. • Even if your computer has only one core, the OS switches between programs very quickly (every few milliseconds), giving the illusion that everything is running at the same time. • If one program needs to wait (for example, to load a file), the OS lets another program use the CPU in the meantime. Processes, multitasking, and threads What is a Thread? • A thread is a smaller part of a process. One process can have many threads, each doing a different task. • For example: • One thread may wait for a file • Another thread may keep showing the user interface • Threads are: • Faster to switch between than whole processes • Share memory and resources of the main process • Each has its own call stack and program counter so it can run independently • A process is like the whole company • Threads are the workers doing different jobs inside the company Caching • Caching is a technique used to speed up data access. • A cache is a small, fast memory located close to the CPU. • It stores recently or frequently used data, so the CPU doesn’t have to go to the slower main memory every time. • Think of it like keeping your most-used tools on your desk instead of in a far away toolbox. Cache Mappings Cache mapping determines how data from main memory is placed into the cache. Three main types: • Direct Mapping – Each memory block goes to one fixed cache location. • Associative Mapping – A memory block can go anywhere in the cache. • Set-Associative Mapping – A balance; memory block can go to a specific group (set) in the cache. Helps improve efficiency and hit rate (chances of finding data in cache). Virtual Memory • Virtual memory gives programs the illusion that they have more memory than is physically available. • It uses a part of the hard drive as if it were RAM. • The OS moves data between RAM and hard drive automatically. • It allows multiple programs to run even if RAM is limited. Instruction-Level Parallelism (ILP) • ILP means executing multiple instructions at the same time (in parallel) inside the CPU. • Modern CPUs look for independent instructions and try to run them together. • Helps make programs run faster without changing the code. Pipelining • Like an assembly line in a factory. • CPU breaks instruction execution into stages (fetch, decode, execute, etc.).While one instruction is being executed, the next one can be fetched. • Increases the throughput (number of instructions done in a given time). Hardware Multithreading • Allows the CPU to run multiple threads at the same time using the same core. • If one thread is waiting (e.g., for data), another thread can run. • Improves CPU usage and makes programs more responsive. • Example: Hyper-Threading in Intel processors. Classifications of parallel computers Flynn’s Taxonomy (Based on Instructions and Data)Flynn’s taxonomy is a way to classify computers based on: • Instruction Stream = the flow of commands being executed. • Data Stream = the flow of data being processed. a) SISD (Single Instruction, Single Data) Executes one instruction at a time on one piece of data. Traditional, non-parallel computers. A single person solving math problems one at a time. Old single-core CPUs like early Intel Pentium. One instruction → one data → one result. Classifications of parallel computers b) SIMD (Single Instruction, Multiple Data) Executes the same instruction on many data points at once. Ideal for repetitive tasks on large datasets. A teacher gives one instruction ("Add 10") and every student applies it to their own number. GPUs – used in image processing, video rendering, deep learning (e.g., NVIDIA CUDA cores). One instruction → many data → many results. Classifications of parallel computers c) MIMD (Multiple Instruction, Multiple Data) Executes different instructions on different data simultaneously. Most powerful and flexible model for general-purpose computing. Several chefs in a kitchen cooking different dishes using different ingredients. Modern multi-core CPUs, cloud servers, distributed systems. Many instructions → many data → many results. Classifications of parallel computers d) (Less Common) MISD (Multiple Instruction, Single Data) • Multiple instructions work on the same data. • Rare in practice; mostly used in specialized safety systems. • Example: Fault-tolerant systems in aircraft or space vehicles where data is checked by multiple processors in different ways. Classifications of parallel computers Memory-Based Classification of Parallel Systems Shared Memory System All processors share the same physical memory. They communicate by directly reading and writing to shared variables. Distributed Memory System Each processor has its own private memory. They communicate by sending messages over a network. SIMD Systems (Single Instruction, Multiple Data) • Imagine a teacher standing in front of a classroom, giving the same instruction to all students: “Add 5 to your number.” Each student has a different number, but they all follow the same command at the same time. • This is exactly how a SIMD system works. • In SIMD computers, there's one "control unit" (like the teacher) that gives out a single instruction, and multiple "datapaths" (like students) that each carry out that instruction on their own piece of data. • This makes SIMD very good for tasks that need to repeat the same operation many times on different data for example, adding two arrays of numbers element by element. SIMD Systems (Single Instruction, Multiple Data) • But SIMD has a limitation. If some pieces of data don’t need the operation, the corresponding datapaths just sit idle. • For example, if we only want to add positive numbers, then datapaths working on negative numbers do nothing. This wastes resources and slows performance. • In SIMD systems, all parts (called datapaths) must work together and follow the same instruction at the same time. They can’t do different things on their own. This makes SIMD less flexible. • But when the job is suitable like working on big image or sound files SIMD can be very fast and efficient. SIMD Systems (Single Instruction, Multiple Data) Vector Processors • Vector processors are a special type of SIMD system. • They work on entire arrays (called vectors) of numbers at once, not just one number at a time. • It's like a machine that fills a whole tray of glasses instead of pouring one glass at a time. • These processors have something called vector registers, which can store many numbers together. • They use special vector instructions to perform operations (like addition) on all these numbers in one go. SIMD Systems (Single Instruction, Multiple Data) Vector Processors • For example, if you want to add two arrays, the vector processor can load both arrays, add them, and store the result all in just a few steps. • Their memory is divided into parts called memory banks, which allows them to fetch multiple pieces of data at once. • They also support advanced access methods, like skipping over memory (called strided (scatter/gather). access) or picking data from different places SIMD Systems (Single Instruction, Multiple Data) Vector Processors • Vector processors are very fast and efficient for tasks like scientific computing, where the data is organized in neat rows or columns. • But they don't work well with messy or irregular data, like linked lists or tree structures. • Also, it's hard to make a single vector processor very large, so modern systems use many vector processors together to get more power. SIMD Systems (Single Instruction, Multiple Data) Graphics Processing Units (GPUs) • A GPU (Graphics Processing Unit) is a special chip inside your computer. It was first made to handle pictures and videos. • When you play a game or watch a 3D animation, the GPU takes shapes like triangles and turns them into tiny dots called pixels that make up what you see on the screen. • GPUs are very good at doing the same task many times at once. Instead of doing one thing at a time like a CPU, a GPU can do hundreds or thousands of tasks all together. • This is called parallel processing, and it's why GPUs are so fast. • In graphics, small programs called shaders run on the GPU. These shaders do simple tasks like changing the color of a pixel or moving a shape. • The GPU can run the same shader on many pieces of data at the same time. That’s why graphics look smooth and realistic. SIMD Systems (Single Instruction, Multiple Data) Graphics Processing Units (GPUs) • A GPU has many cores (small processors), and each core can handle multiple tasks at once. It can do work like a SIMD system (doing the same task on many data items), but it can also do different tasks in different cores like a MIMD system. So GPUs are a mix of both styles. • If a task on the GPU is waiting (for example, waiting to get data from memory), the GPU doesn’t sit idle. It quickly switches to another task using something called hardware multithreading. Some GPUs can keep track of over 100 waiting tasks at once, so they never waste time. • GPUs are powerful when you give them a lot of work many threads and lots of data. But if the job is very small or simple, the GPU might not be very efficient, because it’s built to handle large workloads. MIMD Systems (Multiple Instruction, Multiple Data) • MIMD systems use many processors that all work on different tasks and different data at the same time. • Each processor has its own control system and own working datapath, so it works independently. • Unlike SIMD (where all processors follow the same instruction at the same time), MIMD processors can run at different speeds and don’t need to stay in sync. • There’s usually no global clock, meaning two processors might do totally different things at the same moment unless the programmer tells them to work together. • MIMD systems are very flexible and powerful, good for complex tasks like simulations, servers, or AI training. Types of MIMD Systems MIMD Systems (Multiple Instruction, Multiple Data) Types of MIMD Systems: 1. Shared-Memory Systems: • All processors share the same memory space. • It's like having multiple cooks in the same kitchen, all using the same fridge and pantry. • Communication happens by reading and writing to the same memory. • These systems are usually made using multicore processors (a single chip with multiple small CPUs inside it). MIMD Systems (Multiple Instruction, Multiple Data) • Shared-memory systems can be: • UMA (Uniform Memory Access): All cores take the same time to access memory. • NUMA (Non-Uniform Memory Access): Some cores can access their own memory block faster than others (like some cooks being closer to the fridge). MIMD Systems (Multiple Instruction, Multiple Data) 2. Distributed-Memory Systems: • Each processor has its own private memory and they communicate by sending messages to each other. • It’s like having many cooks in separate kitchens who talk using phones or emails. • Most common distributed systems are called clusters a group of regular computers connected using a network (like Ethernet). • Clusters are often made up of shared-memory nodes, so we call them hybrid systems. • For large systems spread across locations, Grid computing connects them all, even if they use different hardware types (this is called heterogeneous systems). Interconnection networks • In parallel computers (whether shared or distributed memory), processors need to talk to each other and to memory. The system that lets them do this is called the interconnection network. • Even if the processor and memory are super fast, if the network connecting them is slow, the whole system will be slow. So, a good interconnection is very important for performance. Shared-Memory Interconnects • In shared-memory systems, all processors use the same memory. The interconnect helps them reach that memory. Interconnection networks Bus-Based Systems • A bus is like a shared wire connecting all the devices. • It was used because it was cheap and flexible easy to add more devices. • But since only one device can use the bus at a time, if too many processors are connected, they have to wait their turn, which makes things slow. • Imagine many people sharing one single phone line only one can talk at a time. Interconnection networks Switched Interconnects • As systems grew bigger, buses became too slow, so engineers started using switched networks, like a crossbar. • As the name says, switched interconnects use switches to control how data moves between processors and memory. One common type is called a crossbar it’s simple but powerful. Figure 2.7(a) • It shows a crossbar network. • The lines are two-way (bidirectional) paths where data can flow. • The squares represent processors (cores) or memory blocks. • The circles are switches that control the paths. Interconnection networks Switches Configuration (Figure 2.7(b)) • Each switch can connect a processor to a memory block or keep them separate. • This controls which processor can use which memory.. These settings help control who can send or receive data, and where. Example (Figure 2.7(c)): Let’s say we have: P1 writing to M4 P2 reading from M3 P3 reading from M1 P4 writing to M2 Interconnection networks • The switches will be set in a way that all these actions can happen at the same time, because none of them are trying to use the same memory. • That’s the power of crossbars; multiple processors can talk to different memory blocks at the same time. Interconnection networks Distributed-Memory Interconnects • In distributed-memory systems, each processor has its own private memory, and processors need to send messages to talk to each other. • This communication happens through interconnects and there are two main types: 1. Direct Interconnects and 2. Indirect Interconnects. Interconnection networks Distributed-Memory Interconnects Direct Interconnects • In direct interconnects, each computer (processor and memory) is connected directly to a switch, and the switches are connected to each other. Examples of Direct Interconnects: Ring Network • Think of a circle where each computer is connected to two neighbors. • Only a few messages can go through at a time. • If you cut the ring into two equal parts, only 2 messages can cross the cut (called bisection). Interconnection networks Interconnection networks Toroidal Mesh • A grid of computers, connected both row-wise and column-wise, and the ends are connected in a loop. • Allows more messages to pass at once. • Bisection width: For p computers, it’s 2√p (2 times square root of number of computers). Hypercube • Imagine a cube (3D), and even more dimensions. • Each computer connects to others in a very organized way, like folding paper into cubes. • More connections, more expensive, but faster. • For p computers, bisection width is p/2. Interconnection networks Fully Connected Network • Every computer is directly connected to every other computer. • Fastest possible, but very expensive (needs too many wires). What is Bisection Width? • Suppose we split the network into two equal halves. Bisection width is the minimum number of wires you need to cut to disconnect them. • It shows how much data can flow across the middle at once. What is Bisection Bandwidth? • Instead of counting wires, we add up the speed (bandwidth) of those wires. • If each wire transfers 1 billion bits/sec, and there are 2 wires across the middle, total = 2 billion bits/sec Interconnection networks Indirect Interconnects • In indirect interconnects, computers don’t connect directly to each other. Instead, they go through a network of switches. Examples of Indirect Interconnects: Crossbar Network • Each processor has its own path to every other processor. • Like everyone having their own private road. • Very fast, but expensive. • Bisection width = p (for p × p crossbar). Interconnection networks latency and bandwidth Whenever you send data from one place to another (e.g., from memory to processor, or between two computers) two important things matter: • Latency – How long it takes to start receiving the data. • Bandwidth – How fast the data comes once it starts flowing. What is Latency? • Think of latency like waiting time before data even starts arriving. Example: Imagine ordering food online. • Latency is the time from when you place the order until the delivery guy rings your doorbell. • It includes time to pack the food and travel before it reaches you. • In computers, latency is the delay from when the data starts being sent to when the first byte is received. Interconnection networks What is Bandwidth? • Once the data starts arriving, bandwidth is how quickly it keeps coming. Example: • Think of bandwidth as how fast the delivery guy hands you boxes of food once he reaches your house. • In computing, it’s usually measured in bytes per second (e.g., MB/s or GB/s). Higher bandwidth means more data per second. Interconnection networks Full Message Time To find out how long it takes to send n bytes of data, we use this formula: Total time = Latency + (n / Bandwidth) So, even if bandwidth is high, high latency means slow start. If you send a large file, bandwidth matters more. If you send tiny messages, latency matters more. A network link has a latency of 20 milliseconds and a bandwidth of 100 MB/s. find the time taken to send: • n = 2 MB (small file) • n = 200 MB (large file) Cache Coherence Cache Coherence Modern CPUs use caches to speed up data access. These caches are controlled by the hardware, not the programmer. In shared-memory systems with multiple cores, each core has its own private cache. This can lead to problems when multiple cores use and update shared variables. Let’s say two cores (core 0 and core 1) each have private variables and access a shared variable x. Initially, x = 2. Cache Coherence At time 0: Core 0: y0 = x; Core 1: y1 = 3*x; At time 1: Core 0: x = 7; At time 2: Core 1: z1 = 4*x; Now, we expect: y0 = 2, y1 = 6 But what about z1? • Since x was already loaded into core 1's cache at time 0, and the cache doesn't know x was updated to 7 by core 0, core 1 might still use the old value x = 2. • So z1 could become 4*2 = 8 instead of 28. • This shows the problem: caches don't automatically see each other's updates. • The system doesn’t ensure that changes made by one core to a shared variable are visible to other cores. • This issue is known as the cache coherence problem. Cache Coherence Snooping Cache Coherence • To solve this, one method is snooping. • In a bus-based system, all cores are connected to a common bus. When one core updates a variable, it can broadcast this update on the bus. • Other cores can watch (snoop) this bus, and if they see a change in a variable they also have in their cache, they can mark their copy as invalid. • Snooping works for both write-through and write-back caches: • In write-through, updates go directly to memory. • In write-back, updates stay in cache and are written to memory later, so extra steps are needed to inform other caches. Cache Coherence Directory-Based Cache Coherence • Snooping works well for small systems, but for large systems (like 100+ cores), broadcasting updates to everyone is too slow. So we use directorybased coherence. • Here, a directory keeps track of which cores have copies of which variables (or cache lines). It’s like a log book. • When core 0 reads a variable, the directory notes: "core 0 has it". • When core 0 writes to the variable, the system checks the directory and tells all other cores who have it to invalidate their copies. • This way, only the cores that need to be notified are contacted. It saves time and resources, especially in large systems. • This method needs extra storage for the directory, but it avoids unnecessary broadcasts. Cache Coherence False Sharing CPU stores memory in blocks called cache lines (about 64 bytes). Several variables can fit inside one cache line. If two cores use different variables in the same cache line, they still have to share that block. When one core changes its variable, the whole block is updated slowing both cores down. Cache Coherence False Sharing int i, j, m, n; double y[m]; /* Assign y = 0 */ ... for (i = 0; i < m; i++) for (j = 0; j < n; j++) y[i] += f(i,j); parallelize it /* Private variables */ int i, j, iter_count; /* Shared variables initialized by one core */ int m, n, core_count; double y[m]; iter_count = m / core_count; /* Core 0 does this */ for (i = 0; i < iter_count; i++) for (j = 0; j < n; j++) y[i] += f(i,j); /* Core 1 does this */ for (i = iter_count; i < 2*iter_count; i++) for (j = 0; j < n; j++) y[i] += f(i,j); Cache Coherence Assume: Memory is stored in 64-byte blocks called cache lines. A double is 8 bytes, so y[0] to y[7] (8 doubles) fit in one cache line. Core 0 changes y[0]–y[3] and Core 1 changes y[4]–y[7], but they’re still in the same cache line. When one core changes its part, the whole block is marked as changed, so the other core must reload it over and over. Even though Core 0 touches the first half and Core 1 touches the second half, the CPU treats the whole chunk as shared. So every time one core writes, the other core’s copy of that chunk becomes “old” and has to be reloaded. This constant reloading wastes time, that’s false sharing. It’s “false” because the cores aren’t actually working on the same data, but the hardware can’t tell the difference. Solution: Use temporary variables (local to the thread/core) and then copy the results to the shared array at the end. This avoids unnecessary memory traffic. Shared-memory vs. distributed-memory Aspect Shared-Memory System Distributed-Memory System All processors share a single global Each processor has its own private Memory Access memory. memory. Done explicitly using message passing Communication Done implicitly via shared variables. (e.g., MPI). Programming Easier to program using threads (e.g., More complex; requires handling Ease OpenMP). communication manually. Highly scalable; supports thousands of Limited scalability due to bus Scalability processors using scalable contention and memory bottlenecks. interconnects. Crossbar interconnects are expensive; Cost and Cheaper and easier to expand using buses become bottlenecks with more Hardware interconnects like hypercube or mesh. processors. Best suited for small-scale systems like Ideal for large-scale computing like Usage desktops and shared servers. supercomputers and data centers. Parallel Software • Parallel hardware (like multicore processors) is now common in desktops, laptops, and phones. • While hardware has advanced, many programs still run on a single core. • Some apps (like Chrome, Excel) use multiple cores, but many developers lack experience in writing parallel code. • To boost performance, software must be written to use parallelism—in shared-memory, distributed-memory, MIMD, or SIMD systems. • In shared-memory, one process creates multiple threads. • In distributed-memory, multiple processes run in parallel. • If both apply, we say processes/threads handle tasks. Coordinating the processes/threads • Sometimes, making a program parallel is easy. For example, if you want to add two arrays, each thread can work on different parts. • The programmer must: • Divide the work among threads/processes so that: a. Each one does roughly the same amount of work (this is called load balancing). b. They communicate as little as possible (to save time). • Load balancing is easy if you know the work beforehand, but gets harder when work changes during execution. • Converting a regular (serial) program into a parallel one is called parallelization. If the work is very easy to split (like array addition), we call it embarrassingly parallel. Coordinating the processes/threads • But most problems are not so easy. For those, we need: • Synchronization – making sure threads/processes work in the right order and don’t clash. • Communication – they need to share information at the right time. • Often, synchronization and communication are connected: • In distributed-memory, communication usually leads to synchronization. • In shared-memory, synchronization often acts as communication. Dynamic and Static Threads Dynamic Threads: • A single master thread remains active and waits for incoming work, such as a user request. • It creates worker threads only when there is a need to perform a task. • Once the assigned task is completed, the worker thread terminates and releases its resources. • This approach saves system resources because threads exist only when they are actively performing work. Dynamic and Static Threads Static Threads: • All threads are created at the start of the program or task execution. • These threads remain active and keep running until all the work is fully completed. • Even when idle, these threads continue to consume memory and system resources. • However, this method is generally faster, since it avoids the time and cost involved in repeatedly creating and destroying threads. • The static threading model is somewhat similar to how distributed-memory systems manage their processes. Critical Section and Mutex A critical section is a block of code that only one thread should run at a time. To control this, we use a mutex (mutual exclusion lock): Lock(&mutex); x += my_val; Unlock(&mutex); •While one thread holds the lock, others must wait. •This ensures correct results, but slows things down. •So, keep critical sections short and few. Race Condition A race condition happens when two or more threads try to update the same shared variable at the same time, and the result depends on who gets there first. Example: x += my_val; Both threads want to update x. If both do it together, the final result might be wrong. We need to make sure only one thread updates x at a time. This is done by using locks. Busy-Waiting • Another way to control order is busy-waiting: • A thread keeps checking a condition in a loop until it becomes true. • Example: • Thread 1 waits until Thread 0 updates a shared variable ok_for_1 = true. • Thread 1 is busy doing nothing, wasting CPU time. • It’s simple but inefficient. Thread Safety • A function is thread-safe if it can be safely used by multiple threads at the same time. • Most C functions are safe, but some are not. • Example: strtok (used for splitting strings) • It uses a shared static variable inside the function. • If two threads call it at the same time, the result can be wrong. • So: Avoid using non-thread-safe functions in parallel programs. Or use thread-safe alternatives like strtok_r. Message-Passing Message-Passing • This is the most common way for processes to communicate in distributed-memory systems. • Every process has a rank (like ID: 0, 1, 2, ...). • A Send function sends data. • A Receive function gets data. • Example: • Process 1 sends a message to process 0. • Process 0 receives it and prints it. Message-Passing Example behavior: if (my_rank == 1) { Send(message, 100, 0); // send to process 0 } else if (my_rank == 0) { Receive(message, 100, 1); // receive from process 1} This is still an SPMD program: one program, different actions based on rank. Each process has its own copy of the variable message. Blocking and Non-Blocking • In blocking send, the sender waits until the receiver starts receiving. • In non-blocking send, the sender finishes once the data is saved internally. • Receive usually blocks—waits until data arrives. • Also available: • Broadcast: one process sends data to all others. • Reduction: collects data from all processes and combines them (e.g., adds all values).