第6章：QoS机制与仲裁策略

延迟分解：
Latency_total = Latency_queue + Latency_arbitration + Latency_command + Latency_data

其中：

- Latency_queue: 请求在队列中的等待时间
- Latency_arbitration: 仲裁决策时间
- Latency_command: DDR命令发送和执行时间
- Latency_data: 数据传输时间

关键指标：

- Average Latency: 平均延迟
- P99 Latency: 99分位延迟
- Maximum Latency: 最坏情况延迟

带宽利用率：
BW_efficiency = BW_actual / BW_theoretical

其中：
BW_theoretical = Frequency × DataWidth × 2 (DDR)
BW_actual = DataTransferred / Time

带宽分配：
BW_allocated[i] = Weight[i] × BW_available
BW_guaranteed[i] = Min_BW[i]  // 最小保证带宽
BW_maximum[i] = Max_BW[i]      // 最大限制带宽

QoS Contract = {
    Priority_Level,          // 优先级等级
    Min_Bandwidth,          // 最小带宽保证
    Max_Latency,           // 最大延迟限制
    Burst_Size,            // 突发大小
    Deadline,              // 完成时限
    Preemptible            // 是否可抢占
}

系统配置：

- DDR4-3200, 32-bit数据宽度
- 理论带宽：3200 × 32 / 8 = 12.8 GB/s

主设备QoS需求：
┌─────────────┬──────────┬───────────┬──────────┬─────────┐
│   Master    │ Priority │ Min BW    │ Max Lat  │  Type   │
├─────────────┼──────────┼───────────┼──────────┼─────────┤
│ CPU Cluster │  High    │ 2.0 GB/s  │ 100 ns   │ Latency │
│ GPU         │  Medium  │ 4.0 GB/s  │ 500 ns   │ Bandwidth│
│ Display     │  Critical│ 1.5 GB/s  │ 200 ns   │ Real-time│
│ Video Codec │  Medium  │ 2.0 GB/s  │ 1000 ns  │ Bandwidth│
│ ISP         │  Medium  │ 1.0 GB/s  │ 500 ns   │ Mixed   │
│ DMA         │  Low     │ 0.5 GB/s  │ No limit │ Best-effort│
└─────────────┴──────────┴───────────┴──────────┴─────────┘

总需求：11.0 GB/s (利用率 86%)

优先级队列结构：
┌────────────────────────────────┐
│     Priority Queue Manager      │
├────────────────────────────────┤
│  High Priority Queue  [P=3]    │ ← CPU, Interrupt
│    ├─ Request 1                │
│    ├─ Request 2                │
│    └─ ...                      │
├────────────────────────────────┤
│  Medium Priority Queue [P=2]   │ ← GPU, Video
│    ├─ Request 1                │
│    └─ ...                      │
├────────────────────────────────┤
│  Normal Priority Queue [P=1]   │ ← General Traffic
│    └─ ...                      │
├────────────────────────────────┤
│  Low Priority Queue   [P=0]    │ ← DMA, Prefetch
│    └─ ...                      │
└────────────────────────────────┘
          ↓
    Arbitration Logic
          ↓
     DDR Commands

动态优先级计算：
Priority_effective = Priority_base + Age_factor × Waiting_time

其中：

- Priority_base: 基础优先级
- Age_factor: 老化因子（可配置）
- Waiting_time: 在队列中的等待时间

示例配置：
if (Waiting_time > Threshold_1) Priority += 1
if (Waiting_time > Threshold_2) Priority += 2
if (Waiting_time > Threshold_3) Priority = MAX_PRIORITY

基于deadline的优先级：
Urgency = (Deadline - Current_time) / Service_time
Priority_effective = f(Priority_base, Urgency)

紧急度分级：

- Critical: Urgency < 1.5  → 最高优先级
- Urgent:   Urgency < 3.0  → 优先级+2
- Normal:   Urgency < 5.0  → 优先级+1
- Relaxed:  Urgency ≥ 5.0  → 保持原优先级

