(57)【要約】プログラム中の命令を圧縮する方法が、プログラム中の命令から一意的な諸ビット・パターンを抽出する段階と、前記一意的なビット・パターン、前記命令および／またはメモリ記憶のサイズから線形計画法定式化または整数計画法定式化を構築する段階とを含む。線形計画法定式化または整数計画法定式化を解いて解を生成しうる。本方法は、前記解に基づいて、前記一意的なビット・パターンの少なくともいくつかをメモリに記憶し前記メモリへの対応するインデックスを新しい圧縮された命令中に入れることによって、前記命令のうち少なくともいくつかを圧縮する段階を含みうる。
2010521751.tif 000002
【特許請求の範囲】
【請求項１】
プログラム中の命令を圧縮する方法であって：
前記プログラム中の命令から一意的な諸ビット・パターンを抽出する段階と；
前記一意的なビット・パターンおよび前記命令から線形計画法定式化または整数計画法定式化を構築する段階と；
前記線形計画法定式化または前記整数計画法定式化を解いて解を生成する段階と；
前記解に基づいて、前記一意的なビット・パターンの少なくともいくつかをメモリに記憶し前記メモリへの対応するインデックスを新しい圧縮された命令中に入れることによって、前記命令のうち少なくともいくつかを圧縮する段階とを有する、
方法。
【請求項２】
前記抽出する段階の前に、前記プログラム中の前記命令をコンパイルして、前記命令を第一の表現からバイナリーまたは機械語表現に変換する段階をさらに有する、
請求項１記載の方法。
【請求項３】
前記構築する段階が：
不等式の制約条件の組と、最小化されると前記プログラムを最適に圧縮する式とを含む線形計画法定式化を構築することを含む、
請求項１記載の方法。
【請求項４】
前記構築する段階が：
不等式の制約条件の組と、最小化されると前記プログラムを最適に圧縮する式とを含む整数計画法定式化を構築することを含む、
請求項１記載の方法。
【請求項５】
前記構築する段階が：
少なくとも部分的には、前記ビット・パターンを記憶するために使われるメモリのサイズに基づいて、前記線形計画法定式化または前記整数計画法定式化を構築することを含む、
請求項１記載の方法。
【請求項６】
前記構築する段階が：
前記一意的なビット・パターンを前記線形計画法定式化または前記整数計画法定式化における変数として表現することを含む、
請求項１記載の方法。
【請求項７】
実行の前に、前記新しい圧縮された命令中の前記対応するインデックスに基づいて前記メモリから前記一意的なビット・パターンの前記少なくともいくつかを取り出すことによって、前記新しい圧縮された命令を圧縮解除する段階をさらに有する、
請求項１記載の方法。
【請求項８】
プログラム中の命令を圧縮する方法であって：
前記プログラムをコンパイルしてバイナリー・データを生成する段階と；
前記バイナリー・データから一意的な諸ビット・パターンを抽出する段階と；
前記一意的なビット・パターンおよび前記一意的なビット・パターンのための記憶容量に基づいて、解けば前記記憶容量について前記プログラムの最適圧縮を与える線形計画法定式化または整数計画法問題を構築する段階と；
前記線形計画法定式化または前記整数計画法問題を解いて解を生成する段階と；
前記解に基づいて、前記プログラム中の前記命令の少なくともいくつかを圧縮する段階とを有する、
方法。
【請求項９】
前記構築する段階が：
前記一意的なビット・パターンを前記線形計画法定式化または前記整数計画法問題における変数にマッピングする段階を含む、
請求項８記載の方法。
【請求項１０】
前記整数計画法問題が線形整数計画法問題を含む、請求項８記載の方法。
【請求項１１】
前記解が、前記圧縮する段階において使用されるべき指定された一意的パターンを特定し、
前記圧縮する段階が、前記指定された一意的パターンをメモリ内の前記記憶容量中に記憶する段階を含む、
請求項８記載の方法。
【請求項１２】
圧縮された命令を、該圧縮された命令の実行前に圧縮解除する段階をさらに有する、請求項８記載の方法。
【請求項１３】
前記のコンパイルする段階、抽出する段階、構築する段階、解く段階および圧縮する段階が第一の処理システムによって実行され、
前記の圧縮解除する段階が第二の処理システムによって実行される、
請求項１２記載のシステム。
【請求項１４】
プログラムを圧縮するシステムであって：
前記プログラムをバイナリー・フォーマットに変換するコンパイラと；
バイナリー・データを記憶するための、ある容量をもつメモリと；
前記コンパイラおよび前記メモリに接続されたコンパクト化器であって、前記プログラムの前記バイナリー・フォーマットから一意的な諸ビット・パターンを抽出し、前記メモリの容量および前記一意的なビット・パターンに基づいて、前記一意的なビット・パターンの少なくともいくつかを前記メモリ中に記憶し対応するインデックスを前記プログラム中に挿入することによって前記プログラムを最適に圧縮するコンパクト化器とを有する、
システム。
【請求項１５】
前記メモリおよび前記コンパクト化器に接続された処理システムであって、前記の最適に圧縮されたプログラムを実行する段階をさらに有する、
請求項１４記載のシステム。
【請求項１６】
前記処理システムが、前記対応するインデックスを使って前記メモリから前記一意的なビット・パターンの前記少なくともいくつかを取り出すことによって前記の最適に圧縮されたプログラムを圧縮解除するよう構成されている、請求項１５記載のシステム。
【請求項１７】
前記コンパクト化器が、前記プログラムを最適に圧縮するために整数計画法問題を定式化し、解くよう構成されている、請求項１４記載のシステム。
【請求項１８】
前記コンパクト化器がさらに、前記整数計画法問題を定式化するときに前記一意的なビット・パターンを変数にマッピングするよう構成されている、請求項１７記載のシステム。
【請求項１９】
前記整数計画法問題が線形整数計画法問題である、請求項１７記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
特許請求される発明の実装は概括的にはデータ圧縮に、より詳細にはプログラムの実行に先立つプログラム（またはコード）中の命令の圧縮に関係しうる。
【背景技術】
【０００２】
多くの処理システムは命令を実行する。よって、プログラムをなす命令を生成し、記憶し、および／またはこれにアクセスすることができることが望ましい。特に、記憶および／またはバンド幅の節約のため、プログラム／コードを縮小することが一般に望ましいことがありうる。ランタイムにキャッシュ（たとえばL2）に記憶されるデータを圧縮するためのいくつかの技法が提案されている。しかしながら、ランタイムでの圧縮はハードウェアの複雑のほか、データが圧縮される必要があるかどうかについてのポリシー判断をなすための追加的な遅延を導入しうる。
【０００３】
提案されているもう一つの技法は、エコー命令である。これは、共通／類似の命令シーケンスをエコー命令で置き換えることによってプログラム／コードを縮小しうる。しかしながら、この技法は、共通／類似の命令シーケンスを検索する際に命令レベルの情報に焦点を当て、よって命令の内部に有用な情報があっても無視してしまう。
【０００４】
しかしながら、プログラム／コード・サイズを縮小するそのような方式は、計算集約的であり、および／または個別的なプログラムについて最適でない圧縮につながりうる。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本願発明は従来技術の問題を解決しようとするものである。
【課題を解決するための手段】
【０００６】
本願発明の課題は請求項記載の手段によって解決される。
【０００７】
付属の図面は本明細書に組み込まれ、本明細書の一部をなすものであり、本発明の原理と整合する一つまたは複数の実装を図示し、本記載とともにそのような実装を説明するものである。図面は必ずしも縮尺通りではなく、本発明の原理を例解することに重点が置かれている。
【図面の簡単な説明】
【０００８】
【図１】第一および第二の処理システムを有するシステムのブロック図である。
【図２】図１の第一の処理システムのブロック図である。
【図３】プログラム中のビット・パターンを最適に圧縮する方法を示す図である。
【図４】ビット・パターンの変数へのマッピングを例解するための例示的な命令の組を示す図である。
【発明を実施するための形態】
【０００９】
以下の詳細な記述は付属の図面を参照する。異なる図面において同じまたは類似の要素を特定するために同じ参照符号が使用されることがある。以下の記述では、限定ではなく説明の目的のため、特許請求される発明のさまざまな側面の十全な理解を提供するために、具体的な構造、アーキテクチャ、インターフェース、技法などといった個別的な詳細が述べられる。しかしながら、本開示の恩恵を受けた当業者には、特許請求される発明のさまざまな側面がこれらの個別的詳細から外れる他の例において実施されてもよいことは明白であろう。場合によっては、無用な詳細で本発明の記述を埋没させることがないよう、よく知られた装置、回路および方法の記述は省略される。
【００１０】
いくつかの実装では、第一の処理システムが、第二の処理システムによる実行のために、少なくとも部分的にコンパクト化された命令（またはそのような命令からなるプログラム）を生成することに使用されうる。
【００１１】
図１は、いくつかの実装に基づくシステム１００のブロック図である。図１を参照すると、システム１００は第一の処理システム１１０および第二の処理システム１２０を含む。第一の処理システム１１０および第二の処理システム１２０は、たとえば第一の通信リンク１３０を介して互いに結合されていてもよい。システム１００は、命令および／またはプログラムのコンパクト化の際に第一の処理システム１１０によって生成されるビット・パターンを記憶するための一つまたは複数のインデックス付けされたキャッシュ１９０を含んでいてもよい。これについてはのちにより詳細に説明する。
【００１２】
いくつかの実装によれば、第一の処理システム１１０は第二の処理システム１２０のための命令を生成することにおいて使用される。それに関し、いくつかの実装では、システム１００は１４０で示される入力または第一のデータ構造を受け取りうる。第一のデータ構造１４０は第二の通信リンク１５０を通じて受信されてもよく、これに限られないが第一の数の命令を含むプログラムを含みうる。第一の数の命令は、第一の言語、たとえば高水準言語またはアセンブリ言語の命令を含みうる。いくつかの実装では、第一の言語でのこれらの命令は128ビット命令であってもよい。ただし、本発明はそれに限定されるものではない。
【００１３】
第一のデータ構造１４０は第一の処理システム１１０の入力に供給されてもよい。第一の処理システムは、第二の処理システム１２０に関連する一つまたは複数の要件に従って第一のデータ構造１４０の一つまたは複数の部分をコンパイルおよび／またはアセンブルするコンパイラおよび／またはアセンブラを含んでいてもよい。第一の処理システム１１０の出力は、１６０で示される第二のデータ構造を供給しうる。第二のデータ構造１６０は、これに限られないが、第二の数の命令を含むプログラムを含みうる。第二の数の命令は、第二の言語、たとえば機械語またはバイナリー語での命令を含みうる。いくつかの実装では、第二の言語は、64ビット命令を含みうるという点を除いて第一の言語と同じであってもよい。いくつかの実装では、第二の言語での命令の一部または全部が64ビット命令であってもよい。ただし、第二の言語での命令はいくつかの128ビット命令をも含んでいてもよい。もちろん、本発明はいかなる特定の長さ（単数または複数）の命令にも限定されないが、第二の言語での命令の少なくとも一部は第一の言語での命令より短い、あるいはそれからコンパクト化されていることがありうる。
【００１４】
図２は、第一の処理システム１１０の一つの実装のブロック図である。図２を参照すると、いくつかの実装では、第一の処理システム１１０は、いくつかの実装では存在しなくてもよいコンパイラおよび／またはアセンブラ２１０と、コンパクト化器２２０とを含む。コンパイラおよび／またはアセンブラ２１０およびコンパクト化器２２０は、たとえば通信リンク２３０を介して互いに結合されうる。説明の簡単のため二つの別個の要素として示されているが、実装によっては、コンパクト化器２２０はコンパイラおよび／またはアセンブラ１１０の機能部分であってもよい。
【００１５】
いくつかの実装では、第一の処理システム１１０は通信リンク１５０を通じて第一のデータ構造１４０を受信しうる。上記のように、第一のデータ構造１４０は、これに限られないが、第一の複数の命令を含みうる。第一の複数の命令は、第一の言語、たとえば高水準言語またはアセンブリ言語での命令を含みうる。
【００１６】
第一のデータ構造１４０はコンパイラおよび／またはアセンブラ２１０の入力に供給されうる。コンパイラおよび／またはアセンブラ２１０は、第二の処理システム１２０に関連する一つまたは複数の要件に従って第一のデータ構造１４０の一つまたは複数の部分をコンパイルおよび／またはアセンブルするコンパイラ、アセンブラならびに／またはそれらの組み合わせを含む。
【００１７】
コンパイラおよび／またはアセンブラ２１０は、２４０で示されるデータ構造を生成しうる。データ構造２４０はこれに限られないが、第二の言語、たとえばバイナリーまたは機械語での命令を含みうる複数の命令を生成しうる。いくつかの実装では、第二の言語は、64ビット命令を含みうるという点のほかは第一の言語と同じであってもよい。いくつかの実装では、前記複数の命令は、第二の処理システム１２０の実行エンジンによって実行されるべき複数の機械コード命令であってもよい。いくつかの実装では、前記複数の命令は二つ以上の型（type）の命令を含んでいてもよい。
【００１８】
データ構造２４０はコンパクト化器２２０の入力に供給されうる。コンパクト化器２２０はデータ構造２４０内の各命令を処理して、そのような命令が第二の処理システム１２０のためのコンパクト命令によって置き換えられることができるかどうかを判定する。その命令が置き換え可能であれば、コンパクト化器２２０はそのような命令の代わりとなるコンパクト命令を生成しうる。実装によっては、コンパクト化器２２０はコンパクト命令を、少なくとも部分的には置き換えられるべき命令に基づいて生成する。実装によっては、コンパクト命令は、そのコンパクト命令がコンパクト命令であることを示すフィールドを含む。
【００１９】
いくつかの実装によれば、コンパクト化器２２０は、命令をコンパクト命令で置き換える。その点に関し、前記複数の命令は命令のシーケンスを表しうる。命令はシーケンス中のその位置から取り除かれてもよく、コンパクト命令がシーケンス中のそのような位置に挿入されてもよく、それによりシーケンス中のコンパクト命令の位置が、それにより置き換えられる命令の、該命令のシーケンスからの除去前の位置と同じとなるようにされる。
【００２０】
のちにより詳細に説明するように、コンパクト化器２２０はデータ構造２４０中のいくつかの命令のコンパクト化を、共通して現れるビット・パターンをキャッシュ（単数または複数）１９０中に記憶することによって行いうる。コンパクト化器２２０は、命令（単数または複数）のコンパクト化を、第二のデータ構造１６０内での命令においてビット・パターンそのものの代わりにキャッシュ（単数または複数）１９０内でのそのビット・パターンの位置へのインデックスを使うことによって行いうる。
【００２１】
図１を参照すると、第二のデータ構造１６０は第一の通信リンク１３０を通じて第二の処理システム１２０の入力に供給されうる。第二の処理システムは、第二の複数の命令の一つまたは複数を実行でき、１７０で示されるデータを生成しうる。いくつかの実装では、第二の処理システム１２０は、第二のデータ構造１６０中のいかなるコンパクト化された命令（たとえば64ビット命令）をも、実行前に、コンパクト化命令中のインデックス値（単数または複数）を介してキャッシュ（単数また複数）１９０内の適切なビット・パターンにアクセスすることによって、伸張しうる。コンパクト化されていない第二のデータ構造１６０中の命令（たとえば128ビット命令）は、キャッシュ（単数または複数）１９０を使うことなく第二の処理システム１２０によって処理されうる。
【００２２】
第二の処理システム１２０は、一つまたは複数の通信リンク、たとえば第三の通信リンク１８０を通じて一つまたは複数の外部装置（図示せず）に結合されてもよく、データ１７０の一部または全部を、そのような通信リンクの一つまたは複数を通じてそのような外部装置の一つまたは複数に供給してもよい。
【００２３】
上で説明したように、第二の処理システム１２０のための命令の一つまたは複数の部分（たとえばビット・パターン）は一つまたは複数のメモリ・ユニット（たとえばキャッシュ１９０）に記憶されうる。この点に関し、キャッシュ（単数または複数）１９０は単一のメモリ・ユニットを含んでいてもよいし、複数のメモリ・ユニットを含んでいてもよい。場合によっては（たとえば比較的小さなプログラムについては）、キャッシュ１９０は第一のデータ構造１４０（またはデータ構造２４０）中の命令をフルに圧縮するために必要なすべてのビット・パターンを記憶するのに十分なスペースを有していてもよい。場合によっては（たとえば比較的大きなプログラムについては）、キャッシュ１９０は第一のデータ構造１４０（またはデータ構造２４０）中の命令をフルに圧縮するために必要なすべてのビット・パターンを記憶するのに十分なスペースを有していなくてもよい。そのような実装では、キャッシュ１９０のサイズ制約が与えられたもとでの最大圧縮量を得るために、データ構造（単数または複数）１４０または２４０中の命令について圧縮比を最適化することが望ましいことがありうる。ここで、そのようなコード最適化方式を説明する。
【００２４】
上で言及し、関連出願で説明したように、プログラム中の命令は、たとえば128ビット命令から共通のビット・パターンを抽出することによって圧縮されうる。インデックス付けされたキャッシュ（単数または複数）１９０はこれらの共通ビット・パターンおよび新しいコンパクト命令（たとえば64ビット命令）のために必要とされる他の任意の情報を保持しうる。コンパイラまたはアセンブラ２１０は、どのビット・パターンがインデックス付けされたキャッシュ１９０に記憶されるべきかを識別でき、また、どの命令が新しいコンパクト命令で置き換えられることができるかも判定しうる。それらの命令を含むプログラムのサイズおよび／またはキャッシュ１９０のサイズに依存して、ある命令はキャッシュ１９０内の限られたスペースのため、圧縮できないことがありうる。そのような場合、コンパクト化器２２０（またはコンパクト化機能がコンパイラ・モジュールの一部である場合にはコンパイラ２１０）がプログラムを最適に圧縮する（たとえばできるだけ強く圧縮する）ことが望ましいことがありうる。
【００２５】
より詳細には、たとえば図４に概念的に図示されているように、プログラム中の各命令がいくつかのフィールドに分割されうる。しかしながら、実装によっては、命令のいくつかの部分がいかなるフィールドの一部でもないこともありうることは注意しておくべきである。これまでに実行された実験に基づき、たいていのプログラムは、それらのフィールドのいくつかについて、いくつかの共通の反復ビット・パターン（M、1以上の整数）を含む可能性が高い。M個のフィールドのそれぞれは同じサイズでなくてもよいことも注意しておくべきである（すなわち、各フィールドは、他のすべてのフィールドと全く異なる数のビットを含んでいてもよい）。ある命令のM個すべてのビット・パターンがみな、もとのビット・パターンを記憶するキャッシュ（単数または複数）１９０中を指すのに使われるインデックス値によって置き換えられるなら、その命令は、よりコンパクトな命令を使って置き換えられることができ、よりコンパクトなプログラムが生じる。キャッシュ（単数または複数）１９０のエントリー数は限られているので、プログラムの命令中に見出されるすべてのビット・パターンがテーブル中に記憶され、インデックス値で置き換えられるわけにはいかない。
【００２６】
図３の方法３００は、キャッシュ（単数または複数）１９０において記憶されるべきビット・パターンを選択するための方式であって、最適なコード・コンパクト化比（たとえば、コンパクト化器２２０によって出力されるコンパクト化されたデータ構造１６０のサイズとコンパクト化器２２０に入力されるデータ構造２４０（またはデータ構造１４０）のサイズとの最も小さい比）につながるものを記載している。方法３００は図１、図２および図４に関して説明されるかもしれないが、方法３００の方式はこれらの図面に示される個別事項に限定されるものではない。方法３００は、（たとえば命令をコンパイルするコンパイラ２１０によって）機械語またはバイナリー・フォーマットにされた命令から出発しうる。そこからビットのパターンが識別されうる。
【００２７】
方法３００は、コンパクト化器２２０が、目標プログラムの命令中の圧縮可能なフィールドから一意的な諸ビット・パターンを抽出することで始まりうる［工程３１０］。工程３１０では、それらの命令内の一意的なビット・パターンの数を決定するために、いくつもある既知のビット識別方式のいずれを使ってもよい。工程３２０に関して説明されるように、これらの一意的なビット・パターンは、整数または線形計画法の定式化における変数にマッピングされうる。
【００２８】
ビット・パターンの集合を識別したのち、コンパクト化器２２０は、目標プログラムの最適コンパクト化の整数計画法（integer  programming）または線形整数計画法（linear  integer  programming）表現を構築しうる［工程３２０］。そのような整数計画法または線形整数計画法の表現は、工程３１０において抽出された一意的な諸ビット・パターンから、コンパクト化器２２０によって、以下の原理、例および一般化に従って、自動的に構築されうる。
【００２９】
キャッシュ（単数または複数）１９０には圧縮されたビット・パターンを記憶するためにN個のテーブルがあってもよく（N≧1）、テーブル中に挿入すべきビット・パターンを選択するもとになるM個のフィールドがあってもよい（M≧1、M≧N）。たとえば図４に示されるように、各命令はいくつかのフィールドを含みうる。たとえば、二つの可能な筋書きは、M個のフィールドすべてが単一の（N＝1）テーブルを共有する場合、あるいは各フィールドが独自のテーブルをもつ場合（N＝M）である。いずれの筋書きでも、各フィールドは、その命令が圧縮される場合、圧縮されたビット・パターンを取り出す専用のテーブルをもつ。工程３２０における方式は、圧縮可能フィールドからテーブルへの多対一のマッピングを使ってもよい。
【００３０】
i番目のテーブルはMi個のフィールドによって共有されうる。i番目のテーブルについて、一組の変数がありうる。各変数は、Miフィールドにおいて現れる一意的なビット・パターンに対応する。このように、変数の数はMiフィールドの間に見出される一意的なビット・パターンの総数に対応する。
【００３１】
工程３２０は、最適なコード・コンパクト化定式化を構築する二つ（またはそれ以上）の方式：（ａ）整数計画法問題としての方式、および（ｂ）線形整数計画法としての方式、のうちの一つを使用しうる。これら二つの方式が記述されるが、最適なプログラム・コンパクト化のために解くべき定式化をセットアップするために、多くの多変量最適化方式が工程３２０において利用されうることは注意しておくべきである。
【００３２】
〈（Ａ）整数計画法（Integer  programming）〉
工程３２０を実装するための直観的な概念を与えるため、各方式について二つの個別的な例（すなわちM＝NとN＝1）が呈示される。次いでこれら二つの例の一般化が呈示される。図４は、四つの命令をもつ例示的なプログラム４１０（これは入力データ構造２４０または１４０の個別的な事例である）とそのビット・パターンを示している。各命令が三つのフィールドをもつ。以下の例はこのプログラムを圧縮のために定式化する。圧縮のための候補でない他のフィールドは記述の簡単のため図示していないが、そのようなフィールドもプログラム中に存在していてもよい。この例では記述の簡単のためフィールドはみな同じサイズとしているが、のちに呈示する一般化はそのような前提を必要としない。
【００３３】
〈M＝Nの例〉
各フィールドが独自のテーブルをもつ場合、X、Y、Zが変数の諸セットとして定義されうる。各テーブルについて一つである。フィールドX、Y、Zはそれぞれ３、２、３個の一意的なビット・パターンをもつ。こうして、テーブルX(x1,x2,x3)については３つの変数があり、テーブルY(y1,y2)については２つの変数があり、テーブルZ(z1,z2,z3)については３つの変数がある。代替的な見方は、テーブルX、YおよびZに記憶されるべき３個、２個および３個の候補ビット・パターンがあるというものである。この筋書きにおいて、命令１のフィールドはみな同じビット・パターンをもっているが、各テーブルに一つで３つの変数があることを注意しておく。テーブルX、Y、Zはさらに、それぞれTx個、Ty個、Tz個のエントリーをもつよう定義される。
【００３４】
各変数は、ビット・パターンが圧縮される（すなわちその変数が対応するテーブル中にエントリーを得る）場合かつその場合にのみ値1を割り当てられ、その他の場合には値0を得る。命令は、その圧縮可能なフィールドすべてが圧縮される（すなわち実際にテーブル中へのインデックスで置き換えられる）場合かつその場合にのみ圧縮される。命令は、圧縮される場合値1を割り当てられ、そうでない場合には値0を割り当てられる。
【００３５】
この定式化を構築するため、各命令は、そのフィールドのビット・パターンに対応する変数すべての積によって表現される。この例では、積は命令１ないし４についてそれぞれx1y1z1、x2y2z2、x1y2z3、x3y1z3である。
【００３６】
コード・コンパクト化（すなわち圧縮される命令の数）を最大化することが望ましい。M＝Nの場合についての整数計画法定式化は、その場合、前記積の和を最大にするxi、yi、zi、についての値を見出すことである：
x1y1z1＋x2y2z2＋x1y2z3＋x3y1z3を最大化
課される制約条件：
xi（i＝1..3）＝0または1
yi（i＝1,2）＝0または1
zi（i＝1..3）＝0または1
Σi=1..3  xi≦Tx
Σi=1..2  yi≦Ty
Σi=1..3  zi≦Tz    （すなわち、圧縮されたビット・パターンの数はそれぞれの対応するテーブルに収まらなければならない）。
【００３７】
〈N＝1の例〉
すべてのフィールドが単一のテーブルを共有する場合、整数計画法定式化のために必要とされるのは一組の変数（すなわち、変数のセットX）のみである。図４のフィールドX、Y、Zの間に、一意的なビット・パターンは４通りしかない。よって、テーブルX（x1,x2,x3,x4）について４つの変数または４つの候補ビット・パターンがある。この筋書きでは、命令１中のすべてのフィールドは、みな同じビット・パターンをもつので同じ変数x1によって表される。テーブルXはT個のエントリーをもちうる。
【００３８】
N＝1の場合についての整数計画法定式化は、次いで、前記積の和を最大にするxiについての値を見出すことである：
x1y1z1＋x2y2z2＋x1y2z3＋x4y1z3を最大化
課される制約条件：
xi（i＝1..4）＝0または1
Σi=1..4  xi≦T
。
【００３９】
〈一般化〉
一般に、キャッシュ（単数または複数）１９０内にN（≧1）個のテーブルがありうる。i番目のテーブルは、全命令（たとえばQ個の命令すべて）のMi個のフィールドのうちで見出されたPi個の候補ビット・パターンをもつ。M1＋M2＋…＋MN＝M＝圧縮できるフィールドの総数、である。その際、Mi個のフィールドの組（および対応してi番目のテーブル）は、各候補ビット・パターンについて一つでPi個の変数の組をもつ。
【００４０】
各命令は、圧縮できる各フィールドから一つでM個の変数の積によって表現されうる。M＝Nであれば（上例のように）、各変数は異なる組からくる。一般的な整数計画法定式化は、すべての積の和を最大にすることである：
Σj=1,...Q  Πk=1,...M  x(j,k)  を最大化
ここで、x(j,k)はj番目の命令のk番目のフィールドに位置するビット・パターンについての変数である。k番目のフィールドのビット・パターンがi番目のテーブル中に記憶されるべき候補である場合、x(j,k)変数はi番目のテーブルに関連付けられたPi個の変数のうちからである。
【００４１】
上記に対する制約条件は：
x＝0,1    N個のテーブルすべてからのすべての変数xについて
かつ
Σk=1...Pi  xk≦Ti
ここで、Tiはi番目のテーブル中のエントリー数である。つまり、テーブルのどれかに挿入されうる候補ビット・パターンの最大数はテーブルのサイズによって制限される。
【００４２】
〈（Ｂ）線形整数計画法（Linear  integer  programming）〉
工程３２０のための第二のアプローチは、このコード・コンパクト化のゴールを、線形整数計画法問題の形で定式化することである。二つの異なる筋書きについて工程３２０についての直観的な概念を与えるために、上記の例のパラメータが再び使用され（すなわちM＝NおよびN＝1）、その後、その一般化について述べる。ここでもまた、図４は４つの命令について、各命令が３つの圧縮できるフィールドをもつものとして議論されうる。
【００４３】
〈M＝Nの例〉
先の方式と同様、各ビット・パターン関係変数は、ビット・パターンが圧縮される場合にかつその場合にのみ値1を受け、そうでない場合には値0を得る。さらに、各命令について一つで４つのさらなる変数がある（w1,w2,w3,w4）。各命令関係変数は、その命令が圧縮される場合かつその場合にのみ値0を受け取り、そうでない場合には値1を得る。和Σj=1..4  wjは、圧縮される命令の数が最大にされる場合かつその場合にのみ最小化される。
【００４４】
命令関係変数（wi）とビット・パターン関係変数（xi,yi,zi）との間に制約条件関係も確立されうる。各命令について、そのフィールドのビット・パターンのいずれかが圧縮されない場合（すなわち、ビット・パターン関係変数＝0）、その命令は圧縮されない（すなわち、命令関係変数＝1）。たとえば、第一の命令について：
w1＋x1≧1、      w1＋y1≧1、      w1＋z1≧1。
【００４５】
線形整数計画法定式化は、和を最小化するwiについての値を見出すことである：
w1＋w2＋w3＋w4  を最小化
制約条件は：
xi（i＝1..3）＝0または1
yi（i＝1,2）＝0または1
zi（i＝1..3）＝0または1
wi（i＝1..4）＝0または1
および
w1＋x1≧1、      w1＋y1≧1、      w1＋z1≧1
w2＋x2≧1、      w2＋y2≧1、      w2＋z2≧1
w3＋x1≧1、      w3＋y2≧1、      w3＋z3≧1
w4＋x3≧1、      w4＋y1≧1、      w4＋z3≧1    （すなわち、命令が圧縮されるのはそのフィールドすべてが圧縮されるときのみ）
および
Σi=1..3  xi≦Tx
Σi=1..2  yi≦Ty
Σi=1..3  zi≦Tz    （すなわち、圧縮されたビット・パターンの数はそれぞれの対応するテーブルに収まらねばならない）。
【００４６】
〈N＝1の例〉
すべてのフィールドが単一のテーブルを共有する（たとえばキャッシュ１９０内で）場合、一意的なビット・パターンは４つしかない。４つの候補ビット・パターンについての４つの変数（x1,x2,x3,x4）に加えて、４つの命令関係変数（w1,w2,w3,w4）もある。さらに、テーブルXはT個のエントリーをもちうる。
【００４７】
整数計画法定式化は、和を最小化するwiについての値を見出すことである：
w1＋w2＋w3＋w4  を最小化
課される制約条件は：
xi（i＝1..4）＝0または1
wi（i＝1..4）＝0または1
Σi=1..4  xi≦T      選択される候補の数をテーブルのサイズに制限するため
w1＋x1≧1、      w1＋x1≧1、      w1＋x1≧1
w2＋x2≧1、      w2＋x2≧1、      w2＋x2≧1
w3＋x1≧1、      w3＋x2≧1、      w3＋x3≧1
w4＋x4≧1、      w4＋x1≧1、      w4＋x3≧1
上記の制約条件は、そのいくつかは冗長であるが、明確さのためにすべて挙げられている。
【００４８】
〈一般化〉
一般に、キャッシュ（単数または複数）１９０内にN（≧1）個のテーブルがある。i番目のテーブルは、全命令（たとえばQ個の命令すべて）のMi個のフィールドのうちで見出されたPi個の候補ビット・パターンのうちから、そのサイズ内に収まるように選ばねばならない。M1＋M2＋…＋MN＝M＝圧縮できるフィールドの総数、である。その際、i番目のテーブルは、各候補ビット・パターンについて一つでPi個の変数の組をもつ。また、各命令について一つでQ個の変数がある（wj,  j＝1...Q）。各命令は、圧縮できる各フィールドについて一つでM個の制約条件の組を生成する。
【００４９】
一般的な線形整数計画法定式化は、和を最小化するwiについての値を見出すことである：
Σj=1,...Q  wj  を最小化
制約条件は次によって与えられる：
x＝0,1    一意的なビット・パターンに対応するすべての変数xについて
wj＝0,1    すべての命令関係変数について
Σk=1...Pi  xk≦Ti
ここで、Tiはi番目のテーブル中のエントリー数である（すなわち、テーブルのどれかに挿入できる候補ビット・パターンの最大数はテーブルのサイズによって制限される）。
【００５０】
さらに、各j番目の命令について、M個の制約条件がある：
wj＋x(j,k)≧1    （k＝1,...M）
ここで、x(j,k)は、j番目の命令のk番目のフィールド中に位置されるビット・パターンについての変数である。結論として、上記の整数計画法定式化または線形整数計画法定式化のいずれも、工程３１０で抽出された一意的なビット・パターンからコンパクト化器２２０によって工程３２０において自動的に構築されうる。
【００５１】
方法３００は、コンパクト化器２２０が線形または整数計画法定式化を解くことで続きうる［工程３３０］。定式化または表現は、任意の整数計画法または線形整数計画法の解法器〔ソルバー〕にしかるべく入力されうる。そのような解法器は既知であり、線形または整数計画法問題を最小化する最適な解を生成しうる。工程３３０における変数について結果として得られる解は、コード・コンパクト化比を最大にする、圧縮化されるべきビット・パターンを同定する。
【００５２】
コンパクト化器２２０は、工程３３０で得られた解に基づいてプログラム中の適切なビット・パターンを圧縮しうる［工程３４０］。命令を圧縮するためのいくつかの技法が関連出願において記述されている。コンパイル時に（またはその後まもなく）工程３４０において圧縮されるとき、プログラムは、キャッシュ（単数または複数）１９０のサイズ制約条件が与えられたもとで最適にコンパクト化されうる。上で説明したように、工程３３０において圧縮のために同定された一意的なビット・パターンは、工程３４０においてキャッシュ（単数または複数）１９０に記憶されてもよく、そのインデックスが圧縮された命令中に挿入されてもよい。
【００５３】
方法３００は、実行時に第二の処理システム１２０が、当該プログラムを実行する際に圧縮されている任意の命令を圧縮解除することで続きうる［工程３５０］。上記のように、すべての命令が圧縮される必要はないが、キャッシュ（単数または複数）１９０が十分な記憶容量をもつならすべてが圧縮されてもよい。圧縮されない命令については、工程３５０は適用されない。圧縮されている（たとえば128ビットから64ビットに）命令について、工程３５０において、第二の処理システム１２０はもとの、より大きな命令を、圧縮されている命令中のインデックス（単数または複数）に基づいてキャッシュ（単数または複数）１９０から記憶されているビット・パターン（単数または複数）を取り出すことによって、再アセンブルしうる。圧縮解除された命令は、工程３５０において、第二の処理システム１２０によって、たとえば実行パイプライン中に挿入されうる。
【００５４】
上記の方式およびシステムは、プログラム（たとえばカーネルまたは他のプログラム）を有利にかつ最適に圧縮でき、個別的な整数計画法または線形整数計画法のアルゴリズムや実装とは独立である。コンパイル時におけるそのような最適プログラム圧縮は、圧縮を通じた著しい命令フットプリント縮小につながり、大きな複雑なカーネルが命令キャッシュに収まることを許容しうる。命令コード・サイズの縮小は、命令キャッシュ・サイズの増大としても等しく効果的である。命令圧縮はまた、命令フェッチ（パイプ、キャッシュなど）のパワーおよび／またはバンド幅要求をも軽減しうる。
【００５５】
一つまたは複数の実装の以上の記述は、例示および説明を提供するが、網羅的であることも、本発明の範囲を開示されている厳密な形に限定することも意図されていない。修正および変形が、上記の教示に照らして可能であり、本発明のさまざまな実装の実践から習得されうる。
【００５６】
たとえば、線形および整数計画法の方式が記載されてきたが、最適なプログラム・コンパクト化を得るためにコンパイルされる命令中のどのビット・パターンを圧縮すべきかを決定するために、いかなる多変量最適化方式が利用されてもよい。
【００５７】
本願の記述において使用されるいかなる要素、工程または命令も、明示的にそう述べられているのでない限り、本発明にとって決定的または本質的であると解釈すべきではない。また、ここでの用法では、単数形は一つまたは複数の項目を含むことが意図されている。本発明の精神および原理から実質的に外れることなく、特許請求される発明の上記の実装に対して変形および修正がなされうる。そのようなすべての修正および変形は、本開示の範囲内に含まれ、付属の請求項によって保護されることが意図されている。
【図１】
2010521751.tif 000003
【図２】
2010521751.tif 000004
【図３】
2010521751.tif 000005
【図４】
2010521751.tif 000006
【国際調査報告】
2010521751.tif 000007
2010521751.tif 000008