组合电路

构造性计算机体系结构

组合电路

Arvind 教授麻省理工学院计算机科学与人工智能实验室

日期：2016年9月9日网址：http://csg.csail.mit.edu/6.175

本章介绍了组合电路的设计，尤其是算术逻辑单元（ALU）的构建。让我们分步分析：

1. 组合电路基础

组合电路是一种没有回路的门电路的互连，包括AND、OR、NOT、XOR、NAND和NOR等基本逻辑门。这类电路的输出完全由当前输入决定，不涉及存储元件，因此输出随输入改变而实时变化。

2. 算术逻辑单元（ALU）

ALU是处理器的核心组件之一，负责执行基本的算术和逻辑操作。ALU的设计通常使用纯组合电路来实现，这意味着其操作基于当前的输入，不依赖于先前的状态。

3. 全加器和进位链加法器（Ripple-Carry Adder）

全加器是构建加法器的基本单元，可以同时处理两个输入位和一个进位输入，并产生一个和位与一个进位输出。通过将多个全加器级联，可以构建出处理多位数字的加法器，如进位链加法器。此加法器的特点是低位的进位输出将作为高位的进位输入，逐步向上串联。

4. BSV语言特点

BSV（Bluespec System Verilog）是一种用于硬件设计的强类型语言，其通过类型检查确保所有操作都具有明确的意义。BSV支持表达式共享和类型推断，这有助于简化硬件设计代码并优化最终的电路实现。

5. 组合ALU设计

组合ALU可以通过组合不同的算术和逻辑操作来构建，例如加法、减法、位运算等。在BSV中，可以使用条件表达式来表达不同的操作，并将它们组合成一个完整的ALU功能。

常见问题

如何确保ALU设计的效率和速度？
- 在设计组合ALU时，需要考虑电路的延迟和速度。例如，进位链加法器由于其串行进位特性，可能会导致较长的延迟。解决这个问题的一种方法是使用更高级的加法器设计，如并行加法器。
BSV语言如何处理类型安全？
- BSV通过强类型系统来避免常见的类型错误，例如隐式类型转换。这在硬件设计中尤其重要，因为错误的类型操作可能导致严重的硬件故障。
全加器与其他基本电路元件如何实现在BSV中？
- 在BSV中，全加器可以通过定义逻辑门操作（如AND、OR和XOR）来实现。BSV的表达式共享特性允许在不同部分的电路中重用相同的逻辑表达式，以减少硬件资源的消耗。

这一节课的内容主要集中在介绍和设计组合电路和算术逻辑单元（ALU）。

组合电路：
- 组合电路是由基本的逻辑门（如AND、OR、NOT）以非循环方式相互连接构成的。
- 讲解了如何使用这些逻辑门构建半加器和全加器，这些是构建更复杂组合电路的基本组件。
Bluespec System Verilog（BSV）：
- 介绍了BSV语言，这是一种专门用于硬件设计的高级硬件描述语言。
- 解释了BSV中的类型系统，包括枚举、类型定义、数值类型（如Int#(32)与无界整数Integer）、布尔类型与一位类型（Bool与Bit#(1)）和向量。
- 讲述了在BSV中如何通过参数化类型和类型同义词来创建灵活和可重用的代码。
- 展示了如何使用BSV中的let语法来简化代码，并避免显式声明类型。
- 强调了类型声明与类型推断的重要性，以及编译器在类型检查阶段如何捕捉类型错误。
静态展开阶段：
- 讨论了在BSV编译过程中的静态展开阶段，这一阶段涉及将程序中的抽象结构（如循环）转换为具体的硬件实现。
算术逻辑单元（ALU）：
- ALU是计算机中执行所有算术和逻辑运算的核心部件。
- 解释了ALU如何根据操作码执行不同的运算，并返回计算结果和比较结果。

课程内容的深入部分还包括了如何将数值从类型世界转换到值世界，如使用valueOf函数　　　　　　　　　　　　　　　　　，以及如何在类型层面上执行数学运算，如使用TAdd#等操作符。

