TOP > 国内特許検索 > データ処理装置

データ処理装置

国内特許コード P09A014407
整理番号 517
掲載日 2009年5月8日
出願番号 特願2004-266056
公開番号 特開2006-079563
登録番号 特許第4660747号
出願日 平成16年9月13日(2004.9.13)
公開日 平成18年3月23日(2006.3.23)
登録日 平成23年1月14日(2011.1.14)
発明者
  • 中島 康彦
出願人
  • 学校法人京都大学
発明の名称 データ処理装置
発明の概要

【課題】 比較的簡素な構成によって、再利用を行う上でより的確な入出力グループを命令区間記憶手段に登録することを可能とするデータ処理装置を提供する。
【解決手段】 依存関係格納部Mは、各出力アドレスおよび出力値が、どの入力アドレスおよび入力値を起源とするものであるかを示している。出力側番号格納部wgpidは、各出力要素が所属する入出力グループの情報を格納し、入力側番号格納部rgpidは、各入力要素が所属する入出力グループの情報を格納する。行一時格納部tmp00は、入出力グループを生成している途中に、依存関係格納部Mに変更があった場合に、変更された出力要素と入力要素との依存関係を格納し、番号一時格納部tmp01は、入出力グループを生成している途中に、上記依存関係格納部に変更があった場合に、変更された入出力グループの情報を格納する。
【選択図】 図17

従来技術、競合技術の概要


従来、CPU(Central Processing Unit)を始めとするマイクロプロセッサにおいて、演算速度の高速化技術に関する研究開発が盛んに行われている。高速化技術としては、例えばパイプライン、スーパースケーラ、アウトオブオーダー実行、および、レジスタリネーミングなどが挙げられる。



パイプラインは、命令の実行処理を数段階に分解し、複数の命令を流れ作業的に同時処理を行う技術である。スーパースケーラは、命令の実行回路を2組以上用意し、複数の命令を同時に並行して実行する技術である。アウトオブオーダー実行は、命令の記述順序を無視して、いくつかの連続する命令の中から先に実行可能なものを探して先行処理を行う技術である。レジスタリネーミングは、例えばCISC(Complex Instruction Set Computer)タイプのプロセッサにおいて、従来のプロセッサにおける命令の互換性を保ちながら、汎用レジスタの数を増やすことによって並行処理が行われる確率を増大させる技術である。



このように、マイクロプロセッサにおける演算速度の高速化を図る際には、命令の実行を並行して行うことが重要となっている。しかしながら、プログラム中には、ある命令の結果に応じて異なる命令が行われるような依存関係、言い換えれば分岐が含まれている場合がほとんどである。このような分岐が含まれている場合、並行処理によって先行して処理を行っていると、分岐の結果によって先行処理した内容が無駄になるという状況が発生することになり、演算速度の高速化の効果が小さくなるという問題がある。



そこで、プログラム中に分岐がある場合に、分岐先を予測することによって先行処理が無駄になる確率を低減し、並行処理の効果を向上させる技術、いわゆる分岐予測に関する研究が数多く行われている。



しかしながら、分岐予測に基づいて投機的先行処理を行う場合には、一般的に次のような問題がある。第1の問題としては、予測の正当性を常に検証する必要があるので、先行命令列の実行時間そのものを削減することはできない、という点である。第2の問題としては、誤った予測に基づく一連の先行演算結果を全て無効化する必要があるので、一度に投機的先行処理できる命令数を多くするには、相応のハードウェアコストを要する、という点である。第3の問題としては、命令間の依存関係が多いほど、多重に投機的先行処理をする必要が生じ、予測の正当性の検証処理、および誤った予測に基づく処理の無効化処理が極めて複雑になる、という点である。



一方、分岐予測とは異なる高速化技術として、値再利用という技術も提案されている。この値再利用とは、プログラムの一部分に関する入力値および出力値を再利用表に登録しておき、同じ箇所を再度実行する際に、入力値が再利用表に登録されているものである場合には、登録されている出力値を出力する、という技術である。この値再利用による効果としては次のようなものが挙げられる。(1)入力値が、再利用表に登録されている入力値と一致すれば、実行結果を検証する必要がない。(2)入力値および出力値の総数によってのみハードウェアコストが決定され、省略可能な命令列の長さが制約されない。(3)命令間の依存関係の多少は、再利用機構の複雑さに影響を与えない。(4)冗長なロード/ストア命令を削減することができるとともに、これに伴う消費電力の削減も実現される。



