实验 4: N 元 FIFOs

实验 4 截止日期： 2016年10月12日，星期三，晚上11:59:59 EDT。

实验 4 的交付内容包括：

在 MyFifo.bsv 中对练习 1-4 的回答

在 discussion.txt 中对讨论问题 1-4 的回答

引言

本实验聚焦于设计各种 N 元素 FIFO，包括无冲突 FIFO。无冲突 FIFO 是流水线设计的重要工具，因为它们允许流水线阶段被连接，而不引入额外的调度约束。

创建一个无冲突的 FIFO 是困难的，因为你需要创建不会相互冲突的入队和出队方法。不是无冲突的 FIFO，如流水线和旁路 FIFO，假设了入队和出队的顺序。流水线 FIFO 假设在入队前完成出队，而旁路 FIFO 假设在出队前完成入队。仅用 EHRs 来实现流水线和旁路 FIFOs，并用 EHRs 加上规范化规则来创建无冲突 FIFO。

参数化大小 FIFO 的功能

在讲座中，你已经看到了一个两元素无冲突 FIFO 的实现。这个模块利用 EHRs 和一个规范化规则来实现无冲突的入队和出队方法。出队仅从第一个寄存器读取，而入队仅写入第二个寄存器。如果需要，规范化规则会将第二个寄存器的内容移动到第一个寄存器。这种结构对于小型 FIFO 如两元素 FIFO 来说效果很好，但对于更大的 FIFO 来说使用过于复杂。

要实现更大的 FIFO，你可以使用循环缓冲区。

图 1 显示了在循环缓冲区中实现的 FIFO。这个 FIFO 包含数据 [1, 2, 3]，1 在前端，3 在后端。指针 deqP 指向 FIFO 的前端，enqP 指向 FIFO 后的第一个空闲位置。

索引	0	1	2	3	4	5
数据	`-`	`-`	`1`	`2`	`3`	`-`
			↑			↑
指针			`deqP`			`enqP`

图 1：实现在循环缓冲区中的 6 元素 FIFO 示例。这个 FIFO 包含 [1, 2, 3]。

在循环缓冲区中实现的 FIFO 中，入队只是在 enqP 的位置写入，并将 enqP 增加 1。将值 4 入队到示例 FIFO 的结果可见于图 2。

索引	0	1	2	3	4	5
数据	`-`	`-`	`1`	`2`	`3`	`4`
	↑		↑
指针	`enqP`		`deqP`

图 2：入队 4 后的 6 元素 FIFO。这个 FIFO 包含 [1, 2, 3, 4]。

出队则更为简单

。出队时，只需将 deqP 增加 1。从示例 FIFO 出队一个值的结果可见于图 3。请注意数据并未被移除。虽然值 1 仍存储在 FIFO 的寄存器中，但它处于无效空间，因此用户再也看不到它。FIFO 图中的所有 - 都是指之前曾在 FIFO 中但现已无效的旧数据。这个 FIFO 结构中没有有效位。位置在出队指针之后但在入队指针之前时有效。这为判断 FIFO 是满还是空增加了一些复杂性。

索引	0	1	2	3	4	5
数据	`-`	`-`	`1`	`2`	`3`	`4`
	↑			↑
指针	`enqP`			`deqP`

图 3：出队一个元素后的 6 元素 FIFO。这个 FIFO 包含 [2, 3, 4]。

考虑图 4 中的 FIFO 状态。这个图显示了一个 FIFO，其中 enqP 和 deqP 指针指向同一个元素。这个 FIFO 是满的还是空的？除非你有更多的信息，否则无法判断。为了跟踪当指针重叠时 FIFO 的状态，我们将有一个寄存器表示 FIFO 是否满，另一个表示 FIFO 是否空。图 5 显示了一个满 FIFO，附加的寄存器跟踪满和空的状态。

索引	0	1	2	3	4	5
数据	`3`	`9`	`6`	`2`	`0`	`3`
			↑ ↑
指针			`enqP` `deqP`

图 4：6 元素 FIFO 满还是空。

索引	0	1	2	3	4	5
数据	`3`	`9`	`6`	`2`	`0`	`3`
			↑ ↑
指针			`enqP` `deqP`

大小	full:	`True`		empty:	`False`

图 5：6 元素 FIFO 满。

清空的 FIFO 将会使 enqP 和 deqP 指向同一位置，其中 empty 为 True 而 full 为 False。

