輸入緩存調(diào)度算法的仿真與實現(xiàn)范文

本站小編為你精心準(zhǔn)備了輸入緩存調(diào)度算法的仿真與實現(xiàn)參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

《空間電子技術(shù)雜志》2015年第一期

1一種改進(jìn)的串行調(diào)度算法

1．1算法思想由于衛(wèi)星信道具有時延長、星上芯片資源有限等特點，在星上交換機(jī)中要求輸入緩存調(diào)度算法具有較好的調(diào)度時延及丟失率等性能。文章采用串行調(diào)度的思想，對原有串行調(diào)度算法進(jìn)行改進(jìn)，在對端口仲裁時，改進(jìn)算法優(yōu)先選擇對收到請求數(shù)目最少的輸出端口進(jìn)行仲裁，較晚仲裁收到請求數(shù)目較多的端口，這樣可以增加每個時隙內(nèi)匹配更多輸入/輸出端口的可能性，從而改善星上交換機(jī)性能。同時每個端口在仲裁時采用了輪詢指針的方法，該指針在每次成功匹配后都進(jìn)行更新，這樣能夠保證算法的公平性。改進(jìn)的輸入緩存調(diào)度算法包括以下幾個步驟:首先，各個輸入端口同時向它的隊列中信元可能到達(dá)的輸出端口發(fā)送調(diào)度請求信號。其次，所有收到請求的輸出端口采用串行的方式進(jìn)行仲裁。仲裁所有收到請求的輸出端口時，選擇收到請求數(shù)目較少的輸出端口優(yōu)先進(jìn)行仲裁，較晚仲裁請求數(shù)目較多的輸出端口。當(dāng)每個輸出端口進(jìn)行仲裁時，可從輪詢指針目前指示的輸入端口開始，選擇出一個尚未匹配的輸入端口，然后通知各個輸入端口其請求是否被準(zhǔn)許，同時更新該輸出端口的輪詢指針。當(dāng)完成一個輸出端口的仲裁后，可以重新開始對下一個輸出端口的仲裁，最終輪詢完所有的輸出端口。由于很難通過建立數(shù)學(xué)模型的方法來比較各種不同調(diào)度算法的性能，因此本文在對改進(jìn)算法進(jìn)行性能分析、舉例說明的基礎(chǔ)上，利用仿真的方法來比較各算法性能，最后通過FPGA設(shè)計對其可行性進(jìn)行驗證。

