Top > Search of Japanese Patents > DATA PROCESSING DEVICE, DATA PROCESSING PROGRAM, AND RECORDING MEDIUM RECORDED THE DATA PROCESSING PROGRAM

DATA PROCESSING DEVICE, DATA PROCESSING PROGRAM, AND RECORDING MEDIUM RECORDED THE DATA PROCESSING PROGRAM

Patent code P09A014412
File No. 586
Posted date May 8, 2009
Application number P2004-347124
Publication number P2006-155370A
Patent number P4635193
Date of filing Nov 30, 2004
Date of publication of application Jun 15, 2006
Date of registration Dec 3, 2010
Inventor
  • (In Japanese)中島 康彦
Applicant
  • (In Japanese)国立大学法人京都大学
Title DATA PROCESSING DEVICE, DATA PROCESSING PROGRAM, AND RECORDING MEDIUM RECORDED THE DATA PROCESSING PROGRAM
Abstract PROBLEM TO BE SOLVED: To provide a data processing device for reading a sequence of instructions and/or values from a main storage means to carry out the process of writing the results of operations into the main storage means and which achieves more effective pre-execution of an instruction section by increasing the rate at which predictions are right.
SOLUTION: The number of times that an output element is stored when an instruction section is executed is recorded. On the basis of the number of times that the output element is stored, a store counter (S-Count) is set for a predicted input address. On the basis of an input element predicted by a prediction process part, an MSP/SSP executes the corresponding instruction section in advance and, for the predicted input address registered in a storage area for addresses that need waiting, the MSP/SSP waits until the number of times that the input address is stored is reached, based on the store counter (S-Count) that corresponds to the address; then the MSP/SSP reads from the main storage to execute the corresponding instruction section in advance.
Outline of related art and contending technology (In Japanese)


