L12 Module Interfaces and Concurrency

MIT 6.004 2019 L12 Module Interfaces and Concurrency，由教授Arvind讲述。

这次讲座的主题为：模块接口和并发

主要内容

顺序机器的最后讲座：今天我们将讨论并发性问题，探索当存在并发活动时如何处理，这是到目前为止我们还未深入讨论的主题。
简单的观察：设计大型组合电路时通常有多种选择，很多选择涉及将组合电路转换为顺序电路。
管道化（Pipelining）：通过在组合电路的阶段之间插入FIFO，可以同时处理多个数据包，从而提高吞吐量，虽然可能会增加延迟。
折叠电路（Folded Circuits）：数据循环通过电路多次来处理，而不是一次性通过，这有助于减少电路的面积，但吞吐量低。
设计选择的理由：设计选择的背后有很好的理由，这取决于系统的某些高级属性，比如你计算的是什么，以及你计算的属性是什么，例如延迟（单个输入处理的时间）和吞吐量（每秒可以产生的答案数量）。
设计替代方案的比较：从延迟和吞吐量的角度分析不同的设计方案，以及它们对时钟周期的影响。
蓝图规格语义（Bluespec Specification Semantics）：即使多个规则可能同时就绪，也要保持“一次只执行一个规则”的语义。并行执行的规则不能引入任何新行为。
多规则系统的效率硬件：要求多个规则并行执行，而不违反一次只执行一个规则的语义。编译器构建的调度器电路尽可能并发执行多个规则。
课程后续内容：学习如何构建具有适当特性的FIFO以构建流水线系统。并在接下来的课程中使用到目前为止学到的汇编语言编程和逻辑设计知识构建一个真正的RISC-V计算机。

分页知识点

设计替代方案：延迟和吞吐量

假设每个f的延迟为5ns，FIFO为1ns，多路选择器（mux）为1ns，寄存器为1ns。

组合型（C）

设计中包含三个纯组合逻辑块f1、f2、f3。
输入数据连续流入且随后连续流出，不能同时存在两个输入。

管道型（P）

在f1、f2、f3的每个阶段之间插入FIFO，允许多个数据包同时在系统中被处理。
首个数据包进入后，下一个数据包可以随即进入，多个数据包可以在系统中并行处理，随后依次离开系统。

折叠型（F）

一个f块被重复使用，数据在系统中绕多圈后才离开。
比起独立使用多个组合逻辑块，面积最小，但吞吐量较低。

延迟和吞吐量比较

延迟（Latency）：处理单个元素所需的总时间。
吞吐量（Throughput）：系统可以处理新元素的速率。
在给定的f延迟下，组合型设计的延迟最低（17ns），但吞吐量最低（1/17）。管道型设计吞吐量更高（1/6），但延迟稍高（19ns）。折叠型设计面积最小，但延迟最高（23ns）且吞吐量最低（1/23）。

管道化系统

这样的系统包括三个阶段，通过FIFO连接，以流水线的方式处理数据。
stage1规则：当输入队列（inQ）中有元素且FIFO1有空间时触发，从inQ取出数据，应用f0处理后放入FIFO1，并从inQ中删除该数据。
stage2规则：从FIFO1中取出数据，应用f1处理后放入FIFO2，并从FIFO1中删除该数据。
stage3规则：从FIFO2中取出数据，应用f2处理后放入输出队列（outQ），并从FIFO2中删除该数据。

问题讨论：

管道系统中的三个阶段是否可以并发执行？
- 是的，但FIFO必须允许同时进行入队（enq）和出队（deq）操作。
阶段1（stage1）和阶段3（stage3）是否可以并发执行？
- 是的，即使FIFO不允许同时进行enq和deq操作。

在管道化系统中，不允许并发执行将无法称其为真正的流水线系统。设计这样的系统时，必须确保可以同时处理多个阶段，否则就不能充分利用流水线带来的性能优势。在Bluespec编程中，会确保这种并行性，并允许不同的规则在不冲突的情况下并发执行，以实现高性能的硬件设计。

代码段

rule stage1;
  fifo1.enq(f0(inQ.first)); // 对输入队列中的第一个元素应用函数f0，并将结果入队到fifo1
  inQ.deq; // 输入队列出队一个元素
endrule

