(57)【要約】  命令コードおよびデータの両方を柔軟に圧縮することができる組込みシステム・アーキテクチャが開示される。
2008503922.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサと、
メモリ・ユニットと、
前記メモリ・ユニットと前記プロセッサの中の任意のキャッシュの間に置かれたバッファおよび圧縮エンジンとを有し、前記バッファは、前記圧縮エンジンによって効率的に圧縮されるのに十分に大きなサイズを有する１つまたは複数の非圧縮フレームを格納し、非圧縮フレームの少なくとも一部が圧縮されたフォーマットで前記メモリ・ユニットに格納されている、システム。
【請求項２】
バッファ・ミスがあれば、前記メモリ・ユニットに格納された圧縮されたフレームを復元エンジンによって復元して前記バッファに置くことができる、請求項１に記載のシステム。
【請求項２】
前記バッファは、非圧縮コードと非圧縮データの両方を格納する一体化されたバッファである、請求項１に記載のシステム。
【請求項３】
前記バッファは、非圧縮コードのための第１の独立したバッファと、非圧縮データのための第２の独立したバッファとをさらに有する、請求項１に記載のシステム。
【請求項４】
前記圧縮エンジンは、コードを圧縮するためと、データを圧縮するためとで、異なる圧縮アルゴリズムを使用する、請求項３に記載のシステム。
【請求項５】
前記圧縮エンジンは、圧縮された各フレームを前記メモリ・ユニットに格納された一定サイズの複数のサブフレームに細分割する、請求項１に記載のシステム。
【請求項６】
圧縮されたフレームを前記メモリ・ユニットに格納された前記一定サイズのサブフレームに関連づけるマッピング・テーブルをさらに有する、請求項５に記載のシステム。
【請求項７】
前記圧縮エンジンは、辞書ベースのアルゴリズムを使用し、かつランレングス符号化を含んでいる、請求項１に記載のシステム。
【請求項８】
前記システムは、組込みシステムである、請求項１に記載のシステム。
【請求項９】
一定サイズのフレームをメモリ内の一定サイズの境界上にそろえられた複数のサブフレームの位置に関連づけるエントリをさらに有するマッピング・テーブルを有し、前記一定サイズのフレームは、可変サイズの圧縮されたフレームに圧縮され、圧縮されたフォーマットでメモリに格納される前に前記複数のサブフレームに細分割される、圧縮されたメモリ・アーキテクチャ。
【請求項１０】
フレームが、コードまたはデータを収容することができる、請求項９に記載の圧縮されたメモリ・アーキテクチャ。
【請求項１１】
空きスペースが、メモリ内の一定サイズの境界上にそろえられた未使用のサブフレームの位置に対する一連のポインタを使用して追跡される、請求項９に記載の圧縮されたメモリ・アーキテクチャ。
【請求項１２】
圧縮されたメモリ・システム設計の方法であって、
圧縮されたメモリと任意のプロセッサ・キャッシュの間に置かれた圧縮バッファの初期サイズを選択することと、
前記圧縮バッファの前記サイズを性能飽和点に到達するまで大きくすることと、
前記圧縮バッファの前記サイズを少なくとも１つの予め定められた制約が満たされるまで小さくすることと、
を有する方法。
【請求項１３】
フレーム・サイズを性能飽和点に到達するまで大きくするステップをさらに有する、請求項１２に記載の方法。
【請求項１４】
サブフレーム・サイズ、バッファ置換ポリシー、コードまたはデータのための一体化されたまたは個別のバッファ・アーキテクチャ、および、異なる圧縮アルゴリズムからなるグループから選択された異なるパラメータ同士を比較するステップをさらに有する、請求項１２に記載の方法。
【請求項１５】
各フレームが一定数のサブフレームに細分割され、各フレームを前記一定数のサブフレームのメモリ内の位置に関連づけるためにマッピング・テーブルが使用される、複数のフレームを格納するようになっているランダム・アクセス・メモリと、
一定サイズのフレームを可変長の圧縮されたフレームに圧縮するように前記メモリに接続され、可変長の圧縮された各フレームは、サブフレームの前記一定数に等しいかまたはこれよりも小さい数のサブフレームに格納され、前記マッピング・テーブルを使用して索引付けられる圧縮器と、
を有する、組込みシステム・アーキテクチャ。
【請求項１６】
フレームが命令コードまたはデータを含むことができる、請求項１５に記載の組込みシステム・アーキテクチャ。
【請求項１７】
各サブフレームは、前記メモリ内の一定サイズの境界上にそろえられている、請求項１に記載の組込みシステム・アーキテクチャ。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願
本出願は、同時係属出願の同一出願人による米国特許出願、“ダイナミックでコンテント・アウェア（ＣＯＮＴＥＮＴ−ＡＷＡＲＥ）なメモリ圧縮および暗号化アーキテクチャ”、代理人整理番号０３０４１−Ｂ、出願番号未定、および、“メモリ暗号化アーキテクチャ”、代理人整理番号０３０４２、出願番号未定、に関するものであり、これら両出願は、本出願と同時に出願され、参考文献としてこの中に含まれている。
【０００２】
発明の背景
本発明は、メモリ・アーキテクチャに関し、特に、組込みシステムにおけるメモリの圧縮のためのアーキテクチャに関する。
【背景技術】
【０００３】
圧縮技術が良く知られている。最近の動向としては、コンピュータ・アーキテクチャにおけるメイン・メモリのサイズを小さくするために圧縮技術が使用されている。例えば、Ｍ．Ｋｊｅｌｓｏ他、“メイン・メモリ・ハードウェア・データ圧縮”、２２ｎｄ  Ｅｕｒｏｍｉｃｒｏ  Ｃｏｎｆｅｒｅｎｃｅ、４２３−３０ページ、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙ  Ｐｒｅｓｓ（Ｓｅｐｔ．１９９６）を参照されたい。例えば、ＩＢＭの研究者は、Ｌ３キャッシュからメイン・メモリへデータを転送する場合またはその逆の場合に、アプリケーションのランタイム中に圧縮および復元を行う“ＭＸＴ”アーキテクチャをサーバ用に開発した。Ｔｒｅｍａｉｎｅ他、“ＩＢＭメモリ拡張技術（ＭＸＴ）”、ＩＢＭ  Ｊ．Ｒｅｓ．＆Ｄｅｖ．、Ｖｏｌ．４５，Ｎｏ．２（Ｍａｒｃｈ  ２００１）を参照されたい。また、参考文献としてこの中に含まれている米国特許第５７６１５３６号、第５８１２８１７号、および第６２４０４１９号を参照されたい。
【０００４】
組込みシステムの設計においては、ハードウェア・サイズを小さく保ちつつ、複雑な機能が要求されるのが現在の傾向になっている。携帯電話やディジタル・カメラのような装置が小さくなればなるほど、組込みシステムの設計者は、メモリ圧縮技術によって、少ないスペースに多くの機能を詰め込むことが可能となる。組込みメモリ圧縮の以前の研究は、一般に、実行可能なコードの命令部分を実行前に圧縮し、ランタイム中に復元することに集中していた。例えば、Ｌ．Ｂｅｎｉｎｉ他、“組込みシステムにおけるメモリ・エネルギー縮減のための選択的な命令圧縮”、ＩＥＥＥ／ＡＣＭ  Ｐｒｏｃ．  ｏｆ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｌｏｗｅｒ  Ｐｏｗｅｒ  Ｅｌｅｃｔｒｏｎｉｃｓ  ａｎｄ  Ｄｅｓｉｇｎ（ＩＳＬＰＥＤ  ‘９９）、２０６−１１ページ、（１９９９）を参照されたい。残念なことに、発明者は、単なる命令部分の圧縮では、多くの場合に、追加圧縮ハードウェアの使用を保証するのに十分なメモリ削減をもたらすものではないと認識している。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
そのため、現在までに利用可能な解決策は、コードおよびデータを同時に処理しないこと、または、組込みシステムの分野で実行可能な解決策を提供しないことである。したがって、コードおよびデータの両方の圧縮を柔軟かつ効率的な方法で処理することが可能な、組込みシステムのための一体化されたアーキテクチャが必要である。
【課題を解決するための手段】
【０００６】
発明の概要
本発明は、命令コードおよびデータの両方の圧縮を効率的な方法でサポートできるシステム・アーキテクチャを導くものである。本発明の実施形態によれば、バッファおよび圧縮エンジンは、プロセッサ内の任意のメモリ・キャッシュとメイン・メモリの間に置かれており、バッファは、圧縮エンジンによって効率的に圧縮されるのに十分に大きなサイズを有する１つまたは複数の非圧縮フレームを格納し、そのフレームは圧縮されたフォーマットでメイン・メモリに格納される。バッファ・ミスがあれば、メモリ・ユニットに格納された圧縮されたフレームを復元してバッファに置くことができる。コードまたはデータのどの圧縮されたフレームも、都合の良いことに、従来のキャッシュ・ラインよりも大幅に大きく、高レベルな圧縮を可能にするのに十分に大きい。アーキテクチャは、コードまたはデータのための一体化されたバッファ、または、コードのための個別のバッファおよびデータのための個別のバッファを利用することができる。アーキテクチャは、都合の良いことに、プロセッサの設計から独立し、または、利用されるキャッシング階層（ハイアラーキー）があったとしても、これから独立している。さらに、都合の良いことに、コードおよびデータのための個別の圧縮アルゴリズムを含む任意の圧縮アルゴリズムが利用できる。
【０００７】
本発明の他の態様によれば、メイン・メモリ内のメモリ断片化は、バッファから読み出された一定サイズのフレームを圧縮し、圧縮されたフレームをランダム・アクセス・メモリに格納された一定サイズの多数のサブフレームに細分割することにより行われる。各サブフレームは、メモリ内の一定サイズの境界上にそろえるのが望ましい。圧縮されたフレームの各サブフレームの位置は、マッピング・テーブル内に容易に保持できる。ポインタの構造は、ランダム・アクセス・メモリ内の空きスペースを追跡するために使用できる。
【０００８】
本発明は、特に、多様な組込みシステム・アーキテクチャで機能し得る柔軟でかつ特有な設計を提供する。本発明の他の態様によれば、システム設計者が、都合良く、バッファ・サイズ、フレーム・サイズ、サブフレーム・サイズ、バッファ・ミス・ポリシー、および圧縮アルゴリズムを含む特定のアプリケーションに適合するように、システムの多様な異なるパラメータを調整可能にする、設計スペース検証手順が開示される。
【０００９】
本発明は、都合の良いことに、命令コードおよびデータの両方を効率的に圧縮することができ、圧縮の高速化を実現するためのメモリ・キャッシングを必要としない。都合の良いことに、圧縮モジュールは、オペレーティング・システム内の圧縮サポートが利用できないシステムにも備えることができる。アーキテクチャは、組込みコード圧縮に対する異なる方法の試験にも有用である。本発明を具体化する組込みシステムは、従来技術で可能であったものよりも複雑なアプリケーションを実行するが、その一方で、場合によっては少ないメモリしか必要としない。この結果、低コストで高品質のシステムがもたらされる。本発明のこれらのおよび他の利点は、当業者であれば、下記の詳細説明と添付図面を参照することによって明白になるであろう。
【発明を実施するための最良の形態】
【００１０】
詳細な説明
図１は、本発明の態様の実施形態により組み込まれたシステムに使用可能なメモリ階層の各種レベルを示す図である。中央処理装置（ＣＰＵ）１１０は、図１に示されており、１つまたは複数のレベルのキャッシング１２０を有してもよく、有していなくてもよい。キャッシュ１２０は、命令および／またはデータ・キャッシュとすることができる。ここで開示されるメモリ圧縮アーキテクチャは、都合の良いことに、特定のＣＰＵおよび利用されるキャッシング階層から独立していることに注目すべきである。この方法は、キャッシングのどのようなレベルを要求することも前提とすることもせず、キャッシュが一切ないシステムでも容易に実現可能である。説明のために、このシステムには仮想メモリが備えられていないと仮定する。
【００１１】
複数レベルのメモリ階層を備える既存のアーキテクチャは、通常は、性能に着目して設計されてきた。コードに加えてデータを圧縮するための顕著な性能オーバー・ヘッドがあると仮定すると、ＣＰＵから離れたメモリ階層レベルで圧縮および復元を行うことが一般には有利である。この方法は、例えば、Ｌ３キャッシュとメイン・メモリの間で圧縮が生ずる、上述した従来技術のＭＸＴアーキテクチャで採られている方法である。しかし、組込みシステムにおいては、メモリ階層の層は、通常は（たとえ存在するとしても）僅かしか存在しないため、システム・アーキテクチャの設計者は、ＣＰＵの近くで圧縮／復元することを余儀なくされていた。キャッシュを内蔵するシステムを仮定すると、メモリ圧縮に対処する簡単な方法は、キャッシュ・ライン・レベルで圧縮を行うことであろう。キャッシュ・ミスが起きる度に、圧縮されたキャッシュ・ラインは、メモリから取り出され、復元されてキャッシュに置かれるであろう。しかし、キャッシュ・ラインは、通常、効率的に圧縮するにはあまりにも小さいので、ここでは、この方法は実際には十分に機能しないと考えられる。これは、特に、キャッシュ・ラインが、他のキャッシュ・ラインからの一切の統計情報を使用せずに圧縮される場合であり、本発明はその場合に該当する。例えば、本発明者は、３２バイトのキャッシュ・ラインについては、通常、サイズの削減は元のキャッシュ・ライン・サイズの１〜３パーセントであり、一方、６４バイトのキャッシュ・ラインについては、圧縮比率は元のキャッシュ・ライン・サイズの５〜１０パーセントの範囲にあることを見出した。これらの圧縮比率は、圧縮／復元ハードウェアの使用を保証するのに充分な圧縮を何らもたらすものではない。広く統計をとれば、小さなサイズのキャッシュ・ラインが、より効率的に圧縮され得ることに注目されたい。しかし、本発明の場合には、これは、本発明のシステムを非普遍的とし、他のアプリケーションでは実際に発見されない可能性のあるデータの統計値の特定に関係するので、非実用的である。
【００１２】
他方、本システムは、メモリ削減に着目して設計されているので、圧縮されたブロックはキャッシュ・ラインよりも実質的に大きくなり得る。図１に示すように、本発明の態様の実施形態によれば、復元されたコードまたはデータの１つまたは複数のバッファ・ライン１５１，１５２，１５３等を保持するバッファ１５０が設けられている。ここで、バッファライン・サイズは、都合の良いことに、高レベルの圧縮が可能となるように、十分に大きくなっている。バッファ１５０は、プロセッサ１１０とメイン・メモリ１３０の間に置かれている。
【００１３】
図１には、コードおよびデータのための一体化された１つのバッファ１５０が示されているが、本発明はそれに限定されないことに注目すべきである。ここでさらに説明するように、別の実施形態は、コードのための個別のバッファとデータのための個別のバッファを有している。
【００１４】
バッファ１５０のバッファ・ライン１５１，１５２，１５３は、データのフレームを格納しており、このフレームは、復元されたフォーマットであり、メイン・メモリ１３０に格納される前に圧縮エンジン１６０を使用して圧縮されたものである。バッファ１５０は、バッファ・ライン１５１，１５２，１５３の状態を追跡するメカニズムを保持している。例えば、各バッファ・ライン１５１，１５２，１５３は、当該技術分野において“ダーティー”ビットと呼ばれるものを収容することができる。“ダーティー”ビットは、バッファ・ラインが変更されたか否か、および、書き戻しが必要か否かを示している。ダーティー・ビットは、バッファ１５０に挿入された何らかの新しいデータが存在する場合に設定される。ダーティー・データは、補充の必要がある新しいデータがなければ、圧縮してメモリ１３０に書き戻す必要はなく、また、古いデータは、メモリ１３０に再び書き戻されなければならない。バッファ“ミス”が発生すると、圧縮されたフレームがメモリ１３０から検索され、復元エンジン１６０を使用して復元され、バッファ１５０の１つまたは複数のバッファ・ラインに置かれる。新しいバッファ・ラインがバッファ１５０を占有する必要があるとき、既存のバッファ・ラインの内容を立ち退かせなければならない場合がある。どのバッファ・ラインを立ち退かせるべきかを決める何らかの置換ポリシーを利用することが有利である。例えば、これに限定されないが、置換ポリシーとしては、“ラウンド・ロビン”および“最低使用頻度”（ＬＲＵ）置換ポリシーなどが利用できる。
【００１５】
メモリ管理。メモリ管理には、２つの異なる課題がある。読み取り中に、圧縮されたデータを位置付けることと、書き込み中に、新たに圧縮されたデータを格納する空き位置を検出することである。データ・エリアをフレーム（当該技術分野において、ブロックまたはページとも呼ばれる）に分割し、フレーム・レベルでランダム・アクセスを提供することが重要である。ランダム・アクセスをバイト・レベルやさらにワード・レベルで提供するには、メモリ管理情報を格納するために巨大なメモリを必要とし、実現可能ではない。
【００１６】
したがって、データ・スペースは、ここでは“ページ”と呼ばれる多数のフレームに都合良く分割される。ページは、個々に圧縮されているメイン・メモリの一定数のバイトを参照する。通常、図１に示すように、ページ・サイズは、バッファ・ラインに等しいが、一般的には、バッファ・ラインの倍数でもよい。ページは、１Ｋバイトから１６Ｋバイトの範囲のサイズが望ましい。データを１ＫＢよりも小さいページに分割することは、充分な圧縮比率を達成するのに効果的ではないことが実証されている。ここでは、説明のために、ページ・サイズは１ＫＢであると仮定する。
【００１７】
圧縮後には、圧縮されたページの各々は、元のページよりも少ないスペースを占めるであろう。圧縮が何らのサイズ削減をもたらさないような稀な場合には、ページは元の形式で格納することができる。そのため、一般的な場合には、１ＫＢのページは、１ＫＢ以下の何らかのサイズに圧縮される。この可変サイズによって、圧縮されたページの索引付けが著しく複雑になり得る。本発明の別の態様の実施形態によれば、本発明者が“Ｃフレーム”と呼ぶグループに、ページを細分割することが有利である。Ｃフレームは、圧縮されたメモリ内の最小のアドレス可能な単位を表す。圧縮されたページは、Ｃフレーム・サイズの倍数として表される。Ｃフレーム・サイズをより小さくすると、メモリの断片化が減少する。しかし、Ｃフレーム・サイズをより小さくすると、マッピング・テーブルがより大きくなる。説明のために、１ＫＢのページは１６個のＣフレームに都合良く分割され、各Ｃフレームのサイズは６４バイトに設定されているとする。
【００１８】
さらに、各Ｃフレームのブロック・アライメントは規制されている。例えば、６４バイトに設定されたＣフレームについては、すべてのＣフレームは６４バイトの境界上にそろえられている。
【００１９】
メモリ内の圧縮されたページをマッピングするためのテーブルを、図２に示す。各テーブル・エントリ２００は、圧縮されたページに対応し、１６個のＣフレームの位置を格納している。メモリの位置はビット・ポインタ２０１，２０２等として表すことができ、Ｃフレームは６４ビットの境界上にそろえられているので、各ポインタは６４ビットの境界を示している。ページごとに１６ブロックのスペースを割り当てることにより、圧縮比率にかかわらず、どのページもテーブルに格納できることが保証される。他の利点としては、マッピング・テーブルは一定サイズであるため、例えば、ページ・ポインタの第１ビットによって、容易に索引付けをすることができる。そのため、マッピング・テーブルによって、メモリ内の圧縮されたページを検出する手段が提供される。マッピング・テーブルは、圧縮されたデータと共にメモリ内に格納できることに注目されたい。（代替方法では、よく圧縮するページについてはスペースを節約し、１６個のＣフレーム・ポインタについてはスペースを割り当てないであろう。しかし、この方法は、テーブルが一定サイズのエントリを有さず、索引付けがより難しいであろうから、設計を複雑にするであろう。）
メモリへのページの書き戻しを試みる場合に、書き込み中に、空きスペースの位置付けを支援する構造が必要となる。このような構造を図３に示す。図３に示す構造は、空きスペースを示している一連のポインタを有する。この構造は、ＦＩＦＯとして作用し、６４バイトの塊（ｃｈｕｎｋ）の中にブロックできる。空き位置に対するポインタからなる各塊は、６４バイトを占めるため、それ自身６４バイトの空きブロックとみなすことができる。
【００２０】
圧縮アルゴリズム。本発明は、都合の良いことに、何らかの特定の圧縮／復元アルゴリズムに限定されない。設計者は、本アーキテクチャとの関係において、任意の有利な圧縮ＩＰを容易にプラグインすることが可能である。
【００２１】
実行可能なコード圧縮は、通常のデータ圧縮とは異なる複雑な問題であることに注目すべきである。これは、組込みシステムが、通常、スペース制約のために、ランタイム中に圧縮されたデータの部分的な復元を必要とするためである。実行可能なプログラムは、連続して実行されないため、ランダム・アクセス復元が必要となる。圧縮／復元アルゴリズムを選択する場合、データは新たな課題を提起する。コード圧縮のランダム・アクセス要求に加えて、データに関するさらなる問題は、データはメモリへの書き戻しが可能ということである。したがって、圧縮の高速化とメモリ管理技術が必要である。
【００２２】
そのため、圧縮アルゴリズムは、ハードウェアにおける圧縮／復元の高速化を提供し、僅かなハードウェア領域を占有し、バッファ・サイズ・レベルでランダム・アクセス圧縮／復元を提供するものであることが望ましい。１０２４のページ・サイズを仮定すれば、アルゴリズムは、１ＫＢのデータを十分に圧縮することが望ましい。多くのデータ圧縮アルゴリズムでは、有効な統計量を収集するための十分なデータとはならないことに注目すべきである。本発明者は、これらの要求を満たす最高の成果が得られるアルゴリズムの１つが、入力バイトを、ランレングス符号化と呼ばれる技術と組み合わされた辞書と呼ばれるテーブルの中の値と一致させる、ダイナミック辞書技術であることを見出した。辞書技術とランレングス符号化の説明については、参考文献としてこの中に包含される、Ｔ．Ｃ．  Ｂｅｌｌ  および  Ｊ．Ｇ．  Ｃｌｅａｒｙ  および  Ｉ．Ｈ  Ｗｉｔｔｅｎ、“テキスト圧縮”、Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ  （１９９０）を参照されたい。辞書技術は、ハードウェア・インプリメンテーションに特に適しており、本発明者は、このような技術が最も高速であり、かつ、メモリ消費が最少であることを見出した。または、これに限定されないが、２値データを圧縮する場合に特に強力なダイナミック・マルコフ圧縮のバージョンのような他の圧縮技術を利用することが可能である。
【００２３】
設計検証。アーキテクチャの設計は、組込みコード圧縮に対する異なる方法を試験するためのプラットフォームとして役立つ柔軟性を有している。容易に変更可能で構成可能な多様なパラメータを定義することが有利である。設計者は、次に説明するパラメータを使用して、特定のアプリケーションに対して、システムを容易に調整することができる。
【００２４】
ａ．圧縮ＩＰ：本設計は、設計者が任意の圧縮／復元アルゴリズムを“プラグイン”し、それをシミュレートすることを可能にする。シミュレーション環境は、外部のプログラムとして実行可能なものを動作させるために使用できるため、圧縮／復元アルゴリズムについては、単に実行可能なもののみが必要である。
【００２５】
ｂ．コードおよびデータに対する個別の圧縮ソフトウェア。コード・エリアの圧縮は、必ずしもデータ・エリアの圧縮と同じ技術を使用する必要はない。データも書き込まれる必要があり、多くの場合、異なる圧縮方法を必要とする。コードはプログラムの実行中は変化しないので、コードについては、汎用の圧縮モデルを構築することが可能である。この汎用の圧縮モデルを使用して、ページ・レベルで圧縮を行うことが可能であり、各ページを独立して圧縮／復元することが可能である。これにより、コード部分全体から統計値を使用する能力が与えられる。他方、このような方法はデータについては不可能であり、データは実行中に変化するので、汎用の圧縮モデルは意味をなさない。
【００２６】
ｃ．バッファ・サイズ。設計者は、バッファ・サイズを容易に変更することができる。バッファ・サイズをより小さくすると、一般に、必要なエリアが少なくなる。しかし、バッファをより小さくすると、多くのページ・ミスを招くため、性能を悪化させるであろう。そのため、本プラットフォームを使用して容易に実証可能なエリア／性能のトレード・オフの関係がある。
【００２７】
ｄ．ページ・サイズ。ページ・サイズは変更可能な別の重要なパラメータである。ページ・サイズをより小さくすると、コードおよび特にデータの圧縮が困難になる。このことは、上述のようにデータについては汎用の圧縮モデルを構築できないので、コードよりもデータに当てはまり、したがって、ページの圧縮／復元は、残りの部分から完全に独立して行わなければならない。ページ・サイズをより小さい値に設定すると、多くの場合、効率的に圧縮するには１ページの統計情報だけでは不十分である。しかし、ページ・サイズは、任意に大きくすることはできない。ページ・サイズは、バッファ・サイズ以下でなければならず、重大なミス・ペナルティーを招くほどに大きすぎてもいけない。
【００２８】
ｅ．Ｃフレーム・サイズ。Ｃフレーム・パラメータは、主にメモリ断片化に影響を与える。本プラットフォームは、このパラメータの変更を容易にする。
【００２９】
ｆ．バッファ・ミス・ポリシー。ダーティー・バッファ・ライン・ビットが設定される場合、バッファ・ラインは、バッファ・ミス中に置換される（立ち退かされる）。プラットフォームは、異なるバッファ・ミス／置換ポリシーをサポートするように容易なものとすることができる。例えば、これに限定されないが、プラットフォームは、“ラウンド・ロビン”ポリシーをサポートすることができる。新しいバッファ・ラインをバッファに持ち込まなければならない場合、どのバッファ・ラインを立ち退かせるべきかを決定するために、通常はラップ・アラウンド・カウンタを使用して、立ち退かせるべきバッファ・ラインを循環様式で選択する。プラットフォームは、“最低使用頻度”（ＬＲＵ）ポリシーをサポートすることができる。キャッシュによってバッファ・ラインが要求される度に、タイム・スタンプが保存される。立ち退きが必要な場合、最も以前に使用されたもの（最も古いタイム・スタンプ）が選択される。
【００３０】
ｇ．一体化されたおよび個別のバッファ。コードおよびデータは異なる位置を示す。このことは、コードのための１つのバッファとデータのための１つのバッファの、２つの個別のバッファを備えることにより、上手く利用され得る。プラットフォームは、２つの個別のバッファに加えて、さらに一体化されたバッファの使用も可能とする。
【００３１】
ｈ．ＣＰＵ独立。いかなるＣＰＵもアーキテクチャにプラグインすることが可能である。これにより、異なる命令セット・アーキテクチャを使用する研究が可能となる。圧縮／復元技術は、ＣＰＵから完全に独立であることに注目されたい。
【００３２】
図４は、本発明のこの態様の実施形態による設計スペース検証手順のフローチャートである。検証の目標は、性能とエリアに関して、アプリケーションを最適化することである。次の基準は、エリア・オーバー・ヘッドとシステムの性能を評価するために追跡するのに有用である。
【００３３】
−サイクル回数：これは、システム性能を与える回数の総数を測定する。
【００３４】
−断片化：これは、メモリ・ページ内の未使用のスペースの基準である。
【００３５】
−バッファ・ミス比率：バッファ・ミス比率は、性能の間接的な基準である。
【００３６】
−ページ書き戻し回数：書き戻しは、メイン・メモリへの書き込み前に、圧縮アルゴリズムがデータを何回圧縮する必要があったかを参照する。この数は、ランタイム中に、どれぐらい圧縮が必要であったかを示している。
【００３７】
−ページ読み取り回数：これは、バッファ・ミス比率に直接関係するものであり、ページの復元が何回実行されたかを示している。
【００３８】
組込み環境に適したＣＰＵを選択した後に、設計スペース検証は次のように進行することが可能である。
【００３９】
１．コンパイル。アプリケーションは、選択されたプロセッサに対して、コンパイルされる。
【００４０】
２．アプリケーション圧縮。アプリケーションは圧縮される。データ領域およびコード領域の両方は、圧縮されたフォーマットで格納される。
【００４１】
３．空きスペース割り当て。圧縮されたコードおよびデータ領域の近くに、アプリケーション実行中に書き込まれるデータのための若干の空きスペースを割り当てる必要がある。本発明者は、シミュレーション実験に基づいて、５０％以上の圧縮が達成可能な目標であることを見出した。しかし、アプリケーションは、供給される入力に応じて異なる動作をするであろうから、空きスペースに何が要求されているかを、常に事前に知ることができるわけではない。この理由により、圧縮された実行可能なプログラムと空きスペースを合わせて元のアプリケーションの約５０％になるように、保守的な推定値をとり、空きスペースを十分なものにすることが有利である。これは、大きいデータ・エリアを有するアプリケーションについて選択される。小さなデータ・エリアを有するアプリケーションは、効率的には圧縮されないが、他方、それらは、通常、書き込みが少ない。したがって、多くの場合には、元のスペースの５０％を割り当てることは合理的な選択となる。ある場合には、多くの異なる形式のデータを有するアプリケーションを実行することにより、何がスペースに要求されているかについて、より良いアイデアが与えられるであろう。
【００４２】
４．パラメータ選択−出発点。すべてのパラメータに対する出発点が選択されるべきである。例えば、バッファ・サイズ、ページ・サイズ、Ｃフレーム・サイズ、バッファ置換ポリシー、および、一体化されたまたは個別のバッファ。
【００４３】
５．パラメータ・チューニング。この段階において、パラメータが変更され、段階３に戻る。説明すべき手順は、図４に示すフローチャートに示されている。パラメータは、次のように変更可能である。
【００４４】
（ａ）バッファ・サイズ。バッファ・サイズは、ミス比率とエリアに影響を与える。明らかに、バッファをより大きくすると、ミス比率が最も低くなるため、より高性能である。しかし、このことは、システムの全エリアに不利な影響を与えるであろう。図４において、次に大きいサイズから、十分に性能が改善しないと思われる最良のサイズが選択される（性能飽和点）。
【００４５】
（ｂ）ページ・サイズ。ページ・サイズは、第１に圧縮比率に、第２に性能に影響を与える。最良の圧縮比率を与えるページ・サイズが選択される。
【００４６】
（ｃ）Ｃフレーム・サイズ。Ｃフレーム・サイズは、主にメモリ断片化に影響を与え、圧縮への影響は少ない。性能への本質的な影響はない。断片化を極小化するＣフレーム・サイズが選択される。
【００４７】
（ｄ）バッファ置換ポリシー。これは、性能のみに影響を与える。サイクルの総数に関して最良の性能となるポリシーが選択される。
【００４８】
（ｅ）一体化されたバッファ対個別のバッファ。コードおよびデータの両方のための一体化されたバッファは、コードおよびデータのための２つのバッファの性能とともに研究可能であり、その性能と比較可能である。２つの選択の中で最良の性能が選択される。
【００４９】
（ｆ）最終段階−制約を満たしているか？この段階において、制約、例えば、エリアおよび性能を評価することができる。もしエリアが侵害されていれば、戻って、バッファ・サイズを小さくする。もし性能違反があれば、異なる圧縮アルゴリズムを選択可能であり、手順を最初からやり直すことができる。
【００５０】
当業者によって理解されるであろうように、設計手順が、消費電力のような他の制約条件を考慮して変更可能であることは明らかである。様々なレベルのメモリ階層、および、ＣＰＵまたはメモリ・モジュールと相互作用する任意の他のカスタム・デバイスを含めるためにカスタマイズし得るプロセッサ・シミュレータを使用して、手順を実行することが有利である。
【００５１】
上記の具体例は、本発明の単なる例示である。添付した請求の範囲のみにより限定される本発明の範囲内で様々な変更が可能であることは当業者によって理解されよう。
【図面の簡単な説明】
【００５２】
【図１】本発明の態様の実施形態によるメモリ階層のレベルを示す図である。
【図２】メモリ・マッピング・データ構造の概略図である。
【図３】空きスペース管理データ構造の概略図である。
【図４】本発明の他の態様の実施形態による設計検証手順のフローチャートである。
【図１】
2008503922.tif 000003
【図２】
2008503922.tif 000004
【図３】
2008503922.tif 000005
【図４】
2008503922.tif 000006
【国際調査報告】
2008503922.tif 000007
2008503922.tif 000008