後記する非特許文献1には、プログラムにおける関数に関して値再利用を行う技術が示されている。この従来技術では、一般的にロードモジュールがABI(Application Binary Interface)に従って作られることを利用しており、特に、SPARC(Scalable Processor ARChitecture) ABIを利用している。そして、このABIにおいて関数の入出力を特定することによって値再利用を実現している。すなわち、値再利用のためのコンパイラによる専用命令の埋め込みが不要となっており、既存ロードモジュールへの適用が可能となっている。



また、関数の多重構造を動的に把握することにより、関数内局所レジスタやスタック上の局所変数を値再利用における入出力値から除外するようにしており、これによって効率を向上させている。特に関数については、関数の複雑さに拘わらず、最大6のレジスタ入力、最大4のレジスタ出力、および、局所変数を含まない最小限の主記憶値の登録による再利用および事前実行が可能となっている。この従来技術について以下に詳細に説明する。



まず、単一の関数を対象として、何が入力で何が出力であるかを明らかにし、1レベルの再利用を行うために必要な機構について説明する。プログラムにおいては、一般的に関数は多重構造を形成している。関数A(Function-A)が関数B(Function-B)を呼び出す構造を図21(a)に示す。



大域変数(Globals)は、関数Aの入出力(Ain/Aout)および関数Bの入出力(Bin/Bout)になりうるものである。関数Aの局所変数(Locals-A)は、関数Aの入出力ではないが、ポインタを通じてBの入出力になりうるものである。また、関数Aから関数Bへの引数(Args)は、関数Bへの入力となりうるものであり、関数Bから関数Aの返り値(Ret.Val.)は、関数Bからの出力となりうるものである。なお、関数Bの局所変数(Locals-B)は、関数Aおよび関数Bの入出力には含まれない。



コンテクストに依存せずに関数Bを再利用するには、関数Bの実行時に、関数Bの入出力Bin/Boutのみを入出力として登録しなければならない。ここで、図21(a)に示すプログラム構造を実行する際の主記憶におけるメモリマップを図21(b)に示す。このメモリマップにおいて、Bin/Boutを含まない領域はLocals-Bのみとなっている。よって、Bin/Boutを識別するには、GlobalsとLocals-Bとの境界、および、Locals-BとLocals-Aとの境界をそれぞれ確定しなければならない。前者については、一般的にOS(Operating System)が実行時のデータサイズおよびスタックサイズの上限を決めることを利用し、OSが設定する境界(LIMIT)に基づいてGlobalsとLocals-Bとの境界を確定することができる。後者については、Bが呼び出される直前のスタックポインタの値(SP in A)を用いることによって、Locals-BとLocals-Aとの境界を確定することができる。



次に、与えられた主記憶アドレスが、大域変数であるか、または、どの関数の局所変数であるかを識別する方法について説明する。ロードモジュールは、SPARC ABIに規定されている以下の条件を満たすと仮定する。なお、%fpはフレームポインタ、%spはスタックポインタを意味するものとする。
(1)%sp以上の領域のうち、%sp+0~63はレジスタ退避領域、%sp+68~91は引数退避領域であり、いずれも関数の入出力ではない。
(2)構造体を返す場合の暗黙的引数(Implicit Arg.)は%sp+64~67に格納される。
(3)明示的引数(Explicit Arg.)はレジスタ%o0~5、%sp+92以上の領域に置かれる。



まず、大域変数と局所変数とを区別するために、一般的に、OSが実行時のデータサイズおよびスタックサイズの上限を決めることを利用し、次の事項を仮定する。
(1)大域変数はLIMIT未満の領域に置かれる。
(2)%spは、LIMIT以下になることはなく、LIMIT~%spの領域は無効である。