如果 enqP 或 deqP 指向同一位置，empty 或 full 其中之一应为真。当一个指针移动到另一个指针的位置时，根据移动指针的方法，FIFO 需要设置 empty 或 full 信号。如果执行了入队操作，full 应该为真。如果执行了出队操作，empty 应该为真。

N 元素 FIFO 的实现细节

本节深入探讨了如何在 Bluespec 中以循环缓冲区的形式实现 N 元素 FIFO。

数据结构

FIFO 将具有 n 元素的寄存器向量来存储 FIFO 中的数据。这个 FIFO 应该能够使用参数类型 t 工作，因此寄存器将是 Reg#(t) 类型。

FIFO 将具有入队和出队操作的指针。这些指针，enqP 和 deqP，指向下一次操作将发生的位置。入队指针指向所有有效数据之后的下一个元素，而出队指针指向有效数据的前端。这些指针将是 Bit#(TLog#(n)) 类型的寄存器值。TLog#(n) 是对应于数值类型 n 的值的基数 2 对数的上限的数值类型。简单来说，TLog#(n) 是从 0 到 n-1 计数所需的位数。

状态标志

FIFO 还将伴随入队和出队指针具有两个状态标志：full 和 empty。这些寄存器在 enqP 不等于 deqP 时都为假，但当 enqP 和 deqP 相等时，要么 full 要么 empty 为真，表达 FIFO 的状态。

接口方法

此 FIFO 将保持与课堂上介绍的以前的 FIFO 相同的接口。

interface Fifo#(numeric type n, type t);
  method Bool notFull;
  method Action enq(t x);
  method Bool notEmpty;
  method Action deq;
  method t first;
  method Action clear;
endinterface

数据类型为 t，大小为数值类型 n。

NotFull

notFull 方法返回内部 full 信号的否定。
Enq

enq 方法将数据写入入队指针指向的位置，增加入队指针，并在必要时更新 empty 和 full 值。如果无法入队，此方法应通过守卫被阻塞。
NotEmpty

notEmpty 方法返回内部 empty 信号的否定。
Deq

deq 方法增加出队指针，并在必要时更新 empty 和 full 值。如果无法出队，此方法应通过守卫被阻塞。
First

first 方法返回出队指针指向的元素，只要 FIFO 不为空。如果 FIFO 为空，此方法应通过守卫被阻塞。
Clear

clear 方法将入队和出队指针设置为 0，并通过设置内部 full 和 empty 信号的适当值将 FIFO 状态设置为空。

方法排序

根据实施的 FIFO 类型，enq 和 deq 可能以任何顺序、固定顺序触发，或者它们可能无法在同一周期触发。通常与 enq 和 deq 相关联的方法应该能够与各自的方法触发。即 notFull 应该能够

与 enq 触发，同样 notEmpty 和 first 应该能够与 deq 触发。在所有情况下，clear 方法应该优先于所有其他方法，因此它会看起来最后发生。

测试基础设施

这个实验室有两套测试台：功能测试台和调度测试台。

功能测试台将您的 FIFO 实现与参考 FIFO 进行比较。测试台随机入队和出队数据，并确保两个 FIFO 的所有输出结果相同。这些参考 FIFO 是作为内置 BSV FIFO 的包装实现的。

调度测试台的工作方式与迄今为止的所有其他测试台不同。调度测试台不是用来运行的，它们只是用来编译的。这些测试台强制执行您的 FIFO 应该能够满足的调度。如果测试台编译时没有警告，则您的 FIFO 能够满足这些调度，并且它们通过了测试。如果您的 FIFO 无法满足调度，将在编译期间产生编译器警告或错误。这些信息将表明两个规则在测试台中不能一起触发，或者某些规则的条件取决于该规则的触发。

查看编译器输出时，确保通过找到显示

code generation for <module_name> starts

的行来查看哪个模块导致了错误。由于 Bluespec 编译器的使用方式，无论何时构建一个测试台，都会部分编译所有测试台，因此您可能会看到与您当前不关注的模块相关的警告。

实现 N 元素 FIFOs

有冲突的 FIFOs

首先，您将实现一个只使用寄存器的 N 元素 FIFO。这将导致 enq 和 deq 发生冲突，但它将为所有后续的 FIFO 设计提供一个起点。

练习 1（5 分）：在 MyFifo.bsv 中实现 mkMyConflictFifo。您可以通过运行以下命令来构建和运行功能测试台
$ make conflict
$ ./simConflictFunctional
由于预期 enq 和 deq 会发生冲突，因此此模块没有调度测试台。