总的来说，这节课为学生提供了硬件设计中组合电路的概念，以及如何在BSV语言中实现这些概念的细节，这对于理解现代处理器内部的算术逻辑单元的设计至关重要。

开始

构建性计算机架构

组合电路

Arvind 教授
麻省理工学院计算机科学与人工智能实验室

日期：2016年9月9日
网址：http://csg.csail.mit.edu/6.175

内容

设计一个从基本门电路And、Or和Not开始的组合ALU
组合电路作为基本门电路的非循环接线图
介绍BSV
- 类型介绍 — 枚举、类型定义、数值类型、Int#(32)与Integer、Bool与Bit#(1)、向量
- 简单操作：串联、条件判断、循环
- 函数
- 静态展开和文本代码的结构解释

组合电路是非循环的门电路互连

And、Or、Not
Nand、Nor、Xor
…

组合电路是逻辑门的互连，不包含循环路径，意味着它们不会存储任何历史状态，电路的输出完全取决于当前的输入。例如，And门会在两个输入都为真（1）时输出真（1），Or门则会在至少有一个输入为真时输出真，而Not门则将输入的逻辑状态取反。

半加器

半加器是实现二进制加法的最基本组件，它能够处理两个一位二进制数的加法。

输入: A、B - 输入位

输出: S - 和，C - 进位

布尔方程式：
S = (~a & b) | (a & ~b) ，C = a & b

优化后：
S = a ⊕ b ，C = a & b

半加器通过以下布尔逻辑实现两个一位二进制数的相加：

输出S（和）是输入A和B的异或（XOR）运算结果，当输入A和B不同时为1时输出1。
输出C（进位）是输入A和B的与（AND）运算结果，只有当A和B都为1时才会产生进位。

这种结构很简单，但构成了更复杂加法器的基础。例如，在全加器中，我们还会考虑低位的进位输入，而在构建多位数的加法器时，多个半加器可以级联使用，从而实现多位的二进制数相加。

全加器

全加器是二进制加法中能够考虑进位输入的基本单元。它能够处理两个一位二进制数以及一个进位输入，并产生一个和位与一个进位输出。

输入: A、B - 输入位，C_in - 进位输入

输出: S - 和，C_out - 进位输出

布尔方程式: \[ S = (\sim a \cdot \sim b \cdot C_{in}) + (\sim a \cdot b \cdot \sim C_{in}) + (a \cdot \sim b \cdot \sim C_{in}) + (a \cdot b \cdot C_{in}) \] \[ C_{out} = (\sim a \cdot b \cdot C_{in}) + (a \cdot \sim b \cdot C_{in}) + (a \cdot b \cdot \sim C_{in}) + (a \cdot b \cdot C_{in}) \]

优化后: \[ t = a \oplus b \] \[ S = t \oplus C_{in} \] \[ C_{out} = (a \cdot b) + (C_{in} \cdot t) \]

这些方程描述了全加器的逻辑功能，其中S是输出的和位，它由输入位A和B以及进位输入C_in的异或结果t再次与C_in进行异或运算得到。C_out是进位输出，它由A和B的与操作以及C_in和t的与操作后的结果进行或运算得到。

全加器：一个一位加法器

函数定义如下:

function fa(a, b, c_in);
  t = (a ^ b);
  s = t ^ c_in;
  c_out = (a & b) | (c_in & t);
  return {c_out, s};
endfunction

结构代码 - 只指定了boxes之间的互连。

这段代码尚未完全正确 - 需要类型标注。

在上面的代码中，函数fa定义了一个全加器，接收三个输入：a、b和c_in。首先计算t，它是输入a和b的异或结果。然后，s是t和进位输入c_in的异或结果，代表和位。c_out是输出的进位位，由a和b的与结果以及c_in和t的与结果进行或操作得到。最后，函数返回一个包含c_out和s的元组。在硬件设计中，这些操作将被翻译成门电路的互连。

请注意，这段代还需要类型标注，这是因为在硬件描述语言中，明确指定变量类型是重要的，这有助于编译器检查和优化生成的硬件电路。在编写实际的硬件描述代码时，开发者需要确保所有变量都有正确的类型声明。

