Alpha Systems Inc. · TSE:4719

Alpha Systems — Technical Presentation (March 2005)

28 slides from Alpha Systems's technical presentation, Mar 2, 2005

  1. Slide 1: ブロックソート法を用いた圧縮ループバックブロックデバイスの実装と評価

    ブロックソート法を用いた 圧縮ループバックブロックデバイスの 実装と評価 北川 健司† 丹 英之† 千葉 大作† 須崎 有康‡ 飯島 賢吾‡ 八木 豊志樹‡ 株式会社 アルファシステムズ† 独立行政法人 産業技術総合研究所‡ 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 1/22

  2. Slide 2: 発表の流れ

    発表の流れ KNOPPIXとは？ 研究目的 圧縮ループバックブロックデバイスとは？ (cloop： Compressed Loopback Blockdevice) 実装･評価 今後の展開/検討事項 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 2/22

  3. Slide 3: KNOPPIXとは？

    KNOPPIXとは？ CDブート可能なDebian GNU/Linux AutoConfigにより、デバイス自動認識・設定が 優れている 圧縮ループバックブロックデバイス(cloop)により 膨大なファイルを１CDに格納 CD起動のため、作成したファイルは、 外部メディアやリモートホストに保存 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 3/22

  4. Slide 4: KNOPPIXの使用例

    KNOPPIXの使用例 テンポラリなLinux OSの使用 環境を統一した多人数教育 HDDトラブルから重要ファイルの救済 自分専用のカスタマイズCDの作成 ユーザは多数のアプリケーションを希望 でも、 メディアサイズは有限(CD700MB) 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 4/22

  5. Slide 5: 研究目的

    研究目的 限られた記録媒体に、より多くの情報を詰めたい 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 5/22

  6. Slide 6: KNOPPIXの仕組み

    KNOPPIXの仕組み 圧縮ファイル 圧縮ファイル 圧縮 圧縮ファイル ファイル ＝ 圧縮ファイル 圧縮 圧縮ファイル ファイル ファイル ＝ cloopファイル ファイル cloopファイル 圧縮ファイル して参照 /KNOPPIX/KNOPPIX を伸 張 イ ル ファ 圧縮 bootloader 圧縮ファイル 圧縮ファイルを ファイルを読み込むことで miniroot ・メディアサイズ以上 メディアサイズ以上の 以上のファイルを ファイルを格納 ・CDドライブの ドライブの読み込み速度を 速度をカバー kernel ルートファイルシステムの ルートファイルシステムの 必要最低限の 必要最

  7. Slide 7: 圧縮ループバックブロックデバイスとは？

    圧縮ループバックブロックデバイス†とは？ （†cloop： Compressed Loopback Blockdevice ） 圧縮ループバックブロックデバイス ＝ 圧縮機能 ＋ ループバックブロックデバイス ループバックブロックデバイス ファイルをHDDのように扱う機能を提供 つまり、 圧縮されたファイルをファイルシステムとして マウントできる機能を提供 ただし、cloopファイルは読込み専用 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 7/22

  8. Slide 8: cloopの圧縮の流れ

    cloopの圧縮の流れ 1.8GB のファイルを CD700MBに格納 圧縮前 圧縮前 圧縮後 圧縮後 /KNOPPIX/KNOPPIX bin bootloader boot ・・・ miniroot / cdrom ブロックサイズ ファイル cloopファイル ファイル cloopファイル kernel ・・・ 64KB ブロックサイズ 単位で圧縮 現在の 現在の 現在 現在の ：：cloopの のKNOPPIX： KNOPPIX： の の圧縮アルゴリズム cloopの 圧縮アルゴリズムは 圧縮 アルゴリズムは アルゴリズム 圧縮アルゴリズム アルゴリズムは 法 はLZ法 法 LZ法 情報

  9. Slide 9: cloopの伸張の流れ

    cloopの伸張の流れ Kernel CD Loopback file cloop file 圧縮後 圧縮後 伸張後 伸張後 System call ext2fs sys_read( ) etc... ・・・ page cache ・・・ CDから読込む ページキャッシュ 必要なブロック になければ だけ伸張 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 9/22

  10. Slide 10: KNOPPIXへの実装(1/2)

    KNOPPIXへの実装(1/2) 圧縮アルゴリズムに着目 法より圧縮率の高いブロックソート LZ法 ブロックソート法 ブロックソート法を利用 (zlib) (libbzip2) libbzip2 (bzip2-1.0.2) LKM zlib (advancecomp-1.9_create_compressed_fs) cloop-2.01 kernel2.6.8.1 KNOPPIX3.6日本語版 (knoppix_v3.6_20040816-20040914) zlibとlibbzip2を判断して伸張するLKM††を作成 (†LKM： Linux Kernel Module) 情報処理学会 第

  11. Slide 11: KNOPPIXへの実装(2/2)

    KNOPPIXへの実装(2/2) 情報圧縮では、読込系列が長くなるにつれて 圧縮率が情報源のエントロピーに漸近する ブロックサイズに着目 ブロックサイズを変更 （64,128,256,512KB） アルゴリズム(2種)とブロックサイズ(4種)を それぞれ変更したCD8枚を作成 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 11/22

  12. Slide 12: 評価

    評価 測定項目 実験環境 圧縮率 CPU ： Pentium III 933MHz CDからの読込時間 RAM ： 256MB(PC100) ブロックの伸張時間 CDドライブ ： 24倍速 (時間計測にjiffies†を利用) 測定作業 KDE ・・・ デスクトップ環境,PC起動からKDE起動完了まで OpenOffice.org ・・・ オフィススィート,文書ファイル表示 Mozilla ・・・ Webブラウザ,初期画面表示 ： 1ms(kernel2.6)の († jiffies： のタイマー割 タイマー割り込みでインクリメント みでインクリメントされる インクリメントされる値 される値

  13. Slide 13: 測定結果：圧縮率(1/2)

    測定結果： 圧縮率(1/2) 圧縮前の 圧縮前のサイズ ファイル数：93,485 合計サイズ：1,923MB 現在の 現在のKNOPPIXの の実装 圧縮率 block size (KB) 64 128 256 512 zlib (%) 36.46 36.02 35.81 35.70 libbzip2 (%) 35.20 34.24 33.48 32.89 圧縮後のサイズ(MB) 圧縮率（%）＝ ×100 圧縮前のサイズ(MB) 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 13/22

  14. Slide 14: 測定結果：圧縮率(2/2)

    測定結果： 圧縮率(2/2) 圧縮前の 圧縮前のサイズ ファイル数：93,485 合計サイズ：1,923MB 現在の 現在のKNOPPIXの の実装 圧縮後の 圧縮後のサイズ block size (KB) 64 128 256 512 zlib (MB) 669 661 657 655 libbzip2 (MB) 646 628 614 604 差分 23 33 43 51 圧縮後：65MB削減 圧縮前：200MB相当 同じ容量のメディアを用いる場合、より多くの アプリケーションをインストールできる 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems I

  15. Slide 15: 測定結果：伸張時間

    測定結果： 伸張時間 現在の 現在のKNOPPIXの の実装 圧縮率の向上により 読込時間の短縮 圧縮率と伸張時間はトレードオフの関係 伸張時間がボトルネックとなった 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 15/22

  16. Slide 16: 伸張時間削減のための検討

    伸張時間削減のための検討 同じブロックが何回も呼ばれると仮定 読み込みブロック数の半数が 2回以上呼ばれていた キャッシュを設けてブロック伸張の回数を 減らすことで伸張時間を削減できないか？ 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 16/22

  17. Slide 17: キャッシュの導入

    キャッシュの導入 Kernel CD Loopback file cloop file 圧縮後 圧縮後 伸張後 伸張後 ext2fs ・・・ page cache キャッシュ ・・・ ページキャッシュ 一度伸張したブロックを になければ キャッシュする（LRU†) 次回の読み出しに利用 （†LRU： Least Recently Used ） 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 17/22

  18. Slide 18: キャッシュ(LRU，16MB)の有無による測定

    評価 キャッシュ(LRU，16MB)の有無による測定 測定項目 実験環境 CDからの読込時間 CPU ： Pentium III 933MHz ブロックの伸張時間 RAM ： 256MB(PC100) (時間計測にjiffies†を利用) CDドライブ ： 24倍速 測定作業 KDE ・・・ デスクトップ環境,PC起動からKDE起動完了まで ： 1ms(kernel2.6)の († jiffies： のタイマー割 タイマー割り込みでインクリメント みでインクリメントされる インクリメントされる値 される値 ) 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha syste

  19. Slide 19: 測定結果：キャッシュの効果(1/2)

    測定結果：キャッシュの効果(1/2) キャッシュ無しに比べ 伸張時間を約46%削減 キャッシュ（LRU）により伸張時間を約半分に削減 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 19/22

  20. Slide 20: 測定結果：キャッシュの効果(2/2)

    測定結果：キャッシュの効果(2/2) 現在の 現在のKNOPPIXの の実装 合計時間は増加したが、200MB相当 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 20/22

  21. Slide 21: まとめ

    まとめ 今回、ブロックソート法(libbzip2)を用いたcloopの 実装を行い、高圧縮KNOPPIXの評価を行った 圧縮率 現状のKNOPPIXのアルゴリズムの変更だけで２１MB削減 アルゴリズムとブロックサイズを変更すると65MB削減 伸張時間 アルゴリズムとブロックサイズに応じて増加したが、 キャッシュ（LRU）の実装により約半分に削減 今までより200MB相当のアプリケーションが追加可能 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 21/22

  22. Slide 22: 今後の展開/検討事項

    今後の展開/検討事項 バイトコストの高いメディア(CF,USB-key)， 低帯域ネットワークでのSFS-KNOPPIXの使用に有効では？ 伸張時間の高速化 他のアルゴリズムやメディアについて検討 アプリケーションやデータの使用率に応じて そのファイルの圧縮アルゴリズムを選択する 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc. 22/22

  23. Slide 23: ご清聴ありがとうございました。

    ご清聴ありがとうございました。 デモセッション会場 B棟 1F 玄関ホール にて無料配布中！！ 是非、お立ち寄りください。 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc.

  24. Slide 24: (c) Alpha systems Inc.

    情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc.

  25. Slide 25: おまけ(1/2) アルゴリズムの違いによる圧縮率の変化

    おまけ(1/2) アルゴリズムの違いによる圧縮率の変化 圧縮率が上がらない CD読込がボトルネックになる ＊アルゴリズムの アルゴリズムの違いによる圧縮率 いによる圧縮率の 圧縮率の変化 680 680 zlib 660 圧縮後のサイズ (MB) 660 640 640 libbzip2 620 620 600 600 580 580 560 560 64 128 256 512 ブロックサイズ (KB) 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc.

  26. Slide 26: おまけ(2/2)

    おまけ(2/2) ブロックソート法の伸張処理はCPUを消費するため、高スペックPCでも実験を行った libbzip2 PC_A PC_A PC_B PC_B 読込時間より伸張時間 PC_A PC_B の方が短縮の割合が CPU PentiumIII 933MHz Pentium4 3.2GHz 高かった RAM 256MB(PC100) 2.5GB(PC3300) CDドライブ 24倍速 48倍速 CPU性能の更なる向上により、伸張時間には 十分な速度が見込める 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc.

  27. Slide 27: SFS-KNOPPIX

    SFS-KNOPPIX 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc.

  28. Slide 28: 圧縮アルゴリズム

    圧縮アルゴリズム zlib LZ法 bzip2 ブロックソート法（バロウズ-ホイラー変換） MTF (Move-To-Front) 法 ハフマン符号化法 情報処理学会 第67回全国大会 (2005.3.2) (c) Alpha systems Inc.

Alpha Systems — Technical Presentation (March 2005) on 6ix