rule stage2;
  fifo2.enq(f1(fifo1.first)); // 对fifo1中的第一个元素应用函数f1，并将结果入队到fifo2
  fifo1.deq; // fifo1出队一个元素
endrule

rule stage3;
  outQ.enq(f2(fifo2.first)); // 对fifo2中的第一个元素应用函数f2，并将结果入队到输出队列outQ
  fifo2.deq; // fifo2出队一个元素
endrule

每个规则代表了处理流中的一个阶段。每个enq操作是将数据元素放入下一个队列（或FIFO）中，而每个deq操作是从当前队列中移除元素。这三个规则可以视为一个管道处理的三个阶段，其中数据在队列之间流动。

多规则系统

多规则系统（Multirule Systems）中，不同的规则（或操作）可以在同一时间准备执行。这与之前我们遇到的系统不同，在那些系统中，同一时间只有一个规则准备好执行，而其他规则则是两两互斥（pair-wise mutually exclusive rules）。

这是我们迄今为止看到的系统的扩展，其中可以同时准备执行多个规则。
考虑到一个多规则可以同时准备执行的系统：
- 当可以同时执行这样的规则时？
- 对于同时执行规则的情况，合成硬件是如何看起来的？

在多规则系统中，我们要解决的问题是确定在哪些条件下可以并行执行多个规则，并且如何设计硬件以支持这种并行操作，同时保持规则的逻辑正确性。

Bluespec的一规则一次语义

Bluespec编程语言在设计时保证了其程序可以按照一次只执行一个规则的方式来更新状态。这意味着Bluespec程序的任何合法行为都可以通过观察应用一个规则后的状态更新来解释。然而，为了提高性能，我们尽可能地并行执行多个规则。

重复地：

选择准备好执行的任意规则
计算状态更新
进行状态更新

并行规则执行

如果满足以下两个条件，两个规则可以并发执行：

并发执行不会导致双重写入错误
最终状态可以通过以某种顺序一次执行一个规则来获得

我们要问的问题是，这些规则是否可以并发执行，而不违反一规则一次的语义？

示例 1

rule ra;
  x <= x+1; // 规则ra：将x的值加1
endrule
rule rb;
  y <= y+2; // 规则rb：将y的值加2
endrule

示例 2

rule ra;
  x <= y+1; // 规则ra：将x的值设为y的值加1
endrule
rule rb;
  y <= x+2; // 规则rb：将y的值设为x的值加2
endrule

示例 3

rule ra;
  x <= y+1; // 规则ra：将x的值设为y的值加1
endrule
rule rb;
  y <= y+2; // 规则rb：将y的值加2
endrule

解释与补充：

在Bluespec语言中，每个规则定义了状态的变化，类似于时序逻辑中的一次时钟周期操作。
规则ra和rb示例中描述了变量x和y的独立更新（示例1）以及相互依赖的更新（示例2和示例3）。
如果规则可以并行执行，那么我们必须确保它们之间不会互相干扰，例如不会同时写入同一状态变量，从而避免双重写入错误。
示例1中的规则ra和rb操作不同的变量，可以并发执行。而示例2和示例3中，由于它们操作了彼此的输出结果，因此它们之间存在潜在的冲突，需要进一步分析以确定是否可以并发执行。

在示例2和示例3中，我们看到x和y都依赖于对方的值。在这种情况下，并行执行可能会导致冲突，因为每个规则的输出都依赖于另一个规则的结果。如果同时执行这两个规则，那么结果将取决于硬件实现的细节，这可能会违反Bluespec设计的预期行为。

并行执行

示例1

rule ra;
  x <= x+1;
endrule
rule rb;
  y <= y+2;
endrule

给定初始值(0,0)，并行执行的最终值是(1,2)。

示例2

rule ra;
  x <= y+1;
endrule
rule rb;
  y <= x+2;
endrule

给定初始值(0,0)，并行执行的最终值是(1,2)。

示例3

rule ra;
  x <= y+1;
endrule
rule rb;
  y <= y+2;
endrule

给定初始值(0,0)，并行执行的最终值是(1,2)。

ra < rb 表示执行ra规则后再执行rb规则。 rb < ra 表示执行rb规则后再执行ra规则。

执行ra规则在rb规则之前 (ra < rb)

示例1 的最终值是(1,2)。
示例2 的最终值是(1,3)。
示例3 的最终值是(1,2)。