1．2性能分析帶寬利用率、調(diào)度時延及公平性是衡量Crossbar調(diào)度算法性能的幾個主要指標(biāo)。帶寬利用率是指平均每次調(diào)度匹配成功的輸入、輸出端口數(shù)目與Crossbar開關(guān)總端口數(shù)目之比。當(dāng)交換結(jié)構(gòu)總端口數(shù)目一定時，如果每次調(diào)度匹配成功的輸入、輸出端口數(shù)目越多，那么該算法的帶寬利用率也就越高，同時若信元在隊列中等候的時間越短，交換結(jié)構(gòu)中信元平均延時也就越短。因此當(dāng)緩存隊列有限時，增加每次匹配的端口數(shù)目也可以降低交換結(jié)構(gòu)中信元的丟失率。(1)不同仲裁順序?qū)rossbar交換結(jié)構(gòu)帶寬利用率的影響由于采用不同的仲裁順序，交換結(jié)構(gòu)可成功匹配輸入、輸出端口的數(shù)目也不同，這里首先分析并比較不同的仲裁順序?qū)Τ晒ζヅ涠丝跀?shù)目產(chǎn)生的影響。這里假設(shè)有兩個輸出端口a和b，各端口分別收到m1、m2個輸入端口的請求，并且m1＞m2，當(dāng)首先匹配輸出端口b時，輸出端口a成功匹配的概率將大于先匹配輸出端口a時輸出端口b成功匹配的概率。證明:(a)當(dāng)兩個輸出端口收到的請求中，所有輸入端口都沒有重復(fù)時，那么按照這兩種順序成功匹配數(shù)目相同。(b)當(dāng)兩個輸出端口收到的請求中，有m個重復(fù)的輸入端口(m＜m1，m2)若優(yōu)先匹配輸出端口選擇的輸入端口不在這m個端口中，仲裁順序不會影響成功匹配端口的數(shù)目，因此這里主要考慮優(yōu)先匹配輸出端口在m個輸入端口中選擇輸入端口的情況。當(dāng)優(yōu)先匹配輸出端口a時，以的概率在m/m1個端口中選擇輸入端口;其次匹配輸出端口b時，該輸出端口可選擇輸入端口的數(shù)目變?yōu)閙2－1，那么該情況下輸出端口成功匹配的概率是。綜上所述，優(yōu)先選擇仲裁收到請求數(shù)目較少的輸出端口可以增加成功匹配端口數(shù)目的概率，進(jìn)而增加了提高Crossbar交換結(jié)構(gòu)帶寬利用率的可能性。(2)比較keepfull過程下信元的最大等待時延keepfull到達(dá)過程是指在任何時刻，任何VOQ隊列都非空，這種情況下原有串行調(diào)度算法中緩存區(qū)信元在VOQ隊頭等待被交換的最大延時為N2，而在改進(jìn)輸入緩存調(diào)度算法中，緩存區(qū)信元在隊頭等待被交換的最大延時為N。證明:假設(shè)緩存區(qū)中某個信元在時刻t成為某隊列的隊頭(HeadOfLine)信元:(a)那么根據(jù)原算法的思想，在t時刻后的N2次匹配中，必然會有N次匹配先從端口b開始進(jìn)行仲裁;由于該算法中輪詢指針僅在首次匹配后修改，那么在之后N次仲裁中，輸出端口b的輪詢指針必然會有一次等于a，因此，在t時刻后的N2個時隙內(nèi)該信元必然會被交換到輸出端口b。(b)根據(jù)改進(jìn)算法的思想，當(dāng)keepfull到達(dá)過程時，該算法可以得到完全匹配。這是因為改進(jìn)算法在每次匹配成功后都需要更新該輸出端口處得的輪詢指針，這樣可保證各個輸出端口處的輪詢指針必然不同。這種情況下各個輸出端口收到輸入端口的請求數(shù)目都是N，而每次匹配的順序不會改變，那么在t時刻后的N個時隙內(nèi)，輸出端口的輪詢指針必然會有一次等于a，因此，在t時刻后的N個時隙內(nèi)該信元必然會被交換到輸出端口b。證畢。綜上所述，本文提出的改進(jìn)輸入串行調(diào)度算法優(yōu)先匹配選擇范圍較小的輸出端口，較晚匹配選擇范圍較大的輸出端口，這樣相比收到請求少的輸出端口，成功匹配的概率比較大。因此，改進(jìn)輸入串行調(diào)度算法在每個信元時隙內(nèi)可以比原算法獲得更多的成果匹配數(shù)目，同時降低了調(diào)度時延、丟失率等指標(biāo)，也可以更好地滿足衛(wèi)星交換的需要。另一方面，改進(jìn)算法每次成功匹配后都會更新輸出端口處的輪詢指針，這樣能夠保證算法的公平性。

1．3舉例說明下面以4×4的交換單元為例進(jìn)行對原有算法和改進(jìn)算法進(jìn)行說明:圖1給出了一個在4端換開關(guān)上分別使用輸出串行調(diào)度算法和改進(jìn)算法的例子。某時刻各輸入端口的請求和調(diào)度器的狀態(tài)分別如圖1中(a)和(b)所示。根據(jù)原有輸出串行調(diào)度算法，從輸出端口1開始，按照1、2、3、0的順序依次對每個輸出端口進(jìn)行仲裁。首先對輸出端口1進(jìn)行匹配，根據(jù)輪詢指針的優(yōu)先級選擇了輸入端口1;接著輸出端口2進(jìn)行仲裁，由于該端口只收到輸入端口1的一個請求，而該輸入端口又已經(jīng)被匹配，因此在該時隙里輸出端口2無法得到匹配;同理對3、0端口分別匹配，最終得到如圖1中(c)所示的結(jié)果。而該二分圖可以達(dá)到如圖1中(d)所示的最大匹配。在改進(jìn)的串行調(diào)度算法中，收到請求數(shù)目最少的輸出端口優(yōu)先仲裁，即按照輸出端口2、0、3、1的順序進(jìn)行仲裁，對每個輸出端口仲裁時仍然按照輪詢(Round-Robin)指針的方法，每個端口輪詢指針的狀態(tài)依然如圖1中(b)所示。該算法首先為輸出端口2選擇輸入端口，由于只收到輸入端口1的請求，所以選擇輸入端口1，同時該輸出端口的輪詢指針指向輸入端口2;接著為輸出端口0、3進(jìn)行匹配，為保證公平性，每個端口得到匹配后都要更新輪詢指針;最后匹配輸出端口1時，雖然已有3個輸入端口被匹配，但由于該輸出端口收到的請求數(shù)目最多，因此在這種情況下，該端口獲得匹配的可能性仍然比較大。在這個例子中，輸出端口1仍然得到了匹配。圖1中(e)給出了改進(jìn)算法調(diào)度的結(jié)果。從分析的結(jié)果可知，在這種情況下，采用原有的輸出串行調(diào)度算法得到的匹配數(shù)目只是最大匹配的一半;而采用改進(jìn)算法得到的匹配數(shù)目和最大匹配相同。這是因為根據(jù)收到請求的數(shù)目來安排仲裁輸出端口的順序，保證了選擇范圍較小的輸出端口先仲裁，而選擇范圍較大的輸出端口即使較晚仲裁，較之收到請求少的輸出端口，得到匹配的概率也會較大。這種算法不一定達(dá)到最大匹配，但大大增加了接近最大匹配的概率。

