JPH1091592A

JPH1091592A - 並列計算機

Info

Publication number: JPH1091592A
Application number: JP8245930A
Authority: JP
Inventors: Tatsuo Higuchi; 達雄樋口; Hideki Murahashi; 英樹村橋; Shigeo Takeuchi; 茂雄武内; Tatsu Toba; 達鳥羽; Toshiaki Tarui; 俊明垂井; Katsuyoshi Kitai; 克佳北井
Original assignee: Hitachi ULSI Engineering Corp; Hitachi Ltd
Current assignee: Hitachi Ltd; Hitachi Solutions Technology Ltd
Priority date: 1996-09-18
Filing date: 1996-09-18
Publication date: 1998-04-10
Anticipated expiration: 2016-09-18
Also published as: JP3789011B2

Abstract

(57)【要約】【課題】データ受取りノードでのデータ到着確認の負
荷を減らす。【解決手段】複数のノードに分散されたデータを読み
出すときに、読み出されたデータを受信したことを示す
共通のフラグ３７に各データが到着したときに演算回路
５６により１を加え、このフラグ３７の値が全てのノー
ドからのデータ受信完了を表す値と一致したことを一致
判定回路５３で判別し、一致している場合にプロセッサ
２４に割込を発生させるアンド回路５９を設ける。【効果】プロセッサ２４は分散されたデータ全体を受
信したときにのみ割込を受信することができ、無駄な割
込により本来処理を阻害しない。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、複数のプロセッサ
を有する計算機システムにおいて、これらのプロセッサ
により共有されている資源を持つ並列計算機に関し、特
にそれぞれプロセッサを有する複数のノードがネットワ
ークを介して結合されている並列計算機において資源を
複数のノードに分散配置する並列計算機の構成方法に関
する。

【０００２】

【従来の技術】大量のメディア情報を供給するメディア
サーバとしては、複数のプロセッサから構成される並列
計算機かまたは複数の計算機からなるクライアント・サ
ーバ型の分散処理システムが知られている。本明細書で
は、並列計算機を構成する複数のプロセッサとクライア
ント・サーバ型の分散処理システムを構成する複数の計
算機とを区別することなく言及するするために、分散処
理システムの分散処理を実行する計算機要素を「ノー
ド」と呼ぶ。

【０００３】メディア情報は並列計算機内の複数のディ
スク装置に分散して保持されることが多く、ユーザから
のアクセス処理要求は複数のノードの協調動作により処
理される。

【０００４】たとえば、メディアサーバの例としては、
映画などの大量の映像情報を格納し、複数のユーザに映
像情報を供給するビデオオンデマンドサーバがある。映
像情報は供給時間が延びてしまうと画像の途切れや画面
のちらつきが発生するという特徴をもつ。このため、遅
延時間の短縮は重要な課題である。

【０００５】ところで、ビデオオンデマンド処理に関し
ては遅延時間の短縮に関して考慮しなければならないこ
とがある。それは、メディア情報へのアクセスパターン
である。つまり、ビデオオンデマンドサーバは、複数の
ユーザが同時に異なるタイトルをアクセスする場合と、
同一のタイトルをアクセスするいずれの場合において
も、高速に映像情報を提供しなければならない。

【０００６】前者の課題を解決するためには、映像情報
をタイトル毎に複数のノードに分散配置すればよい。こ
れにより、複数のノードに負荷を分散させることができ
る。ユーザは自分の見たいタイトルを格納しているノー
ドと交信し、映像データを供給して貰えばよい。ユーザ
により同時に要求される複数のタイトルが均等に複数ノ
ードに分散されていれば、処理負荷を分散させることが
できる。

【０００７】しかし、この構成では後者の課題を解決で
きない。上記のシステム構成において、同一タイトルに
アクセスが集中した場合、分散システムを構成するノー
ド数が大きい場合でも負荷はそのタイトルを格納してい
るノードのみにかかってしまう。これでは１ノードから
なるシステムと性能が変わらない。

【０００８】そこで、一つの映像タイトルを複数のセル
データに分割し、セルデータをハッシュ関数等の分配条
件にしたがって、複数のディスクに分散配置を行う方法
がよく用いられる。これは「ストライピング」と呼ばれ
る。例えば、参考文献１：「日経エレクトロニクス」６
０２号、１９９４．２．２８号、第１３頁〜第１４頁参
照。このストライピングをディスクからノードに拡張
し、同一タイトルを複数のノードに分散配置することを
「ノード間ストライピング」と呼ぶ。これにより、たと
え同一タイトルに対して複数のユーザからアクセスがあ
った場合にでも、複数ノードに負荷を分散させることが
でき、分散システムの処理性能を向上させることができ
る。

【０００９】

【発明が解決しようとする課題】しかしながら、従来の
ノード間ストライピング方法をビデオオンデマンドサー
バに適用した場合には、次ぎの問題が生じる。

【００１０】一人のユーザに対して映像データを供給す
るノード（インターフェスノードと呼ぶ）は映像データ
の連続性保証や順序保証を行わなければならず、ノード
間ストライピングにより分散格納されたセルデータを集
めてからユーザに供給する必要がある。

【００１１】ところが、分散処理システムでよく用いら
れるデータ交換方法としてＴＣＰ／ＩＰを用いた場合に
は、転送されたセルデータを格納するメッセージが到着
するたびに割込やアクノリッジ返送などのソフトウエア
処理が必要である。このソフトウエア処理はインタフェ
ースノードが本来行っているユーザインタフェース処理
を邪魔してしまう。また、このオーバヘッドはノード間
ストライピングを行うノード数に比例して増加するた
め、性能を向上するためデータ供給ノードを増やすとか
えってインタフェースノードはセルの到着確認に忙殺さ
れ、ユーザインタフェース処理がますます邪魔され、ユ
ーザサービスの質が低下する。

