JPH03214235A - 複数パス並列処理方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、複数の命令を同時処理するための複数パス並
列処理方法に関するものである。

［従来の技術］ 演算処理の高速化のために、複数の命令を同時実行する
ようにした処理装置の例として、特開昭６３−４９８４
３号、米国特許４　、７６６　、５６６号、及びヨーロ
ッパ特許８７１．１０７５１．２号に記載されたものが
あり、これらの特許は同一内容のものを各国に対して出
願したものである。この特許出願における主張は近年ス
ーパスカつという名前で呼ばれている並列化方式であり
、アドレスが連続する２つの命令を同時に実行するもの
である。米国特許４，７６６．５６６号のＦｊ（＜、２
−７に記載されているように、同時に実行される２つの
命令は単一の命令バッファに納められており、これらが
同時に実行される。この方式では、分岐が生じたときに
連続した命令の実行はできないから、一方の実行ユニッ
トで分岐命令が実行されたときに命令バッファをキャン
セルして分岐発生時の処理を行っている。

〔発明が解決しようとする課題］ 上記従来技術には１分岐命令による本質的な並列度の減
少という問題があった。即ち、一方の実行ユニノ１−の
分岐命令によって、命令バッファがキャンセルされてし
まい、このとき２つの実行ユニットが独立して動作でき
ない。従って、命令の並列度の抽出時に最適化を行う範
囲がエントリと分岐命令との間のみに限定されてしまう
。ここでエントリとは分岐命令の飛先あるいは分岐命令
の直後の命令を指す。分岐命令は５命令に１度以上の割
合で出現するといわれており、この状態では最適化はほ
とんど意味を持たない。２倍のハードウェア物景を投入
した割に２命令同時実行による性能向上の効果は少ない
、あるいは殆どないという結果となる。

本発明の１」的は、この分岐命令による並列度の減少を
解決し、分岐命令自身の並列化も可能とする複数パスＭ
１列処理方法を提供するにある。

し課題を解決するための手段］ 」１記の目的を達成するために、本発明においては、パ
イプライン構成された命令取り出し手段、デコード手段
及び命令実行手段から成るところの互いに独立動作可能
な処理系を複数個設け、さらに１つの処理系がその命令
を実行したときに他の処理系の動作を開始及び停止させ
るための分裂命令及び融合命令と、命令の実行がどこま
で進んだかを示すフラグと、該フラグを参照して各処理
系による命令の実行を制御する条件休止命令とを設けた
。

Ｃ作用］ １つの処理系により分裂命令が実行されると、他の処理
系の命令取り出し手段が上記分裂命令によってセットさ
れる命令アドレス、あるいはすでにセットされている命
令アドレスに従い命令用キャッシュメモリをアクセスす
る。これにより、それぞれの命令取り出し手段は異なる
プログラムカウンタを持つため、基本的に独立に動作し
、従ってそれぞれの側で処理中の命令列の内部での分岐
があっても、各処理系における並列処理を継続できる。

一方、このようにして独立に動作し始めた各処理系を再
び１本に絞り込む必要性もでてくる。このときは１つの
命令実行手段により融合命令を実行することにより、他
の処理系の命令取り出し手段の動作を停止させる。これ
にともない命令実行手段も停止される。即ちパイプライ
ンが絞り込まれる。融合命令によって停止したパイプラ
インは動作中のパイプラインによる分裂命令あるいは一
定時間ごとに行われるタイマチエツク機構によってのみ
再開される。

２つの処理系の処理の間にデータの依存関係がある場合
は、コンパイラが有する実行順序の情報に従って実行コ
ードの中に実行順序の制御のための命令、即ち条件休止
命令を埋め込む。複数の処理系の処理のパスにはそれぞ
れ同期用のフラグがあって、これらは分裂命令によって
その値を増加させられる。そして、条件休止命令は各処
理系のフラグの内容とそのときの自処理系の処理結果に
よって次の処理を待つか否かを判断し、これによって必
要なデータが得られた後に当該処理が行われるように各
処理系の処理の実行制御を行う。

〔実施例］ 以下１本発明の一実施例を詳細に説明する。第１図は本
発明を応用したプロセッサのブロック図である。命令フ
ェッチユニット１００及び１０２は、それぞれの内部に
独立動作するプログラムカウンタを持ち、４ｇ号縁線１
１１び１１２を用いて命令用キャッシュメモ１月０１に
対して命令フェッチ要求を出す。

