（管理科學(xué)與工程專業(yè)論文）半markov型排隊(duì)網(wǎng)絡(luò)的優(yōu)化及其并行仿真算法研究與應(yīng)用.pdf

摘要 本文的工作重點(diǎn)是研究半m a r k o v 控制過(guò)程中的并行優(yōu)化算法。首先給出一種半 m a r k o v 控制過(guò)程性能勢(shì)的估計(jì)算法，相對(duì)于基于實(shí)現(xiàn)矩陣的估計(jì)方法具有速度快，對(duì)計(jì)算 機(jī)硬件要求不高等特點(diǎn)。其后研究了半m a r k o v 控制過(guò)程基于單樣本軌道的仿真優(yōu)化算法， 并從實(shí)際應(yīng)用的角度出發(fā)發(fā)展了相應(yīng)的并行算法，并提供了計(jì)算實(shí)例并分析比較其結(jié)果。 最后，我們給出了通訊中兩個(gè)實(shí)際網(wǎng)絡(luò)的優(yōu)化與導(dǎo)數(shù)估計(jì)的應(yīng)用實(shí)例一是半m a r k o v 決 策過(guò)程方法在航空軍械綜合系統(tǒng)維護(hù)問(wèn)題中的應(yīng)用；二是m p h 1 排隊(duì)系統(tǒng)的性能靈敏度估 計(jì)與仿真及其在a t m 交換機(jī)性能分析中的應(yīng)用。 本文的創(chuàng)新之處在于： ( 1 ) ：根據(jù)m a r k o v 性能勢(shì)理論，將它推廣到半m a r k o v 模型，得出了半m a r k o v 模型 的性能優(yōu)化公式，并給出了相應(yīng)的優(yōu)化算法。 ( 2 ) ：利用并行估計(jì)，給出了一套并行算法，大大提高了處理速度。 、，上 天 建- 7 ：半m a r k o v 過(guò)程，性能勢(shì)，實(shí)現(xiàn)矩陣，優(yōu)化算法，并行仿真 a b s t r a c t p a r a l l e ls i m u l a t i o na l g o r i t h mo fs e m i m a r k o vc o n t r o lp r o c e s s e si ss t u d i e di nt h i st h e s i s a s i m u l a t i o na l g o r i t h mo ft h ep e r f o r m a n c ep o t e n t i a l si sp r e s e n t e d ，w i t ht h ea d v a n t a g eo ff a s t e r s p e e d ，l o w e rd e m a n d so fc o m p u t e rh a r d w a r et h a nt h ea l g o r i t h mb a s e do nr e a l i z a t i o nm a t r i x t h e nw ep r o v i d eas i m u l a t i o no p t i m i z a t i o na l g o r i t h mo fs e m i m a r k o vc o n t r o lp r o c e s s e sb a s e d o ns i n g l es a m p l ep a t h ，a n dac o r r e s p o n d i n gp a r a ll e l a l g o r i t h mw a sd e v e l o p e d s o m en u m e r i c a l e x a m p l e sa r eg i v e nt oi l l u s t r a t et h ea p p l i c a t i o no ft h ea l g o r i t h m s f i n a l l y , t w or e a le x a m p l e si nc o m m u n i c a t i o nw e r eg i v e n o n ee x a m p l ei st h a ts e m i m a r k o v d e c i s i o np r o c e s sm e t h o di nt h em a i n t e n a n c eo ft h ea v i a t i o no r d n a n c es y n t h e t i cs y s t e m t h eo t h e r i s s e n s i t i v i t ye s t i m a t e & s i m u l a t i o n so fp e r f o r m a n c ei nm p h 1 q u e u e i n gs y s t e m sa n dt h e a p p l i c a t i o n si na t m s w i t h t h ei n n o v a t i o no ft h i sp a p e ri s ： ( 1 ) ：a c d o r d i n gt ot h em a r k o vp e r f o r m a n c ep o t e n t i a l st h e o r y , e x t e n di tt ot h es e m i m a r k o v m o d l e ，g e tt h ep e r f o r m a n c eo p t i m i z a t i o ne q u m i o n ，a n dt h eo p t i m i z a t i o na l g o r i t h m si sg i v e n ( 2 ) ：b a s e do nt h ep a r a l l e ls i m u l m i o n ，ap a r a l l e la l g o r i t h m si s g i v e n ，a n dt h es p e e di sm u c h h i g h e r 一， - k e y w o r d s ：s e m i m a r k o vc o n t r o lp r o c e s s e s ，p e r f o r m a n c ep o t e n t i a l ，r e a l i z a t i o nm a t r i x o p t i m i z m i o na l g o r i t h m ，p a r a l l e ls i m u l m i o n 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 第一章緒論 在這一章中簡(jiǎn)單介紹了離散事件動(dòng)態(tài)系統(tǒng)，其后說(shuō)明了本文的工作所涉及到的相關(guān)概 念：半m a r k o v 控制過(guò)程和性能勢(shì)、仿真及并行計(jì)算，并簡(jiǎn)單介紹了本文的結(jié)構(gòu)，作為后續(xù) 文章的基礎(chǔ)。 1 1 離散事件動(dòng)態(tài)系統(tǒng) 離散事件動(dòng)態(tài)系統(tǒng)是系統(tǒng)和控制領(lǐng)域的一門新的分支，它在許多實(shí)際應(yīng)用中有著廣泛 的應(yīng)用前景，因此自提出以來(lái)得到飛速的發(fā)展。 1 1 1 基本概念 隨著信息通訊、計(jì)算機(jī)和機(jī)器人等高新技術(shù)的發(fā)展和應(yīng)用，在通信網(wǎng)絡(luò)、柔性制造、 交通管理、軍事指揮等領(lǐng)域相繼出現(xiàn)了大量反映現(xiàn)代科學(xué)技術(shù)發(fā)展方向的人造系統(tǒng)，這類 系統(tǒng)通常能被描述為離散事件動(dòng)態(tài)系統(tǒng)( d e d s ) 。經(jīng)過(guò)近幾十年的快速發(fā)展，離散事件動(dòng)態(tài) 系統(tǒng)己經(jīng)成為控制和系統(tǒng)領(lǐng)域的一個(gè)前沿方向，并在當(dāng)今一大批高科技領(lǐng)域獲得了廣泛應(yīng) 用，是系統(tǒng)和控制領(lǐng)域的一門新的分支，它是由哈佛大學(xué)何毓琦( yc h o ) 教授等人于八十 年代前后創(chuàng)立的 1 】，名稱也是由何毓琦教授等人提出的，以區(qū)別于此前已得到廣泛研究的 連續(xù)變量動(dòng)態(tài)系統(tǒng)( c v d s ) 。在d e d s 中，對(duì)系統(tǒng)行為進(jìn)程起決定作用的是一批離散事件， 而不是連續(xù)變量，所遵循的是一些復(fù)雜的人為規(guī)則，而不是物理學(xué)定律或廣義物理學(xué)定律。 正是基于對(duì)這類人造系統(tǒng)行為和性能研究的需要，推動(dòng)著d e d s 理論的形成和發(fā)展【2 1 2 】 構(gòu)成d e d s 的基本要素是離散事件，d e d s 行為隨時(shí)間的演化過(guò)程就是離散事件復(fù)雜 交互影響的結(jié)果。粗略地說(shuō)，離散事件是指d e d s 中發(fā)生在離散時(shí)刻的事件，所謂事件則 是使d e d s 狀態(tài)發(fā)生變動(dòng)的一個(gè)行動(dòng)或事情。 和離散時(shí)間連續(xù)變量動(dòng)態(tài)系統(tǒng)不同，d e d s 中離散事件的發(fā)生時(shí)刻通常是異步的。離 散事件的發(fā)生時(shí)刻，取決于這一時(shí)刻前系統(tǒng)行為的演化過(guò)程。柔性生產(chǎn)線中的“工件到達(dá) 機(jī)床”和“工件加工完成”，通信網(wǎng)絡(luò)中的“信號(hào)到達(dá)網(wǎng)絡(luò)”和“信息傳遞結(jié)束”，就是離 散事件的一些典型例子。在d e d s 中，一個(gè)離散事件的發(fā)生，在驅(qū)動(dòng)系統(tǒng)狀態(tài)產(chǎn)生躍變的 同時(shí)，還會(huì)按照系統(tǒng)的運(yùn)行規(guī)則在系統(tǒng)其他部分觸發(fā)新的離散事件，從而形成在離散事件 驅(qū)動(dòng)下系統(tǒng)狀態(tài)的演化過(guò)程。柔性生產(chǎn)線中工件沿著加工機(jī)床的持續(xù)加工過(guò)程，通信網(wǎng)絡(luò) 中信息沿傳輸設(shè)施的持續(xù)傳遞和變換過(guò)程，就是離散事件復(fù)雜交互影響下所形成的d e d s 行為演化過(guò)程的一些例子。 從上面可以看出，d e d s 中的離散事件具有三個(gè)基本特征：其一，離散事件是導(dǎo)致d e d s 狀態(tài)發(fā)生躍變和觸發(fā)新離散事件的唯一因素，也即離散事件是驅(qū)動(dòng)系統(tǒng)狀態(tài)演化的基本因 素。其二，離散事件的發(fā)生時(shí)刻是異步的和非約定的，即發(fā)生時(shí)刻由且只由系統(tǒng)的演化過(guò) 程所決定。其三，離散事件是研究d e d s 的主體，對(duì)d e d s 的分析歸結(jié)為確定離散事件交 互影響所導(dǎo)致的系統(tǒng)狀態(tài)的演化過(guò)程，對(duì)d e d s 的控制歸結(jié)為禁止不期望事件的發(fā)生或使 事件按期望的時(shí)序發(fā)生。 在實(shí)際系統(tǒng)中有許多可以用d e d s 來(lái)描述。例如一間只有一個(gè)理發(fā)師的理發(fā)店，在正 常工作的時(shí)間內(nèi)，如果沒(méi)有顧客到達(dá)理發(fā)店，則理發(fā)師空閑：如果有顧客到達(dá)理發(fā)店，則理 4 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 發(fā)師為顧客進(jìn)行理發(fā)服務(wù)。如果顧客到達(dá)理發(fā)店時(shí)，理發(fā)師正在為其他顧客服務(wù)，則新來(lái) 的顧客在一旁排隊(duì)等待。顯然，每個(gè)顧客到達(dá)理發(fā)店的時(shí)間是隨機(jī)的，而理發(fā)師為每個(gè)顧 客進(jìn)行理發(fā)服務(wù)的時(shí)間也是隨機(jī)的，從而每個(gè)隊(duì)列中的顧客等待的時(shí)間也是隨機(jī)的，這是 一個(gè)典型的離散事件系統(tǒng)的例子。 在現(xiàn)代高技術(shù)領(lǐng)域中出現(xiàn)的大量人造系統(tǒng)大多數(shù)也可以用d e d s 來(lái)描述。例如通訊 網(wǎng)絡(luò)中的呼叫接入系統(tǒng)，其中一個(gè)用戶呼叫的到來(lái)和結(jié)束就是兩個(gè)離散的事件，而某一時(shí) 刻所有不同的服務(wù)節(jié)點(diǎn)中接入的不同形式的用戶數(shù)目就構(gòu)成了一個(gè)狀態(tài)。如果考慮緩沖器， 則還需要計(jì)入不同緩沖器中的不同的用戶數(shù)目。 如圖1 1 所示的柔性生產(chǎn)線或稱柔性制造系統(tǒng)，簡(jiǎn)稱為f m s ( f l e x i b l e m a n u f a c t u r i n g s y s t e m s ) ，也是最具典型性和重要性的一個(gè)例子。在計(jì)算機(jī)控制單元的控制下，不同的待加 工工件通過(guò)自動(dòng)物料傳送系統(tǒng)輸送到相應(yīng)加工中心的緩沖區(qū)，由加工中心對(duì)工件進(jìn)行多類 型的加工，從刀具的控制到加工工藝的確定都由計(jì)算機(jī)控制程序決定和控制，且程序的調(diào) 用和更改非常方便靈活，因此具有很好的柔性。加工完畢的工件通過(guò)自動(dòng)物料傳送系統(tǒng)輸 送到自動(dòng)倉(cāng)庫(kù)。 圖1 1 柔性制造系統(tǒng)示意圖 這樣的柔性制造系統(tǒng)是一個(gè)典型的離散事件動(dòng)態(tài)系統(tǒng)。在f m s 中，各個(gè)加工中心對(duì) 各類工件的加工活動(dòng)構(gòu)成為系統(tǒng)的狀態(tài)，由工件和加工中心組成系統(tǒng)的資源，資源的投入 或釋放構(gòu)成為系統(tǒng)的離散事件。表征系統(tǒng)加工活動(dòng)的狀態(tài)的躍變，由待加工工件的到達(dá)( 投 入) 和機(jī)床的完成加工( 釋放) 等事件所驅(qū)動(dòng)。顯然，狀態(tài)演化過(guò)程中，狀態(tài)躍變時(shí)刻將呈現(xiàn) 出異步性，而系統(tǒng)演化則由離散事件錯(cuò)綜復(fù)雜的相互作用所決定。當(dāng)f m s 的基本參數(shù)( 如 加工中心對(duì)各種工件的作業(yè)時(shí)間、自動(dòng)物料傳送系統(tǒng)的運(yùn)行速度、工件的加工特性等) 為固 定不變時(shí)，f m s 中出現(xiàn)的事件可認(rèn)為是確定性的，整個(gè)f m s 可表征為一個(gè)確定性d e d s 。 如果f m s 的基本參數(shù)( p n 機(jī)床作業(yè)時(shí)間、自動(dòng)物料傳送系統(tǒng)的運(yùn)行速度等) 受內(nèi)部和外部因 素影響而具有不確定性時(shí)，f m s 中的事件在本質(zhì)上是隨機(jī)性的，f m s 相應(yīng)地需要采用隨機(jī) d e d s 來(lái)描述。 基于f m s 的d e d s 模型，可用來(lái)確定對(duì)待加工工件的排序，分析加工過(guò)程的加工節(jié) 奏，避免f m s 出現(xiàn)阻塞現(xiàn)象，優(yōu)化配置各個(gè)緩沖區(qū)的容量，以及優(yōu)化系統(tǒng)的生產(chǎn)率等。 5 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 1 1 2d e d s 的研究方法 d e d s 的研究，根據(jù)所用模型和采用工具的不同，基本上可以分為三個(gè)不同的方向， 即邏輯層次，時(shí)間層次，及隨機(jī)統(tǒng)計(jì)層次。采用不同的方式來(lái)描述d e d s 中的事件和狀態(tài) 這兩個(gè)基本要素，并通過(guò)它們運(yùn)用不同的手段來(lái)研究同一個(gè)過(guò)程，從而決定了這三種模型 及其研究方法。在對(duì)d e d s 的研究中各有其側(cè)重點(diǎn)，因而它們也各有其優(yōu)缺點(diǎn)。 在邏輯層次模型下，采用的系統(tǒng)模型主要有形式語(yǔ)言，有限自動(dòng)機(jī)，m a r k o v 鏈，p e t r i 網(wǎng)j 1 3 一i 8 1 等。在該層次模型下，一般用一些離散的符號(hào)來(lái)表征系統(tǒng)的狀態(tài)，并且不要求狀 態(tài)空間( 事件的集合) 有任何的拓?fù)浣Y(jié)構(gòu)。運(yùn)用人們規(guī)定的某種機(jī)制來(lái)驅(qū)動(dòng)事件的產(chǎn)生和滅 亡，從而導(dǎo)致系統(tǒng)狀態(tài)的轉(zhuǎn)移。因此，從邏輯層次研究d e d s ，就是研究事件和狀態(tài)按照 邏輯時(shí)間序列運(yùn)行，而不涉及系統(tǒng)的真實(shí)物理時(shí)間。故其采用的研究手段，大多是一些邏 輯性較強(qiáng)的工具，例如有限自動(dòng)機(jī)，p e t r i 網(wǎng)等，在邏輯層次下，對(duì)系統(tǒng)的控制及控制作用 下的系統(tǒng)行為有較深刻的研究，但由于其未考慮系統(tǒng)的物理時(shí)間，故難以用于連續(xù)時(shí)間 d e d s 的動(dòng)態(tài)分析。 在時(shí)問(wèn)層次模型下，采用的主要建模方法包括，極大極小代數(shù)，有限遞歸過(guò)程等，而 基于極大極小代數(shù)或更一般的雙子代數(shù)的研究，由于其特殊的運(yùn)算規(guī)則，導(dǎo)致系統(tǒng)的動(dòng)態(tài) 方程非常類似于通常連續(xù)變量線性系統(tǒng)。在這一層次下，不僅考慮事件和狀態(tài)的邏輯順序 關(guān)系，而且也涉及系統(tǒng)真實(shí)的物理時(shí)間，從而可以用于系統(tǒng)的動(dòng)態(tài)分析。特別是，基于線 性化的動(dòng)態(tài)方程，可以定量的研究系統(tǒng)的穩(wěn)定性及結(jié)構(gòu)特征等系統(tǒng)行為。但其主要缺陷是 適用的范圍較窄 1 9 】，并且通常連續(xù)變量線性系統(tǒng)中一系列行之有效的分析，控制和優(yōu)化 技術(shù)難以應(yīng)用到這樣的線性系統(tǒng)模型中。 在隨機(jī)統(tǒng)計(jì)層次模型下，采用的系統(tǒng)模型主要是排隊(duì)網(wǎng)絡(luò)和隨機(jī)過(guò)程。一般來(lái)說(shuō)， d e d s 中某個(gè)參變量的微小變化，都會(huì)導(dǎo)致系統(tǒng)以十分不同的方式運(yùn)行，因此需要考慮系 統(tǒng)中許多參變量的隨機(jī)變化，從而在性能分析中需要采用統(tǒng)計(jì)平均的方法。從統(tǒng)計(jì)性能層 次研究d e d s ，也是d e d s 研究的最初形式，何毓琦( yc h o ) 教授等人提出d e d s 這個(gè)概 念時(shí)就是從該層次出發(fā)的。在這一層次下，采用的系統(tǒng)模型主要為m a r k o v 過(guò)程、半m a r k o v 過(guò)程、廣義半m a r k o v 過(guò)程和各種類型的排隊(duì)網(wǎng)絡(luò)等，其中有代表性的研究方法是攝動(dòng)分 析( p a ) ，無(wú)窮小攝動(dòng)分析( i p a ) ，m a r k o v 決策( 控制) 過(guò)程等。 總體而言，現(xiàn)在對(duì)離散事件動(dòng)態(tài)系統(tǒng)建模的研究，還遠(yuǎn)不是成熟的和完善的。不管是 從形式的統(tǒng)一性，還是從數(shù)學(xué)表達(dá)的簡(jiǎn)明性和計(jì)算分析的可行性，都遠(yuǎn)不如連續(xù)變量動(dòng)態(tài) 系統(tǒng)的建模那樣完美。更廣義地說(shuō)，由于d e d s 屬于人造系統(tǒng)的范疇，系統(tǒng)機(jī)制中可能會(huì) 同時(shí)并存多種交互作用，如事件之間的交互作用、人與系統(tǒng)的交互作用、系統(tǒng)與環(huán)境的交 互作用等，系統(tǒng)各種關(guān)系中也可能會(huì)同時(shí)含有多種表達(dá)形式，如定t 、定性和知識(shí)的形式 等。因此，一個(gè)復(fù)雜的離散事件動(dòng)態(tài)系統(tǒng)助建模，最終可能需要同時(shí)借助于運(yùn)籌學(xué)、系統(tǒng) 與控制理論、人工智能與自然語(yǔ)言理解等多學(xué)科的方法的結(jié)合。一般認(rèn)為，如圖1 2 所示 那樣，d e d s 的模型定位于這三個(gè)學(xué)科之間的交叉部分。 1 2 半m a r k o v 控制過(guò)程和性能勢(shì) m a r k o v 控制過(guò)程，又稱為m a r k o v 決策過(guò)程、m a r k o v 決策規(guī)劃、m a r k o v 動(dòng)態(tài)規(guī)劃和 受控m a r k o v 過(guò)程等，是研究類隨機(jī)序貫決策問(wèn)題的理淪，即在系列相繼的或連續(xù)的時(shí)刻( 稱 6 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 之為決策時(shí)刻) 點(diǎn)做出決策，在各個(gè)決策時(shí)刻點(diǎn)，決策者根據(jù)觀察到的狀態(tài)從可用的若干個(gè) 決策中選擇一個(gè)；將決策付諸實(shí)施后，系統(tǒng)將獲得與所處狀態(tài)和所采取決策有關(guān)的一項(xiàng)報(bào)酬 ( 或費(fèi)用等) 并影響系統(tǒng)在下一決策時(shí)刻點(diǎn)所處的狀態(tài)。系統(tǒng)在下一決策時(shí)刻點(diǎn)處的狀態(tài)是 隨機(jī)的。在這一新的決策時(shí)刻點(diǎn)上，決策者要觀察系統(tǒng)所處的新的狀態(tài)( 即收集新的信息) 并采取新的決策，如此一步一步進(jìn)行卜去。在每一決策時(shí)刻采取的決策不僅影響當(dāng)前決策 周期的運(yùn)行和性能( 狀態(tài)的逗留時(shí)間，獲得的報(bào)酬或代價(jià)等) ，而且會(huì)直接或問(wèn)接影響下決策 時(shí)刻系統(tǒng)的運(yùn)行和性能，并以此影響將來(lái)。決策的目的是選擇一種控制決策方案，使系統(tǒng) 的運(yùn)行在某種意義下( 稱為性能準(zhǔn)則) 達(dá)到最優(yōu)，例如在期望平均報(bào)酬( 或期望平均代價(jià)) 準(zhǔn)則 下，使系統(tǒng)的期望平均總報(bào)酬( 或期望平均代價(jià)) 最大( 或最小) 。這樣，在每一個(gè)決策時(shí)刻所 選擇的控制決策，不但要使當(dāng)前決策周期獲得的報(bào)酬( 代價(jià)) 盡可能大( 小) ，而且要使系統(tǒng) 在將來(lái)的后續(xù)周期所獲得的報(bào)酬( 代價(jià)) 盡可能大( 小) 。這需要決策者從全局的觀點(diǎn)做出權(quán) 衡，因而這也是m c p 優(yōu)化控制問(wèn)題的難點(diǎn)所在m c p 實(shí)際上是隨機(jī)型離散事件動(dòng)態(tài)系統(tǒng)的 唯一的動(dòng)態(tài)控制方法，與離散事件動(dòng)態(tài)系統(tǒng)的邏輯控制方法也有著密切的關(guān)系。其基本模 型有離散時(shí)間m a r k o v 控制過(guò)程( d t m c p ) 和連續(xù)時(shí)間m a r k o v 控制過(guò)程( c t m c p ) 。從性能 上來(lái)說(shuō)，m c p 又可分為折扣準(zhǔn)則m c p 和平均代價(jià)m c p 等。 圖1 2d e d s 與其它學(xué)科的關(guān)系 m c p 的優(yōu)化方法通常有數(shù)值計(jì)算求解、直接搜索法、線性規(guī)劃方法( l p ) ，梯度方法、以 及策略迭代( p i ) 和數(shù)值迭代( v i ) 方法等。目前后三種方法是主要的優(yōu)化手段。對(duì)于m c p 的 優(yōu)化目前國(guó)際上已經(jīng)有諸多理論和應(yīng)用成果問(wèn)世 3 1 3 5 】，國(guó)內(nèi)在其優(yōu)化理論和應(yīng)用方面的 研究，也有了諸多成果 3 6 4 0 1 。對(duì)有限行動(dòng)集或可數(shù)行動(dòng)集、緊致行動(dòng)集，折扣準(zhǔn)則下以 及平均性能準(zhǔn)則下的優(yōu)化問(wèn)題都有了很多研究成果。本文在m c p 基于性能勢(shì)的最優(yōu)性原 理和最優(yōu)性方程的基礎(chǔ)上考慮一些優(yōu)化算法，如策略迭代算法以及數(shù)值迭代算法。 在實(shí)際的優(yōu)化問(wèn)題中，系統(tǒng)模型可以是已知的，也可以是未知或者不完全知道的。在 系統(tǒng)模型已知時(shí)，可以根據(jù)模型參數(shù)直接進(jìn)行優(yōu)化計(jì)算。然而在狀態(tài)空間很大的優(yōu)化計(jì)算 問(wèn)題中，存在兩個(gè)問(wèn)題。一是直接的優(yōu)化計(jì)算量常常相當(dāng)大，尤其是矩陣求逆運(yùn)算等，需 要耗費(fèi)大量的運(yùn)算時(shí)間；二是在一定的策略下一部分狀態(tài)出現(xiàn)的概率很小或者幾乎不出現(xiàn)， 7 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 對(duì)優(yōu)化問(wèn)題的貢獻(xiàn)很小，從而耗費(fèi)了不必要的計(jì)算時(shí)間。為了降低優(yōu)化問(wèn)題的成本，我們 可以考慮基于仿真的算法，通過(guò)仿真隨機(jī)產(chǎn)生出具有代表性的狀態(tài)，然后對(duì)這些狀態(tài)進(jìn)行 計(jì)算，這樣避免了每次都要對(duì)那些很少出現(xiàn)的狀態(tài)進(jìn)行計(jì)算，因而節(jié)省了計(jì)算時(shí)間。另外 由于性能勢(shì)的一個(gè)特點(diǎn)就是可以在一條單樣本軌道上得到其無(wú)偏估計(jì)值，并用于進(jìn)一步的 優(yōu)化，因此在基于性能勢(shì)的優(yōu)化問(wèn)題中也要考慮基于仿真的優(yōu)化方法。 在系統(tǒng)模型未知或者不完全知道時(shí)，也必須求助于仿真的方法。首先需要對(duì)系統(tǒng)的模 型參數(shù)進(jìn)行估計(jì)和改進(jìn)以期得到和符合實(shí)際系統(tǒng)的優(yōu)化結(jié)果，而在基性能勢(shì)的優(yōu)化算法中， 不僅要對(duì)系統(tǒng)的模型參數(shù)進(jìn)行估計(jì)，還要對(duì)性能勢(shì)進(jìn)行估計(jì)。 二十世紀(jì)九十年代，曹希仁( x r c a o ) 教授和陳翰馥教授提出了一個(gè)新的理論：m a r k o v 性能勢(shì)理論 2 7 1 ，并揭示了m a r k o v 性能勢(shì)、無(wú)窮小攝動(dòng)分析( i p a ) 與m a r k o v 決策過(guò)程三者 之間的聯(lián)系【4 l l 】。這一成果被廣泛應(yīng)用到一般m a r k o v 系統(tǒng)和排隊(duì)網(wǎng)絡(luò)的靈敏度分析中， 并取得了顯著成果 2 7 2 8 4 1 4 8 ；另一方面，曹希仁( x r c a o ) 運(yùn)用m a r k o v 性能勢(shì)理論，給 出了m c p 在有限行動(dòng)集下基于性能勢(shì)的優(yōu)化理論和算法 4 l ，4 2 】。在此基礎(chǔ)上，我們進(jìn)一 步建立了m a r k o v 控制過(guò)程和受控排隊(duì)網(wǎng)絡(luò)在緊致行動(dòng)集上基于性能勢(shì)的優(yōu)化理論和算法 4 9 5 3 】 事實(shí)上，性能勢(shì)理論為m c p 的優(yōu)化提供了一個(gè)統(tǒng)一的基本的理論框架。運(yùn)用性能勢(shì) 理論，從p o i s s o n 方程著手，在較少的假設(shè)條件下，很容易建立起m c p 基于性能勢(shì)的最優(yōu) 性原理和最優(yōu)性方程，并且容易證明其最優(yōu)解的存在性定理。在此基礎(chǔ)上可給出一些收斂 的優(yōu)化算法，如基于計(jì)算的梯度類算法和策略迭代以及數(shù)值迭代算法 4 0 ，4 9 5 4 l 。但是這 種基于理論計(jì)算的優(yōu)化方法，依賴于系統(tǒng)的精確模型，往往需要系統(tǒng)的轉(zhuǎn)移矩陣或無(wú)窮小 矩陣的完全信息及有關(guān)矩陣的求逆運(yùn)算( 如由p o i s s o n 方程求解性能勢(shì)) 。對(duì)于一個(gè)實(shí)際系 統(tǒng)，其模型可能未知或不全知，那種需要轉(zhuǎn)移矩陣或無(wú)窮小矩陣的理論算法己經(jīng)不再適用； 另一方面，對(duì)那些存在“維數(shù)災(zāi)難”問(wèn)題的大規(guī)模實(shí)際系統(tǒng)，即使模型己知，由于其狀態(tài) 空間很大，在進(jìn)行優(yōu)化計(jì)算時(shí)，有關(guān)矩陣求逆運(yùn)算也需要大量計(jì)算機(jī)內(nèi)存，占用相當(dāng)長(zhǎng)的 計(jì)算時(shí)間，往往導(dǎo)致計(jì)算機(jī)負(fù)擔(dān)過(guò)重而不可行。而性能勢(shì)的一個(gè)重要特點(diǎn)是可以通過(guò)仿真 或觀測(cè)一個(gè)實(shí)際系統(tǒng)的運(yùn)行，得到單個(gè)樣本軌道來(lái)進(jìn)行無(wú)偏估計(jì) 2 8 】，在此基礎(chǔ)上可以發(fā) 展基于單條樣本軌道的仿真優(yōu)化算法和有關(guān)在線優(yōu)化算法。這種算法將適用于大規(guī)模實(shí)際 系統(tǒng)在模型已知或未知情況下的優(yōu)化求解。 從實(shí)際應(yīng)用的角度出發(fā)，需要對(duì)基于單樣本軌道的優(yōu)化算法效率做進(jìn)一步的優(yōu)化。考 察性能勢(shì)的仿真算法，可以發(fā)現(xiàn)其具有很好的并行性，而且基于性能勢(shì)的策略迭代算法和 數(shù)值迭代算法都易于進(jìn)行并行處理。這樣在理論計(jì)算優(yōu)化方法和仿真優(yōu)化方法的基礎(chǔ)上可 以進(jìn)一步發(fā)展一種新的高效并行理論算法和并行仿真算法 5 5 5 7 】，因而能大大節(jié)省計(jì)算時(shí) 間，從而為大規(guī)模實(shí)際系統(tǒng)的優(yōu)化提供一條途徑這也是本文的主要內(nèi)容之一。 性能勢(shì)的這些性質(zhì)為實(shí)際m a r k o v 系統(tǒng)的性能分析和優(yōu)化提供了一個(gè)強(qiáng)有力的工具， 它在實(shí)際系統(tǒng)中的應(yīng)用突出體現(xiàn)在排隊(duì)網(wǎng)絡(luò)中。實(shí)際系統(tǒng)中的許多排隊(duì)網(wǎng)絡(luò)都可以用 m a r k o v 控制過(guò)程來(lái)描述，我們稱這樣的排隊(duì)網(wǎng)絡(luò)為m a r k o v 型排隊(duì)網(wǎng)絡(luò)。本文也把有關(guān)排 隊(duì)網(wǎng)絡(luò)的研究作為重要內(nèi)容。 目前，離散事件動(dòng)態(tài)系統(tǒng)在隨機(jī)統(tǒng)計(jì)層次下是主要以m a r k o v 過(guò)程為研究模型的，該 類模型的性能靈敏度分析以及性能優(yōu)化問(wèn)題已經(jīng)有了很多成果。但是由于半m a r k o v 過(guò)程 的逗留時(shí)間服從一般分布，因而半m a r k o v 過(guò)程是比m a r k o v 過(guò)程更為廣泛的一類系統(tǒng)，更 接近實(shí)際系統(tǒng)。所以半m a r k o v 控制過(guò)程的相關(guān)問(wèn)題逐漸成為近年來(lái)d e d s 領(lǐng)域的一個(gè)研 究熱點(diǎn)問(wèn)題。半m a r k o v 控制過(guò)程( s m c p ) 是一類受到一系列控制決策驅(qū)動(dòng)的半m a r k o v 系 統(tǒng)，其狀態(tài)轉(zhuǎn)移規(guī)律和控制決策所采用的行動(dòng)方案相互作用決定了系統(tǒng)的演化，過(guò)程在每 個(gè)狀態(tài)的逗留時(shí)間服從一般分布。并且該分布不僅與當(dāng)前狀態(tài)有關(guān)，而且與將要轉(zhuǎn)移到的 8 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 下一個(gè)狀態(tài)有關(guān)。很明顯，如果該分布是指數(shù)分布，則就是m a r k o v 控制過(guò)程，那么，我 們可以看出，半m a r k o v 控制過(guò)程是一類比m a r k o v 控制過(guò)程更廣泛的一類系統(tǒng)。 本文將重點(diǎn)研究半m a r k o v 控制過(guò)程的相關(guān)理論，并給出一些實(shí)際例子 1 3 仿真及并行計(jì)算 計(jì)算機(jī)仿真方法己經(jīng)成為分析復(fù)雜系統(tǒng)的重要手段，這一方法能夠?yàn)楦鞣N類型的實(shí)際 問(wèn)題提供數(shù)值解。利用仿真手段可以代替某些費(fèi)用昂貴的試驗(yàn)，并且能夠更快地積累數(shù)據(jù)， 以便選擇合適的假設(shè)及檢驗(yàn)預(yù)測(cè)的結(jié)論，并檢驗(yàn)有關(guān)理論中假設(shè)的合理性。在實(shí)際仿真中 運(yùn)算速度常常是考慮的重點(diǎn)之一，因此除了理論本身的改進(jìn)之外需要采取并行計(jì)算的方法 減少運(yùn)算時(shí)間滿足實(shí)際仿真的需求。 1 3 1 仿真 上面已經(jīng)說(shuō)明基于性能勢(shì)來(lái)解決m a r k o v 控制系統(tǒng)優(yōu)化問(wèn)題可以通過(guò)理論方法，計(jì)算 出性能勢(shì)的理論值進(jìn)行優(yōu)化，但這種方法涉及到矩陣求逆等運(yùn)算，對(duì)于大規(guī)模系統(tǒng)則力不 從心。而基于性能勢(shì)的優(yōu)化方法的一個(gè)重要優(yōu)點(diǎn)就是可以通過(guò)觀測(cè)或仿真系統(tǒng)的一條單樣 本軌道得到性能勢(shì)的無(wú)偏估計(jì)，因而適用于大規(guī)模實(shí)際系統(tǒng)。不同于傳統(tǒng)的基于直接計(jì)算 的優(yōu)化方法，在這種基于仿真的優(yōu)化方法中，穩(wěn)態(tài)概率和性能勢(shì)都是根據(jù)系統(tǒng)的一條樣本 軌道信息來(lái)估計(jì)計(jì)算的 2 8 ，5 8 】。 所謂系統(tǒng)仿真是以系統(tǒng)理論、形式化理論、隨機(jī)過(guò)程與統(tǒng)計(jì)學(xué)理論和優(yōu)化理論為基礎(chǔ)， 以計(jì)算機(jī)和仿真系統(tǒng)軟件為工具，對(duì)現(xiàn)實(shí)系統(tǒng)或未來(lái)系統(tǒng)進(jìn)行動(dòng)態(tài)實(shí)驗(yàn)研究的理論和方法 5 9 - 6 l 】 從系統(tǒng)仿真的實(shí)施過(guò)程來(lái)看，系統(tǒng)仿真是通過(guò)對(duì)所研究系統(tǒng)的認(rèn)識(shí)和了解，抽取其中 的基本要素的關(guān)鍵參數(shù)，建立與現(xiàn)實(shí)系統(tǒng)相對(duì)應(yīng)的仿真模型，經(jīng)過(guò)模型的確認(rèn)和仿真程序 的驗(yàn)證，在仿真實(shí)驗(yàn)設(shè)計(jì)的基礎(chǔ)上，對(duì)該模型進(jìn)行仿真實(shí)驗(yàn)，以模仿系統(tǒng)的運(yùn)行過(guò)程，觀 察系統(tǒng)狀態(tài)變量隨時(shí)問(wèn)變化的動(dòng)態(tài)規(guī)律性，并通過(guò)數(shù)據(jù)采集和統(tǒng)計(jì)分析，得到被仿真系統(tǒng) 參數(shù)的統(tǒng)計(jì)特性，據(jù)此推斷和估計(jì)系統(tǒng)的真實(shí)參數(shù)和性能測(cè)度，為輔助決策提供依據(jù) 系統(tǒng)仿真的一般步驟如圖1 3 所示【6 l 】 1 3 2 并行計(jì)算及其在仿真中的應(yīng)用 由于并行計(jì)算在本文中有重要應(yīng)用，因此我們介紹有關(guān)概念并根據(jù)相關(guān)研究的特點(diǎn)選 擇合適的硬件和軟件。 9 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 1 3 2 1 并行計(jì)算的背景 簡(jiǎn)單的講，并行計(jì)算( p a r a l l e lc o m p u t i n g ) 就是在并行計(jì)算機(jī)上所做的計(jì)算 6 2 6 4 】，它和 常說(shuō)的高性能計(jì)算( h i g hp e r f o r m a n c ec o m p u t i n g ) 、超級(jí)計(jì)算( s u p e r c o m p u t i n g ) 是同義詞，因 為任何高性能計(jì)算和超級(jí)計(jì)算總是離不開使用并行技術(shù)。隨著計(jì)算機(jī)和計(jì)算方法的飛速發(fā) 展，幾乎所有的學(xué)科都走向定量化和精確化，從而產(chǎn)生了一系列諸如計(jì)算物理、計(jì)算化學(xué)、 計(jì)算生物學(xué)、計(jì)算地質(zhì)學(xué)、訓(xùn)算氣象學(xué)冪n i - t 4 算材料科學(xué)等的計(jì)算科學(xué)，在世界上逐漸形成 了一門計(jì)算性的學(xué)科分支，即計(jì)算科學(xué)與工程，簡(jiǎn)稱為c s e ( c o m p u t a t i o n a ls c i e n c e & e n g i n e e r i n g ) 。在許多情況下，或者是理論模型復(fù)雜甚至理論尚未建立，或者試驗(yàn)費(fèi)用昂 貴甚至試驗(yàn)無(wú)法進(jìn)行，此時(shí)計(jì)算就成為求解問(wèn)題的唯一或主要手段計(jì)算極大地增強(qiáng)了人們 從事科學(xué)研究的能力，大大地加速了把科技轉(zhuǎn)化為生產(chǎn)力地過(guò)程，深刻地改變著人類認(rèn)識(shí) 世界和改造世界的方法和途徑。計(jì)算科學(xué)的理論和方法，作為新的研究手段和新的設(shè)計(jì)與 制造技術(shù)的理論基礎(chǔ)，正在推動(dòng)著當(dāng)代科學(xué)與技術(shù)向縱深發(fā)展。 l o 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 圖1 3 系統(tǒng)仿真的步驟 科學(xué)和工程計(jì)算中的重大挑戰(zhàn)性課題，要求能提供lt f l o p s 計(jì)算能力、i t b 主存容量 和1t b s 的i o 帶寬，這就是所謂的3 t 性能目標(biāo)。而在h p c c 計(jì)劃提出的當(dāng)時(shí)，性能最 好的計(jì)算機(jī)與3 t 指標(biāo)相比，速度太慢，而存儲(chǔ)容量太小，帶寬太窄。面對(duì)這些要求，只 有采用并行計(jì)算的技術(shù)，才能夠在要求的時(shí)間內(nèi)解決相同的問(wèn)題，或在相同的時(shí)間內(nèi)解決 更多更復(fù)雜的問(wèn)題，以較低的投入完成串行計(jì)算的任務(wù)。另外對(duì)于今后越來(lái)越高的計(jì)算速 度要求，不能依賴物理設(shè)備的進(jìn)化，光速是不可逾越的速度極限，設(shè)備和材料也不可能做 得無(wú)限小，處理器本身的速度不能夠無(wú)限提高，只有通過(guò)并行才能夠不斷提高速度，滿足 越來(lái)越高的性能要求。 由于并行計(jì)算是本文工作的重點(diǎn)，因此下面詳細(xì)介紹一下有關(guān)的概念。 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 1 3 2 2 并行計(jì)算機(jī)的分類 為了利用計(jì)算機(jī)實(shí)現(xiàn)相關(guān)算法，使所用的高級(jí)語(yǔ)言能夠被有效的編譯并且能夠用硬件 來(lái)實(shí)現(xiàn)，必須有一種計(jì)算模型作為硬件和軟件之間的橋梁以充分設(shè)計(jì)分析算法。在串行計(jì) 算時(shí)，馮諾依曼機(jī)就是一個(gè)理想的串行計(jì)算模型，在此模型上硬件設(shè)計(jì)者可以設(shè)計(jì)多種 多樣的馮諾依曼機(jī)而無(wú)需慮及將要在其上執(zhí)行的軟件：而軟件工程師能夠編寫各種可在此 模型上有效執(zhí)行的程序而不需考慮所使用的硬件。但在并行計(jì)算時(shí)尚未有一個(gè)類似于馮， 諾依曼機(jī)地真正通用的并行計(jì)算模型因此對(duì)于不同的并行結(jié)算機(jī)硬件結(jié)構(gòu)，在其上的軟件 編制工作都有相當(dāng)大的不同。在我們的并行訓(xùn)。算工作中也必須根據(jù)所采用的并行計(jì)算機(jī)硬 件結(jié)構(gòu)特點(diǎn)，分析如何發(fā)展盡量通用和高效的算法，這也是本文工作的重點(diǎn)之一。 在考慮并行算法之前首先需要熟悉并行計(jì)算機(jī)的各種分類及其特點(diǎn) 6 2 ， 6 4 。根據(jù)一個(gè)并 行計(jì)算機(jī)能夠同時(shí)執(zhí)行的指令與處理的數(shù)據(jù)的多少，可以把并行計(jì)算機(jī)分為s i m i ) ( s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ，單指令多數(shù)據(jù)并行計(jì)算機(jī)) 和m i m d ( m u l t i p l e i n s t r u c t i o n m u l t i p l e d a t a ，多指令多數(shù)據(jù)并行計(jì)算機(jī)) 兩種 按同時(shí)執(zhí)行的程序和數(shù)據(jù)的不同，人們又提出了s p m d ( s i n g l e p r o g r a m m u l t i p l e d a t a ， 單程序多數(shù)據(jù)并行計(jì)算機(jī)) 和m p m d ( m u l t i p l e p r o g r a m m u l t i p l e d a t a ，多程序多數(shù)據(jù)并行計(jì) 算機(jī)) 的概念。這種劃分方式所依據(jù)的執(zhí)行單位不是指令而是程序，顯然其劃分粒度( 劃分 對(duì)象的大小程度) 要大得多。 根據(jù)并行計(jì)算機(jī)結(jié)構(gòu)模型的不同，一般可以分為六類：?jiǎn)沃噶疃鄶?shù)據(jù)流機(jī)s i m d ( s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ) 并行向量處理機(jī)p v p ( p a r a l l e lv e c t o r p r o c e s s o r ) 、對(duì)稱多 處理機(jī)s m p ( s y m m e t r i cm u l t i p r o c e s s o r ) 、大規(guī)模并行處理機(jī)m p p ( m a s s i v e l yp a r a l l e l p r o c e s s o r ) ，i 作站機(jī)群c o w ( c l u s t e ro fw o r k s t a t i o n ) 和分布式共享存儲(chǔ)d s m ( d i s t r i b u t e d s h a r e dm e m o r y ) 多處理機(jī)。 從物理劃分上，共享內(nèi)存和分布式內(nèi)存是兩種基本的并行計(jì)算機(jī)存儲(chǔ)方式。除此之外， 分布式共享內(nèi)存也成為一種越來(lái)越重要的并行汁算機(jī)存儲(chǔ)方式。具體可分為下面幾類：均勻 存儲(chǔ)訪問(wèn)u m a ( u n i f o r mm e m o r ya c c e s s ) ，非均勻存儲(chǔ)訪問(wèn)n u m a ( n o n u n i f o r mm e m o r y a c c e s s ) 、全高速緩存存儲(chǔ)訪問(wèn)c o m a ( c a c h e o n l ym e m o r ya c c e s s ) 、高速緩存一致性非均 勻存儲(chǔ)訪問(wèn)c c n u m a ( c o h e r e n t c a c h en o n u n i f c l l 1 1 1m e m o r ya c c e s s ) 和非遠(yuǎn)程存儲(chǔ)訪問(wèn) n o r m a ( n o r e m o t em e m o r ya c c e s s ) 對(duì)于共享內(nèi)存的并行計(jì)算機(jī)，各個(gè)處理單元通過(guò)對(duì)共享內(nèi)存的訪問(wèn)來(lái)交換信息，協(xié)調(diào) 各處理器對(duì)并行任務(wù)的處理。這種共享內(nèi)存的編程實(shí)現(xiàn)起來(lái)相對(duì)簡(jiǎn)單，但共享內(nèi)存往往成 為性能特別是擴(kuò)展性的重要瓶頸 對(duì)于分布式內(nèi)存的并行計(jì)算機(jī)，各個(gè)處理單元都擁有自己獨(dú)立的局部存儲(chǔ)器。由于不 存在公共可用的存儲(chǔ)單元，因此各個(gè)處理器之間通過(guò)消息傳遞來(lái)交換信息，以協(xié)調(diào)和控制 各個(gè)處理器的執(zhí)行。這也是本文采用的消息傳遞并行編程模型所面對(duì)的并行計(jì)算機(jī)的存儲(chǔ) 方式不難看出，通信對(duì)分布式內(nèi)存并行計(jì)算機(jī)的性能有重要的影響，復(fù)雜的消息傳遞語(yǔ)句 的編寫成為在這種并行計(jì)算機(jī)上進(jìn)行并行程序設(shè)計(jì)的難點(diǎn)所在，但是，對(duì)于這種類型的并 行計(jì)算機(jī)，出于它有很好的擴(kuò)展性和很高的性能，因此它的應(yīng)用非常廣泛。 本文的并行工作的硬件基礎(chǔ)是國(guó)家高性能中心( 合肥) 曙光2 0 0 0 并行計(jì)算機(jī) 6 5 6 6 曙光 2 0 0 0 基于分布式存儲(chǔ)機(jī)群系統(tǒng)和消息傳遞體系結(jié)構(gòu)，是通用的可擴(kuò)展超級(jí)服務(wù)器系統(tǒng)。系 統(tǒng)的節(jié)點(diǎn)數(shù)目可以從4 個(gè)擴(kuò)展到1 2 8 個(gè)，節(jié)點(diǎn)c p u 采用m o t o r o l a 公司的p o w e rp c 6 0 4 e 微 處理器，節(jié)點(diǎn)之間通過(guò)1 0 1 0 0 m b p s 高速以太網(wǎng)和1 0 0 m b s 的“蛀洞”( w o r m h o l e ) 路由芯片 組成的二維網(wǎng)絡(luò)互連。在3 2 個(gè)計(jì)算節(jié)點(diǎn)( 單c p u ) 缺省配置下，整機(jī)峰值速度達(dá)到 1 2 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 2 0 0 g f l o p s ( 耳p 每秒2 0 0 億次浮點(diǎn)運(yùn)算) ，內(nèi)存總?cè)萘窟_(dá)到8 g b ，磁盤總?cè)萘窟_(dá)到1 4 4 g b 曙光2 0 0 0 的節(jié)點(diǎn)運(yùn)行完整的i b ma i x 操作系統(tǒng)，可以運(yùn)行上千種a i x 應(yīng)用程序和數(shù)據(jù)庫(kù)、 網(wǎng)絡(luò)服務(wù)器等商用軟件，支持c ，f o r t r a n j a v a 等程序設(shè)計(jì)語(yǔ)言，支持e s s l ，b l a s ，s c a l a p a c k 等高效數(shù)學(xué)和工程庫(kù)。系統(tǒng)軟件提供b c l ( b a s i cc o m m u n i c a t i o n l i b r a r y ) 底層通訊機(jī)制、定 制的p v m 和m p i 并行程序設(shè)計(jì)環(huán)境、集成化并行程序設(shè)計(jì)環(huán)境、并行調(diào)試器、基于w e b 的友好界面、自動(dòng)并行化工具、c o s m o s 可擴(kuò)展文件系統(tǒng)、對(duì)高可用性的支持、作業(yè)管理、 資源管理、系統(tǒng)管理、a u t o p a r 自動(dòng)并行化工具、服務(wù)器聚集軟件，以及d s m ，h p f , p a r a v t 等其它工具。廣泛采用j m ，a 和面向?qū)ο蠓椒?，在設(shè)計(jì)上注重可用性要求。 1 3 2 3 并行算法模型及并行語(yǔ)言的選擇 一個(gè)物理問(wèn)題并行求解的最終目的是將該問(wèn)題映射到并行機(jī)上通過(guò)不同層次上的抽象 映射來(lái)實(shí)現(xiàn)的。如圖1 4 所示。 圖1 4 問(wèn)題的并行求解過(guò)程 忽略并行機(jī)的非本質(zhì)的細(xì)節(jié)特征，可以得到該并行機(jī)的并行計(jì)算模型。在這一模型上， 可以設(shè)計(jì)各種適合該模型的并行算法，這些算法精確描述了該并行模型能夠?qū)崿F(xiàn)的功能， 而這些算法是通過(guò)用特定的并行語(yǔ)言設(shè)計(jì)并行程序后得以實(shí)現(xiàn)。對(duì)于現(xiàn)實(shí)世界的物理問(wèn)題， 為了能夠高效地并行求解，必須建立它的并行求解模型，一個(gè)串行的求解模型是很難在并 行機(jī)上取得滿意的并行效果的。有了并行求解模型，就可以針對(duì)該模型設(shè)計(jì)高效的并行算 法，對(duì)該問(wèn)題的求解進(jìn)行精確描述和定量分析，對(duì)各種算法進(jìn)行性能上的比較，最后通過(guò) 并行程序設(shè)計(jì)，實(shí)現(xiàn)問(wèn)題和并行機(jī)的結(jié)合。 并行程序設(shè)計(jì)需要將問(wèn)題的并行求解算法轉(zhuǎn)化為特定的適合并行計(jì)算模型的并行算 法。為了達(dá)到這一目的，首先是問(wèn)題的并行求解算法必須能夠?qū)?wèn)題內(nèi)在的并行特征充分 體現(xiàn)出來(lái)，否則并行求解算法將無(wú)法利用這些并行特征，從而使問(wèn)題的高效并行求解成為 1 3 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 不可能：其次是并行求解模型要和并行計(jì)算模型盡量吻合，這樣，就為問(wèn)題在并行機(jī)上的高 效解決提供了前提。 目前兩種最重要的并行編程模型是數(shù)據(jù)并行和消息傳遞【6 4 】。數(shù)據(jù)并行編程模型的編 程級(jí)別比較高、編程相對(duì)簡(jiǎn)單，但它僅適用于數(shù)據(jù)并行問(wèn)題；消息傳遞編程模型的編程級(jí)別 相對(duì)較低，但消息傳遞編程模型可以有更廣泛的應(yīng)用范圍。數(shù)據(jù)并行即將相同的操作同時(shí) 作用于不同的數(shù)據(jù)，因此適合在s i m d 及s p m d 并行計(jì)算機(jī)上運(yùn)行。在向量機(jī)上通過(guò)數(shù)據(jù) 并行求解問(wèn)題的實(shí)踐也說(shuō)明，數(shù)據(jù)并行可以高效地解決一大類科學(xué)與工程計(jì)算問(wèn)題。 消息傳遞即各個(gè)并行執(zhí)行的部分之間通過(guò)傳遞消息來(lái)交換信息、協(xié)調(diào)步伐、控制執(zhí)行， 消息傳遞一般是面向分布式內(nèi)存的，但是它也可適用于共享內(nèi)存的并行饑c 消息傳遞為編 程者提供靈活的控制手段和表達(dá)并行的方法，一些用數(shù)據(jù)并行方法很難表達(dá)的并行算法， 都可以使用消息傳遞模型來(lái)實(shí)現(xiàn)。靈活性和控制手段的多樣化，是消息傳遞并行程序能提 供高的執(zhí)行效率的重要原因。 消息傳遞模型一方面為編程者提供了靈活性，另一方面，它也將各個(gè)并行執(zhí)行部分之 間復(fù)雜的信息變換和協(xié)調(diào)、控制的任務(wù)交給了編程者，在一定程度上增加了編程者的負(fù)擔(dān)， 這也是消息傳遞編程模型編程級(jí)別低的主要原因：雖然如此，消息傳遞的基本通信模式是簡(jiǎn) 略和清楚的，學(xué)習(xí)和掌握這些部分并不困難，因此目前大量的并行程序設(shè)計(jì)仍然是消息傳 遞并行編程模式。本文的并行工作考慮到為了盡可能擴(kuò)大程序的適用面，因此采用消息傳 遞模型。 本文考慮到并行語(yǔ)言的使用廣泛性和并行程序設(shè)計(jì)的通用性，另外由于c 語(yǔ)言在工程 和科學(xué)計(jì)算中的廣泛應(yīng)用，因此選擇m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 并行標(biāo)準(zhǔn)的c 語(yǔ)言版 本實(shí)現(xiàn)并行算法6 4 】 m p i 是一個(gè)庫(kù)，而不是一門語(yǔ)言?？梢园裞 + m p i 看作是一種在原來(lái)串行語(yǔ)言( c 語(yǔ)言) 基礎(chǔ)之上擴(kuò)展后得到的并行語(yǔ)言。m p i 庫(kù)可以被c c + + 調(diào)用，從語(yǔ)法上說(shuō)，它遵守所有對(duì) 庫(kù)函數(shù)過(guò)程的調(diào)用規(guī)則，與一般的函數(shù)過(guò)程沒(méi)有什么區(qū)別。m p i 是種標(biāo)準(zhǔn)或規(guī)范的代表， 而不特指某一個(gè)對(duì)它的具體實(shí)現(xiàn)。迄今為止，所有的并行計(jì)算機(jī)制造商都提供對(duì)m p i 的支 持，可以在網(wǎng)上免費(fèi)得到m p i 在不同并行計(jì)算機(jī)上的實(shí)現(xiàn)，一個(gè)正確的m p i 程序，可以 不加修改地在所有的并行機(jī)上運(yùn)行。m p i 是一種消息傳遞編程模型，并成為這種編程模型 的代表和事實(shí)上的標(biāo)準(zhǔn)m p i 雖然很龐大，但是它的最終日的是服務(wù)于進(jìn)程問(wèn)通信這一目標(biāo) 的。在m p i 上很容易移植其他的并行代碼，而且編程者不需要去努力掌握許多其他的全新 概念，就可以學(xué)習(xí)編寫m p i 程序。正是由于m p i 的這些特點(diǎn)，促使本文的并行算法都采 用m p i 來(lái)實(shí)現(xiàn)。 1 4 文章結(jié)構(gòu)安排 本文主要研究具有數(shù)狀態(tài)空間的半m a r k o v 控制過(guò)程在無(wú)窮水平平均代價(jià)準(zhǔn)則下的性 能靈敏度分析和優(yōu)化問(wèn)題。給出了以等價(jià)m a r k o v 過(guò)程和嵌入m a r k o v 鏈的性能勢(shì)表示的靈 敏度公式，建立了優(yōu)化理論，給出了最優(yōu)性方程并證明了解的存在性定理：研究了優(yōu)化算法， 給出了基于單個(gè)樣本軌道的仿真優(yōu)化算法及其并行算法。并給出了大量的數(shù)值例子，來(lái)說(shuō) 明相應(yīng)算法的應(yīng)用。文章的結(jié)構(gòu)安排如下： 第二章中建立了半m a r k o v 過(guò)程的性能勢(shì)理論，并在性能勢(shì)的基礎(chǔ)上討論了穩(wěn)態(tài)性能 勢(shì)靈敏度分析問(wèn)題。首先利用等價(jià)無(wú)窮小矩陣，定義了半m a r k o v 過(guò)程的p o i s s o n 方程，將 該p o i s s o n 方程的解定義為半m a r k o v 過(guò)程的性能勢(shì)：然后利用等價(jià)m a r k o v 過(guò)程和嵌入 m a r k o v 鏈的方法，討論了半m a r k o v 過(guò)程的性能靈敏度分析問(wèn)題，導(dǎo)出了基于等價(jià)m a r k o v 1 4 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 過(guò)程和嵌入m a r k o v 鏈的性能勢(shì)的靈敏度公式。并對(duì)其進(jìn)行了串行和并行的仿真。 第三章討論了一類可數(shù)狀態(tài)空間的半m a r k o v 控制過(guò)程的性能優(yōu)化問(wèn)題，研究半 m a r k o v 控制過(guò)程基于直接計(jì)算的理論優(yōu)化方法，討論了半m a r k o v 控制過(guò)程基于樣本軌道 仿真的優(yōu)化方法。 第四章，我們給出了通訊中兩個(gè)實(shí)際網(wǎng)絡(luò)的優(yōu)化與導(dǎo)數(shù)估計(jì)的應(yīng)用實(shí)例一是m a r k o v 決 策過(guò)程方法在呼叫接入控制中的應(yīng)用；二是m p h 1 排隊(duì)系統(tǒng)的性能靈敏度估計(jì)與仿真及其 在a t m 交換機(jī)性能分析中的應(yīng)用。 最后對(duì)本文工作做了一個(gè)總結(jié)，指出了進(jìn)一步的研究方向。 事實(shí)上，許多實(shí)際人造系統(tǒng)，例如柔性制造系統(tǒng)中自動(dòng)車的移動(dòng)策略，物流系統(tǒng)中的 最小代價(jià)路徑問(wèn)題，大規(guī)模計(jì)算機(jī)和通信網(wǎng)絡(luò)中的多媒體信流的接收和發(fā)送，系統(tǒng)的最優(yōu) 維護(hù)代價(jià)和安全可靠性等問(wèn)題，最終均可歸結(jié)為一個(gè)半m a r k o v 控制過(guò)程問(wèn)題。本論文的 研究能夠?yàn)榇罅繉?shí)際復(fù)雜人造系統(tǒng)的性能優(yōu)化提供一個(gè)直接的、行之有效的方法，這對(duì)進(jìn) 一步改進(jìn)系統(tǒng)的設(shè)計(jì)，提高系統(tǒng)的運(yùn)行效率和管理水平具有極其重要的意義。 中國(guó)科學(xué)技術(shù)大學(xué)碩士論文 第二章半m a r k o v 性能勢(shì)及其仿真 2 1 半m a r k o v 性能勢(shì)理論 在實(shí)際系統(tǒng)中，我們還常常會(huì)遇到非m a r k o v 型排隊(duì)網(wǎng)絡(luò)的情況，與m a r k o v 過(guò)程相比， 半m a r k o v 過(guò)程或廣義半m a r k o v 過(guò)程具有更廣泛的應(yīng)用范圍。 2 1 1 半m a r k o v 過(guò)程 定義1 若狀態(tài)空間= 1 , 2 ，k ) 上的隨機(jī)過(guò)程n = n ，；f 0 ) 滿足下列條件： ( 1 ) 對(duì)任意的f ，j ，若已知過(guò)程處于狀態(tài)f ，則它下一次轉(zhuǎn)移到狀態(tài)的概率是p 口， 并設(shè)p 。= 0 ( 2 ) 若已知過(guò)程處于狀態(tài)f 和下一次將轉(zhuǎn)移到狀態(tài)j ，則它在狀態(tài)f 的逗留時(shí)間的分布為 弓。 則稱n = n ，；f 0 ) 為一個(gè)半m a r k o v 過(guò)程( s m p ) 。 定義2 設(shè)n = n ，；f 0 ) 為狀態(tài)空間= 1 , 2 ，k ) 上的隨機(jī)過(guò)程， 0 = r l f 2 是該過(guò)程發(fā)生狀態(tài)轉(zhuǎn)移的時(shí)刻，則x 。= m 。+ o 是過(guò)程在時(shí)刻f 。發(fā)生的第刀 次轉(zhuǎn)移后所處的狀態(tài)。若對(duì)任意的整數(shù)，2 0 ，任意的i o ，i ，f ，j 和任意的實(shí)數(shù)f 0 ， 均有 = 工一乙4 五= 攻，后= a 1 1 ；門一1 ，k = 蠢，；乙) = p ( x 州= j , t 川一f 。刮以= f ) = 鱗( f ) ( 2 1 ) 則稱隨機(jī)過(guò)