全加器：一个一位加法器（修正版）

function Bit#(2) fa(Bit#(1) a, Bit#(1) b, Bit#(1) c_in);
  Bit#(1) t = a ^ b;
  Bit#(1) s = t ^ c_in;
  Bit#(1) c_out = (a & b) | (c_in & t);
  return {c_out, s};
endfunction

“Bit#(1) a” 类型声明表示a是一位宽的。
{c_out, s} 代表位串联。

问：{c_out, s} 有多大？
答：2位

在这段修正版的全加器BSV代码中，我们为每个输入和输出添加了明确的类型注解。例如，Bit#(1) 表明对应的变量是一位宽的二进制数。这种强类型声明有助于确保电路的每个部分都正确接收和处理适当宽度的信号。函数fa的返回类型Bit#(2)表明它返回一个由两个一位宽的二进制数串联而成的结果，即和位S和进位输出C_out。这两位可以表示四种可能的值（00、01、10、11），对应于全加器的两种输出状态。

类型

类型是一组值的集合：
- 整数：1, 2, 3, …
- 布尔值：真（True），假（False）
- 位元：0, 1
- 一对整数：Tuple2#(Integer, Integer)
- 一个从整数到整数的函数：function Integer fname(Integer arg);
BSV程序中的每个表达式都有一个类型；有时它是显式指定的，有时是由编译器推断的。
因此，我们说一个表达式有一个类型或属于一个类型
每个表达式的类型都是唯一的

在BSV这种硬件描述语言中，类型的概念对于编写高质量的代码来说非常重要。不同于某些软件编程语言，BSV中的每个值和表达式都必须有一个确切的类型。这种类型系统的严格性有助于减少错误，并能在编译阶段捕获到潜在的问题。对于硬件设计来说，这一点尤为重要，因为任何类型不匹配的错误都可能导致硬件行为异常。此外，BSV的类型系统还支持复杂的数据结构和函数类型，使得硬件逻辑能够以类似于软件的方式组织和抽象。

参数化类型

参数化类型的声明本身可以通过其他类型进行参数化。这些参数是通过使用#语法标识的。

例如Bit#(n)代表n位宽，可以通过指定n的值来实例化，如Bit#(1)、Bit#(32)、Bit#(8)等。

这表明在BSV中，您可以定义具有泛型参数的类型，这使得相同的类型声明可以用于创建不同大小的数据类型。这对于设计可重用和可扩展的硬件组件非常有用，因为您可以根据需要实例化不同宽度的数据类型，而不需要为每种大小重写类型定义。

类型同义词

typedef bit [7:0] Byte;  // 这两个声明是相同的
typedef Bit#(8) Byte;

typedef Bit#(32) Word;

typedef Tuple2#(a, a) Pair#(type a);

typedef Int#(n) MyInt#(type n);  // 这两个声明是相同的
typedef Int#(n) MyInt#(numeric type n);

这里展示了如何在BSV中创建类型同义词，使得开发者可以使用更有意义的类型名称，而不是每次都指定具体的类型范围或结构。例如，Byte可以用来代表一个8位宽的数据类型，而Word则代表一个32位宽的数据类型。这有助于提高代码的可读性和可维护性。

类型声明与推断

程序员在程序中指定一些表达式的类型，编译器推断其余表达式的类型。如果类型推断无法执行，或者类型声明不一致，编译器会报错。

function Bit#(2) fa(Bit#(1) a, Bit#(1) b, Bit#(1) c_in);
  Bit#(1) t = a ^ b;
  Bit#(1) s = t ^ c_in;
  Bit#(2) c_out = (a & b) | (c_in & t);  // 类型错误，编译器会报错
  return {c_out, s};
endfunction

类型检查可以防止许多简单错误。

在上述代码示例中，c_out的声明为Bit#(2)，但是基于它的计算表达式结果应该是Bit#(1)。这种不一致性将会导致编译器报错，因为我们尝试将两个Bit#(1)类型的值合并成一个Bit#(2)类型的值，但按照逻辑和电路设计，c_out只应该是一个位宽（Bit#(1)）。这种类型系统确保了硬件描述的正确性和一致性，是硬件设计中确保电路设计正确性的关键部分。

