Computer Organization and Architecture - Pipeline Processing

Memory Hierarchy Cache Access NAT Practice

  • Memory Hierarchy Configuration:
    • Instruction Cache (II-cache): Read access time = 2 ns2\,\text{ns}, Hit ratio = 0.80.8
    • Data Cache (DD-cache): Read access time = 2 ns2\,\text{ns}, Hit ratio = 0.90.9
    • Level 2 Cache (L2L_2-cache): Read access time = 8 ns8\,\text{ns}, Hit ratio = 0.90.9
    • Main Memory: Read access time = 90 ns90\,\text{ns}
  • System Operational Policies and Assumptions:
    • Read policy: Referred-word-first
    • Write policy: Write-back
    • Cache Mapping: Direct-mapped for all caches
    • Dirty bit status: Always 00 for all blocks in the caches
  • Workload Characteristics:
    • Instruction Fetch (II-cache access): 60%60\% of total memory reads
    • Memory Operand Fetch (DD-cache access): 40%40\% of total memory reads
  • Average Read Access Time Result:
    • Under the specified operational conditions, the calculated average read access time across the memory hierarchy is 4.072 ns4.072\,\text{ns}.

Fundamentals of Parallel Processing

  • Definition:
    • Parallel processing refers to the simultaneous execution of data processing operations to enhance computational speed and system throughput.
  • Classification of Parallel Processing Techniques:
    • Vector Processing
    • Array Processing
    • Pipeline Processing (Pipelining)

Pipeline Processing Principles and Execution Trace

  • Concept and Mechanics:
    • Pipelining is a technique used to decompose a sequential processing task into sub-operations.
    • Each sub-operation is executed in a dedicated segment or stage of the pipeline.
    • Each segment performs its respective sub-operation concurrently on different inputs in parallel.
    • Pipelining is particularly useful when the same processing sequence is repeatedly applied over a large batch of inputs.
  • Sequential vs. Pipelined Manufacturing Example (Shirt Making):
    • Sub-operations required for one shirt:
    • Cutting: 10 min10\,\text{min}
    • Stitching: 10 min10\,\text{min}
    • Finishing: 10 min10\,\text{min}
    • Packing: 10 min10\,\text{min}
    • Sequential (Non-pipeline) System:
    • Total time required per shirt = 10 min+10 min+10 min+10 min=40 min10\,\text{min} + 10\,\text{min} + 10\,\text{min} + 10\,\text{min} = 40\,\text{min}.
    • Segmented Pipeline System:
    • Segment 1 (S1S_1): Cutting (10 min10\,\text{min})
    • Segment 2 (S2S_2): Stitching (10 min10\,\text{min})
    • Segment 3 (S3S_3): Finishing (10 min10\,\text{min})
    • Segment 4 (S4S_4): Packing (10 min10\,\text{min})
    • Number of segments (kk) = 44
  • Timing Trace Across Clock Pulses for n=5n = 5 Inputs:
    • Clock Pulse 1: Segment S1S_1 processes Task 1.
    • Clock Pulse 2: Segment S1S_1 processes Task 2; Segment S2S_2 processes Task 1.
    • Clock Pulse 3: Segment S1S_1 processes Task 3; Segment S2S_2 processes Task 2; Segment S3S_3 processes Task 1.
    • Clock Pulse 4: Segment S1S_1 processes Task 4; Segment S2S_2 processes Task 3; Segment S3S_3 processes Task 2; Segment S4S_4 processes Task 1.
    • Clock Pulse 5: Segment S1S_1 processes Task 5; Segment S2S_2 processes Task 4; Segment S3S_3 processes Task 3; Segment S4S_4 processes Task 2.
    • Clock Pulse 6: Segment S2S_2 processes Task 5; Segment S3S_3 processes Task 4; Segment S4S_4 processes Task 3.
    • Clock Pulse 7: Segment S3S_3 processes Task 5; Segment S4S_4 processes Task 4.
    • Clock Pulse 8: Segment S4S_4 processes Task 5.
  • Formula for Total Clock Cycles:
    • Cycles=k+n−1\text{Cycles} = k + n - 1
    • For k=4k = 4 stages and n=5n = 5 inputs: Cycles=4+5−1=8 cycles\text{Cycles} = 4 + 5 - 1 = 8\,\text{cycles}.
  • Time Comparison Across Task Batch Sizes (1 cycle=10 min1\,\text{cycle} = 10\,\text{min}):
    • For n=5n = 5 inputs:
    • Non-pipeline execution time: 5×40 min=200 min5 \times 40\,\text{min} = 200\,\text{min}
    • Pipeline execution time: 8×10 min=80 min8 \times 10\,\text{min} = 80\,\text{min}
    • For n=6n = 6 inputs:
    • Non-pipeline execution time: 6×40 min=240 min6 \times 40\,\text{min} = 240\,\text{min}
    • Pipeline execution time: (6+4−1)×10 min=9×10 min=90 min(6 + 4 - 1) \times 10\,\text{min} = 9 \times 10\,\text{min} = 90\,\text{min}
    • For n=7n = 7 inputs:
    • Non-pipeline execution time: 7×40 min=280 min7 \times 40\,\text{min} = 280\,\text{min}
    • Pipeline execution time: (7+4−1)×10 min=10×10 min=100 min(7 + 4 - 1) \times 10\,\text{min} = 10 \times 10\,\text{min} = 100\,\text{min}
    • For n=8n = 8 inputs:
    • Non-pipeline execution time: 8×40 min=320 min8 \times 40\,\text{min} = 320\,\text{min}
    • Pipeline execution time: (8+4−1)×10 min=11×10 min=110 min(8 + 4 - 1) \times 10\,\text{min} = 11 \times 10\,\text{min} = 110\,\text{min}