现在我们已经有了一个初始的有冲突 FIFO，我们将看看它的冲突并构建它的冲突矩阵。

讨论问题 1（5 分）：每个接口方法中都读取和写入了哪些寄存器？记住，守卫中进行的寄存器读取也算数。

讨论问题 2（5 分）：为 mkMyConflictFifo 填写冲突矩阵。为简化起见，将对同一寄存器的写入视为冲突（不仅仅是在单个规则内冲突）。

流水线和旁路 FIFOs

流水线和旁路 FIFO 是有冲突 FIFO 的下一步。流水线和旁路 FIFO 通过声明它们与它们各自的方法之间的固定顺序，使并发入队和出队成为可能。

流水线 FIFO 具有以下调度注释。

{notEmpty, first, deq} < {notFull, enq} < clear

旁路 FIFO 具有以下调度注释。

{notFull, enq} < {notEmpty, first, deq} < clear

用 EHRs 创建排序关系

有一个结构化的程序可以使用 EHRs 从一个有冲突的设计中获取这些调度注释。

用 EHRs 替换有冲突的寄存器。
分配 EHRs 的端口以匹配所需的调度。第一组方法访问端口 0，第二组访问端口 1，等等。

例如，要获取调度注释

{notEmpty, first, deq} < {notFull, enq} < clear

首先将阻止上述调度注释的寄存器替换为 EHRs。在这种情况下，包括 enqP, deqP, full, 和 empty。现在，分配 EHRs 的端口以匹配所需的调度。{notEmpty, first, deq} 都获得端口 0，{notFull, enq} 获得端口 1，而 clear 获得端口 2。你可以通过减少未使用端口的 EHRs 的大小来稍微优化这个设计，但这对于本实验室的目的并不必要。

练习 2（10 分）：在 MyFifo.bsv 中使用上述方法和 EHRs 实现 mkMyPipelineFifo 和 mkMyBypassFifo。您可以通过运行以下命令来构建流水线 FIFO 和旁路 FIFO 的功能和调度测试台
$ make pipeline
和
$ make bypass
分别。如果这些编译没有调度警告，那么调度测试台通过了，这两个 FIFO 具有预期的调度行为。要测试它们的功能是否符合参考实现，你可以运行
$ ./simPipelineFunctional
和
$ ./simBypassFunctional
如果您在实现 clear 时遇到符合正确的调度和功能的困难，您可以通过将 has_clear 设置为 false 来暂时从关联模块中的 TestBench.bsv 中删除它。

无冲突 FIFOs

无冲突 FIFO 是最灵活的 FIFO。它可以放置在处理器流水线中，而不增加阶段之间的额外调度约束。无冲突 FIFO 的理想调度注释如下所示。

{notFull, enq} CF {notEmpty, first, deq}
{notFull, enq, notEmpty, first, deq} < clear

选择 clear 方法不与 enq 和

deq 无冲突，因为它在其他方法之前被赋予了优先权。如果 clear 和 enq 在同一个周期内发生，clear 方法将有优先权，并且在下一个周期 FIFO 将为空。要匹配使用方法顺序的行为，clear 在 enq 和 deq 之后。

使用 EHRs 创建无冲突的调度

就像为流水线和旁路 FIFOs 的程序一样，有一个程序可以使用 EHRs 获取所需的无冲突调度注释。

对于每个需要与另一方法无冲突的有冲突的 Action 和 ActionValue 方法，添加一个 EHR 来表示对该方法的调用请求。如果方法没有参数，EHR 中的数据类型应该是 Bool（True 表示请求，False 表示无请求）。如果方法有一个类型为 t 的参数，则 EHR 的数据类型应该是 Maybe#(t)（tagged Valid x 表示带参数 x 的请求，tagged Invalid 表示无请求）。如果方法有类型为 t1, t2 等的参数，则 EHR 的数据类型应该是 Maybe#(TupleN#(t1,t2,...))。
用新添加的 EHR 替换每个有冲突的 Action 和 ActionValue 方法中的动作。
创建一个规范化规则，从 EHRs 中获取请求并执行每个方法中曾经的动作。这个规范化规则应该在每个周期结束后触发，所有其他方法之后。

使用编译器属性强制规则触发

BSV 没有强制规范化规则每个周期都触发的方法，但它可以在编译时静态检查它是否会在每个周期触发。通过使用编译器属性，你可以向 Bluespec 编译器添加有关模块、方法、规则或函数的额外信息。你已经看到了 (* synthesize *) 属性，现在你将学习另外两个用于规则的属性。