【００１２】また、映像情報は大規模であるため、例え
ば２時間の映画を見る場合にはデータを格納しているノ
ードからインターフェスノードへのデータ供給性能は、
ユーザに映像の途切れを感じさせない程度に速くなけれ
ばならない。このためにデータを格納しているノードか
らインタフェースノードへ連続的にデータを供給する必
要がある。（以下、ストリーム処理と呼ぶ。）このスト
リーム処理を実現するためにはデータの受取り側と送り
手側でフロー制御を行う必要がある。

【００１３】フロー制御方法としてＴＣＰ／ＩＰではパ
ケットを受信する毎に割込を発生し、ＯＳ（オペレーテ
ィングシステム）が受信バッファの容量を計算してアク
ノリッジとして返送する。参考文献２：「ＵＮＩＸ
４．３ＢＳＤの設計と実装」第３７４頁〜第３９７頁、
Ｓ．Ｊ．Ｌｅｆｆｌｅｒ他著（１９９１）。

【００１４】しかし、このようなフロー制御方法では次
の問題が起る。ノード間ストライピングにより１つのイ
ンタフェースノードが相手をしなければならないデータ
供給ノードの数が増えるにしたがって、フロー制御情報
を送信ノードに返送する回数が増大し、本来の処理であ
るユーザインタフェース処理が邪魔されてしまう。

【００１５】そこで、本発明の第１の目的は、複数ノー
ドに分散している資源（映画情報等のデータ等、またプ
ロセス等もデータと考える）をアクセスする場合に、分
割されたデータが集まったことを高速に確認することが
できる並列計算機を提供することである。

【００１６】そして、本発明の第２の目的は、ノード間
でのデータの転送に関して高速なフロー制御のできる並
列計算機を提供することである。

【００１７】

【課題を解決するための手段】第１の目的を実現するた
めに、本発明の並列計算機は、少なくとも１つ以上のプ
ロセッサをそれぞれ有する複数のノードと、上記複数の
ノードの間でメッセージを交換するための上記ノードを
相互に接続するネットワークとからなる並列計算機にお
いて、該複数のノードにより利用可能な少なくとも１つ
の資源と、その資源を複数のノードに分割して格納する
手段を有し、その資源に対してアクセス要求を行うノー
ドは、その資源を分割格納している複数のノードに対し
て一連のアクセス要求を行うときに、該一連のアクセス
要求に対してアクセス結果が返答されたか否かを格納す
る手段（フラグと呼ぶ）を有し、該アクセス要求を受け
付けたノードは、該アクセス要求に対してアクセス結果
を返答するときに、アクセス結果とともに該フラグに対
して自ノードがアクセス結果を返したことを記録するた
めに、該フラグを指定する手段と、該フラグに対する記
録方法を指定する手段とを有し、アクセス要求を行った
ノードは、該アクセス結果を受け取ったときに、付帯す
る該フラグを指定する手段で示されるフラグに対して、
該フラグに対する記録方法で指定された手段で記録を行
い、そのフラグが全てのノードから返答があったことを
示すか否かを判定する手段と、全てのノードから返答が
あったと判定された場合に該プロセッサに割込を発生す
る回路を有する。

【００１８】また第２の目的を実現するために、本発明
の並列計算機は、少なくとも１つ以上のプロセッサをそ
れぞれ有する複数のノードと、上記複数のノードの間で
メッセージを交換するための上記ノードを相互に接続す
るネットワークとからなる並列計算機において、該並列
計算機は該複数のノードにより利用可能な少なくとも一
つの資源を有し、該ノードには、その資源を直接アクセ
スする手段を有する第１のノードと、直接アクセスでき
ない第２のノードがあり、該第２のノードは、該資源を
アクセスする場合に、複数のアクセス結果を格納する手
段を有し、該第１のノードは、該アクセス結果格納手段
の空き数を格納する手段と、該アクセスに対する結果を
第２のノードに返答するときに、上記格納手段に格納さ
れた該空き数を減少させる回路を有し、該第２のノード
は、該アクセス結果を利用することにより、該アクセス
結果格納手段を解放した場合に、該第１のノードにある
該空き数を格納する手段に納められた空き数を増加させ
る回路を有し、該第１のノードは、該第２のノードの該
アクセス結果格納手段に空きがあるか否かを判定する回
路と、該空きの判定の結果が空きがない場合にアクセス
結果の返答を遅延させる手段を有する。

【００１９】

【発明の実施の形態】以下、本発明にかかわる並列計算
機を図面に示した実施の態様を参照してさらに詳細に説
明する。なお、以下においては、同じ参照番号は同じも
のもしくは類似のものを表わすものとする。なお、以下
では実施の態様の１つの例を実施例と呼ぶ。

【００２０】（１）実施例図１に本実施例１による並列計算機を示す。この並列計
算機では、複数のノード２はネットワーク１により結合
され、各ノード２は、少なくとも一つのプロセッサ２４
と、ディスク装置２５を含み、このディスク装置２５内
に、ノード間ストライピングにより分散されたデータが
保持されている。各データは、それを保持するノード
（データ供給ノード）のみからアクセス可能であり、こ
のデータをアクセスしたい他のノード（データ消費ノー
ド）は、このデータ供給ノードにデータ供給要求を行
う。

【００２１】なお、この並列計算機では、全てのノード
は同じ構成をとり、同一の処理を行うことができが、本
実施例では説明をわかりやすくするために図１におい
て、ノード＃０、ノード＃１をデータ供給ノード、ノー
ド＃２をデータ消費ノードと位置付ける。そして、ノー
ド＃２がノード＃０、ノード＃１に分散配置されたデー
タをアクセスする場合について説明する。

