基于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.

（編輯：孫怡銘）