従来、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)を呼び出す構造を図22(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のみを入出力として登録しなければならない。ここで、図22(a)に示すプログラム構造を実行する際の主記憶におけるメモリマップを図22(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を呼び出す場合の、メモリマップにおける引数およびフレームの概要を図23に示す。同図を参照しながら、以下に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つの関数を再利用するために必要なハードウェア構成を図24に示す。複数の関数を再利用可能とするには、この構成を複数組用意することになる。



この表において、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ワードを検出する、途中でシステムコールや割り込みが発生する、などの擾乱が発生しなかった場合、復帰命令を実行した時点で、登録中の入出力表エントリを有効にする。



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



ここで、命令区間の一例として、図25に示す命令区間が、図24に示したRFおよびRBの構成によって実行された場合の例について説明する。同図において、PCは、該命令区間が開始された際のPC値を示している。すなわち、命令区間の先頭が1000番地となっている。また、図26は、図25に示す命令区間が実行された場合に、RBに登録される入力アドレスおよび入力データ、並びに出力アドレスおよび出力データを簡略化して示しており、図27は、RBにおける実際の登録状況を示している。



第1行目の命令(以降、単に第1の命令のように称する)において、アドレス定数A1がレジスタR0にセットされる。第2の命令において、レジスタR0の内容をアドレスとする主記憶からロードされた4バイトデータ(00110000)がレジスタR1に格納される。この場合、アドレスA1、マスク(FFFFFFFF)(マスクにおいて、Fが有効バイトを示しており、0が無効バイトを示す)、データ(00110000)は、入力としてRBにおけるInput側の第1列に登録され、レジスタ番号R1、マスク(FFFFFFFF)、およびデータ(00110000)は出力としてRBにおけるOutput側の第1列に登録される。



第3の命令において、アドレス定数A2がレジスタR0にセットされる。第4の命令において、レジスタR0の内容をアドレスとする主記憶からロードされた1バイトデータ(02)がレジスタR2に格納される。この場合、アドレスA2、マスク(FF000000)、およびデータ(02)は入力としてRBにおけるInput側の第2列に登録される。この際、アドレスA2の残り3バイトについては、Don't Careを意味する「-」が格納される。レジスタ番号R2、マスク(FFFFFFFF)およびデータ(00000002)は出力としてRBにおけるOutput側の第2列に登録される。



第5の命令において、アドレス(A2+R2)からロードされた1バイトデータ(22)がレジスタR2に格納されている。アドレスR2の値は(02)であったので、アドレス(A2+02)、およびデータ(22)が、入力としてRBにおけるInput側の第2列に追加登録される。この際、アドレス(A2+02)の部分に登録が行われ、アドレス(A2+01)および(A2+03)に対応する部分は、Don't Careを意味する「-」のままとなる。すなわち、アドレスA2に対応するマスクは(FF00FF00)となる。レジスタ番号R2、マスク(FFFFFFFF)、およびデータ(00000022)は、出力としてRBにおけるOutput側の第2列に上書きされる。



第6の命令において、アドレス定数A3がレジスタR0にセットされる。第7の命令において、レジスタR0の内容をアドレスとする主記憶からロードされた1バイトデータ(33)がレジスタR3に格納される。この場合、アドレスA3、マスク(00FF0000)、およびデータ(33)は入力としてRBにおけるInput側の第3列に登録される。レジスタ番号R3、マスク(FFFFFFFF)、およびデータ(00000033)は出力としてRBにおけるOutput側の第3列に登録される。



第8の命令において、アドレス(R1+R2)からロードされた1バイトデータ(44)がレジスタR4に格納される。この場合、アドレスR1とアドレスR2は命令区間の内部にて上書きされたレジスタのアドレスとなるので、アドレスR1およびアドレスR2は命令区間の入力とはならない。一方、アドレス(R1+R2)によって生成されたアドレスA4は命令区間の入力であるので、アドレスA4、マスク(00FF0000)、およびデータ(44)は入力としてRBにおけるInput側の第4列に登録される。レジスタ番号R4、マスク(FFFFFFFF)、およびデータ(00000044)は出力としてRBにおけるOutput側の第4列に登録される。



第9の命令において、レジスタR5から値が読み出され、読み出された値に1が加えられた結果が再びレジスタR5に格納される。この場合、レジスタR5、マスク(FFFFFFFF)、およびデータ(00000100)は入力としてRBにおけるInput側の第5列に登録される。また、レジスタ番号R5、マスク(FFFFFFFF)、およびデータ(00000101)は出力としてRBにおけるOutput側の第5列に登録される。



以上のように、命令実行時におけるメモリ/レジスタからの読み出しに際しては、以下の処理が行われる。
(1)RBにおけるOutput側が検索され、読み出されたアドレス/レジスタ番号が既登録であれば、該アドレス/レジスタ番号はInput側に登録されずに終了する。
(2)RBにおけるOutput側になければRBにおけるInput側が検索され、読み出されたアドレス/レジスタ番号が既登録であれば該アドレス/レジスタ番号は登録されずに終了する。
(3)RBにおけるInput側にもなければ、RBに新たにエントリが追加されて、該アドレス/レジスタ番号および値が登録される。



また、命令実行時におけるメモリ/レジスタへの書き込みに際しては以下の処理が行われる。
(1)RBにおけるOutput側が検索され、読み出されたアドレス/レジスタ番号が既登録であれば値が更新されて終了する。
(2)RBにおけるOutput側になければ、新たにエントリが追加されて読み出されたアドレス/レジスタ番号および値が登録される。



また、後述する特許文献1では、上記のような再利用を行う構成において、プロセッサを複数設け、並列事前実行を行う構成が開示されている。この並列事前実行が行われる際の入力の予測方法として、最後に出現した引数および最近出現した2組の引数の差分に基づいて、ストライド予測を行う方法が開示されている。



以上のように入力予測を行えば、上記した入力パラメータが単調に変化し続けるような場合に、事前に予測しておいた結果に基づいて効果的に再利用を行うことが可能となる。
【非特許文献1】
情報処理学会論文誌:ハイパフォーマンスコンピューティングシステム,HPS5,pp.1-12,Sep.(2002),“関数値再利用および並列事前実行による高速化技術”(中島康彦、緒方勝也、正西申悟、五島正裕、森眞一郎、北村俊明、富田眞治)(発行日2002年9月15日)
【特許文献1】
特開2004-258905号公報(公開日2004年9月16日)

Field of industrial application (In Japanese)


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

Scope of claims (In Japanese)
【請求項1】
 
主記憶手段から命令区間を読み出し、演算処理を行った結果を主記憶手段に書き込む処理を行うデータ処理装置において、
上記主記憶手段から読み出した命令区間に基づく演算を行う第1の演算手段と、上記第1の演算手段による上記主記憶手段に対する読み出しおよび書き込み時に用いられるレジスタと、複数の命令区間の実行結果としての入力パターンおよび出力パターンを記憶する入出力記憶手段とを備え、
上記第1の演算手段が、命令区間を実行する際に、該命令区間の入力パターンと、上記入出力記憶手段に記憶されている入力パターンとが一致した場合、該入力パターンと対応して上記入出力記憶手段に記憶されている出力パターンをレジスタおよび/または主記憶手段に出力する再利用処理を行うとともに、
上記データ処理装置が、
上記第1の演算手段による命令区間の実行結果を、上記入出力記憶手段に記憶する際に、入力パターンに含まれる入力要素のうち、予測を行うべき入力要素と予測を行う必要のない入力要素とを区別し、この区別情報を上記入出力記憶手段に登録するとともに、上記入出力記憶手段に格納される出力パターンにおける出力要素のうち、該当命令区間の実行の際にストアが行われたものについてそのストアの回数をカウントし、このカウント値を上記入出力記憶手段に格納する登録処理手段と、
上記区別情報に基づいて、上記入出力記憶手段に記憶されている入力要素のうち、予測を行うべき入力要素の値の変化の予測を行う予測処理手段と、
上記予測処理手段によって予測された入力要素に基づいて、該当する命令区間を事前実行するとともに、該当入力要素のアドレスと一致する出力要素における上記カウント値の回数だけ、該当入力要素に対して行われるストアの回数を待機した上で主記憶からの読み出しを行って該当する命令区間の事前実行を行う第2の演算手段とをさらに備え、
上記第2の演算手段による命令区間の事前実行結果が上記入出力記憶手段に記憶されることを特徴とするデータ処理装置。

【請求項2】
 
上記入出力記憶手段が、上記第1の演算手段による命令区間の実行結果としての入力パターンおよび出力パターンを一時的に記録する入出力記録領域を備え、
上記入出力記録領域が、各出力要素に対して、ストアが行われた回数を格納するストアカウンタを有することを特徴とする請求項1記載のデータ処理装置。

【請求項3】
 
上記入出力記憶手段が、上記第1の演算手段によって演算が行われた命令区間毎に過去の実行結果の履歴を格納する履歴格納領域を備え、
上記登録処理手段が、上記入出力記録領域に記録された実行結果を上記履歴格納領域に格納するとともに、上記入出力記録領域に記録された実行結果の入力パターンに含まれる入力要素のうち、履歴格納領域に前回の実行結果として登録されている出力要素と同じアドレスの入力要素に対して、対応する前回の出力要素のストアカウンタを該入力要素に対するストアカウンタとして登録することを特徴とする請求項2記載のデータ処理装置。

【請求項4】
 
上記入出力記憶手段が、上記予測処理手段によって予測された入力要素を格納する予測値格納領域を備え、
上記予測処理手段が、上記履歴格納領域に格納されている入力要素のうち、実行履歴の間での値の変化量が一定である入力要素に関して値の予測を行い、上記予測値格納領域に格納することを特徴とする請求項3記載のデータ処理装置。

【請求項5】
 
上記入出力記憶手段が、ストアの回数を待機した上で主記憶からの読み出しを行うべき入力要素を格納する待機要アドレス格納領域を備え、
上記予測処理手段が、上記履歴格納領域に格納されている入力要素のうち、実行履歴においてアドレスが変化せず、実行履歴の間での値の変化量が不定である入力要素に関して、上記ストアカウンタ、および予測距離に基づく値としての待機カウンタを上記待機要アドレス格納領域に格納することを特徴とする請求項3記載のデータ処理装置。

【請求項6】
 
上記入出力記憶手段が、ストアの回数を待機した上で主記憶からの読み出しを行うべき入力要素を格納する待機要アドレス格納領域を備え、
上記予測処理手段が、上記履歴格納領域に格納されている入力要素のうち、実行履歴においてアドレス自体が変化し、それぞれのアドレスの値も、ストアが発生することにより変化する入力要素に関して、上記ストアカウンタに基づく値としての待機カウンタを上記待機要アドレス格納領域に格納することを特徴とする請求項3記載のデータ処理装置。

【請求項7】
 
請求項1ないし6のいずれか一項に記載のデータ処理装置が備える各手段が行う処理をコンピュータに実行させることを特徴とするデータ処理プログラム。

【請求項8】
 
請求項7に記載のデータ処理プログラムを記録したコンピュータ読取り可能な記録媒体。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2004347124thum.jpg
State of application right Registered
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.


PAGE TOP

close
close
close
close
close
close
close