2OPNET仿真及比較

本節(jié)利用OPNET軟件對改進(jìn)的輸入緩存調(diào)度算法及其他典型算法進(jìn)行仿真并進(jìn)行性能比較。iS-LIP算法是目前比較常用的一種輸入緩存調(diào)度算法，該算法通常少于log2N次迭代后收斂［14］，也具有一定的代表性。因此，本節(jié)通過OPNET構(gòu)造一個16×16的Crossbar交換結(jié)構(gòu)仿真模型，在該模型中對4-SLIP算法、原有串行調(diào)度算法及改進(jìn)的串行調(diào)度算法進(jìn)行仿真，并根據(jù)仿真結(jié)果來分析并比較這三種算法在高負(fù)載，突發(fā)長度為32情況下的平均調(diào)度時延，同時在緩存隊列有限的情況下，比較改進(jìn)輸入緩存算法與原串行調(diào)度算法的丟失率。在圖2中，當(dāng)信元突發(fā)到達(dá)時，改進(jìn)算法的平均調(diào)度時延明顯小于4-SLIP算法和原輸出串行調(diào)度算法。這是由于串行迭代調(diào)度算法能夠避免并行迭代算法中的同步現(xiàn)象，這樣可以增加每次調(diào)度中成功匹配的數(shù)目，同時也就降低了平均時延;因此仿真中的兩種串行調(diào)度算法時延都小于4-SLIP算法，而本文提出的改進(jìn)串行調(diào)度算法在原串行調(diào)度的基礎(chǔ)優(yōu)先仲裁請求數(shù)目較少的輸出端口，使調(diào)度中成功匹配的數(shù)目增加，因此改進(jìn)算法的平均時延低于原串行調(diào)度算法;而改進(jìn)串行調(diào)度算法在各輸出端口成功匹配后更新輪詢指針，也保證了算法的公平性。從圖3中可看出，當(dāng)負(fù)載分別為0．65和0．95、突發(fā)長度為10時，不同VOQ隊列長度下改進(jìn)串行調(diào)度算法帶來的信元丟失率小于輸出串行調(diào)度算法;當(dāng)負(fù)載較低(0．65)時，兩種算法的丟失率均小于負(fù)載較高(0．95)的情況;另外增加緩存區(qū)的大小可明顯減少低負(fù)載(0．65)下信元的丟失率，但是要減少高負(fù)載(0．95)下到達(dá)信元的丟失率，緩存區(qū)的設(shè)置需要很大。

3硬件實現(xiàn)的分析與仿真

3．1調(diào)度模塊的硬件設(shè)計框圖圖4給出了基于星上交換的輸入緩存調(diào)度算法調(diào)度模塊的實現(xiàn)框圖，該調(diào)度模塊主要由時序產(chǎn)生、指針產(chǎn)生、請求處理、仲裁和輸出控制等模塊組成。時序產(chǎn)生模塊根據(jù)改進(jìn)算法的要求產(chǎn)生當(dāng)前需要輪詢的輸出端口號，同時由R－R指針產(chǎn)生模塊產(chǎn)生該端口處的輪詢指針;仲裁模塊根據(jù)請求及當(dāng)前輪詢指針對該輸出端口進(jìn)行仲裁，并將仲裁結(jié)果交給輸出控制模塊，同時更新輪詢指針;當(dāng)輸出控制模塊收到所有輸出端口的仲裁結(jié)果后，將每個輸入端口匹配的結(jié)果分別送給各輸入端口及交換模塊，用于下個時隙信元的交換。

