基于Dais—CMX模型机的斐波那契数列指令集设计

高俊杰

摘 要：在现代计算机系统中，利用高级语言可设计出多种计算斐波那契数列的算法，但需要众多指令的支持。为了简化斐波那契数列的计算过程，提高计算速度，文章提出在Dais-CMX模型机上，基于硬件底层微程序设计，利用寄存器寻址、寄存器间接寻址和指令跳转等硬件技术，设计7条指令即可完成斐波那契数列运算的方法。

关键词：指令集；微程序；斐波那契数列；寻址技术

文章编号：1672-5913（2017）07-0065-04

中图分类号：G642

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）。

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

FUNCTION_FIBONACCI（Fibonacci，n）

step1：Fibonacci[0] = 0

step2：Fibonacci[1] = 1

step3：For i=2 to n

step4： Fibonacci[i]=Fibonacci[i-1]+Fibonacci[i-2]

step5： return

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

#include

int main（）{

int Fibonacci[20]={0，1}；

int i；

printf（"%d %d "，Fibonacci[0]，Fibonacci[1]）；

for （i=2；i<20；i++）{

Fibonacci[i] = Fibonacci[i-1]+Fibonacci[i-2]；

printf（"%d "，Fibonacci[i]）；

}

}

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

mov esi，OFFSET array

mov ecx，lengthof array

mov edx，offset prompt

call writestring

mov edx，offset prompt1

mov edi，0

mov [esi]，edi

mov eax，[esi]

call writeint

call writestring

mov edi，1

mov [esi + 4]，edi

mov eax，[esi + 4]

call writeint

call writestring

sub ecx，2

由匯编语言代码可知，一个采用递推算法的程序在实际运行时至少调用了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寄存器。

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

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

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

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

3 实验结果及性能比较

3.1 实验结果

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

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

表10将斐波那契数列实现的两种方法进行了比较，可知硬件实现的性能提高了很多。

4 結 语

通过实验证实，斐波那契数列指令集设计是正确可行的。斐波那契数列指令集设计原理可以移植到嵌入式系统，如基于斐波那契数列的加密设备、指纹识别设备等，结合本硬件算法设计可以加快计算速度，减少内存占用，提高可靠性。

参考文献：

[1] 凌晓牧. 有趣的斐波那契数列[J]. 江苏第二师范学院学报： 自然科学版， 2011（5）： 31-33.

[2] Douady S， Couder Y. Phyllotax is as a physical self-organized growth process.[J]. Physical Review Letters， 1992， 68（13）： 2098-2101.

[3] 蔡秀梅， 范九伦， 高新波.基于斐波那契数列的指纹增强方向滤波模板[J]. 模式识别与人工智能， 2011， 24（3）： 360-367.

[4] 邱紫华， 潘和平. 基于斐波那契数列采样的BP神经网络金融时间序列短期趋势预测[J].管理学家：学术版， 2010（5）： 50-60.

[5] 赵秀梅， 赵宗昌. Fibonacci数列的应用研究[J]. 山东建筑大学学报， 2004， 19（2）： 73-75.

[6] 陈宏建， 陈崚， 沈洁， 等. 一种改进的矩阵幂运算及其性能分析[J].计算机工程与应用， 2003， 39（33）： 61-64.

[7] 唐朔飞. 计算机组成原理[M]. 北京： 高等教育出版社， 2008： 72-103.

[8] 齐学梅. 计算机硬件基础实验教程[M]. 芜湖： 安徽师范大学出版社， 2013： 25-40.

（编辑：孙怡铭）