以上の条件を満たしながら、関数Aが関数Bを呼び出す場合の、メモリマップにおける引数およびフレームの概要を図22に示す。同図を参照しながら、以下にAの局所変数およびBの局所変数を区別する方法について説明する。



同図において、(a)はA実行中の状態を示している。LIMIT未満の太枠部分に命令(Instructions)および大域変数(Global Vars.)が格納され、%sp以上に有効な値が格納されている。%sp+64には、Bが構造体を返り値とする場合の暗黙的引数として、構造体の先頭アドレスが格納される。Bに対する明示的引数の先頭6ワードはレジスタ%o0~5、第7ワード以降は%sp+92以上に格納される。ベースレジスタを%spとするオペランド%sp+92が出現した場合、この領域は引数の第7ワードすなわちBの局所変数である。一方、オペランド%sp+92が出現しない場合、この領域はAの局所変数である。このように、(a)の状態では、オペランドを検証することによってAの局所変数とBの局所変数とを区別することができる。



一方、(b)はB実行中の状態を示している。引数が入力、返り値が出力、大域変数およびAの局所変数が入出力となりうる。ただし、Bは可変長引数を受け入れる場合があるので、一般に%fp+92以上の領域がAの局所変数の領域となるかBの局所変数の領域となるかは判断できない。



局所変数を区別するには、まず、(a)の時点において引数の第7ワード以降を検出した関数呼び出しは再利用の対象外とし、第7ワード以降を検出しない関数呼び出しに関して、直前に%sp+92の値を記録しておくようにする。なお、第7ワード以降を使用する関数呼び出しの出現頻度が低いと予想されることから、第7ワード以降を使用する関数を再利用の対象外とする制限による性能低下は軽微なものと考える。



以上の準備により、(b)における主記憶参照アドレスが、予め記録した%sp+92の値以上の場合はAの局所変数、小さい場合はBの局所変数であることがわかる。B実行時には、Bの局所変数を除外しながら、大域変数およびAの局所変数を再利用表へ登録する。



再利用の際は、Bの局所変数は入出力から除外されるので、Bの局所変数のアドレスが一致している必要がない。このため、いかなるコンテクストであっても、入力さえ一致すれば、再利用することが可能である。ただし、Bが参照する大域変数やAの局所変数については、アドレスおよびデータの両方が再利用表の内容と完全に一致する必要がある。すなわち、Bを実行する前に、どのようにして比較すべき主記憶アドレスを網羅するかがポイントになる。



Bが参照する大域変数やAの局所変数のアドレスは、そもそもBにおいて生成されるアドレス定数や、大域変数/引数を起源とするポインタに基づいているものである。よって、まず引数が完全に一致する再利用表中のエントリを選択した後に、関連する主記憶アドレスをすべて参照して一致比較を行うことにより、Bが参照すべき主記憶アドレスを網羅することができる。そして、全ての入力が一致した場合にのみ、登録済の出力(返り値、大域変数、およびAの局所変数)を再利用することができる。



関数再利用を実現するために、再利用表として、関数管理表(RF)および入出力記録表(RB)を設けることにする。1つの関数を再利用するために必要なハードウェア構成を図23に示す。複数の関数を再利用可能とするには、この構成を複数組用意することになる。



この表において、RFおよびRBに保持されるVは、エントリが有効であるか否かを示すフラグであり、LRU(least recently used)は、エントリ入れ替えのヒントを示している。RFは、上記のVおよびLRUの他に、関数の先頭アドレス(Start)、および参照すべき主記憶アドレス(Read/Write)を保持する。RBは、上記のVおよびLRUの他に、関数呼び出し直前の%sp(SP)、引数(Args.)(V:有効エントリ、Val.:値)、主記憶値(Mask:Read/Writeアドレスの有効バイト、Value:値)、および、返り値(Return Values)(V:有効エントリ、Val.:値)を保持する。



返り値は、%i0~1(リーフ関数では%o0~1に読み替える)または%f0~1に格納され、%f2~3を使用する返り値(拡張倍精度浮動小数点数)は対象プログラムには存在しないものと仮定する。ReadアドレスはRFが一括管理し、MaskおよびValueはRBが管理することにより、Readアドレスの内容とRBの複数エントリをCAM(content-addressable memory)により一度に比較する構成を可能としている。