Quantitative Performance Metrics and Speed Up

  • Pipeline Cycle Time (tpt_p):
    • Defined as the minimum time interval required for all pipeline segments to finish their respective sub-operations concurrently in parallel.
  • Mathematical Formulation of Processing Time:
    • Pipeline Processing Time:
    • Time required to process the 1st input = k×tpk \times t_p
    • Time required for the remaining (n−1)(n - 1) inputs = (n−1)tp(n - 1)t_p
    • Total clock cycles required = k+n−1k + n - 1
    • Total execution time in pipeline: (k+n−1)tp(k + n - 1)t_p
    • Non-Pipeline Processing Time:
    • For a non-pipeline system taking time tnt_n to perform one complete task:
    • Total execution time in non-pipeline: n×tnn \times t_n
  • Speed Up Ratio (SS):
    • Quantifies the performance gain achieved by employing a pipeline system over a non-pipeline system.
    • S=Non-pipeline timePipeline time=n×tn(k+n−1)tpS = \frac{\text{Non-pipeline time}}{\text{Pipeline time}} = \frac{n \times t_n}{(k + n - 1)t_p}
  • Asymptotic and Ideal Speed Up:
    • When the number of inputs is extremely large (n≫kn \gg k):
    • The initial k−1k - 1 cycles required to fill the pipeline become negligible and are ignored.
    • The pipeline effectively outputs 1 task per cycle, taking nn cycles (n×tpn \times t_p execution time).
    • Ideal Speed Up (S_{\ideal}):       S_{\ideal} = \frac{t_n}{t_p}
    • Special Case where single task execution time is identical in both systems (tn=k×tpt_n = k \times t_p):
    • S_{\ideal} = \frac{k \times t_p}{t_p} = k
    • Default Evaluation Rule:
    • If the value of nn is omitted or ideal conditions are presumed, speedup is computed as S=tntpS = \frac{t_n}{t_p}.

