データストリーム伝送路におけるロスレス圧縮技術の開発

【研究概要】

通信・映像・センサといった情報源が発するデータ量の爆発的な増加に伴い、データ伝送路に超高周波での実装が要求され、困難を極める状況にある。一定のデータ塊を単位として圧縮・復号するブロッキング圧縮によるデータ量の削減は従来から行われているが、常に流れ出る高速データ源では処理が間に合わず破綻する。伝送路で直に圧縮できればよいがハードウェアで効果的に実装できる技術がない。そこで、本研究は伝送路に流れるデータの出現統計をリアルタイムに生成し、圧縮・復号するストリーム圧縮ハードウェア技術を開発する。この技術は伝送路の物理的容量限界を超えたデータ伝送が可能な高信頼コンピューティングへの基盤技術の確立を狙う。Read More

１．研究背景

産業界では、データ伝送路に流れるデータ量の爆発的増加に対応する圧縮技術が必要とされている。PCI Express、HDMI、USBといったデータ伝送路標準はGHzに達する勢いで、それを実装するプリント基板製造の現場では複数パターンを設計し、その中から期待通りに動作するものを採用するといった非科学的開発手法を採用するまでにデータ伝送路の実装は困難を極めている。実装技術を複雑化せず転送量を増加させるには、伝送路に流れるデータを圧縮し、周波数や伝送量を減少させ、実装を簡単化するハードウェアでの圧縮技術の開発が喫緊の課題である。

その一方で、既存の圧縮技術をブロッキング圧縮からストリーム圧縮へ技術シフトを急ぐ必要がある。つまり、これまで、メモリにデータを溜めて圧縮・複合を実行するブロッキング圧縮は行われてきたが、データ伝送路の帯域が増加すると破綻する。さらに、ハードウェアで高速化しても、伝送路の性能向上に比例した回路の高速化を余儀なくされ、性能の“いたちごっこ”に陥り、技術破綻を予想できる。従って、伝送路の性能に比例したデータの高濃度化を実現できるストリーム圧縮に技術をシフトする必要があるが、ハードウェアにスケーラブルな実装が可能な技術が未踏である。データ圧縮は最頻出で最長のデータ列（シンボル列と呼ぶ）をデータの中から探し、それを単一のデータ（シンボル）に置き換えて情報量を削減するが、従来法を使うと１）シンボル列抽出処理時間予測が不可、２）シンボル変換テーブルサイズが予測不可、３）テーブルを復号側へ送信するオーバヘッド、４）テーブル自体が圧縮率を低下、という問題によって、圧縮・復号処理を伴ったデータ伝送を連続的に実行できない。

２．研究の目的

以上の背景から、本研究では、データ伝送路に流れるデータをリアルタイムに圧縮するストリーム圧縮技術の開発を目的として。本研究で扱うデータは区切りがない連続したデータである。従って、シンボル変換テーブルを送るタイミングがない。そこで、リアルタイムに圧縮側と復号側で同じテーブルを保持し、圧縮・復号を行う必要がある。これをハードウェアのデータ伝送路に組み込むために本研究は、少ないリソースで、かつ、高速に動作できる、ハードウェア化が可能な、１）ストリームデータ伝送路でのリアルタイム圧縮・復号機構をもった通信プロトコルと、２）リアルタイムにデータ出現頻度をランキングするシンボル変換テーブル更新機構の開発を目指した。これらの処理をハードウェアでスケーラブルに実施するためには、固定長のシンボル列をテーブルに登録し、さらに、テーブル容量が飽和した場合に最も使われていないシンボル列の規則を入れ替える方式を開発できれば良いことはわかっていた。このような動的管理方式によって、伝送路に流れる時々刻々と出現率が変化するデータであっても、伝送路中のデータ量の高濃度化を実現でき、伝送路のピーク性能を超えるストリーム圧縮ハードウェアが実装できる。

データストリームの統計的傾向が変化しても高い圧縮率を維持するシステムを開発するために、１）シンボルテーブル更新を可能にする通信プロトコルの開発、２）データストリームの統計的傾向を求めるアルゴリズムの開発、３）アプリケーションの開発、の３つの大テーマに分けて実施した。１）に関しては、初年度に実施し、アルゴリズムの開発とその実装方法に関して議論を重ね、ソフトウェアとハードウェアでの施策を行なった。

３．研究成果