【００２２】本実施例１ではノード＃０、ノード＃１の
ディスク装置２５に分散格納されたデータ３５をノード
＃２が読み出すときに、ノード＃０が転送したデータと
ノード＃１が転送したデータの両方が揃ったことを高速
に判定することが第１の特徴である。そして、データ消
費ノードではデータ供給ノードから連続的にデータを受
信できる様に循環バッファ３８を有している。この循環
バッファ３８の空き容量をデータ供給ノードが高速に判
定できることが第２の特徴である。これら２つのために
ノード２にはイベント制御回路５００と、循環バッファ
へのデータの到着を示すフラグ３７とこのフラグを操作
するためのフラグレジスタ５８とフロー制御レジスタ群
５２が設けられている。循環バッファ３８はデータ供給
ノードからのデータ転送と、データ消費ノードが転送さ
れたデータを用いてユーザにサービスを提供する処理を
並行して行うために設けられ、図２に示すような構成を
とる。すなわち、ノード＃０、ノード＃１からそれぞれ
転送されたデータを格納するバッファエリア、ノード＃
０用［ｍ］，ノード＃１用［ｍ］と、これらが到着して
いるか否かを示すフラグ［ｍ］である。データ供給ノー
ドはｍ＝０から順番にデータをデータ消費ノードに転送
し、データ消費ノードはｍ＝０から順番に消費してい
く。

【００２３】フラグレジスタ５８はノード２がメッセー
ジ１１を受信したときにローカルメモリ上のフラグ３７
を一時的に格納するレジスタである。

【００２４】また、フロー制御レジスタ群５２は循環バ
ッファ３８の空き容量を管理するレジスタでデータ供給
ノードで用いられる。データを転送すべきノード、ここ
ではデータ消費ノードの循環バッファ３８の空き容量を
格納する。本実施例では、データ供給ノードがデータを
データ消費ノードに転送した場合に該当するフロー制御
レジスタを減少させ、データ消費ノードが転送されたデ
ータを処理し終えたら、データ供給ノードの該当フロー
制御レジスタを増加させることに特徴がある。これによ
り、データ供給ノードは該当するフロー制御レジスタが
０より大きければ、データを転送することができると判
断可能であるとともに、データ消費ノードはメッセージ
の到着した時ではなく、データを消費する時にフロー制
御を行うことができる。したがって、データ消費ノード
では、ユーザへのサービス処理への無駄な割込が防止で
きる。

【００２５】以下、本実施例の回路とその動作の詳細を
説明する。

【００２６】（ノード２）図１に示すように各ノード２
は、データ供給プログラム３１やデータ消費プログラム
３２を実行するプロセッサ２４と、ローカルメモリ２３
と、ノードに分散されたデータ３５を格納するディスク
装置２５と、本実施例で特徴的な高速フロー制御処理を
行うための送信制御回路２１と、受信制御回路２２とか
ら構成される。この並列計算機は、いわゆる分散メモリ
型並列計算機で、ローカルメモリ２３は他のノードから
はアクセスできず、そのローカルメモリの属するノード
のみアクセス可能である。そして、ローカルメモリ２３
にはそのノードで実行されるプログラムやそのプログラ
ムが使用あるいは生成するデータを格納する。さらに、
本実施例ではデータ供給ノードではディスク装置２５か
ら読み出したデータ３５が一時的に格納された転送デー
タ３６が置かれる。一方、データ消費ノードではデータ
を受け取るための循環バッファ３８とそのフラグ３７が
置かれる。

【００２７】また、このノード内の各回路は、システム
バス２６に接続され、メモリマップドＩＯ方法により、
プロセッサ２４からロード命令やストア命令などのメモ
リアクセス命令でローカルメモリ２３と区別することな
くアクセスすることができる。

【００２８】送信制御回路２１はメッセージ生成回路４
１と、送信パラメータ格納レジスタ４２と送信状態レジ
スタＳＴ４３から構成される。受信制御回路２２は入力
バッファ５１と、メモリアクセス回路６０とフロー制御
レジスタ群５２とから構成される。メモリアクセス回路
６０はネットワークから受信したデータをローカルメモ
リ２３に書き込んだり、フラグ３７を読み出してこれを
更新して書き戻す。イベント制御回路５００は、２つの
入力が同一か否かを判定する一致制御回路５３と、２つ
の入力の大小を比較する大小判定回路５４と、２つの入
力の加算、減算、ビットセット、ビットリセット、を行
なう演算回路５６と、セレクタ５５、５７、６１と、ア
ンド回路５９とからなる。

【００２９】（ネットワーク１）ネットワーク１は、形
態は特に規定しないがメッセージ１１のノード番号Ｎａ
ｄで示されるノードにメッセージを伝達する。例えば、
特願平６−５３４０５号明細書に記載されたものと同じ
でよい。

【００３０】以下では、ノード＃０、ノード＃１のディ
スクに格納されたメディアデータ３５をノード＃２が読
み出す手順を説明する。

【００３１】（フロー制御レジスタ群５２の初期化）各
ノード２はシステムの起動時にフロー制御レジスタ群５
２を０に初期化する。

【００３２】（循環バッファ３８の初期化）ノード＃２
はメディアデータを読み出すための循環バッファ３８と
その読み出し完了を表すフラグ３７をローカルメモり２
３に確保し、フラグ３７には初期値として０を書き込
む。この循環バッファ３８は図２に示すようにノード＃
０用のデータ領域とノード＃１用のデータ領域とそのフ
ラグを１組として（ｍ＋１）組ある。後から述べるよう
にノード＃０、ノード＃１はこの循環バッファ３８の先
頭からデータ転送の宛先として用い、（ｍ＋１）組目ま
で進む。そして、次は０組目へと循環して用いる。この
ように循環して用いることにより、循環バッファ３８よ
りも大きなメディアデータを読み出して、例えば表示装
置に表示するなどの処理を行なうことができる。

