輸入緩存調度算法的仿真與實現范文

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

《空間電子技術雜志》2015年第一期

1一種改進的串行調度算法

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

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

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

2OPNET仿真及比較

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

3硬件實現的分析與仿真

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

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

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

4結論

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

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