执行rb规则在ra规则之前 (rb < ra)

示例1 的最终值是(1,2)。
示例2 的最终值是(3,2)。
示例3 的最终值是(3,2)。

当x+1没有明确定义时，对于任何x，如果没有x^t+1定义，则使用x^t+1 = x^t

在Bluespec硬件设计语言中，正确理解并行执行对于编写高效硬件逻辑至关重要。并行执行的规则必须在逻辑上等效于它们被顺序执行的结果，即并行执行不会产生新的行为。这是Bluespec编译器保证语义正确性的一部分。如果并行执行的结果与顺序执行的结果不同，那么这种并行执行是不被允许的。

在给定的示例中，我们看到：

在示例1中，由于ra和rb操作独立的变量x和y，它们可以安全地并行执行。
在示例2和示例3中，尽管并行执行的结果与某些顺序执行的结果相匹配，但它们涉及对共享变量的更新，因此可能需要进一步的同步机制来确保一致性。

编译器需要生成额外的硬件逻辑来协调可能并行执行的规则，以确保最终状态的一致性。在示例2和3中，ra和rb的执行顺序会影响最终结果，因此它们在并行执行时需要特别的处理。在实际的硬件设计中，通常需要在这些规则之间引入锁或其他同步机制来确保一致性，而Bluespec编译器会自动处理这些同步问题。

这张图是关于Bluespec语言中规则的并行执行分析和它们之间的冲突矩阵（Conflict Matrix, CM）。下面是中文翻译和详细解释：

是否可以并行执行这些规则？

（不违反单规则一次执行的语义）

冲突矩阵（CM）

BSV编译器生成的成对冲突信息

示例1 冲突矩阵显示ra和rb之间没有冲突，可以并行执行（CF）。
示例2 冲突矩阵显示ra和rb之间有冲突，不能并行执行（C）。
示例3 冲突矩阵显示ra和rb之间的关系是ra必须在rb之前执行（ra < rb），即使可以并行执行，最终的效果就像是先执行了ra。

在Bluespec硬件设计语言中，了解规则间的依赖和冲突对于设计并行硬件逻辑非常重要。冲突矩阵是Bluespec编译器的重要组成部分，它帮助确定哪些规则可以安全地并行执行而不违反单规则一次执行的语义。这些信息是由编译器自动生成的，并用于指导生成正确的硬件逻辑。

在给出的示例中，ra和rb表示两个规则。示例1表明如果两个规则操作独立的变量，它们可以并行执行无冲突。示例2和3展示了当规则操作相同或相关的变量时，并行执行可能导致冲突，需要根据冲突矩阵来顺序执行或采用其他同步机制。

在实际硬件设计中，编译器会生成额外的硬件逻辑来协调这些并行执行的规则，确保在并行操作时维持一致性和状态的正确更新。这样做既保持了设计的高效性，同时也确保了逻辑的准确性和可预测性。

使用冲突信息进行硬件合成

并行规则执行
- 示例2:
```
rule ra;
  x <= y + 1;
endrule
rule rb;
  y <= x + 2;
endrule
```
- 假设我们将ra的就绪信号（ra.rdy）连接到ra的使能信号（ra.en），rb的就绪信号（rb.rdy）连接到rb的使能信号（rb.en）。
- 这个电路将并行执行规则ra和rb。
- 只有当规则ra和rb不冲突时，这个电路才是正确的。
- 但在这个示例中，规则ra和rb是有冲突的！

调度器的需求

对于示例2：
- 保护信号（rdy signals）或所有规则被馈送到一个调度器。
- 使用冲突矩阵（CM），调度器让只有非冲突的规则继续执行。
- 调度器是一个纯组合电路，只有少量的门（gates）。
- 一个正确但性能低下的调度器可能仅每次执行一个规则，但对于高性能设计，我们希望尽可能并行地执行多个规则。

在并行硬件设计的背景下，冲突矩阵（CM）帮助设计师了解哪些规则在运行时可能导致状态冲突。这是一个重要的考虑因素，因为它决定了哪些规则可以被同时激活，并且保证了整体系统的稳定和一致性。调度器的角色在于动态地管理这些冲突，确保合成的硬件逻辑在执行时不会违反设计的语义。例如，在这里讨论的示例中，两个规则ra和rb都想要更新同一个变量x，如果它们被同时触发，将导致不确定的行为，所以需要调度器来保证一次只有一个规则可以更新x。这样的硬件调度对于构建可预测和可控的并行处理系统至关重要。

