高俊杰

摘 要：在現(xiàn)代計算機(jī)系統(tǒng)中，利用高級語言可設(shè)計出多種計算斐波那契數(shù)列的算法，但需要眾多指令的支持。為了簡化斐波那契數(shù)列的計算過程，提高計算速度，文章提出在Dais-CMX模型機(jī)上，基于硬件底層微程序設(shè)計，利用寄存器尋址、寄存器間接尋址和指令跳轉(zhuǎn)等硬件技術(shù)，設(shè)計7條指令即可完成斐波那契數(shù)列運(yùn)算的方法。

關(guān)鍵詞：指令集；微程序；斐波那契數(shù)列；尋址技術(shù)

文章編號：1672-5913（2017）07-0065-04

中圖分類號：G642

0 引 言

13世紀(jì)，意大利數(shù)學(xué)家斐波那契在《算盤書》的修訂版中加入了一道著名的兔子繁殖問題：假設(shè)一對兔子要一個月才能到成熟期，而一對成熟的兔子每月會生一對兔子，那么由一對初生兔子開始，12個月會有多少對兔子呢？從第一個月到第十二個月兔子的對數(shù)分別是：2，3，5，8，13，21，34，55，89，144……，這個數(shù)列被稱為斐波那契數(shù)列[1]。

斐波那契數(shù)列在數(shù)學(xué)、物理、化學(xué)、生物、計算機(jī)科學(xué)中都發(fā)揮著極為重要的作用。為此，美國數(shù)學(xué)會從1960年代起出版了《斐波納契數(shù)列》季刊，專門刊載這方面的研究成果?？茖W(xué)家發(fā)現(xiàn)，一些植物的花瓣、萼片、果實(shí)的數(shù)目以及排列方式也與斐波那契數(shù)列有著驚人的相似。1992年，兩位法國科學(xué)家通過對花瓣形成過程的計算機(jī)仿真實(shí)驗，證實(shí)了在系統(tǒng)保持最低能量的狀態(tài)下，花朵會以斐波那契數(shù)列長出花瓣[2]。在計算機(jī)科學(xué)中，斐波那契堆（Fibonacci heap）是最小堆有序樹的集合，它和二項式堆有類似的性質(zhì)，可用于實(shí)現(xiàn)合并優(yōu)先隊列。近年來在計算機(jī)領(lǐng)域，基于斐波那契數(shù)列的研究層出不窮，如基于斐波那契數(shù)列的指紋增強(qiáng)方向濾波模板[3]、基于斐波那契數(shù)列采樣的BP神經(jīng)網(wǎng)絡(luò)金融時間序列短期趨勢預(yù)測[4]等都運(yùn)用了斐波那契數(shù)列的運(yùn)算。

在現(xiàn)代計算機(jī)系統(tǒng)中，利用高級語言可以設(shè)計出多種計算斐波那契數(shù)列的算法，如遞推算法[5]、特征方程求解法[5]、矩陣冪運(yùn)算加速算法[6]等，但這些基于高級語言的算法，在實(shí)現(xiàn)時需要調(diào)用眾多指令，需要較為龐大的指令系統(tǒng)支持。為了簡化斐波那契數(shù)列的計算過程，提高運(yùn)算速度，筆者基于Dais-CMX模型機(jī)硬件底層微程序，設(shè)計出一個經(jīng)過簡化的計算斐波那契數(shù)列的指令集，利用寄存器尋址、寄存器間接尋址、指令的跳轉(zhuǎn)[7]等硬件功能相互組合，融合軟件技術(shù)中的指針概念，最終實(shí)現(xiàn)本設(shè)計。斐波那契數(shù)列指令集適用于Dais-CMX模型機(jī)系統(tǒng)，通過7條指令完成數(shù)列的計算，相比于大多數(shù)軟件算法，在性能上有較大提高。

1 問題描述

斐波那契數(shù)列的計算可以通過軟件方法或硬件方法進(jìn)行設(shè)計。

1.1 軟件設(shè)計方法及性能分析

斐波那契數(shù)列可以用軟件設(shè)計方法中的遞推法實(shí)現(xiàn)。遞推法是迭代算法的一種，其基本思想是用若干步可重復(fù)的簡單運(yùn)算描述復(fù)雜的數(shù)學(xué)問題，以便于計算機(jī)處理。這種方法的求解過程與遞推關(guān)系的思想完全一致，由邊界條件開始往后逐個推算[5]。

斐波那契數(shù)列的遞推關(guān)系：

從遞推關(guān)系公式（1）可以看出，斐波那契數(shù)列第一項為0，第二項為1，其后各項為前兩項之和。根據(jù)這一條件，可以歸納出該算法的時間復(fù)雜度為O（n）。

斐波那契數(shù)列偽代碼如下：

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

斐波那契數(shù)列用C語言編制程序，其代碼如下：

#include

int main（）{

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

int i；

printf（"%d %d "，F(xiàn)ibonacci[0]，F(xiàn)ibonacci[1]）；

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

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

printf（"%d "，F(xiàn)ibonacci[i]）；

}

}

高級語言有著較強(qiáng)的可讀性和算法描述能力，與此同時隱藏了許多硬件的實(shí)現(xiàn)細(xì)節(jié)，通過匯編語言可以體現(xiàn)出程序的硬件實(shí)現(xiàn)過程。遞推法匯編語言部分代碼如下：

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