3．2工作頻率與端口速率的關(guān)系本文提出的星上輸入緩存調(diào)度算法完成每次調(diào)度共需要N+1個時鐘節(jié)拍，調(diào)度模塊需要在交換一個信元的時間內(nèi)計算出下個時隙的端口匹配情況，因此調(diào)度的總時間應(yīng)該小于交換一個信元的時間。假設(shè)交換機(jī)的端口速率為Vbps，調(diào)度模塊芯片的工作頻率為MHz，端口數(shù)目為N。由于交換機(jī)內(nèi)部采用64字節(jié)的定長交換，每秒鐘到達(dá)的信元數(shù)目為V/(64*8)，那么信元到達(dá)的周期為T=(64×8)/V秒，也就是說要在時間T內(nèi)完成一個信元的交換;另一方面，平均每次調(diào)度需要N+1個時鐘節(jié)拍，那么調(diào)度模塊完成一次調(diào)度的時間為(N+1)/Ms。

3．3FPGA仿真結(jié)果星上輸入緩存調(diào)度算法FPGA仿真的輸入條件為每個輸入端口的請求，如果該輸入端口有信元發(fā)送到第j個輸出端口，那么該輸入端口的第j位設(shè)為1;通過仿真應(yīng)該得到的是每個輸入端口的匹配情況，如果該輸入端口與第j個輸出端口匹配，那么發(fā)往該輸入端口的結(jié)果中第j位為1。每個輸出端口處的輪詢指針根據(jù)每次匹配的結(jié)果來更新。本文通過編寫輸入端口請求消息作為激勵源，并對比VHDL仿真的結(jié)果和按照算法應(yīng)得到的匹配結(jié)果。如果仿真得到的匹配結(jié)果與本文提出的改進(jìn)算法期望得到的結(jié)果相同，說明該算法是可實現(xiàn)的。仿真分為功能仿真和時序仿真，前者驗證設(shè)計模塊的邏輯功能，后者用于驗證設(shè)計模塊的時序關(guān)系。由于不同器件的內(nèi)部時延不一樣，不同的布局布線方案也給時延造成不同的影響。因此在設(shè)計處理以后，對系統(tǒng)和各模塊進(jìn)行時序仿真，分析其時序關(guān)系，估計設(shè)計的性能，以及檢查和消除競爭冒險等是非常有必要的。實際上這也是與實際器件工作情況基本相同的仿真。因此，為仿真實際器件的工作情況，本節(jié)采用時序仿真的方法來驗證星上輸入緩存調(diào)度算法的FP-GA設(shè)計。下面以仿真中一個信元時隙里的調(diào)度為例驗證本算法的可實現(xiàn)性。假設(shè)輸入條件如矩陣A表示，表示輸入端口A(i，j)=1有信元準(zhǔn)備發(fā)送到輸出端口j。圖5為本次ModelSim仿真結(jié)果的波形圖。將仿真結(jié)果與計算出的結(jié)果相比較，可看出兩者一致，說明仿真正確，本文提出的改進(jìn)的輸入緩存調(diào)度算法是可實現(xiàn)的。

4結(jié)論

針對星上交換的性能要求，本文對原有的串行調(diào)度算法進(jìn)行了改進(jìn)，并對改進(jìn)算法進(jìn)行了性能分析。同時本文構(gòu)造了OPNET仿真模型，在信元突發(fā)到達(dá)過程下對改進(jìn)算法和常見的幾種典型調(diào)度算法進(jìn)行了仿真和比較。仿真結(jié)果表明，在平均調(diào)度時延方面，本文提出的改進(jìn)串行調(diào)度算法性能明顯優(yōu)于iSLIP算法及原有輸出串行調(diào)度算法;另外，當(dāng)緩存區(qū)大小有限時，改進(jìn)串行調(diào)度算法的丟失率明顯小于原串行調(diào)度算法。最后，本文對改進(jìn)串行調(diào)度算法節(jié)能型了硬件分析和仿真，通過分析和仿真算法可知，該算法是可實現(xiàn)的，且實現(xiàn)起來比并行調(diào)度算法更加簡單。因此，針對星上交換的時延大且芯片受限等特點，可考慮將該算法用于ATM或IP交換結(jié)構(gòu)中，同時也可以應(yīng)用于多級交換的基本交換單元里。

作者：張怡周詮黎軍李靜玲梁薇單位：中國空間技術(shù)研究院西安分院空間微波技術(shù)國家級重點實驗室