単一の関数を再利用するには、まず、関数実行時に、局所変数を除外しながら、引数、返り値、大域変数および上位関数の局所変数に関する入出力情報を再利用表に登録していく。ここで、読み出しが先行した引数レジスタは関数の入出力として、また、返り値レジスタへの書き込みは関数の出力として登録する。その他のレジスタ参照は登録する必要がない。主記憶参照も同様に、読み出しが先行したアドレスについては入力、書き込みは出力として登録する。



関数から復帰するまでに次の関数を呼び出した場合、または、登録すべき入出力が再利用表の容量を超える、引数の第7ワードを検出する、途中でシステムコールや割り込みが発生する、などの擾乱が発生しなかった場合、復帰命令を実行した時点で、登録中の入出力表エントリを有効にする。



以降、図23を参照しながら説明すると、関数を呼び出す前に、(1)関数先頭アドレスを検索し、(2)引数が完全に一致するエントリを選択し、(3)関連する主記憶アドレスすなわち少なくとも1つのMaskが有効であるReadアドレスをすべて参照して、(4)一致比較を行う。全ての入力が一致した場合に、(5)登録済の出力(返り値、大域変数、およびAの局所変数)を書き戻すことによって、関数の実行を省略することができる。

【非特許文献1】情報処理学会論文誌:ハイパフォーマンスコンピューティングシステム,HPS5,pp.1-12,Sep.(2002),“関数値再利用および並列事前実行による高速化技術”(中島康彦、緒方勝也、正西申悟、五島正裕、森眞一郎、北村俊明、富田眞治)(発行日2002年9月15日)

産業上の利用分野


本発明は、主記憶手段から命令区間を読み出し、演算処理を行った結果を主記憶手段に書き込む処理を行うデータ処理装置に関するものである。