2位进位链加法器

function Bit#(3) add(Bit#(2) x, Bit#(2) y, Bit#(1) c0);
  Bit#(2) s = 0;
  Bit#(3) c = {?,c0};
  
  let cs0 = fa(x[0], y[0], c0);
  c[1] = cs0[1]; s[0] = cs0[0];
  
  let cs1 = fa(x[1], y[1], c[1]);
  c[2] = cs1[1]; s[1] = cs1[0];
  
  return {c[2], s};
endfunction

只要我们了解 fa 的类型签名，就可以将其用作黑盒

“let” 语法避免了显式写下类型。

在这段代码中，add 函数定义了一个2位进位链加法器，它接受两个2位输入x和y，以及一个初始进位输入c0。使用“let”语法可以避免在代码中多次重复类型声明，编译器可以推断出cs0和cs1的类型。每次调用全加器fa时，都会处理一位输入并产生相应的和位和进位。最后，函数返回一个包含最终进位和2位和的结果。

“let” 语法

let cs0 = fa(x[0], y[0], c0);

“let” 语法：如果编译器可以推断出类型，就无需写明类型。

Bit#(2) cs0 = fa(x[0], y[0], c0);  // 与上面声明相同

“let” 语法允许开发者在编写代码时省略变量类型的显式声明，这样可以让代码更加简洁。编译器会自动推断变量的类型，这不仅减少了编码工作量，还可以减少因显式类型声明错误导致的编程错误。

选择导线：x[i]

常数选择器：例如，x[2]

假设x为4位宽。

x[2]

没有硬件; x[2]只是导线名称的一部分。

在这个例子中，使用方括号和索引来选择多位数字中的特定位。例如，x[2]表示选择变量x的第二位。在硬件电路中，这不需要额外的硬件，只需要连接指定的导线。

动态选择器：x[i]

x[i]

这需要4路复用器。

而在动态选择器的例子中，索引i是可变的，所以需要一个多路复用器（在这个例子中是4路复用器）来根据索引值动态选择导线。这是硬件实现中一个更复杂的结构，通常用于例如寄存器文件或者内存访问中，允许动态地根据索引信号选择导线。

两路多路复用器

两路多路复用器根据单一的选择信号 S 来选择两个输入 A 或 B 中的一个作为输出。

如果选择信号 (S==0)，则输出 A；
否则，输出 B。

条件表达式也可以使用多路复用器来实现。例如，在编程中，我们经常使用 ?: 操作符，其在硬件中的对应实现就是多路复用器。

门级实现显示了如何通过AND和OR逻辑门构造这样的多路复用器。当 S 为真时，B 被传递，而 S 为假时，则 A 被传递。

四路多路复用器

四路多路复用器可以根据两个选择信号 s1, s0 的组合从四个输入 A, B, C, D 中选择一个作为输出。

case {s1, s0} matches
  0: A;
  1: B;
  2: C;
  3: D;
endcase

在这个结构中，{s1, s0} 能够代表四种状态（00, 01, 10, 11），并对应地选择四个输入中的一个。这在硬件描述语言中通常通过 case 语句来实现，是一种在硬件设计中常用来根据多个选择信号动态选取输入的方式。

w位进位链加法器

function Bit#(w+1) addN(Bit#(w) x, Bit#(w) y, Bit#(1) c0);
  Bit#(w) s; Bit#(w+1) c = 0; c[0] = c0;
  for(Integer i = 0; i < w; i = i + 1)
  begin
    let cs = fa(x[i], y[i], c[i]);
    c[i+1] = cs[1]; s[i] = cs[0];
  end
  return {c[w], s};
endfunction

注释：这不完全正确，需要展开循环来获取连线图。

