JPH0624361B2 - データ伝送方式 - Google Patents
データ伝送方式Info
- Publication number
- JPH0624361B2 JPH0624361B2 JP63030881A JP3088188A JPH0624361B2 JP H0624361 B2 JPH0624361 B2 JP H0624361B2 JP 63030881 A JP63030881 A JP 63030881A JP 3088188 A JP3088188 A JP 3088188A JP H0624361 B2 JPH0624361 B2 JP H0624361B2
- Authority
- JP
- Japan
- Prior art keywords
- node
- data
- priority
- transmission
- nodes
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Description
【発明の詳細な説明】 (産業上の利用分野) 本発明は、ハイパーキューブ状に結合されたノード間に
おけるデータ伝送方式に関するものである。
おけるデータ伝送方式に関するものである。
(従来の技術) 複数のノードをハイパーキューブ状に結合し、ノード間
でデータ転送(伝送)を行い並列処理を実行するシステ
ムとしては、例えば、ジョンP.ヘイズ(John P.Haye
s)他「ハイパーキューブ スーパコンピュータのアー
キテクチャ(ARCHITECTURE OF A HYPERCUBE SUPERCOMPUT
ER)」1986 IEEEやJ.C.ピータソン(J.C.Peterson)
他「マークIII ハイパーキューブ−アンサンブル コ
ンカレント コンピュータ(THE MARK III HYPERCUBE-EN
SEMBLE CONCURRENT COMPUTER)」1985IEEE等に記載
されているシステムを始め、数多く開発されている。第
2図にハイパーキューブ結合の例を示す。同図におい
て、黒丸印はノードを示す。このようなハイパーキュー
ブはN(=2n,nは正の整数)個のノードからなり、
各ノードは主として、処理を実行するプロセッサと各ノ
ード間でデータ伝送を行うデータ通信部とから成る。各
ノードにはn本の転送路がある。ノードaのアドレスは
2進数(anan−1……a2a1)で表わされる。ノ
ードAは、nan−1……a2a1)、(an
n−1……a2a1)、……、(anan−1……2
a1)、(anan−1……a2 1)をアドレスとす
るノードと結合している。すなわち、アドレスaのノー
ドAはそれとハミング距離が1だけ異なるノードに直接
結合している。
でデータ転送(伝送)を行い並列処理を実行するシステ
ムとしては、例えば、ジョンP.ヘイズ(John P.Haye
s)他「ハイパーキューブ スーパコンピュータのアー
キテクチャ(ARCHITECTURE OF A HYPERCUBE SUPERCOMPUT
ER)」1986 IEEEやJ.C.ピータソン(J.C.Peterson)
他「マークIII ハイパーキューブ−アンサンブル コ
ンカレント コンピュータ(THE MARK III HYPERCUBE-EN
SEMBLE CONCURRENT COMPUTER)」1985IEEE等に記載
されているシステムを始め、数多く開発されている。第
2図にハイパーキューブ結合の例を示す。同図におい
て、黒丸印はノードを示す。このようなハイパーキュー
ブはN(=2n,nは正の整数)個のノードからなり、
各ノードは主として、処理を実行するプロセッサと各ノ
ード間でデータ伝送を行うデータ通信部とから成る。各
ノードにはn本の転送路がある。ノードaのアドレスは
2進数(anan−1……a2a1)で表わされる。ノ
ードAは、nan−1……a2a1)、(an
n−1……a2a1)、……、(anan−1……2
a1)、(anan−1……a2 1)をアドレスとす
るノードと結合している。すなわち、アドレスaのノー
ドAはそれとハミング距離が1だけ異なるノードに直接
結合している。
以上のように構成されたシステムにおける従来のデータ
伝送方式の処理手順について説明する。例えば、ノード
A(an……a1)からノードB(bn……b1)への
データ転送は次のように行われる。最下位ビットから調
べて、最初にaibi=1となるノード(an……b
ibi−1……b1)にデータを送る。(an……ai
……ai)と(an……bibi−1……b1)はiビ
ット目のみ異なっている2進数であるので、直接つなが
っている隣接ノードとなっている。最上位ビットまでこ
の過程を繰り返すと、ノードAとノードBの通信ができ
る。
伝送方式の処理手順について説明する。例えば、ノード
A(an……a1)からノードB(bn……b1)への
データ転送は次のように行われる。最下位ビットから調
べて、最初にaibi=1となるノード(an……b
ibi−1……b1)にデータを送る。(an……ai
……ai)と(an……bibi−1……b1)はiビ
ット目のみ異なっている2進数であるので、直接つなが
っている隣接ノードとなっている。最上位ビットまでこ
の過程を繰り返すと、ノードAとノードBの通信ができ
る。
このように、任意の2つのノード間でデータ伝送を行う
場合、ノード数が多くなるほど、経由する転送路の平均
数は増加する。
場合、ノード数が多くなるほど、経由する転送路の平均
数は増加する。
ノードのデータ通信部においては、伝送制御を簡単にす
るために、半二重通信で行うことが考えられている。す
なわち、データの伝送を送信と受信に分け、同時に実行
しない方式である。この場合、データの伝送は以下に示
す手順に従って実行される。まず、送信ノードは送信要
求を隣接するノード(受信ノード)に送信する。該送信
要求を受信したノードは受信できる状態ならば、受信可
(ACK)を、また受信できない状態ならば受信不可
(NAK)を返送する。送信ノードは受信ノードからA
CKを受信することにより、データの送信を開始する。
また受信ノードは、ACKを返送した後、データ受信状
態にはいる。
るために、半二重通信で行うことが考えられている。す
なわち、データの伝送を送信と受信に分け、同時に実行
しない方式である。この場合、データの伝送は以下に示
す手順に従って実行される。まず、送信ノードは送信要
求を隣接するノード(受信ノード)に送信する。該送信
要求を受信したノードは受信できる状態ならば、受信可
(ACK)を、また受信できない状態ならば受信不可
(NAK)を返送する。送信ノードは受信ノードからA
CKを受信することにより、データの送信を開始する。
また受信ノードは、ACKを返送した後、データ受信状
態にはいる。
また、各ノードにおいて、データ送信とデータ受信を同
時に行おうとする場合には、送信を受信よりも優先する
送信優先、あるいはこの逆の受信優先により行う。
時に行おうとする場合には、送信を受信よりも優先する
送信優先、あるいはこの逆の受信優先により行う。
(発明が解決しようとする問題点) しかしながら、上記データ伝送方式では、送信優先とす
る場合を考えると、ノードAがノードBへデータ伝送す
ることと、ノードBがノードAにデータ伝送しようとす
ることが同時に起きた場合、ノードAもノードBを互い
にデータを送信しようとするが、どちらもデータ受信さ
れないので、デッドロックとなる。また逆に、受信優先
の場合も、両方のノードが受信状態になり、デッドロッ
クとなる。このように、従来の送信優先、受信優先のデ
ータ伝送方式はデッドロックを起こすという問題点があ
った。本発明は以上述べた問題点を解決し、デッドロッ
クを防止するデータ伝送方式を提供することを目的とす
る。
る場合を考えると、ノードAがノードBへデータ伝送す
ることと、ノードBがノードAにデータ伝送しようとす
ることが同時に起きた場合、ノードAもノードBを互い
にデータを送信しようとするが、どちらもデータ受信さ
れないので、デッドロックとなる。また逆に、受信優先
の場合も、両方のノードが受信状態になり、デッドロッ
クとなる。このように、従来の送信優先、受信優先のデ
ータ伝送方式はデッドロックを起こすという問題点があ
った。本発明は以上述べた問題点を解決し、デッドロッ
クを防止するデータ伝送方式を提供することを目的とす
る。
(問題点を解決するための手段) 本発明は前記問題点を解決するために、隣接するノード
がそれぞれハミング距離が1だけ異なるように2進数の
アドレスを付与されたハイパーキューブ状に結合されノ
ード間で、パケットを単位としてデータ伝送を行うデー
タ伝送方式において、隣接するノード間で互いにパケッ
トを送信しようとする際に、各送信ノードは自ノードの
アドレスと隣接する送信先のノードのアドレスを比較
し、相異なるビット位置の値が1か0かにより、パケッ
ト送信の優先順位を決定するものである。
がそれぞれハミング距離が1だけ異なるように2進数の
アドレスを付与されたハイパーキューブ状に結合されノ
ード間で、パケットを単位としてデータ伝送を行うデー
タ伝送方式において、隣接するノード間で互いにパケッ
トを送信しようとする際に、各送信ノードは自ノードの
アドレスと隣接する送信先のノードのアドレスを比較
し、相異なるビット位置の値が1か0かにより、パケッ
ト送信の優先順位を決定するものである。
(作用) 本発明は次のように作用する。隣接するノード間で互い
にパケットを送信しようとする際に、各ノードは、自ノ
ードのアドレスと隣接する送信先のノードのアドレスを
比較し、相異なるビット位置の値が1か0かにより、パ
ケット送信の優先順位を決定する。優先順位の高い方の
送信ノードは送信不可(NAK)パケットを相手側ノード
に送信することにより、パケットを送信することができ
る。この後、優先順位の低い方のノードの送信を行う。
従って、デッドロックを防止することが可能となる。
にパケットを送信しようとする際に、各ノードは、自ノ
ードのアドレスと隣接する送信先のノードのアドレスを
比較し、相異なるビット位置の値が1か0かにより、パ
ケット送信の優先順位を決定する。優先順位の高い方の
送信ノードは送信不可(NAK)パケットを相手側ノード
に送信することにより、パケットを送信することができ
る。この後、優先順位の低い方のノードの送信を行う。
従って、デッドロックを防止することが可能となる。
(実施例) 第1図は本発明の一実施例を示すシステム構成図であっ
て、説明を簡単にするため、ハイパーキューブ結合され
た複数のノードのうち、隣接するノードA,Bの構成の
みを示すものである。ノードA1aは通信路(転送路)
2を介してノードB1bに接続される。各ノードは同一
の内部構成を持ち、CPU3、送信データ用のバッファ
(OB)4、受信データ用のバッファ(IB)5、中継
データ用のバッファ(TB)6,7、ネットワーク制御
部(CNT)8、ポート(PORT)9から構成され
る。CPU3はノード全体を制御するプロセッサであ
る。OB4はCPU1で作成したデータを他ノードに送
信するためのバッファ、IB5は他ノードから自ノード
へ送信されてきたデータを受信するためのバッファ、T
B6,7は中継データを一時蓄積するためのバッファで
ある。CNT8は、データを送受信するための制御とル
ーティング処理を実行するネットワーク制御部である。
PORT9はデータの送受信を行うためのものであり、
他ノードと通信路によって接続される。
て、説明を簡単にするため、ハイパーキューブ結合され
た複数のノードのうち、隣接するノードA,Bの構成の
みを示すものである。ノードA1aは通信路(転送路)
2を介してノードB1bに接続される。各ノードは同一
の内部構成を持ち、CPU3、送信データ用のバッファ
(OB)4、受信データ用のバッファ(IB)5、中継
データ用のバッファ(TB)6,7、ネットワーク制御
部(CNT)8、ポート(PORT)9から構成され
る。CPU3はノード全体を制御するプロセッサであ
る。OB4はCPU1で作成したデータを他ノードに送
信するためのバッファ、IB5は他ノードから自ノード
へ送信されてきたデータを受信するためのバッファ、T
B6,7は中継データを一時蓄積するためのバッファで
ある。CNT8は、データを送受信するための制御とル
ーティング処理を実行するネットワーク制御部である。
PORT9はデータの送受信を行うためのものであり、
他ノードと通信路によって接続される。
ここで、ノードA1aの構成要素の参照符号には添字
a、同様にノードB1bのものには添字bを付与する。
a、同様にノードB1bのものには添字bを付与する。
データの送受信は、パケットを単位として行う。各ノー
ドのアドレスは2進数で表わしたとき、i番目のビット
のみが異なる。即ち、ノードA1aのアドレスを(an
……ai+1aiai−1……a1)、ノードB1bの
アドレスを(bn……bi+1bibi−1……b1)
とすると、 aj=bj(n≧j≧i+1、i−1≧j≧1) aj≠bj(j=i) である。ここでは、ai=1,bi=0とする。
ドのアドレスは2進数で表わしたとき、i番目のビット
のみが異なる。即ち、ノードA1aのアドレスを(an
……ai+1aiai−1……a1)、ノードB1bの
アドレスを(bn……bi+1bibi−1……b1)
とすると、 aj=bj(n≧j≧i+1、i−1≧j≧1) aj≠bj(j=i) である。ここでは、ai=1,bi=0とする。
すなわち、異なるビット位置の値(前述の優先情報)が
1のノードを優先ノード、0のノードを非優先ノードと
する。すなわちノードAが優先ノード、ノードBが非優
先ノードである。
1のノードを優先ノード、0のノードを非優先ノードと
する。すなわちノードAが優先ノード、ノードBが非優
先ノードである。
次に本実施例の動作を説明する。
ノードAからノードBにデータを送信する場合には、C
PU3aは送信先のアドレスと自ノードのアドレスを含
むパケット毎のデータを作成してOB4aに格納する。
OB4aに送信要求パケットが格納されると、CNT8
aはこのパケットをポート9a及び通信路2を介してノ
ードB1bへ送信する。ノードB1bではポート9bを
介してCNT8bが当該パケットを受信したとき(受信
パケットはIB5bに一旦格納される)、CNT8
bは、自ノードがノードA1aに対してCPU3bによ
り作成された送信要求パケットをOB4bより読み出し
てポート9bより送信し、送信可(ACK)パケットあ
るいは送信不可(NAK)パケットの応答を待っている
状態であれば、自ノードとノードA1aとの送信の優先
度を判断し、自ノードの優先度が高い場合には、ノード
A1aからのデータ送信を不許可するためにNAKパケ
ットを送信し、逆に、自ノードの優先度が低い場合に
は、ノードA1aからのデータ送信を許可するためにA
CKパケットを送信する。
PU3aは送信先のアドレスと自ノードのアドレスを含
むパケット毎のデータを作成してOB4aに格納する。
OB4aに送信要求パケットが格納されると、CNT8
aはこのパケットをポート9a及び通信路2を介してノ
ードB1bへ送信する。ノードB1bではポート9bを
介してCNT8bが当該パケットを受信したとき(受信
パケットはIB5bに一旦格納される)、CNT8
bは、自ノードがノードA1aに対してCPU3bによ
り作成された送信要求パケットをOB4bより読み出し
てポート9bより送信し、送信可(ACK)パケットあ
るいは送信不可(NAK)パケットの応答を待っている
状態であれば、自ノードとノードA1aとの送信の優先
度を判断し、自ノードの優先度が高い場合には、ノード
A1aからのデータ送信を不許可するためにNAKパケ
ットを送信し、逆に、自ノードの優先度が低い場合に
は、ノードA1aからのデータ送信を許可するためにA
CKパケットを送信する。
一方、ノードA1aはノードB1bへの送信要求パケッ
トを送信した後、ノードB1bからの送信要求パケット
を受信したとき、自ノードの優先度が高い場合には、ノ
ードB1bに対しNAKパケットを送信し、自ノードの
優先度が低い場合には、ノードB1bに対しACKパケ
ットを送信する。NAKパケットを受信した場合、ノー
ドはデータの送信を止め、ACKパケットを受信した場
合、データ送信を行う。ここで、各ノードにおけるデー
タ伝送の優先順位の判断は次の基準による。
トを送信した後、ノードB1bからの送信要求パケット
を受信したとき、自ノードの優先度が高い場合には、ノ
ードB1bに対しNAKパケットを送信し、自ノードの
優先度が低い場合には、ノードB1bに対しACKパケ
ットを送信する。NAKパケットを受信した場合、ノー
ドはデータの送信を止め、ACKパケットを受信した場
合、データ送信を行う。ここで、各ノードにおけるデー
タ伝送の優先順位の判断は次の基準による。
・互いにデータ送信を行おうとする2つのノードの優先
度はノードの番号による。すなわち、ノードの番号を2
進数で表したとき、異なる1つのビットの値が1のノー
ドを優先度が高いノードとし、0のノードを優先度が低
いノードとする。あるいは、逆にビットの値が0のノー
ドを優先度が高いノード、1のノードを優先度が低いノ
ードとしてもよい。
度はノードの番号による。すなわち、ノードの番号を2
進数で表したとき、異なる1つのビットの値が1のノー
ドを優先度が高いノードとし、0のノードを優先度が低
いノードとする。あるいは、逆にビットの値が0のノー
ドを優先度が高いノード、1のノードを優先度が低いノ
ードとしてもよい。
(発明の効果) 隣接するノード間で互いにデータを送信しようとする場
合、各送信ノードのアドレスを比較することにより、一
方を優先順位の高いノード、他の一方を優先順位の低い
ノードとする。まず、優先順位の高い方のノードからの
送信を行い、その後優先順位の低いノードからの送信を
行うので、従って、デッドロックを防止することが可能
となる。
合、各送信ノードのアドレスを比較することにより、一
方を優先順位の高いノード、他の一方を優先順位の低い
ノードとする。まず、優先順位の高い方のノードからの
送信を行い、その後優先順位の低いノードからの送信を
行うので、従って、デッドロックを防止することが可能
となる。
第1図は本発明の一実施例を示すシステム構成図、第2
図はハイパーキューブ結合例を示す図である。 1(1a,1b)……ノード(A,B) 2……通信路(転送路)、 3(3a,3b)……CPU、 4(4a,4b)……送信データ用のバッファ(OB)、 5(5a,5b)……受信データ用のバッファ(IB)、 6(6a,6b)、7(7a,7b)…… 中継データ用のバッファ(TB)、 8(8a,8b)……ネットワーク制御部(CNT)、 9(9a,9b)……ポート(PORT)。
図はハイパーキューブ結合例を示す図である。 1(1a,1b)……ノード(A,B) 2……通信路(転送路)、 3(3a,3b)……CPU、 4(4a,4b)……送信データ用のバッファ(OB)、 5(5a,5b)……受信データ用のバッファ(IB)、 6(6a,6b)、7(7a,7b)…… 中継データ用のバッファ(TB)、 8(8a,8b)……ネットワーク制御部(CNT)、 9(9a,9b)……ポート(PORT)。
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭58−90850(JP,A) 特開 昭60−84661(JP,A) 特開 昭58−166850(JP,A) 特公 昭58−47110(JP,B2)
Claims (1)
- 【請求項1】隣接するノードがそれぞれハミング距離が
1だけ異なるように2進数のアドレスを付与されたハイ
パーキューブ状に結合されノード間で、パケットを単位
としてデータ伝送を行うデータ伝送方式において、 隣接するノード間で互いにパケットを送信しようとする
際に、各送信ノードは自ノードのアドレスと隣接する送
信先のノードのアドレスを比較し、相異なるビット位置
の値が1か0かにより、パケット送信の優先順位を決定
することを特徴とするデータ伝送方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63030881A JPH0624361B2 (ja) | 1988-02-15 | 1988-02-15 | データ伝送方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63030881A JPH0624361B2 (ja) | 1988-02-15 | 1988-02-15 | データ伝送方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH01206751A JPH01206751A (ja) | 1989-08-18 |
| JPH0624361B2 true JPH0624361B2 (ja) | 1994-03-30 |
Family
ID=12316080
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63030881A Expired - Lifetime JPH0624361B2 (ja) | 1988-02-15 | 1988-02-15 | データ伝送方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0624361B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4643527B2 (ja) * | 2006-09-05 | 2011-03-02 | エヌ・ティ・ティ・コミュニケーションズ株式会社 | データ転送システム、データ転送方法、及びこれらに用いる転送装置 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5847110A (ja) * | 1981-09-16 | 1983-03-18 | Toshiyuki Ikegami | 回転板使用の内燃機関用吸・排気穴開閉装置 |
| JPS5890850A (ja) * | 1981-11-24 | 1983-05-30 | Nec Corp | ル−プ伝送方式およびその送受信装置 |
| US4814973A (en) * | 1983-05-31 | 1989-03-21 | Hillis W Daniel | Parallel processor |
-
1988
- 1988-02-15 JP JP63030881A patent/JPH0624361B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JPH01206751A (ja) | 1989-08-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4160642B2 (ja) | ネットワークデータ転送方法 | |
| US6011910A (en) | Supporting authentication across multiple network access servers | |
| US6266334B1 (en) | Method for optimizing acknowledge packet rate | |
| US4667287A (en) | Multiprocessor multisystem communications network | |
| JP3586281B2 (ja) | 適応性ルーターを使用するネットワーク通信装置 | |
| US4630259A (en) | Lockup detection and recovery in a packet switching network | |
| JP3806183B2 (ja) | データ通信システム及び方法 | |
| US5590328A (en) | Protocol parallel processing apparatus having a plurality of CPUs allocated to process hierarchical protocols | |
| US6453406B1 (en) | Multiprocessor system with fiber optic bus interconnect for interprocessor communications | |
| US8023520B2 (en) | Signaling packet | |
| Shanley | InfiniBand network architecture | |
| US20050132089A1 (en) | Directly connected low latency network and interface | |
| CA2011935A1 (en) | Dual-path computer interconnect system with four-ported packet memory control | |
| JPH0771110B2 (ja) | 自己経路選択パケツトスイツチ回路網 | |
| CN101320361B (zh) | 一种多cpu通讯方法及系统 | |
| US6147987A (en) | Supporting load sharing across multiple network access servers | |
| US6026085A (en) | Architecture to support a single system image across multiple network access servers | |
| WO2026067538A1 (zh) | 一种基于rdma的请求装置、响应装置和系统 | |
| US5054019A (en) | Transfer direction turnaround in network data communications | |
| US6278705B1 (en) | Integrated architecture to support a single system image across multiple network access servers | |
| WO1999014903A1 (en) | Dual priority chains for data-communication ports in a multi-port bridge for a local area network | |
| JPS63501663A (ja) | マルチプロセッサ通信装置 | |
| US6233232B1 (en) | Supporting multilink connections across multiple network access servers | |
| US8885673B2 (en) | Interleaving data packets in a packet-based communication system | |
| CN118869582B (zh) | 面向异构资源的网内聚合方法及系统 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| EXPY | Cancellation because of completion of term |