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
Application number
JP63030881A
Other languages
English (en)
Other versions
JPH01206751A (ja
Inventor
信行 守谷
康 和宇慶
実治 棟安
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
National Institute of Advanced Industrial Science and Technology AIST
Original Assignee
Agency of Industrial Science and Technology
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Agency of Industrial Science and Technology filed Critical Agency of Industrial Science and Technology
Priority to JP63030881A priority Critical patent/JPH0624361B2/ja
Publication of JPH01206751A publication Critical patent/JPH01206751A/ja
Publication of JPH0624361B2 publication Critical patent/JPH0624361B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

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(=2,nは正の整数)個のノードからなり、
各ノードは主として、処理を実行するプロセッサと各ノ
ード間でデータ伝送を行うデータ通信部とから成る。各
ノードにはn本の転送路がある。ノードaのアドレスは
2進数(an−1……a)で表わされる。ノ
ードAは、n−1……a)、(a
n−1……a)、……、(an−1……
)、(an−1……a )をアドレスとす
るノードと結合している。すなわち、アドレスaのノー
ドAはそれとハミング距離が1だけ異なるノードに直接
結合している。
以上のように構成されたシステムにおける従来のデータ
伝送方式の処理手順について説明する。例えば、ノード
A(a……a)からノードB(b……b)への
データ転送は次のように行われる。最下位ビットから調
べて、最初にa=1となるノード(a……b
i−1……b)にデータを送る。(a……a
……a)と(a……bi−1……b)はiビ
ット目のみ異なっている2進数であるので、直接つなが
っている隣接ノードとなっている。最上位ビットまでこ
の過程を繰り返すと、ノードAとノードBの通信ができ
る。
このように、任意の2つのノード間でデータ伝送を行う
場合、ノード数が多くなるほど、経由する転送路の平均
数は増加する。
ノードのデータ通信部においては、伝送制御を簡単にす
るために、半二重通信で行うことが考えられている。す
なわち、データの伝送を送信と受信に分け、同時に実行
しない方式である。この場合、データの伝送は以下に示
す手順に従って実行される。まず、送信ノードは送信要
求を隣接するノード(受信ノード)に送信する。該送信
要求を受信したノードは受信できる状態ならば、受信可
(ACK)を、また受信できない状態ならば受信不可
(NAK)を返送する。送信ノードは受信ノードからA
CKを受信することにより、データの送信を開始する。
また受信ノードは、ACKを返送した後、データ受信状
態にはいる。
また、各ノードにおいて、データ送信とデータ受信を同
時に行おうとする場合には、送信を受信よりも優先する
送信優先、あるいはこの逆の受信優先により行う。
(発明が解決しようとする問題点) しかしながら、上記データ伝送方式では、送信優先とす
る場合を考えると、ノードAがノードBへデータ伝送す
ることと、ノードBがノードAにデータ伝送しようとす
ることが同時に起きた場合、ノードAもノードBを互い
にデータを送信しようとするが、どちらもデータ受信さ
れないので、デッドロックとなる。また逆に、受信優先
の場合も、両方のノードが受信状態になり、デッドロッ
クとなる。このように、従来の送信優先、受信優先のデ
ータ伝送方式はデッドロックを起こすという問題点があ
った。本発明は以上述べた問題点を解決し、デッドロッ
クを防止するデータ伝送方式を提供することを目的とす
る。
(問題点を解決するための手段) 本発明は前記問題点を解決するために、隣接するノード
がそれぞれハミング距離が1だけ異なるように2進数の
アドレスを付与されたハイパーキューブ状に結合されノ
ード間で、パケットを単位としてデータ伝送を行うデー
タ伝送方式において、隣接するノード間で互いにパケッ
トを送信しようとする際に、各送信ノードは自ノードの
アドレスと隣接する送信先のノードのアドレスを比較
し、相異なるビット位置の値が1か0かにより、パケッ
ト送信の優先順位を決定するものである。
(作用) 本発明は次のように作用する。隣接するノード間で互い
にパケットを送信しようとする際に、各ノードは、自ノ
ードのアドレスと隣接する送信先のノードのアドレスを
比較し、相異なるビット位置の値が1か0かにより、パ
ケット送信の優先順位を決定する。優先順位の高い方の
送信ノードは送信不可(NAK)パケットを相手側ノード
に送信することにより、パケットを送信することができ
る。この後、優先順位の低い方のノードの送信を行う。
従って、デッドロックを防止することが可能となる。
(実施例) 第1図は本発明の一実施例を示すシステム構成図であっ
て、説明を簡単にするため、ハイパーキューブ結合され
た複数のノードのうち、隣接するノードA,Bの構成の
みを示すものである。ノードA1は通信路(転送路)
2を介してノードB1に接続される。各ノードは同一
の内部構成を持ち、CPU3、送信データ用のバッファ
(OB)4、受信データ用のバッファ(IB)5、中継
データ用のバッファ(TB)6,7、ネットワーク制御
部(CNT)8、ポート(PORT)9から構成され
る。CPU3はノード全体を制御するプロセッサであ
る。OB4はCPU1で作成したデータを他ノードに送
信するためのバッファ、IB5は他ノードから自ノード
へ送信されてきたデータを受信するためのバッファ、T
B6,7は中継データを一時蓄積するためのバッファで
ある。CNT8は、データを送受信するための制御とル
ーティング処理を実行するネットワーク制御部である。
PORT9はデータの送受信を行うためのものであり、
他ノードと通信路によって接続される。
ここで、ノードA1の構成要素の参照符号には添字
a、同様にノードB1のものには添字bを付与する。
データの送受信は、パケットを単位として行う。各ノー
ドのアドレスは2進数で表わしたとき、i番目のビット
のみが異なる。即ち、ノードA1のアドレスを(a
……ai+1i−1……a)、ノードB1
アドレスを(b……bi+1i−1……b
とすると、 a=b(n≧j≧i+1、i−1≧j≧1) a≠b(j=i) である。ここでは、a=1,b=0とする。
すなわち、異なるビット位置の値(前述の優先情報)が
1のノードを優先ノード、0のノードを非優先ノードと
する。すなわちノードAが優先ノード、ノードBが非優
先ノードである。
次に本実施例の動作を説明する。
ノードAからノードBにデータを送信する場合には、C
PU3は送信先のアドレスと自ノードのアドレスを含
むパケット毎のデータを作成してOB4に格納する。
OB4に送信要求パケットが格納されると、CNT8
はこのパケットをポート9及び通信路2を介してノ
ードB1へ送信する。ノードB1ではポート9
介してCNT8が当該パケットを受信したとき(受信
パケットはIB5に一旦格納される)、CNT8
は、自ノードがノードA1に対してCPU3によ
り作成された送信要求パケットをOB4より読み出し
てポート9より送信し、送信可(ACK)パケットあ
るいは送信不可(NAK)パケットの応答を待っている
状態であれば、自ノードとノードA1との送信の優先
度を判断し、自ノードの優先度が高い場合には、ノード
A1からのデータ送信を不許可するためにNAKパケ
ットを送信し、逆に、自ノードの優先度が低い場合に
は、ノードA1からのデータ送信を許可するためにA
CKパケットを送信する。
一方、ノードA1はノードB1への送信要求パケッ
トを送信した後、ノードB1からの送信要求パケット
を受信したとき、自ノードの優先度が高い場合には、ノ
ードB1に対しNAKパケットを送信し、自ノードの
優先度が低い場合には、ノードB1に対しACKパケ
ットを送信する。NAKパケットを受信した場合、ノー
ドはデータの送信を止め、ACKパケットを受信した場
合、データ送信を行う。ここで、各ノードにおけるデー
タ伝送の優先順位の判断は次の基準による。
・互いにデータ送信を行おうとする2つのノードの優先
度はノードの番号による。すなわち、ノードの番号を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)。
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭58−90850(JP,A) 特開 昭60−84661(JP,A) 特開 昭58−166850(JP,A) 特公 昭58−47110(JP,B2)

Claims (1)

    【特許請求の範囲】
  1. 【請求項1】隣接するノードがそれぞれハミング距離が
    1だけ異なるように2進数のアドレスを付与されたハイ
    パーキューブ状に結合されノード間で、パケットを単位
    としてデータ伝送を行うデータ伝送方式において、 隣接するノード間で互いにパケットを送信しようとする
    際に、各送信ノードは自ノードのアドレスと隣接する送
    信先のノードのアドレスを比較し、相異なるビット位置
    の値が1か0かにより、パケット送信の優先順位を決定
    することを特徴とするデータ伝送方式。
JP63030881A 1988-02-15 1988-02-15 データ伝送方式 Expired - Lifetime JPH0624361B2 (ja)

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)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4643527B2 (ja) * 2006-09-05 2011-03-02 エヌ・ティ・ティ・コミュニケーションズ株式会社 データ転送システム、データ転送方法、及びこれらに用いる転送装置

Family Cites Families (3)

* Cited by examiner, † Cited by third party
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

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