多级队列结构：
Level 0: Quantum = 1 transaction  [最高优先级]
Level 1: Quantum = 4 transactions
Level 2: Quantum = 8 transactions
Level 3: Quantum = No limit       [最低优先级]

调度规则：

1. 新请求进入Level 0
2. 用完时间片降级到下一级
3. 完成IO提升一级
4. 长时间等待自动提升

状态转换：
    [New] → Level 0
      ↓ (quantum expired)
    Level 1
      ↓ ↑ (promote after wait)
    Level 2
      ↓ ↑
    Level 3

带宽分配表：
┌──────────┬────────────┬─────────────┬──────────┐
│  Master  │ Reserved % │ Actual BW   │  Credits │
├──────────┼────────────┼─────────────┼──────────┤
│ CPU      │    20%     │  2.56 GB/s  │   256    │
│ GPU      │    35%     │  4.48 GB/s  │   448    │
│ Display  │    15%     │  1.92 GB/s  │   192    │
│ Video    │    20%     │  2.56 GB/s  │   256    │
│ Others   │    10%     │  1.28 GB/s  │   128    │
└──────────┴────────────┴─────────────┴──────────┘

周期性刷新：
每个Epoch（如1000个时钟周期）重置信用值

自适应算法：

1. 监测实际使用率
   Utilization[i] = Used_BW[i] / Allocated_BW[i]

2. 重新分配未使用带宽
   Unused_BW = Σ(Allocated[i] - Used[i])
   Extra[j] = Unused_BW × Weight[j] / Σ(Weight)

3. 更新分配
   New_Allocated[i] = Base_Allocated[i] + Extra[i]

信用消耗与补充：
┌─────────────────────────────────────┐
│         Credit Manager               │
├─────────────────────────────────────┤
│ Master A: Credits = 100             │
│   - Issue request: Credits -= 8     │
│   - Per cycle: Credits += 2         │
│   - Max credits: 200                │
├─────────────────────────────────────┤
│ Master B: Credits = 50              │
│   - Issue request: Credits -= 4     │
│   - Per cycle: Credits += 1         │
│   - Max credits: 100                │
└─────────────────────────────────────┘

仲裁决策：
if (Credits[i] > 0 && Has_Request[i]) {
    Grant[i] = true;
    Credits[i] -= Request_Size[i];
}

两级信用系统：
Level 1: Guaranteed Credits (保证带宽)
Level 2: Best-effort Credits (额外带宽)

调度逻辑：

1. 优先使用Guaranteed Credits
2. Guaranteed用完后使用Best-effort Credits
3. 两种信用独立计算和补充

信用借贷：

- 允许紧急请求借用未来信用
- 设置最大透支额度
- 透支后需要还清才能继续

令牌桶参数：
┌──────────────────────────────┐
│     Token Bucket             │
├──────────────────────────────┤
│ Bucket Size: 1024 tokens     │
│ Fill Rate: 100 tokens/cycle  │
│ Current Tokens: 756           │
└──────────────────────────────┘

算法流程：

1. 初始化：Tokens = Bucket_Size
2. 每周期：Tokens += Fill_Rate (不超过Bucket_Size)
3. 发送请求：
   if (Tokens >= Request_Cost) {
       Tokens -= Request_Cost;
       Grant_Request();
   } else {
       Queue_Request();
   }

突发处理：

- 桶满时可处理突发流量
- Fill Rate决定平均带宽
- Bucket Size决定突发容量

请求分类：
┌─────────────┬──────────┬────────────┐
│ Request Type│   Size   │  Priority  │
├─────────────┼──────────┼────────────┤
│ Cache Line  │  64 B    │    High    │
│ Partial     │  128 B   │   Medium   │
│ Full Burst  │  256 B   │   Normal   │
│ Block       │  512 B+  │    Low     │
└─────────────┴──────────┴────────────┘

调度策略：

1. 估算服务时间：
   Service_Time = Size / Bandwidth + Fixed_Overhead

2. 按服务时间排序：
   Priority_Queue.sort(by: Service_Time)

3. 防止大请求饥饿：
   if (Large_Request.Wait_Time > Threshold) {
       Boost_Priority(Large_Request);
   }

