26-bit CLA Critical Path Analysis of Four Arrangements

Module Delay Parameters (Unit: ΔG)

Module XY→S XY→Cout Cin→Cout Cin→S
FA (1-bit) 2 2 2 2
4-bit CLA 4 3 2 3
16-bit CLA 8 5 2 5

Formula (Assuming the overall adder Cin=0, hardwired, available at t=0):

Where $C_0 = 0$

Scheme ①: FA → 4b → 16b → 4b → FA

1 + 4 + 16 + 4 + 1 = 26 bits, 5 modules

Stage Module Covered Bits Cout Calc Cout S Calc S
1 FA [0] max(2, 0+2) 2 max(2, 0+2) 2
2 4-bit [4:1] max(3, 2+2) 4 max(4, 2+3) 5
3 16-bit [20:5] max(5, 4+2) 6 max(8, 4+5) 9
4 4-bit [24:21] max(3, 6+2) 8 max(4, 6+3) 9
5 FA [25] max(2, 8+2) 10 max(2, 8+2) 10

IMPORTANT
Critical Path = 10 ΔG
Path: Stage1 XY→Cout (2) → Stage2 Cin→Cout (+2=4) → Stage3 Cin→Cout (+2=6) → Stage4 Cin→Cout (+2=8) → Stage5 Cin→S (+2=10)

时间  0   1   2   3   4   5   6   7   8   9  10
      ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
 S₀:  |███████|                                      2 ΔG
 C₁:  |███████|                                      2 ΔG  ← carry starts
 
 S₁₋₄:        |███████████|                          5 ΔG
 C₅:          |███████|                              4 ΔG
 
 S₅₋₂₀:               |███████████████████|          9 ΔG  ★
 C₂₁:                 |███████|                      6 ΔG
 
 S₂₁₋₂₄:                      |███████████|          9 ΔG  ★
 C₂₅:                         |███████|              8 ΔG
 
 S₂₅:                                 |███████|     10 ΔG ★★
 C₂₆:                                 |███████|     10 ΔG

Scheme ②: FA → 4b → 4b → 16b → FA

1 + 4 + 4 + 16 + 1 = 26 bits, 5 modules

Stage Module Covered Bits Cout Calc Cout S Calc S
1 FA [0] max(2, 0+2) 2 max(2, 0+2) 2
2 4-bit [4:1] max(3, 2+2) 4 max(4, 2+3) 5
3 4-bit [8:5] max(3, 4+2) 6 max(4, 4+3) 7
4 16-bit [24:9] max(5, 6+2) 8 max(8, 6+5) 11
5 FA [25] max(2, 8+2) 10 max(2, 8+2) 10

CAUTION
Critical Path = 11 ΔG
Bottleneck is at Stage 4: Cin→S for 16-bit CLA is too large (5 ΔG), while the carry arrives quite late (t=6), resulting in S₉₋₂₄ = 6+5 = 11 ΔG

时间  0   1   2   3   4   5   6   7   8   9  10  11
      ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
 S₀:  |███████|                                      2 ΔG
 C₁:  |███████|                                      2 ΔG

 S₁₋₄:        |███████████|                          5 ΔG
 C₅:          |███████|                              4 ΔG

 S₅₋₈:                |███████████|                  7 ΔG
 C₉:                  |███████|                      6 ΔG

 S₉₋₂₄:                       |███████████████████| 11 ΔG ★★
 C₂₅:                         |███████|              8 ΔG

 S₂₅:                                 |███████|     10 ΔG
 C₂₆:                                 |███████|     10 ΔG

Failure Reason: 16-bit CLA is placed too far back → carry arrives at t=6 → plus Cin→S=5 → Total 11 ΔG

Scheme ③: 4b → 16b → 4b → 4b

4 + 16 + 4 + 4 = 28 bits (top 2 bits of input set to 0), 4 modules

Stage Module Covered Bits Cout Calc Cout S Calc S
1 4-bit [3:0] max(3, 0+2) 3 max(4, 0+3) 4
2 16-bit [19:4] max(5, 3+2) 5 max(8, 3+5) 8
3 4-bit [23:20] max(3, 5+2) 7 max(4, 5+3) 8
4 4-bit [25:24]+0 max(3, 7+2) 9 max(4, 7+3) 10

IMPORTANT
Critical Path = 10 ΔG
Path: Stage1 XY→Cout (3) → Stage2 Cin→Cout (+2=5) → Stage3 Cin→Cout (+2=7) → Stage4 Cin→S (+3=10)

时间  0   1   2   3   4   5   6   7   8   9  10
      ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
 S₀₋₃:|███████████████|                              4 ΔG
 C₄:  |███████████|                                  3 ΔG  ← carry starts

 S₄₋₁₉:           |███████████████████|              8 ΔG
 C₂₀:             |███████|                          5 ΔG

 S₂₀₋₂₃:                  |███████████|              8 ΔG
 C₂₄:                     |███████|                  7 ΔG

 S₂₄₋₂₅:                          |███████████|     10 ΔG ★★
 C₂₆:                             |███████|          9 ΔG

Scheme ④: 4b → 4b → 16b → 4b

4 + 4 + 16 + 4 = 28 bits (top 2 bits of input set to 0), 4 modules

Stage Module Covered Bits Cout Calc Cout S Calc S
1 4-bit [3:0] max(3, 0+2) 3 max(4, 0+3) 4
2 4-bit [7:4] max(3, 3+2) 5 max(4, 3+3) 6
3 16-bit [23:8] max(5, 5+2) 7 max(8, 5+5) 10
4 4-bit [25:24]+0 max(3, 7+2) 9 max(4, 7+3) 10

IMPORTANT
Critical Path = 10 ΔG
Two parallel critical paths: Stage 3's Cin→S (5+5=10) and Stage 4's Cin→S (7+3=10) arrive at the same time.

时间  0   1   2   3   4   5   6   7   8   9  10
      ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
 S₀₋₃:|███████████████|                              4 ΔG
 C₄:  |███████████|                                  3 ΔG

 S₄₋₇:            |███████████|                      6 ΔG
 C₈:              |███████|                          5 ΔG

 S₈₋₂₃:                   |███████████████████|     10 ΔG ★★
 C₂₄:                     |███████|                  7 ΔG

 S₂₄₋₂₅:                          |███████████|     10 ΔG ★★
 C₂₆:                             |███████|          9 ΔG

Comparison and Summary of the Four Schemes

Scheme Arrangement Module Count Total Bits Critical Path Bottleneck Location
① FA → 4b → 16b → 4b → FA 5 26 10 ΔG ✅ Stage 5 (FA) Cin→S
② FA → 4b → 4b → 16b → FA 5 26 11 ΔG ❌ Stage 4 (16b) Cin→S = 6+5
③ 4b → 16b → 4b → 4b 4 28→26 10 ΔG ✅ Stage 4 (4b) Cin→S
④ 4b → 4b → 16b → 4b 4 28→26 10 ΔG ✅ Stage 3 & Stage 4 (tied)

Design Guidelines

  1. Do not place the 16-bit CLA too far back: Its Cin→S = 5 ΔG is the largest among all modules. If the carry arrives late (e.g. at t=6 in Scheme ②), the total delay is amplified to 6+5 = 11 ΔG.
  2. Optimal Strategy: Place the 16-bit CLA early (1st or 2nd stage) so that the carry arrives before it waits too long, allowing its large Cin→S delay to be masked by the local XY→S delay.
  3. Schemes ③ and ④ are optimal: Achieving 10 ΔG with only 4 modules, which is more hardware-efficient than Scheme ① (5 modules, same 10 ΔG).