清華大學(xué)綜合訓(xùn)練論文模板

清華大學(xué)綜合論文訓(xùn)練題目：基于PetriNet的目標(biāo)機(jī)描述的初步研究系別：計(jì)算機(jī)科學(xué)與技術(shù)系專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)姓名：符文杰指導(dǎo)教師：王生原二OO六年六月十九日11指導(dǎo)教師評(píng)語(yǔ):指導(dǎo)教師（簽字）評(píng)閱教師評(píng)語(yǔ):評(píng)閱教師（簽字）答辯小組意見(jiàn):組長(zhǎng)（簽字）績(jī):教學(xué)負(fù)責(zé)人（簽字）關(guān)于學(xué)位論文使用授權(quán)的說(shuō)明本人完全了解清華大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留學(xué)位論文的復(fù)印件，允許該論文被查閱和借閱；學(xué)?？梢怨荚撜撐牡娜炕虿糠謨?nèi)容，可以采用影印、縮印或其他復(fù)制手段保存該論文。（涉密的學(xué)位論文在解密后應(yīng)遵守此規(guī)定）簽名：導(dǎo)師簽名：13期：綜合論文訓(xùn)練任務(wù)書(shū)姓名學(xué)號(hào)班號(hào)系別同組姓名指導(dǎo)教師一、課題名稱：［單擊此處鍵入］二、論文主要內(nèi)容及進(jìn)度安排:［單擊此處鍵入］三、論文主要要求（如主要指標(biāo)）:［單擊此處鍵入］四、主要參考文獻(xiàn):［單擊此處鍵入］教學(xué)負(fù)責(zé)人簽字中文摘要在編譯程序中，可重定向性非常重要，而目標(biāo)機(jī)描述是實(shí)現(xiàn)可重定向性的核心環(huán)節(jié)。本文研究了用Petri網(wǎng)模型對(duì)目標(biāo)機(jī)進(jìn)行描述的問(wèn)題。Petri網(wǎng)的并發(fā)性等特點(diǎn)使得它在作為目標(biāo)機(jī)描述語(yǔ)言有一定的優(yōu)勢(shì)，但是目前在該領(lǐng)域中的研究并不多。本文中用對(duì)象Petri網(wǎng)對(duì)…個(gè)具體的CPU設(shè)計(jì)做了完整的建模，通過(guò)簡(jiǎn)單的性質(zhì)驗(yàn)證和模擬執(zhí)行等手段驗(yàn)證了它的正確性。設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)面向體系結(jié)構(gòu)的對(duì)象Petri網(wǎng)模擬器。在這些工作的基礎(chǔ)上，今后可以對(duì)更復(fù)雜的目標(biāo)機(jī)進(jìn)行建模，并逐漸形成一套有效的建模方法。關(guān)鍵詞：目標(biāo)機(jī)描述語(yǔ)言、Petri網(wǎng)、對(duì)象Petri網(wǎng)、建模、執(zhí)行ABSTRACTRetargetabilityisespeciallyimportantincompilers,andarchitecturedescriptionisoneofthekeyelementsforsuchapurpose.ThethesisstudieshowtospecifythearchitectureusingsomekindsofPetriNetmodels.TheconcurrencyandotherpropertiesPetriNethasmakeitcertainadvantagesasanArchitectureDescriptionLanguage,butthecurrentresearchinthefieldisnotsomuch.Awell-modeledCPUdesignusingObjectPetriNetwillbepresented,andbeverifiedbysomepropertiesitenjoysalongwithsimulation.WedesignandimplementanObjectPetriNetsimulatorwhichisorientedtoarchitecturedescription.Onthebasisofthesework,wecancarryoutmorecomplicatedarchitecturemodelanddevelopanefficientmethodinthefuture.Keywords：ArchitectureDescriptionLanguage,PetriNet,ObjectPetriNet,Modeling,Execution主要符號(hào)對(duì)照表ADL目標(biāo)機(jī)描述語(yǔ)言O(shè)PNObjectPetriNet,對(duì)象Petri網(wǎng)TokenPetri網(wǎng)的一個(gè)基本元素，有譯作托肯Place庫(kù)所，Petri網(wǎng)的一個(gè)基本元素Transition變遷，Petri網(wǎng)的一個(gè)基本元素輸入弧從庫(kù)所到變遷的弧輸出弧從變遷到庫(kù)所的弧CPU中央處理器ALU算術(shù)邏輯運(yùn)算單元IF五級(jí)流水中的一步，取指令I(lǐng)D五級(jí)流水中的一步，將指令譯碼EX五級(jí)流水中的一步，執(zhí)行指令MEM五級(jí)流水中的一步，訪問(wèn)內(nèi)存WB五級(jí)流水中的一步，寫(xiě)回寄存器TOC\o"1-5"\h\z\o"CurrentDocument"中文摘要 IABSTRACT Ill\o"CurrentDocument"主要符號(hào)對(duì)照表 V目錄 VII\o"CurrentDocument"第一章引言 1\o"CurrentDocument"1.2主要貢獻(xiàn) 2\o"CurrentDocument"第二章Petri網(wǎng) 5\o"CurrentDocument"Petri網(wǎng)模型的選擇 5\o"CurrentDocument"對(duì)象Petri網(wǎng)的直觀描述 5\o"CurrentDocument"對(duì)象Petri網(wǎng)的形式化定義 6\o"CurrentDocument"對(duì)象網(wǎng)與有色網(wǎng)的等價(jià)性 7\o"CurrentDocument"第三章建模 9\o"CurrentDocument"目標(biāo)機(jī)選擇 9\o"CurrentDocument"主要部件建模 10時(shí)鐘與同步 11內(nèi)內(nèi)問(wèn) 13寄存器堆及寄存器訪問(wèn) 15\o"CurrentDocument"流水線建模 18流水線的暫停和排空 20IF流水步詳述 24334ID流水步詳述 25EX流水步詳述 28MEM流水步詳述 31消除數(shù)據(jù)相關(guān)性 34停機(jī) 38\o"CurrentDocument"建模小結(jié) 38完整模型 38常見(jiàn)問(wèn)題小結(jié) 41\o"CurrentDocument"第四章驗(yàn)證 43\o"CurrentDocument"簡(jiǎn)單不變量 43單庫(kù)所Token數(shù)目不變量 43雙庫(kù)所Token數(shù)目不變量 44\o"CurrentDocument"極大并發(fā)意義下的不變量 45\o"CurrentDocument"五變遷并發(fā)的可行性 46\o"CurrentDocument"第五章模擬器 49\o"CurrentDocument"需求分析 49性能需求 50運(yùn)行需求 505.2.2處理流程 51\o"CurrentDocument"5.3詳細(xì)設(shè)計(jì) 51類型定義類的設(shè)計(jì) 51Token類的設(shè)計(jì) 55弧類的設(shè)計(jì) 56庫(kù)所類的設(shè)計(jì) 57變遷類的設(shè)計(jì) 57執(zhí)行代碼設(shè)計(jì) 57輸入格式設(shè)計(jì) 60\o"CurrentDocument"第六章結(jié)論 65\o"CurrentDocument"6.2建模心得 65\o"CurrentDocument"插圖索引 I\o"CurrentDocument"表格索引 III\o"CurrentDocument"參考文獻(xiàn) V致謝 VII聲明 IX\o"CurrentDocument"附錄A外文資料原文 XI\o"CurrentDocument"附錄B外文資料翻譯 XLIII附錄C目標(biāo)機(jī)指令集 LVII附錄D建模結(jié)果的代碼表示 LIX第一章引言1.1選題背景我們知道在編譯程序中，可重定向性是一個(gè)重要的追求目標(biāo)。它的原因有很多，如：(1)現(xiàn)代計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)呈多樣性的態(tài)勢(shì)。(2)相對(duì)于計(jì)算機(jī)硬件技術(shù)的迅猛發(fā)展，系統(tǒng)軟件和工具的開(kāi)發(fā)周期更長(zhǎng)、費(fèi)用更高。(3)許多應(yīng)用系統(tǒng)，特別是嵌入式系統(tǒng)，需要用到宿主機(jī)上具有重定向能力的交叉開(kāi)發(fā)工具。(4)在軟硬件協(xié)同設(shè)計(jì)過(guò)程中，目標(biāo)機(jī)環(huán)境并不可用，系統(tǒng)結(jié)構(gòu)設(shè)計(jì)方案也是多變的。目標(biāo)機(jī)描述是實(shí)現(xiàn)可重定向性的核心環(huán)節(jié)。對(duì)目標(biāo)機(jī)的描述可分為結(jié)構(gòu)級(jí)、行為級(jí)和這兩種的混合。結(jié)構(gòu)級(jí)以描述各功能部件的結(jié)構(gòu)及其互聯(lián)關(guān)系為主。行為級(jí)以指令集系統(tǒng)結(jié)構(gòu)的描述為主。服務(wù)于可重定向編譯程序的目標(biāo)機(jī)描述語(yǔ)言I至少應(yīng)該包含行為級(jí)的描述，多數(shù)都不同程度地包含結(jié)構(gòu)級(jí)信息的描述。但是，當(dāng)前的目標(biāo)機(jī)描述語(yǔ)言中結(jié)構(gòu)級(jí)信息的描述能力和分析使用能力較弱，并且缺乏形式化的方法。這也是這個(gè)題目的研究意義之所在。1ArchitectureDescriptionLanguage,簡(jiǎn)稱ADL。使用Petri網(wǎng)⑴⑵作為目標(biāo)機(jī)描述語(yǔ)言在這方面具有一些優(yōu)勢(shì)，原因是：Petri網(wǎng)在描述并發(fā)性，資源流動(dòng)、依賴與共享等方面優(yōu)于其它的形式模型。Petri網(wǎng)具有簡(jiǎn)單、易理解的圖形表示。Petri網(wǎng)具有較強(qiáng)的行為分析、模擬和正確性(安全性和活性)驗(yàn)證能力。所以，用Petri網(wǎng)作為目標(biāo)機(jī)描述語(yǔ)言來(lái)對(duì)體系結(jié)構(gòu)進(jìn)行建模是一項(xiàng)很有意義的研究。1.2主要貢獻(xiàn)本文首先根據(jù)任務(wù)的特點(diǎn)，選擇了一種適合的Petri網(wǎng)模型——對(duì)象網(wǎng)作為目標(biāo)機(jī)描述語(yǔ)言。給出了對(duì)象Petri網(wǎng)的形式化定義(第2章)，并簡(jiǎn)單地證明了對(duì)象Petri網(wǎng)和有色Petri網(wǎng)的等價(jià)性。因此，有色網(wǎng)的一些有用的性質(zhì)在對(duì)象Petri網(wǎng)中仍然成立。然后對(duì)一具體的單發(fā)射五級(jí)流水CPU設(shè)計(jì)用對(duì)象Petri網(wǎng)進(jìn)行建模(第3章)，得到一個(gè)完整的模型。過(guò)去很少有人做過(guò)類似的工作，所以這是?項(xiàng)很有意義的探索性研究。執(zhí)行這個(gè)對(duì)象Petri網(wǎng)模型能夠得到和原設(shè)計(jì)相同的結(jié)果。在建模各個(gè)部分的過(guò)程中，對(duì)多種可能的建模方案進(jìn)行比較，篩選出最適合的方案加以采用。在建模完成后，對(duì)用Petri網(wǎng)對(duì)體系結(jié)構(gòu)進(jìn)行建模的過(guò)程中經(jīng)常碰到的問(wèn)題進(jìn)行討論，給出解決方案，并提出了一些構(gòu)建Petri網(wǎng)模型的心得。這些技巧與心得能為以后的工作一對(duì)更復(fù)雜的體系結(jié)構(gòu)進(jìn)行Petri網(wǎng)建模一積累經(jīng)驗(yàn)。接著對(duì)模型的一些簡(jiǎn)單的性質(zhì)進(jìn)行驗(yàn)證（第4章）。通過(guò)一些性質(zhì)的驗(yàn)證可以幫助我們發(fā)現(xiàn)模型中的錯(cuò)誤，能夠在執(zhí)行對(duì)象Petri網(wǎng)模型前將錯(cuò)誤減得盡可能的少。從而能夠節(jié)省調(diào)試的時(shí)間。我的畢業(yè)設(shè)計(jì)的另一項(xiàng)工作就是實(shí)現(xiàn)一個(gè)通用的對(duì)象Petri網(wǎng)模擬器（第5章）。它能夠使對(duì)象Petri網(wǎng)模型實(shí)際運(yùn)行起來(lái)。這個(gè)模擬器不是專門(mén)針對(duì)某?個(gè)建模結(jié)果而設(shè)計(jì)的，但是它針對(duì)描述體系結(jié)構(gòu)的過(guò)程中容易碰到的一些通性問(wèn)題作了優(yōu)化，所以它的執(zhí)行效率會(huì)比普通的對(duì)象Petri網(wǎng)模擬器高。在設(shè)計(jì)模擬器時(shí)，既考慮了執(zhí)行效率的問(wèn)題，又考慮了簡(jiǎn)潔性的問(wèn)題，最后在兩者之間作了折衷。第二章Petri網(wǎng)Petri網(wǎng)模型的選擇Petri網(wǎng)的種類很多，從簡(jiǎn)單的庫(kù)所/變遷網(wǎng)，到有色網(wǎng)，到更復(fù)雜的Petri網(wǎng)，如：隨機(jī)Petri網(wǎng)、時(shí)間Petri網(wǎng)、對(duì)象Petri網(wǎng) 越復(fù)雜的Petri網(wǎng)模型往往具有越強(qiáng)的建模能力，但是同時(shí)也削弱了其模擬、分析和驗(yàn)證的能力，并且不具備足夠的簡(jiǎn)潔、有效性。所以，我們需要找一種適用于描述體系結(jié)構(gòu)的Petri網(wǎng)模型來(lái)使用，既要有足夠的建模能力，又要簡(jiǎn)潔以滿足模擬的需要。在這樣的條件下，對(duì)象Petri網(wǎng)是一個(gè)比較好的選擇。關(guān)于對(duì)象Petri網(wǎng)，目前還沒(méi)有一個(gè)統(tǒng)…的定義。已經(jīng)有人在這方面作了一些工作⑸⑹⑺。但是，這些目前比較流行的對(duì)象Petri網(wǎng)模型大多是用于建模并發(fā)或分布軟件系統(tǒng)的，比較復(fù)雜。然而在目標(biāo)機(jī)描述中并不需要太復(fù)雜的數(shù)據(jù)結(jié)構(gòu)或類型，而我們期望的僅是把一些緊密相關(guān)的數(shù)據(jù)結(jié)合在一起，使得它們存在于一個(gè)Token中。因此，我們將自己給出對(duì)象Petri網(wǎng)的定義。對(duì)象Petri網(wǎng)的直觀描述我們可以認(rèn)為對(duì)象Petri網(wǎng)是在有色Petri網(wǎng)上的?種擴(kuò)展，它們的主要區(qū)別在Token的類型上。在有色網(wǎng)中，每個(gè)Token都可以有一個(gè)顏色，相當(dāng)于這個(gè)Token的值。在對(duì)象網(wǎng)中，每個(gè)Token就成了一個(gè)對(duì)象，它可以具有多個(gè)（有限個(gè)）屬性值。舉例來(lái)說(shuō)：一個(gè)有色網(wǎng)的Token可以是紅、黃、藍(lán)三種顏色之一；一個(gè)對(duì)象網(wǎng)的Token除了具有顏色的屬性（可以是紅、黃、藍(lán)中任一種顏色）之外，還可以具有大小的屬性（可以是大、中或小的），當(dāng)然它還可以具有更多的屬性。我們可以用Token和C++中的變量類型作一個(gè)形象的類比：有色網(wǎng)的Token相當(dāng)于C++中的--個(gè)簡(jiǎn)單類型變量，如int；對(duì)象網(wǎng)的Token相當(dāng)于C++中的一個(gè)對(duì)象（class或struct）。對(duì)象Petri網(wǎng)的形式化定義由于對(duì)象Petri網(wǎng)是在有色Petri網(wǎng)的基礎(chǔ)上擴(kuò)展出來(lái)的，所以我們就在有色Petri網(wǎng)的形式化定義⑵的基礎(chǔ)上給出對(duì)象Petri網(wǎng)的形式化定義。定義2.3.1對(duì)象網(wǎng)中的每一個(gè)類是由有限個(gè)屬性組成的，其中每一個(gè)屬性都只有正的有限種值。定義2.3.2一個(gè)對(duì)象網(wǎng)（OPN）是一個(gè)六元組N=（P,T,Pre,Post,C,cd）,其中尸是一個(gè)有窮集合（N的庫(kù)所集合）：T是一個(gè)有窮集合（N的變遷集合），并且和「不相交；。是對(duì)象類的集合；cd：PUT-C是對(duì)象域的映射；Pre.PosteB''X''是矩陣(網(wǎng)N的向前和向后關(guān)聯(lián)矩陣)，使得對(duì)于每-對(duì)(p,t)wPXT,Pre[p,t\:cd{t}—?Bag(cd(p))和Post[p,t]:cd(t)fBag(cd(0))是映射。一個(gè)包/g是,?個(gè)從非空集合A到自然數(shù)集的函數(shù)，即bg：A—N。集合Bag(J)表示定義在集合A上的所有包的集合。集合B可由形如映射f:cd(r)fBag(cd(o))組成的集合來(lái)表示。C=Post-Pre稱為關(guān)聯(lián)矩陣。定義2.3.3對(duì)象網(wǎng)N=(P,T,Pre,Post,C,cd)的標(biāo)識(shí)是一個(gè)向量m,使得對(duì)每個(gè)庫(kù)所滿足m[p]GBag(cd(0))。網(wǎng)N和初始標(biāo)識(shí)m0稱為對(duì)象網(wǎng)系統(tǒng)，表示為S=(N,m?！祷?=(P,T,Pre,Post,C,cd,mo)?當(dāng)且僅當(dāng)mNPrelZ句(￡)，變遷力《7對(duì)于綁定￡在標(biāo)識(shí)m下具有發(fā)生權(quán)(表示為m0^)。在這種情況下，后繼標(biāo)識(shí)關(guān)系定義為:<=>m>Pre[/^句(￡)Am)=m+Post[/^H(￡)-Pre[ZW(萬(wàn))=m+C出t](j3)0對(duì)象網(wǎng)與有色網(wǎng)的等價(jià)性我們給出的對(duì)象Petri網(wǎng)的定義是在有色Petri網(wǎng)的基礎(chǔ)上作一個(gè)簡(jiǎn)單的變化得到的，區(qū)別就在于把顏色(類)變成了對(duì)象(類)，所以我們只要證明?個(gè)對(duì)象(類)能轉(zhuǎn)換成一個(gè)等價(jià)的顏色(類)即可。1也叫多重集multiset任取一個(gè)對(duì)象類O,根據(jù)定義231,設(shè)它含有k個(gè)屬性C|~Ck，屬性G具有Zi（4>0）種取值Vij?Viz。該對(duì)象類的對(duì)象可以有T=Z產(chǎn)Z2*…*Zk種不同的值。下面就設(shè)計(jì)一種轉(zhuǎn)換，把這個(gè)對(duì)象類轉(zhuǎn)換為一個(gè)顏色類C（共有0-T-1這T種顏色），且對(duì)象類O的值與顏色類C的值一一對(duì)應(yīng)。首先，我們對(duì)對(duì)象類O的每一個(gè)屬性G定義一個(gè)由它的值Vi』?Viz到0?Z『1間自然數(shù)的一個(gè)一一映射：fi（Mj）=j-l。然后，我們就可以定義F：。-C°F（o）=F（（vi,V2,…,V。）='"（匕）*升4）i=1 j=l其中V「Vk依次表示對(duì)象。的每個(gè)屬性的取值。其思想就是先把每個(gè)屬性的值映射成一個(gè)0?Z『1間的自然數(shù)。然后從右往左寫(xiě)成一排，把它看成是??個(gè)不等進(jìn)制數(shù)，從低位到高位的第i位的進(jìn)制是Z"最后把它換算成一個(gè)十進(jìn)制數(shù)。以2.2節(jié)中的例子來(lái)說(shuō)明，該對(duì)象O有兩個(gè)屬性C］顏色和C2大?。篊i的取值可以是紅、黃、藍(lán)；C2的取值可以是大、中、小。Zi=3,Z2=3o定義6：｛紅，黃，藍(lán)｝f｛0,1,2｝,6（紅）=0,6（黃）=1,6（藍(lán)）=2,它是一個(gè)一一映射。定義fz：｛大，中，?。齠8,1,2｝,個(gè)大）=0,f2仲）=1,fz（?。?2,它也是一4映射。F（（vbv2））=￡（Z（v,）*nz；）=f>（vi）+f2（v2）*3i=l j=\一個(gè)紅色的小的該類對(duì)象，映射后的顏色位F（（紅，?。?0+2*3=6；一個(gè)藍(lán)色的中的該類對(duì)象，映射后的顏色位F（（藍(lán)，中））=2+1*3=5。枚舉各種取值后可以證實(shí)它們確實(shí)各不相同。第三章建模目標(biāo)機(jī)選擇由于這項(xiàng)工作之前兒乎沒(méi)人做過(guò)，所以我們本著從簡(jiǎn)單入手的原則，選擇了一個(gè)比較簡(jiǎn)單的體系結(jié)構(gòu)模型進(jìn)行建模，希望能夠建起一個(gè)完整的模型，并對(duì)一些關(guān)鍵部件的建模方法進(jìn)行探討，以此為今后的工作積累經(jīng)驗(yàn)。我們選用的目標(biāo)機(jī)來(lái)自于孫林春和周文超在專業(yè)實(shí)踐中設(shè)計(jì)的CPU。它是一個(gè)按照MIPS思想設(shè)計(jì)的單發(fā)射五級(jí)流水CPU。五個(gè)流水步分別為：取指1、譯碼2、執(zhí)行3、訪存4和寫(xiě)回5。表3.1建模目標(biāo)機(jī)CPU主要參數(shù)參數(shù)項(xiàng)參數(shù)值流水級(jí)數(shù)丘級(jí)字長(zhǎng)16位指令長(zhǎng)16位Cache和內(nèi)存無(wú)Cache,指令和數(shù)據(jù)均從同一塊內(nèi)存直接讀取。寄存器16個(gè)取指令I(lǐng)nstructionFetch,簡(jiǎn)稱IF。指令譯碼InstructionDecode,簡(jiǎn)稱ID。執(zhí)行Execution,簡(jiǎn)稱EX。4訪問(wèn)內(nèi)存Memory，讀或?qū)懀?jiǎn)稱MEM。寫(xiě)回寄存器WriteBack,簡(jiǎn)稱WB。指令執(zhí)行順序順序發(fā)射，順序執(zhí)行。該CPU支持的指令包括：控制指令：NOP,HLTHalt,Halt,停機(jī)指令。算術(shù)運(yùn)算指令：ADD,SUB,INC,DEC,SHL,SHR,CMP邏輯運(yùn)算指令：AND,OR,XOR,NOT數(shù)據(jù)傳送指令：SETL,SETH,MOV,LOD,STO跳轉(zhuǎn)指令：JMP,JNZ,JZ,JNC,JC,JNS,JS指令的具體含義參見(jiàn)附錄。3.2主要部件建模CPU中的通用寄存器、指令寄存器和內(nèi)存等部件包含了指令、寄存器值和內(nèi)存值等數(shù)據(jù)，這些信息必須保存在Petri網(wǎng)的Token中。寄存器堆、內(nèi)存、流水步間寄存器等部件是存儲(chǔ)上述數(shù)據(jù)的地方，所以就建模成Petri網(wǎng)的庫(kù)所。每一個(gè)流水步的執(zhí)行中，數(shù)據(jù)發(fā)生了變化，所以對(duì)應(yīng)于Petri網(wǎng)的變遷（數(shù)據(jù)的變化由Token的變化表示出來(lái)）。我們很自然地把每個(gè)流水步建模成個(gè)變遷。時(shí)鐘與同步Petri網(wǎng)具有并發(fā)的特性，所以它可以很自然地描述5個(gè)流水步的并發(fā)操作。但是普通的Petri網(wǎng)并沒(méi)有對(duì)可同時(shí)觸發(fā)的變遷的觸發(fā)次序做出規(guī)定，而我們使用的CPU的指令執(zhí)行方式是順序發(fā)射順序執(zhí)行，因此就會(huì)引出如下圖的問(wèn)題。時(shí)刻1時(shí)刻2時(shí)刻3圖3」順序錯(cuò)亂的指令執(zhí)行示意圖上面的示意圖中有兩個(gè)流水步，兩個(gè)流水步的變遷的觸發(fā)條件都是從輸入弧中輸入任何一個(gè)Token,輸出還是該Token。在時(shí)刻I,流水線中有兩條指令：黑色的Token代表的指令執(zhí)行順序在前，且完成了第一個(gè)流水步；灰色的Token代表的指令執(zhí)行順序在后。此時(shí),流水步1和流水步2這兩個(gè)變遷都可以觸發(fā)。在沒(méi)有規(guī)定觸發(fā)發(fā)生的順序的前提下，有可能會(huì)發(fā)生流水步2先觸發(fā)的情況。觸發(fā)之后就是時(shí)刻2的情形。在時(shí)刻2,兩個(gè)Token(指令)都在第二個(gè)庫(kù)所中。此時(shí)，流水步2既可以綁定黑色的Token觸發(fā)，也可以綁定灰色的Token觸發(fā)。在未規(guī)定其觸發(fā)順序的情況下，就有可能先綁定灰色Token觸發(fā)，成為時(shí)刻3的情形。這樣順序靠后的灰色Token就先于黑色的Token完成了兩個(gè)流水步。但是，這種情況是我們所不希望看到的。所以，我們必須要進(jìn)一步做出某種限制，來(lái)避免這種情況的發(fā)生。通過(guò)上述的例子的分析過(guò)程，我們可以發(fā)現(xiàn)2種途徑來(lái)避免其發(fā)生：(1)在任意時(shí)刻，都并發(fā)觸發(fā)盡可能多的變遷。(2)在庫(kù)所中給Token建立一個(gè)先進(jìn)先出隊(duì)列。第一種方案中的“盡可能”多不是最大值的意思，而是極大值的意思、。相當(dāng)于對(duì)任意隨機(jī)選擇的可觸發(fā)的Token,先把它的每條輸入弧上需要的Token都取走，而不馬上產(chǎn)生輸出弧上應(yīng)該產(chǎn)生的新Token,然后繼續(xù)隨機(jī)挑選一個(gè)可以觸發(fā)的變遷，重復(fù)此操作，直到找不到可觸發(fā)的變遷為止。當(dāng)不能再觸發(fā)變遷時(shí)，把前面積累下來(lái)的未及時(shí)生成的Token添加到相應(yīng)的庫(kù)所中，開(kāi)始下一輪。第二種方案中，如果對(duì)每個(gè)庫(kù)所都規(guī)定Token要先進(jìn)先出，則限制比較大，可能會(huì)無(wú)法滿足其它方面的需求。如果僅對(duì)部分庫(kù)所規(guī)定Token要先進(jìn)先出，則增加了模型的復(fù)雜度，不是我們所希望的。第一種方案中的變遷并發(fā)觸發(fā)與流水線并發(fā)執(zhí)行的本質(zhì)完全吻合，所以我們選擇了第一種方案來(lái)避免指令亂序執(zhí)行的問(wèn)題。模型沒(méi)有變化，只是模擬的時(shí)候增加了一些要求，需要模擬器配合實(shí)現(xiàn)。不過(guò)這樣也給建模帶來(lái)了一個(gè)限制 每個(gè)流水步只能經(jīng)過(guò)-一個(gè)變遷。內(nèi)存及內(nèi)存訪問(wèn)因?yàn)閮?nèi)存中的數(shù)據(jù)是可變的，所以我們把內(nèi)存設(shè)計(jì)為一個(gè)Token。它是一個(gè)相當(dāng)大的Token,包含了許多屬性，每個(gè)屬性對(duì)應(yīng)了一個(gè)內(nèi)存中的一-個(gè)字節(jié)。因?yàn)閮?nèi)存的大小是一定的，所以這個(gè)Token的屬性個(gè)數(shù)滿足定義2.3.1的規(guī)定，是有限個(gè)。在需要讀寫(xiě)內(nèi)存數(shù)據(jù)的流水步里，我們?yōu)榱四軌驅(qū)?nèi)存數(shù)據(jù)進(jìn)行操作，就必須在該流水步對(duì)應(yīng)的變遷中把內(nèi)存Token從內(nèi)存庫(kù)所中取出來(lái)。然后，我們可以從中讀取一個(gè)字節(jié)為其他的Token設(shè)置值，或者修改它的某一位的值。最后，我們要把內(nèi)存Token放回內(nèi)存庫(kù)所中，使得以后能夠繼續(xù)訪問(wèn)內(nèi)存。圖3.2內(nèi)存訪問(wèn)建模示意圖因?yàn)橐粋€(gè)Token在一個(gè)時(shí)刻不能同時(shí)被兩個(gè)變遷取走，所以在這樣的設(shè)計(jì)中，同一時(shí)刻只能有一個(gè)流水步訪問(wèn)內(nèi)存。當(dāng)有兩個(gè)流水步需要同時(shí)訪問(wèn)內(nèi)存的時(shí)候I就必須把其中的一個(gè)暫停，以避免訪問(wèn)沖突。我們拿來(lái)建模的目標(biāo)機(jī)本身就有這種內(nèi)存訪問(wèn)互斥的性質(zhì)，它的設(shè)計(jì)中已經(jīng)包含了內(nèi)存訪在我們選擇的目標(biāo)機(jī)中，取指IF流水步需要訪問(wèn)內(nèi)存，訪存MEM流水步在執(zhí)行的指令是讀或?qū)憙?nèi)存時(shí)也需要訪問(wèn)內(nèi)存。所以有可能會(huì)發(fā)生內(nèi)存訪問(wèn)沖突。問(wèn)互斥的處理I,所以不需要我們?cè)诮５臅r(shí)候做特殊處理，只要把它的設(shè)計(jì)完全表示出來(lái)即可。寄存器堆及寄存器訪問(wèn)寄存器堆與內(nèi)存是比較相似的：它們都是存儲(chǔ)數(shù)據(jù)的部件。它們都有讀和寫(xiě)操作。兩者之間也有一些差異：存儲(chǔ)的數(shù)據(jù)量上的差異：內(nèi)存中存儲(chǔ)的數(shù)據(jù)很多，在M數(shù)量級(jí)以上;寄存器堆中存儲(chǔ)的數(shù)據(jù)一般就幾十個(gè)。訪問(wèn)方式上的差異：一個(gè)時(shí)刻只能訪問(wèn)一個(gè)內(nèi)存數(shù)據(jù)；在寄存器堆中，一個(gè)時(shí)刻能夠讀寫(xiě)多個(gè)不同寄存器的值。寄存器Token的設(shè)計(jì)方案可以在以下兩種中選擇：第一種是類似于內(nèi)存Token的設(shè)計(jì)，只有一個(gè)Token,包含了多個(gè)寄存器的值。第二種是給每個(gè)寄存器一個(gè)Token,其中有兩個(gè)字段，第一個(gè)字段標(biāo)識(shí)寄存器的編號(hào)，第二個(gè)字段記錄寄存器的值。這樣在寄存器堆中就有多個(gè)Token。第一種方案中Token只有一個(gè)，顯得比較簡(jiǎn)潔，但是這也成了它的一個(gè)缺陷一多個(gè)流水步（變遷）不能同時(shí)訪問(wèn)寄存器堆，即使它們?cè)L問(wèn)的不是同一個(gè)寄存器。事實(shí)上，這種情況是會(huì)出現(xiàn)的2。'當(dāng)MEM流水步需要訪問(wèn)內(nèi)存時(shí)，就暫停取指一拍，IF.ID,EX流水步均暫停一回合。2譯碼1D和寫(xiě)回WB步都可能需要訪問(wèn)寄存器。第二種方案則比較好地利用了內(nèi)存和寄存器堆的差異。把每個(gè)寄存器的值用一個(gè)單獨(dú)的Token來(lái)保存可以滿足并發(fā)訪問(wèn)多個(gè)寄存器的需求。在我們選擇的目標(biāo)機(jī)中只有16個(gè)通用寄存器，數(shù)量不多，也不會(huì)使得模型變得太復(fù)雜。綜合上述原因，我們自然選擇第二種方案。需要注意的是，在該模型下仍然不能同時(shí)讀寫(xiě)同一個(gè)寄存器，因?yàn)楹性摷拇嫫鞯闹档腡oken只有一個(gè)，不可能同時(shí)取出兩個(gè)來(lái)。如果我們需要在一個(gè)流水步（變遷）中訪問(wèn)兩個(gè)寄存器I這兩個(gè)寄存器可能是不同的也可能是相同的，就需要在建模的時(shí)候用一點(diǎn)技巧。在譯碼ID流水步就仃這樣的需要。

圖3.3同時(shí)讀取兩個(gè)寄存器的值的模型示意圖上圖中，白色的Token為寄存器Token,第一個(gè)數(shù)值是寄存器的編號(hào)，第二個(gè)是寄存器的值。黑色的Token是要讀取值的寄存器的標(biāo)號(hào)，范圍在0~3o變遷有兩類綁定，分別對(duì)應(yīng)每一條弧上的上下兩行。第一類綁定是要讀取的兩個(gè)寄存器是同一個(gè)的情況，它們的編號(hào)都是nl。在這類綁定下只要將編號(hào)為nl的寄存器Token取出，得到它的值后再放回。第二類綁定是讀取兩個(gè)不同的寄存器nl和n2的值，這是一般的情況。在這類綁定下要從寄存器堆庫(kù)所中將編號(hào)為nl的寄存器Token和編號(hào)為n2的寄存器Token都取出，得到它們的值后再放回。上面討論的是在一個(gè)變遷中需要訪問(wèn)兩個(gè)寄存器的情況。如果是在兩個(gè)變遷中都需要訪問(wèn)內(nèi)存，則必須在建模時(shí)讓兩個(gè)變遷不會(huì)去同時(shí)訪問(wèn)同一個(gè)寄存器，否則在模擬時(shí)就可能發(fā)生意外。具體內(nèi)容將在后面討論。流水線建模根據(jù)上一節(jié)的主要部件設(shè)計(jì)，我們已經(jīng)可以勾畫(huà)出了這個(gè)5級(jí)流水CPU的對(duì)象Petri網(wǎng)模型的基本框架。基本框架(Memory)//圖3.4EX（EX/MEM）、工、MEMZmem7\IWBJ、WB模型基本框架示意圖圖中IF,ID,EX,MEM和WB這5個(gè)變遷對(duì)應(yīng)了5個(gè)流水段。IF/ID、1D/EX、EX/MEM和MEM/WB這4個(gè)庫(kù)所是5個(gè)流水段之間的段間寄存器。PC庫(kù)所存放的是指令指針pc,Memory是內(nèi)存庫(kù)所，Registers是通用寄存器堆庫(kù)所。在IF和MEM流水步可能會(huì)訪問(wèn)內(nèi)存，在ID和WB流水步可能會(huì)訪問(wèn)寄存器堆，這些都已經(jīng)在圖中表示出來(lái)了。在取指IF流水段會(huì)讀取pc的值,根據(jù)它讀取內(nèi)存獲得要執(zhí)行的指令，最后將pc加1放回PC庫(kù)所。圖中沒(méi)有標(biāo)記弧上的輸入輸出Tokeno流水線的暫停和排空兩種情況的出現(xiàn)條件：(1)流水線暫停根據(jù)目標(biāo)CPU的設(shè)計(jì)，當(dāng)訪存流水步有實(shí)際操作時(shí)，取指和訪存流水步就不能同時(shí)訪問(wèn)內(nèi)存，所以流水線上就要暫停-拍。IF、ID和MEM流水段都暫停一拍，到下一個(gè)回合再處理流水線上的指令。暫停實(shí)際上是插入一-條無(wú)效指令。(2)流水線排空當(dāng)在EX流水步執(zhí)行到一條跳轉(zhuǎn)指令且跳轉(zhuǎn)條件成立，則已經(jīng)取入流水線的下兩條語(yǔ)句不應(yīng)當(dāng)被執(zhí)行，所以要將其排出。并且還要通知IF流水步，根據(jù)新的指令地址讀取下一條指令。排空實(shí)際上是用一條無(wú)效指令替換當(dāng)前的指令。于是，我們需要有一個(gè)控制信號(hào)給IF、ID和EX,決定它們進(jìn)行哪種操作。每個(gè)控制信號(hào)就是一個(gè)Token,相應(yīng)的有?一個(gè)庫(kù)所來(lái)存放這個(gè)信號(hào)。這第三章建模些信號(hào)由EX流水步對(duì)應(yīng)的變遷在觸發(fā)后產(chǎn)生，命名為IF_Ctrl、ID_Ctrl和EX_Ctrl,取值為C_Normal、C_Pause或C_Jump)由于有流水線暫停和排空的情況存在，流水線上就會(huì)有一些無(wú)效指令的存在。為了能讓變遷立刻分辨出當(dāng)前要處理的指令是否為無(wú)效指令，我們?cè)黾恿藥讉€(gè)信號(hào)IE_Enable,EX_Enable,MEM_Enable和WB_Enable分別表示這兒個(gè)流水步當(dāng)前的指令是否為有效指令。它們均由上一級(jí)流水步的變遷在觸發(fā)后產(chǎn)生，它們的取值是true或false。在EX流水步，還有一個(gè)寄存器存放CSZ標(biāo)志位2的值，在條件跳轉(zhuǎn)時(shí)需要用到。在需要跳轉(zhuǎn)的情況下，EX流水步還應(yīng)當(dāng)提供給IF新的指令地址的值，所以需要再增加?個(gè)庫(kù)所NewPC。增加了這些控制信號(hào)后的模型示意圖如下。'在下文中簡(jiǎn)寫(xiě)為Normal,Pause和Jump.或者用首字母N,P.J表示。2表示運(yùn)算結(jié)果是否進(jìn)位、是否為負(fù)、是否為0IF/IDNewPCEnable(NTROLMemoryID/EXEnable1NTROLCONTROLRegisterEX/MEMMEM_EnableTagsMEMMEM/

WBWB_

EnableWB圖3.5加入控制信號(hào)后的模型示意圖上圖中，庫(kù)所右下角的文字表示該庫(kù)所屬于的對(duì)象類，也就是其中存放的Token屬于的對(duì)象類。表3.2對(duì)象類說(shuō)明對(duì)象類名說(shuō)明uint非負(fù)整數(shù)類型bool布爾類型，取值為false或trueCONTROL流水線控制信號(hào)類型，取值為Normal,Pause或JumpUU在停機(jī)的小節(jié)會(huì)增加?種取值Halt。REG通用寄存器類，包含兩個(gè)屬性i和V。i表示寄存器的編號(hào)，V記錄寄存器的值。i和v都是uint類型。MEM內(nèi)存類，它是一個(gè)數(shù)組。數(shù)組的大小是內(nèi)存的大小，數(shù)組的每個(gè)元素都是該對(duì)象類的一個(gè)屬性，記錄內(nèi)存的值。每個(gè)屬性都是uint類型。FLAGS運(yùn)算標(biāo)志類。它包含3個(gè)屬性c,z,s,每個(gè)屬性都是bool類型。II取兩個(gè)流水段名稱的首字母組成。取兩個(gè)流水段名稱的首字母組成。IF與ID段間寄存器類。包含4個(gè)uint類型的屬性：pc,ir,sr,dr。pc保存當(dāng)前指令地址，ir保存指令內(nèi)容，sr和dr是這條指令用到的寄存器編號(hào)。如果沒(méi)有則設(shè)為(uint)-l。IEID與EX段間寄存器類。包含多個(gè)uint類型的屬性pc,sr,aport,bport.imm,ex_op和多個(gè)bool類型的屬性ex_asel,mem_asel,mem_msel,wb_en,wb_dselo具體含義在后面介紹。EMEX與MEM段間寄存器類。包含3個(gè)uint類型的屬性dr,result,addr和4個(gè)bool類型的屬性mem_asel,mem_msel,wb_en,wb_dseL具體含義在后面介紹。MWMEM與WB段間寄存器類。包含3個(gè)uint類型的屬性dr,result,data對(duì)象類名 說(shuō)明和2個(gè)bool類型的屬性wb_en,wb_dsel?具體含義在后面介紹。IF流水步詳述在目標(biāo)CPU設(shè)計(jì)中，IF流水步涉及的部件有PC寄存器、（指令）內(nèi)存、IF/ID寄存器、PC加法器和PC選擇器。涉及的信號(hào)有MEM.MEM_SEL內(nèi)存選讀信號(hào)、JMP_SEL跳轉(zhuǎn)信號(hào)和Addr跳轉(zhuǎn)地址。圖3.6IF流水段數(shù)據(jù)通路圖Addr信號(hào)由NewPC庫(kù)所中的Token給出。JMP_SEL信號(hào)和MEM.MEM_SEL信號(hào)由IF_Ctrl庫(kù)所中的Token?并給出。

圖3.7IF流水段模型圖變遷IF針對(duì)IF.Ctrl中Token的值有三類綁定，所以每條弧上都有三行標(biāo)簽。None表示不需要Token或不產(chǎn)生Token。圖中ii是一個(gè)II類的Token□在第2類綁定下，它的賦值為ii.pc=pc2;ii.ir=m[pc2]；在第3類綁定下，它的賦值為ii.pc=pc;ii.ir=m[pc]o這里類II的定義與原設(shè)計(jì)中的IF/ID間寄存器稍有不同，多了sr和dr兩個(gè)字段。作用是提前對(duì)指令中要用到的寄存器編號(hào)進(jìn)行解碼，這樣可以大大簡(jiǎn)化ID變遷的設(shè)計(jì)。這在下一小節(jié)的模型中可以明顯地體現(xiàn)出來(lái)。IF流水步地建模難度不大，復(fù)雜度也不高。ID流水步詳述ID流水步的主要工作是譯碼，其中建模難度最大的是兩個(gè)寄存器的同時(shí)讀取，我們已經(jīng)在3.2.3中作了一些討論。

ID流水步涉及的部件有寄存器堆、控制碼生成器、IF/ID寄存器、ID/EX寄存器、譯碼邏輯。在該段會(huì)生成EX、MEM和WB流水步使用的控制信號(hào)。圖3.8ID流水段數(shù)據(jù)通路圖ID變遷共有5類綁定。第1類是從ID_Ctrl取到流水線控制信號(hào)Pauseo此時(shí)大部分弧上都為None。第2類是從ID_Ctrl取到流水線控制信號(hào)Jumpo此時(shí)從IF/ID和ID_Enable各輸入一個(gè)Token,向EX_Enable輸出一個(gè)值為false的Token,

向ID/EX輸出一個(gè)未賦值的IE類Tokeno整個(gè)操作就是排空當(dāng)前流水線上的指令。后3類都是從ID_Ctrl取到流水線控制信號(hào)Normal-它們的區(qū)別在于需要從Registers中取幾個(gè)Token,可以是0個(gè)、1個(gè)或2個(gè)。在這里的判斷中用到了在上一個(gè)流水步中提前解析的sr和dr的值：如果sr和dr均為-1,則不需要從Registers中取Token；如果sr與dr相等，或者其中有--個(gè)為-1,則只需要從Registers中取1個(gè)Token；如果sr與dr不相等且都不等于-1,則只需要從Registers中取2個(gè)TokenoNoneii((ii.sr**-None(RegisteryREGVrOrO.r1圖Noneii((ii.sr**-None(RegisteryREGVrOrO.r1圖3.9ie的賦值在上圖中被省去。ie.pc=ii.pc;ie.sr=ii.sr;ie.dr\ ) VEnable)]--****!IINone NoneH b1H(ii.sr**-1&&ii.dr?*-1) truel||ii.sn?rO.i)&&(ii.dr??-1||ii.dr??rO.i))trueii(ii.sr??r1i&&iisr??rO.i) true Pause , 、ID —rXal——(ID_Ctrl)Normal '_ J/ . NormalK TORtrolNonex.Noneie 、falseie trueie true、ie true\ ) kEnable) -^1e ^caiID流水段模型圖=ii.dr;(直接從上一個(gè)段間寄存器復(fù)制)ie.aport=ii.dr寄存器的值;ie.bport=ii.sr寄存器的值;（讀取寄存器值）ie.ex_op（運(yùn)算符）、ie.imm（立即數(shù)）、ie.wb_en（結(jié)果是否要寫(xiě)回寄存器）、ie.wb_dsel（寫(xiě)回運(yùn)算結(jié)果/讀內(nèi)存結(jié)果）、ie.mem_asel（是否需要訪存）、ie.mem_msel（讀/寫(xiě)）、ie.ex_asel（同mem_msel）均從ii.ir（指令值）中解析出來(lái)。需要注意的是，這里并沒(méi)有解決可能發(fā)生的ID流水段和WB流水段同時(shí)讀寄存器堆沖突的問(wèn)題。這個(gè)問(wèn)題將在3.3.8節(jié)解決。EX流水步詳述EX流水段中主要包含ALU,跳轉(zhuǎn)指令控制器。中主要。他的建模難度不高，但是賦值部分比較復(fù)雜。在目標(biāo)CPU設(shè)計(jì)中，EX流水步涉及的部件有寄存器堆、控制碼生成器。在這里需要完成算術(shù)運(yùn)算、判斷是否需要跳轉(zhuǎn)、判斷下-時(shí)刻是否需要因?yàn)樽x取內(nèi)存數(shù)據(jù)而暫停流水線。所以，變遷EX會(huì)生成許多控制信號(hào)（Token）。

圖3.10EX流水段數(shù)據(jù)通路圖

圖3.11EX流水段模型圖EX變遷中，前3類綁定分別對(duì)應(yīng)于流水線暫停、流水線排空、流水線上是無(wú)效指令。第4類綁定中需要對(duì)cl,em,fo進(jìn)行賦值。如果當(dāng)前指令是跳轉(zhuǎn)指令且跳轉(zhuǎn)條件成立，則cl取值為Jump；如果當(dāng)前指令的ie.mem_asel為true,即需要訪問(wèn)內(nèi)存，則cl取值為Pause；否則cl取值為Normal。一條指令不可能同時(shí)需要訪存和跳轉(zhuǎn)。em的各屬性的值通過(guò)ie中的屬性的值計(jì)算而得，需要處理ALU的各種運(yùn)算乙最后，運(yùn)算標(biāo)志位fo根據(jù)運(yùn)算過(guò)程和結(jié)果計(jì)算得到。具體運(yùn)算過(guò)程不難實(shí)現(xiàn)但午常瑣碎，所以在這里略去。

MEM流水步詳述MEM流水步的操作比較簡(jiǎn)單，僅在指令需要讀內(nèi)存或者寫(xiě)內(nèi)存時(shí)才有實(shí)際操作。自然地，該流水段中需要用到內(nèi)存。WBMEMAddrDRFlagsResultMUMSLLWBDRDataResultWBMEMAddrDRFlagsResultMUMSLLWBDRDataResult圖3.12MEM流水段數(shù)據(jù)通路圖MEM變遷有3類綁定。第1類綁定是流水線上是無(wú)效指令。此時(shí)不需要從Memory庫(kù)所中取出Token,只要向下一個(gè)流水步輸出一個(gè)無(wú)效指令。第2類綁定是指令有效但不需要訪問(wèn)內(nèi)存，即em.mem_asel為false□此時(shí)也不需要從Memory庫(kù)所中取出Token,只需要把一些數(shù)據(jù)傳到MEM/WB段間寄存mw.dr=em.dr;mw.result=em.result;mw.wb_en=em.wb_en;mw.wb_dsel=em.wb_dselo第3類綁定是指令有效且需要訪問(wèn)內(nèi)存，即em.mem_asel為true。此時(shí)需要從Memory庫(kù)所中取出Token,根據(jù)em.mem_msel的值得知是讀操作還是寫(xiě)操作，完成操作，并對(duì)mw進(jìn)行賦值。最后，把內(nèi)存類m78放回Memory庫(kù)所。18如果是讀操作，則m'=m。如果是寫(xiě)操作，則m'是m的某一位修改過(guò)之后的值。

WB流水步詳述WB流水步的操作是寫(xiě)回寄存器堆。WBWB.REGLnableDataResultWBWB.REGLnableDataResult圖3.14WB流水段數(shù)據(jù)通路圖圖3.15WB流水段模型圖WB變遷有3類綁定。第1類綁定是流水線上是無(wú)效指令。此時(shí)不需要從Registers庫(kù)所中取出寄存器Token,也不需要輸出任何Token。第2類綁定是指令有效但不寫(xiě)回寄存器，即mw.wb_en為false□此時(shí)與第一類情況同樣處理。第3類綁定是指令有效且要寫(xiě)回寄存器，即mw.wb_en為true。此時(shí)需要從Registers庫(kù)所中取出一?個(gè)寄存器Tokenrl,且它的編號(hào)等于mw.dr。根據(jù)mw.wb_dsel的值，決定是把mw.data或是mw.result寫(xiě)入rl.v中，最后把rl放回到Registers庫(kù)所，完成了寫(xiě)回寄存器的操作。消除數(shù)據(jù)相關(guān)性流水線中的數(shù)據(jù)相關(guān)包括“寫(xiě)后讀相關(guān)”、“讀后寫(xiě)相關(guān)”、“寫(xiě)后寫(xiě)”相關(guān)。我們的建模的這個(gè)流水線設(shè)計(jì)采用的是順序執(zhí)行的方式，因此只存在“寫(xiě)后讀”相關(guān)。在該設(shè)計(jì)中使用硬件的方式來(lái)消除數(shù)據(jù)相關(guān)，采用了建立前向旁路的方法。舉例來(lái)說(shuō)，有如下3條連續(xù)的指令：第三章建模ANDrO,rlADDrO,rlSUBr0,r2ADD和SUB兩條指令的操作數(shù)均依賴于第?條AND指令對(duì)寄存器rO的操作結(jié)果。AND指令必須到WB階段才能將運(yùn)算結(jié)果寫(xiě)回寄存器rO中，而緊隨其后的ADD指令和SUB指令必須在EX階段就準(zhǔn)備好操作數(shù)，因此就引起了先寫(xiě)后讀沖突。雖然ADD指令要到WB階段才能將ALU的運(yùn)算結(jié)果寫(xiě)回寄存器，但是這一結(jié)果在EX階段結(jié)束時(shí)就可以得到，并保存在段間寄存器中隨著流水線逐級(jí)下傳，因此通過(guò)建立前向旁路的方法可以消除這一沖突。以ALU的A-Port數(shù)據(jù)為例。在不考慮數(shù)據(jù)沖突時(shí)，A-Port的數(shù)據(jù)僅由ID/EXE寄存器得到。在引入旁路后，增加了兩個(gè)數(shù)據(jù)來(lái)源：EX/MEM寄存器中的Result和MEM/WB寄存器中的Result或Data。選擇邏輯如下：IfID/EX.dr=EX/MEM.drandEX/MEM.wb_enthenSelectEX/MEM.Result;ElseIfID/EX.dr=MEM/WB.drandMEM/WB.wb_enthenIfMEM/WB.wb_dselthenSelectMEM/WB.data;ElseSelectMEM/WB.result;ElseSelectID/EX.aport;也就是說(shuō)，在EX流水步執(zhí)行的時(shí)候，需要得到MEM和WB流水步中正在執(zhí)行的指令需要寫(xiě)回的寄存器編號(hào)及數(shù)值。我們也需要把這個(gè)部件建模添加到對(duì)象Petri網(wǎng)模型中。我們知道這些段間寄存器的值是儲(chǔ)存在一個(gè)Token中的，而這唯一的Token是傳遞給下一個(gè)流水步的變遷使用的，不可能把它作為之前的流水步變遷EX的輸入。所以，要想在變遷EX中得到這些值，就需要把這些值復(fù)制一份。要無(wú)延時(shí)地復(fù)制這些值，就需要在生成它們的時(shí)候多生成?份。舉例來(lái)說(shuō)，我們要把WB流水步執(zhí)行的指令需要寫(xiě)回的寄存器編號(hào)及值(它們被暫存在MEM/WB寄存器中)讓EX變遷能夠訪問(wèn)到，就需要新建一個(gè)庫(kù)所WB_FWD_EX,使得它的值與MEM/WB中相應(yīng)屬性值相等。所以這個(gè)庫(kù)所中Token的產(chǎn)生就要和MEM/WB中Token的生成一樣，在MEM變遷中完成，如卜圖。圖3.16前向旁路模型圖前向旁路WB_FWD_EX庫(kù)所是一個(gè)寄存器類型(REG)的庫(kù)所，表示的是WB流水步當(dāng)前指令要寫(xiě)回的寄存器的編號(hào)和值。如果不需要寫(xiě)回寄存器，則把編號(hào)置為-1。類似地，我們還需要建立MEM_FWD_EX庫(kù)所、WB_FWD」D庫(kù)所和MEM_FWDJD庫(kù)所。有了WB_FWD」D庫(kù)所，ID流水段和WB流水段同時(shí)讀寄存器堆沖突的問(wèn)題也就解決了。只有在WB變遷中可能會(huì)寫(xiě)通用寄存器，在ID變遷中只會(huì)讀通用寄存器。如果在ID步不能讀到寄存器的值，還可以利用前向旁路來(lái)得到所需的寄存器的值。所以，在對(duì)…個(gè)通用寄存器需要同時(shí)讀和寫(xiě)的時(shí)候，應(yīng)當(dāng)優(yōu)先滿足WB變遷的寫(xiě)操作。ID變遷中的讀操作僅在WB變遷中不需要寫(xiě)該寄存器時(shí)，才訪問(wèn)該寄存器的Token。這樣就徹底避免了沖突的發(fā)生。li&&N((ii.sr?-1||Msr=rO.i||ii.sr?r21)&&(ii.drs?-1||iidr*?rO.i||ii.dr??r2.i))ii(ii.sr??r1.i&&ii.sr??rO.i)圖3.17消除訪問(wèn)寄存器沖突后的ID流水段模型示意圖上圖中略去了一些與訪問(wèn)寄存器沖突無(wú)關(guān)的庫(kù)所和輸入輸出弧。停機(jī)以上介紹的建模過(guò)程都是使得模型能夠正常的工作。這一節(jié)討論的問(wèn)題是如果讓對(duì)象Petri網(wǎng)模型在執(zhí)行到停機(jī)指令HLT之后，能夠停止觸發(fā)，達(dá)到停下來(lái)的效果。需要注意的是，停機(jī)指令的判斷最早可以在EX流水段做。一定不能在EX流水段之前的流水段上做。因?yàn)橹挥袌?zhí)行到EX流水段的指令才是一定會(huì)執(zhí)行的指令，之前的流水線上的指令可能會(huì)因?yàn)槌绦蛱D(zhuǎn)而被排出流水線。當(dāng)執(zhí)行到停機(jī)指令后，也需要排空其后的流水線上的所有指令。這點(diǎn)和跳轉(zhuǎn)指令比較類似，所以我們?cè)贓X變遷上做停機(jī)指令的判斷是比較合適的。我們可以利用向IF、ID和EX流水步給出的下一回合動(dòng)作的控制信號(hào)IF_CtrKID_Ctrl和EX_Ctrl來(lái)處理停機(jī)的情況。給CONTROL類增加一種取值CJHalt。當(dāng)變遷IF、ID和EX得到CJHalt的控制信號(hào)時(shí)，則從輸入的段間寄存器中取出Token,不向輸出的段間寄存器中輸出Token。這樣，前3流水段就立刻排空且停止運(yùn)轉(zhuǎn)了。后兩個(gè)流水段在處理完流水線上的剩余指令后也會(huì)停止。建模小結(jié)完整模型綜合上述對(duì)各個(gè)部分的建模，可以得到一個(gè)完整的對(duì)象Petri網(wǎng)模型圖。圖中省略了弧上的標(biāo)記。IF/IDEnable'CONTROLITROLEnableMemoryID/EXRegisterEX/MEMEnableMWMEM_EnableMEMWDIMEMWDMEM/WBWB_FWD_EXCONTROLMEMWB圖3.18完整的模型示意圖表3.3模型的初始Token設(shè)置庫(kù)所名初始TokenPCuint0（初始的指令指針值）RegistersREG16個(gè)Token,i字段分別為0~15MemoryMEM1個(gè)Token,屬性的個(gè)數(shù)為內(nèi)存的大小。IF/IDII1個(gè)未設(shè)值的TokenID/EXIE1個(gè)未設(shè)值的TokenEX/MEMEM1個(gè)未設(shè)值的TokenMEM/WBMW1個(gè)未設(shè)值的TokenID_Enableboolfalse（初始時(shí)刻，該流水段中為無(wú)效指令）EX_Enableboolfalse（初始時(shí)刻，該流水段中為無(wú)效指令）MEM_Enableboolfalse（初始時(shí)刻，該流水段中為無(wú)效指令）WB_Enableboolfalse（初始時(shí)刻，該流水段中為無(wú)效指令）IF_CtrlCONTROLNormal（沒(méi)有暫停、跳轉(zhuǎn)或停機(jī)）ID_CtrlCONTROLNormal（沒(méi)有暫停、跳轉(zhuǎn)或停機(jī)）EX.CtrlCONTROLNormal（沒(méi)有暫停、跳轉(zhuǎn)或停機(jī)）NewPCuint0FlagsFLAGS1個(gè)未設(shè)值的TokenMEM_FWD_IDREG（-1,0）（表示不寫(xiě)回寄存器）MEM_FWD_EXREG（-1,0）（表示不寫(xiě)回寄存器）各個(gè)類的定義見(jiàn)表3.2庫(kù)所名類19初始TokenWB.FWDJDREG(-1,0)(表示不寫(xiě)回寄存器)WB_FWD_EXREG(-1,0)(表示不寫(xiě)回寄存器)在不考慮停機(jī)的情況下，任意時(shí)刻5個(gè)變遷都應(yīng)當(dāng)能并發(fā)發(fā)生。在停機(jī)發(fā)生之前的任意時(shí)刻，每個(gè)存儲(chǔ)信號(hào)的庫(kù)所中的Token數(shù)量應(yīng)該都是1個(gè)。PC寄存器和段間寄存器的庫(kù)所中的Token數(shù)量也應(yīng)該是1個(gè)。內(nèi)存和寄存器堆庫(kù)所中的Token數(shù)目也不應(yīng)該發(fā)生變化。常見(jiàn)問(wèn)題小結(jié)一個(gè)信號(hào)需要同時(shí)在多個(gè)流水段被用到因?yàn)樾盘?hào)所蘊(yùn)含的數(shù)據(jù)只能通過(guò)Token進(jìn)行傳遞。一個(gè)流水段對(duì)應(yīng)的變遷想要獲得某個(gè)信號(hào)，就必須把包含這個(gè)信號(hào)的Token作為變遷輸入。但是一個(gè)Token在一個(gè)時(shí)刻只能作為一個(gè)變遷的輸入。為了使得流水段可以并發(fā)執(zhí)行，我們需要把這個(gè)信號(hào)復(fù)制多份，也就是是產(chǎn)生多個(gè)Token。同時(shí)，為了避免不必要的混淆，我們把存放這些Token的庫(kù)所也復(fù)制多個(gè)，每次只向這些存放信號(hào)的庫(kù)所輸出一個(gè)Token。比如，IF_Ctrl、ID_Ctrl和EX_Ctrl就是這種設(shè)計(jì)的產(chǎn)物。MEM_FWDJD和MEM_FWD_EX也是完全相同的，并且它們的值與EX/MEM中的相關(guān)屬性是一致的。類似的還有WB_FWD」D、WB_FWD_EX和MEM/WBo(2)數(shù)據(jù)的訪問(wèn)沖突上述方法可以解決一個(gè)信號(hào)被多個(gè)流水段用到的問(wèn)題，但是這些信號(hào)都只是一次性使用的。這種方法對(duì)內(nèi)存、通用寄存器等存儲(chǔ)部件中的數(shù)據(jù)不適用。試想如果我們把通用寄存器Token也復(fù)制一份，供兩個(gè)變遷同時(shí)各取走一個(gè)。那么當(dāng)我們要修改寄存器的值時(shí)，就要把兩個(gè)Token都取來(lái)，修改他們的值屬性。這時(shí)又會(huì)發(fā)生訪問(wèn)沖突，不是一個(gè)正確的解決方法。要解決該問(wèn)題，必須對(duì)多個(gè)存在訪問(wèn)沖突可能的變遷進(jìn)行協(xié)同設(shè)計(jì)，排定一-個(gè)優(yōu)先級(jí)。采用(1)中的方法將高優(yōu)先級(jí)的變遷在下一時(shí)刻要訪問(wèn)的資源的編號(hào)傳遞過(guò)來(lái)，作為本變遷的一個(gè)輸入。然后通過(guò)觸發(fā)條件確保在下一時(shí)刻不會(huì)和優(yōu)先級(jí)的變遷爭(zhēng)用同一個(gè)數(shù)據(jù)資源。(3)一個(gè)寄存器的值的設(shè)置在由兩個(gè)流水段輸出的值之間選擇這樣的情況發(fā)生在PC寄存器上，通過(guò)一個(gè)2路選擇器，PC寄存器的值有可能來(lái)自于IF流水步(正常+1)也可能來(lái)自于EX流水步(跳轉(zhuǎn)地址)。由于我們不容易協(xié)調(diào)究竟讓哪個(gè)流水步的變遷向該寄存器的庫(kù)所輸出Token,所以最好的方法是把該庫(kù)所一拆為二。兩個(gè)變遷各向一個(gè)庫(kù)所進(jìn)行輸出，在把原庫(kù)所作為輸入的變遷中，把拆分后的庫(kù)所都作為它的輸入，各取一個(gè)Token,此時(shí)再根據(jù)情況選擇正確的數(shù)據(jù)。相當(dāng)于把數(shù)據(jù)選擇滯后了一拍。第四章驗(yàn)證簡(jiǎn)單不變量我們從簡(jiǎn)單的不變量入手，驗(yàn)證模型是否和我們的期望一致。單庫(kù)所Tbken數(shù)目不變量以PC庫(kù)所為例，與它相連的弧只有兩條，且都連接到變遷IF。圖4.1模型的PC庫(kù)所局部圖圖中，在任何一類綁定的情況下，從PC庫(kù)所取出的Token數(shù)等于放入PC庫(kù)所中的Token數(shù)。因此，PC庫(kù)所中的Token數(shù)目不會(huì)變化，是一個(gè)不變量，等于初始時(shí)的1個(gè)。這里只考慮Token的數(shù)量，不考慮Token的不同取值。與之類似的，Memory庫(kù)所、Registers庫(kù)所、Flags庫(kù)所、EX_Ctrl庫(kù)所和MEM_FWD_EX庫(kù)所也有這樣的性質(zhì)。對(duì)于Registers庫(kù)所，我們還可以證明其中的Token的序號(hào)屬性不會(huì)發(fā)生變化。即16個(gè)Token的序號(hào)分別為0~15。

