[科普中国]-硬件算法

定义

硬件算法这个术语是随着大规模集成电路的发展而出现的，但最初不过是逻辑设计的同义语，它描述逻辑设计问题的解决步骤和实现方法。随着逻辑设计的规模越来越大，越来越复杂，硬件实现本身又具有较大的灵活性和自由度，硬件算法作为单独的研究对象出现在设计自动化领域。1

硬件算法则是以硬件的物理实现为前提。对于一个具体的设计问题，如何实现所要求的的功能，应该由哪些部件组成，如何组织各个部件，各个部件之间应有什么样的相互关系，如何实现对各个部件的控制等，用形式的方法把实现方法描述出来，就是硬件算法。1

硬件算法涉及到数字系统的各个设计级别，上至系统结构，下至门级。硬件算法的研究，必将使硬件设计更加科学化、合理化、形式化。它有利于实现系统设计到逻辑设计的自动化，有利于将现有的软件系统做成专用硬件。今后，硬件算法的研究必将在设计自动化系统的研究领域中占据重要的地位。1

设计与分析与软件算法相类似，解决同一个问题，可以有不同的算法，又可以有不同的实现方法。比如我们要设计一个乘法器，可以有串行进位、位移加法的算法，并行进位、位移相加的算法，阵列相乘，冗余二进制并行算法等。而同一算法又可以用组合逻辑、PLA、单元阵列、积木式等各种电路结构来实现，芯片类型还可以有TTL、MOS、CMOS等等。1

硬件算法的设计和分析撇开具体电路的实现，仅对于较抽象的功能实现方法进行研究。一种情况是，在给定硬件实现环境的条件下要求找出适合于该实现环境的最好的硬件算法。另一种情况是，对于一个带有普遍性的实际设计问题，比较其多种不同的算法，分析它们的优缺点并研究新的效率更高的算法。电路实现可以从中选择最好的最实用的的一种。1

描述方法与软件算法类似，硬件算法也有各种描述方法：
（1）自然语言；

（2）数学模型；

（3）硬件描述语言；

（4）流程图；

（5）逻辑图。1

硬件算法与逻辑设计两个方面的研究在逻辑设计中，硬件算法的研究有两方面：

（1）为满足逻辑设计要求、选择所用的计算模型、开发实际系统而预先设计硬件算法；

（2）对某个问题的解决方法做原理性研究，分析评价已有算法，并以实现化为目的研究效率更高的硬件算法。1

与软件算法比较硬件算法与软件在形式上没有什么不同。实际上许多硬件算法都是从软件算法演变而来的，特别是软件硬件化的专用硬件，大都是以软件算法为基础的。1

分析与评价在硬件设计中要求有尽量高的性能和可靠性，尽量低的开销，因而要求能够对硬件算法的性能作定量的分析和评价。

在评价一个软件算法时，主要考虑计算时间和占用空间（存储量）。在硬件算法中同样要考虑计算时间和占用空间的问题，不过计算时间主要表现在输入端到输出端的延迟时间，而占用空间主要指芯片所需的面积，它主要取决于元件个数，每个元件占的面积，以及线长、线宽与间隔等。1

时间复杂度一般来说，设n为时间的规模（大小），计算时间关于n的函数称为时间复杂度。

对于一个排序问题，其计算时间显然是记录个数n的一个函数，在并行计算排序算法中，总的计算时间为2n。算法的时间复杂度T为O(n)数量级，即与记录个数成正比。1

面积复杂度一般来说，设n为时间的规模（大小），而占用的芯片面积关于n的函数称为面积复杂度。

在影响面积复杂度的诸因素中，无疑元件个数是最重要的，因而常用元件个数作为面积的度量。在排序算法中，对于n个记录，就需要n个单元，因而面积复杂度A=O(n)，即面积也与记录成正比。1

面积时间复杂度时间复杂度与面积复杂度常常相互影响。串行进位加法器计算时间长，元件个数少。并行进位加法器提高了计算速度，却增加了元件个数，因而增加了面积。为此常把时间复杂度T与面积复杂度A综合考虑，形成复合评价尺度，称为面积时间复杂度。二者的不同组合可以得到不同的面积时间复杂标准。最常见的有AT，（或）。1