正如你所知，规则或方法的守卫是显式守卫和隐式守卫的组合。属性 (* no_implicit_conditions *) 放在规则前面，告诉编译器你不希望规则体中有任何隐式守卫（编译器称守卫为条件）。如果你错了，并且规则中确实存在隐式守卫，编译器将在编译时抛出错误。这个守卫充当了断言，即 CAN_FIRE 等于显式守卫。

另一阻止规则触发的可能是与其他规则和方法的冲突。属性 (* fire_when_enabled *) 放在一个规则前面，告诉编译器只要规则的守卫满足，规则就应该触发。如果存在守卫满足而规则不触发的情况，那么编译器会在编译时抛出错误。这个守卫充当了断言，即 WILL_FIRE 等于 CAN_FIRE。

这两个属性一起使用会断言只要你的显式守卫为真，规则就会触发。如果你的显式守卫是真（或为空），那么它就断言规则将在每个周期触发。下面是两个属性一起使用的例子：

(* no_implicit_conditions *)
(* fire_when_enabled *)
rule firesEveryCycle;
    // 规则体
endrule

(* no_implicit_conditions, fire_when_enabled *)
rule alsoFiresEveryCycle;
    // 规则体
endrule

如果规则 fireEveryCycle 实际上不能每个周期都触发，Bluespec 编译器将抛出错误。你应该将这些属性放在你的规范化规则之上，以确保它每个周期都触发。

讨论问题 3（5 分）：使用 mkMyConflictFifo 的冲突矩阵，哪些冲突不符合上述无冲突 FIFO 的调度约束？

练习 3（30 分）：按照上述描述实现 mkMyCFFifo，但不包括 clear 方法。您可以通过运行以下命令构建功能和调度测试台
$ make cfnc
如果这些编译没有调度警告，那么调度测试台通过了，FIFO 的 enq 和 deq 方法可以以任何顺序调度。（如果有警告说规则 m_maybe_clear 没有动作将被移除，也是可以接受的。）你可以通过运行以下命令来运行功能测试台
$ ./simCFNCFunctional

向无冲突 FIFO 添加 clear 方法

添加 clear 方法增加了设计的复杂性。它需要调度约束来防止 clear 在 enq 和 deq 之前被调度，但它不能与规范化规则发生冲突。

创建方法之间调度约束的最简单方法之一是让一个方法写入 EHR，另一个方法从 EHR 的后面端口读取。在这种情况下，你应该能够使用现有的 EHR 来强

使用编译器属性强制规则触发

(* no_implicit_conditions *)
(* fire_when_enabled *)
rule firesEveryCycle;
    // 规则体
endrule

(* no_implicit_conditions, fire_when_enabled *)
rule alsoFiresEveryCycle;
    // 规则体
endrule

讨论问题 3（5 分）：使用 mkMyConflictFifo 的冲突矩阵，哪些冲突不符合上述无冲突 FIFO 的调度约束？

练习 3（30 分）：按照上述描述实现 mkMyCFFifo，但不包括 clear 方法。您可以通过运行以下命令构建功能和调度测试台
$ make cfnc
如果这些编译没有调度警告，那么调度测试台通过了，FIFO 的 enq 和 deq 方法可以以任何顺序调度。（如果有警告说规则 m_maybe_clear 没有动作将被移除，也是可以接受的。）你可以通过运行以下命令来运行功能测试台
$ ./simCFNCFunctional

向无冲突 FIFO 添加 clear 方法

添加 clear 方法增加了设计的复杂性。它需要调度约束来防止 clear 在 enq 和 deq 之前被调度，但它不能与规范化规则发生冲突。

创建方法之间调度约束的最简单方法之一是让一个方法写入 EHR，另一个方法从 EHR 的后面端口读取。在这种情况下，你应该能够使用现有的 EHR 来强

制这种调度约束。

练习 4（10 分）：向 mkMyCFFifo 添加 clear() 方法。它应该在所有其他接口方法之后，并在规范化规则之前。您可以通过运行以下命令构建功能和调度测试台
$ make cf
如果这些编译没有调度警告，则调度测试台通过，FIFO 具有预期的调度行为。你可以通过运行
$ ./simCFFunctional
来运行功能测试台。

讨论问题 4（5 分）：在设计 clear() 方法时，您是如何强制执行调度约束 {enq, deq} < clear 的？

讨论问题 5（可选）：您花了多长时间完成这个实验室？

| MIT6.175 Labs Instruction |