[go: up one dir, main page]

JP2708172B2 - 並列処理方法 - Google Patents

並列処理方法

Info

Publication number
JP2708172B2
JP2708172B2 JP63068135A JP6813588A JP2708172B2 JP 2708172 B2 JP2708172 B2 JP 2708172B2 JP 63068135 A JP63068135 A JP 63068135A JP 6813588 A JP6813588 A JP 6813588A JP 2708172 B2 JP2708172 B2 JP 2708172B2
Authority
JP
Japan
Prior art keywords
synchronization
synchronization point
processors
processor
signal
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
JP63068135A
Other languages
English (en)
Other versions
JPH01241662A (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.)
Toshiba Corp
Original Assignee
Toshiba Corp
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 Toshiba Corp filed Critical Toshiba Corp
Priority to JP63068135A priority Critical patent/JP2708172B2/ja
Publication of JPH01241662A publication Critical patent/JPH01241662A/ja
Application granted granted Critical
Publication of JP2708172B2 publication Critical patent/JP2708172B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Landscapes

  • Multi Processors (AREA)

Description

【発明の詳細な説明】 〔発明の目的〕 (産業上の利用分野) この発明は、マルチプロセッサシステムにおいて、複
数のプロセッサに割りつけられているマルチプロセッサ
同期方式に関する。
(従来の技術) 近年のマイクロプロセッサのめざましい発展により、
何百・何千というプロセッサを並列に稼働させることに
よって、処理の高速化を目ざすことか可能になってき
た。一方、高速化が望まれるアプリケーションは、行列
計算のように大量のデータに対して同一の処理をするよ
うなものばかりではなくなってきている。近年の人工知
能需要の高まりに伴ない、大量のデータに対して多種・
多様な処理を施すようなアプリケーションの高速化が切
望されるようになってきた。
しかし、いくらたくさんのプロセッサを使おうとも、
それだけでは処理の高速化は望めない。並列処理の効果
を出すためには、処理をうまく分担しあって、1つのプ
ロセッサでの処理量を減らさなければならない。
近年では、パイプライン型の計算機でも、パイプライ
ンを複数持ち、並列に稼働させて高速化をはかる動きも
出てきたが、その効果を発揮させるためには、処理のル
ープ長が長いことが望ましい。つまり、計算の結果を互
いに参照することのない同一内容の処理の繰り返しが多
いアプリケーションでは並列処理効果を引き出しやす
い。逆に、ループ長の短かいループが乱発するような処
理では、1つのループ内での並列度は低いため、2つ以
上のループ間の依存関係・順序関係まで考慮した上での
並列処理を考えない限り、高速化は期待できない。特
に、非常に多くのプロセッサを用いて、そのようなアプ
リケーションを並列処理する時、1つのループ内の並列
処理のみを考えていたのでは、大半のプロセッサはデー
タが枯唱してしまう。ゆえにプロセッサの数を増せば増
すほど、従来1つのプロセッサでシーケンシャルに行っ
ていた一連の処理を細かく分割し、(その分割された処
理の単位をプロセスと呼ぶことにする)複数のプロセッ
サにプロセスをマッピングして、プロセス間の依存関係
・順序関係に従って、互いに連けいを取り合いながら処
理を進めることが必要になる。
例えば、第4図に示すようなA.B.Cの3つの処理があ
って、A.Bの結果を用いてCの処理を行なうとする。こ
の時、Aの処理の完了と、Bの処理の完了を待ち合わせ
て、Cの処理を開始するといったことが必要となる。こ
こで処理A.B.Cが別のプロセッサにマッピングされて並
列に処理される場合、プロセッサ間での待ち合わせ(同
期)が必要となる。
一方、マルチタスク実行時のように、以上のような同
期がマルチプロセッサシステムのいたる所で、複数種類
必要な場合、それらが互いに干渉しないようにしなけれ
ばならない。第5図に示した処理のように、プロセスが
同期によって完全にグループ化できるようなアプリケー
ションに対しては、プロセッサをクラスタ化して、各ク
ラスタごとに独立した同期機構(割込線など)を持たせ
れば、以上の干渉は防げる。しかし、この方式はプロセ
スの自由なマッピングを阻害するため、システムを専用
化してしまう。又、第6図のように、同一のプロセスが
複数の同期にかかわるようなアプリケーションに対して
は、複数の同期機構をシステム全体にはりめぐらさねば
ならない。汎用マシンでは、マッピングは定まらないの
で、従来はこのような同期をハードウェアにより行うこ
とは避けられていた。このため、ソフトウェアでこのよ
うな同期をとらざるを得ず、オーバーヘッドが大きく効
率が悪かった。
(発明が解決しようとする課題) この様に従来のマルチプロセッサシステムでは、シス
テム上にマッピングされたプロセス間での待ち合わせが
円滑に行なえないという欠点が有った。
本発明は、汎用な問題をマルチプロセッサシステムで
処理する際、システム上にマッピングされたプロセス間
での待ち合わせを円滑に行なうことを目的とし、実行の
順序制御を矛盾なく行なえることを保証することによっ
て、各々のプロセスのマルチプロセッサ上への自由なマ
ッピングを可能にすることを目的とする。
〔発明の構成〕
(課題を解決するための手段) 本発明では、複数のプロセスを並行処理させるマルチ
プロセッサシステムに対し、各プロセッサに同期ポイン
ト識別子付の同期ポイント到達信号生成手段と、各プロ
セッサからの上記信号の検出装置と、上記検出装置から
の検出信号を受けて全プロセッサに対して同期ポイント
識別子付の待期解除信号を生成し放送する手段を具備さ
せる。
(作用) まず、マルチプロセッサシステムに複数のプロセスを
マッピングする。この時、相互の依存関係から、待ち合
わせを要するポイントを元のプログラムから解析し、そ
れぞれに同期ポイント識別子を割り当てる。なおシステ
ムの処理実行の開始に際し、各プロセッサは、自分には
関わりのない同期ポイント識別子すべてに対し、ダミー
の同期ポイント到達信号を出しておく。各プロセッサ
は、自分が担当するプロセスの実行が、その同期ポイン
トへ到達したならば、そのポイントにつけられた識別子
を持った同期ポイント到達信号を、検出装置に送る。検
出装置は、その監視下の全プロセッサからある識別子付
の同期ポイント到達信号を受けたならば、更に上位の検
出装置又は待期解除信号生成手段へ、その識別子付の同
期ポイント到達信号を送る。最上位の検出装置は、その
直下からの到達信号が全てそろったことをもって、シス
テム全体の同期ポイント到達を識別する。その検出信号
を受けて待期解除信号生成手段は全プロセッサに対し、
検出信号中の識別子付の待期解除信号を放送する。こう
して全プロセッサは、その識別子で指定されるシステム
全体における待ち合わせが完了したことを知ることがで
き、その待ち合わせ完了を待っていたプロセッサは、待
ち合わせ完了後の処理を開始できる。
(実施例) 以下、本発明の一実施例について説明する。第1図は
本発明における同期ポイント到達信号検出装置の一実施
例である。ここでは、検出装置F1つにつき、8本の下方
リンクLL、1本の上方リンクULを持つものを例にとり説
明する。各プロセッサは自分に割り当てられたすべての
プロセスについて、ある同期ポイントに到達したなら
ば、検出装置Fの下方リンクに同期ポイント到達信号を
出力する。同期ポイント到達信号は第2図のフォーマッ
ト例に示すように、そのデータが同期ポイント到達信号
であることを示す同期データフラグSと、同期ポイント
を識別する同期番号Nを必ず含むようにする。Nのビッ
ト幅によって一つの検出装置F内に設置するカウンタC
の個数が決まる。例えば、同期番号Nが4ビットなら
ば、カウンタCは16個必要で、最大16種類までの同期を
とることが可能になる。下方リンクL0〜L7から入ったデ
ータは、それぞれレジスタR0〜R7にラッチされる。それ
らのデータ中の同期データフラグが1ならば、アービタ
Aに要求信号が出され、調停された後、許可がおりたレ
ジスタ中の同期番号NはマルチプレクサMを通してデコ
ーダD1に渡たされ、同期番号Nに対応するカウンタCN
インクリメントする。次にアービタAはデコーダD2を介
して先程許可をおろしたレジスタの同期フラグSを0に
リセットする。こうして次の調停が開始して、上記のこ
とがくり返される。下方の全プロセッサが同期ポイント
Nに到達すると、8本の下方リンクから同期データが入
ってくるので、カウンタNは8を示すようになる。この
時、カウンタNから同期データジェネレータに上方リン
クへの同期データ生成要求信号が出される。同期データ
ジェネレータGは、同期データ生成要求信号を出したカ
ウンタの番号を持つ同期データを生成し上方リンクから
送信する。次に同期データを上方リンクに送信させたカ
ウンタは、次回の同一の同期番号の同期に備えてリセッ
トされる。
検出装置Fをプロセッサの個数に応じて、第3図に示
すような数階層の8分木構造で接続して、マルチプロセ
ッサの同期システムを構築する。このように接続してお
けば、全プロセッサが同期番号Nの同期ポイントに到達
したならば最上位の検出装置の上方リンクから同期デー
タNが送信される。これを待機解除信号として全プロセ
ッサへ放送すれば、全プロセッサは、システム全体が同
期ポイントNに到達したことを知ることができ、それを
待っていたプロセッサは、次のステップへの実行が開始
される。
なお、プロセスの割りあてかたによっては、全プロセ
ッサが全同期ポイントに関係するとは限らないので、各
プロセッサはリセット時と、同期データが上から放送さ
れてきた時に、自分に関係のない同期番号の同期データ
を生成して上方に送信することになる。
また、プロセッサ数に対してプロセス数のほうが多い
場合、1つのプロセッサに対して複数のプロセスがマッ
ピングされる。この時、1つのプロセッサ内でのプロセ
ス間の同期は、ソフトウェアで行ない、プロセッサ内部
での同期がとれたら、はじめて検出装置Fへ、そのプロ
セッサからの同期ポイント到達信号を出力することにな
る。ソフトウェアでシステム全体の同期をとろうとする
と、システム内の全プロセスとの通信を行わなければな
らないので、非常にオーバーヘッドが大きいが、本方式
では、通信を伴わないプロセッサ内部のソフトウェア式
同期を終えたら、同期ポイント到達信号を1回出すだけ
で、あとはプロセッサ外の同期機構が処理してくれるの
で、プロセッサの負担は軽く、オーバーヘッドが少な
い。
ハードウェア量の観点から本システムはどうかという
と、同期ポイント到達信号が転送される通信路は、プロ
セッサとホスト間のデータ通信路と共用可能なので、新
たな配線量の増加分はないといえる。
〔発明の効果〕
以上の説明から明らかなように、本発明によれば、複
数のプロセスを並行して処理させるマルチプロセッサシ
ステムにおいて、相互干渉や極度の配線量増大、オーバ
ーヘッド増大を起こすことなしに、複数の同期ポイント
に対するプロセッサ間同期が可能となる。又、プロセス
のマッピングにかかわりなく、実行の順序制御を矛盾な
く行なうことができるので、プロセッサへのプロセスの
自由なマッピングが可能になる。
【図面の簡単な説明】
第1図は本発明における同期ポイント到達信号検出装置
の一実施例の図、第2図は同期ポイント到達信号及び待
期解除信号のフォーマットの一例の図、第3図は第1図
の検出装置を用いたマルチプロセッサの同期システムの
図、第4図は待ち合わせを必要とする処理の概念図、第
5図はクラスタ化により同期間干渉を排除できる問題の
例の図、第6図はクラスタ化では同期間干渉を排除でき
ない問題の例の図である。

