VLSI Systems 2(计算题)

1 低位交织计算

CPU周期时间公式：

$$T_{CPU}=\frac{1}{CPU\mathrm{时}\mathrm{钟}\mathrm{频}\mathrm{率}}$$

所需存储体(memory bank)的数量：

$$N=\frac{\mathrm{内}\mathrm{存}\mathrm{访}\mathrm{问}\mathrm{时}\mathrm{间}{T}_{memory}}{CPU\mathrm{周}\mathrm{期}\mathrm{时}\mathrm{间}{T}_{CPU}}$$

Example:

已知：CPU 时钟 = 200MHz，内存访问时间 = 50ns，求所需存储体数量和第 1 个 Bank 的地址。

Solution:

1. 计算 CPU 周期： $T_{cpu}=\frac{1}{200\times {10}^6}=5ns$

2. 计算存储体数量： $N=\frac{50ns}{5ns}=10\mathrm{个}$ ，采用 10 路低位交叉

3. 第 1 个 Bank 的地址：0,10,20,30…（步长 = 存储体数量）

2 两级内存层次平均访问时间计算

核心参数：

• $H_R$ ：命中率(Hit Ratio)，CPU访问中命中高速层的比例， $0\le H\le 1$

• $t_{A1}$ ：高速层 ( $M1$ ，如 Cache/主存)的访问时间， $t_{A1}=t_{M1}$

• $t_{A2}$ ：高速层( $M2$ ，如主存/硬盘)的系统访问时间， $t_{A2}=t_B+t_{A1}$

• $t_B$ ：从 $M2$ 到 $M1$ 的块传输时间， $t_B=b_s\times t_{M2}$ ，其中 $b_s$ 是块大小，$ t_{ M2 } $ 是 $M2$ 的单字访问时间

四个公式要背：

1. 平均系统访问时间公式(The average system access time for a word)：

   $$t_A=H\times t_{A1}+(1-H)\times t_{A2}$$

   展开公式得到：

   $$\begin{gathered} t_A=H\times t_{M1}+(1-H)\times (t_B+t_{t_{M1}}) \\ =t_{M1}+(1-H)\times t_B \\ =t_{M1}+(1-H)\times b_s\times t_{M2} \end{gathered}$$

2. 块大小 $b_s=1$ 时，简化公式：

   $$t_A=t_{M1}+(1-H)\times t_{M2}$$

3. 访问效率公式：

   $$\begin{gathered} e=\frac{t_{A1}}{t_A}=\frac{1}{H+\frac{(1-H)\cdot t_{A2}}{t_{A1}}} \\ =\frac{t_{A1}}{H}\cdot (1-H)t_{A2} \end{gathered}$$

Example:

主存访问时间 $t_{M1}=200ns$

(a) Cache-主存层次：Cache 命中率 $H=0.7$ ，Cache 访问时间 $t_{A1}=20ns$

(b) 主存-硬盘层次：主存命中率 $H=0.99$ ，硬盘单字传输时间 50ms，页大小 1K=1024 字

Solution:

(a)

$$\begin{gathered} t_{A2}=\mathrm{主}\mathrm{存}\mathrm{访}\mathrm{问}\mathrm{时}\mathrm{间}+Cache\mathrm{访}\mathrm{问}\mathrm{时}\mathrm{间}=200+20=220ns \\ {t}_A=0.7\times 20+(1-0.7)\times 220=14+66=80ns \end{gathered}$$

速度提升： $\frac{(200-80)}{200}=60\mathrm{\%}$ ；

结论：即使 H=0.7，也能大幅提升速度。

(b)

先进行单位转换： $1ms=1\times {10}^{6}ns$ ，

因此，

$$t_{M2}=50\times {10}^6=5\times {10}^{7}ns$$

块传输时间为：

$$t_B=b_S\times t_{M2}=1024\times 5\times {10}^{7}ns=5.12\times {10}^{10}ns$$

所以，

$$t_{A2}=t_B+t_{A1}=5.12\times {10}^{10}+200\approx 5.12\times {10}^{10}ns$$

