LZ圧縮回路の設計とハード・ソフト 最適分割の検討 電子情報デザイン学科 高性能計算研究室 ４回生 中山 和也 2009/2/27
研究背景と目的 ・背景 -圧縮アルゴリズムは処理時間が長い -通信の分野で、トラフィック軽減用に、 HTML・画像等を高速圧縮して送信したい ・目的 -ハードで処理、圧縮時間の短縮 -ハード・ソフト最適分割についても検討
LZ圧縮の概要 ・Zip LHA 等の圧縮プログラムに使用されているアルゴリズム ・データを先頭から順番に符号化していく方式。 現在注目している位置から始まる記号列が、それ以前に出現していたかを探す。発見された場合、圧縮情報に置き換える。
アルゴリズム A B C D E A B C D E Pointer Index Equalnum 処理前 1.順にシーク。以前に同じ文字が出現していないか検索 Pointer 2.発見した場合、何文字前から一致したかをindexに記憶 Index 3. 残りの文字も同じかどうか調べる。Equalnumに一致文字数を記憶 Equalnum 処理前 A B C D E A B C D E 結果 圧縮後 A B C D E [ 5 5 ] Index・Equalnum
処理結果 235 1 5.9 40 ソース 圧縮後 ・ソース45kb→27kbに圧縮 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" 26文字前のHTMLと6文字一致 （空白文字を含む） 圧縮後 ASCII文字を整数に変換し、 確認すると[,]は[25,6] ・ソース45kb→27kbに圧縮 実行クロックサイクル数(Mclock) 速度向上比 Ｃプログラム 235 1 Verilog記述 5.9 40
モジュール構成と回路規模 Mem Loop Out モジュール名 Mem Loop Out total 処理内容 入力データの保持 圧縮処理 ソースファイル 圧縮データ モジュール名 Mem Loop Out total 処理内容 入力データの保持 圧縮処理 圧縮情報を出力 - スライス数 303~3479 2147 1482 7108
ハード・ソフト最適分割について 分割案 回路規模とSW負荷 7108 - 3479 39 2147 60 1482 1 関数のCPU負荷割合 ハードウェア規模 （スライス数） SW実行時の 負荷割合（％） Total 7108 - Mem 3479 39 Loop 2147 60 out 1482 1 分割案 分割パターン ハードウェア処理 ソフトウェア処理 A Loop,Out Mem B Loop Mem,Out C Loop,Mem Out D Loop,out 関数のCPU負荷割合
まとめ 今後の課題 LZ圧縮のハードウェア回路、ソフトウェアを作成 ハードウェア化で40倍の高速化 回路規模・処理速度のトレードオフを考慮した分割案の検討 分割して設計する場合、メモリの役割は最初からソフトで設計するのが良い 今後の課題 FPGA上での動作検証、正確な速度を測定する