上面的函数 addN 描述了一个可参数化位宽的进位链加法器的实现，它使用了 for 循环来逐位计算和和进位。循环中的每一次迭代都调用全加器 fa 并处理当前位以及进位。这个实现可能不完全正确，因为在某些硬件描述语言（HDL）中，可能需要将循环结构展开以形成一个详细的硬件连线图，而不是用抽象的循环表达式。

实例化参数化加法器

function Bit#(w+1) addN(Bit#(w) x, Bit#(w) y, Bit#(1) c0);

// 具体实例化addN的例子
function Bit#(33) add32(Bit#(32) x, Bit#(32) y, Bit#(1) c0) = addN(x,y,c0);

function Bit#(4) add3(Bit#(3) x, Bit#(3) y, Bit#(1) c0) = addN(x,y,c0);

代码展示了如何根据参数化加法器函数 addN 的定义，实例化具体位宽的加法器。这里定义了两个加法器实例：add32 是一个32位加法器，add3 是一个3位加法器。

代码显示了如何通过改变参数 w 的值来实现不同大小的加法器，这是通过在函数调用时传递具体的位宽值来完成的。在硬件描述语言中，这种方法允许设计者编写可重用的组件，这些组件可以用于多种不同的上下文和位宽，而不需要为每种情况重新编写代码。

valueOf(w) 与 w

每个表达式都有一个类型和一个值，它们来自两个完全不同的领域。
在Bit#(w)中的w位于类型世界（types world）中。
有时我们需要将类型世界中的值用于实际计算，例如，i<w，但这并不是类型正确的。
函数valueOf允许我们将一个数值类型提升为一个值。
- 使得i<valueOf(w)类型正确。

这里提到的类型世界和值世界的区别在于硬件描述语言中的类型系统。类型世界指的是类型本身的声明和操作，而值世界则是实际计算时使用的数值。valueOf 函数是一种机制，允许我们将类型参数（如类型宽度）转换成可用于计算的实际数值。这是硬件描述语言中处理参数化类型时非常重要的特性。

TAdd#(w,1) 与 w+1

有时我们需要在类型世界中执行与值世界中非常相似的操作。
- 例如：加法（Add）、乘法（Mul）、对数（Log）。
我们在类型世界中为这些操作定义了一些特殊的运算符。
- 例如：TAdd#(m,n)，TMul#(m,n)等。

在这一部分中，TAdd# 和 TMul# 是在类型层面上进行数学运算的特殊运算符。它们允许设计者在声明类型大小时执行加法和乘法运算，这些计算是在编译时进行的，而不是在硬件实际运行时。这种能力在设计可以适应不同尺寸输入的通用硬件组件时尤其重要。

整数与Int#(32)

在数学中，整数是无界限的，但在计算机系统中，整数始终具有固定大小。
BSV允许我们表达这两种类型的整数，尽管无界限的整数仅作为编程方便而使用。

for(Integer i = 0; i < valw; i = i + 1)
begin
  let cs = fa(x[i], y[i], c[i]);
  c[i + 1] = cs[1]; s[i] = cs[0];
end

在数学中，整数是没有上下限的，可以是任何大小。然而，在计算机中，由于存储和处理的限制，我们使用有固定位宽的整数表示，例如32位的Int#(32)。在BSV中，Integer类型表示一个无界限的整数，通常用于循环的索引或编程中的计数等，而Int#(32)等类型则用于表示固定位宽的整数。

已修正的w位进位链加法器

function Bit#(TAdd#(w,1)) addN(Bit#(w) x, Bit#(w) y, Bit#(1) c0);
  Bit#(w) s; Bit#(TAdd#(w,1)) c; c[0] = c0;
  let valw = valueOf(w);
  for(Integer i = 0; i < valw; i = i + 1)
  begin
    let cs = fa(x[i], y[i], c[i]);
    c[i + 1] = cs[1]; s[i] = cs[0];
  end
  return {c[valw], s};
endfunction

在代码循环中，TAdd#(w,1) 和 valueOf(w) 都是BSV中类型运算和值转换的例子，TAdd#(w,1) 在类型层面上将w加1，而valueOf(w) 将类型w转换为循环中可以使用的数值。这种方法允许BSV代码在描述硬件行为时保持类型安全，同时提供了编程时的灵活性。这里展示的代码需要正确地将循环展开，以生成一个无循环的图表，这对于生成可实现在硬件上的电路至关重要。

