[發明專利]加速壓縮方法以及加速壓縮裝置

有效

• 申請號: 201910091399.1
• 申請日: 2019-01-30
• 公開（公告）號: CN109857463B
• 公開（公告）日: 2020-12-01
• 發明（設計）人: 李琳;王崢;李曉陽;齊宗普
• 申請（專利權）人: 上海兆芯集成電路有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38;G06F16/903;H03M7/30
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 徐協成

本發明公開一種加速壓縮方法以及加速壓縮裝置。該加速壓縮裝置包括預取緩沖器(look?ahead buffer)、字串匹配處理流水線及控制電路。從數據緩沖器(data buffer)提取的待壓縮字串被存儲至預取緩沖器。在每個發布周期從所述預取緩沖器并行發布P個實例。當這些實例所對應的P個子字串互為完全相同時，所述控制電路所述P個實例中的一個實例發送至所述字串匹配處理流水線進行匹配操作，而不將所述P個實例中的其余實例發送至所述字串匹配處理流水線。

技術領域

本發明涉及一種加速裝置，且特別涉及一種對壓縮操作進行硬件加速的加速壓縮方法以及加速壓縮裝置。

背景技術

壓縮加速裝置(compression accelerator)是專門協助執行壓縮/解壓縮的硬件。壓縮加速裝置一般會采用基于字典的壓縮算法(例如LZ77、LZSS、LZ78、LZW等算法)。在字典(即滑動窗，sliding window)中的位置信息(包含匹配長度與匹配偏移量)被用來替代原始數據(raw data)，從而實現數據壓縮。對于壓縮加速裝置來說，最復雜的部分在于進行最長首碼字串匹配(longest-prefix string matching)，而最長首碼字串匹配方法通常可歸類為：基于內容可定址存儲器(CAM-based，Content Addressable Memory-based)以及基于散列(hash-based)二種。

以基于散列的字串匹配器為例，其通常利用散列電路將待壓縮字串的多個字符(散列鍵，Hask Key)轉換為散列值(Hash Value)。散列電路依據散列值對散列表(hashtable)進行查表與比較。散列鍵對應的散列值出現在散列表中，表明字典(滑動窗)的內容具有這個字符(散列鍵)，因此壓縮加速裝置可以獲得這個字符在字典(滑動窗)中的位置(匹配偏移量)，接著進行最長匹配(Longest Match，LM)比較。所謂最長匹配比較，是從所述匹配偏移量開始，在字典(滑動窗)中尋找最長能匹配的長度。最后，壓縮加速裝置可以輸出匹配對(match pair，即匹配長度與匹配偏移量)來替代原始數據(raw data)，從而實現數據壓縮。

無論如何，若是待壓縮字串的內容出現了大量連續重復字符，很顯然地，這些連續重復字符(相同的Hask Key)必然對應相同的散列值。相同的散列值都進入同一個散列庫(Hash Bank)，導致原本可以并行方式處理多個散列鍵的硬件壓縮加速器，只能以串行方式處理，進而導致數據吞吐能力(throughput)降低，甚至可能會降低至軟件壓縮的水準。

發明內容

本發明提供一種加速壓縮方法以及加速壓縮裝置，以改善相同內容的多個子字串被發送至散列匹配器導致散列沖突的情形，提高硬件壓縮加速器的壓縮效率。

本發明的實施例提供一種加速壓縮方法，用以實施于一加速壓縮裝置中。加速壓縮裝置包括預取緩沖器及字串匹配處理流水線。所述加速壓縮方法包括：從數據緩沖器提取待壓縮字串并存儲至預取緩沖器，其中所述待壓縮字串包括Q個字符；以及在每個發布周期從所述預取緩沖器并行發布P個實例(instance)。其中，所述P個實例的每一個依序對應于以所述待壓縮字串中的連續P個字符的每一個字符作為起始字符的一個子字串，其中Q和P為大于1的正整數，且Q大于P。當所述P個實例所對應的P個所述子字串互為完全相同時，將所述P個實例中的其中之一發送至所述字串匹配處理流水線進行匹配操作，而不將所述P個實例中的其余實例發送至所述字串匹配處理流水線。