My overlead LaTex code is not written well and formatted poorly. modify it so that the layout and format is professional and looks good when compiled:

\documentclass{article}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage{amsmath}

\title{FIT3143 Applied Session 5 (Week 10)}
\author{Sanket S}
\date{September 2024}

\begin{document}

\maketitle

\section{Question 1: GPU/NPU Architectures (30\%)}

\subsection*{A. GPGPU/GPU vs. CPU:  Architectural Differences}

\textbf{Source:  Week 4 Lecture Slides (Slides 45-51), Week 5 Lecture Slides (Slides 10, 24)}

CPUs and GPUs are designed with distinct objectives, leading to fundamental architectural differences:

| Feature              | CPU                                                                    | GPGPU/GPU                                                            |
|-----------------------|--------------------------------------------------------------------------|-----------------------------------------------------------------------|
| Number of Cores      | Fewer, more complex cores optimized for general-purpose tasks and handling complex control flow  | Massive number of simpler cores optimized for parallel data processing |
| Core Complexities   | Complex, with sophisticated control logic, branch prediction, large caches, and out-of-order execution capabilities. | Simpler, with a focus on executing the same instructions on multiple data elements (SIMD). |
| Memory Bandwidth    | Lower bandwidth, as general-purpose tasks often have less regular memory access patterns.  |  Extremely high bandwidth, essential for efficient data access by many parallel processing units.  |
| ILP Exploitation     | Extensive use of pipelining, superscalar execution, and out-of-order execution to maximize instruction throughput. |  Emphasis on SIMD parallelism, leveraging the massive number of cores to process data concurrently. |

\textbf{Why the Differences?}

* \textbf{CPUs are Versatile Generalists:} They must handle a wide range of tasks efficiently, including running operating systems, executing complex applications, and handling unpredictable code with complex dependencies. Their design prioritizes flexibility and efficiency for diverse workloads.
* \textbf{GPUs are Parallel Processing Powerhouses:}  GPUs excel at highly parallel, data-intensive computations, particularly those with regular patterns (like matrix operations, image processing, and simulations). Their architecture is optimized for massive data parallelism, even at the expense of some flexibility.

\textbf{Blurring Lines:}

-  Modern CPUs are incorporating more cores and SIMD capabilities to enhance parallel processing performance.
-  GPUs are becoming more programmable (GPGPUs), expanding their applicability beyond graphics and into general-purpose computing domains.

\subsection*{B.  CPU-GPU Memory Transfer}

\textbf{Source:}  Week 5 Lecture Slides (Slide 24), Week 6A Lecture Slides (Slides 7, 25)

Efficient data transfer between the CPU's main memory (e.g., DDR5 SDRAM) and the GPU's memory (e.g., GDDR5) is crucial for GPU-accelerated applications.

\textbf{Mechanism: PCIe and DMA}

- **PCIe (Peripheral Component Interconnect Express):** A high-speed bus often used for connecting GPUs to the CPU and system memory. It provides a dedicated communication channel.
- **DMA (Direct Memory Access):** Allows the GPU to directly access and transfer data from main memory to its own memory without involving the CPU in every transfer step. This frees up the CPU to perform other tasks while data transfer is in progress.

**Diagram:**
Use code with caution.
Latex
[CPU] -----[PCIe bus] ----- [GPU]
| |
[Main Memory (DDR5)] [GPU Memory (GDDR5)]

**Data Transfer Steps:**

1. The CPU initiates the data transfer.
2. The DMA controller on the GPU takes over, managing the data transfer over the PCIe bus. 
3. Data is transferred directly between main memory and GPU memory. 
4. The CPU can continue executing other instructions while the DMA transfer is happening.

\subsection*{C.  CUDA Programming Model}

\textbf{Source:} No explicit reference in the slides, but it's a widely used model for GPGPU programming. 

CUDA (Compute Unified Device Architecture) is a programming model from NVIDIA that simplifies GPGPU programming by providing a more intuitive way to express parallelism and manage data.

\textbf{Processing and Data Flow:}

1.  \textbf{CPU Preparation (Host):}  The CPU (host) prepares the data to be processed by the GPU and allocates memory on the GPU.
2.  \textbf{Data Transfer:} The CPU initiates a DMA transfer to copy the data from main memory to GPU memory. 
3.  \textbf{Kernel Launch:}  The CPU launches a *kernel* (a parallel function) on the GPU. 
4.  \textbf{Parallel Execution (Device):} The GPU (device) executes the kernel, using its many cores to process the data in parallel. 
5.  **Results Transfer:** The GPU uses DMA to transfer the results back from GPU memory to main memory.
6.  **CPU Processing (Host):** The CPU can then access and process the results. 

**Diagram:**
Use code with caution.
[CPU (Host)] --(Data Transfer)--> [GPU (Device)]
| |
[Main Memory] [GPU Memory]
| <--(Results Transfer)-- |

\textbf{Key CUDA Features:}

* **Kernels:** Parallel functions executed on many GPU cores simultaneously. 
* **Thread Hierarchy:**  Threads are organized into blocks and grids, mapping well to the GPU's architecture. 
* **Memory Model:** CUDA provides different memory spaces (global, shared, constant) with varying access speeds and scopes, enabling programmers to optimize data access patterns.

\newpage

\section{Question 2: Clock Synchronization (30\%)}

\textbf{Source:} Week 9A Lecture Slides (Slides 9, 10, 12, 21, 24, 25)