Claims (1)

    (57)【特許請求の範囲】
  1. 【請求項1】複数のプロセッサを用い、複数のプロセス
    を並行して処理する並列処理方法において、 各プロセッサは同期ポイント識別子付の同期ポイント到
    達信号を出力し、 前記同期ポイント識別子ごとに下位の全プロセッサから
    同期ポイント到達信号が出力されたか否かを検出し、 前記同期ポイント到達信号の出力が検出された場合に対
    応する識別子付の同期ポイント到達信号を上位のプロセ
    ッサに出力し、 最上位のプロセッサは特定の同期ポイント識別子付の同
    期ポイント到達信号の出力を検出した場合、前記同期ポ
    イント識別子付の待機解除信号を下位の全プロセッサに
    放送することを特徴とする並列処理方法。
JP63068135A 1988-03-24 1988-03-24 並列処理方法 Expired - Lifetime JP2708172B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP63068135A JP2708172B2 (ja) 1988-03-24 1988-03-24 並列処理方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP63068135A JP2708172B2 (ja) 1988-03-24 1988-03-24 並列処理方法

Publications (2)

Publication Number Publication Date
JPH01241662A JPH01241662A (ja) 1989-09-26
JP2708172B2 true JP2708172B2 (ja) 1998-02-04

Family

