隨機(jī)存取機(jī)器模型
[拼音]:suiji cunqu jiqi moxing
[外文]:random access machine model
算法分析與計算復(fù)雜性理論中重要的串行計算模型,簡稱 RAM。引進(jìn)它是為了便于從理論上分析計算機(jī)串行程序所耗費的時間、空間等資源。一個RAM由k個變址器I1,I2,…,Ik、無窮個普通寄存器R0,R1,R2,…和一個有窮長的程序所組成。變址器也是寄存器,每個寄存器中可以存放一個自然數(shù),但只有變址器的內(nèi)容可以作為間接地址。
RAM的程序使用兩種形式的地址。一種是直接地址,形式為Ij(j=1,2,…,k)或Ri(i=0,1,2,…);另一種是間接地址,形式為Ij(j=1,2,…,k)。如果Ij中存的自然數(shù)為i,則Ij代表地址Ri。
RAM的指令為下列形式之一:
(1)A←a,表示把地址A的內(nèi)容改為自然數(shù)a;
(2)A←B,表示把地址A的內(nèi)容改為地址B的內(nèi)容;
(3)A←B*C,表示把地址B中的內(nèi)容和地址C中的內(nèi)容作為運算*之后,送入地址A。這里*可以是自然數(shù)的加法、減法、乘法或整數(shù)除法。減法的定義為:若a≥b則等于a–b,否則等于0;
(4)A←F(B,C),此處F是一個可以用多帶圖靈機(jī)器在多項式空間和對數(shù)多項式的巡回中實現(xiàn)的變換(見多帶圖靈機(jī)模型)。A、B、C可以是直接地址,也可以是間接地址。A是寫入地址,B、C是讀出地址。
RAM除了可以用以上的指令編程序外,還可以判斷某個寄存器或變址器的內(nèi)容是否為0,以實現(xiàn)條件轉(zhuǎn)移。
變址器是用來實現(xiàn)間接地址的,所以要求在運算過程中變址器中所存的自然數(shù)不大于所用到的普通寄存器數(shù)目的某個常數(shù)倍。
RAM程序的一個例子是:設(shè)n個自然數(shù)a1,a2,…,an分別存放在R1,R2,…,Rn中,n存放在R0中,要求把這n個數(shù)的和計算出來,結(jié)果放在R0中。程序如圖。
RAM的資源耗費有兩種定義方式,即均勻耗費和對數(shù)耗費。均勻的空間耗費是指計算中曾經(jīng)使用過的寄存器的總數(shù)。均勻的時間耗費是指自始至終被執(zhí)行的指令和轉(zhuǎn)移的總條數(shù)。均勻耗費常用于算法分析中。
另一種標(biāo)準(zhǔn)是對數(shù)耗費。此時空間耗費指計算中普通寄存器存過的自然數(shù)的最大長度之和。時間耗費則指被執(zhí)行的每條指令的時間耗費之和。而一條指令的時間耗費則被認(rèn)為與被運算的自然數(shù)的長度成正比的。
對于RAM,還可以定義巡回(虛擬的并行時間)。它是計算中周相的總數(shù),而一個周相則是 RAM工作的一個階段,在此階段中,沒有任何一個普通寄存器先被寫入然后又被讀出。
建筑資質(zhì)代辦咨詢熱線:13198516101
標(biāo)簽:suiji cunqu jiqi moxing、隨機(jī)存取機(jī)器模型
版權(quán)聲明:本文采用知識共享 署名4.0國際許可協(xié)議 [BY-NC-SA] 進(jìn)行授權(quán)
文章名稱:《隨機(jī)存取機(jī)器模型》
文章鏈接:http://m.fjemb.com/12391.html
該作品系作者結(jié)合建筑標(biāo)準(zhǔn)規(guī)范、政府官網(wǎng)及互聯(lián)網(wǎng)相關(guān)知識整合。如若侵權(quán)請通過投訴通道提交信息,我們將按照規(guī)定及時處理。