特許請求の範囲 【請求項1】
主記憶手段から命令区間を読み出し、演算処理を行った結果を主記憶手段に書き込む処理を行うデータ処理装置において、
上記主記憶手段から読み出した命令区間に基づく演算を行う第1の演算手段と、上記第1の演算手段による上記主記憶手段に対する読み出しおよび書き込み時に用いられるレジスタと、上記第1の演算手段によって命令区間の演算が行われたときの入力パターンおよび出力パターンからなる入出力グループを生成する入出力生成手段と、上記入出力生成手段によって生成された入出力グループを記憶する命令区間記憶手段とを備え、
上記第1の演算手段が、命令区間を実行する際に、該命令区間の入力パターンと、上記命令区間記憶手段に記憶されている入力パターンとが一致した場合、該入力パターンと対応して上記命令区間記憶手段に記憶されている出力パターンをレジスタおよび/または主記憶手段に出力する再利用処理を行い、
上記入出力生成手段が、
出力パターンに含まれる各出力要素が、入力パターンに含まれるどの入力要素を起源とするものであるかを示す依存関係格納部と、
1以上の上記出力要素を含む出力パターンと、1以上の上記入力要素を含む入力パターンとからなる入出力グループを設定する入出力グループ設定手段とを備え、
上記入出力グループ設定手段が、
各出力要素が所属する入出力グループのグループ番号を示す情報を格納する出力側グループ格納部と、
各入力要素が所属する入出力グループのグループ番号を示す情報を格納する入力側グループ格納部と、
一時格納部と、
グループ一時格納部とを備え
上記依存関係格納部が、上記各出力要素を行成分、上記各入力要素を列成分とする2次元配列メモリによって構成され、該2次元配列メモリの各メモリ要素が、該メモリ要素の行成分に対応する出力要素が、該メモリ要素の列成分に対応する入力要素を起源とするか否かの情報を保持しており、
上記第1の演算手段によって命令区間の演算が行われる際に、レジスタおよび/または主記憶手段から読み出しが行われた場合に、上記入出力生成手段が、
(1)読み出しが行われたレジスタおよび/または主記憶手段のアドレスが、出力要素として依存関係格納部に登録されている場合、該出力要素に対応する依存関係格納部の行成分と、上記一時格納部の各要素との論理和を該一時格納部に格納するとともに、該出力要素に対応する出力側グループ格納部の行成分と、上記グループ一時格納部の各要素との論理和を該グループ一時格納部に格納する処理、
(2)読み出しが行われたレジスタおよび/または主記憶手段のアドレスが、出力要素としては依存関係格納部に登録されておらず、入力要素として依存関係格納部に登録されている場合、該入力要素に対応する依存関係格納部の列に対応するメモリ要素を1とし、その他のメモリ要素を0とした情報を上記一時格納部に格納するとともに、該入力要素に対応する入力側グループ格納部の各要素と、上記グループ一時格納部の各要素との論理和を該グループ一時格納部に格納する処理、および、
(3)読み出しが行われたレジスタおよび/または主記憶手段のアドレスが、出力要素および入力要素のいずれとしても依存関係格納部に登録されていない場合には、該アドレスおよび値を入力要素として依存関係格納部に登録するとともに、該入力要素に対応する依存関係格納部の列に対応するメモリ要素を1とし、その他のメモリ要素を0とした情報を上記一時格納部に格納する処理を行い、
レジスタおよび/または主記憶手段への書き込みが行われた場合に、上記入出力生成手段が、
(4)書き込みが行われたレジスタおよび/または主記憶手段のアドレスが、出力要素として登録されている場合、登録されている出力要素に対応する出力値を、書き込みが行われた値に更新するとともに、
既に登録されている出力要素に対応する依存関係格納部の行成分を、その時点で一時記憶されている上記一時格納部に格納されている情報に置き換えるとともに、上記グループ一時格納部に格納されている情報に基づいて、該出力要素に対応する出力側グループ格納部の情報、および、該出力要素が依存する各入力要素に対応する入力側グループ格納部の情報を更新する処理、および、
(5)書き込みが行われたレジスタおよび/または主記憶手段のアドレスが、出力要素として登録されていない場合、該アドレスおよび値を出力要素として依存関係格納部に登録するとともに、該出力要素に対応する依存関係格納部の行成分を、その時点で一時記憶されている上記一時格納部に格納されている情報に置き換えるとともに、上記グループ一時格納部に格納されている情報に基づいて、該出力要素に対応する出力側グループ格納部の情報、および、該出力要素が依存する各入力要素に対応する入力側グループ格納部の情報を更新する処理を行うことを特徴とするデータ処理装置。

【請求項2】
上記入出力グループ設定手段が、入出力グループを生成している途中に、上記出力要素および/または上記入力要素に対して既に割り当てられている入出力グループの情報を格納するグループ管理部をさらに備えていることを特徴とする請求項1記載のデータ処理装置。

【請求項3】
上記入出力グループ設定手段が、入出力グループを生成している途中に、条件分岐命令が検出された場合に、該条件分岐命令が依存する入力要素の情報を格納する条件分岐格納部をさらに備えていることを特徴とする請求項1記載のデータ処理装置。

【請求項4】
上記命令区間記憶手段が、複数の上記入力パターンを、一致比較すべき項目をノードとみなした木構造として記憶する入力パターン記憶手段を備えていることを特徴とする請求項1記載のデータ処理装置。

【請求項5】
上記入力パターン記憶手段が、上記入力パターンにおいて一致比較すべき項目の値と、次に比較すべき項目とを対応させて格納することによって、上記木構造を実現することを特徴とする請求項4記載のデータ処理装置。

【請求項6】
上記入力パターン記憶手段が、連想検索手段と、付加記憶手段とを備え、
上記連想検索手段が、一致比較すべき項目の値を格納する値格納領域と、該項目を識別するキーを格納するキー格納領域とを有する1つ以上の検索対象ラインを備え、
上記付加記憶手段が、上記検索対象ラインに対応した対応ラインごとに、次に連想検索を行うべき項目を格納する検索項目指定領域を有していることを特徴とする請求項5記載のデータ処理装置。
産業区分
  • 演算制御装置
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2004266056thum.jpg
出願権利状態 権利存続中
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記までご連絡ください。


PAGE TOP

close
close
close
close
close
close
close