【００３３】（ノード＃０、ノード＃１への読み出しリ
クエスト）ノード＃２はノード＃０へ読み出すべきメデ
ィアデータのタイトルと、受信する循環バッファ３８の
ノード＃０用のエリアのアドレスと、フラグのアドレス
と、循環バッファ３８の大きさ（ｍ＋１）と、フロー制
御に用いるフロー制御レジスタのＩＤであるＲ＃を、ネ
ットワークを介して伝える。図１には記載されていない
が、これはイーサネットなどの従来技術を用いても構わ
ない。同様にノード＃１へも読み出しリクエストを伝え
る。さらに本実施例で特徴的なノード間ストライプ数を
ノード＃２はノード＃０とノード＃１に伝達する。ここ
ではノード＃０とノード＃１への２分割であるため２で
ある。一般的にｎ台のノードに分割されている場合には
ｎである。またこの時、用いるフロー制御レジスタには
０が設定されている。これは、ノード＃０のデータ供給
プログラム３１からは循環バッファ３８に空きがないこ
とと等価にみえる。このため、ノード＃０、ノード＃１
はデータの供給を停止して、フロー制御レジスタが０よ
り大きくなることを待つ。

【００３４】（ノード＃０、ノード＃１への読み出し開
始指示）この段階ではノード＃０およびノード＃１はノ
ード＃２の循環バッファ３８に空きがない状態であると
認識しているため待機している。そこで、ノード＃２は
自ノードのデータ消費プログラム３２の準備が完了した
ところでノード＃０およびノード＃１に読み出し開始指
示を次の手順にしたがって行う。この開始指示はより具
体的にはノード＃０およびノード＃１のフロー制御レジ
スタに循環バッファ３８の空き容量を設定することであ
る。

【００３５】すなわち、システムバス２６を介してプロ
セッサ２４は送信パラメタ格納レジスタ４２に次の値を
設定し、メッセージをノード＃０、ノード＃１に送信す
る。

【００３６】Ｎａｄ：＝ノード＃０またはノード＃１の識別子ＣＴＬ（Ｒ）：＝１［フロー制御レジスタ群宛のメッセ
ージであることを示す］ＣＴＬ（Ｒ＃）：＝宛先のフロー制御レジスタ識別子Ｄａｄ：＝０［このメッセージでは参照されない］Ｄｌｎ：＝０［このメッセージでは参照されない］Ｆａｄ：＝０［このメッセージでは参照されない］Ｉｎｔ：＝０［このメッセージでは参照されない］Ｄ０：＝０［このメッセージでは参照されない］Ｄ１：＝（ｍ＋１）［循環バッファ３８の容量］Ｃｔ０：＝０［このメッセージでは参照されない］Ｃｔ１：＝値設定を表すコードＴａｄ：＝０［このメッセージでは参照されない］このように送信パラメタを設定することにより、メッセ
ージ生成回路４１はメッセージ１１を生成し、ネットワ
ーク１へ送出する。そして、送信状態レジスタＳＴ４３
に送信完了を表すコードを書き込む。

【００３７】ネットワーク１はメッセージ１１のＮａｄ
が示すノード、ここではノード＃０またはノード＃１へ
メッセージを配送する。

【００３８】次に上記メッセージを受信したノード＃０
およびノード＃１の動作について説明する。

【００３９】ノード２ではネットワーク１から受信した
メッセージ１１を一時的に入力バッファ５１に格納し、
各フィールドの切出しを行う。本メッセージはＣＴＬ
（Ｒ）＝１であることから本メッセージはフロー制御レ
ジスタに対する更新要求であると判断する。また、Ｃｔ
１が「値設定」であることから、イベント制御回路５０
０はセレクタ５７にＤ１を選択するように制御し、フロ
ー制御レジスタ群５２からＣＴＬ（Ｒ＃）で示されるレ
ジスタに対し、Ｄ１に格納された（ｍ＋１）を書き込
む。

【００４０】これによりフロー制御レジスタ［Ｒ＃］に
は循環バッファ５８の空き容量として（ｍ＋１）が設定
された。

【００４１】（データ供給ノードからのデータ転送）一
方ノードのプロセッサ２ではデータ供給プログラム３１
がシステムバス２６を介してフロー制御レジスタ［Ｒ
＃］を監視し、０より大きくなるまで待機している。上
記ノード＃２からの読み出しリクエストによりフロー制
御レジスタ［Ｒ＃］は（ｍ＋１）になっているため、デ
ータ供給プログラム３１はデータ転送処理を次の手順に
従い行う。

【００４２】プロセッサ２４はディスク装置２５からデ
ータ３５をシステムバス２６を介して読みだし、ローカ
ルメモリ２３に転送データ３６として格納する。そし
て、このデータをノード＃２に転送する。

【００４３】すなわち、プロセッサ２４はシステムバス
２６を介して送信パラメタ格納レジスタ４２に次のよう
にパラメタを設定する。