上記の研究の背景で説明した従来からのデータ圧縮における問題点を克服する、無限に続くデータストリームに適用でき、さらに、ハードウェアで高速動作させることが可能な新しい方式LCA -DLTを提案し、ハードウェア、ソフトウェアの両面で良好な性能を示すことが出来た。この圧縮方式では、図１のように、①２つの単位データを１つに圧縮するモジュールを用意し、②そのモジュールが動的に変換テーブルを作り、③圧縮されたデータの構造に②のテーブルの作成手順を隠し持つことで、④解凍側で同一の変換テーブルを復元し、データを元に戻す。この技術では、変換テーブルを解凍側に送る必要がなく、圧縮されたデータストリームを受信し始めると、次々と解凍を行う事ができる。つまり、最初のデータが圧縮されると、そのデータは次々と解凍側に渡されて、解凍側はそれらを順次、データ構造から連想される変換テーブルを復元し、解凍していく。従って、ストリームでの圧縮・解凍処理が可能である。

さらに、圧縮モジュールは２データ→１データの圧縮であるため、５０％しか圧縮出来ない。そのモジュールをカスケード接続することで、４段の場合、最大で１/１６＝２５％まで理論的には圧縮できるユニバーサル性を持つ革新的な圧縮方式を開発することが出来た。本研究の学術的な意義として、これまで、メモリに保持したデータをプロセッサがランダムアクセスすることによるデータ圧縮方式のみが主流であったが、データストリームのようなランダムアクセスが不可能である特徴を持つデータ生成環境（例えば、センサのデータなど）においても適用できる新しいアルゴリズムが実現できることが証明でき、今後、ストリームデータ圧縮という新しい学術分野を期待できる。

Research articles in Journals and Magazines

Shinichi Yamagiwa, Koichi Marumo, Suzukaze Kuwabara. Exception Handling Method Based on Event from Look-Up Table Applying Stream-Based Lossless Data Compression, Electronics, 240, (2021-01-21), DOI:10.3390/electronics10030240
Koichi Marumo, Shinichi Yamagiwa, Ryuta Morita, Hiroshi Sakamoto. Lazy Management for Frequency Table on Hardware-Based Stream Lossless Data Compression, Information, 63, (2016-10-31), DOI:10.3390/info7040063

Conference Proceedings

Shinichi Yamagiwa, Ryuta Morita, Koichi Marumo. Reducing Symbol Search Overhead on Stream-Based Lossless Data Compression, ICCS 2019: Computational Science, 619--626, (2019-06-08), DOI:10.1007/978-3-030-22750-0_59
Shinichi Yamagiwa, Ryuta Morita, Koichi Marumo. Bank Select Method for Reducing Symbol Search Operations on Stream-Based Lossless Data Compression, 2019 Data Compression Conference (DCC), , (2019-03-26), DOI:10.1109/dcc.2019.00123
Koichi Marumo, Shinichi Yamagiwa. Time-Sharing Multithreading on Stream-Based Lossless Data Compression, 2017 Fifth International Symposium on Computing and Networking (CANDAR), , (2017-11-19), DOI:10.1109/candar.2017.42
Shinichi Yamagiwa, Koichi Marumo, Hiroshi Sakamoto. Stream-Based Lossless Data Compression Hardware Using Adaptive Frequency Table Management, In proceedings of Big Data Benchmarks, Performance Optimization, and Emerging Hardware. BPOE 2015. Lecture Notes in Computer Science Vol. 9495, 133--146, (2016-01-09), DOI:10.1007/978-3-319-29006-5_11
Shinichi Yamagiwa, Hiroshi Sakamoto. A reconfigurable stream compression hardware based on static symbol-lookup table, 2013 IEEE International Conference on Big Data, , (2013-10-06), DOI:10.1109/bigdata.2013.6691702

受賞、報道

（受賞）大学発ベンチャー表彰「科学技術振興機構理事長賞」受賞名：ストリームデータ圧縮技術〜Data Copression3.0〜（２０１８年８月）
（受賞）常陽ビジネスアワード最優秀賞（成長事業部門）「Data Compression3.0〜新ロスレスデータ圧縮技術がつくるスマートライフのためのテクノロジ〜」（２０１６年５月）
（受賞）Embedded Technology Award 2015「特別賞」（受賞技術：高性能ストリームデータ圧縮技術〜ストリームを高速にコンパクトに。未来のロスレス圧縮のカタチ）（一般社団法人　組込みシステム技術協会）（２０１５年１１月）
（受賞）Best Paper Award（VLDB2015/BPOE-6）（２０１５年９月）Shinichi Yamagiwa, Koichi Maruo and Hiroshi Sakamoto, Stream-based Lossless Data Compression Hardware using Adaptive Frequency Table Management, In Proceedings of VLDB2015/BPOE-6, pp.133-146, Springer, Sep 2015.）　
（報道）常陽新聞２０１５年８月２７日「新方法のデータ圧縮開発」筑波大准教授山際伸一さんら　様々な機器に実装可能

獲得予算

（科研費）基盤研究B　代表, “データストリーム伝送路におけるロスレス圧縮技術の開発”, 2015-2018, （研究代表者　山際伸一）

【研究概要 】