让我们一步一步解析这段BSV代码，它定义了一个参数化的w位进位链加法器。

function Bit#(TAdd#(w,1)) addN(Bit#(w) x, Bit#(w) y, Bit#(1) c0);

这行声明了一个函数 addN，它返回 TAdd#(w,1) 类型的值，即它返回一个比输入位宽 w 大一位的二进制数。这是因为加法可能产生进位，导致结果比最大的输入数多一位。参数 Bit#(w) x 和 Bit#(w) y 是两个要相加的w位宽的二进制数，Bit#(1) c0 是初始进位输入。

  Bit#(w) s; Bit#(TAdd#(w,1)) c; c[0] = c0;

这里声明了两个变量 s 和 c。s 用于存储加法的结果，c 用于存储从每一位加法产生的进位。然后，将 c0（初始进位值）赋值给 c 数组的第一个元素。

  let valw = valueOf(w);

通过 valueOf 函数将类型参数 w 转换为可以用于实际计算的整数值，用于控制循环的迭代次数。

  for(Integer i = 0; i < valw; i = i + 1)
  begin
    let cs = fa(x[i], y[i], c[i]);

开始一个循环，遍历每一位进行加法运算。每次迭代都调用 fa 函数（即全加器），处理两个输入 x[i] 和 y[i]，以及上一位的进位 c[i]。

    c[i + 1] = cs[1]; s[i] = cs[0];
  end

fa 函数返回一个包含两个位的元组，第一个位 cs[0] 是当前位的和，赋值给 s[i]；第二个位 cs[1] 是当前位的进位，赋值给下一位的进位 c[i + 1]。

  return {c[valw], s};
endfunction

循环结束后，函数返回一个包含总进位 c[valw]（即最后一个进位值，可以是最高位的进位）和所有位的和 s 的元组。

总体来说，这个函数通过逐位计算并处理进位，实现了一个完整的参数化的进位链加法器，能够处理任意位宽的二进制加法运算。

静态展开阶段

当BSV程序编译时，首先进行类型检查，然后编译器会消除许多没有直接硬件意义的构造，如整数和循环。

for(Integer i = 0; i < valw; i = i + 1) begin
  let cs = fa(x[i], y[i], c[i]);
  c[i+1] = cs[1]; s[i] = cs[0];
end

被展开为：

cs0 = fa(x[0], y[0], c0); c[1] = cs0[1]; s[0] = cs0[0];
cs1 = fa(x[1], y[1], c[1]); c[2] = cs1[1]; s[1] = cs1[0];
...
csw = fa(x[valw-1], y[valw-1], c[valw-1]); c[valw] = csw[1]; s[valw-1] = csw[0];

这里描述的是硬件设计中的一个关键过程，称为静态展开。在编译阶段，复杂的结构（如循环和递归）将被转换成简单的、非循环的硬件电路。这意味着循环中的每次迭代都被转换为一组独立的硬件实现。

算术逻辑单元（ALU）

算术逻辑单元（ALU）执行所有的算术和逻辑函数。

操作码（Op）
- 加法（Add）、减法（Sub）…
- 与（And）、或（Or）、异或（Xor）、非（Not）…
- 大于（GT）、小于（LT）、等于（EQ）、零（Zero）…
结果（Result）
比较（Comp）？

每个独立的功能都可以描述为一个组合电路。

ALU是计算机中用于进行算术运算（如加减乘除）和逻辑运算（如与或非异或）的关键硬件组件。操作码指定了ALU应执行的具体操作，而输入A和B是执行这些操作的数据。ALU不仅返回计算结果，还可以返回比较标志或其他状态信息（如溢出指示），依此来指导程序的下一步行为。每个ALU的操作都可以使用基本的逻辑门（如AND、OR、NOT）来实现，从而构建出能够执行复杂运算的组合逻辑电路。

移位操作符

