[發(fā)明專利]一種并行環(huán)境下高吞吐量的模逆計算方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202110090167.1
• 申請日: 2021-01-22
• 公開（公告）號: CN112799637B
• 公開（公告）日: 2023-03-14
• 發(fā)明（設(shè)計）人: 朱輝;黃煜坤;李暉;劉興東;李臨風(fēng)
• 申請（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號: G06F7/72
• 分類號: G06F7/72;G06F21/64
• 代理公司: 西安長和專利代理有限公司 61227
• 代理人: 黃偉洪

1.一種并行環(huán)境下高吞吐量的模逆計算方法，其特征在于，所述并行環(huán)境下高吞吐量的模逆計算方法包括：

數(shù)據(jù)劃分階段：根據(jù)輸入數(shù)據(jù)的規(guī)模和并行計算平臺的計算能力選擇合適的參數(shù)，所述參數(shù)表示分組后每組包含數(shù)據(jù)的個數(shù)；根據(jù)所述參數(shù)對數(shù)據(jù)進(jìn)行分組并編號，建立原始輸入數(shù)據(jù)與分組后數(shù)據(jù)之間的一一映射關(guān)系；

并行求逆階段：在并行計算設(shè)備上開啟多個線程接收對應(yīng)多組數(shù)據(jù)的輸入，線程間并行運(yùn)行同時模逆算法；

數(shù)據(jù)組整合階段：所有線程運(yùn)行結(jié)束后可得到多組模逆數(shù)據(jù)；根據(jù)步驟一中建立的映射關(guān)系，將多組非完整數(shù)據(jù)整合為一組完整數(shù)據(jù)，即為所求的所有模逆值；

所述數(shù)據(jù)劃分階段包括三個子階段：參數(shù)選取階段、數(shù)據(jù)分組階段、映射關(guān)系建立階段，包括：

(1)參數(shù)選取階段：根據(jù)待求逆值的個數(shù)m和并行計算平臺的計算能力選擇合適的參數(shù)k；其中，所述k表示在完成數(shù)據(jù)分組階段后，每組數(shù)據(jù)包含待求逆值的個數(shù)；若k越大，則本計算方法的并行程度越不明顯，無法發(fā)揮并行計算平臺的全部性能；若k越小，則實際進(jìn)行的模逆運(yùn)算次數(shù)越多、計算方法的總計算量越多、線程束分化程度越明顯，計算方法對模逆運(yùn)算的吞吐量提升越不明顯；由于k值的選擇對方法的性能影響較大，需根據(jù)性能分析模塊的分析結(jié)果不斷對k值進(jìn)行調(diào)整；

(2)數(shù)據(jù)分組階段：將待求逆值劃分為編號共組數(shù)據(jù)，其中前組數(shù)據(jù)中每組數(shù)據(jù)包含編號j＝1，2，...，k共k個待求逆值，第組數(shù)據(jù)包含編號共個待求逆值；分組后的數(shù)據(jù)為其中i表示組編號，j表示組內(nèi)編號；

(3)映射關(guān)系建立階段：a₁，a₂，...，a_m這m個輸入值與分組后的數(shù)據(jù)建立映射關(guān)系如下：

2.如權(quán)利要求1所述的并行環(huán)境下高吞吐量的模逆計算方法，其特征在于，所述并行求逆階段，包括：并行計算設(shè)備上開啟個線程接受對應(yīng)組數(shù)據(jù)的輸入，每個線程最大接受k個待求逆值輸入，個線程并行運(yùn)行同時模逆算法，每個線程輸出所接收的待求逆值關(guān)于模p的逆。

3.如權(quán)利要求2所述的并行環(huán)境下高吞吐量的模逆計算方法，其特征在于，所述同時模逆算法分為三個子步驟：輸入值預(yù)處理步驟、模逆計算步驟和模逆迭代計算步驟，包括：

1)輸入值預(yù)處理步驟為：計算輸入序列每個值與它之前所有輸入值的模乘積，共需進(jìn)行(k-1)次模乘運(yùn)算；

2)模逆計算步驟，根據(jù)設(shè)備模乘計算能力的強(qiáng)弱，分別選擇使用基于費(fèi)馬小定理或基于拓展歐幾里得算法的模逆算法，計算經(jīng)過預(yù)處理后的序列最后一值的模逆；

3)模逆迭代計算步驟通過對臨時變量的迭代，計算每個預(yù)處理值與臨時變量的模乘來計算每個輸入值的模逆，該步驟需進(jìn)行(k-1)輪迭代，每輪迭代進(jìn)行2次模乘運(yùn)算，共計2(k-1)次模乘運(yùn)算，計算得到全部輸入值的模逆。

4.如權(quán)利要求1所述的并行環(huán)境下高吞吐量的模逆計算方法，其特征在于，所述數(shù)據(jù)組整合階段，包括：經(jīng)過并行求逆階段，所有線程運(yùn)行結(jié)束后可得到組共m個模逆值；根據(jù)數(shù)據(jù)劃分階段中建立的映射關(guān)系，并將這組數(shù)據(jù)整合為一組輸出值即為所求的m個逆值。