则：

$$t_A=0.99\times 200+(1-0.99)\times 5.12\times {10}^{10}\approx 198+5.12\times {10}^8\times ns\approx 512ms$$

结论：即使 $H=0.99$ ，硬盘的慢速会导致系统速度大幅下降。

3 匹配逻辑布尔函数

1. 单比特匹配逻辑： $A_j$ 是参数寄存器第 $j$ 位， $F_{ij}$ 是第 $i$ 个字第 $j$ 位的存储内容，该位匹配的逻辑是同或（XNOR）： $$X_j=A_j·F_{ij}+A_j^{\prime }·F_{ij}^{\prime }$$

（ $A_j$ 和 $F_{ij}$ 相等时， $X_j=1$ ，否则为 0）

2. 带掩码的单比特逻辑： $K_j$ 是键寄存器第 j 位， $K_j=1$ 时参与匹配， $K_j=0$ 时该位恒为匹配成功：

   $$\begin{array}{}\text{(1)}& X_j+K_j^{\prime }=\{\begin{array}{l}{X}_j,if{K}_j=1\\ 1,if{K}_j=0\end{array}\end{array}$$

3. 单字完整匹配逻辑：所有位都匹配成功，该字才匹配成功，是所有位的逻辑与：

   $$M_i=(X_1+K_1^{\prime })·(X_2+K_2^{\prime })·\dots ·(X_n+K_n^{\prime })$$

   无掩码时（K 全 1），简化为： $M_i=X_1·X_2·\dots ·X_n$
   最终可以化为：

   $$M_i=\prod _{j=1}^n(A_j\cdot F_{ij}+A_j^{\prime }\cdot F_{ij}^{\prime }+K_j^{\prime })$$

4. 带元位（有效位）的匹配逻辑：

   加入元位 $T_i$ ， $T_i=1$ 表示该字有效，只有有效字的匹配才有效。

   有效匹配需要同时满足 “内容匹配 $M_i=1$ ” 和 “字有效 $T_i=1$ ”，因此布尔函数为：

   $$L_{match}=M_i\cdot T_i$$

4 段页式映射(Segmented-Page Mapping）)

5 页面置换算法

Example:

Given a main memory size of 3 page frames for a given page stream of

2 3 2 1 5 2 4 5 3 2 5 2

6 栈算法

7 页面大小优化与内存利用率

7.1 最优页大小计算

1. 内存开销组成

   • 内部碎片浪费：平均每个段的最后一页浪费 $\frac{S_p}{2}$ 个字

   • 页表开销：页表有 $\frac{S_s}{S_p}$ 个表项，每个表项 1 个字

   • 总开销公式：

     $$W=\frac{S_p}{2}+\frac{S_s}{S_p}$$

     （ $S_s$ = 段大小， $S_p$ = 页大小）

2. 最优页大小推导

   对 $S_p$ 求导，令导数为 0，得到开销最小的最优页大小：

   $$S_p=\sqrt{(2\cdot S_s)}$$

7.2 内存利用率 U 计算

核心公式：

$$U=\frac{S_s}{(S_s+W)}$$

代入最优页大小 $S_p=\sqrt{(2S_s)}$ ，化简得：

$$U=\frac{1}{(1+\sqrt{(\frac{2}{S_s})})}$$

1. 当 $S_p$ 较小时，命中率随 $S_p$ 的增大而升高（相邻访问更大概率在同一页）
2. 当 $S_p$ 超过临界值后，命中率随 $S_p$ 的增大而降低（主存能存放的页面数减少，频繁缺页）
3. 核心结论：大型系统中，能获得最优命中率的页大小，通常远大于开销最小的最优页大小；系统性能优先时，优先保证高命中率，而非最小开销。

8 Cache 存储器

• 命中（Hit）：CPU 要访问的字在 Cache 中

• 未命中（Miss）：CPU 要访问的字不在 Cache 中

• 命中率（H）：命中次数 / 总访问次数，命中率越接近 1，系统访问时间越接近 Cache 速度。

8.1 Cache-主存系统平均成本计算

核心公式：

$$C_s=\frac{(C_c\cdot S_{ca}+C_m\cdot S_{me})}{(S_{ca}+S_{me})}$$

其中，

• $C_c$ =Cache 每比特成本，
• $C_m$ = 主存每比特成本，
• $S_{ca}$ =Cache 大小，
• $S_{me}$ = 主存大小。

Example:

If the cost of the cache memory is 10 times the cost of the main memory, and the total amount of memory required is 32 MB, determine the size of each type of memory to achieve a total memory cost of only 1.01 times the cost of the main memory.

Solution:

已知： $C_c=10\cdot C_m$ ，总内存大小 $S_{ca}+S_{me}=32MB$ ，要求 $C_s=1.01·C_m$

代入公式：

$$C_s=\frac{(C_c·S_{ca}+C_m·S_{me})}{(S_{ca}+S_{me})}$$

得：

$$10C_m\cdot S_{ca}+C_m\cdot S_{me}=1.01C_m\times 32MB$$

约去 $C_m$ ，代入 $S_{me}=32MB-S_{ca}$ ，解得：

$$\begin{gathered} S_{ca}\approx 0.0319MB=31.9KB， \\ {S}_{me}\approx 31.968MB \end{gathered}$$

结论：仅增加 1% 的成本，就能大幅提升系统速度。

8.2 Cache性能计算

核心公式：

1. 平均系统访问时间：

   $$T_s=H·T_c+(1-H)·T_m$$

   （ $T_c$ =Cache 访问时间， $T_m$ = 主存访问时间， $H$ = 命中率）

2. 访问效率：

   $$e=\frac{T_c}{T_s}=\frac{1}{H+(1-H)\cdot \frac{T_m}{T_c}}$$

3. 加速比：

   $$S_c=\frac{T_m}{T_s}=\frac{1}{1-H\cdot (1-\frac{T_c}{T_m})}$$

   加速比上限为 $\frac{T_m}{T_c}$ ，当 H=1 时达到最大值。

   $r=\frac{T_m}{T_c}$ ，通常 r=5~10，即主存访问时间是 Cache 的 5~10 倍；要获得合理的访问效率，命中率需要 $ \geq 0.75$。

Example:

For a cache-main memory design, if $T_m=10T_c$ , determine the cache hit ratio that would yield an average system access time $T_s=\frac{T_m+T_c}{4}$ . What are the system access efficiency and the speedup due to cache?

Solution:

已知： $T_m=10·T_c$ ，要求 $T_s=\frac{T_m+T_c}{4}$ ，求 $H、e、S_c$

1. 代入公式： $\frac{10T_c+T_c}{4}=H·T_c+(1-H)·10T_c$
2. 化简得： $\frac{11}{4}{T}_c=H{T}_c+(1-H)10T_c\to H=\frac{7.25}{9}\approx 0.8056$
3. 访问效率： $e=\frac{T_c}{T_s}=\frac{4}{11T_c}\cdot T_c\approx 0.3636$
4. 加速比： $S_c=\frac{T_m}{T_s}=e(\frac{T_m}{T_c})=0.363636\times (\frac{10T_c}{T_c})\approx 3.6364$

9 性能度量指标

各项参数：

CPU 性能指标为 CPI：

每条指令周期数 (Cycles per instruction)

$$CPI=\frac{\sum (Instructioncount\times clockcyclecount)}{\sum Instructioncount}$$

指令带宽 ( $b_I$ )：

$$MIPS=\frac{f}{CPI\times {10}^6}$$

吞吐量（数据带宽 $b_D$ ）：

• MFLOPS 百万次浮点运算每秒：每秒百万次浮点运算
• GFLOPS 十亿次浮点运算每秒：每秒十亿次浮点运算
• 任务的执行时间 = 总时钟周期数 × 时钟周期时间

加速：

$$\mathrm{加}\mathrm{速}\mathrm{比}=\frac{\mathrm{并}\mathrm{行}\mathrm{执}\mathrm{行}\mathrm{时}\mathrm{间}}{\mathrm{串}\mathrm{行}\mathrm{执}\mathrm{行}\mathrm{时}\mathrm{间}}$$

并行度：

$$S(n)=\frac{T(1)}{T(n)}$$

效率：

$$E(n)=\frac{Effectiveprocessingtimeused}{Totalavailableprocessingtime}=\frac{S(n)}{n}$$

9.1 并行计算机的性能分析(Amdahl 定律)

设 F 为所有浮点操作中以标量操作执行的比例, 那么 (1-F) 即为以向量操作执行的比例

$b_v$ = 向量操作的吞吐量 = 标量操作的吞吐量

设平均系统吞吐量为 $b$ （每个操作的平均耗时）, 我们有: $\frac{1}{b}=\frac{F}{b_s}+\frac{1-F}{b_v}$ ，单个 N 分量向量操作的执行时间为 $T_v=\frac{N}{b_v}，$ 单个标量操作的执行时间为 $T_s=\frac{1}{b_s}$

有 $T_v=T_0+\frac{N}{n}{T}_s$ ，其中 $T_0$ 是独立于向量长度的固定设置时间或启动时间, 而 n 是处理器的并行度。当向量长度 N较大的时候， $T_0$ 可以被忽略，由此得到 $b_v=n{b}_s$

然后再代入平均系统吞吐量的公式， $b=\frac{n{b}_s}{1+(n-1)F}$ 。 $b_s$ 和 $n$ 可以是常数。

这里也可以看出，标量运算操作对系统平均吞吐量的影响。

加速比为 $S(n)=\frac{b}{b_s}=\frac{n}{1+(n-1)F}$ ，即阿姆达尔定律。

当 $F=0$ 的时候，系统完全并行，加速比取决于 $n$ 。当 $0<F<1$ 时，性能提受到串行部分影响； $F=1$ 的时候完全串行。

Example:

标量吞吐量 $b_s=10Mflops$ ，处理器并行度 $n=100$ ，求不同标量占比 $F$ 下的系统吞吐量。

Solution:

Note that $b_s$ and $n$ can be assumed to be constant.
If $b_s=10$ Mflops and $n=100$ , we have:

$$b=\frac{1000}{1+99F}$$

当 $F=0$ （无串行运算，全并行）： $b=1000$ Mflops = 1 Gflops，加速比 $S=100$ ，达到理论最大值；

当 $F=0.01$ （仅 1% 串行运算）： $b=\frac{1000}{(1+0.99)}\approx 500$ Mflops，性能直接下降一半

9.2 流水线的性能分析

假设每个阶段的处理周期时间为 $t_p$ ，假设有 $N$ 个任务，每个任务花费 $M$ 时间。如果使用 $M$ 级流水线，总处理时间为 $(M+N-1)t_p$ ；如果不使用流水线，总处理时间为 $(N\times M)t_p$ 。 加速比为 $S_n=\frac{N\times M}{N+M-1}$ 。

从 Tp1 到 Tp5 的总可用处理时间为 $(N+M-1)M{t}_p$ （总可用处理时间描述的每个阶段的处理周期总和，在流水线中每个阶段的总处理周期都是 $N+M-1$ ，共 $M$ 个阶段）。 总处理时间为 $M\times N\times t_p$ ，这个是需要计算所有处理器实际执行操作的时间总和，是否流水线都一样。 流水线效率为 $E=\frac{N}{M+N-1}$

[! note] 可以想象一个矩形，其长为完成 $N$ 个任务所需要的时间；宽为流水线级数。

• 加速比就是使用流水线加速后，原本的完成时间与加速完成时间的比例；
• 流水线效率就是完成任务花费的时间（占用的面积）与总面积的比例。

Example:

已知M=3 级流水线，N=3 个操作，每个阶段时间均为 $T_p$ ，求加速比、效率、吞吐量。

Solution:

1. 串行总时间： $T_{seq}=3\times 3\times T_p=9T_p$
2. 流水线总时间： $T_{pipe}=(3+3-1)Tp=5Tp$
3. 加速比： $S=\frac{9Tp}{5Tp}=1.8$
4. 效率： $E=\frac{3}{(3+3-1)}=0.6=60\mathrm{\%}$
5. 吞吐量： $b_p=\frac{3}{(5Tp)}$

10 同步失败概率计算

核心公式： $\mathrm{同}\mathrm{步}\mathrm{失}\mathrm{败}\mathrm{总}\mathrm{概}\mathrm{率}=\mathrm{进}\mathrm{入}\mathrm{亚}\mathrm{稳}\mathrm{态}\mathrm{的}\mathrm{概}\mathrm{率}\times \mathrm{等}\mathrm{待}\mathrm{后}\mathrm{仍}\mathrm{处}\mathrm{于}\mathrm{亚}\mathrm{稳}\mathrm{态}\mathrm{的}\mathrm{概}\mathrm{率}$

$$P_f=P_e\cdot P_s$$

1. 进入亚稳态的概率 $P_e$

   • 触发条件：触发器的输入信号在 孔径时间 $t_a$ 内发生跳变，就可能进入亚稳态。

   • 孔径时间 $t_a$ ：触发器要求输入信号在时钟跳变前后保持稳定的时间窗口（建立时间 + 保持时间）。

   • 计算公式：

     $$P_e=\frac{t_a}{t_{cy}}=f_{cy}\cdot t_a$$

     其中： $t_{cy}$ 为采样时钟周期， $f_{cy}$ 为采样时钟频率。

2. 等待后仍处于亚稳态的概率 $Ps$

   • 原理：亚稳态的电压差随时间指数放大，等待时间越长，仍处于亚稳态的概率指数级下降。

   • 计算公式：

     $$P_s=e^{(\tau s-tw)}$$

     其中： $t_w$ 为亚稳态等待时间， ${\tau }_s$ 为触发器再生时间常数。

3. 同步失败频率 $f_f$

   • 定义：单位时间内发生同步失败的次数，与异步信号的事件频率成正比。

   • 计算公式：

     $$f_f=f_e\cdot P_f$$

     其中： $f_e$ 为异步输入信号的事件频率（每秒跳变次数）。

4. 平均无故障时间 MTBF

   • 定义：两次同步失败之间的平均时间，是衡量同步器可靠性的核心指标。

   • 计算公式：

     $$MTBF=\frac{1}{f_f}\mathrm{单}\mathrm{位}：\mathrm{秒}（s）$$

Example:

Assume a Brute-force synchroniser with a 500MHz clock samples a 10MHz asynchronous input signal ,

The flip-flops have **aperture time( $t_a$ ) ** and regeneration time( ${\tau }_s$ ) of 100ps .

What is the probability of synchronisation failure( $P_f$ ) ?

What is the frequency of synchronisation failure( $f_f$ ) ?

What is the mean time between synchronisation failures( $MTBF$ ) ?

Solution:

1. 统一单位：

   $$\begin{gathered} t_a={10}^{-10}s， \\ {\tau }_s={10}^{-10}s， \\ {f}_{cy}=5\times {10}^{8}Hz， \\ {f}_e={10}^{7}Hz，t_w=2\times {10}^{-9}s \end{gathered}$$

2. 计算进入亚稳态的概率：

   $$P_e=f_{cy}\cdot t_a=5\times {10}^8\times {10}^{-10}=0.05=5\times {10}^{-2}$$

3. 计算等待后仍处于亚稳态的概率：

   $$P_s=e^{\frac{-2\times {10}^{-9}}{{10}^{-10}}}=e^{-20}\approx 2.1\times {10}^{-9}$$

4. 计算总失败概率：

   $$P_f=P_e\cdot P_s=5\times {10}^{-2}\times 2.1\times {10}^{-9}\approx {10}^{-10}$$

5. 计算失败频率：

   $$f_f=f_e\cdot P_f={10}^7\times {10}^{-10}={10}^{-3}Hz$$

6. 计算 MTBF：

   $$MTBF=\frac{1}{f_f}={10}^{3}s=16.7\mathrm{分}\mathrm{钟}$$