在计算机硬件和编程中，移位操作符用于将二进制数字向左或向右移动一定数量的位。这些操作对于位级别的数值操作非常重要，常用于乘除运算、位字段提取和调整数值的大小。

逻辑右移2位

固定大小的移位操作在硬件中是廉价的——只需要适当地连接电路：

例如，对于一串比特 a,b,c,d，逻辑右移2位意味着原本在 a 和 b 位置的比特现在会移到输出的最右边两位，而最左边两位会填充为0（如上图所示）。

无论是旋转、带符号扩展的移位，都同样容易实现。

条件操作：移位与不移位

为了在硬件中实现可选择的移位或不移位操作，我们需要一个多路复用器来选择适当的线路：

如果选择信号 s 为0，多路复用器会选择左边的线路；
否则，它会选择右边的线路。

例如，表达式 (s==0) ? {a,b,c,d} : {0,0,a,b}; 表示如果 s 为0，输出为 a,b,c,d，否则输出为 0,0,a,b，相当于将输入数据向右逻辑移位两位。

逻辑右移n位

逻辑右移 n 位可以通过 log n 步骤的固定长度移位来分解，这些步骤的大小分别为1、2、4等：

例如，移位3可以通过执行一个移位2和一个移位1来完成。
我们需要一个多路复用器来省略特定大小的移位。
移位电路可以表示为 log n 嵌套的条件表达式。

在这种情况下，如果需要根据变量 n 执行移位操作，可以通过一系列的嵌套条件表达式来逐步执行移位，每个条件表达式都对应一个固定大小的移位步骤，而多路复用器用于控制是否执行每个步骤。通过这种方式，可以灵活地构建复杂的移位操作电路。

关于类型的题外话

假设我们有一个变量 c，其值可以代表三种不同的颜色：

我们可以声明 c 的类型为 Bit#(2) 并规定 00 代表红色（Red），01 代表蓝色（Blue）和 10 代表绿色（Green）。
更好的方法是创建一个名为 Color 的新类型，如下所示：

typedef enum {Red, Blue, Green} Color deriving (Bits, Eq);

编译器将自动为这三种颜色分配一些位表示，并且提供一个函数来测试两种颜色是否相等。如果你不使用 “deriving”，那么你将需要指定表示和等价性。

类型防止我们混淆表示颜色的位和原始的位。

在硬件描述语言中，创建枚举类型可以让我们以更有意义的方式来表达一组值，例如颜色或操作码。使用枚举类型可以提高代码的可读性和维护性，并防止将数据错误地解释为非预期的类型。

枚举类型

typedef enum {Red, Blue, Green} Color deriving (Bits, Eq);
typedef enum {Eq, Neq, Le, Lt, Ge, Gt, AT, NT} BrFunc deriving (Bits, Eq);
typedef enum {Add, Sub, And, Or, Xor, Nor, Slt, Sltu, LShift, RShift, Sra} AluFunc deriving (Bits, Eq);

每种枚举类型定义了一个新的类型。

这些枚举类型示例显示了如何在BSV中定义一组具体的命名值。使用 “deriving” 关键字表示这些枚举类型可以派生出位表示（即每个枚举值都可以对应一个唯一的位模式）和相等性比较（可以使用 == 和 != 来比较这些枚举值）。这种枚举类型特别适用于定义一组固定的选项，如 ALU 操作码，这些操作码可以直接映射到硬件操作。

算术逻辑单元（ALU）

算术逻辑单元（ALU）执行所有的算术和逻辑函数。

操作码（Op）
- 加法（Add）、减法（Sub）…
- 与（And）、或（Or）、异或（Xor）、非（Not）…
- 大于（GT）、小于（LT）、等于（EQ）、零（Zero）…
结果（Result）
比较（Comp）？

每个独立的功能都可以描述为一个组合电路。

组合ALU（Arithmetic-Logic Unit）