ID=13365001

Family Applications (1)

Application Number Title Priority Date Filing Date
JP63068135A Expired - Lifetime JP2708172B2 (ja) 1988-03-24 1988-03-24 並列処理方法

Country Status (1)

Country Link
JP (1) JP2708172B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2009023076A1 (en) * 2007-08-14 2009-02-19 Hewlett-Packard Development Company, L.P. Synchronization of processors in a multiprocessor system

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4114480B2 (ja) 2001-02-24 2008-07-09 インターナショナル・ビジネス・マシーンズ・コーポレーション グローバル割込みおよびバリア・ネットワーク
JP5239751B2 (ja) 2008-10-31 2013-07-17 富士通株式会社 ノード間同期装置、ノード間同期方法およびノード間同期プログラム
WO2012127534A1 (ja) * 2011-03-23 2012-09-27 富士通株式会社 バリア同期方法、バリア同期装置及び演算処理装置

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2009023076A1 (en) * 2007-08-14 2009-02-19 Hewlett-Packard Development Company, L.P. Synchronization of processors in a multiprocessor system

Also Published As

Publication number Publication date
JPH01241662A (ja) 1989-09-26

Similar Documents

Publication Publication Date Title
US12106099B2 (en) Execution or write mask generation for data selection in a multi-threaded, self-scheduling reconfigurable computing fabric
US11675734B2 (en) Loop thread order execution control of a multi-threaded, self-scheduling reconfigurable computing fabric
US11675598B2 (en) Loop execution control for a multi-threaded, self-scheduling reconfigurable computing fabric using a reenter queue
US11573796B2 (en) Conditional branching control for a multi-threaded, self-scheduling reconfigurable computing fabric
US11567766B2 (en) Control registers to store thread identifiers for threaded loop execution in a self-scheduling reconfigurable computing fabric
US11836524B2 (en) Memory interface for a multi-threaded, self-scheduling reconfigurable computing fabric
US11531543B2 (en) Backpressure control using a stop signal for a multi-threaded, self-scheduling reconfigurable computing fabric
US11635959B2 (en) Execution control of a multi-threaded, self-scheduling reconfigurable computing fabric
US10990392B2 (en) Efficient loop execution for a multi-threaded, self-scheduling reconfigurable computing fabric
EP0502680B1 (en) Synchronous multiprocessor efficiently utilizing processors having different performance characteristics
US4497059A (en) Multi-channel redundant processing systems
US12182048B2 (en) Multi-threaded, self-scheduling reconfigurable computing fabric
JP3746371B2 (ja) 性能シミュレーション方法
JPH02238553A (ja) マルチプロセツサ・システム
US20040187118A1 (en) Software barrier synchronization
JPS62159268A (ja) マルチプロセツサシステム
Wallach Alternating sequential/parallel processing
US20160335103A1 (en) Locking/Unlocking CPUs to Operate in Safety Mode or Performance Mode Without Rebooting
JPS6334490B2 (ja)
JP2708172B2 (ja) 並列処理方法
CN109313581A (zh) 用于多核处理器的同步操作的方法
JP2780623B2 (ja) 情報処理装置
JPH02105961A (ja) マルチプロセッサ同期方式
JPH11306038A (ja) 並列演算処理装置およびその方法
JPH11306149A (ja) 並列演算処理装置およびその方法

Legal Events

Date Code Title Description
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081017

Year of fee payment: 11

EXPY Cancellation because of completion of term
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20081017

Year of fee payment: 11