【００４４】Ｎａｄ：＝ノード＃２の識別子ＣＴＬ（Ｒ）：＝０［フロー制御レジスタ宛ではなく、
メモリ宛であることを示す］Ｄａｄ：＝ノード＃０（またはノード＃１）用データ格
納領域［ｉ］の先頭アドレス、一番最初はｉ＝０であ
る。Ｄｌｎ：＝データ長［上記データ格納領域［ｉ］の容量
と同一］Ｆａｄ：＝フラグ格納領域［ｉ］の先頭アドレス、一番
最初はｉ＝０である。Ｉｎｔ：＝１［割込を発生させることを示す］Ｄ０：＝２［データのノード間ストライプ数］Ｄ１：＝１［フラグの増分を表す］Ｃｔ０：＝０［一致判定を選択することを表す］Ｃｔ１：＝加算を表すコードＴａｄ：＝転送データ３６の先頭アドレスこれらのパラメタをプロセッサが書き込むことで、メッ
セージ生成回路４１はメッセージ１１を生成し、ネット
ワーク１へ送出する。このとき、メッセージ１１の転送
データフィールドにはＴａｄに格納された先頭アドレ
ス、すなわち転送データ３６がパッキングされる。

【００４５】（データ供給ノードでのフロー制御レジス
タの更新）データを一つデータ消費ノードに転送し終え
ると、データ供給ノードではフロー制御レジスタの更新
を行う。即ち、プロセッサ２４はシステムバス２６を介
してフロー制御レジスタ［Ｒ＃］から１を引く。この結
果が０に場合、データ供給プログラム３１は待機状態に
なる。さらにデータ供給プログラム３１は次にデータを
転送すべき循環バッファ３８のアドレスをデータ用はノ
ード＃０（またはノード＃１）用のデータ格納領域［ｉ
＋１］、フラグアドレスをフラグ領域［ｉ＋１］に更新
する。もしも、これらのアドレスがそれぞれデータ格納
領域［ｍ］、フラグ領域［ｍ］より大きい場合には循環
バッファの先頭アドレスであるデータ格納領域［０］、
フラグ領域［０］に更新する。そして、タイトルで指定
されたデータを全てノード＃２に転送し終えるまで、こ
ららの動作を繰り返す。

【００４６】（データ消費ノードでのデータの受信）次
に上記メッセージを受信したノード＃２の動作について
説明する。

【００４７】ノード２ではネットワーク１から受信した
メッセージ１１を一時的に入力バッファ５１に格納し、
各フィールドの切出しを行う。本メッセージはＣＴＬ
（Ｒ）＝０であることから本メッセージはローカルメモ
リ２３へのデータ転送であると判断する。メッセージ１
１のＤｌｎで示される長さの転送データを、メモリアク
セス回路６０はシステムバス２６を介してＤａｄが示す
循環バッファ３８のデータ格納領域の先頭アドレスへ書
き込む。次にフラグの更新を行うが、これは本実施例で
特徴的な動作である。メモリアクセス回路６０はメッセ
ージ１１のＦａｄで示されるアドレスからフラグ格納領
域［ｉ］の内容を読みだし、フラグレジスタ５８に格納
する。

【００４８】（フラグに該当する領域に対するデータ転
送が始めての場合）この場合、フラグ領域［ｉ］に格納
されたフラグは初期値０である。イベント制御回路５０
０は、ＣＴＬ（Ｒ）が０であることからセレクタ６１で
フラグレジスタ５８を選択し、演算回路５６の一方に入
力する。そして、演算回路５６のもう一方の入力にはＤ
１すなわちここでは１を入力する。イベント制御回路５
００はＣｔ１が加算を表すコードであることから演算回
路５６とセレクタ５７を制御してセレクタ５７の出力に
演算回路５６の二つの入力の加算結果を出力する。ここ
では０＋１＝１である。そして、フラグレジスタ５８に
書き戻す。次に、イベント制御回路５００はＣｔ０＝０
すなわち、一致判定を示すコードであることから、一致
判定回路５３の一方の入力にＤ０、ここでは２を、他方
にはセレクタ６１で選択されている更新済のフラグレジ
スタ５８の内容、ここでは１を、入力する。一致判定回
路５３は２つの入力線が不一致であるため、出力に０を
出す。このため、セレクタ５５で選ばれた出力は０にな
りアンド回路５９の出力は０になる。したがって、プロ
セッサ２４に対して割込を発生しない。すなわち、デー
タが片側しか到着していなければプロセッサ２４に無駄
な割込を発生しない。これにより、データ消費プログラ
ムの実行を阻害しない効果が実現できる。

【００４９】そして、メモリアクセス回路６０はフラグ
レジスタ５８に格納された更新済みのフラグの値１をＦ
ａｄが示すフラグ格納領域［ｉ］へシステムバス２６を
介して書き戻す。

【００５０】（フラグに該当する領域に対するデータ転
送が２つ目の場合）同様にフラグの更新を行うが、今回
はローカルメモリ２３のフラグ格納領域［ｉ］から読み
出されたフラグの値は１である。したがって、演算回路
５６で１を加算されたフラグの値は２になり、この値が
フラグレジスタ５８に格納される。そして、一致判定回
路５３の２つの入力は今回はどちらも２になるため、一
致判定回路５３の出力は１になる。そして、アンド回路
５９の２つの入力はＩｎｔが１であるため、出力に１を
出す。これにより、イベント制御回路５００はプロセッ
サ２４に割込をかけることができ、プロセッサは使用可
能なデータを受信したことを無駄なく知ることができ
る。

【００５１】そして、メモリアクセス回路６０はフラグ
レジスタ５８に格納された更新済みのフラグの値２をＦ
ａｄが示すフラグ格納領域［ｉ］へシステムバス２６を
介して書き戻す。