function Data alu(Data a, Data b, AluFunc func);
  Data res = case(func)
    Add    : (a + b);
    Sub    : (a - b);
    And    : (a & b);
    Or     : (a | b);
    Xor    : (a ^ b);
    Nor    : ~(a | b);
    Slt    : zeroExtend(pack(signedLT(a, b)));
    Sltu   : zeroExtend(pack(a < b));
    LShift : (a << b[4:0]);
    RShift : (a >> b[4:0]);
    Sra    : signedShiftRight(a, b[4:0]);
  endcase;
  return res;
endfunction

这个函数 alu 描述了一个组合算术逻辑单元，可以执行多种算术和逻辑操作。每种操作由 AluFunc 类型的参数 func 指定。例如，当 func 为 Add 时，alu 函数返回输入 a 和 b 的和；当 func 为 Sub 时，返回它们的差；对于逻辑操作，如 And、Or 和 Xor，分别返回它们的与、或和异或结果。移位操作则由 LShift、RShift 和 Sra 实现，这些操作根据 b 的最低5位来决定移位的数量。如果我们有了像 addN、Shift 等基本操作的实现，那么可以通过引入由 op 控制的多路复用器（mux）简单地实现 alu。

比较操作符

function Bool aluBr(Data a, Data b, BrFunc brFunc);
  Bool brTaken = case(brFunc)
    Eq  : (a == b);
    Neq : (a != b);
    Le  : signedLE(a, b);
    Lt  : signedLT(a, b);
    Ge  : signedGE(a, b);
    Gt  : signedGT(a, b);
    AT  : True;
    NT  : False;
  endcase;
  return brTaken;
endfunction

aluBr 函数实现了ALU中的比较操作。它使用 BrFunc 类型的参数 brFunc 来选择具体的比较操作。比如，Eq 检查 a 和 b 是否相等，Neq 检查它们是否不等，Le、Lt、Ge 和 Gt 分别执行有符号的小于等于、小于、大于等于和大于比较。AT 和 NT 是总是返回真或假的特殊情况。

包含比较操作符的ALU

ALU不仅包括算术和逻辑操作，还包括比较操作。在ALU的实现中，我们可以使用多路复用器（如图中所示的 mux）来根据操作码选择相应的运算或比较逻辑电路。例如，如果 func 指示执行加法，则多路复用器将连接加法电路；如果 brFunc 指示进行等于比较，则另一个多路复用器将连接等于比较电路。这种设计允许ALU灵活地根据指令需求执行不同的操作。

复杂组合电路

在计算机架构中，复杂组合电路是由多个基本逻辑门或电路组合在一起执行复杂逻辑功能的电路。它们没有存储元素，所以输出仅由当前输入决定。

通过重复加法的乘法

这张图展示了如何使用重复加法来实现乘法。乘数和被乘数的每一位相乘，然后这些部分产品根据它们的权重（即对应的位位置）相加，以得到最终的乘法结果。

组合32位乘法

function Bit#(64) mul32(Bit#(32) a, Bit#(32) b);
  Bit#(32) tp = 0; Bit#(32) prod = 0;
  for(Integer i = 0; i < 32; i = i+1)
  begin
    Bit#(32) m = (a[i]==0) ? 0 : b;
    Bit#(33) sum = add32(m, tp, 0);
    prod[i] = sum[0];
    tp = sum[32:1];
  end
  return {tp, prod};
endfunction

这个函数 mul32 实现了一个32位的组合乘法器。tp（临时产物）和prod（最终产品）被初始化为0。对于每个a的位i，如果a[i]为0，则乘数m为0；否则，m为b。然后，m和tp通过add32（一个32位加法器函数）相加，结果的最低位赋值给prod[i]，其余位赋值给tp以用于下一次迭代。最后，返回tp和prod的组合，这代表乘法的完整结果。

组合乘法的设计问题

使用了大量的硬件：32位乘法使用了31个add32电路。
长的门延迟链：32位进位链加法器有31个门的长链，32位乘法器按顺序有31个进位链加法器！总延迟是多少？

组合电路的速度由最长的输入到输出路径决定。这导致在设计大型组合电路时，必须仔细考虑延迟和硬件资源的问题。需要考虑是否可以通过顺序电路或带有状态的电路来改善设计。

Table of contents

组合电路
开始