キャッシュメモＩＪＩＯＩはこれらの片方を交互にある
いは両方を同時に受は付ける。対応するデータは同時に
受は付けられた場合にはそのまま、交互に受は付けられ
た場合にはキャッシュメモリ１０１の内部にバッファリ
ングされて、各サイクルごとに信号線１１４及び１１５
へ出力される。それぞれが独立に動作１■能なデコーダ
やシーケンサから成る制御ブロック＋０３及び１０４は
、キャッシュメモリ１０１からの命令をデコードした情
報をもとに、信号線＋１８及び１１９を用いて下記の命
令実行部を並列に制御したり、分岐命令などの情報をも
とに信号線１１３及び１．１６とデータ線１２２及び１
２ｇを用いて命令フェッチユニット１００及び１０２を
も制御する。制御ブロック１０３及び１０４は信号線１
１７によって相互に接続されており、例えば両者の同期
をとるときなどにこの信号が利用される。命令実行部は
１つのレジスタファイル１０６と２つの実行ユニット１
０５及び１０７から構成される。レジスタファイル１０
６の一部と実行ユニット１０５は制御信号１１８によっ
て、レジスタファイル１０６の一部と実行ユニット１０
７は制御信号１１９によってそれぞれ制御される。制御
信号１１８と１１９によって制御されるレジスタファイ
ル１０６の各部分の間には共通部分があってもなくても
よい。実行ユニット１０５及び１０７はそれぞれ独立し
たソースデータバス１２０及び１２１を持ち、またそれ
ぞれ演算結果をファイル１０６へ格納するためのターゲ
ットデータバス１２４及び１２６を持っている。

メモリアクセスは、実行ユニット１０５及び１０７が計
算したメモリアドレスをメモリアクセスコントローラ１
０８及び１１０へ渡し、これらコントローラ１０８及び
１１．０はデータ用キャッシュメモリ１０９に対してア
クセス要求１２９及び１３０を出すことにより行われる
。キャッシュメモリ１０９はこれらの信号を交互あるい
は同時に受は付け、ロード／ストア専用バス】２５を介
してレジスタファイル１０６に対してデータの供給を行
う。

第１図における左右のリソースは特殊な場合を除いて独
立に動作可能であり、プログラムの並列性を抽出し同時
に実行するのに適した構成となっている。極端な場合を
考えると、左右で全く別のプログラムを実行させること
もできる。一方、第１図において左右で共有されている
命令用キャッシュメモ＋Ｊ１０１、レジスタファイル１
０６及びデータ用キャッシュメモリ１０９の内部構造は
、プロセッサの実現方法や使用目的によって多少異なる
可能性がある。即ちキャッシュメモリ１０１．１０９の
内部は２つのキャッシュメモリから構成されてもよし）
し、１つのマルチボートキャッシュメモリから構成され
てもよい。また、フェッチ要求を交互に受は付けること
ができる１つのキャッシュメモリで構成し、命令取り出
しユニットに得られた命令をバッファリングする手段を
持ち、あたかも毎サイクルフェッチしたように見せかけ
るという方法もある。レジスタファイル１０６の内部は
左右で完全に共有されたレジスタファイルでもよいし、
全く独立した２つのレジスタファイルから構成されても
よい。無論部分的に共有する形態のものも考えられる。

共有される部分には、左右に分配される独立したバス１
２０．１２１をもつ必要がある。

次に、このようにして実現されたシステムの動作を第２
図を用いて説明する。タロツク信号に１はマシンサイク
ルの前半で高レベル、後半で低レベルの信号であり、こ
の１サイクルで各部が決められた処理を行う。命令用キ
ャッシュメモＩＪＩＯＩの出力信号１１．４．１１５は
それぞれ２命令分のビット幅を持っており、それゆえに
命令読み出しは２サイクルに一度行えばよい。出力信号
１１４は制御ブロック１０３でデコードされ１次のステ
ージの信号１１８となる。この信号によって更に次のス
テージにおいてデータ１２０がそのまた次のステージに
おいてデータ１２４が制御される。このように１つの命
令を一連の処理に分割することによって命令の並列処理
化を図るパイプラインを構成する。右半分を動作させる
信号線１１５．１１９．１２１．１２６に関しても同様
であるが、ここでは動作していないものとする。

