(57)【要約】デジタルコンピュータシステムは自動的に、ハードウェアコストを設計者の特定された限度より下に維持しながらアプリケーションのセットの性能を増加する目的または所定の必要なレベルの性能が与えられたハードウェアコストを最小にする目的により、ＶＬＩＷ命令、ベクトル演算、ヒューズド演算、特定化演算を潜在的に使用する命令セットアーキテクチャＩＳＡを生成する。【特許請求の範囲】
【請求項１】
高レベル言語で書き込まれた少なくとも１つのソフトウェアプログラムを受信する手段と、
そのプログラムを実行するように最適化された命令セットアーキテクチャを自動的に生成する手段とを具備し、命令セットアーキテクチャは既存の標準または既存のユーザの規定された命令セットアーキテクチャに基づいた１以上の拡張命令を含んでいる構造のセットとして表されるシステム。
【請求項２】
拡張命令は既存の標準または既存のユーザの規定された命令セットアーキテクチャの状態およびレジスタファイルで動作する請求項１記載のシステム。
【請求項３】
拡張命令は既存の命令のベクトル化されたバージョンを含んでいる請求項２記載のシステム。
【請求項４】
拡張命令は既存の命令のＶＬＩＷの組合わせを含んでいる請求項２記載のシステム。
【請求項５】
拡張命令は既存の命令のヒューズド組合わせを含んでいる請求項２記載のシステム。
【請求項６】
拡張命令は既存の命令の特別化されたバージョンを含んでいる請求項２記載のシステム。
【請求項７】
拡張命令は高レベル言語によりサポートされた動作のベクトル化されたバージョンを含んでいる請求項２記載のシステム。
【請求項８】
拡張命令は高レベル言語によりサポートされた動作のＶＬＩＷの組合わせを含んでいる請求項２記載のシステム。
【請求項９】
拡張命令は高レベルの言語によりサポートされた動作のヒューズド組合わせを含んでいる請求項２記載のシステム。
【請求項１０】
拡張命令は高レベル言語によりサポートされた動作の特別化されたバージョンを含んでいる請求項２記載のシステム。
【請求項１１】
拡張命令は既存の命令のベクトル化、ＶＬＩＷ、ヒューズド、特別化のバージョンの少なくとも２つを含んでいる請求項２記載のシステム。
【請求項１２】
拡張命令は高レベルの言語によりサポートされた動作のベクトル化、ＶＬＩＷ、ヒューズド、特別化のバージョンの少なくとも２つを含んでいる請求項２記載のシステム。
【請求項１３】
１以上の拡張命令は拡張言語を使用して記述された他のユーザ規定命令のベクトル化、ＶＬＩＷ、ヒューズド、特別化のバージョンである請求項２記載のシステム。
【請求項１４】
命令セットアーキテクチャの生成は、少なくとも１つのソフトウェアプログラムから集められた解析情報により誘導され、
解析情報は生成された命令セットアルゴリズムから性能の改良を得ることのできるコードの各区域で集められる請求項２記載のシステム。
【請求項１５】
解析情報は実際の、または評価されたプロファイリング情報から決定されるときの各区域の実行カウントを含んでいる請求項１４記載のシステム。
【請求項１６】
解析情報はユーザ供給指示から決定されるときの各区域の実行カウントを含んでいる請求項１４記載のシステム。
【請求項１７】
解析情報は各区域の依存グラフを含んでいる請求項１４記載のシステム。
【請求項１８】
解析情報は各区域の性能を改良するために使用されることができる動作ベクトル長のセットを含んでいる請求項１４記載のシステム。
【請求項１９】
構造により表される命令、動作、レジスタファイル、状態が区域で使用されることができる場合に生じる性能改良を決定するために、各区域は命令セットアーキテクチャ構造のセットによって評価される請求項１４記載のシステム。
【請求項２０】
命令セットアーキテクチャ生成は、構造により表される命令、動作、レジスタファイル、状態を実行するのに必要な論理装置のコストを含んでいる各命令セットアーキテクチャ構造のハードウェアコストの評価のガイドラインとして使用し、
各区域の各命令セットアーキテクチャ構造のハードウェアコストおよび性能の改良は、生成される命令セットアーキテクチャを共に記述する命令セットアーキテクチャ構造のセットを決定するために使用され、それによってソフトウェアプログラムの性能の改良は、生成される命令セットアーキテクチャがコスト予算を超えずに、可能な限り多く増加される請求項１９記載のシステム。
【請求項２１】
命令セットアーキテクチャの生成は、構造により表される命令、動作、レジスタファイル、状態を実行するのに必要な論理装置のコストを含んでいる各命令セットアーキテクチャ構造のハードウェアコストの評価のガイドラインとして使用し、
各区域に対する各命令セットアーキテクチャ構造のハードウェアコストおよび性能の改良は、生成される命令セットアーキテクチャを共に記述する命令セットアーキテクチャ構造のセットを決定するために使用され、それによって生成される命令セットアーキテクチャのハードウェアコストは、性能の改良が性能目標以上でありながら、生成される命令セットアーキテクチャのハードウェアコストが可能な限り小さい請求項１９記載のシステム。
【請求項２２】
各区域に対する各命令セットアーキテクチャハードウェア構造のハードウェアコストおよび性能の改良は、生成される命令セットアーキテクチャを共に記述する各命令セットアーキテクチャ構造のセットを決定するために使用され、それによって生成される命令セットアーキテクチャのハードウェアコストは、性能の改良の予め定められた関数よりも小さい請求項１９記載のシステム。
【請求項２３】
特定の区域に対する特定の命令セットアーキテクチャにより行われる性能の改良は、
区域の変更された依存グラフで動作する命令スケジューリングアルゴリズムにより決定される請求項１８記載のシステム。
【請求項２４】
依存グラフは１よりも小さい動作幅を有する動作を複製するように変更される請求項２３記載のシステム。
【請求項２５】
依存グラフは単一のヒューズド演算により演算のグループを置換するように変更される請求項２３記載のシステム。
【請求項２６】
特定の区域の特定の命令セットアーキテクチャ構造により行われる性能の改良はリソース限度を使用して決定される請求項１９記載のシステム。
【請求項２７】
命令セットアーキテクチャの生成は、構造により表される命令、動作、レジスタファイル、状態を実行するのに必要な論理装置のコストを含んでいる各命令セットアーキテクチャ構造のハードウェアコストの評価をガイドラインとして使用する請求項２記載のシステム。
【請求項２８】
ハードウェコストは命令セットアーキテクチャ構造に存在するコンポーネントのハードウェアコストを付加することにより評価される請求項２７記載のシステム。
【請求項２９】
ハードウェアコストは特定化される演算が一般的な演算を置換するときに必要な減少された論理装置を表すために減少される請求項２７記載のシステム。
【請求項３０】
高レベル言語で書き込まれた少なくとも１つのソフトウェアプログラムを受信する手段と、
前記少なくとも１つのプログラムの解析に基づいて既存の命令セットアーキテクチャの命令へ１以上の新しい拡張命令を付加することにより前記少なくとも１つのプログラムを実行するために最適化された命令セットアーキテクチャを自動的に生成する手段とを具備し、
新しい命令は既存の命令のベクトル化されたバージョンを含んでいるシステム。
【請求項３１】
高レベル言語で書き込まれた少なくとも１つのソフトウェアプログラムを受信する手段と、
前記少なくとも１つのプログラムの解析に基づいて１以上の新しいレジスタファイルを付加することにより前記少なくとも１つのプログラムを実行するために最適化された命令セットアーキテクチャを自動的に生成する手段とを具備し、
新しいレジスタファイルは既存の標準または既存のユーザ規定命令セットアーキテクチャのベクトル化されたバージョンであるシステム。
【請求項３２】
高レベル言語で書き込まれた少なくとも１つのソフトウェアプログラムを受信する手段と、
前記少なくとも１つのプログラムの解析に基づいて既存の命令セットアーキテクチャ中の命令へ１以上の新しい拡張命令を付加することにより前記少なくとも１つのプログラムを実行するために最適化された命令セットアーキテクチャを自動的に生成する手段とを具備し、
新しい命令は既存の標準または既存のユーザ規定命令セットアーキテクチャの特別化されたバージョンを含んでいるシステム。
【請求項３３】
高レベル言語で書き込まれた少なくとも１つのソフトウェアプログラムを受信する手段と、前記少なくとも１つのプログラムの解析に基づいて既存のめいれーセットアーキテクチャの命令へ１以上の新しい拡張命令を付加することにより前記少なくとも１つのプログラムを実行するために最適化された命令セットアーキテクチャを自動的に生成する手段とを具備し、
単一の新しい命令は既存の標準または既存の命令セットアーキテクチャのユーザ規定命令のヒューズド、特定化、ベクトル化の組合わせのうちの１つを含んでいるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルコンピュータシステム、特にデジタルコンピュータシステムにおけるプログラマ可視特徴の自動仕様に関する。
【背景技術】
【０００２】
命令セットアーキテクチャ（ＩＳＡ）はプログラマに可視にされるプロセッサの命令、演算、レジスタファイルを記述している（Hennessy、Computer Architecture、A Quantitative Approach、第２版、第２章）。汎用目的のプロセッサのＩＳＡは広範囲の種々のアプリケーションで合理的なレベルの性能を提供するように設計されている。対照的に、埋設または特定用途用プロセッサのためのＩＳＡはこれらのアプリケーションの性能を可能な限り改良する目的のためにまたは最小の性能要求を満たすため特別なセットのアプリケーションに対して設計される。例えば、ビデオストリームを復号するアプリケーションの性能はビデオが実時間で復号される最小の要求を満たさなければならない。したがってアプリケーションを復号するビデオストリームを実行するプロセッサに対して設計されるＩＳＡはそれが他のアプリケーションに対して提供する性能レベルにかかわりなくアプリケーションにより必要とされる最小の性能レベルを提供しなければならない。
【０００３】
同時に、ＩＳＡの構成に必要とされるプロセッサハードウェアのコストを最小にすることが望ましい。したがって、ＩＳＡ設計者はＩＳＡを構成するためのプロセッサハードウェアコストに対して必要とされるアプリケーション性能をバランスしなければならない。
【０００４】
ＩＳＡを設計するとき、設計者は幾つかの技術を使用でき、各潜在的な性能の改良とハードウェアコストとの間で異なる妥協条件を有する。これらの技術は非常に長い命令ワード（ＶＬＩＷ）（Hennessy、Computer Architecture、A Quantitative Approach、第２版、セクション4.4、284-285頁）と、ベクトル演算（Hennessy、Computer Architecture、A Quantitative Approach、第２版、付録Ｂ）と、ヒューズド演算および特定化を含んでいる。
【０００５】
Ａ．ＶＬＩＷ
ＶＬＩＷ技術は、単一の命令が多数の独立した演算を含むことを可能にする。ＶＬＩＷ命令は複数のスロットに区分され、各スロットは１つの演算動作を含んでいる。ＶＬＩＷ命令の記述は単に各スロットで行われることができる動作の特定を必要とする。例えば、２つのスロットのＶＬＩＷ命令は第１のスロットのロード動作が第２のスロットにおける乗算演算を可能にする。
【０００６】
ＩＳＡがＶＬＩＷを使用するように設計されるならば、ソース言語のコンパイラ（例えばＣまたはＣ＋＋コンパイラ）は多数の動作を単一のＶＬＩＷ命令へパックするためにソフトウェアパイプライン化および命令スケジュール化技術を使用でき、これは性能を非常に増加する可能性を有する（Lam、“Software Pipelining : An Effective Scheduling Technique for VLIW Machines”、Proceedings of the SIGPLAN 1988 Conference on Programming Language Design and Implementation ; Krishnamurthy、“A Brief Survey of Papers on Scheduling for Pipelined Processors”、“SIGPLAN Notices、25巻、＃７、1990年７月”）。しかしながら、ＶＬＩＷを使用するためにＩＳＡを設計することはＶＬＩＷを使用しないＩＳＡと比較してハードウェアコストを増加する。ＶＬＩＷ命令は多数の独立した動作を並列して発生し、実行するので、ハードウェアは多数の並列デコーダを含まなければならない。また、同一のＶＬＩＷ命令内の多数の演算動作が同じレジスタファイルをアクセスするならば、そのレジスタファイルは全ての可能なアクセスを満たすのに十分なポートを含まなければならない。さらに、ＶＬＩＷ命令により動作の多数のインスタンスが命令中に現われることが可能であるならば、その動作を実行するのに必要なハードウェアは動作の多数のインスタンスが並列で実行できるように複製されなければならない。
【０００７】
したがって、各ＶＬＩＷ命令のスロット数、各ＶＬＩＷ命令の動作を満足するのに必要なレジスタファイルポートの数、各ＶＬＩＷ命令で可能にされる動作の組合わせは、命令により与えられる性能の改良と、命令を実行するのに必要な論理装置のハードウェアコストとの両者に影響する。例えば整数の加算演算が両スロットで行われることを可能にする２スロットＶＬＩＷ命令は、整数レジスタファイルが少なくとも４つの読取りポート（各加算は入力として２つの整数のレジスタを必要とする）と、少なくとも２つの書込みポート（各加算は１つの整数レジスタに結果を生成する）を有することを必要とし。さらに加算論理の２つのコピーを必要とする。付加的な復号論理装置、レジスタファイルポート、加算論理装置は非ＶＬＩＷ命令と比較して著しくハードウェアの価格を増加するが、ハードウェアコストは２つの命令を並列して実行できるならば正当化され、アプリケーションの性能を著しく増加する。
【０００８】
ＶＬＩＷ命令を含むＩＳＡの設計を簡単にするため、従来技術のＰＩＣＯシステム（Aditya、“Automatic Architectural Synthesis of VLIW and EPIC Processors ”、Proc, International Symposium on System Synthesis、ISSS’99、サンジョセ、カリフォルニア州、1999年、107-113頁）はＶＬＩＷプロセッサのスペースをサーチしてそれぞれのコストと性能を評価することによりアプリケーションから自動的にＶＬＩＷ  ＩＳＡを生成する。ＰＩＣＯによりサーチされる設計スペース内では、ＶＬＩＷプロセッサはレジスタファイルの寸法およびタイプ、動作、命令での動作の可能にされた組合わせを特徴とする。サーチ結果を使用して、設計者は性能およびハードウェアコストの要求を満たすＶＬＩＷ  ＩＳＡを選択できる。
【０００９】
Ｂ．ベクトル演算
ベクトル演算技術は１よりも多数のデータエレメントで一度に演算するベクトル演算を生成することによりデータスループットを増加する（ベクトル演算はＳＩＭＤ演算とも呼ばれる）。ベクトル演算は各データエレメントで行う演算、並列で動作するデータエレメント数、即ちベクトルの長さとにより特徴づけられる。
【００１０】
例えば、４幅ベクトルの整数の加算演算はそれぞれ４つの整数を含んでいる２つの入力ベクトルを加算し、４つの整数を含んでいる単一結果のベクトルを生成する。ＩＳＡがベクトル演算を使用するように設計されているならば、ソース言語コンパイラは、１以上のアプリケーションループの性能を大きく増加するために、自動並列化およびベクトル化技術を使用することができる（Wolfe、Optimizing Supercompilers for Supercomputers、MIT Press、Cambridge、MA、1989年；Zima、Hans、Supercompilers for Parallel and Vector Machines、ACM Press/Addison-Wesley、Reading、MA、1991年）。しかしながら、ＶＬＩＷでは、ベクトル演算は多数のデータエレメントでの演算を並列に行うことができる論理を必要とするので、ベクトル演算を使用してハードウェアコストを増加する。また、ベクトル演算はデータエレメントのベクトルを保持できるベクトルレジスタファイルを必要とする。
【００１１】
例えば、４幅ベクトル整数の加算は４整数加算を並列で実行するために論理装置を必要とし、４整数値のベクトルを保持できるベクトルレジスタファイルを必要とする。したがって、ベクトル演算を使用するためのＩＳＡの設計は設計者が１組のベクトル演算と、ベクトル演算により演算されるデータエレメントの数と、ベクトル演算によりアクセスされるベクトルレジスタファイル中のレジスタ数を決定することを必要とし、それによって、所望のアプリケーション性能はハードウェアのコストに対して平衡される。ベクトル演算を使用するＩＳＡの設計を簡単にするために、ハードウェアコストを平衡しながらアプリケーション性能を改良するベクトル演算を行うことのできる自動ＩＳＡ生成システムが技術で必要とされている。
【００１２】
Ｃ．ヒューズド（Fused）演算
ヒューズド演算は幾つかの簡単な演算からなる演算を行う技術である。ヒューズド演算技術はヒューズド乗算―加算（Hennessy、Computer Architecture、A Quantitative Approach、第２版、セクションＡ．７）と類似しているが、ヒューズド乗算―加算と異なって、ヒューズド演算の意味論は簡単な演算の意味論の構成と同一である。
【００１３】
簡単な演算の代りにヒューズド演算を使用すると、コードのサイズと発生帯域幅を減少し、レジスタファイルポートの要求を減少する。またヒューズド演算の待ち時間は簡単な演算の組み合わされた待ち時間よりも少ない。ヒューズド演算の１例はTensilicaのXtensa Architectureに存在する１による加算とシフトの演算である（Xtensa Instruction Set Architecture Reference Manual、第５章、170頁）。１による加算およびシフトは１ビットだけ左に値をシフトし、その後それを別の値に加算し、したがって左シフト演算と加算演算から構成されるヒューズド演算である。１つの１による加算およびシフト演算は２つのさらに簡単な演算を置換し、単一のサイクルで実行する。
【００１４】
ヒューズド演算の使用はヒューズド演算が付加的な論理を必要とするならば、またはヒューズド演算がそのオペランドにアクセスするために付加的なレジスタファイルを必要とするならば、ハードウェアコストを増加する。共にアプリケーションのセットにわたって性能の改良を行うヒューズド演算のセットの決定と、ヒューズド演算を実行するためにハードウェアコストに対するその性能の改良を平衡することは困難な仕事である。したがって、ヒューズド演算を使用するＩＳＡの設計を簡単にするために、ハードウェアコストを平衡しながらアプリケーション性能を改良するヒューズド演算を生成できる自動ＩＳＡ生成システムが技術で必要とされている。
【００１５】
Ｄ．特定化
特定化は元の演算よりも小さい値の範囲の１以上のオペランドを常に使用する演算を行う技術である。例えば、１６ビットの乗算演算は定数による乗算に特定化されてもよく、あるいはアプリケーションがもとの演算の一般性全体を必要としないならば８ビット乗算に特定されてもよい。演算はさらに限定された入力のセットで動作するので、特定化された演算を実行するのに必要な論理はもとの演算で必要とされる論理よりも非常に簡単である傾向にある。
【００１６】
例えば、常に３による乗算を行う特定化された乗算演算は一般的な乗算演算よりも必要とする論理装置が非常に少ない。しかしながら、アプリケーションは特定化されたバージョンに加えて演算の一般的なバージョンを必要とし、したがって特定化された演算の付加はハードウェアコストを増加する。一定のオペランドが演算の実行前にレジスタにロードされる必要はないので、特定化された演算は性能を増加できる。
【００１７】
例えば、通常の乗算演算により３による乗算を行うためには、特定化された３による乗算演算がレジスタロードで必要とされずに、レジスタに定数“３”がロードされ、その後乗算に入力されることを必要とする（乗算は入力で２のレジスタを読取ることを仮定する）。
【００１８】
アプリケーションのセットにわたって性能の改良を共に行う特定化された演算のセットを決定し、特定化された演算を実行するためにハードウェアコストに対してその性能改良を平衡することは困難な仕事である。したがって、特定化された演算を使用するＩＳＡの設計を簡単にするために、ハードウェアコストを平衡しながらアプリケーション性能を改良する特定化された演算を生成できる自動ＩＳＡ生成システムが技術で必要とされている。
【発明の開示】
【発明が解決しようとする課題】
【００１９】
所定のハードウェアコストの最大の性能改良を獲得するために、または所定の性能改良のハードウェアコストを最小にするために、設計者はベクトル演算、ヒューズド演算、特定化演算、およびこれらの技術を組合わせる演算（例えば、４つの整数の２ベクトルにおいて４つの並列の３累算による乗算計算を行うことができ、４つの整数の結果ベクトルを発生する単一の演算）を含むことができるＩＳＡを考慮しなければならない。さらに、設計者は多数の独立した演算が並列に発生され実行されることを可能にするＶＬＩＷの使用を考慮しなければならない。同時に、アプリケーション性能がハードウェアコストに対して平衡されるようにＩＳＡを設計することが極めて困難であるときの全ての４つの技術を考察する。したがって、ハードウェアコストを平衡しながらアプリケーション性能を改良するＩＳＡを生成するため、ＶＬＩＷ、ベクトル演算、ヒューズド演算、特定化演算を使用する自動ＩＳＡ生成システムが技術で必要とされている。
【課題を解決するための手段】
【００２０】
従来技術の前述の問題を考慮すると、本発明の好ましい実施形態は、ハードウェアコストを設計者の特定された限度より下に維持しながらアプリケーションのセットの性能を増加する目的または所定の必要なレベルの性能が与えられたハードウェアコストを最小にする目的により、ＶＬＩＷ命令、ベクトル演算、ヒューズド演算、特定化演算を潜在的に使用する。
【発明を実施するための最良の形態】
【００２１】
本発明の１実施形態のこれらおよび他の特徴は、添付図面を参照とする以下の好ましい実施形態の詳細な説明を読むことにより良好に理解されるであろう。
本発明の好ましい実施形態は自動的に、ハードウェアコストを設計者の特定された限度より下に維持しながらアプリケーションのセットの性能を増加する目的または所定の必要なレベルの性能が与えられたハードウェアコストを最小にする目的により、ＶＬＩＷ命令、ベクトル演算、ヒューズド演算、特定化演算を潜在的に使用する命令セットアーキテクチャ（ＩＳＡ）を生成する。
【００２２】
本発明はオリジナル演算のセットからのＩＳＡにより実行される演算を得る。好ましい実施形態では、オリジナル演算は、Ｘｔｅｎｓａ  ＩＳＡの構造のようなオリジナルＩＳＡでアプリケーション言語をサポートするのに必要な演算を含んでおり、またユーザにより明白に規定される演算を含んでもよい。好ましい実施形態では、ユーザはKillianの米国特許第6,282,633号明細書と、米国特許出願第09/246,047号および第09/506,502号明細書に記載されているようにTensilica Instruction Extension(TIE)Languageを使用して新しい演算を規定し、これらの全ての特許明細書はここで参考文献とされている。ＴＩＥの更なる情報については、http://www.tensilica.com/technology_pdf.pdf.html.で入手可能なTensilica Application Specific Microprocessor Solutions Overview Handbookの第４章を参照する。本発明は以下説明するように、ベクトル演算、ヒューズド演算、特定化技術をオリジナル演算に適用することにより新しい演算を生成する。本発明はその後、１以上のオリジナルまたは新しい演算からなる新しい命令を生成するためにＶＬＩＷを使用する。
【００２３】
１．演算のクラス
本発明はオリジナルまたは新しい演算を演算クラスにグループ化する。理想的に、演算クラスは共有されたハードウェアで実行され、同一のレジスタファイルリソースを必要とする演算を表している。例えば３２ビット整数加算演算と３２ビット整数減算演算の両者は２つの入力レジスタを読取り、単一の出力レジスタを書き込む。また、加算および減算演算を実行するために必要とするほとんどの論理装置は共有され、したがって加算および減算演算は同一の演算クラスに置かれなければならない。しかしながら本発明はその演算クラスがこの方法で形成されることを必要としない。好ましい実施形態では、以下の演算クラスが使用される。
【００２４】
ＭＥＭＯＲＹ：この演算クラスはユーザ規定ロードおよび記憶装置を含むメモリをアクセスする全てのオリジナル演算を含む。ＭＥＭＯＲＹ演算クラスはまたベクトル演算、ヒューズド演算および／または特定化技術を使用してオリジナルのメモリ演算から生成される新しい演算を含んでいる。
【００２５】
ＵＳＥＲ，ＵＳＥＲ’，ＵＳＥＲ’’，．．．．：これらの演算クラスはユーザ規定ロードおよび記憶装置を除く全てのオリジナルユーザ規定演算と、ベクトル演算、ヒューズド演算および／または特定化技術を使用するユーザ規定演算から生成される全ての新しい演算を含んでいる。ＭＥＭＯＲＹクラス演算とＵＳＥＲクラス演算の両者からなるヒューズド演算はＵＳＥＲクラスには含まれない。全てのユーザ規定演算はそれらのオペランド使用に基づいて異なるＵＳＥＲクラスに区分され、それによって同一のオペランド使用を有する全てのユーザ規定演算は同一のＵＳＥＲ演算クラスに置かれている。
【００２６】
ＭＵＬＴ：この演算クラスはユーザ規定演算を除外して乗算を行う全てのオリジナル演算を含んでいる。演算クラスはまたベクトル演算、ヒューズド演算、特定化技術を使用してオリジナル乗算演算から生成された全ての新しい演算を含んでいる。ＭＥＭＯＲＹクラス演算および／またはＵＳＥＲクラス演算、ＭＵＬＴクラス演算の両者からなるヒューズド演算はＭＵＬＴクラスに含まれない。
【００２７】
ＡＬＵ：この演算クラスはＭＥＭＯＲＹ、ＭＵＬＴまたはＵＳＥＲ演算クラスに含まれない全てのオリジナルおよび新しい演算を含んでいる。このようなオリジナル演算の例は加算、減算、シフト等である。
【００２８】
各演算は１以上のタイプにより表される値を生成および消費する。オリジナル演算はオリジナルタイプを生成し消費する。オリジナルタイプはアプリケーションプログラミング言語で組込みタイプ、または従来技術のＴＩＥ  ｃｔｙｐｅ構造を有する好ましい実施形態では特定化されるユーザ規定タイプを表す。好ましい実施形態では、アプリケーションはＣおよびＣ＋＋プログラミング言語で表され、組込みタイプはｃｈａｒ、ｓｈｏｒｔ、ｉｎｔ、ｌｏｎｇおよびｆｌｏａｔ、ｄｏｕｂｌｅのバリエーションでサインされ、またはサインされない。演算クラスのオリジナル演算は幾つかのタイプのみで演算するようにユーザによりマニュアルで制限される。例えばアプリケーションがｆｌｏａｔまたはダブル値での演算を必要としないならば、これらの演算は演算クラスから除去され、演算クラスを実行するために必要なハードウェアを減少する。
【００２９】
本発明により生成される新しい演算はオリジナルタイプと新しいタイプの両者を生成し消費する。新しいタイプは本発明により生成され、オリジナルタイプのベクトルバージョンを表すために使用される。例えば新しいタイプは４つのｉｎｔのベクトルを表すために生成される。オリジナルｉｎｔタイプを消費するオリジナル加算演算から、本発明は４つのｉｎｔのベクトルを表す新しいタイプを消費する新しい４幅ベクトル加算演算を生成することができる。
【００３０】
各オリジナルタイプはレジスタファイルに含まれている。多数のタイプは同一のレジスタファイルを共有する。好ましい実施形態では、１つのレジスタファイルは全てのオリジナル組込み整数タイプ（サインされたまたはサインされていないｃｈａｒ、ｓｈｏｒｔ、ｉｎｔ、ｌｏｎｇ）を保持するために使用され、１つのレジスタファイルは全てのオリジナル組込みのリアルタイプ（ｆｌｏａｔ、ｄｏｕｂｌｅ）を保持するために使用される。好ましい実施形態では、各オリジナルユーザ規定タイプでは、ユーザは従来技術のＴＩＥ  ｒｅｇｆｉｌｅ構造を使用してタイプを含むレジスタファイルを特定する。
【００３１】
各新しいタイプは以下説明するように、本発明により作成される新しいレジスタファイルに含まれる。好ましい実施形態では、１つの新しいレジスタファイルは生成されるならば組込み整数タイプのベクトルバージョンを表す全ての新しいタイプを保持するように生成され、１つの新しいレジスタファイルは生成されるならば組込みリアルタイプのベクトルバージョンを表す全ての新しいタイプを保持するように生成される。本発明はまたユーザ規定レジスタファイルに含まれるユーザ規定タイプのベクトルバージョンを保持するために各ユーザ規定レジスタファイルの１つの新しいレジスタファイルを生成する。
【００３２】
以下の例では、ＭＵＬＴＩおよびＡＬＵクラスは整数タイプ（即ちサインされたまたはサインされていないｃｈａｒ、ｓｈｏｒｔ、ｉｎｔ、ｌｏｎｇ）で演算するオリジナル演算を含むがリアルタイプ（即ちｆｌｏａｔ、ｄｏｕｂｌｅ）で演算するオリジナル演算を含まないことが仮定される。１つのユーザ規定演算ＭＵＬ２４を含み、２４ビット整数を表すユーザ規定されたｉｎｔ２４タイプの２つの値を乗算し、ｉｎｔ結果を生成する単一のＵＳＥＲクラスが存在する。ＭＥＭＯＲＹクラスは整数タイプおよびｉｎｔ２４タイプをロードし記憶するためオリジナル演算を含んでいる。
【００３３】
２．ＩＳＡ構造
ＩＳＡの特性は１以上のＩＳＡ構造により説明される。ＩＳＡに含まれる演算、命令、レジスタファイルはＩＳＡを作る各ＩＳＡ構造により必要とされる演算、命令、レジスタファイルのユニオンである。好ましい実施形態では、ＩＳＡ構造は以下のパラメータから構成される。
【００３４】
１．ベクトル長（ＶＬ）。可能な値はゼロよりも大きい整数である。このパラメータは構造により表される演算のベクトル幅を示し、したがって各ベクトルエレメントに含まれる複数のスカラエレメントを与える。ＶＬ＝１は演算が単一のスカラで演算することを示しており、即ち構造はベクトル演算を使用しない。
【００３５】
２．発行幅（ＩＷ）。可能な値はゼロよりも大きい整数である。このパラメータは各ＶＬＩＷ命令中に含まれることができる演算数を示す。ＩＷ＝１は各命令が単一の演算を含んでいることを示しており、即ち構造はＶＬＩＷを使用しない。
【００３６】
３．演算クラス（ＯＣ）。構造により実行される１以上の演算クラスのセットである。構造が演算クラスを実行するならば、構造は演算クラスの全ての演算をサポートし、これらの動作を実行するのに必要なハードウェアを含んでいる。
【００３７】
４．命令−テンプレートセット（ＩＴＳ）。共に全ての可能な方法の演算クラスを記述する１以上の命令テンプレートのセットはＶＬＩＷ命令に結合されることができる。各命令テンプレートは各命令スロットの演算クラスを特定することにより１つの可能な組合わせを記述する。例えば命令テンプレートは、２つのスロットＶＬＩＷ命令がスロットゼロでメモリ演算を有することができ、スロット１の乗算演算は｛ＭＥＭＯＲＹ，ＭＵＬＴ｝であることを示す。命令−テンプレートセットは全ての可能にされたテンプレートを示し、したがってＩＴＳ＝｛｛ＭＥＭＯＲＹ，ＭＵＬＴ｝，｛ＡＬＵ，ＡＬＵ｝｝は各命令がメモリ演算および（それぞれスロットゼロと１の）乗算演算を含むことができ、または（各スロットで１の）２つのＡＬＵ演算を含むことができる。
【００３８】
５．演算幅（ＯＷ）。可能な値は１／ｎであり、ここで‘ｎ’はＶＬの係数である。各演算クラスに対しては、このパラメータは演算により演算されるベクトルのエレメントの分数を示している。例えば、ベクトル長４の構造では、ベクトルの各エレメントで１の全（ＯＷ＝１）幅の乗算は並列して４乗算を行う。半（ＯＷ＝０．５）幅乗算は並列で２乗算を行い、ベクトルで４エレメントの２のみで演算する（したがって２つの乗算演算は全部で４つのエレメントを乗算するために実行されなければならない）。
【００３９】
６．結合された演算セット（ＣＯＳ）。１以上の新しい演算のセットは以下説明するように、ヒューズド演算技術および／または特定化技術を使用して形成する。
【００４０】
例えば、図１で示されているｖｅｃ４構造は並列で４までのスカラエレメントを演算する演算セットを示しており、ＭＥＭＯＲＹクラスとＡＬＵクラスの演算は並列で全ての４つのエレメントで実行され、ＭＵＬＴクラスとＵＳＥＲクラスの演算は並列で２つのエレメントで実行される。構造は全ての演算クラスからの演算を含み、２つの演算は各命令で符号化されることを可能にし、可能にされた演算スロットの割当ては命令テンプレートにより示される。構造は結合された演算を実行しない。
【００４１】
ＩＳＡ構造を実行するのに必要なハードウェアは単に構造のパラメータにより説明される特徴を実行するのに必要なレジスタファイルと論理装置である。好ましい実施形態では、構造のハードウェアコストは演算発生および復号論理、演算実行論理、レジスタファイルエントリ、レジスタファイルポートのコストを含んでいる。
【００４２】
構造のＩＷとＩＳＴは、演算の復号および発行論理の並列インスタンスが必要とされる数を決定する。ＩＴＳ中の命令テンプレートは各復号器が復号できなければならない演算を示している。発行スロットの復号器は任意のテンプレートに対するスロットで現われる各演算クラスの全ての演算を復号しなければならない。ｖｅｃ４例では、スロット０の復号器はＭＥＭＯＲＹとＡＬＵクラスの演算を復号しなければならず、スロット１の復号器はＭＵＬＴ、ＡＬＵ、ＵＳＥＲクラスの演算を復号しなければならない。
【００４３】
構造のＶＬ、ＯＣ、ＩＴＳ、ＯＷは構造により必要とされる演算を実行するのに必要な論理を決定する。ＯＣはどの演算クラスか、したがってどの演算が構造の論理装置で実行されなければならないかを示す。ＶＬとＯＷは各演算が動作するデータエレメント数を示し、したがって実行論理が並列で行うべきである計算数を示す。ＩＴＳは並列で発行され実行されることができる演算クラスを示し、したがって各演算に対して必要とされる実行論理の並列インスタンスの数を示す。
【００４４】
例えば、ｖｅｃ４構造は全ての演算クラスを実行し、構造により必要とされるハードウェアは全ての演算クラスに含まれる全ての演算を実行するのに必要な論理装置を含んでいる。ＶＬ＝４およびＯＷ＝［ＭＥＭＯＲＹ］＝ＯＷ［ＡＬＵ］＝１であるので、ＭＥＭＯＲＹとＡＬＵ演算クラスの各演算は並列で４つのデータエレメントで演算し、したがって各演算を実行する論理は並列して４つの計算を実行しなければならない。ＶＬ＝４およびＯＷ［ＭＵＬＴ］＝ＯＷ［ＵＳＥＲ］＝０．５であるので、ＭＵＬＴとＵＳＥＲ演算クラスの各演算は並列で２つのデータエレメントで演算し、したがって各演算を実行する論理は並列で２つの計算を実行しなければならない。ｖｅｃ４構造の｛ＡＬＵ，ＡＬＵ｝テンプレートは２つのＡＬＵクラスの演算が同時に実行されることができ、したがって構造を実行することを必要とされる論理はＡＬＵクラスの演算で必要とされる論理の２つのコピーを含まなければならないことを示している。
【００４５】
構造のＩＷおよびＩＴＳは各レジスタファイルで必要とされるレジスタファイルポートの数を決定する。各レジスタファイルで必要とされるレジスタファイルポートの数は任意の命令テンプレートで生じることのできる演算により必要とされるポート数の最大数である。ｖｅｃ４例では、｛ＡＬＵ，ＡＬＵ｝テンプレートは２つのＡＬＵクラスの演算が同時に実行されることができることを示している。ＡＬＵ演算クラスの任意の演算により必要とされる大部分の整数レジスタファイルアクセスは２つの整数レジスタファイルの読取りと１つの整数レジスタファイルの書込みであると仮定すると、｛ＡＬＵ，ＡＬＵ｝テンプレートは４つの整数レジスタファイルの読取りポートと２つの整数レジスタファイルの書込みポートとを必要とする。全ての命令テンプレートにおける最大のレジスタフィルの要求は構造の要求である。
【００４６】
構造により必要とされる各レジスタファイルのエントリ数は以下説明するように、ＩＳＡが生成されるときに決定される。レジスタファイルのエントリ数が一度知られると、これらのレジスタファイルエントリのハードウェアコストは構造の最初のハードウェアコストに付加される。
【００４７】
３．新しいＩＳＡの生成および使用
本発明の好ましい実施形態は図２で示されているアプリケーションのセットデＩＳＡを生成するため以下のステップを行う。
【００４８】
１．潜在的にアプリケーションの性能を改良するために使用される全ての演算、命令、レジスタファイルを共に記述するＩＳＡ構造のセットを生成する。
【００４９】
２．前述したように、構造により必要とされる演算、命令、レジスタファイルを実行するために必要とされるハードウェアのコストを表す各構造へコストを割当て、
３．アプリケーションを解析し、生成されるＩＳＡが潜在的に性能の改良を行うアプリケーションの各区域についての情報を集める。
【００５０】
４．ＩＳＡ構造のセットの各構造に対して、構造により含まれる演算、命令、レジスタファイルにより与えられる性能の改良を決定するために各アプリケーション区域を評価する。必要ならば、ヒューズドおよび／または特定化演算を含み、それらをＩＳＡ構造のセットに添付して新しいＩＳＡ構造を生成する。
【００５１】
５．特定された予算よりも少ない価格のハードウェアを必要としながら、アプリケーション性能を最大にしようとするＩＳＡを共に規定し、または必要なレベルの性能を与えながらハードウェアコストを最小にしようとするＩＳＡを共に規定する１以上の構造を決定する。
【００５２】
６．ＩＳＡに必要なハードウェアを生成する。
【００５３】
４．ＩＳＡ構造の生成
本発明の好ましい実施形態はＶＬ、ＩＷ、ＯＣ、ＩＴＳ、ＯＷパラメータ値の全ての組合わせを列挙することによりＩＳＡ構造のセットを生成する。ヒューズドまたは特定された演算を含んだ構造は以下説明するように後に生成される（即ち各生成された構造のＣＯＳパラメータはエンプティである）。過度に多数の構造の生成を防止するために、可能にされたパラメータ値の制限はターゲットプロセッサの限定とユーザからの誘導に基づいて与えられる。例えば、発行幅は命令の各スロット中の演算のオプコードおよびオペランドを符号化するために必要とされるビット数により制限される。さらに、ターゲットプロセッサがせいぜい１つのメモリインターフェースを可能にするならば、ＭＥＭＯＲＹ演算クラスは命令テンプレートのせいぜい１つのスロットで生じることができる。
【００５４】
ＩＳＡ構造を自動的に生成する代わりとして、ユーザはまた考慮されるべき構造のセットを特別に選択してもよい。
【００５５】
ＳＣＡＬＡＲと呼ばれる特別なＩＳＡ構造は常に生成される。ＳＣＡＬＡＲは命令当りただ１つの演算を可能にし、スカラ演算だけを実行する命令を表している。ＳＣＡＬＡＲ構造は全ての他の構造が比較されるベースラインとして使用される。可能なＳＣＡＬＡＲ構造は図３に示されている。
【００５６】
各ＩＳＡ構造は構造を形成する命令、演算、レジスタファイルを実行するのに必要な論理装置のハードウェアコストを表す初期コストを割当てられる。ほとんどの正確なハードウェアコストは構造を構成するのに必要な論理装置を実際に生成し、結果的なハードウェアのサイズを測定することにより発見される。論理装置はＳｙｎｏｐｓｙｓ’  Ｄｅｓｉｇｎ  Ｃｏｍｐｉｌｅｒにより与えられるような論理合成技術を使用して自動的に生成されることができる。しかしながら、これは非常に時間を費やすので実際的ではない。代わりに典型的なハードウェアコストのデータベースは限定された数の構造の合成から集められることができる。
【００５７】
例えば、データベースは、加算器、乗算器、レジスタフィルポート、メモリインターフェースなどのコストを記録する。データベースを使用して、構造の最初のコストは、迅速に構造のコンポーネント部品のコストから評価されることができる。構造の最初のコストは任意の結合された演算のコストまたはレジスタフィルエントリのコストを含まない。これらのコストは以下説明するように後に構造へ付加される。
【００５８】
５．ＩＳＡ構造の利点の評価
本発明の好ましい実施形態は次に、アプリケーションの各区域について、各ＩＳＡ構造が与える利点とレジスタフィルの要求を決定する。好ましい実施形態では、区域は任意のループに含まれないコードのループネストまたは単一の基本ブロックである（Aho、Compilers : Principle, Techniques, and Tools、セクション9.4、528-529頁）。各構造に対して、利点はＳＣＡＬＡＲ構造に関連して、構造により可能にされるサイクルカウントの減少である。
【００５９】
各区域では、本発明はその区域の構造の利点全体を決定するために使用される解析情報を集める。解析情報は以下のものを含んでいる。
１．ＤＥＰ＿ＧＲＡＰＨ：区域中の演算の依存グラフ（Morgan、Building an Optimizing Compiler、242頁）。
【００６０】
２．ＥＸＥＣ＿ＣＮＴ：区域の実行カウント。好ましい実施形態では、実際の、または評価されたプロファイルまたユーザ供給指示から得られる場合の実行カウント（Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation）。実際のプロファイルはアプリケーションの実際の実行から集められ、評価されたプロファイルはループ構造およびアプリケーションの他の特性を検査することにより決定される。ユーザ供給指示は例えばプラグマを使用して区域の実行カウントを示すためにアプリケーションに挿入される。
【００６１】
３．ＶＬ：この区域の演算に使用されることができ潜在的に短い長さのベクトルと比較される性能改良を行うベクトル長のセット。本発明は従来技術の依存解析（Maydan、“An Efficient Method for Extract Data Dependence Analysis”、PLDI 1991年、1-14頁）と、ループ変換（Wolf、“Combining Loop Transformations Considering Cashes And Scheduling”、Proc.MICRO’961、274−286頁、1996年）と、区域がベクトル化されることができるか否かを決定するためベクトル化技術を使用し、それによってベクトル演算を使用できる。区域がベクトル化されることができるならば、ＶＬはその区域に使用されることができ、短いベクトルと比較して性能の改良を行うベクトル長を示す。区域がベクトル化されることができないならば、ＶＬ＝｛１｝であり、即ちベクトルではない演算だけがその区域で使用されることができる。
【００６２】
例えば、Ｃコードの区域および対応する依存グラフは図４のＡ乃至４のＢにそれぞれ示されている。コードは両者とも先に規定したユーザ規定されたｉｎｔ２４タイプとユーザにより規定されたＭＵＬ２４演算を使用する。ｌｏａｄ＿ｃｏｎｓｔインターフェース算は整数のレジスタを特定の定数値へ設定するＡＬＵクラス演算である。区域は１００回実行し、２幅または４幅ベクトルの演算を使用するためにベクトル化されることができる。
【００６３】
各区域では、好ましい実施形態は各ＩＳＡ構造の利点を評価するために解析情報を使用する。幾つかの構造はその区域を実行するのに必要な演算を行わず、単にネガチブな利点を割当てる。これらはその区域により必要とされる演算クラスを実行せず、または短いベクトル長と比較して改良された性能を与えないベクトル長を有する構造である。実施例の区域はユーザ規定されたＭＵＬ２４演算を含み、ＵＳＥＲ演算クラスを実行するＩＳＡ構造だけがその区域を実行するために使用されることができる。同様に、ＶＬ＝８を有する構造はＶＬ＝４ベクトルを有する点を除いて同一である構造と比較して何等性能改良を与えない。
【００６４】
構造がその区域を実行するために使用されることができるならば、その区域の構造により与えられる利点を決定する第１のステップは、その区域を実行するのに必要とされるサイクル数とその区域で必要とされるレジスタの最小数とを正確に決定する命令スケジューリングアルゴリズムを使用することである。好ましい実施形態は、ループを表す領域に対する任意の従来技術のソフトウェアパイプライニングアルゴリズムを使用し、他の領域に対しては任意の従来技術のスケジューリングアルゴリズムを使用する。
【００６５】
ソフトウェアパイプライニングまたはスケジューリングアルゴリズムの代わりとして、その区域を実行するようにリクエストされたサイクル数の評価はソフトウェアパイプライニングで行われるようにリソースのバウンドを使用して決定されることができる。スケジューリングアルゴリズムは最少数のサイクルでその区域を実行するために使用される命令を決定し、命令により演算される全ての値を保持するために必要なレジスタの最少数を決定する。
【００６６】
スケジューリングアルゴリズムを適用する前に、１よりも小さい演算幅を有する演算クラスに属す各演算は反復演算として実行されなければならないか、あるいは複製されなければならない。演算が反復演算として実行されるならば、同一の論理装置は結果の多数のパートを生成する。同一の論理装置は結果全体を生成するために反復して使用されるので、反復演算の待ち時間は非反復演算よりも長い。演算が複製されるならば、演算の複数バージョンが出力全体を生成するように作成される。演算の各バージョンは同一の入力を消費する。演算の各バージョンは同一の入力を消費するが、異なる出力部分を生成する。例えば、前述したような例示的なｖｅｃ４構造は半幅のＭＵＬ２４演算を実行する。したがって、４つのＭＵＬ２４のベクトルを計算するため、結果は２つの演算、即ち２つのベクトルエレメントを計算するＭＵＬ２４＿０演算と、他の２つのベクトルエレメントを計算するＭＵＬ２４＿１演算とを必要とする。
【００６７】
演算の全ての複製は同一の入力にしたがい、同一の出力の異なる部分を生成するので、依存グラフは入力オペランドと出力オペランドの間に依存チェーンを形成するように複製された演算を示すように変更される。例えば、ｖｅｃ４構造は図５で示されている変更された依存グラフを必要とする。
【００６８】
次に、スケジューリングアルゴリズムは変更された依存グラフに適用される。例えば、ＩＳＡ構造を有する従来技術のソフトウェアパイプライニングアルゴリズムを使用して、実施例の区域のｖｅｃ４は図６で示されている４サイクルスケジュールを生成する。このスケジュールは、ｖｅｃ４構造がスロット０のＭＥＭＯＲＹクラス演算がスロット１のＵＳＥＲまたはＡＬＵ演算とグループ化されることを可能にするので可能である。
【００６９】
ヒューズド演算および／または特定化技術の使用によりさらにサイクルカウントを減少することが可能である。ヒューズド演算技術は２以上の依存演算を新しいヒューズド演算に結合する。ヒューズド演算はオリジナル演算よりも少数の発行スロットしか必要ではなく、ヒューズド演算はオリジナル演算の総待ち時間よりも短い待ち時間を有するので、オリジナル演算の代わりにヒューズド演算を使用することによってサイクルカウントを減少させることができる。
【００７０】
依存演算の候補グループは依存グラフの任意の接続されたコンポーネントであり、ここではそのコンポーネントの演算は単一のヒューズド演算として実行されることができる。ヒューズド演算として実行されることができる演算の数およびクラスと、ヒューズド演算のオペランド数には制限が与えられる。演算クラスの限度はヒューズド演算により必要とされるハードウェアリソースを限定するために必要とされる。
【００７１】
例えば、ヒューズド演算のＭＥＭＯＲＹクラス演算を１に限定することは、ヒューズド演算の実行に必要なハードウェアがせいぜい１つのメモリインターフェースしか必要としないことを保証する。オペランド数はヒューズド演算がそれに対して可能にされたビットで符号化されることができることを確実にするために限定されることができる。演算で利用可能なビット数は命令のサイズと、構造のＩＷ（即ち命令で符号化される演算数）に依存する。この例では、ヒューズド演算はせいぜい１つのＭＥＭＯＲＹクラス演算を含むように限定され、ＭＵＬＴ、ＡＬＵ、ＵＳＥＲクラスの演算数に限度がなく、せいぜい４のオペランドに限定されると仮定する。
【００７２】
実施例の依存グラフでは、全ての演算を含んでいる依存グラフの接続されたコンポーネントが存在するが、全ての演算を単一のヒューズド演算に結合することは多数のＭＥＭＯＲＹクラス演算を必要とする。これは１つのＭＥＭＯＲＹクラス演算の限度を超過するので、その接続されたコンポーネントは候補として考慮されない。同様に、他の接続されたコンポーネントは考慮から除外されることができる。
【００７３】
各候補ヒューズド演算では、依存グラフは候補ヒューズド演算を使用するように変更され、その後、演算が任意のサイクル減少を行うか否かを決定するために再スケジュールされる。好ましい実施形態では、ヒューズド演算の待ち時間は各演算を行う論理装置により必要とされる時間を保持し、演算を復号する時間またはオペランドの読取りまたは書込みをするための時間を含まないデータベースから決定される。ヒューズド演算に必要な時間はヒューズド演算を表す依存グラフのコンポーネントの任意の依存チェーンに沿った演算に必要な時間と、演算を復号しオペランドを読取り書き込むための時間との和の最大値である。サイクル減少を行う各ヒューズド演算では、ＩＳＡ構造のコピーが生成され、ヒューズド演算は構造の結合された演算セットに付加され、構造のコストはヒューズド演算のコストにより増加される。各ヒューズド演算のコストはＩＳＡ構造のコストと同じ方法で決定される。好ましい実施形態では、コンポーネントハードウェアコストのデータベースは調べられ、ヒューズド演算のコストは組立てられる演算のコストの和である。例えば、ｖｅｃ４構造を有する例示的な依存グラフを使用して、図７で示されている依存グラフの接続されたコンポーネントは候補のヒューズド演算を表す。ヒューズド演算の待ち時間は１サイクルである。
【００７４】
ヒューズド演算と結果的なスケジュールを使用するように変更された依存グラフは図８のＡおよびＢに示されている。ヒューズド演算の使用はサイクルカウントを４から３に減少し、ＩＳＡ構造のコピーが生成され、ヒューズド演算はＩＳＡ構造コピーに付加され、ＩＳＡ構造コピーのコストはヒューズド演算のコストを含むように増加される。
【００７５】
ＳＣＡＬＡＲ構造が図４のＡに示されている区域に対する６サイクルスケジュールを必要とすると仮定すると、図８のＢに示されているスケジュールは３サイクルの改良を与える。付加的なサイクルの減少は構造がその区域の実行頻度を減少するようにベクトル演算を使用するならば実現される。例えば、ｖｅｃ４構造は長さ４のベクトルで演算するので、例示的な区域のループは１００の代わりに２５回のみ実行しなければならず、命令はＳＣＡＬＡＲ構造の４分の１だけ実行される。各構造の利点はＳＣＡＬＡＲ構造に関して構造のサイクルカウントを取ることにより発見される。
【００７６】
スケジューリングアルゴリズムはまた各タイプに必要とされるレジスタの最少数を決定する。全ての区域にわたって各タイプで必要なレジスタの最大数は各構造で記録される。また、各構造のコストはその構造で必要なレジスタのコストを考慮するために増加される。
【００７７】
各区域の各構造の利点を見つけた後、各構造は、１以上の定数値または小さい範囲の値で演算する１による一般的な演算の置換によって、特定化技術は構造のハードウェアコストを減少するのに使用されることができるか否かを見るために再度検査される。各構造では、特定化技術は候補の特定化された演算を見つけるために各区域の依存グラフを検査する。１以上の入力が定数または小さい範囲の値である依存グラフの任意の演算は特定化候補である。例えば図５の（Ａ）で示されている依存グラフは図９の依存グラフにより表される候補の特定化された演算を有する。
【００７８】
特定化候補は、特定化された演算による演算の一般的なバージョンを置換するならばハードウェアコストを減少する。したがって特定化候補の一般的な演算はどの区域でも必要とされないならば、一般的な演算は特定化された演算により置換されることができ、潜在的にハードウェアコストを減少することができる。例えば、図９の依存グラフにより表される特定化候補は、ヒューズド（ｓｔｏｒｅ  ｃ［ｉ］，ａｄｄ）演算の一般的なバージョンを区域が必要としないならば、潜在的にハードウェアコストを減少する。
【００７９】
一般的な演算が特定化される演算により置換されることができるならば、ＩＳＡ構造のコピーが生成され、特定化された演算は構造の結合された演算セットに付加され（通常の演算がヒューズド演算であるならば対応するヒューズド演算を置換し）、構造のコストは特定化された演算および対応する一般的な演算のコスト間の差だけ減少される。例えばヒューズド（ｓｔｏｒｅ  ｃ［ｉ］，ａｄｄ）演算の一般的なバージョンがどの区域によっても必要とされないと仮定すると、特定化されたヒューズド（ｓｔｏｒｅ  ｃ［ｉ］，ａｄｄ  １２）演算により構造中で置換され、構造のコストは特定化および一般的演算のコストの差を考慮して減少される。
【００８０】
６．ＩＳＡを構成するＩＳＡ構造の決定
好ましい実施形態は、各ＩＳＡ構造におけるコストおよびレジスタの要求と、各区域でのその構造の性能の利点とを有する。次に、本発明は２つの以下の状態の一方が満たされるように１以上の構造の解のセットを集める。共に、解のセットの構造はＩＳＡを形成する。
【００８１】
１．ハードウェアコスト予算では、解のセットの構造の総価格が予算を超えない制約下で解のセットの構造の利点を最大にしようとする。
【００８２】
２．性能の利点の目標では、構造により与えられる利点が性能の利点の目標を満たすかそれを超える制約下で解のセット中の構造のハードウェアコスト全体を最小にしようと試みる。
【００８３】
（図１０でも示されている）以下のステップは、所定の価格予算を超えずに利点を最大にしようとするために使用される。
【００８４】
１．各構造に対して、各区域の構造により与えられる利益を合計することにより構造の総予算を計算する。
【００８５】
２．最大の総利点を有し、予算を超えないコストの構造、即ち構造ＭＡＸを解のセットに付加する（多数の構造が最大利点を有するならば、最小のコストを有するものを選択する）。
【００８６】
３．ＭＡＸ構造のコストにより予算を減少（デクリメント）する。
【００８７】
４．各残りの構造に対して、各区域の構造により与えられる予算を再計算するために、解のセットの構造により与えられる命令、演算、レジスタファイルもまた使用で利用可能であると仮定する。
【００８８】
５．残りの構造に対しては、解のセットの構造で必要とされる論理装置およびレジスタが既に存在するならば、その構造で必要とされる論理装置およびレジスタを構成するための増加コストを表すように構造のコストを減少する。好ましい実施形態では、構造の増加コストは解のセット構造に既に存在する構造のこれらのコンポーネントだけにコストをかけることにより発見される。前述したように、各コンポーネントのハードウェアコストはハードウェアコストのデータベースを使用して評価される。例えば、解のセットが４幅のＡＬＵ演算クラスを実行する構造を含んでいると仮定する。幾つかの構造Ａが１、２または４幅のＡＬＵ演算クラスを必要とするならば、論理装置は既に解のセットの構造により与えられているので、そのクラスで必要な論理装置のコストは構造Ａのコストから除去される。同様に、構造Ａが８幅のＡＬＵ演算クラスを必要とするならば、そのクラスに必要な論理装置のコストは４幅ＡＬＵ演算クラスに必要な論理のコストと、８幅ＡＬＵ演算クラスで必要とされる論理のコストとの間の差である。それ故、構造Ａ’のコストは８幅ＡＬＵ演算クラスの論理のハードウェアコストと増加コストとの間の差を考慮するために減少される。
【００８９】
６．残りのコスト予算がゼロよりも大きいならば、ステップ１へ進む。
【００９０】
（図１１でも示されている）以下のステップは利点の目標に到達またはそれを超えてコストを最小にしようとするために使用される。
【００９１】
１．各構造に対して、各区域の構造により与えられる利点を合計することにより構造の総利点を計算する。
【００９２】
２．利点の目標以上の利点を有する最低のコスト構造を選択する。利点の目標以上の大きい利点を有する構造がないならば、最大の利点を有する構造を選択する（多数の構造が最大の利点を有するならば、最小のコストを有する構造を選択する）。この構造、即ち構造ＭＩＮを解のセットへ付加する。
【００９３】
３．ＭＩＮ構造の利点による利点目標を減少する。
【００９４】
４．構造ＭＡＸに置換される構造ＭＩＮにおいて前述のステップ４と同一。
【００９５】
５．前述のステップ５と同一。
【００９６】
６．残りの利点目標が０よりも大きいならば、ステップ１へ進む。
【００９７】
７．ＩＳＡを記述するためのハードウェアの生成
解のセットは本発明が生成しているＩＳＡを共に記述するＩＳＡ構造のセットを示す。ＩＳＡを構成するために必要なハードウェアは特定されなければならない。このセクションは生成されたＩＳＡを構成するために生成されなければならないハードウェアの概要を説明する。
【００９８】
解のセットで各タイプを保持するのに必要なレジスタ数は解のセットの各構造の必要なレジスタ数の最大である。レジスタの要求は異なるタイプ間でのレジスタの共用を考慮するためにさらに結合される。例えば、好ましい実施形態では単一のレジスタファイルが全てのベクトル整数タイプに対して使用される。したがって、ベクトル整数レジスタファイル中のレジスタの数は任意の整数のベクトルタイプで必要とされるレジスタの最大数である。
【００９９】
各レジスタファイルエントリの幅は、そのレジスタファイルに含まれる最大のタイプの幅により決定される。例えば、ｖｅｃ４構造はベクトルの整数レジスタファイルが最大の整数のタイプ、即ちｌｏｎｇの４値を保持するのに十分な幅であることを必要とし、ベクトルユーザレジスタファイルが４つのｉｎｔ２４値を保持するのに十分な幅であることを必要とする。任意の区域で必要とされるベクトル整数レジスタの最少数が１６であり、任意の区域で必要とされるベクトルユーザレジスタの最少数が４であると仮定すると、ＩＳＡのハードウェアは４つの整数値のベクトル（即ち各エントリは１２８ビット）を保持するために１６のエントリベクトルレジスタファイルを構成しなければならず、４つのユーザ規定されたｉｎｔ２４値のベクトル（即ち各エントリは９６ビット）を保持するため４のエントリベクトルレジスタファイルを構成しなければならない。
【０１００】
各レジスタファイルで必要とされる読取りおよび書込みポートの数はＩＳＡを記述する全ての構造の命令テンプレートを検査することにより発見される。各レジファイルで必要とされるレジスタファイルの読取りおよび書込みポートの数は任意の命令テンプレートで行われることのできる演算により必要とされる読取りおよび書込みポートの数の最大数である。
【０１０１】
ＩＳＡのハードウェアは各構造により必要とされる演算を実行する論理装置を含んでいなければならない。例えば、ｖｅｃ４構造の論理装置は（ＶＬ＝４、ＯＷ［ＭＥＭＯＲＹ］＝ＯＷ［ＡＬＵ］＝１であるので）全てのＭＥＭＯＲＹおよびＡＬＵクラスの演算の４幅のベクトルバージョンを実行しなければならず、（ＶＬ＝４、ＯＷ［ＭＵＬＴ］＝ＯＷ［ＵＳＥＲ］＝０．５であるので）全てのＭＵＬＴとＵＳＥＲクラス演算の２幅ベクトルバージョンを実行しなければならない。
【０１０２】
前述の好ましい実施形態は単なる例示の目的で与えられ、本発明はこれらに限定されると解釈されるべきではない。本発明の変形はこの明細書を読んだ後、当業者により容易に明白になり、本発明の技術的範囲はこのような変形を含むことを意図している。
【図面の簡単な説明】
【０１０３】
【図１】本発明の１実施形態にしたがったｖｅｃ４構造を示す図。
【図２】本発明の１実施形態にしたがったフローチャート。
【図３】本発明の１実施形態にしたがったスカラ構造を示す図。
【図４】本発明の１実施形態にしたがったＣコード区域と、対応する依存グラフを示す図。
【図５】本発明の１実施形態にしたがった変更されたｖｅｃ４依存グラフ。
【図６】本発明の１実施形態にしたがった４サイクルスケジュールを示す図。
【図７】本発明の１実施形態にしたがったヒューズド演算の依存グラフ。
【図８】本発明の１実施形態にしたがった依存グラフおよびヒューズドグラフを使用する結果的なスケジュールを示す図。
【図９】本発明の１実施形態にしたがった特定化された演算の依存グラフ。
【図１０】本発明の１実施形態にしたがって、所定のコスト予算を超えずに、利点を最大にしようとすることに使用されるＩＳＡ設計プロセスを示す図。
【図１１】利点の目標に到達またはそれを超えながらコストを最小にしようとすることに使用されるＩＳＡ設計プロセスを示す図。
【図１】
2005507105.tif 000002
【図２】
2005507105.tif 000003
【図３】
2005507105.tif 000004
【図４】
2005507105.tif 000005
【図５】
2005507105.tif 000006
【図６】
2005507105.tif 000007
【図７】
2005507105.tif 000008
【図８】
2005507105.tif 000009
【図９】
2005507105.tif 000010
【図１０】
2005507105.tif 000011
【図１１】
2005507105.tif 000012
【国際公開パンフレット】
2005507105.tif 000013
2005507105.tif 000014
2005507105.tif 000015
2005507105.tif 000016
2005507105.tif 000017
2005507105.tif 000018
2005507105.tif 000019
2005507105.tif 000020
2005507105.tif 000021
2005507105.tif 000022
2005507105.tif 000023
2005507105.tif 000024
2005507105.tif 000025
2005507105.tif 000026
2005507105.tif 000027
2005507105.tif 000028
2005507105.tif 000029
2005507105.tif 000030
2005507105.tif 000031
2005507105.tif 000032
2005507105.tif 000033
2005507105.tif 000034
2005507105.tif 000035
2005507105.tif 000036
2005507105.tif 000037
2005507105.tif 000038
2005507105.tif 000039
2005507105.tif 000040
2005507105.tif 000041
2005507105.tif 000042
2005507105.tif 000043
2005507105.tif 000044
2005507105.tif 000045
2005507105.tif 000046
2005507105.tif 000047
【国際公開パンフレット（コレクトバージョン）】
2005507105.tif 000048
【国際調査報告】
2005507105.tif 000049
2005507105.tif 000050