文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2016.01.003
中文引用格式： 周佳佳，李濤，黃小康. 多核同時(shí)多線(xiàn)程處理器的線(xiàn)程調(diào)度器設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2016，42(1)：19-21.
英文引用格式： Zhou Jiajia，Li Tao，Huang Xiaokang. Design of a thread scheduler in a simultaneous multi-threaded muti-core processor[J].Application of Electronic Technique，2016，42(1)：19-21.
0 引言
隨著并行技術(shù)的不斷發(fā)展，如何更好地提高處理器的并行處理性能成為處理器設(shè)計(jì)者們急需解決的熱點(diǎn)問(wèn)題。傳統(tǒng)處理器通過(guò)開(kāi)發(fā)指令級(jí)并行(Instruction Level Parallelism，ILP)[1]來(lái)提高處理器的性能，但由于應(yīng)用程序自身的ILP很低、硬件的復(fù)雜度及功耗等眾多因素的影響導(dǎo)致處理器的性能不高。因此設(shè)計(jì)者們把目光紛紛投向更高層次的并行-線(xiàn)程級(jí)并行(Thread Level Parallelism，簡(jiǎn)稱(chēng)TLP)[1-2]。
同時(shí)多線(xiàn)程最先由美國(guó)加州大學(xué)的Tullsen等人在1995年開(kāi)始研究，并提出了基本的SMT[3-4]處理器模型。主要原理是通過(guò)資源競(jìng)爭(zhēng)和資源動(dòng)態(tài)共享的方式使所有的執(zhí)行單元同時(shí)活躍，充分利用TLP和ILP來(lái)提高處理器的資源利用率。
目前的商用處理器采用的技術(shù)主要是同時(shí)多線(xiàn)程和片上多處理器技術(shù)，例如Intel的P4處理器[5]的Hyper-thread技術(shù)實(shí)現(xiàn)同時(shí)執(zhí)行兩個(gè)線(xiàn)程，IBM的Power5處理器[6]每個(gè)芯片有兩個(gè)內(nèi)核，每個(gè)內(nèi)核可以同時(shí)執(zhí)行兩個(gè)線(xiàn)程。SUN的Niagara處理器[7]每個(gè)芯片有8個(gè)內(nèi)核，每個(gè)內(nèi)核可以同時(shí)執(zhí)行4個(gè)線(xiàn)程。我國(guó)的龍芯2號(hào)處理器[8]也采用了超標(biāo)量與同時(shí)多線(xiàn)程技術(shù)來(lái)設(shè)計(jì)。
本文在多核處理器[9-11]的基礎(chǔ)上提出了一種采用同時(shí)多線(xiàn)程技術(shù)[3-4]的線(xiàn)程調(diào)度器[12]設(shè)計(jì)。與Niagara處理器相比，本文中的多線(xiàn)程處理器擁有16個(gè)核，每個(gè)內(nèi)核一共具有8個(gè)線(xiàn)程，最大可以同時(shí)執(zhí)行4個(gè)線(xiàn)程，并且可以在高低線(xiàn)程之間快速切換，減少了因?yàn)榫€(xiàn)程中遇到長(zhǎng)周期指令所造成的資源浪費(fèi)，同時(shí)也提高了處理器的利用效率。
1 整體硬件結(jié)構(gòu)
時(shí)鐘共享多線(xiàn)程處理器是一種適用于圖形和圖像處理的并行陣列機(jī)。該陣列機(jī)支持MIMD(Multiple Instruction Stream Multiple Data Stream)運(yùn)行模式、分布式指令并行模式和流處理運(yùn)行模式這三種工作模式，同時(shí)還具有異步執(zhí)行、核間通信以及線(xiàn)程間通信的機(jī)制。
這種結(jié)構(gòu)的陣列機(jī)由16個(gè)處理單元(Processing Element，PE)互連構(gòu)成一個(gè)4×4的二維陣列，還包括1個(gè)前端處理器、4個(gè)協(xié)處理器、2個(gè)調(diào)度器及2個(gè)存儲(chǔ)管理。系統(tǒng)的整體結(jié)構(gòu)如圖1所示。
2 線(xiàn)程調(diào)度器功能描述
線(xiàn)程調(diào)度器完成的功能描述如下：
(1)監(jiān)測(cè)預(yù)處理模塊，當(dāng)外部需要給線(xiàn)程加載指令或數(shù)據(jù)時(shí)響應(yīng)預(yù)處理模塊；
(2)當(dāng)線(xiàn)程發(fā)生阻塞時(shí)負(fù)責(zé)切換線(xiàn)程，并產(chǎn)生PE某一個(gè)線(xiàn)程的啟動(dòng)信息，其中包括啟動(dòng)有效信號(hào)、 起始PC值、啟動(dòng)的線(xiàn)程號(hào)；
(3)線(xiàn)程之間的同步處理，負(fù)責(zé)監(jiān)視需要同步的線(xiàn)程是否同步結(jié)束；
(4)當(dāng)外部需要重新配置某一個(gè)線(xiàn)程的指令或數(shù)據(jù)時(shí)負(fù)責(zé)停止該線(xiàn)程，產(chǎn)生pe_stop信號(hào)；
(5)給外部提供三個(gè)8位的寄存器，分別為線(xiàn)程啟動(dòng)信息寄存器、線(xiàn)程結(jié)束信息寄存器、線(xiàn)程斷點(diǎn)信息寄存器。
3 同時(shí)多線(xiàn)程設(shè)計(jì)方案
同時(shí)多線(xiàn)程技術(shù)最大的優(yōu)點(diǎn)在于增加很少的面積，就能夠獲得很高的資源利用率，即用較小的成本換取較大的并行性能，充分地挖掘了線(xiàn)程級(jí)的并行。
本文基于時(shí)鐘共享多線(xiàn)程處理器提出的線(xiàn)程調(diào)度器支持八個(gè)線(xiàn)程，最多可以同時(shí)執(zhí)行四個(gè)線(xiàn)程。這四個(gè)線(xiàn)程同時(shí)執(zhí)行各自的程序。每個(gè)線(xiàn)程擁有各自獨(dú)立的取指單元、譯碼單元、指令存儲(chǔ)和數(shù)據(jù)存儲(chǔ)。而其他的資源，如各個(gè)執(zhí)行單元和地址流水線(xiàn)，則是八個(gè)線(xiàn)程共享。
在每一個(gè)時(shí)鐘周期的上升沿，每個(gè)PE最多有八條流水線(xiàn)在執(zhí)行，且最多可輸出四條流水線(xiàn)結(jié)果，這四條流水線(xiàn)產(chǎn)生的結(jié)果屬于不同的線(xiàn)程組，每個(gè)線(xiàn)程組都擁有高低兩個(gè)線(xiàn)程。因此在某一組中若有一個(gè)線(xiàn)程陷入阻塞狀態(tài)，則可以切換至組內(nèi)的另一線(xiàn)程來(lái)執(zhí)行程序，可以有效隱藏線(xiàn)程由于等待過(guò)程所造成的延遲，提高處理器整體的工作效率。
4 線(xiàn)程調(diào)度器詳細(xì)設(shè)計(jì)
4.1 線(xiàn)程管理器的總體結(jié)構(gòu)
該調(diào)度器由信息處理模塊、狀態(tài)控制模塊、寄存器模塊、PE控制模塊四大部分構(gòu)成，各模塊的連接關(guān)系如圖2所示。
線(xiàn)程調(diào)度器的工作流程為：信息處理模塊接收來(lái)自預(yù)處理模塊的配置信息、指令、數(shù)據(jù)及加載結(jié)束信號(hào)，判斷是否需要啟動(dòng)該線(xiàn)程。線(xiàn)程啟動(dòng)之后狀態(tài)控制模塊中對(duì)應(yīng)的線(xiàn)程狀態(tài)機(jī)發(fā)生跳轉(zhuǎn)，同時(shí)寄存器模塊實(shí)時(shí)記錄該線(xiàn)程的PC值。當(dāng)接收到譯碼模塊的阻塞信息時(shí)停止當(dāng)前運(yùn)行的線(xiàn)程且切換線(xiàn)程，PE控制模塊負(fù)責(zé)產(chǎn)生新線(xiàn)程的啟動(dòng)信息。當(dāng)線(xiàn)程運(yùn)行結(jié)束后，信息處理模塊負(fù)責(zé)記錄線(xiàn)程的結(jié)束信息。
4.2 線(xiàn)程調(diào)度器的工作模式
線(xiàn)程調(diào)度器擁有五種工作模式：?jiǎn)?dòng)模式、阻塞工作模式、同步模式、斷點(diǎn)模式和重配置模式。
啟動(dòng)模式線(xiàn)程接收來(lái)自預(yù)處理模塊的線(xiàn)程啟動(dòng)信息配置要啟動(dòng)的線(xiàn)程，將對(duì)應(yīng)的線(xiàn)程ID號(hào)和PC值發(fā)送給PE來(lái)執(zhí)行。
阻塞工作模式表示當(dāng)某一線(xiàn)程遇到阻塞，則切換到其線(xiàn)程組內(nèi)的另一線(xiàn)程上來(lái)執(zhí)行。若是兩個(gè)都阻塞，則先解除阻塞的線(xiàn)程先執(zhí)行。
同步模式下對(duì)需要同步的幾個(gè)線(xiàn)程進(jìn)行等待處理，并判斷是否達(dá)到同步。若達(dá)到，則解除同步模式，開(kāi)始正常執(zhí)行；若沒(méi)有達(dá)到，則繼續(xù)等待。
斷點(diǎn)模式是用來(lái)方便處理器進(jìn)行調(diào)試錯(cuò)誤的一種工作模式。當(dāng)程序計(jì)數(shù)器PC遇到斷點(diǎn)時(shí)，該線(xiàn)程停止工作，保存工作信息以待調(diào)試檢查。
重配置模式是對(duì)線(xiàn)程進(jìn)行重新配置，根據(jù)上層的需要對(duì)線(xiàn)程要執(zhí)行的程序內(nèi)容進(jìn)行添加或更改。
4.3 線(xiàn)程狀態(tài)轉(zhuǎn)移關(guān)系
如圖3所示，為線(xiàn)程調(diào)度器中線(xiàn)程的狀態(tài)轉(zhuǎn)移圖。
其中各個(gè)狀態(tài)說(shuō)明如下：
(1)IDLE：空閑狀態(tài)。當(dāng)線(xiàn)程啟動(dòng)信號(hào)有效時(shí)(th_start=1)，則狀態(tài)跳轉(zhuǎn)到RUN運(yùn)行狀態(tài)；
(2)RUN：運(yùn)行狀態(tài)。當(dāng)線(xiàn)程位于此狀態(tài)時(shí)，表示線(xiàn)程正在執(zhí)行，遇到阻塞或等待跳轉(zhuǎn)到WAIT狀態(tài)；
(3)BREAK：斷點(diǎn)狀態(tài)。當(dāng)線(xiàn)程的斷點(diǎn)數(shù)據(jù)收集結(jié)束(th_break_end=1)時(shí)，狀態(tài)跳轉(zhuǎn)到RUN運(yùn)行狀態(tài)；
(4)WAIT：等待狀態(tài)。當(dāng)線(xiàn)程發(fā)生重配置(th_recfg=1)時(shí)，則狀態(tài)跳轉(zhuǎn)到IDLE初始狀態(tài)；當(dāng)線(xiàn)程阻塞解除(th_blk_fns=1)時(shí)狀態(tài)跳轉(zhuǎn)到RUN運(yùn)行狀態(tài)；
(5)SYN：同步狀態(tài)。線(xiàn)程位于該狀態(tài)下，遇到同步解除(th_syn_fns=1)信號(hào)，跳轉(zhuǎn)到READY狀態(tài)；
(6)READY：準(zhǔn)備狀態(tài)。表示線(xiàn)程處于一個(gè)隨時(shí)可以啟動(dòng)的狀態(tài)，當(dāng)線(xiàn)程被選中時(shí)(th0_hit=1)，則狀態(tài)跳轉(zhuǎn)到RUN運(yùn)行狀態(tài)。
5 仿真結(jié)果分析和比較
本文采用Xilinx公司的ISE14.4工具對(duì)硬件電路進(jìn)行了綜合，選用Xilinx公司型號(hào)為XC7V2000t-2fhg1761的FPGA，設(shè)計(jì)電路的最高頻率可以到達(dá)431.816 MHz。
在完成功能仿真和綜合的同時(shí)，本文還進(jìn)行了簡(jiǎn)單的性能分析。測(cè)試在8個(gè)PE上進(jìn)行，采用圖像處理中的邊緣檢測(cè)算法，分別對(duì)32×32、64×64以及128×64的圖像進(jìn)行測(cè)試，最后得到的結(jié)果如表1所示。另外根據(jù)性能提升計(jì)算公式(1)[12]可以得出整體處理器的性能提升百分比如表2所示。
可以看出，對(duì)于比較小的圖像，過(guò)多的線(xiàn)程會(huì)導(dǎo)致整體運(yùn)算速度變慢。這是因?yàn)榇藭r(shí)圖像整體運(yùn)算時(shí)間比較短，線(xiàn)程切換所造成的延時(shí)會(huì)在整體時(shí)間中占據(jù)比較大的比例。而對(duì)于更大的圖像，同時(shí)多線(xiàn)程技術(shù)則對(duì)處理器的性能提升影響比較大。對(duì)于多核同時(shí)多線(xiàn)程處理器而言，八個(gè)線(xiàn)程的線(xiàn)程調(diào)度器設(shè)計(jì)會(huì)使處理器得到更高的性能提升，充分體現(xiàn)了同時(shí)多線(xiàn)程技術(shù)的優(yōu)點(diǎn)。
6 總結(jié)
本文通過(guò)對(duì)時(shí)鐘共享多線(xiàn)程處理器架構(gòu)的深入研究，采用同時(shí)多線(xiàn)程技術(shù)設(shè)計(jì)和實(shí)現(xiàn)了處理器的核心部件——線(xiàn)程調(diào)度器。通過(guò)在處理器的多個(gè)線(xiàn)程上運(yùn)行圖像處理算法，得到處理器的加速比最大為69.25%，充分提高了多核處理器的性能。并對(duì)所設(shè)計(jì)的硬件電路進(jìn)行了全面仿真驗(yàn)證，綜合和仿真結(jié)果表明電路的功能正確，工作頻率為431.816 MHz，達(dá)到了時(shí)鐘共享多線(xiàn)程處理器的需求。
參考文獻(xiàn)
[1] THEO U，BORUT R，JURIJ S.Multithreaded processors[J].The Computer Journal，2002，45(3)：320-348.
[2] BRUNIE N，COLLANGE S，DIAMOS G.Simultaneous branch and warp interweaving for sustained GPU performance[C].Computer Architecture(ISCA)，2012：49-60.
[3] 劉權(quán)勝，楊洪斌，吳悅.同時(shí)多線(xiàn)程技術(shù)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29(4)：963-967.
[4] EGGERS S J，EMER J S，LEVY H M，et al.Simultaneous multithreading：A platform fornext-generation processors[J].IEEE Micro，1997，17(5)：12-19.
[5] 張?jiān)?解析超線(xiàn)程技術(shù)[J].甘肅聯(lián)合大學(xué)學(xué)報(bào)，2007，21(4)：99-101.
[6] Frank Soltis.Power5對(duì)i系列意味著什么[J].中國(guó)經(jīng)濟(jì)和信息化，2004，20(6)：A2-A3.
[7] POONACHA K.Niagara：a 32-way multithreaded sparc processor[J].Mirco，IEEE，2005，25(2)：21-29.
[8] 李祖松，許先超，胡偉武，等.龍芯2號(hào)處理器的同時(shí)多線(xiàn)程設(shè)計(jì)[J].計(jì)算機(jī)學(xué)報(bào)，2009，32(11)：2266-2273.
[9] 黃虎才.多態(tài)陣列處理器的并行計(jì)算研究[D].西安：西安郵電大學(xué)，2014.
[10] 李濤，楊婷，易學(xué)淵.螢火蟲(chóng)2：一種多態(tài)并行機(jī)的硬件體系結(jié)構(gòu)[J].計(jì)算機(jī)工程與科學(xué)，2014，12(2)：191-200.
[11] 李濤，肖靈芝.面向圖形和圖像處理的輕核陣列機(jī)結(jié)構(gòu)[J].西安郵電學(xué)院學(xué)報(bào)，2012，17(3):41-47.
[12] 錢(qián)博文，李濤，韓俊剛，等.多態(tài)并行處理器中的線(xiàn)程管理器設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2014(2)：30-32.