これらの信号、即ち第１図の右半分に動作させるために
、このプロセッサは特別な命令あるいは命令コード内に
埋め込まれた特別なフィールドを有する。このような命
令をここでは分裂命令（Ｆ−ｉｓｓｉｏｎ　Ｂ　ｒａｎ
ｃｈ　Ｉ　ｎ５ｔｒｕｃｔｉｏｎ）と呼ぶことにする。

この分裂命令がタイムスロットＳ１に実行ユニット１０
５で実行されたとすると、第２図における制御信号２０
１がオンとなり、命令フェッチユニット１０２が動作可
能となる。ユニット１０２は分裂命令によってセットさ
れるアドレス、あるいは既にセットされているアドレス
に従い命令用キャッシュメモリ１０１をアクセスする。

これにより第１図の右半分のパイプラインも動作開始す
ることになる。第１図の右半分と左半分は独立に動作す
る。

一方、このようにして独立に動作し始めたパイプライン
を再び一本に絞り込む必要もある。そのため、分裂の場
合と同様にこのプロセッサは特別な命令あるいは命令コ
ード内に埋め込まれた特別なフィールドを有する。この
ような命令を融合命令（Ｆ　ｕｓｊｏｎ　Ｂ　ｒａｎｃ
ｈ　Ｉ　ｎ５ｔｒｕｃｔｉｏｎ）と呼ぶことにする。こ
の融合命令がタイムスロットＳ２に実行ユニット１０５
で実行されたとすると、第２図における制御信号２０２
がオンとなり、命令フェッチユニット１．００が動作を
停止する。これにともない制御ブロック１０３及び実行
ユニット１０５も停止され、左半分のパイプラインが完
全に停止する。即ちパイプラインが右半分のみに絞り込
まれる。融合命令によって停止したパイプラインは、動
作中のパイプラインによる分裂命令あるいは一定時間ご
とに行われるタイマチニック機構によってのみ再開され
る。また、この融合命令によって並列処理が停止されて
いるとき、従来のスーパスカラ方式により停止された処
理系を利用するようにすることもできる。

次に、このようなプロセッサを用いた場合の効果的なプ
ログラミングについて第３図及び第４図を用いて説明す
る。ここでは、比較の対象として連続アドレスの２命令
を同時に処理するスーパスカラマシンをとりあげる。ス
ーパス力うマシンはハードウェア物量が制約された条件
、たとえば集積度が低いＬＳＩを用いて実現する場合な
どに有効な方式であるが、連続アドレスの２命令という
制約条件があるために並列度が向上しないという問題点
がある。この方式による高速化の割合は、せいぜい１か
ら２割程度と推定される。

第３図では実行サイクル数の異なる８命令（○Ｐ３０１
〜ＯＰ３０ｇ）を両者で実行した場合を示している。簡
単のために各命令の間にデータの競合関係はないものと
する。ＯＰ２Ｏ３，ＯＰ２Ｏ３，ＯＰ２Ｏ３゜０Ｐ３０
８は実行に２サイクル要する命令であり、残りの命令は
１サイクルにて実行可能とする。第３図の左側はスーパ
ス力うマシンの例を示している。スーパス力うマシンは
連続アドレスの２命令を同時に処理するため、それらの
命令は同時に実行が開始される。そのため同時実行され
る命令の処理時間が異なると、ところどころ空きが生じ
、全体の実行にタイムスロットＴ１〜Ｔ８の８サイクル
を要する。一方、第３図右側に示した本発明による複数
パス並列処理方法においてはこのような制約がないため
、タイムスロットＴ１〜Ｔ６の６サイクルにて実行を終
了する。

以上は分岐のない簡単な場合の比較であるが、より重要
な相違点として、並列化の割合が本質的に異なることが
あげられる。即ちスーパスカラマシンにおいては連続の
２命令が必ずしも同時に実行可能と出来ないので、最適
化コンパイラを用いてコートを生成したとしても並列化
不可能な部分は本質的になくならない。分岐命令などが
そのよい例である。スーパス力うマシンにおいては分岐
は一度に１つしか実行できず、しかも分岐の入り口と次
の分岐命令との間の少ないコードの範囲内でしか並列度
を抽出できない。分岐命令は５命令に１度出現すると言
われており、平均４命令の間で並列度を抽出することに
なる。第４図に分岐命令を含むコードの例を示す（ＯＰ
４０１〜０Ｐ４０８）。

