JPH01154275A - 並列計算機間通信制御方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 並列計算機システムにおける計算機関通信の制御に関し
、 通信幅較状態の回避を目的とし、 各プロセッサは、隣接プロセッサへのメツセージを出力
処理する出力処理部に、送信方向ごとに送信メソセージ
をキューイングするメツセージキューを備えると共に、
自プロセッサから送信するメツセージおよび他プロセッ
サから受信し自プロセッサ宛でないメツセージを送信す
る方向を決定する送信方向決定部が、送信先プロセッサ
の位置方向と出力処理部のメツセージキューにキューイ
ングされているメツセージの数から送信方向を決定する
よう構成する。

〔産業上の利用分野〕

本発明は並列計算機システムに係わり、特に並列計算機
間の通信の制御に関する。

複数台のプロセッサが互いにデータ通信を行いながら並
列に処理を進める並列計算機システムが開発され実用さ
れている。このようなシステムでは、全体の通信量が増
大すると通信の輻較状態が発生する可能性があり、通信
のΦｔｕｆｆ状態が発生しにくい通信方式が望まれる。

〔従来の技術〕

並列計算機のプロセッサ間通信において、直接、通信路
で繋がっていないプロセッサ間の通信を行うためには、
あるプロセッサがメツセージを中継する必要がある。

そのとき、複数の通信路を選択できるものとすると、従
来の方式では、あるプロセッサがメツセージを出力する
方向を、 ■全くランダムに方向を選択する。

■予め定めた方向の順序により　（例えば、最初Ｘ方向
に進み、後Ｙ方向に進む）方向を選択する。

等の方法が用いられており、通信の混雑度を条件に経路
を選択する方法はなかった。

例えば、第７図に示す二次元メツシュ状に接続された並
列計算機システムにおいて、ＩＤ＝１のプロセッサから
ＩＤ＝４のプロセッサへ通信する場合、ＩＤ＝１のプロ
セッサは、ＴＤ＝２のプロセッサ、若しくはＩＤ＝３の
プロセッサのどちらかにデータを送信することができ、
その選択の方法として、全くランダムに選択するか、若
しくは最初はＸ方向に進むと決めてＩＤ＝２への通信路
を選択していた。

〔発明が解決しようとする問題点〕

従来の通信路選択の方法では、通信の混雑状態に関係な
く経路を選択していたので、通信の混雑している方向を
選択してしまい、通信の輻較状態が発生しやすいという
問題点があった。　本発明は、このような従来の問題点
を解消し、通信の輻較状態が発生しにくい並列計算機関
通信制御方式を提供しようとするものである。

〔問題点を解決するための手段〕

第１図は、本発明の並列計算機関通信制御方式の原理ブ
ロック図を示す。

図において、ｌは並列計算機システムを構成する一つの
プロセッサである。

１１は出力処理部であり、隣接プロセッサへのメツセー
ジを出力処理する。出力処理部には、送信方向ごとに送
信メツセージをキューイングするメツセージキュー１１
１を備える。

１２は送信方向決定部であり、メツセージを送信する方
向を決定する。

１３はメツセージ送信要求部であり、メソセージを他の
プロセッサに送信することを要求する。

１４は入力処理部であり、隣接プロセッサからのメツセ
ージを受信処理する。

１５は送信先判定部であり、受信したメツセージが自プ
ロセッサ宛であるかどうか判定する。

１６はメツセージ処理部であり、自プロセッサ宛のメツ
セージに関する処理を実行する。

〔作　用〕

各プロセッサ１は、隣接プロセッサへメソセージを送信
処理する出力処理部１１に送信方向ごとにメツセージキ
ュー１１１を備えており、どの方向にメソセージを送信
するかを決定する送信方向決定部１２がある。

自プロセッサから送信要求がある時は、メツセージ送信
要求部１３が送信方向決定部１２を起動する。

送信方向決定部１２は、送信先プロセッサの位置に近づ
く方向のメツセージキュー１１１のメツセージ数を数え
、メツセージ数の最も少ない方向を送（１１？方向と決
定し、出力処理部１１へ送信メツセージを渡す。

出力処理部１１は、メツセージキュー１１１にキューイ
ングされているメツセージを順次隣接プロセッサに送信
する処理を行う。

即ち、出力処理部１１は隣接プロセッサの入力処理部１
４を起動して通信を行い、終了した時送信したメツセー
ジをメツセージキュー１１１から開放する。

入力処理部１４は、通信が終了すると、送信先判定部１
５を起動する。送信先判定部１５は、受信メソセージが
自プロセッサ宛であるか否かを判定し、自プロセッサ宛
でない場合には送信方向決定部１２を起動して送信先プ
ロセッサまたは中継プロセッサにメ、ソセージを転送す
る処理に移行する。中継のメソセージも、送信方向決定
部１２の処理により送信方向を決定され、出力処理部１
１にキューイングされる。自プロセッサ宛である場合に
は、メツセージ処理部１６にメツセージを渡し、メツセ
ージ処理部１６において処理される。

以上のように、出力処理部１１のメツセージキュー１１
１にキューイングされているメソセージの数をその方向
の通信の混雑度と考え、送信方向を決定する条件とする
ことにより、通信の混雑度が均一化され、通信の輻較状
態が発生しにくいことになる。

〔実施例〕

以下第２図〜第６図に示す実施例により、本発明をさら
に具体的に説明する。

第２図は、方式の位置実施例の構成を示す図である。

図において、第１図と同一の符号は同一の対象物を示す
。

各プロセッサ１はマルチタスク環境で動作する。

メツセージを隣接プロセッサに出力する出力タスク１１
は、通信路ごとに備えられ、それぞれ送信処理を行う送
信処理部１１２とメソセージキュー１１１を持っている
。出力タスク１１には、そのほかに、各通信路共通のメ
ッセージ数テーブル１１３を備えている。

