[發明專利]查找表尋址系統及方法

有效

• 申請號: 200680047898.1
• 申請日: 2006-10-17
• 公開（公告）號: CN101341470A
• 公開（公告）日: 2009-01-07
• 發明（設計）人: J·威爾遜;J·A·卡布羅特斯基;Y·斯坦;C·M·梅爾
• 申請（專利權）人: 阿納洛格裝置公司
• 主分類號: G06F12/00
• 分類號: G06F12/00
• 代理公司: 中國國際貿易促進委員會專利商標事務所
• 代理人: 屠長存

技術領域

本發明涉及一種改進的查找表尋址系統和方法。

背景技術

隨著計算機的速度由33MHz提高到1.0GHz甚至更高，計算機運算不能在一個周期內完成。于是采用了管線技術來最高效地利用更高的處理器性能并增加吞吐量。當前，深管線的使用已經多達15級甚至更多。一般來說，在管線化計算系統中有數個同時工作的平行構建部件，其中每一個部件分管整個處理中各個不同的部份。例如，計算單元(CU)負責計算，包含數據地址產生器(DAG)和定序器或控制電路的尋址單元，其中數據地址產生器負責根據所選的地址模式來獲取數據并將其存儲進入存儲器以及定序器或控制電路解碼并發出指令。DAG只是能夠對存儲器尋址的部件。結果，在深管線化系統中，如果某個指令取決于由前一個指令的結果，則在某個管線停止的地方，該管線會出現停滯，在重新開始工作之前等待有問題的指令結束。例如，如果在計算之后，DAG需要CU的輸出來獲取下一個數據，這種輸出不能直接傳送到DAG從而作為獲取數據的條件：在能被DAG處理繼續獲取下一個數據之前其必須被傳送通過管線。這是因為只有DAG能訪問存儲器并且能夠將計算單元結果轉換為地址指針以定位想要的數據。在多任務通用計算機中，這種停滯可能不是很關鍵，但在比如用于蜂窩電話、數字攝像機中的實時計算機系統中，這些停滯就是個問題。參見Wilson等人在2005年10月26日提交的題目為“IMPROVED?PIPELINE?DIGITAL?SIGNAL?PROCESSOR”的美國專利申請，序列號No.11/258,801，其全文通過引用集及于此。

在一種實施方式中，使用比特置換來實現數據加密。在CU中可以進行這種比特置換，但CU中的算術邏輯單元(ALU)被優化用于16、32或64比特運算，而對于逐比特置換則效率不高。例如，如果由ALU進行這種置換，每一比特需要三個運算周期：掩碼(mask)，移位(shift)和或運算(OR)需要。結果，置換單個32位字需要96個或更多的周期。

在另一種實施方式中，代替在ALU中進行置換，置換值可被存儲在位于外部存儲器中的查找表中。但是，此時在ALU中的R寄存器必須傳送字，例如32位，到可以對外部存儲器查找表尋址的DAG中的指針(P)寄存器。然而這需要具有大于33.5兆字節的內存或232位的龐大的查找表(LUT)。為了克服這個問題，可以將ALU中的R寄存器中的32位字處理為例如，4個字節(8位)或8個半字節(4位)。這降低了所需的存儲容量：對于4個字節，需要4個具有256條目、每一個為32位的查找表(或4千字節LUT)而對于8個半字節，需要16條目的8個、每一個為32位的查找表(或512字節LUT)。但是，這也產生了問題：此時對于單個32位字，ALU要求傳輸4(字節)或8(半字節)到DAG的P寄存器。每一次傳輸依次引起許多前面討論過的管線停滯問題。

在不同的但相關的問題中，線性反饋移位寄存器(LFSR)例如，CRC(循環冗余檢驗碼)、加擾器(scrambler)、解擾器(de-scrambler)中，柵格編碼(trellis)在通信系統中被廣泛使用。使用掩碼/移位/OR運算周期，這種LFSR運算可以通過CU按比例變化(scaled)，每次一位，與前面所述的具有同樣的問題。或者可以使用利用每周期4、8或16位的解決所述LFSR問題的特定硬件塊，例如，ASIC、FPGA。通過使用外部查找表或表，可以消除CU中的掩碼/移位/OR方法和ASIC方法，但仍帶有所有上述缺點。

發明內容

因此，本發明的一個目的是提供一種改進的查找表尋址系統和方法。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其最小化在計算單元和數據地址產生器之間出現的管線停滯。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其優化所述查找表的大小。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其加速線性反饋移位寄存器運算而無需額外的專用硬件，例如ASIC或FPGA。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其更快且更省電。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其能夠再利用現有的處理器部件。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其加速置換運算而無需增加專用硬件，例如ASIC或FPGA。

本發明的另一個目的是提供這樣的改進的查找表尋址系統和方法，其能被充分地變化尺寸以適應更大的存儲要求。