雙庫(kù)所Token數(shù)目不變量研究完了單一庫(kù)所的不變量后，我們尋找涉及到兩個(gè)庫(kù)所的不變量。有一些庫(kù)所對(duì)中的Token數(shù)目始終相等，所以他們的差也是一個(gè)不變量。考慮IF/ID庫(kù)所和ID_Enable庫(kù)所。與他們相連的庫(kù)所是IF和ID。圖4.2模型的IF/ID、ID_Enable庫(kù)所局部圖從圖中可見(jiàn)，IF變遷的任一種綁定向這兩個(gè)庫(kù)所中輸出的Token數(shù)目是一樣的，ID變遷的任--種綁定從這兩個(gè)庫(kù)所中輸入的Token數(shù)目是一樣的。所以IF/ID-ID_Enable的差是恒定的，等于初始時(shí)的0。與之類似的，ID/EX庫(kù)所與EX_Enable庫(kù)所含有的Token數(shù)目相同，EX/MEM庫(kù)所與MEM_Enable庫(kù)所含有的Token數(shù)目相同，MEM/WB庫(kù)所與WB_Enable庫(kù)所含有的Token數(shù)目相同，IF_Ctrl庫(kù)所與NewPC庫(kù)所含有的Token數(shù)目相同。極大并發(fā)意義下的不變量在3.2.1節(jié)中我們提到了該模型的正確性有一個(gè)附加的條件——在任意時(shí)刻，都并發(fā)觸發(fā)盡可能多的變遷。流水線上的每-段都是一直不停地工作，即使是處理一-條無(wú)效指令或者執(zhí)行排空流水線的操作時(shí)，它也是在工作的。那么，作為與之對(duì)應(yīng)的建模后的變遷，每個(gè)變遷在每一回合都應(yīng)該要觸發(fā)（除非遇到了停機(jī)指令）。所以,每次都應(yīng)當(dāng)是5個(gè)變遷同步觸發(fā)。在本章的討論中，如非特別說(shuō)明，均不考慮處理停機(jī)指令的情況?，F(xiàn)在，我們假設(shè)每次都是5個(gè)變遷同步觸發(fā)。在這樣的假設(shè)下，分析庫(kù)所中Token個(gè)數(shù)的變化情況。在上一節(jié)中已經(jīng)證明了Token數(shù)不會(huì)變化的庫(kù)所就不需要討論了。表4.1各變遷觸發(fā)后庫(kù)所中Token數(shù)目變化統(tǒng)計(jì)表IFIDEXMEMWB合計(jì)IF/IDl*/0-l*/00ID/EXl*/0-l*/00EX/MEM1-10MEM/WB1-10IF_Ctrl-110ID_Ctrl-110MEM_FWD_ID-110WB_FWD」D-110IFIDEXMEMWB合計(jì)WB_FWD_EX-110表中的值是根據(jù)模型圖得出的。其中*號(hào)表示當(dāng)控制信號(hào)（IF_Ctrl或ID_Ctrl）不為Pause時(shí)，變化值是1,否則是0。1*和-1*正好抵消，得到0。從表中可見(jiàn)，在5個(gè)變遷并發(fā)觸發(fā)的前提下，這些庫(kù)所中的Token數(shù)不變。因?yàn)閘D_Enable中的Token數(shù)與IF/ID中的相等，所以ID_Enable中也一直是1個(gè)Token。對(duì)其它幾個(gè)庫(kù)所也是一樣的。五變遷并發(fā)的可行性有了上面的基礎(chǔ)，我們可以進(jìn)一步驗(yàn)證模型是否在每一時(shí)刻都能有5個(gè)變遷同時(shí)觸發(fā)。證明的方法是用數(shù)學(xué)歸納法證明下述命題：在時(shí)刻k,模型中的每個(gè)庫(kù)所中都有1個(gè)Token（寄存器堆除外，它有16個(gè)Token）,且上一個(gè)回合是5個(gè)變遷同時(shí)發(fā)生。數(shù)學(xué)歸納法的第一步很容易驗(yàn)證。從初始狀態(tài)開(kāi)始，確實(shí)可以5個(gè)變遷同時(shí)觸發(fā)，且觸發(fā)完成后各庫(kù)所中的Token數(shù)目不變。數(shù)學(xué)歸納法的第二步是從時(shí)刻k歸納假設(shè)成立推出時(shí)刻k+1歸納假設(shè)也成立。從WB流水段的模型圖中可以看出，只要MEM/WB和WB_Enable庫(kù)所中有Token且Registers中有序號(hào)為0~15的Token,則該變遷一定能觸發(fā)。類似地MEM和EX變遷也都能觸發(fā)。ID變遷要觸發(fā)需要考察它是否能從Registers庫(kù)所中取出所需的Token。因?yàn)閃B_FWD_ID和MEM/WB庫(kù)所中都只有一個(gè)Token,且上一時(shí)刻5個(gè)變遷都觸發(fā)了（意味著MEM變遷一定會(huì)向WB_FWD_ID和MEM/WB庫(kù)所輸出一個(gè)Token）,所以WB_FWD_ID和MEM/WB庫(kù)所中的Token一定是上一時(shí)刻剛產(chǎn)生的，兩者的值相關(guān)的。所以，在ID變遷中得到了這一時(shí)刻WB變遷會(huì)取走的寄存器序號(hào)。由于ID作了變遷消除數(shù)據(jù)沖突的設(shè)計(jì)，只要驗(yàn)證出它的正確性，就可以保證ID變遷的觸發(fā)。IF變遷的觸發(fā)也面臨著是否能從Memory庫(kù)所中取到Token的問(wèn)題。依照上一段的做法，先證明IF_CtH和EX/MEM庫(kù)所中的Token是相關(guān)的。然后，只要驗(yàn)證IF變遷消除訪問(wèn)內(nèi)存沖突的邏輯正確性，就可以保證IF變遷的觸發(fā)。同理IF_Ctrl和ID_Ctrl都是在上-時(shí)刻產(chǎn)生的，他們的值一定相同。所以根據(jù)4.2節(jié)的證明，五個(gè)變遷觸發(fā)后，各庫(kù)所的Token個(gè)數(shù)均不變。于是,歸納假設(shè)在時(shí)刻k+1也成立。證明完畢。當(dāng)EX變遷執(zhí)行到停機(jī)指令后，會(huì)向IF_Ctrl、ID_Ctrl和EX.Ctrl庫(kù)所輸出值為Halt的Token。在下一"^時(shí)刻的并發(fā)執(zhí)行時(shí)，庫(kù)所中的Token數(shù)不變量會(huì)被破壞，導(dǎo)致變遷不能發(fā)生，最后使得模型停下來(lái)。第五章模擬器需求分析我們需要設(shè)計(jì)并實(shí)現(xiàn)一個(gè)對(duì)象Petri網(wǎng)模擬器，用來(lái)執(zhí)行對(duì)象Petri網(wǎng)模型。該模擬器不是針對(duì)某一特定的目標(biāo)機(jī)設(shè)計(jì)的，而是可以用于不同的對(duì)象Petri網(wǎng)。在當(dāng)前階段，該模擬器主要是作為內(nèi)部使用，所以把主要的注重力放在核心部分的功能，而對(duì)??些輔助性功能（如：界面）不作高的要求。功能需求主要的功能就是能夠以約定的格式，從輸入文件中讀入并解析一個(gè)對(duì)象Petri網(wǎng)模型，然后執(zhí)行它。整個(gè)輸入的模型分成兩大部分——申明部分和圖形部分。?申明部分包括對(duì)象類的申明、變量的申明。?圖形部分包括庫(kù)所、變遷和弧的信息。＞庫(kù)所的描述中包括庫(kù)所名、庫(kù)所的類型和初始Token設(shè)置。＞變遷的描述中包括它的名字、所有輸入弧的起點(diǎn)庫(kù)所、所有輸出弧的終點(diǎn)庫(kù)所、各條弧上的標(biāo)簽以及各類綁定成立的條件。在讀入Petri網(wǎng)模型時(shí)，先把圖形部分的大部分信息以文本的格式作為標(biāo)簽保存在相應(yīng)的庫(kù)所、變遷或弧上，到執(zhí)行前再解析。這樣做是為了以后改成圖形化輸入后能夠平滑地過(guò)渡。在解析的過(guò)程中如果遇到錯(cuò)誤，則給出提示信息。這可以幫助加快模型的書(shū)寫(xiě)過(guò)程。在執(zhí)行的過(guò)程中能夠看到中間結(jié)果。性能需求作為一個(gè)模擬器，當(dāng)然希望它的運(yùn)行性能越高越好。但是過(guò)于追求性能可能會(huì)使設(shè)計(jì)變得非常復(fù)雜。所以，我們?cè)谛阅芎蛷?fù)雜度中做一個(gè)折衷，對(duì)一些影響性能較大的部分作優(yōu)化。運(yùn)行需求我們希望這個(gè)模擬器能夠作為開(kāi)源程序被更多的人使用，所以我們不希望它被操作系統(tǒng)所約束，希望它是一個(gè)跨平臺(tái)的程序?？傮w設(shè)計(jì)概述從組件的角度，整個(gè)程序可以分為6個(gè)部分：庫(kù)所（Place）、變遷（Transition）、弧（Arc）、對(duì)象類定義（TypeDef）、Token和執(zhí)行代碼。每一部分都對(duì)應(yīng)了程序中的一個(gè)類。從功能的角度，整個(gè)程序可以分為2個(gè)部分：讀入解析和模擬執(zhí)行。處理流程首先讀入Petri網(wǎng)模型申明部分中的類型申明，創(chuàng)建各個(gè)類的定義類（TypeDef）,然后讀入變量申明。將類型名和變量名都加入全局標(biāo)識(shí)符詞典。接著，讀入各個(gè)庫(kù)所的申明。如前所述，先把庫(kù)所的類型、初始Token列表等以文本的形式保存在庫(kù)所類（Place）中，稍后再解析。同時(shí)，把庫(kù)所名加入到庫(kù)所/變遷名字典中。再讀入各個(gè)變遷的申明（包括了輸入、輸出弧的信息）。把讀入的模型代碼都以文本的形式保存在變遷類（Transition）或弧類（Arc）中。同時(shí)，把變遷名加入到庫(kù)所/變遷名字典中。至此，輸入的過(guò)程結(jié)束。開(kāi)始解析保存在庫(kù)所、變遷和弧中的文本信息。將類型名轉(zhuǎn)換成類的編號(hào)，將對(duì)象類的值轉(zhuǎn)換成內(nèi)部編碼，將輸入輸出Token及賦值語(yǔ)句轉(zhuǎn)換成中間代碼。如果以上解析均成功，則可以開(kāi)始執(zhí)行。對(duì)任一變遷，先執(zhí)行它的輸入Token搜索代碼和條件判斷代碼，如果條件判斷通過(guò)，則表示該變遷可以觸發(fā)。從輸入庫(kù)所中移除已取出的Token,執(zhí)行它的Token生成代碼，就相當(dāng)于觸發(fā)了這個(gè)變遷。當(dāng)沒(méi)有變遷可以觸發(fā)時(shí)，程序停止。詳細(xì)設(shè)計(jì)類型定義類的設(shè)計(jì)類型定義類是用來(lái)保存一個(gè)對(duì)象類申明的。我們需要用到的對(duì)象類有：數(shù)值類型，比如模型中的uint。枚舉類型，比如模型中的bool和CONTROL。對(duì)象類型。該類可以有多個(gè)屬性，每個(gè)屬性有一個(gè)屬性名稱，每個(gè)屬性可以有自己的類型（必須為簡(jiǎn)單類型）。比如模型中的REG等。數(shù)組類型。該類可以有很多個(gè)屬性，屬性通過(guò)下標(biāo)來(lái)指定，屬性的個(gè)數(shù)為數(shù)組的長(zhǎng)度。比如模型中的MEM。其中數(shù)值類型和枚舉類型是簡(jiǎn)單類型，它們都只有一個(gè)屬性值。這種類型的Token可以用一個(gè)變量來(lái)保存其值。（枚舉類型的值可以轉(zhuǎn)成0開(kāi)始的整數(shù)值）對(duì)象類型一般包括兒個(gè)屬性值。這種類型的Token可以用一個(gè)STL中的vecto"。來(lái)保存其各個(gè)屬性的值。當(dāng)要訪問(wèn)某個(gè)屬性的值時(shí)，只要得到該屬性是第幾個(gè)，用它作下標(biāo)來(lái)訪問(wèn)。數(shù)組類型則可能包含許多個(gè)屬性值，它的數(shù)量可能是非常之巨大，如果我們給它的每個(gè)屬性都分配存儲(chǔ)空間將會(huì)占據(jù)掉極大的內(nèi)存空間。而事實(shí)上，數(shù)組類型主要是用來(lái)描述內(nèi)存的。其特點(diǎn)是內(nèi)存中絕大部分位置在整個(gè)模型的執(zhí)行過(guò)程中是不會(huì)被訪問(wèn)到的。為它們分配空間將造成極大的浪費(fèi)，且影響執(zhí)行速度。所以我們選用STL中的map來(lái)保存數(shù)組中所有用到的元素的值。STL中的map是用紅黑樹(shù)實(shí)現(xiàn)的，是在占用空間與尋找時(shí)間之間的較好折衷。我們?yōu)樗鼈兌x了一個(gè)抽象的基類TypeDefo表5.1模擬器對(duì)象類型定義類表類名說(shuō)明20標(biāo)準(zhǔn)模板庫(kù)STL中的數(shù)組容器。