０Ｉ）４０３及び０Ｐ４０８は条件分岐命令であり、そ
れぞれＯＰ２Ｏ３，ＯＰ２Ｏ３へ分岐する。０Ｐ４０３
は７回分岐を行い１回は分岐しない。また０Ｐ４０８は
５回分岐を行い１回は分岐しない。従って０１）４０１
カら０Ｐ４０３は８回、０Ｐ４０４から０Ｐ４０８は６
回実行される。条件分岐命令において分岐する場合には
その実行に４サイクルを要し、分岐しない場合及びその
他の命令は１サイクルにて実行が終了するものとする。

第４図（ａ）に示したパイプラインの本数が１本の従来
型のアーキテクチャをとった場合（シングルモード）は
、実行命令が５４、分岐が１２回あるため、全体で９０
サイクル要することになる。第４図（ｂ）に示したスー
パスカラモードの場合には、ＯＰ２Ｏ３ト４０２、ＯＰ
　４０４　ト４０５および０Ｐ４０６と４０７がそれぞ
れ並列可能であり実行される命令対の数は３４、分岐は
シングルモードと同様に１２回あるので、全体で７０サ
イクルとなる。これに対し、第４図（Ｃ）に示した本発
明による複数パス並列処理方法を用いれば２つのループ
を別々のパイプラインにｍｌ　ＩＪ当てることができる
ため、分岐命令も含めて並列化が可能となる。即ち０Ｐ
４０１〜４０３をプロセッサの左半分のパイプラインに
割り当て、残りを右半分に割り当てる。プロセッサの左
半分のパイプラインの実行時間は命令数が２４、分岐回
数が７であるため、全部で４５サイクルとなる。また、
プロセッサの右半分のパイプラインの実行時間は命令数
が３０、分岐回数が５であるため、全部でやはり４５サ
イクルとなる。従って全体の実行時間は４５サイクルと
なり、シングルモードの９０サイクルと比較して２倍の
並列度を抽出したことになる。無論、分裂分岐に伴うオ
ーバーヘッドはあるが、ループ回数が大きくなればこの
影響は十分無視できる程度になる。これが本発明がスー
パスカラモードに対して本質的に優れている理由である
。

さて、このような複数パス並列処理方法を用いた場合に
おいて、２つのパス即ち２つのパイプラインの間にデー
タの依存関係がある場合についても考慮しなければなら
ない。何故ならば、このような状況が生じる可能性は極
めて高く、これに対する対策なくしては複数パス並列処
理方法の本質的な高性能性を導きだすことは不可能とな
るからである。第５図は複数パス並列処理方法によるあ
るプログラムの流れを示したものである。本プロセッサ
のパイプラインは分裂命令５０１によって２つに分かれ
るが、それぞれパスは互いに関連をもって動作する。即
ち手続き５０４において第１番目のレジスタあるいはメ
モリに対して書き込み（Ｗｌ）が行われ、それをもう一
方のパスの手続き５０９で参照する（Ｒ１）。手続き５
０９はさらに第２番目のレジスタあるいはメモリに対し
て書き込み（Ｗ２）を行い、それを手続き５１２で参照
する（Ｒ２）。また、同時に手続き５０８では第３番目
のレジスタあるいはメモリに対して書き込み（Ｗ３）を
行い、それを手続き５１３で参照する（Ｒ３）。

その後、融合命令によってパイプラインの一本化が行わ
れる。第５図のプログラムの流れはデータの依存関係に
よって、その実行順序が規定される。

即ち毛続き５０４は手続き５０９より先に、手続き５０
８は手続き５１３より先に、そして手続き５０９は手続
き５１２より先にそれぞれ実行されなければならない。

