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

有效

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

本發明公開一種加速壓縮方法以及加速壓縮裝置。加速壓縮裝置包括預取存儲器(look?ahead memory)、字串匹配處理流水線以及控制電路。依據發布指針，控制電路將待壓縮字串的子字串從預取存儲器發布至字串匹配處理流水線進行匹配操作，以獲得匹配長度及匹配偏移量。依照退卻指針所對應的所述匹配長度，控制電路決定新退卻位置。當新退卻位置超越發布指針所指向的發布位置時，控制電路重置字串匹配處理流水線。

技術領域

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

背景技術

壓縮加速器(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)，從而實現數據壓縮。其中匹配對包括匹配長度(match length)與匹配偏移量(match offset)。

以1個字符占用1個字節為例，由于前述散列鍵是逐字節地(byte by byte)在待壓縮字串中取得的。當待壓縮字串的內容出現了前述的匹配對時，產生的匹配長度(matchlength)所覆蓋的字符可能已經被發送到散列電路進行計算或者甚至已經在進行最長匹配(Longest Match，LM)比較，這些字符的前述計算或比較就會成為不必要的冗余操作，造成匹配效率的降低。

發明內容

本發明提供一種加速壓縮方法以及加速壓縮裝置，以減少冗余操作。

本發明的實施例提供一種加速壓縮方法，實施于加速壓縮裝置中。加速壓縮裝置包括預取存儲器及字串匹配處理流水線。所述加速壓縮方法包括：依據發布指針(issuancepointer)從所述預取存儲器所存儲的待壓縮字串發布至少一個子字串(sub-string)；將所述子字串發送至所述字串匹配處理流水線進行匹配操作，以獲得所述子字串的匹配長度及匹配偏移量；依照退卻指針(retirement pointer)以及所述退卻指針所指向的在所述待壓縮字串中的退卻位置所對應的所述匹配長度，決定新退卻位置；以及當所述新退卻位置超越所述發布指針所指向的在所述待壓縮字串中的發布位置時，重置所述字串匹配處理流水線。

本發明的實施例提供一種加速壓縮裝置。所述加速壓縮裝置包括字串匹配處理流水線、預取存儲器以及控制電路。控制電路耦接于所述字串匹配處理流水線與所述預取存儲器。所述控制電路依據發布指針從所述預取存儲器所存儲的待壓縮字串發布至少一個子字串。所述控制電路將所述子字串發送至所述字串匹配處理流水線進行匹配操作，以獲得所述子字串的匹配長度及匹配偏移量。依照退卻指針以及所述退卻指針所指向的在所述待壓縮字串中的退卻位置所對應的所述匹配長度，所述控制電路決定新退卻位置。當所述新退卻位置超越所述發布指針所指向的在所述待壓縮字串中的發布位置時，所述控制電路重置所述字串匹配處理流水線。