示例调度器

示例1：
- 冲突矩阵显示规则ra和rb有时不冲突（Conflict-Free, CF），有时冲突（Conflict, C）。
- 调度器电路直接将ra的就绪信号（ra.rdy）连接到其使能信号（ra.en），同样也是对rb进行相同的操作。
示例2：
- 冲突矩阵显示规则ra和rb总是冲突的（C）。
- 调度器电路包含了逻辑门，以确保只有一个规则在给定的时间内被使能执行。它通过阻止两个规则同时被使能来避免冲突。
示例3：
- 冲突矩阵表明执行规则ra和rb的顺序很重要（ra < rb 或 rb > ra）。
- 调度器电路设计保证了在某些条件下ra和rb可以同时执行，但是ra的执行会先于rb，从而实现了ra < rb的效果。

调度器的作用是在多个规则都准备好执行的情况下，决定哪些规则可以同时执行，以及执行的顺序，这对于硬件电路的高效运行至关重要。每个示例中的电路图代表了在不同冲突矩阵约束下，如何实现规则的并发执行调度。

规则调度器

多个规则的守卫（r1.rdy … rn.rdy）可能同时为真，它们之间可能会有冲突。
BSV编译器构建了一个组合调度器电路，具有以下特性：

对于所有的规则对 i 和 j，如果 ri.en 和 rj.en 都为真，那么相应的 ri.rdy 和 rj.rdy 也必须为真，并且规则 i 和 j 不能相互冲突。

“规则守卫（rule guards）”是指在硬件设计中用于控制规则何时应该被执行的信号。如果守卫信号为真（即激活状态），则关联的规则就准备好执行。BSV（Bluespec SystemVerilog）编译器利用这些信号来构建一个组合调度器电路。这个电路的目的是同时考虑多个规则的激活状态，并在没有冲突的情况下，尽可能并行地执行它们。

例如，如果规则 A 和规则 B 同时准备就绪（即，rA.rdy 和 rB.rdy 都为真），但它们不能同时执行（因为它们操作相同的资源或有其他冲突），那么调度器电路将保证它们不会同时被激活（即，rA.en 和 rB.en 不会同时为真）。

要点

一次只执行一个规则的语义对于理解系统的合法行为非常重要。
为多规则系统设计高效的硬件需要在不违反一次只执行一个规则的语义的前提下，实现许多规则的并行执行。
BSV编译器构建了一个调度器电路，以便尽可能多地并发执行规则。
对于高性能设计，我们必须关注我们模块的CM（冲突模型）特性。

“一次只执行一个规则”的语义确保了系统行为的可预测性，即便在多规则系统中并行执行时也不例外。它要求调度器在任何时刻只能激活一个无冲突的规则集合进行执行。

在高性能的硬件设计中，冲突模型（Conflict Model, CM）特性变得尤其重要。这是因为它涉及到对资源的争用以及规则之间的相互依赖性。理解和管理这些冲突对于构建可靠且效率高的系统至关重要。

课程后续将讨论更多关于此主题的内容。

我们还没有完成！

// 第一阶段规则
rule stage1;
    fifo1.enq(f0(inQ.first));
    inQ.deq;
endrule

// 第二阶段规则
rule stage2;
    fifo2.enq(f1(fifo1.first));
    fifo1.deq;
endrule

// 第三阶段规则
rule stage3;
    outQ.enq(f2(fifo2.first));
    fifo2.deq;
endrule

无流水线
这些规则可以同时执行，但只有在FIFO允许enq（入队）和deq（出队）操作并行时。
在我们的单元素FIFO设计中，enq和deq是互斥的。
我们将会设计更好的FIFO。

带回家的问题

rule stage1;
    fifo1.enq(f0(inQ.first));
    inQ.deq;
endrule
rule stage2;
    outQ.enq(f1(fifo.first));
    fifo.deq;
endrule

为这个设计绘制硬件电路，忽略FIFO设计的内部。
提示：
- 为每个规则绘制保护（guard）。
- 假设每个规则都有一个激活信号。
- 将规则的准备和激活信号连接到一个调度器。

Table of contents

L12 Module Interfaces and Concurrency
1. 主要内容
分页知识点