隣接プロセッサからのメツセージを受信処理する入力タ
スク１４は、受信処理部１４１および受信メンセージバ
ッファ１４２を備えている。

第３図は、本発明の一実施例のシステム構成を示す。

図（ａ）はシステム構成を示し、図（ｂ）はシステムの
中の一つのプロセッサを示す。図において、３０はプロ
セッサ間通信路を示す。二次元メツシュ状に接続された
並列計算機システムであり、各プロセッサはそれぞれＮ
０ＲＴＨ，ＥＡＳＴ、ＷＥＳＴ。

５ＯＵＴＨの４つの通信路を持っている。従って、各プ
ロセッサの出力タスクは４つ備えられている。

第４図は、本発明の一実施例における送信方向決定部の
処理を示すフローチャートであり、第５図は本実施例に
おける出力タスクのメッセージ数テーブルを示す図であ
る。

第４図のフローチャートのステップに従って、送信方向
決定部の動作を説明する。

■メツセージ送信要求タスク１３、或いは送信先判定部
１５から渡されたメソセージの宛先を読み取り、宛先プ
ロセッサに近づく複数の方向を求める。例えば、第３図
ＩＤ＝１のプロセッサからＴＤ＝７のプロセッサへ送信
する場合、可能な送信方向は、ＥＡＳＴと５ＯＵＴＨに
なる。

■第５図に示したメッセージ数テーブルから、■で求め
た方向のメツセージキューにキューイングされているメ
ツセージの数Ｍ（方向）を求め、その中で最も少ない数
を持つ方向を選択する。

例えば、前記例の場合、ＥＡＳＴとＳ　ＯＵ　Ｔ　Ｈの
出力タスクのメツセージキューにキューイングされてい
るメツセージの数Ｍ　（ＥＡＳＴ）とＭ　（ＳＯＵＴＨ
）を読み取る。Ｍ　（ＥＡＳＴ）　＞　Ｍ　（ＳＯＩＪ
Ｔ）Ｉ）であれば５ＯＵＴＨを、Ｍ　（ＥＭＳＴ）　＜
　Ｍ　（Ｓ、０ＵＴＨ）であればＥＡＳＴを選択する。

Ｍ　（ＥＡＳＴ）　＝　Ｍ　（ＳＯＵＴｌｌ）であれば
どちらを選択してもよい。

■選択された方向の出力タスクのメツセージキューにメ
ツセージをキューイングする。

第６図は、本発明の一実施例における出力タスクの処理
を示すフローチャートである。

以下、フローチャートのステップに従ってその動作を説
明する。

■メツセージキューにメツセージがあるかを調べる。メ
ツセージが無ければステップ＠へ進み、有ればステップ
０へ進む。

＠メツセージを待ち、ステップ■へ戻る。

■隣接プロセッサの入力タスクを起動する。

■隣接プロセッサと通信を行い、メ・７セージの送信を
行う。

■メツセージの送信を終了すれば、そのメツセージをメ
ツセージキューから開放し、ステップ■へ戻る。

各通信路のメツセージキュー１１１は、送信方向決定部
１２からメツセージを渡された時、各通信路共通のメッ
セージ数テーブルの自通信路のメツセージ数を＋１し、
送信処理部１１２がメツセージを開放した時−１する。

〔発明の効果〕

以上説明のように本発明によれば、有るプロセッサから
あるプロセッサへのメツセージ通信において、経路選択
の方法として、出力タスクのメツセージキューにキュー
イングされているメツセージの数を条件とすることによ
り、通信の混雑している通信方向を避けることができ、
また通信の混雑を均一化し、通信の輻較条件が発生しに
く（することができ、処理効率の向上に寄与する効果は
大である。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、 第２図は本発明の一実施例の構成を示す図、第３図は本
発明の一実施例のシステム構成を示す図、 第４図は送信方向決定部の処理を示すフローチャート、 第５図は出力タスクのメッセージ数テーブルを示す図、 第６図は出力タスクの処理を示すフローチャート、 第７図はプロセッサ間通信経路を説明する図である。 図面において、 ｌはプロセッサ、 １１は出力処理部（出力タスク）、 １１１はメンセージキュー、　　１１２は送信処理部、
１１３はメッセージ数テーブル、 １２は送信方向決定部、 １３はメツセージ送信要求部（メツセージ送信要求タス
ク）、 １４は入力処理部（入力タスク）、 １４１は受信処理部、 １４２は受信メツセージバッファ、 １５は送信先判定部、 １６はメツセージ処理部（メツセージ処理タスク）、３
冴は通信路、 をそれぞれ示す。 本発明の原理プロ７り図 ＠１図 送信方向決定部の処理を示すフローチャート第　　４　
　図 出力タスクのメソセージ数テーブルを示す図書　　５　
　図 出力タスクの処理を示すフローチャート第　　６　　図

Claims (1)

1. 【特許請求の範囲】 相互に通信路をもって接続された複数のプロセッサ（１
   ）から構成された並列計算機システムにおいて、 各プロセッサ（１）は、 隣接プロセッサへのメッセージを出力処理する出力処理
   部（１１）に、 送信方向ごとに送信メッセージをキューイングするメッ
   セージキュー（１１１）を備えると共に、自プロセッサ
   から送信するメッセージおよび他プロセッサから受信し
   自プロセッサ宛でないメッセージを送信する方向を決定
   する送信方向決定部（１２）が、 送信先プロセッサの位置方向と出力処理部（１１）のメ
   ッセージキュー（１１１）にキューイングされているメ
   ッセージの数から送信方向を決定するよう構成したこと
   を特徴とする並列計算機間通信制御方式。