【００５２】（ノード＃２によるデータの消費）ノード
＃２はイベント制御回路５００から受け取ったデータ受
信完了割込により、データの受信を知らされると次の手
順でデータを消費する。すなわち、循環バッファ３８の
フラグ３７をシステムバス２６を介して読み、フラグ３
７の値が２のエントリを探索する。ここで値が２とはノ
ード＃０、ノード＃１に分割されたデータを正しく受信
できたことを示す。データ消費プログラム３２は正しく
受信できたデータ格納領域からデータを取りだし、表示
装置へ表示するなどの処理を行う。そして、このエント
リに格納されたデータを消費し切ると次の手順で領域の
解放を行う。すなわち、プロセッサ２４はシステムバス
２６を介してローカルメモリ２３に格納された上記エリ
アに対応するフラグ格納領域に０を書き込む。これは該
当するエリアには有効なデータが存在しないこと、すな
わちこの領域が空き領域であることを表す。そして、循
環バッファ３８の空き領域が増えたことをノード＃０お
よびノード＃１に伝えるために次の手順でメッセージを
送信する。

【００５３】（ノード＃２による循環バッファ３８の空
き領域増加の伝達）すなわち、システムバス２６を介し
てプロセッサ２４は送信パラメタ格納レジスタ４２に次
の値を設定し、メッセージをノード＃０、ノード＃１に
送信する。

【００５４】Ｎａｄ：＝ノード＃０またはノード＃１の識別子ＣＴＬ（Ｒ）：＝１［フロー制御レジスタ群宛のメッセ
ージであることを示す］ＣＴＬ（Ｒ＃）：＝宛先のフロー制御レジスタ識別子Ｄａｄ：＝０［このメッセージでは参照されない］Ｄｌｎ：＝０［このメッセージでは参照されない］Ｆａｄ：＝０［このメッセージでは参照されない］Ｉｎｔ：＝０［このメッセージでは参照されない］Ｄ０：＝０［このメッセージでは参照されない］Ｄ１：＝１［循環バッファ３８の空き容量の増分］Ｃｔ０：＝０［このメッセージでは参照されない］Ｃｔ１：＝加算を表すコードＴａｄ：＝０［このメッセージでは参照されない］このように送信パラメタを設定することにより、メッセ
ージ生成回路４１はメッセージ１１を生成し、ネットワ
ーク１へ送出する。そして、送信状態レジスタＳＴ４３
に送信完了を表すコードを書き込む。

【００５５】ネットワーク１はメッセージ１１のＮａｄ
が示すノード、ここではノード＃０またはノード＃１へ
メッセージを配送する。

【００５６】次に上記メッセージを受信したノード＃０
およびノード＃１の動作について説明する。

【００５７】ノード２ではネットワーク１から受信した
メッセージ１１を一時的に入力バッファ５１に格納し、
各フィールドの切出しを行う。本メッセージはＣＴＬ
（Ｒ）＝１であることから本メッセージはフロー制御レ
ジスタに対する更新要求であると判断する。また、Ｃｔ
１が「加算」であることから、イベント制御回路５００
は演算回路５６とセレクタ５７、６１を制御してＤ１に
格納された値１をフロー制御レジスタ［Ｒ＃］に格納さ
れた値に加算した結果をセレクタ５７の出力に出す。そ
して、この出力結果をフロー制御レジスタ［Ｒ＃」に書
き戻す。また、このときＩｎｔは０であることから、ア
ンド回路５９の出力は０であり、プロセッサ２４に対し
てイベント制御回路５００は割込を発生しない。

【００５８】これにより、フロー制御レジスタに格納さ
れた循環バッファ５８の空き容量は１つ増えたことにな
る。

【００５９】（読み出しの終了）タイトルで指定された
データを全て読み終えたデータ供給プログラム３１は次
にデータの読み出しリクエストが来るまで待機する。

【００６０】他方、データ消費プログラムは最後のデー
タを消費すると、次の手順にしたがって、データ供給ノ
ードのフロー制御レジスタの値を初期値０に戻す。すな
わち、システムバス２６を介してプロセッサ２４は送信
パラメタ格納レジスタ４２に次の値を設定し、メッセー
ジをノード＃０、ノード＃１に送信する。

【００６１】Ｎａｄ：＝ノード＃０またはノード＃１の識別子ＣＴＬ（Ｒ）：＝１［フロー制御レジスタ群宛のメッセ
ージであることを示す］ＣＴＬ（Ｒ＃）：＝宛先のフロー制御レジスタ識別子Ｄａｄ：＝０［このメッセージでは参照されない］Ｄｌｎ：＝０［このメッセージでは参照されない］Ｆａｄ：＝０［このメッセージでは参照されない］Ｉｎｔ：＝０［このメッセージでは参照されない］Ｄ０：＝０［このメッセージでは参照されない］Ｄ１：＝０［初期値］Ｃｔ０：＝０［このメッセージでは参照されない］Ｃｔ１：＝値設定を表すコードＴａｄ：＝０［このメッセージでは参照されない］このように送信パラメタを設定することにより、メッセ
ージ生成回路４１はメッセージ１１を生成し、ネットワ
ーク１へ送出する。そして、送信状態レジスタＳＴ４３
に送信完了を表すコードを書き込む。

【００６２】ネットワーク１はメッセージ１１のＮａｄ
が示すノード、ここではノード＃０またはノード＃１へ
メッセージを配送する。

【００６３】次に上記メッセージを受信したノード＃０
およびノード＃１の動作について説明する。

【００６４】ノード２ではネットワーク１から受信した
メッセージ１１を一時的に入力バッファ５１に格納し、
各フィールドの切出しを行う。本メッセージはＣＴＬ
（Ｒ）＝１であることから本メッセージはフロー制御レ
ジスタに対する更新要求であると判断する。また、Ｃｔ
１が「値設定」であることから、イベント制御回路５０
０はセレクタ５７にＤ１を選択するように制御し、フロ
ー制御レジスタ群５２からＣＴＬ（Ｒ＃）で示されるレ
ジスタに対し、Ｄ１に格納された０を書き込む。