由匯編語言代碼可知，一個采用遞推算法的程序在實(shí)際運(yùn)行時至少調(diào)用了20次關(guān)鍵指令，因此，斐波那契數(shù)列的計算需要進(jìn)行20多次關(guān)鍵指令的操作才能完成。

1.2 硬件設(shè)計分析

基于硬件設(shè)計，其可靠性、計算速度都遠(yuǎn)勝于軟件算法。在硬件底層實(shí)現(xiàn)斐波那契數(shù)列的計算，可以簡化計算過程，提高計算速度。為便于設(shè)計，我們將寄存器間接尋址作為軟件技術(shù)中的指針使用。表1對斐波那契數(shù)列硬件實(shí)現(xiàn)過程進(jìn)行了描述：①在Step1中，R1和R2理解為兩個指針單元；②在Step4中R3送入B，是由于試驗機(jī)限制，每條指令只能選擇一個寄存器，在下一步中完成R2自增，不能再選擇R3，所以在這里將計算結(jié)果暫存為B。

2 指令集和微指令設(shè)計

根據(jù)表1中硬件實(shí)現(xiàn)過程的描述，設(shè)計的指令集見表2，根據(jù)每條指令設(shè)計出相應(yīng)的微操作，并寫成微指令，再利用微指令組成微程序，最終設(shè)計出多條指令與各個微程序相連接，即可完成指令集的設(shè)計。

在微程序控制的系統(tǒng)中，CPU設(shè)計了一個控制存儲器，用于存放各種機(jī)器指令對應(yīng)的微程序段。當(dāng)CPU執(zhí)行機(jī)器指令時，會在控制存儲器里尋找與該機(jī)器指令對應(yīng)的微程序，取出相應(yīng)的微指令來控制執(zhí)行各個微操作，從而完成該程序語句的功能[8]。按照Dais-CMX模型機(jī)系統(tǒng)建議的微指令格式，參照微指令設(shè)計，將每條微指令代碼化，譯成二進(jìn)制代碼表，并將二進(jìn)制代碼表轉(zhuǎn)換成十六進(jìn)制格式文件。

1）指令I(lǐng)N1、指令I(lǐng)N2、指令A(yù)DD1的微指令設(shè)計。

圖1描述了IN1、IN2和ADD1指令運(yùn)行的示意圖，表3—表5描述3條指令對應(yīng)的微指令信息。

2）指令OUT的微指令設(shè)計。

在OUT指令中，通過R2寄存器間接尋址，將@R2送入ALU中的A寄存器。

3）指令A(yù)DD2的微指令設(shè)計。

圖2描述了ADD2指令的運(yùn)行示意圖，表7描述ADD2指令對應(yīng)的微指令信息。

4）指令STA、指令JMP的微指令設(shè)計。

圖3描述了STA指令的運(yùn)行示意圖，表8和表9描述STA指令和JMP指令對應(yīng)的微指令信息。

3 實(shí)驗結(jié)果及性能比較

3.1 實(shí)驗結(jié)果

在Dais-CMX模型機(jī)上，完成指令和微指令集設(shè)計后，啟動系統(tǒng)，運(yùn)行結(jié)果如圖4所示。從內(nèi)存中觀察到設(shè)計的指令集和底層的微指令集，能實(shí)現(xiàn)斐波那契數(shù)列的運(yùn)算，并且運(yùn)算結(jié)果完全正確。

3.2 軟硬件實(shí)現(xiàn)斐波那契數(shù)列的性能比較

表10將斐波那契數(shù)列實(shí)現(xiàn)的兩種方法進(jìn)行了比較，可知硬件實(shí)現(xiàn)的性能提高了很多。

4 結(jié) 語

通過實(shí)驗證實(shí)，斐波那契數(shù)列指令集設(shè)計是正確可行的。斐波那契數(shù)列指令集設(shè)計原理可以移植到嵌入式系統(tǒng)，如基于斐波那契數(shù)列的加密設(shè)備、指紋識別設(shè)備等，結(jié)合本硬件算法設(shè)計可以加快計算速度，減少內(nèi)存占用，提高可靠性。

參考文獻(xiàn)：

[1] 凌曉牧. 有趣的斐波那契數(shù)列[J]. 江蘇第二師范學(xué)院學(xué)報： 自然科學(xué)版， 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] 蔡秀梅， 范九倫， 高新波.基于斐波那契數(shù)列的指紋增強(qiáng)方向濾波模板[J]. 模式識別與人工智能， 2011， 24（3）： 360-367.

[4] 邱紫華， 潘和平. 基于斐波那契數(shù)列采樣的BP神經(jīng)網(wǎng)絡(luò)金融時間序列短期趨勢預(yù)測[J].管理學(xué)家：學(xué)術(shù)版， 2010（5）： 50-60.

[5] 趙秀梅， 趙宗昌. Fibonacci數(shù)列的應(yīng)用研究[J]. 山東建筑大學(xué)學(xué)報， 2004， 19（2）： 73-75.

[6] 陳宏建， 陳崚， 沈潔， 等. 一種改進(jìn)的矩陣冪運(yùn)算及其性能分析[J].計算機(jī)工程與應(yīng)用， 2003， 39（33）： 61-64.

[7] 唐朔飛. 計算機(jī)組成原理[M]. 北京： 高等教育出版社， 2008： 72-103.

[8] 齊學(xué)梅. 計算機(jī)硬件基礎(chǔ)實(shí)驗教程[M]. 蕪湖： 安徽師范大學(xué)出版社， 2013： 25-40.

（編輯：孫怡銘）