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

基于DaisCMX模型机的斐波那契数列指令集设计 高俊杰摘 要：在现代计算机系统中，利用高级语言可设计出多种计算斐波那契数列的算法，但需要众多指令的支持为了简化斐波那契数列的计算过程，提高计算速度，文章提出在Dais-CMX模型机上，基于硬件底层微程序设计，利用寄存器寻址、寄存器间接寻址和指令跳转等硬件技术，设计7条指令即可完成斐波那契数列运算的方法关键词：指令集；微程序；斐波那契数列；寻址技术：1672-5913（2017）07-0065-04：G6420 引 言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] = 0step2：Fibonacci[1] = 1step3：For i=2 to nstep4： 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 arraymov ecx，lengthof arraymov edx，offset promptcall writestringmov edx，offset prompt1mov edi，0mov [esi]，edimov eax，[esi]call writeintcall writestringmov edi，1mov [esi + 4]，edimov eax，[esi + 4]call writeintcall writestringsub 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.（编辑：孙怡铭） 计算机教育2017年7期计算机教育的其它文章基于隐性知识管理的高职Linux操作系统课程改革基于CDIO模式的路由交换课程教学改革与实践“实、导、促、新”课程综合改革探索学术驱动研究生教学方法探讨软件服务外包相关专业大学生创业调查报告软件工程综合实训课程融合初探 -全文完-。