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