(57)【特許請求の範囲】
【請求項１】
データ処理装置であって、前記データ処理装置は、ＶＬＩＷプロセッサであり、
マスタコントローラと、
スレーブコントローラを含む他のプロセッサを具え、相対的に長い待ち時間をもつ演算に対応する第１のタイプの命令を処理するように構成される第１の機能ユニットと、
相対的に短い待ち時間をもつ演算に対応する第２のタイプの命令を処理するように構成される第２の機能ユニットと、
を少なくとも有し、前記第１及び第２の機能ユニットが、共通メモリ手段を共有し、
前記第１の機能ユニットによる命令の実行の中に含まれる入出力操作を表すモデルが組み立てられ、
前記モデルに基づいて、前記第１の機能ユニットにより実行される命令のスケジュールが、前記第２の機能ユニットにより実行される命令のスケジュールを含むＶＬＩＷスケジュールに埋め込まれ、前記第２の機能ユニットに関する命令は、前記第１の機能ユニットが入力データが使用される命令を実行しているとき、前記第１の機能ユニットに前記入力データを供給し、及び／又は前記第１の機能ユニットが出力データが計算される命令を実行しているとき、前記第１の機能ユニットから前記出力データを取り出し、処理するようにスケジュールされる、データ処理装置。
【請求項２】
前記第１の機能ユニットの演算を一時停止させるための、前記マスタコントローラにより制御可能な停止手段を有する、請求項１に記載のデータ処理装置。
【請求項３】
データプロセッサ装置を動作させる方法であって、前記装置が、ＶＬＩＷプロセッサであり、
前記装置の演算を制御するためのマスタコントローラと、
スレーブコントローラを含む他のプロセッサを具え、相対的に長い待ち時間をもつ演算に対応する第１のタイプの命令を実行するように構成される第１の機能ユニットと、
相対的に短い待ち時間をもつ演算に対応する第２のタイプの命令を実行することができる第２の機能ユニットと、
を有し、
前記第１の機能ユニットによる命令の実行の中に含まれる入出力操作を表すモデルが組み立てられ、
前記モデルに基づいて、前記第１の機能ユニットにより実行される命令のスケジュールが、前記第２の機能ユニットにより実行される命令のスケジュールを含むＶＬＩＷスケジュールに埋め込まれ、前記第２の機能ユニットに関する命令は、前記第１の機能ユニットが入力データが使用される命令を実行しているとき、前記第１の機能ユニットに前記入力データを供給し、及び／又は前記第１の機能ユニットが出力データが計算される命令を実行しているとき、前記第１の機能ユニットから前記出力データを取り出し、処理するようにスケジュールされる、方法。
【請求項４】
前記マスタコントローラが、前記第１のタイプの命令の実行の間に、前記第１の機能ユニットの演算を一時的に停止させることを特徴とする、請求項３に記載の方法。
【請求項５】
請求項１に記載のデータ処理装置を動作させるようにプログラムを命令のシーケンスにコンパイルする方法であって、前記方法により、
第１の機能ユニットによる命令の実行の中に含まれる入出力操作を表すモデルが組み立てられ、
このモデルに基づいて、前記第１の機能ユニットにより実行される命令のスケジュールが、前記第２の機能ユニットにより実行される命令のスケジュールを含むＶＬＩＷスケジュールに埋め込まれ、１つ又は複数の前記第２の機能ユニットに関する命令は、前記第１の機能ユニットが入力データが使用される命令を実行しているとき、前記第１の機能ユニットに前記入力データを供給し、及び／又は前記第１の機能ユニットが出力データが計算される命令を実行しているとき、前記第１の機能ユニットから前記出力データを取り出すようにスケジュールされる、方法。
【請求項６】
前記モデルが信号フローグラフであることを特徴とする、請求項５に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ処理装置に関する。本発明は更に、データ処理装置を動作させる方法に関する。本発明は更に、プログラムをコンパイルする方法に関する。
【０００２】
【従来の技術】
今日の信号処理システムは、複数の規格を支援するとともに高い性能を与えるように設計されている。マルチメディア及びテレコミュニケーションは、このような組み合わせられた要求を満たすことができる典型的な分野である。高性能の要求は、特定用途向けハードウェアアクセラレータ有しうるアーキテクチャをもたらす。ＨＷ／ＳＷ協調設計（コデザイン）コミュニティにおいて、「マッピング」は、アプリケーションプログラムの機能を、利用可能なハードウェア構成要素により実行されうる演算の組に割り当てる問題に言及している［１］［２］。演算は、それらの複雑さに従って、細粒度演算及び粗粒度演算という２つのグループに分類される。
【０００３】
細粒度演算の例は、加算、乗算及び条件付きジャンプである。これらは、数クロックサイクルの中で実施され、一度にほんのわずかな数の入力値が処理される。粗粒度演算は、より多くのデータ量を処理し、例えばＦＦＴのバタフライ、ＤＣＴ又は複素数乗算という一層複雑な機能を実現する。
【０００４】
粗粒度演算を実現するハードウェア構成要素は、数サイクル乃至数百サイクルの待ち時間により特徴付けられる。さらに、ユニットにより消費され生成されるデータは、粗粒度演算の最後及び最初に集中しない。そうではなく、ユニットへ及びユニットからのデータのやり取りは粗粒度演算全体の実行の中で分散される。結果として、機能ユニットは、入出力の挙動に関する（複雑な）時間形状(timeshape)を呈する［９］。演算の粒度（粗さ）に従って、アーキテクチャは、２つの異なるカテゴリ、すなわち以下のように規定されるプロセッサアーキテクチャと、ヘテロジニアスマルチプロセッサアーキテクチャとにグループ化される。
【０００５】
−プロセッサアーキテクチャ：アーキテクチャは、ＡＬＵ及び乗算器のような機能ユニット（ＦＵ）のヘテロジニアスな集合からなる。このコンテクストにおける一般的なアーキテクチャは、汎用ＣＰＵ及びＤＳＰアーキテクチャである。例えばＶＬＩＷ及びスーパースカラアーキテクチャのようなこれらのいくつかのアーキテクチャは、複数の演算を並列に実行させることができる。ＦＵは、細粒度演算を実行し、データは、一般に「ワード」の大きさの粒度を有する。
【０００６】
−ヘテロジニアスマルチプロセッサアーキテクチャ：アーキテクチャは、バスを介して接続される専用の特定用途向け命令セットプロセッサ（ＡＳＩＰ）、ＡＳＩＣ並びに標準ＤＳＰ及びＣＰＵからなる。ハードウェアは、２５６入力のＦＦＴのような粗粒度演算を実行し、従って、データは、「ワードのブロック」の大きさの粒度を有する。このコンテクストにおいて、演算は多くの場合はタスク又はプロセスと考えられる。
【０００７】
上述した２つのアーキテクチャの方法は常に分離されていた。
【０００８】
【発明が解決しようとする課題】
本発明の目的は、（協調）プロセッサが、ＶＬＩＷプロセッサのデータパス内にＦＵとして埋め込まれ、ＶＬＩＷプロセッサが、異なる待ち時間をもつ演算を実行するとともに様々なデータ粒度を同時に扱うＦＵを有するデータ処理装置を提供することである。
【０００９】
本発明の他の目的は、このようなデータ処理装置を動作させる方法を提供することである。
【００１０】
本発明の他の目的は、スケジュールの長さ及びＶＬＩＷ命令幅を最小化しつつ、細粒度演算及び粗粒度演算の組み合わせを効率的にスケジュールするプログラムをコンパイルする方法を提供することである。
【００１１】
【課題を解決するための手段】
本発明によるデータ処理装置は、マスタコントローラと、スレーブコントローラをもつ第１の機能ユニットと、第２の機能ユニットとを少なくとも有し、前記第１及び第２の機能ユニットは、共通メモリ手段を共有し、前記装置は、前記第１の機能ユニットによる命令を実行するようにプログラムされ、前記命令の実行は、第１の機能ユニットによる入出力操作を含み、第１の機能ユニットの出力データは、前記実行の間に第２の機能ユニットにより処理され、及び／又は入力データは、前記実行の間に第２の機能ユニットにより生成される。
【００１２】
第１の機能ユニットは、例えば特定用途向け命令セットプロセッサ（ＡＳＩＰ）、ＡＳＩＣ、標準ＤＳＰ又はＣＰＵである。第２の機能ユニットは、一般に、ＡＬＵ又は乗算器のような細粒度演算を実行する。第１及び第２のユニットにより共有される共通メモリ手段は、これらのユニットにより実行されるべき命令を含むプログラムメモリでありうる。他方、共通メモリ手段は、データ記憶のために使用することもできる。
【００１３】
粗粒度演算を組み込むことは、マイクロコード幅に有益な影響を与える。第１に、粗粒度演算を実行するＦＵは、それら自身のコントローラを内部に有するので、ＶＬＩＷコントローラがデータパス全体を操るために必要とする命令ビットがより少なくてすむ。第２に、演算が完了していない場合でも、Ｉ／Ｏ時間形状を利用することによりデータを送り出し、消費することが可能になるので、信号の寿命が短縮され、それゆえデータパスのレジスタ数が低減される。データパスレジスタをアドレスするのに必要とされる命令ビットと、多数のデータパス資源を並列に操ることとが、ＶＬＩＷマイクロコードの大きい幅に寄与する２つの重要なファクタである。最終的に、命令レベル並列性（ＩＬＰ）を改善することにより、スケジュールの長さに良い影響を与え、従ってマイクロコードの長さにも良い影響を与える。マイクロコード領域を小さく保つことは、高性能を目的とし且つ長く複雑なプログラムコードを処理する埋め込みアプリケーションにとって基本的に不可欠である。アプリケーションをスケジュールする間、ＦＵの内部スケジュールが部分的に考慮される。このようにして、ＦＵの内部スケジュールは、アプリケーションのＶＬＩＷスケジュールに埋め込まれるものとして考えることができる。これにより、Ｉ／Ｏ時間形状に関する情報を利用して、「ジャストインタイム」方式でデータを供給し、又はＦＵからデータを取り出すことができる。ユニットにより消費されるすべてのデータが利用可能になっていなくても、演算を開始することができる。粗粒度演算を実施するＦＵは、同様に繰り返し利用されることができる。これは、そのＦＵがＶＬＩＷデータパス内に保持されうるが、その出力データの実際の使用は異なることを意味する。
【００１４】
ＶＬＩＷアーキテクチャに基づく市販のＤＳＰが既に知られており、これはデータパスのＦＵにより実行されるカスタム演算の複雑さを制限することを述べておく。例えば、Ｒ．Ｅ．Ａ．Ｌ．  ＤＳＰ［３］は、特定用途向け実行ユニット（Application-specific eXecution Units、ＡＸＵ）と呼ばれるカスタムユニットの組み込みを可能にする。しかしながら、これらの機能ユニットの待ち時間は、１クロックサイクルに限られている。ＴＩ  ‘Ｃ６０００［４］のような他のＤＳＰは、１乃至４サイクルの待ち時間をもつＦＵを有することができる。フィリップス社のＴｒｉｍｅｄｉａ  ＶＬＩＷアーキテクチャ［５］は、１乃至３サイクルのマルチサイクルのパイプライン演算を可能にする。アーキテクチャレベル合成ツールＰｈｉｄｅｏ［１０］は、時間形状を用いて演算を処理することができるが、制御主体のアプリケーションには適していない。Ｍｉｓｔｒａｌ２［１１］は、信号がＦＵの個々のＩ／Ｏポートに渡されるという制約下において、時間形状の規定を可能にする。今日、いかなるスケジューラも、複雑な時間形状をもつＦＵを良好に処理することができない。スケジューラのジョブを単純化するために、粗粒度演算を実施するユニットは、通常、その待ち時間によってのみ特徴付けられ、演算は極微とみなされる。結果として、ユニットは、入力データの全体量をもたずにその計算のいくつかを実施することができるにもかかわらず、この方法は、演算を始める前にすべてのデータが利用可能でなければならないのでスケジュールを長くする。この方法は、信号の寿命を長くし、必要とされるレジスタの数を増加させる。
【００１５】
本発明によるデータプロセッサ装置を動作させる方法が提供される。この装置は、
−前記装置の演算を制御するマスタコントローラと、
−スレーブコントローラを有し、相対的に長い待ち時間をもつ演算に対応する第１のタイプの命令を実行するように構成される第１の機能ユニットと、
−相対的に短い待ち時間をもつ演算に対応する第２のタイプの命令を実行することができる第２の機能ユニットと、
を少なくとも有する。本発明の方法によると、第１のタイプの命令の実行の間、第１の機能ユニットは、入力データを受け取り、出力データを供給し、前記方法により、前記出力データは、前記実行の間に第２の機能ユニットにより処理され、及び／又は前記入力データは、前記実行の間に第２の機能ユニットにより生成される。
【００１６】
本発明は更に、本発明による処理装置を動作させるように命令のシーケンスにプログラムをコンパイルする方法を提供する。このコンパイル方法により、
−第１の機能ユニットによる命令の実行の中に含まれる入出力操作を表すモデルが組み立てられ、
−このモデルに基づいて、１つ又は複数の前記第２の機能ユニットに関する命令は、前記第１の機能ユニットが入力データが使用される命令を実行しているとき、前記第１の機能ユニットに前記入力データを供給し、及び／又は前記第１の機能ユニットが出力データが計算される命令を実行しているとき、前記第１の機能ユニットから前記出力データを取り出すようにスケジュールされる。
【００１７】
【発明の実施の形態】
本発明のこれら及び他の側面は、図面に関して更に詳細に記述される。
【００１８】
図１は、本発明によるデータ処理装置を概略的に示している。データ処理装置は、マスタコントローラ１と、スレーブコントローラ２０を具える第１の機能ユニット２と、第２の機能ユニット３とを少なくとも有する。２つの機能ユニット２、３は、共通メモリ手段としてマイクロコードを含むメモリ１１を共有する。この装置は、第１の機能ユニット２による命令を実行するようにプログラムされており、前記命令の実行は、第１の機能ユニット２による入出力操作を含む。前記実行の間に、第１の機能ユニット２の出力データが、第２の機能ユニット３により処理され、及び／又は前記実行の間に、入力データが、第２の機能ユニット３により生成される。図示する実施例において、データ処理装置は、他の機能ユニット４、５を有する。
【００１９】
図１に示すデータ処理装置の実施例は、第１の機能ユニット２が、相対的に大きい待ち時間をもつ演算に対応する第１のタイプの命令を処理するように構成され、第２の機能ユニット３が、相対的に小さい待ち時間をもつ演算に対応する第２のタイプの命令を処理するように構成されることを特徴とする。
【００２０】
一例として、「ＦＦＴ  ｒａｄｉｘ−４」ＦＵを使用して実現することができるＦＦＴアルゴリズムの可能なバリエーションを考えることができる。このカスタムＦＵは、アルゴリズムが時間デシメーションから周波数デシメーションのＦＦＴに変更される間、繰り返し利用することができる。埋め込みカスタムＦＵが、その粗粒度演算に関してビジーである間、ＶＬＩＷプロセッサは、他の細粒度演算を実施することができる。従って、長い待ち時間の粗粒度演算は、残りのデータパスの資源がメインスレッドに属する他の計算を実施する間、別個のスレッドを実施するハードウェア上で実現されるマイクロスレッド［６］として理解することができる。
【００２１】
スケジューリング問題を組み込む前に、信号フローグラフ（ＳＦＧ）［７］［８］［９］が、所与のアプリケーションコードを表現するための方法として規定される。ＳＦＧは、コード内で実施される基本的な演算と、それらの演算の間の依存性とを記述する。
【００２２】
規定１．信号フローグラフＳＦＧ
ＳＦＧは、８タプル（Ｖ，Ｉ，Ｏ，Ｔ，Ｅｄ，Ｅｓ，ｗ，δ）である。ここで、・Ｖは、頂点（演算）の組である。
・Ｉは、入力の組である。
・Ｏは、出力の組である。
・Ｔ⊆Ｖ×Ｉ∪Ｏは、Ｉ／Ｏ操作のターミナルの組である。
・Ｅｄ⊆Ｔ×Ｔは、データエッジの組である。
・Ｅｓ⊆Ｔ×Ｔは、シーケンスエッジの組である。
・ｗ：Ｅｓ→Ｚは、各シーケンスエッジに関連付けられた（クロックサイクルにおける）タイミング遅延を記述する関数である。
・δ：Ｖ→Ｚは、各ＳＦＧ演算に関連付けられた（クロックサイクルにおける）実行遅延を記述する関数である。
ＳＦＧの規定において、方向付けられたデータエッジと、方向付けられ且つ重み付けされたシーケンスエッジとは区別される。これらは、「スケジューリング」が、各演算ｖ∈Ｖごとに開始時間ｓ（ｖ）を決定するタスクであり、これはＳＦＧにより指定される優先順位の制約を受けるというスケジューリング問題の異なる制約を課す。形式的に以下に述べる。
【００２３】
規定２．従来のスケジューリング問題
ＳＦＧ（Ｖ，Ｉ，Ｏ，Ｔ，Ｅｄ，Ｅｓ，ｗ，δ）が与えられる場合、演算の整数ラベリングは以下の通りである。
s:V→Z+
ここで、
s(vj)≧s(vi)+δ(vi) ∀i,j,h,k:((vi,oh),(vj,ik))∈Ed
s(vj)≧s(vi)+w((ti,tj)) ∀i,j:(ti,tj)∈Es
また、スケジュールの待ち時間：maxi=1..n{s(vi)}は最小である。
【００２４】
上述したスケジューリング問題において、各演算について１つの決定がなされ、すなわちその開始時間が決定される。Ｉ／Ｏ時間形状は解析には含まれないので、どの出力信号も演算が完了する前に有効になるとは考えられない。同様に、すべての入力信号が利用可能である場合のみ、演算が始まる。これは、確かに安全な仮定ではあるが、演算のデータ消費及び生成時間と、ＳＦＧ内の他の演算の開始時間との間のいかなる同期も可能にしない。
【００２５】
問題を形式的に述べる前に、演算の時間形状が以下のように規定される。
【００２６】
規定３．演算の時間形状
各演算ｖ∈ＶについてＳＦＧが与えられる場合、時間形状は、以下の関数として規定される。
σ:Tv→Z+
ここで、
Tv={t∈T|t=(v,p), with p∈I∪O}
は、演算ｖ∈Ｖに関するＩ／Ｏターミナルの組である。
【００２７】
それぞれのＩ／Ｏターミナルに割り当てられる数は、演算の開始時間に対する相対的なＩ／Ｏアクティビティの遅延をモデル化する。従って、実行遅延δの演算について、時間形状関数は、０からδ−１までの整数値を各Ｉ／Ｏターミナルに関連付ける。演算の時間形状の一例を図３に示す。
【００２８】
従来のスケジューリング問題において、それぞれの演算はグラフにおいて極微のように表されている。演算のＩ／Ｏ時間形状の概念を利用するために、スケジューリング問題が再び検討される。それぞれの演算について１つの決定がなされる場合、ここで、複数の決定がなされる。それぞれのスケジューリング決定は、所与の演算に属するそれぞれのＩ／Ｏターミナルの開始時間を決定することを目的とする。従って、演算の時間形状を考慮に入れる再検討されたスケジューリング問題の規定は、以下の通りである。
【００２９】
規定４．Ｉ／Ｏ時間形状のスケジューリング問題
ＳＦＧ及びＳＦＧ内の各演算ｖ∈Ｖについての時間形状関数が与えられる場合、ターミナルの整数ラベリングは以下の通りである。
s:T→Z+
ここで、
s((vj,ik))≧s((vi,oh)) ∀i,j,h,k:(t(vi,oh),(vj,ik))∈Ed
s(tj)≧s(ti)+w((ti,tj)) ∀i,j:(ti,tj)∈Es
また、スケジュールの待ち時間：maxi=1..n{s(vi)}は最小である。
【００３０】
時間形状の概念を組み込む際に、演算の待ち時間関数δはもはや必要ではなく、それぞれの演算のターミナルについてスケジューリング決定がなされることに注意することが重要である。得られたスケジュールは、データエッジ、シーケンスエッジの制約を満たし、時間形状関数に規定されるようなＩ／Ｏターミナル上でのタイミング関係を守らなければならない。演算のＩ／Ｏ時間形状特性を利用するために、時間形状関数δは、組Ｅｓに追加される複数のシーケンスエッジに変換されなければならない。これらの特別な制約により、あらゆる実現可能なスケジュールについての各Ｉ／Ｏ操作ターミナルの開始時間は、元の粗粒度演算の時間形状が守られるようなものであることが課される。
【００３１】
時間形状関数のシーケンスエッジへの変換は、粗粒度演算を実現しているＦＵをその計算の間に止めることができるか否かに依存して異なる方法で行われる。これについて、図４を参照して更に詳しく説明する。演算を停止させることができる場合、Ｉ／Ｏターミナルの同時性及びシーケンスが保たれるという前提で、演算の時間形状を拡張することができる。ユニットを停止させることができない場合、時間形状関数により制約されるようにＩ／Ｏターミナルの間のシーケンスだけでなく相対的な距離も保たれることを確実にするため、特別な制約が、グラフに追加されなければならない。
【００３２】
例示として、同じ元の粗粒度演算に属する２つのＩ／Ｏターミナル、すなわちｔ１及びｔ２について考える。３つの異なるケースが生じうる。
【００３３】
１）同時性
２つのＩ／Ｏターミナルｔ１及びｔ２が、粗粒度演算の時間形状に従って同じサイクルの間に生じる場合、２つのシーケンスエッジが追加される。これらの特別なエッジは、所与のＳＦＧについて、あらゆる実現可能なスケジュール内の演算ｔ１及びｔ２が同じサイクル（例えば図４ｂのｏ１及びｉ２）に実行されることを確実にする。
σ(t1)=σ(t2)である場合、(t1,t2)(t2,t1)∈Es
with w(t1,t2)=w(t2,t1)=0
再検討されたスケジューリング問題の規定に従って、これら２つの追加されたエッジは以下の制約を与える。
s(t1)≧s(t2)及びs(t2)≧s(t1)
【００３４】
２）シリアライゼーション（ホールド可能な演算）
２つのＩ／Ｏターミナルｔ１及びｔ２が、粗粒度演算の時間形状に従って同時に生じない場合、シーケンスエッジが追加される。この特別なエッジは、いかなる実現可能なスケジュールにおいても２つの演算の順序が保たれることを確実にする。いずれにせよ、これにより演算ｔ２を演算ｔ１に対して延期させることができる（例えば図４Ｂのｉ１及びｉ２）。
s(t2)-s(ts)=λ>0である場合、(t1,t2)∈Es with w(t1,t2)=λ
再検討されたスケジューリング問題の規定に従って、この追加されたエッジは以下の制約を与える。
s(i2)≧s(i1)+w(i1,i2)=s(i1)+λ
従って、s(i2)-s(i1)≧λ
【００３５】
３）シリアライゼーション（ホールド可能でない演算）
いかなる実現可能なスケジュールにおいても、２つのＩ／Ｏターミナルｔ１及びｔ２の開始時間の間の距離には、粗粒度時間形状により規定される制約が与えられる（例えば図４ｃのｉ１及びｉ２）。これは、２つのシーケンスエッジを追加して行われる。
s(t2)-s(t1)=λ>0である場合、(t1,t2),(t2,t1)∈Es
with w(t1,t2)=λ及びw(t2,t1)=λ
再検討されたスケジューリング問題の規定に従って、これらの２つの追加されるエッジは以下のような制約を与える。
s(t2)≧s(t1)+w(t1,t2)=s(t1)+λ
s(t1)≧s(t2)+w(t2,t1)=s(t2)-λ
最後の２つの方程式から、ｔ１及びｔ２の間の開始時間の差は、時間形状において制約されるものに等しくなる。
従って、
s(t2)-s(t1)=λ
【００３６】
それぞれの演算について、方法は、｜Ｉ∪Ｏ｜２のオーダーで多数のエッジを追加する。しかしながら、これらの多くは、例えば演算のターミナルの組に一部のオーダーを組み込むことにより剪定（除去）することができる。除去ステップは、ほとんどの場合は問題ではないので、ここでは説明しない。演算が、Ｉ／Ｏ操作の集合により記述され、シーケンスエッジが追加されると、ＳＦＧは、既知の通常の技法を使用してスケジュールされる。演算の時間形状による制約が守られる場合、それぞれの演算のＩ／Ｏターミナルは、ここで互いに分離され、独立してスケジュールされることができる。
【００３７】
例示として、所与のアプリケーションが、図２に示す「２Ｄｔｒａｎｓｆｏｒｍ」関数を集中的に実施していると仮定する。例示をより現実的にするために、考慮される関数は、２Ｄグラフィック処理を実施している。図２に示されるコードに従って、ベクトル（ｘ，ｙ）を利用して、ベクトル（Ｘ，Ｙ）を戻す。プロセッサの性能を改善するために、「２Ｄｔｒａｎｓｆｏｒｍ」はカスタムＦＵ上のハードウェアにおいて実現される。この関数は、ハードウェア上で実施されるので、これは正当に１つの粗粒度演算として考えることができる。この関数についての信号フローグラフが、図３ａに表されている。（粗粒度）演算について実現可能な内部スケジュールが、図３ｂに示されている。双方が１サイクルの待ち時間をもつ１つの加算器及び１つの乗算器が、カスタムＦＵ内で利用可能である。演算は、４つのＩ／Ｏターミナルを有し、それは、４つのクロックサイクルδ＝０，．．．，３においてカスタムＦＵにより実施される。
【００３８】
この例において、ＦＵは、４サイクルの間、アクティブであるが（図３Ｂ）、サイクル２ではいかなるＩ／Ｏ操作も実施されない。ＶＬＩＷデータパスから、カスタムＦＵにより実施される内部演算は見えないものであり、演算がそのデータを消費し生成する方法をモデル化するために、Ｉ／Ｏ時間形状だけが実際に必要とされる（図３ｂ）。
【００３９】
内容が示されていない図４ａの元の粗粒度演算は、４つの単一サイクルの演算のグラフとして再モデル化される。それぞれの単一サイクル演算は、Ｉ／Ｏターミナルをモデル化する。あらゆる実現可能なスケジュールにおいて元の粗粒度ユニットの時間形状が守られることを保証するために、シーケンスエッジが追加されなければならない。図において、シーケンスエッジは、第１の演算から始まり第２の演算で矢印が終わる破線により示されている。図４ｂには、ホールド可能なカスタムＦＵの挙動をモデル化する導き出されたＳＦＧが示されている。特に、粗粒度演算の時間形状に従って異なるサイクルで実施されるＩ／Ｏターミナルは、それらの順序が保たれるように直列化される。前記の図において、例えば値λ＝１を有するエッジｗ（ｉ１，ｉ２）が、演算ｉ１とｉ２との間に存在する。従って、s(i2)≧s(i1)+w(i1,i2)=s(i1)+λ。２つ又はそれ以上のＩ／Ｏターミナルの同時性も同様に保たれる。図４ｂの時間形状は、例えば双方が値λ＝０を有する第１のエッジｗ（ｉ２，ｏ１）及び第２のエッジｗ（ｏ１，ｉ２）を有するので、演算ｉ２及びｏ１の同時性が保証される。従って、ホールド機構がそのユニットにとって利用可能であるとき、シーケンスエッジが違反されない限り、スケジューラは、Ｉ／Ｏターミナルを互いから離すように動かして、粗粒度演算を延長することができる。ハードウェアの効果により、他の演算に又は他の演算からやり取りされるデータをより良く同期するようにＦＵがストールされてもよい。
【００４０】
図４ｃは、ホールド機構がカスタムＦＵにとって利用可能でないとき、Ｉ／Ｏターミナルにおける粗粒度演算を記述することにより得られるグラフを示している。この場合、追加されるシーケンスエッジは、あらゆる実現可能なスケジュールにおいて、Ｉ／Ｏターミナルのカップルの間の相対的な距離が粗粒度演算の時間形状により制約されるものとは異ならないことを確実にする。
【００４１】
ここで、図５に示すような、複合ＦＵ上にマップされる関数「２Ｄｔｒａｎｓｆｏｒｍ」が使用されるコードについて考える。この例では、「２Ｄｔｒａｎｓｆｏｒｍ」演算はループ本体の一部である。ループ本体では、ＡＬＵ演算及び乗算のような他の細粒度演算が同様に実施される。コードは、乗算器、加算器及び「２Ｄｔｒａｎｓｆｏｒｍ」ＦＵをデータパス内に有するＶＬＩＷプロセッサ上で実行されるものとする。
【００４２】
上述したループ本体のＳＦＧに関する従来のスケジュールが図６ａに示されている。粗粒度演算は「極微」とみなされ、他のいかなる演算もそれと並列には実行されない。図６ｂにおいて、複合ユニットのＩ／Ｏスケジュールは、拡張されており、ループ本体のＳＦＧに埋め込まれている。複合演算は、他の細粒度演算と同時に実行される。スケジュールに従って、データは、実際に必要なときに複合ＦＵからデータパスの残りのものに与えられ、また、この逆も行われ、これによってスケジュールの待ち時間を低減する。あるデータが複合ＦＵにとって利用可能でなく、計算を進めることができないとき、ユニットは停止させられる（例えば図６ｂのサイクル２）。ストールサイクルは、アルゴリズムをスケジュールする間に暗黙的に決定される。提案する解決法を使用することにより、アルゴリズムの待ち時間は、１０から８サイクルに低減される。必要なレジスタの数も同様に減少する。図６ａのサイクル０において生成された値は、２サイクルの間は生きていなければならないが、図６ｂのスケジュールの同じ信号は、直ちに使用される。提案する解決法は、ＶＬＩＷプロセッサのマイクロコード領域に関して効率的である。複合ＦＵはそれ自身のコントローラを有しており、ＶＬＩＷコントローラに任せられる唯一のタスクは、粗粒度ＦＵをデータパス資源の残りのものに同期させることである。ユニットへ送信されなければならない唯一の命令は、開始及びホールドコマンドである。これは、ＶＬＩＷ命令ワード内のわずかなビットを用いて符号化することができる。埋め込み複合ＦＵがその計算によりビジーである間、ＶＬＩＷプロセッサは、他の演算を実施することができる。
【００４３】
長い待ち時間をもつユニットは、ハードウェア上で実現されるマイクロスレッドとみなすことができ、データパスの残りのものがデータパス資源の残りのものを使用して他の計算を実行する間にタスクを実行する。
【００４４】
上記の方法の有効性について、ケーススタディとしてＦＦＴ−ｒａｄｉｘ４アルゴリズムを使用してテストした。ＦＦＴは、ＨＰ−ＵＸマシン上で走るＦｒｏｎｔｉｅｒ  Ｄｅｓｉｇｎ社のアーキテクチャレベル合成ツール「Ａ｜ＲＴ  ｄｅｓｉｇｎｅｒ」を使用して合成される分散されたレジスタファイルをもつＶＬＩＷアーキテクチャについて実現された。考えられたＦＦＴアルゴリズムのコアを構成するｒａｄｉｘ−４関数は、４つの複素数データ値と、３つの複素係数を処理し、４の複素数出力値を返す。カスタムユニット「ｒａｄｉｘ−４」は、加算器、乗算器及びそれ自身のコントローラを内部を有する。ユニットは、１４の（実数）入力値を消費し、８つの（実数）出力値を生成する。「ｒａｄｉｘ−４」ＦＵの特別な詳細を表１に示す。
【表１】
0004884634.tif 000002
【００４５】
３つの異なるＶＬＩＷインプリメンテーションが表２に示すようにテストされる。アーキテクチャ「ＦＦＴ＿ｏｒｇ」及び「ＦＦＴ＿２ＡＬＵ’ｓ」は、同じハードウェア資源を含むが、それらが実行することができる演算の粗さが異なる。
【表２】
0004884634.tif 000003
【００４６】
表３は、それぞれのアーキテクチャインスタンスについて、クロックサイクルにおいて実現されたＦＦＴ  ｒａｄｉｘ４アルゴリズムの性能と、アプリケーションのコードは記憶されるＶＬＩＷマイクロコードメモリの大きさとを示している。第１のインプリメンテーション（「ＦＦＴ＿ｏｒｇ」）を基準とする場合、表３において、「ＦＦＴ＿２ＡＬＵ’ｓ」が、より高い並列性及び最高の性能を示していることが分かる。
【表３】
0004884634.tif 000004
しかしながら、データパス内で利用可能な特別なＡＬＵは、ＶＬＩＷコントローラにより直接に制御されなければならず、マイクロコードの命令の幅の大きなインクリメントが認められる。他方、「ＦＦＴ＿ｒａｄｉｘ４」は、初めの２つの実験の中間の性能に達するが、かなり幅が狭いマイクロコードメモリが合成される。通常、並列処理が必要とされるコードの一部は、コード全体のわずかな部分である。ＦＦＴが、かなり長いアプリケーションコード内のコア機能である場合、マイクロコード幅、従って「ＦＦＴ＿２ＡＬＵ’ｓ」において必要とされるＩＬＰは、コードの他の部分において適切に利用されず、マイクロコード領域の浪費をもたらす。「ＦＦＴ＿２ＡＬＵ’ｓ」及び「ＦＦＴ＿ｒａｄｉｘ４」は共に、重要なＦＦＴループ本体を処理するためにアーキテクチャ内に２つのＡＬＵ及び乗算器を有する。しかしながら、利用可能な並列処理を操るために後者のマイクロコードに必要とされるビットはより少ない。
【００４７】
表４は、各インスタンスごとに、アーキテクチャ内に必要とされるレジスタの数を示している。特に、最後のアーキテクチャにおいて、全レジスタ数は、ＶＬＩＷプロセッサ内に存在するものと、「Ｒａｄｉｘ４」ユニット内で実現されるものとの合計である。行われた実験は、「Ｒａｄｉｘ４」粗粒度演算のＩ／Ｏ時間形状を利用してＦＦＴ  ＳＦＧをスケジュールすることにより、必要なレジスタ数が低減されることを裏付けている。
【表４】
0004884634.tif 000005
【００４８】
本発明による方法は、複合関数がＶＬＩＷデータパス内でＦＵとしてハードウェアで実現されうるフレキシブルなＨＷ／ＳＷ区分化を可能にする。提案する「Ｉ／Ｏ時間形状スケジューリング」方法は、各Ｉ／Ｏ操作のイベントの開始時間を別々にスケジュールすることを可能にし、最終的に、演算の時間形状自体を引き伸ばし、その環境に演算をより良く適応させることができる。ＶＬＩＷアーキテクチャにおいて粗粒度演算を使用することにより、マイクロコードメモリ幅を犠牲にすることなく、高い命令レベル並列性を達成することが可能になる。ＶＬＩＷマイクロコード幅を小さくすることは、高性能を目的とし且つ長く複雑なプログラムコードを処理する埋め込みアプリケーションにとって重要なことである。
【００４９】
参考文献
[1]Jean-Yves Brunel, Alberto Sangiovanni-Vincentinelli, Yosinori Watanabe, Luciano Lavagno, Wido Kruytzer and Frederic Petrot, “COSY: levels of interfaces for modules used to create a video system on chip”, EMMSEC’99 Stockholm 21-23 June 1999.
[2] Pieter van der Wolf, Paul Lieverse, Mudit Goel, David La Hei and Kees Vissers, “An MPEG-2 Decoder Case Study as a Driver for a System Level Design Methodology”, Proceedings 7th International Workshop on Hardware/Software Codesign (CODES ’99), pp 33-37, May 3-5 1999.
[3] Rob Woudsma et al., “R.E.A.L. DSP: Reconfigurable Embedded DSP Architecture for Low-Power/Low-Cost Telecommunication and Consumer Applications”, Philips Semiconductor.
[4] Texas Instruments, “TMS320C6000 CPU and Instruction Set Reference Guide”, Literature Number: SPRU189D March 1999.
[5] Philips Electronics, “Trimedia, TM1300 Preliminary Data Book”, October 1999 First Draft.
[6] R. Chappel, J. Stark, S.P. Kim, S.K. Reinhardt, Y.N. Patt, “Simultaneous subordinate microthreading (SSMT)”, ISCA Proc. of the International Symposium on Computer Architecture, pp.186-95 Atlanta, GA, USA, 2-4 May 1999.
[7] Bart Mesman, Adwin H. Timmer, Jef L. van Meerbergen and Jochen Jess, “Constraints Analysis for DSP Code Generation”, IEEE Transactions on CAD, pp 44-57, Vol. 18, No. 1, January 1999.
[8] B. Mesman, Carlos A. Alba Pinto, and Koen A.J. van Eijk, “Efficient Scheduling of DSP Code on Processors with Distributed Register files” Proc. International Symposium on System Syntesis, San Jose, November 1999, pp. 100-106.
[9] W. Verhaegh, P. Lippens, J. Meerbergen, A. Van der Werf et al., “Multidimensional periodic scheduling model and complexity”, Proceedings of European Conference on Parallel Processing EURO-PAR ‘96, pp. 226-35, vol.2, Lyon, France, 26-29 Aug. 1996.
[10] W. Verhaegh, P. Lippens, J. Meerbergen, A. Van der Werf, “PHIDEO: high-level synthesis for high throughput applications”, Journal of VLSI Signal Processing (Netherlands), vol.9, no.1-2, p.89-104, Jan. 1995.
[11] Frontier Design Inc, “Mistral2 Datasheet”, Danville, California CA 94506 U.S.A
[12] P.E.R. Lippens, J.L. van Meerbergen, W.F.J. Verhaegh, and A.van der Werf , “Modular design and hierarchical abstraction in Phideo”, Proceedings of VLSI Signal Processing VI, 1993, pp. 197-205.
【図面の簡単な説明】
【図１】データ処理装置を示す図。
【図２】図１のデータ処理装置により実行することができる演算の一例を示す図。
【図３ａ】演算の信号フローグラフ（ＳＦＧ）を示す図。
【図３ｂ】演算のスケジュール及びその時間形状関数を示す図。
【図４ａ】図２の演算を示す概略図。
【図４ｂ】ホールド可能なカスタム機能ユニット（ＦＵ）における図４ａの演算の実行をスケジュールするための信号フローグラフを示す図。
【図４ｃ】ホールド可能でないカスタム機能ユニット（ＦＵ）における図４ａの演算の実行をスケジュールするための信号フローグラフを示す図。
【図５】図２の演算を含むネスト化ループに示す図。
【図６ａ】ＳＦＧにおいて図５のネスト化ループの従来のスケジュールを示す図。
【図６ｂ】本発明によるＳＦＧにおける図５のネスト化ループのスケジュールを示す図。
【図１】
0004884634.tif 000006
【図２】
0004884634.tif 000007
【図３ａ】
0004884634.tif 000008
【図３ｂ】
0004884634.tif 000009
【図４ａ】
0004884634.tif 000010
【図４ｂ】
0004884634.tif 000011
【図４ｃ】
0004884634.tif 000012
【図５】
0004884634.tif 000013
【図６ａ】
0004884634.tif 000014
【図６ｂ】
0004884634.tif 000015