類名說(shuō)明TypeDef基類成員變量：unsignedm_uTypeID;//類型編號(hào)stringm_strName; //類型名稱成員函數(shù)：conststring&GetName()const;//取對(duì)象類的名稱virtualToken*CreateToken()const;//創(chuàng)建該類的一個(gè)TokenvirtualToken*CreateToken(conststring&expr)const;〃根據(jù)expr的內(nèi)容，創(chuàng)建該類的一個(gè)帶值的Token,只有簡(jiǎn)單類型能創(chuàng)建成功virtualboolIsSimple()const;//是否為簡(jiǎn)單類型virtualboolIsArray()const;//是否為數(shù)組類型SimpleTypeDef繼承TypeDef描述一個(gè)簡(jiǎn)單類型NumericTypeDef繼承SimpleTypeDef描述一個(gè)數(shù)值類型EnumTypeDef繼承SimpleTypeDef描述一個(gè)枚舉類型成員變量：vector<string>m_ValueNames;//類型的各種取值成員函數(shù)：voidAddEnumValue(conststring&vn);//增加枚舉值STNameToValue(conststring&expr)const;〃得至U內(nèi)部表示數(shù)值

類名說(shuō)明ObjectTypeDef繼承TypeDef描述一個(gè)對(duì)象類型成員變量：vector<pair<string,unsigned>>m_Fields;〃各屬性的名稱及類型編號(hào)成員函數(shù)：boolAddField(conststring&fieldname,unsignedtype);〃增力口屬性boolGetFieldID(conststring&fieldname,unsigned&id)const;〃通過(guò)屬性名，獲得屬性編號(hào)。即該類型的第兒個(gè)屬性ArrayTypeDef繼承TypeDef描述一個(gè)數(shù)組類型成員變量：uint64把unsignedlonglong定義為uint64o把unsignedlonglong定義為uint64ounsignedm_uContentTypeID;〃數(shù)組元素類型，必須是?個(gè)簡(jiǎn)單類型成員函數(shù)：voidInit(uint64size,unsignedsubtype);//初始化，設(shè)置大小和子類型所有的類型定義保存在一個(gè)全局?jǐn)?shù)組vector<TypeDef*>g_types中，數(shù)組的下標(biāo)與TypeDef中的m_uTypeID對(duì)應(yīng)。模擬器中預(yù)定義了簡(jiǎn)單數(shù)值類型uint(表示非負(fù)整數(shù))和枚舉類型bool(取值為false或true,false對(duì)應(yīng)0,true對(duì)應(yīng)DoToken類的設(shè)計(jì)Token類是在模型執(zhí)行過(guò)程中，實(shí)際儲(chǔ)存Token的值的類。我們給Token類的數(shù)據(jù)存儲(chǔ)申明了一個(gè)ST類型。取StorageType的首字母，它是存儲(chǔ)Token的所有屬性的類型。雖然我們現(xiàn)在用的目標(biāo)機(jī)是一個(gè)16位的，不會(huì)超過(guò)普通的unsigned的32位。但是，今后我們可能需要對(duì)64位機(jī)建模，所以定義了ST以方便今后的修改。針對(duì)4種對(duì)象類，我們定義了3種Token類,并定義了抽象的基類Token。表5.2模擬器Token類定義表類名說(shuō)明Token基類成員變量：unsignedm_uMark;〃一個(gè)標(biāo)記，起輔助作用成員函數(shù)：virtualToken*Duplicate();//復(fù)制這個(gè)TokenvirtualvoidSetValue(unsignedindex,STvalue);〃給Token的第index個(gè)屬性賦值virtualboolGetValue(unsignedindex,ST&value)const;〃取Token的第index個(gè)屬性賦值virtualboolEqual(constToken*pt)const;〃判斷兩個(gè)Token是否值相等voidSetMark(unsignedmark);〃設(shè)置標(biāo)記unsignedGetMark()const;//取標(biāo)記virtualvoidShow(ostream&out);//輸出，顯示或調(diào)試用

