基于多核多線程的梅西算法的研究和實(shí)現(xiàn).pdf

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofMasterTheResearchandImplementationofMasseyOptimizationBasedonMulticoreandMultithreadByYataoZhaoSupervisor：AProfXiaojieQianComputerApplicationTechnologySchoolofInformatio

2、nEngineeringMay2011摘要摘要隨著多處理器技術(shù)的發(fā)展，多核技術(shù)得到了廣泛的應(yīng)用。多核處理器通過提高軟件的并行性來提高計(jì)算機(jī)性能，改變了計(jì)算機(jī)以前只依靠提高硬件性能來提高軟件運(yùn)行效率的規(guī)則，人們對(duì)軟件效率也提出了更高的要求。然而，今天我們使用的許多軟件都是設(shè)計(jì)于串行機(jī)上運(yùn)行的，多核硬件技術(shù)的發(fā)展要求與之相適應(yīng)的多核軟件的發(fā)展。因此，我們必須改變觀念，通過提升軟件的并行性來提高軟件的效率。在連續(xù)雷達(dá)的測(cè)距信號(hào)，遙控系統(tǒng)的遙控

3、信號(hào)，數(shù)字通信的群同步信號(hào)以及序列密碼產(chǎn)生密鑰序列等等中，求解域上序列的最短線性移位寄存器一直備受關(guān)注，梅西給出了求解這個(gè)序列的極小多項(xiàng)式的方法。但傳統(tǒng)的梅西算法是在單核處理器上順序執(zhí)行的，雖然多核處理器已經(jīng)出現(xiàn)，梅西算法卻只能利用其中的一個(gè)核心，因此梅西算法未能在多核平臺(tái)上獲得性能的提升。為了能夠充分地利用多核處理器的性能，使先前在單核處理器上運(yùn)行良好的軟件能在多核處理器上發(fā)揮更大效能，就必須改進(jìn)原有的程序，融進(jìn)并行算法的思想。本文在

4、線性移位寄存器的綜合問題上采用梅西算法，通過C語言、C撐語言編程，找到了產(chǎn)生該序列的最短線性移位寄存器。借助多線程技術(shù)，以多核為硬件基礎(chǔ)，從算法的設(shè)計(jì)和分析出發(fā)，將各種并行計(jì)算的特征抽象出來進(jìn)行歸納并設(shè)計(jì)。通過代碼向量化、循環(huán)并行化等技術(shù)進(jìn)行設(shè)計(jì)優(yōu)化。實(shí)驗(yàn)證明，優(yōu)化后的梅西算法，可以產(chǎn)生起始狀態(tài)可預(yù)置、序列周期可改變的隨機(jī)序列的序列發(fā)生器，當(dāng)序列長(zhǎng)度大于215時(shí)，多線程的梅西算法的性能明顯得到提升。并且隨著數(shù)據(jù)規(guī)模的擴(kuò)大，提升比例穩(wěn)定升