Synchronous Pipeline Cycle Time and Register Delays

  • Role of Intermediate Buffers/Registers:
    • In a synchronous pipeline, intermediate registers or buffers are placed between consecutive stages to latch sub-operation outputs.
    • Registers are used exclusively in pipeline architectures and are absent in non-pipeline systems.
  • Determining Pipeline Cycle Time (tpt_p):
    • Without Register Delay:     tp=max⁡(τ1,τ2,…,τk)t_p = \max(\tau_1, \tau_2, \dots, \tau_k)     where τi\tau_i represents the time delay of segment i$.\n * With Register/Buffer Delay (t_r):\n    t_p = \max(\tau_1, \tau_2, \dots, \tau_k) + t_r\n* Equivalent Non-Pipeline Processing Time (t_n):\n * Sum of all individual segment delays without register delays:\n    t_n = \sum_{i=1}^{k} \tau_i\n * Practical Relationship:\n    t_n \le k \times t_p\n* Pipeline Optimization Criterion:\n * For optimal pipeline efficiency and performance, individual segment delays must be almost equal or close to each other.\n\n# Numerical Problems and Optimization Techniques\n\n* Problem 1: Basic Speedup and Asymptotic Convergence\n * Given Parameters:\n * Non-pipeline processing time t_n = 50\,\text{ns}\n * Number of pipeline segments k = 6\n * Pipeline clock cycle time t_p = 10\,\text{ns}\n * Question 1: Determine speedup ratio for n = 100 tasks.\n    S = \frac{100 \times 50}{(6 + 100 - 1) \times 10} = \frac{5000}{105 \times 10} = \frac{5000}{1050} \approx 4.76\n * Question 2: Maximum theoretical speedup achievable (S_{\ideal}).\n    S_{\ideal} = \frac{t_n}{t_p} = \frac{50}{10} = 5\n * Speedup Convergence Progression across Task Volumes:\n * For n = 100 \implies S = 4.76\n * For n = 1000 \implies S = \frac{1000 \times 50}{(6 + 1000 - 1) \times 10} = \frac{50000}{10050} \approx 4.97\n * For n = 100000 \implies S = \frac{100000 \times 50}{(6 + 100000 - 1) \times 10} = \frac{5000000}{1000050} \approx 4.9997\n\n* Problem 2: Pipeline Processing Time with Variable Segment Delays\n * Given Parameters:\n * Number of segments k = 6\n * Segment delays: \tau_1 = 20\,\text{ns},,\tau_2 = 23\,\text{ns},,\tau_3 = 21\,\text{ns},,\tau_4 = 21\,\text{ns},,\tau_5 = 24\,\text{ns},,\tau_6 = 25\,\text{ns}\n * Task volume n = 1000\n * Step 1: Calculate pipeline cycle time t_p:\n    t_p = \max(20, 23, 21, 21, 24, 25) = 25\,\text{ns}\n * Step 2: Calculate total processing time:\n    \text{Total Time} = (k + n - 1)t_p = (6 + 1000 - 1) \times 25\,\text{ns} = 1005 \times 25\,\text{ns} = 25125\,\text{ns} = 25.125\,\mu\text{s}\n\n* Problem 3: Pipeline Processing Time including Register Delays\n * Given Parameters:\n * Four segments (k = 4)withdelays:) with delays:t_1 = 50\,\text{ns},,t_2 = 30\,\text{ns},,t_3 = 95\,\text{ns},,t_4 = 45\,\text{ns}\n * Interface register delay t_r = 5\,\text{ns}\n * Task volume n = 100\n * Step 1: Calculate pipeline cycle time t_p:\n    t_p = \max(50, 30, 95, 45) + 5 = 95 + 5 = 100\,\text{ns}\n * Step 2: Calculate total processing time:\n    \text{Total Time} = (4 + 100 - 1) \times 100\,\text{ns} = 103 \times 100\,\text{ns} = 10300\,\text{ns}\n\n* Problem 4: Decomposing Bottleneck Segments for Execution Acceleration\n * Objective: Reduce total execution time to approximately one-half of Problem 3's time (10300\,\text{ns}).\n * Optimization Technique: Decompose segment 3 (t_3 = 95\,\text{ns}) into two separate segments:\n * Segment 3.1 delay t_{31} = 50\,\text{ns}\n * Segment 3.2 delay t_{32} = 45\,\text{ns}\n * New Pipeline Parameters:\n * Total segments k_{\text{new}} = 5\n * Segment delays: t_1 = 50\,\text{ns},,t_2 = 30\,\text{ns},,t_{31} = 50\,\text{ns},,t_{32} = 45\,\text{ns},,t_4 = 45\,\text{ns}\n * Register delay t_r = 5\,\text{ns}\n * Step 1: Calculate new cycle time t_{p,\text{new}}:\n    t_{p,\text{new}} = \max(50, 30, 50, 45, 45) + 5 = 50 + 5 = 55\,\text{ns}\n * Step 2: Calculate new execution time for n = 100 tasks:\n    \text{New Time} = (5 + 100 - 1) \times 55\,\text{ns} = 104 \times 55\,\text{ns} = 5720\,\text{ns}\n * Step 3: Compute speedup ratio of new pipeline relative to old pipeline:\n    \text{Speedup} = \frac{\text{Old Pipeline Time}}{\text{New Pipeline Time}} = \frac{10300\,\text{ns}}{5720\,\text{ns}} \approx 1.8\n\n# Practice and Homework Exercises\n\n* Homework Problem Formulation:\n * Initial Pipeline: A 6-stage pipeline with delays 2\,\text{ns},,4\,\text{ns},,3\,\text{ns},,5\,\text{ns},,3\,\text{ns},and, and4\,\text{ns}.\n * Upgraded Pipeline: Upgraded to a new 8-segment pipeline where each segment delay is equal to 2\,\text{ns}.\n * Task Batch Size: n = 100 tasks.\n* Homework Question 1:\n * Calculate the total time saved using the new upgraded pipeline over the old pipeline for processing 100 tasks.\n* Homework Question 2:\n * Calculate the speedup ratio achieved by the new upgraded pipeline compared to the old pipeline for processing 100$$ tasks.