关键路径标记：
┌────────────────────────────────┐
│   Critical Path Detection      │
├────────────────────────────────┤
│ CPU Instruction Fetch: ← Critical
│ CPU Data Load (blocking): ← Critical
│ CPU Data Store (posted): ← Normal
│ GPU Texture Fetch: ← High
│ GPU Frame Buffer: ← Normal
│ Prefetch: ← Low
└────────────────────────────────┘

识别机制：

1. 硬件标记：
   - CPU发出的请求携带critical标志
   - 根据指令类型自动判断

2. 软件提示：
   - 通过QoS字段指定关键性
   - 编译器或OS标记关键路径

3. 动态学习：
   - 监测请求的后续影响
   - 建立关键路径预测模型

延迟目标管理：
每个请求携带延迟目标：
Request = {
    Address,
    Size,
    Target_Latency,  // 期望完成时间
    Arrival_Time     // 到达时间
}

松弛度计算：
Slack = Target_Latency - Expected_Service_Time - (Current_Time - Arrival_Time)

调度优先级：
Priority = 1 / (Slack + ε)  // ε防止除零

动态调整：
if (Slack < 0) {
    // 已经违反目标
    Priority = MAXIMUM;
    Record_Violation();
} else if (Slack < Critical_Threshold) {
    // 接近违反
    Priority = HIGH;
    Alert_System();
}

公平性指标：

1. Jain's Fairness Index:
   J = (Σ(xi))² / (n × Σ(xi²))
   其中xi是各主设备获得的带宽
   J ∈ [0,1], 1表示完全公平

2. Max-Min Fairness:
   最大化最小份额
   max(min(BW[i] / Demand[i]))

3. Proportional Fairness:
   按权重比例分配
   BW[i] / Weight[i] = Constant

监测示例：
┌──────────┬─────────┬────────┬──────────┐
│  Master  │ Expected│ Actual │ Fairness │
├──────────┼─────────┼────────┼──────────┤
│  CPU     │  25%    │  23%   │   0.92   │
│  GPU     │  40%    │  42%   │   1.05   │
│  Display │  20%    │  19%   │   0.95   │
│  Others  │  15%    │  16%   │   1.07   │
└──────────┴─────────┴────────┴──────────┘
Overall Fairness Index: 0.96

监测参数：

- Max_Wait_Time: 最大等待时间
- Min_Service_Rate: 最小服务速率
- Starvation_Threshold: 饥饿判定阈值

检测逻辑：
for each request in queue:
    if (Current_Time - Arrival_Time > Max_Wait_Time) {
        Flag_Starvation(request);
        Boost_to_Maximum_Priority(request);
    }

for each master:
    if (Service_Rate[master] < Min_Service_Rate) {
        Flag_Master_Starvation(master);
        Reserve_Emergency_Bandwidth(master);
    }

1. 保证最小份额：
   每个主设备保证最小带宽
   Reserved_BW[i] >= Min_Required[i]

2. 轮询机制：
   定期强制轮询所有队列
   if (Cycle % Round_Robin_Period == 0) {
      Service_Next_Queue();
   }

3. 优先级上限：
   限制高优先级连续服务次数
   if (High_Priority_Count > Max_Consecutive) {
      Force_Service_Lower_Priority();
   }

虚拟时间系统：
Virtual_Time = Service_Amount / Weight

调度算法：

1. 计算虚拟完成时间
   Virtual_Finish[i] = Virtual_Start[i] + Size[i] / Weight[i]

2. 选择最小虚拟完成时间的请求
   Next_Request = min(Virtual_Finish[i])

3. 更新虚拟时间
   Virtual_Start[next] = max(Virtual_Time, Virtual_Finish[prev])

示例执行：
时刻T0: 
Master A (W=2): VF = 0 + 64/2 = 32  ← 选中
Master B (W=1): VF = 0 + 64/1 = 64

时刻T1:
Master A (W=2): VF = 32 + 64/2 = 64
Master B (W=1): VF = 0 + 64/1 = 64  ← 选中

带宽比例 A:B = 2:1 (符合权重比)