【００６５】これによりフロー制御レジスタ［Ｒ＃］に
は循環バッファ５８の空き容量として０が設定された。
これにより、再びこのフロー制御レジスタを利用してフ
ロー制御を行う場合に、読み出し開始要求が来るまでデ
ータ供給プログラムが待機することを保証する。

【００６６】以上の動作を行うことにより、データ消費
ノード（ノード＃２）では分割されたデータが全て整っ
たときにのみ本来の処理であるデータ消費プログラム３
２に割込がかかり、メッセージの受信処理を行えば良
い。これにより、データ消費プログラムが邪魔されて、
たとえば表示装置への表示処理が途切れて、画像が乱れ
ることを防止できる。

【００６７】また、循環バッファの空き容量の管理に関
しては、メッセージが到着するごとにデータ消費プログ
ラムが邪魔されることがなく、実際にバッファを解放し
たときにのみ空き容量をデータ供給プログラム３１へ伝
達すればよい。本実施例の説明では循環バッファの１つ
のエントリを消費した場合について述べたが、データ消
費プログラム３２の構造上の理由により、複数エントリ
を一括して消費しても構わない。この場合、データ消費
ノードからデータ供給ノードに伝えられる循環バッファ
３８の空き容量の増分は１より大きくなる。

【００６８】そして、データ供給ノードではデータ供給
プログラム３１はローカルに配置されたフロー制御レジ
スタの値を調べることにより、送信先の循環バッファ３
８の空き容量を知ることができる。

【００６９】このようにそれぞれのプログラムがローカ
ルな情報に基づいて動作をできるため、並行処理を行う
ことができ、並列計算機の性能を向上させることができ
る。

【００７０】（２）変形例次に、上記で示した実施例１の変形例を示す。上記実施
例１では分割されたデータの到着確認にデータ分割数を
利用した。また上記実施例１では２分割であったため２
であった。変形例では到着しているデータと到着してい
ないデータを判別できるように上記実施例を変形して実
現する。

【００７１】変形例ではフラグ３７に格納される値の各
ビットに対してデータ供給ノードからデータ到着済とい
う意味を与える。

【００７２】例えば、ノード＃０にはフラグのビット０
を割り当て、ノード＃１にはビット１を割り当てる。

【００７３】以下、このビット割り当てに基づき実施例
１との相違点のみを説明する。

【００７４】（ノード＃２による読みだしリクエスト）
実施例１では分割数２を知らせた代わりに変形例１では
２＾０＋２＾１＝３、すなわちノード＃０とノード＃１
の両方からデータが正しく到着したときのフラグの期待
値を知らせる。ここで「＾」はべき乗を表す。さらに、
ノード＃０に対しては、データを書き込むときに２＾０
＝１をフラグに加算するように伝え、ノード＃１には２
＾１＝２を加算するように伝える。

【００７５】（データ供給ノードからのデータ転送）デ
ータ供給ノードではデータをノード＃２に転送するとき
に送信パラメタ格納レジスタの値を実施例１とは異なり
以下のように設定する。

【００７６】Ｎａｄ：＝ノード＃２の識別子ＣＴＬ（Ｒ）：＝０［フロー制御レジスタ宛ではなく、
メモリ宛であることを示す］Ｄａｄ：＝ノード＃０（またはノード＃１）用データ格
納領域［ｉ］の先頭アドレス一番最初はｉ＝０である。

【００７７】Ｄｌｎ：＝データ長［上記データ格納領域
［ｉ］の容量と同一］Ｆａｄ：＝フラグ格納領域［ｉ］の先頭アドレス一番最初はｉ＝０である。

【００７８】Ｉｎｔ：＝１［割込を発生させることを示す］Ｄ０：＝３［両方のデータ到着した時のフラグの期待値
＝２＾０＋２＾１］Ｄ１：＝２＾０＝１（ノード＃０の場合）または２＾１
＝２（ノード＃１の場合）［フラグの増分を表す］Ｃｔ０：＝０［一致判定を選択することを表す］Ｃｔ１：＝加算を表すコードＴａｄ：＝転送データ３６の先頭アドレス（フラグに該当する領域に対するデータ転送が始めての
場合）この場合、フラグ領域［ｉ］に格納されたフラグ
は初期値０である。イベント制御回路５００は、ＣＴＬ
（Ｒ）が０であることからセレクタ６１でフラグレジス
タ５８を選択し、演算回路５６の一方に入力する。そし
て、演算回路５６のもう一方の入力にはＤ１すなわちこ
こでは１または２を入力する。イベント制御回路５００
はＣｔ１が加算を表すコードであることから演算回路５
６とセレクタ５７を制御してセレクタ５７の出力に演算
回路５６の二つの入力の加算結果を出力する。ここでは
１または２である。そして、フラグレジスタ５８に書き
戻す。次に、イベント制御回路５００はＣｔ０＝０すな
わち、一致判定をしめすコードであることから、一致判
定回路５３の一方の入力にＤ０、ここでは３を他方には
セレクタ６１で選択されている更新済のフラグレジスタ
５８の内容、ここでは１または２を入力する。一致判定
回路５３は２つの入力線が不一致であるため、出力に０
を出す。このため、セレクタ５５で選ばれた出力は０に
なりアンド回路５９の出力は０になる。したがって、プ
ロセッサ２４に対して割込を発生しない。すなわち、デ
ータが片側しか到着していなければプロセッサ２４に無
駄な割込を発生しない。これにより、データ消費プログ
ラムの実行を阻害しない効果が得られる。

【００７９】そして、メモリアクセス回路６０はフラグ
レジスタ５８に格納された更新済みのフラグの値１また
は２をＦａｄが示すフラグ格納領域［ｉ］へシステムバ
ス２６を介して書き戻す。