類名說(shuō)明Simplelbken繼承Token對(duì)應(yīng)NumericTypeDef和EnumTypeDef成員變量：STm_Value;//單一屬性的值ObjectToken繼承Token對(duì)應(yīng)ObjectTypeDef成員變量：vector<ST>m_Values;//依次對(duì)應(yīng)每個(gè)屬性的值A(chǔ)rrayToken繼承Token對(duì)應(yīng)ArrayTypeDef成員變量:map<unsigned,ST>m_Values;〃保存用到的屬性的值所有的全局變量保存在??個(gè)全局?jǐn)?shù)組vector<Token*>g_tokens中，數(shù)組的下標(biāo)與變量的標(biāo)號(hào)相對(duì)應(yīng)?；☆惖脑O(shè)計(jì)弧類的設(shè)計(jì)比較簡(jiǎn)單，定義了一個(gè)Arc類。記錄了它的起點(diǎn)和終點(diǎn)是庫(kù)所、變遷或是懸空以及它連接的庫(kù)所和變遷的編號(hào)。懸空的弧在圖形化界面下編輯Petri網(wǎng)時(shí)可能發(fā)生。Arc類中還用字符串?dāng)?shù)據(jù)vector<string>保存了弧上的標(biāo)記。庫(kù)所類的設(shè)計(jì)定義了一個(gè)抽象的基類Place。包括庫(kù)所名稱、編號(hào)、類型名稱、初始時(shí)Token字符串、類型編號(hào)。在解析時(shí)，根據(jù)類型名稱得到類型編號(hào)，根據(jù)初始時(shí)Token字符串生成初始Token加入到該庫(kù)所中。在該抽象基類的基礎(chǔ)上可以根據(jù)需要定義不同的庫(kù)所類。比如，本文中的模型要求盡可能多的變遷同步觸發(fā)。在變遷觸發(fā)后不馬上把輸出的Token放到庫(kù)所中，而是等到?jīng)]有觸發(fā)可以發(fā)生時(shí)一起放回。在實(shí)現(xiàn)時(shí)，當(dāng)一個(gè)變遷向庫(kù)所輸出Token時(shí)，把Token放在一個(gè)等候加入的列表中。當(dāng)沒(méi)有變遷可以觸發(fā)時(shí)，通過(guò)調(diào)用庫(kù)所的RoundFinish函數(shù)，把等候加入的Token正式加入到這個(gè)庫(kù)所的可用Token中。變遷類的設(shè)計(jì)定義了一個(gè)抽象的基類Transition。變遷在模擬執(zhí)行中占據(jù)核心的地位。所以在其中保存變遷的名稱、所有輸入弧、所有輸出弧、各類綁定的發(fā)生條件（字符串）以及解析后的執(zhí)行代碼（包括搜索代碼、條件判斷代碼和觸發(fā)發(fā)生代碼）。關(guān)于執(zhí)行代碼將在下一節(jié)中介紹。在該抽象基類的基礎(chǔ)上可以根據(jù)需要定義不同的變遷類。執(zhí)行代碼設(shè)計(jì)執(zhí)行代碼根據(jù)不同的作用分成兩類：-類是搜索Token代碼；另一類是運(yùn)行及Token輸出代碼。搜索代碼SCode結(jié)構(gòu)有3個(gè)字段：m_type,m_place和m_param□

表5.3模擬器的搜索代碼類型m_type含義SC_Value從m_place庫(kù)所中搜出一個(gè)值等于m_param的Token（僅限簡(jiǎn)單類型）SC_New從m_place庫(kù)所中取出任意一個(gè)Token,將它復(fù)制給編號(hào)為m_param的全局變量SC_Same從m_place庫(kù)所中搜出一個(gè)值等于編號(hào)為m_param的全局變量的Token搜索代碼的執(zhí)行通過(guò)遞歸來(lái)實(shí)現(xiàn)。通過(guò)這樣的搜索代碼設(shè)計(jì)，模型在執(zhí)行它們的時(shí)候能夠及時(shí)地做-些判斷，避免了一些無(wú)謂的搜索。運(yùn)行及Token輸出代碼ECode結(jié)構(gòu)也有3個(gè)字段：m_type,m_param（在下表中簡(jiǎn)記為pl）和m_param2（在下表中簡(jiǎn)記為p2）。ECode代碼的運(yùn)行是利用一個(gè)堆棧執(zhí)