このような実行順序はハードウェアでは制御不可能であ
るが、このプログラムのコードを生成するコンパイラは
実行順序の情報を持っているため、コード中に実行順序
制御のための命令を埋め込むことができる。この命令に
条件休止命令（Ｉ　ｎｃｒｅｍｅｎｔ　ａｎｄ　Ｃｏｎ
ｄｉｔｉｏｎａｌ　Ｐａｕｓｅ）と呼ぶことにして、そ
の動作について説明する。前述の説明の通り、手続き５
０４は手続き５０９より早く実行されなければならない
。そこで、条件休止命令５０６．５０７を用いて同期を
とる。２つのパスにはそれぞれ同期用のフラグ５０２．
５０３があって、これらは分裂命令５０１によってリセ
ットされ、条件休止命令によってその値を増加させられ
る。条件休止命令５０７は手続き５０９の実行を手続き
５０４の実行終了まで待たせる働きをするものである。

手続き５０４の実行終了時には、条件休止命令５０６が
実行されており、フラグ５０２は１となっている。条件
休止命令５０７はフラグ５０３を１にしてフラグ５０２
と比較する。このとき、条件休止命令５０７はフラグ５
０２の内容を信号線５１５を用いて参照できる。もしも
フラグ５０２がＯの場合、即ちフラグ５０２がフラグ５
０３と等しくない時には、条件休止命令５０７はパイプ
ラインを停止して条件休止命令５０６の実行終了を待つ
。条件休止命令５１０と５１１に関しても同様であるが
、手続き５１２及び５１３はそれぞれ手続き５０９及び
５０８が終了していないと実行開始不能であるので、相
手のフラグと値が等しくない場合にパイプラインを停止
するという判定条件を持つ条件休止命令を使用する。

このようにして誤動作なく目的のプログラムを並列に実
行できる。

［発明の効果コ 本発明によれば、命令取り出し部分を複数もつことによ
り、分岐命令による並列度の減少を解決し、分岐命令自
身をも並列化できるので、問題プログラムから並列度を
１．００％抽出することができる。また、複数の命令実
行部の同期をとるための命令とハードウェアを採用する
ことにより、誤動作なく命令の実行順序を制御できる。

【図面の簡単な説明】

第１図は本発明の方法を適用した処理装置の一実施例を
示すブロック図、第２図は第１図の処理装置におけるパ
イプライン制御の説明図、第３図及び第４図は従来方法
と本発明の方法によったときの処理例を示す図、第５図
は命令間にデータ依存関係があるときの実行順序制御方
法の説明図である。 １００、１０２・・・命令フェッチユニット、１０３．
１０４・・制御ブロック、１０５．１０７・・・実行ユ
ニット、５０２゜５０３・・フラグ。

Claims (1)

1. 【特許請求の範囲】 １、メモリから命令を取り出す命令取り出し手段、該手
   段により取り出された命令のデコード手段、及び該手段
   によりデコードされた命令の実行手段より成るところの
   独立動作可能な処理系の複数個と、分裂命令及び融合命
   令とを設けるとともに、１つの処理系により処理中の命
   令列に同時処理可能な命令が存在するときには、当該処
   理系で分裂命令を実行させることにより他処理系による
   同時並列処理を開始し、複数の処理系による同時並列処
   理を１つの処理系の処理へまとめるときには、当該１つ
   の処理系によって上記融合命令を実行させることにより
   上記１つの処理系以外の上記同時並列処理を行っていた
   処理系の動作を停止することを特徴とする複数パス並列
   処理方法。 ２、前記複数の処理系によって同時並列処理を行う場合
   に、複数の処理系の各々にフラグを設け、さらに上記処
   理系の処理対象とする命令列の中に条件休止命令を挿入
   するとともに、同時並列処理の開始を指示する前記分裂
   命令によって各処理系の上記フラグをクリアし、各処理
   系が上記条件休止命令を実行したときには自処理系のフ
   ラグを＋１更新しかつ他処理系のフラグを調べ、もし自
   処理系と他処理系のフラグの値が異なるときはその値が
   一致するまで自処理系の次の命令の処理を休止すること
   を特徴とする請求項１記載の複数パス並列処理方法。 ３、前記融合命令が実行されたときに、該融合命令を実
   行した処理系で継続される処理の連続する命令の一部を
   、該連続する命令が分岐命令を含まないときに上記融合
   命令により動作を停止された処理系により同時並列処理
   することを特徴とする請求項１記載の複数パス並列処理
   方法。