【００８０】これによりデータ消費プログラム３２はフ
ラグ格納領域［ｉ］を読み出すことにより、この値が０
であればどちらも受信していないことを判別できる。そ
して、１であればノード＃０からだけデータを受信した
ことを判別できる。そして、２であればノード＃１から
だけデータを受信したことを判別できる。３であれば、
両方を受信していることを判別できる。

【００８１】（フラグに該当する領域に対するデータ転
送が２つ目の場合）同様にフラグの更新を行うが、今回
はローカルメモリ２３のフラグ格納領域［ｉ］から読み
出されたフラグの値は１または２である。したがって、
もう一方のデータを受信すると演算回路５６で２または
１を加算されるため、フラグの値はどちらの場合も３に
なり、この値がフラグレジスタ５８に格納される。そし
て、一致判定回路５３の２つの入力は今回はどちらも３
になるため、一致判定回路５３の出力は１になる。そし
て、アンド回路５９の２つの入力はＩｎｔが１であるた
め、出力に１を出す。これにより、イベント制御回路５
００はプロセッサ２４に割込をかけることができ、プロ
セッサは使用可能なデータを受信したことを無駄なく知
ることができる。

【００８２】

【発明の効果】ノードは、一連のデータを分散されたノ
ードへアクセスした際、分散されたノードから一連のデ
ータの全体を受信したときに割り込みを発生するので、
一連のデータの個々のデータを受信した時と比べ、割り
込み回数を減らすことができ、当該ノードでの本来の処
理を中断する回数が縁、ノードの処理効率を高めること
ができる。

【００８３】また、ノードアクセス時にノードにあるア
クセス結果を格納する空き数に応じてアクセス結果の応
答を遅延させる手段を有するので、フロー制御信号をノ
ード間で送受信する場合と比べ、フロー制御信号を送受
信する必要が無く、ノード間の信号送受信に新たな負荷
をかけることなく、高速なフロー制御を行うことができ
る。

【図面の簡単な説明】

【図１】本発明による並列計算機の構成図である。

【図２】図１の循環バッファ３８の詳細構成図である。

【符号の説明】

１ネットワーク２ノード２１送信制御回路、２２受信制御回路、２３ローカルメモリ、２４プロセッサ、２５ディスク装置、３８循環バッファ、４２送信パラメタ格納レジスタ、５００イベント制御回路。

───────────────────────────────────────────────────── フロントページの続き (72)発明者村橋英樹東京都国分寺市東恋ケ窪一丁目280番地株式会社日立製作所中央研究所内 (72)発明者武内茂雄東京都小平市上水本町５丁目20番１号日立超エル・エス・アイ・エンジニアリング株式会社内 (72)発明者鳥羽達東京都小平市上水本町５丁目20番１号日立超エル・エス・アイ・エンジニアリング株式会社内 (72)発明者垂井俊明東京都国分寺市東恋ケ窪一丁目280番地株式会社日立製作所中央研究所内 (72)発明者北井克佳東京都国分寺市東恋ケ窪一丁目280番地株式会社日立製作所中央研究所内

Claims

【特許請求の範囲】

【請求項１】少なくとも１つ以上のプロセッサをそれぞ
れ有する複数のノードと、上記複数のノードの間でメッ
セージを交換するための上記ノードを相互に接続するネ
ットワークとからなる並列計算機において、該複数のノードにより利用可能な少なくとも１つの資源
と、その資源を複数のノードに分割して格納する手段を
有し、その資源に対してアクセス要求を行うノードは、その資
源を分割格納している複数のノードに対して一連のアク
セス要求を行うときに、該一連のアクセス要求に対して
アクセス結果が返答されたか否かを格納する手段（フラ
グと呼ぶ）を有し、該アクセス要求を受け付けたノードは、該アクセス要求
に対してアクセス結果を返答するときに、アクセス結果
とともに該フラグに対して自ノードがアクセス結果を返
したことを記録するために、該フラグを指定する手段
と、該フラグに対する記録方法を指定する手段とを有
し、アクセス要求を行ったノードは、該アクセス結果を受け
取ったときに、付帯する該フラグを指定する手段で示さ
れるフラグに対して、該フラグに対する記録方法で指定
された手段で記録を行い、そのフラグが全てのノードか
ら返答があったことを示すか否かを判定する手段と、全
てのノードから返答があったと判定された場合に該プロ
セッサに割込を発生する回路を有することを特徴とする
並列計算機。
【請求項２】少なくとも１つ以上のプロセッサをそれぞ
れ有する複数のノードと、上記複数のノードの間でメッ
セージを交換するための上記ノードを相互に接続するネ
ットワークとからなる並列計算機において、該並列計算機は該複数のノードにより利用可能な少なく
とも一つの資源を有し、該ノードには、その資源を直接アクセスする手段を有す
る第１のノードと、直接アクセスできない第２のノード
があり、該第２のノードは、該資源をアクセスする場合に、複数
のアクセス結果を格納する手段を有し、該第１のノードは、該アクセス結果格納手段の空き数を
格納する手段と、該アクセスに対する結果を該第２のノ
ードに返答するときに、上記格納手段に格納された該空
き数を減少させる回路を有し、該第２のノードは、該アクセス結果を利用することによ
り、該アクセス結果格納手段を解放した場合に、該第１
のノードにある該空き数を格納する手段に納められた空
き数を増加させる回路を有し、該第１のノードは、該第２のノードの該アクセス結果格
納手段に空きがあるか否かを判定する回路と、該空きの
判定の結果が空きがない場合にアクセス結果の返答を遅
延させる手段を有することを特徴とする並列計算機。