【封面文章】基于Dais-CMX模型机的斐波那契数列指令集设计

2017-08-03 高俊杰 计算机教育

2017年《计算机教育》第7期封面文章

0 引言

13 世纪，意大利数学家斐波那契在《算盘书》的修订版中加入了一道著名的兔子繁殖问题：假设一对兔子要一个月才能到成熟期，而一对成熟的兔子每月会生一对兔子，那么由一对初生兔子开始，12 个月会有多少对兔子呢？从第一个月到第十二个月兔子的对数分别是：2,3,5,8,13,21,34,55,89,144……，这个数列被称为斐波那契数列^[1]。

斐波那契数列在数学、物理、化学、生物、计算机科学中都发挥着极为重要的作用。为此，美国数学会从1960 年代起出版了《斐波纳契数列》季刊，专门刊载这方面的研究成果。科学家发现，一些植物的花瓣、萼片、果实的数目以及排列方式也与斐波那契数列有着惊人的相似。1992 年，两位法国科学家通过对花瓣形成过程的计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列长出花瓣^[2]。在计算机科学中，斐波那契堆（Fibonacci heap）是最小堆有序树的集合，它和二项式堆有类似的性质，可用于实现合并优先队列。近年来在计算机领域，基于斐波那契数列的研究层出不穷，如基于斐波那契数列的指纹增强方向滤波模板^[3]、基于斐波那契数列采样的BP 神经网络金融时间序列短期趋势预测^[4] 等都运用了斐波那契数列的运算。

在现代计算机系统中，利用高级语言可以设计出多种计算斐波那契数列的算法，如递推算法^[5]、特征方程求解法^[5]、矩阵幂运算加速算法^[6] 等，但这些基于高级语言的算法，在实现时需要调用众多指令，需要较为庞大的指令系统支持。为了简化斐波那契数列的计算过程，提高运算速度，笔者基于Dais-CMX 模型机硬件底层微程序，设计出一个经过简化的计算斐波那契数列的指令集，利用寄存器寻址、寄存器间接寻址、指令的跳转^[7]等硬件功能相互组合，融合软件技术中的指针概念，最终实现本设计。斐波那契数列指令集适用于Dais-CMX 模型机系统，通过7 条指令完成数列的计算，相比于大多数软件算法，在性能上有较大提高。

1 问题描述

斐波那契数列的计算可以通过软件方法或硬件方法进行设计。

1.1 软件设计方法及性能分析

斐波那契数列可以用软件设计方法中的递推法实现。递推法是迭代算法的一种，其基本思想是用若干步可重复的简单运算描述复杂的数学问题，以便于计算机处理。这种方法的求解过程与递推关系的思想完全一致，由边界条件开始往后逐个推算^[5]。

斐波那契数列的递推关系：

从递推关系公式（1）可以看出，斐波那契数列第一项为0，第二项为1，其后各项为前两项之和。根据这一条件，可以归纳出该算法的时间复杂度为O(n) 44 33310 44 14941 0 0 3949 0 0:00:08 0:00:03 0:00:05 3949

斐波那契数列伪代码如下：

斐波那契数列用C 语言编制程序，其代码如下：

高级语言有着较强的可读性和算法描述能力，与此同时隐藏了许多硬件的实现细节，通过汇编语言可以体现出程序的硬件实现过程。递推法汇编语言部分代码如下：

由汇编语言代码可知，一个采用递推算法的程序在实际运行时至少调用了20 次关键指令，因此，斐波那契数列的计算需要进行20 多次关键指令的操作才能完成。

1.2 硬件设计分析

基于硬件设计，其可靠性、计算速度都远胜于软件算法。在硬件底层实现斐波那契数列的计算，可以简化计算过程，提高计算速度。为便于设计，我们将寄存器间接寻址作为软件技术中的指针使用。表1 对斐波那契数列硬件实现过程进行了描述：①在Step1 中，R1 和R2 理解为两个指针单元；②在Step4 中R3 送入B，是由于试验机限制，每条指令只能选择一个寄存器，在下一步中完成R2 自增，不能再选择R3，所以在这里将计算结果暂存为B。

2 指令集和微指令设计

根据表1 中硬件实现过程的描述，设计的指令集见表2，根据每条指令设计出相应的微操作，并写成微指令，再利用微指令组成微程序，最终设计出多条指令与各个微程序相连接，即可完成指令集的设计。

在微程序控制的系统中，CPU 设计了一个控制存储器，用于存放各种机器指令对应的微程序段。当CPU 执行机器指令时，会在控制存储器里寻找与该机器指令对应的微程序，取出相应的微指令来控制执行各个微操作，从而完成该程序语句的功能^[8]。按照Dais-CMX 模型机系统建议的微指令格式，参照微指令设计，将每条微指令代码化，译成二进制代码表，并将二进制代码表转换成十六进制格式文件。

1）指令IN1、指令IN2、指令ADD1 的微指令设计。

图1 描述了IN1、IN2 和ADD1 指令运行的示意图，表3—表5 描述3 条指令对应的微指令信息。

2）指令OUT 的微指令设计。

在OUT 指令中，通过R2 寄存器间接寻址，将@R2 送入ALU 中的A 寄存器，如表6。

3）指令ADD2 的微指令设计。

图2 描述了ADD2 指令的运行示意图，表7描述ADD2 指令对应的微指令信息。

4）指令STA、指令JMP 的微指令设计。

图3 描述了STA 指令的运行示意图，表8 和表9描述STA指令和JMP指令对应的微指令信息。

3 实验结果及性能比较

3.1 实验结果

在Dais-CMX 模型机上，完成指令和微指令集设计后，启动系统，运行结果如图4 所示。从内存中观察到设计的指令集和底层的微指令集，能实现斐波那契数列的运算，并且运算结果完全正确。

3.2 软硬件实现斐波那契数列的性能比较