\textbf{A.  Why Distributed Systems Need Clock Synchronization}

1. **Consistent Event Ordering:**  In distributed systems, determining the order of events across different machines is crucial for debugging, auditing, and ensuring the correctness of distributed algorithms.  A consistent time reference helps establish a clear order.

2. **Distributed Algorithm Coordination:**  Many distributed algorithms rely on timestamps or timeouts for coordination, leader election, and ensuring consistency. Without synchronized clocks, these algorithms could fail or produce incorrect results.

3. **Real-World Applications:** Applications like banking, e-commerce, and distributed databases require a global notion of time for transactions, scheduling, and data consistency.  

\textbf{B. Logical vs. Real Clocks}

* **Logical Clocks:**
   - **Focus:**  On establishing the relative order of events within a distributed system, not on precise time values. 
   - **Lamport's Algorithm:** A common example, where logical clocks are updated based on the "happens-before" relationship between events (if event A happens before event B, A's timestamp will be less than B's timestamp). 

* **Real Clocks:**
   - **Focus:** On approximating real-world time as closely as possible across all machines in the distributed system.
   - **Examples:** Cristian's algorithm, the Berkeley algorithm, Network Time Protocol (NTP).

\textbf{C. Lamport's Clock and Event Ordering Limitations}

* **The Issue:** While Lamport's clocks guarantee that events that happen before will have lower timestamps, the *reverse is not always true*.  Just because an event has a lower timestamp doesn't mean it happened earlier in real time. 

* **Slide 25 Example:** The diagram on slide 25 shows that event `E13` on process `P1` occurs *after* event `E24` on `P2` in real time, even though `E13` has a lower timestamp. This highlights the limitation of logical clocks in capturing true event ordering based on real time. 

* **Why This Matters:**
    - **Logical clocks are sufficient for many distributed algorithms** where the relative order of events is critical, but not the exact time difference. 
    - **For applications requiring real-time accuracy** (e.g., financial transactions, time-sensitive control systems), logical clocks are not adequate. 

**Question 3: Deadlock and Mutual Exclusion (40%)**

\textbf{Source:**  Week 9B Lecture Slides (Slides 13-21, 26-27)} 

\textbf{A. Resource Allocation Graph and Deadlock Conditions}

- **Deadlock:** A situation in which two or more processes are blocked indefinitely, each waiting for a resource held by another process in the group. 

- **Resource Allocation Graph:**  A directed graph used to model resource allocation and requests, making it easier to visualize potential deadlocks.
    -  **Processes:** Represented by circles (nodes).
    - **Resources:**  Represented by squares (nodes).
    - **Edges:** 
       - **Request Edge:** A directed edge from a process to a resource, indicating a request. 
       - **Assignment Edge:** A directed edge from a resource to a process, indicating that the resource is allocated to that process. 

- **Example (Deadlock Scenario):**

    ```
    [P1] --> [R1] --> [P2]
     ^          |
     |          v
    [R2] <-- [P3]
    ```

    - This graph shows a deadlock. `P1` is holding `R2` and waiting for `R1`, while `P2` is holding `R1` and waiting for `R2`. 

- **Four Necessary Conditions for Deadlock:** 

   1. **Mutual Exclusion:**  Only one process can hold a resource at a time (e.g., `P2` has exclusive access to `R1`).
   2. **Hold and Wait:**  A process holding a resource can request additional resources (e.g., `P1` holds `R2` but is requesting `R1`). 
   3. **No Preemption:** Resources cannot be forcibly taken from a process.
   4. **Circular Wait:** Two or more processes are waiting for resources in a circular chain. 

\textbf{B. Wait-for Graph and Chandy-Misra-Haas Algorithm}

- **Wait-for Graph:** A simplified version of the resource allocation graph that focuses only on processes and their dependencies. It shows which processes are waiting for which other processes. 
- **Chandy-Misra-Haas Algorithm:** A distributed algorithm for *detecting* deadlocks.  

**How It Works:**

1. **Probe Messages:** When a process is blocked waiting for a resource, it sends a "probe" message to the process holding that resource.
2. **Message Propagation:**  The probe message is forwarded along the dependency chain, with each process adding its ID to the message.
3. **Cycle Detection:**  If a probe message comes back to the process that originally sent it, a deadlock has been detected (the message has traveled in a cycle). 

**Relationship to Wait-for Graph:**

- The probe messages essentially trace the paths in the wait-for graph.
-  If a cycle exists in the wait-for graph, it will be detected by the probe messages circulating in the system. 

\textbf{C. False Deadlocks with the Centralized Algorithm}

- **Centralized Algorithm:** A single coordinator process manages resource requests and allocations.

- **False Deadlock Scenario (Slide 27):**  Imagine these events:
   1. Process `P1` releases a resource `R`.
   2. `P1` requests a resource `T` from a different machine.

   - **The Problem:** If the "release R" message arrives at the coordinator *after* the "request T" message, the coordinator might mistakenly think there's a deadlock, as it sees `P1` requesting `T` while seemingly still holding `R`.

- **Why This Happens:** The centralized approach relies on messages to communicate resource states.  Delays in message delivery can lead to an inconsistent view of the system at the coordinator.

- **Solutions to Prevent False Deadlocks:**
    1.  **Global Time Ordering:** Use timestamps to ensure that messages are processed by the coordinator in the correct order.
    2.  **Explicit Release Queries:** The coordinator can directly query each process to confirm if it has released a resource before assuming a deadlock.

\end{document}