JPH064492A - 同期テーブルを用いた手続の同期方式 - Google Patents

Abstract

(57)【要約】 【目的】 少数のエントリから構成される同期テーブル
を用いた手続の同期方式を得る。 【構成】 プログラム解析部１１は１個のプログラムを
複数の手続きに分割し、並列実行可能な手続きをブロッ
クという同期のための管理単位で区分する。同期テーブ
ル作成部１２はプログラム解析部１１から伝達されたブ
ロックの数と同数の同数のエントリを持ち、各エントリ
にはブロックで実行される手続の数が設定される数記録
部と、現在の手続きの実行状況を表すエントリを持つ実
行状況記録部とからなる同期テーブル１３に設定する。
同期テーブル制御部１４は手続実行部１５，１５ａの実
行状況に応じて実行状況記録部のエントリの値を更新す
ることにより手続きの同期をとる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はタイトリ・カップル・マ
ルチプロセッサ（ＴＣＭＰ）における手続の同期方式に
係り、特に同期を得るための同期テーブルのエントリの
個数の軽減に関するものである。

【０００２】

【従来の技術】図５は特開昭６１−２６４４６８号公報
に開示されている手続の同期方式の原理説明図であり、
複数のプロセッサを持つシステムにおいてＯＳを経由せ
ずに同期テーブルを更新して手続の同期をとるようにし
ている。図において、主記憶装置ＭＳは複数のプロセッ
サＣＰＵ１，ＣＰＵ２，…に共通な憶装置であり、プロ
セッサＣＰＵ１は手続Ｐ１を実行し、プロセッサＣＰＵ
２は手続Ｐ２を実行する。手続Ｐ１と手続Ｐ２とは並列
実行可能な手続であり、手続Ｐ３は手続Ｐ１及び手続Ｐ
２の実行終了後に実行される手続である。同期テーブル
１０は手続Ｐ１とＰ２との同期をとるためのテーブルで
あり、手続の個数分だけのエントリを持っている。エン
トリＥ１は手続Ｐ１の実行状態を表す同期テーブル１０
内の実行状態を表すエントリであり、エントリＥ２は手
続Ｐ２の実行状態を表す同期テーブル１０内のエントリ
である。エントリＥ３は手続Ｐ３の実行状態を表す同期
テーブル１０内のエントリである。

【０００３】次に動作について説明する。手続Ｐ１と手
続Ｐ２とを並列実行した後に手続Ｐ３を実行する場合に
は、手続Ｐ１をプロセッサＣＰＵ１が実行し、手続Ｐ２
をプロセッサＣＰＵ２が実行し、そして、手続Ｐ３は手
続Ｐ１及び手続Ｐ２の実行が終了したのを待ってから実
行される。つまり、手続Ｐ１と手続Ｐ２の同期をとって
手続Ｐ３を実行することになる。この同期をとるため
に、手続の個数分だけのエントリＥ１，Ｅ２，Ｅ３が同
期テーブル１０内に予め用意されている。手続Ｐ１と手
続Ｐ２とは同期をとる手続が必要ないため、エントリＥ
１とエントリＥ２の初期値をそれぞれ「０」とする。エ
ントリＥ３の初期値は、同期をとる手続の個数が２個の
ため「−２」とする。そして、手続Ｐ１，Ｐ２をプロセ
ッサＣＰＵ１，ＣＰＵ２で並列に実行する。この時エン
トリＥ１，Ｅ２に実行表示を付加する。これにより、手
続Ｐ１，Ｐ２は他のプロセッサにより実行されることは
ない。この実行が終了した時、各プロセッサＣＰＵ１，
ＣＰＵ２はエントリＥ３の値を「＋１」とする。つま
り、手続Ｐ１及び手続Ｐ２がともに実行終了した時、エ
ントリＥ３の値は「０」となる。この「０」とエントリ
Ｅ３３に実行表示のないことを他のプロセッサが見つ
け、手続Ｐ３を実行し、エントリＥ３に実行表示を付加
する。

【０００４】

【発明が解決しようとする課題】従来の同期テーブル１
０のエントリの数は実行する手続の数と同数である。従
って、手続が多数存在する場合には同期テーブルのエン
トリ数も莫大となり、それだけ大容量のメモリを必要と
するという問題点があった。

【０００５】本発明は、上記のような問題点を解消する
ためになされたものであり、同期テーブルのエントリの
数を軽減して小容量のメモリにより実現できるようにし
た同期テーブルを用いた手続の同期方式を提供すること
を目的とする。

【０００６】

【課題を解決するための手段】本発明の同期テーブルを
用いた手続の同期方式は、共通の主記憶装置と複数のプ
ロセッサを所有するデータ処理装置において、実行する
１個のプログラムを複数の手続に分割し、並列実行可能
な手続を同期のための管理単位であるブロックに区分す
るプログラム解析部と、ブロックの数と同数でかつ時系
列に配列されたエントリを持ち、各エントリには該当す
るブロック内の手続の数が設定される手続数記録部と、
現在の手続の実行状況を表すエントリを持つ実行状況記
録部とからなる同期テーブルを設定する同期テーブル作
成手段と、同期テーブルの実行状況記録部のエントリの
値を手続の実施状況に応じて更新する同期テーブル制御
手段とを有する。そして、複数のプロセッサは、同期テ
ーブルの手続数記録部のエントリの該当する手続をそれ
ぞれ並列実行し、同期テーブル制御手段はその実行の度
に実行状況記録部のエントリを更新し、そのエントリの
値が手続数記録部の該当するエントリの値と一定の関係
になると、次のエントリの各手続の実行を開始する。

【０００７】

【作用】本発明においては、同期テーブルは手続数記録
部と実行状況記録部とから構成されており、手続数記録
部はブロックの数と同数のエントリを持ち、各エントリ
には該当するブロック内の手続の数が設定され、実行状
況記録部は現在の手続の実行状況を表すエントリを持っ
ている。従って、同期テーブルのエントリの数はをブロ
ックの数と実行状況記録部のエントリの数との和とな
り、少数のエントリにより同期テーブルを実現すること
ができる。

【０００８】

【実施例】

実施例１．図１は本発明の一実施例に係る同期テーブル
を用いた手続の同期方式の構成を示すブロック図であ
る。図において、プログラム解析部１１は、実行する１
個のプログラムを複数の手続に分割し、並列実行可能な
手続をブロックという同期のための管理単位に区分し、
そのブロックの数（この実施例では「４」）を同期テー
ブル作成部１２に伝達するものである。同期テーブル作
成部１２は、プログラム解析部１１から伝達されたブロ
ックの数と同数でかつ時系列に配列されたエントリを持
ち、各エントリには該当するブロック内の手続の数が設
定される手続数記録部と、現在の手続の状況を表す４個
のエントリを持つ実行状況記録部とからなる同期テーブ
ル１３を例えば図５の主記憶装置ＭＳ内に形成し、各記
録部の初期値を設定する。同期テーブル制御部１４は、
同期テーブル１３の実行状況記録部の４個のエントリの
値を更新することにより手続の同期をとる。手続実行部
１５は、同期テーブル１３を参照して該当する手続を実
行する。ＣＰＵ１は上述のプログラム解析部１１、同期
テーブル作成部１２、同期テーブル制御部１４及び手続
実行部１５を構成しており、また、ＣＰＵ２も同様な構
成からなる同期テーブル制御部１４ａ及び手続実行部１
５ａを構成している。

【０００９】図２は手続のブロック区分を示した図であ
る。図において、ブロックＢ１〜Ｂ４は同期のための管
理単位となるブロックである。この実施例においてはＰ
１〜Ｐ１２の１２個の手続を並列実行可能な手続ごとに
ブックに区分するため、手続Ｐ１はブロックＢ１、手続
Ｐ２〜Ｐ５はブロックＢ２、手続Ｐ６〜Ｐ８はブロック
Ｂ３，手続Ｐ９〜Ｐ１２はブロックＢ４に区分されてい
る。従って、この実施例ではブロックＢ１の手続Ｐ１の
実行終了後にブロックＢ２の手続Ｐ２〜Ｐ５を並列実行
する。これらの手続の実行終了後、ブロックＢ３の手続
Ｐ６〜Ｐ８を並列実行し、更にこれらの手続の実行終了
後、ブロックＢ４の手続Ｐ９〜Ｐ１２を並列実行する。

【００１０】図３は同期テーブル１３の構成図である。
同期テーブル１３は手続数記録部２０及び実行状況記録
部２１から構成されている。手続数記録部２０はエント
リＥ１〜Ｅ４から構成されている。エントリＥ１はブロ
ックＢ１で実行される手続の数を表すエントリ、エント
リＥ２はブロックＢ２で実行される手続の数を表すエン
トリ、エントリＥ３はブロックＢ３で実行される手続の
数を表すエントリであり、エントリＥ４はブロックＢ４
で実行される手続の数を表すエントリＥ4 である。そし
て、これらのエントリＥ１〜Ｅ４は時系列に配列されて
いる。実行状況記録部２１はエントリＢ，Ｆ，Ｓ，Ｔか
ら構成されている。エントリＢは現在実行中の手続のブ
ロック番号を表すエントリ、エントリＦ４は現在のブロ
ックで実行終了した手続の数を表すエントリ、エントリ
Ｓはブロック内の手続のみを実行するためのエントリで
あり、エントリＴは実行された手続の総数を表すエント
リである。

【００１１】次に、以上の構成からなるこの実施例の動
作を説明する。図４はこの実施例の動作を示すフローチ
ャートである。図において、処理（Ｓ２）における条件
（：エントリＢは「４」以下）は全ての手続の実行終了
を判定するための条件、処理（Ｓ３）における条件（：
エントリＳ＝Ｓ＋１はエントリＥB 以下）はブロック内
の手続のみを実行するための条件であり、処理（Ｓ６）
における条件（：エントリＦとエントリＥB は一致）は
ブロック内の手続が全て実行終了したかどうかを判定す
る条件である。 (1) まず、ＣＰＵ１のプログラム解析部１１はプログラ
ムを解析し、同期テーブル作成部１２はその解析結果に
基づいて同期テーブル１３を作成し、そして、各エント
リの初期値Ｅ１＝１、Ｅ２＝４、Ｅ３＝３，Ｅ４＝４、
Ｂ＝１，Ｆ＝Ｓ＝Ｔ＝０をそれぞれ設定する（Ｓ１）。
なお、Ｂ＝１，Ｆ＝Ｓ＝Ｔ＝０の初期設定は同期テーブ
ル制御部１４によって設定してもよい。 (2) ＣＰＵ１の手続実行部１５は同期テーブル１３のエ
ントリＢが「４」以下であるかどうか判断する（Ｓ
２）。ここではＢ＝１に設定されているので、Ｂが
「４」以下であると判断される。

【００１２】(3) 次に、ＣＰＵ１の同期テーブル制御部
１４はエントリＳ＝Ｓ＋１とし、手続実行部１５はこの
エントリＳ（＝１）がエントリＥ１の値以下であるかど
うかを判断する（Ｓ３）。ここでは、Ｓ＝１，Ｅ１＝１
であるから、エントリＳ（＝１）がエントリＥ１の値以
下であると判断され、次に、同期テーブル制御部１４は
エントリＴ＝Ｔ＋１＝１に設定する（Ｓ４）。手続実行
部１５はブロックＢ１の手続ＰT 即ちＰ１を実行し、そ
の実行が終了するとその終了したことを同期テーブル制
御部１４に連絡する。この連絡を受けると、同期テーブ
ル制御部１４はエントリＦ＝Ｆ＋１（＝１）と設定する
（Ｓ５）。なお、ブロックＢ２，Ｂ３，Ｂ４の各手続は
前記の処理（Ｓ３）の条件が満足されないので実行され
ない。 (4) 次に、同期テーブル制御部１４がエントリＳ＝Ｓ＋
１（＝２）と設定すると、手続実行手段１５は同期エン
トリＳ＝Ｓ＋１（＝２）はエントリＥ１（＝１）を越え
ていると判断し（Ｓ３）、次に、エントリＦ＝Ｅ１であ
るどうかを判断する（Ｓ６）。ここではＦ＝１，Ｅ１＝
１であるから一致しているものと判断される。このよう
に判断されると、同期テーブル制御部１４はエントリＢ
＝Ｂ＋１（＝２）、エントリＳ＝Ｆ＝０と設定してブロ
ックＢ２の処理に進む（Ｓ７）。

【００１３】(5) ＣＰＵ１の手続実行部１５は次にエン
トリＢが「４」以下であるかどうか判断するが（Ｓ
２）、ここではＢ＝２に設定されているので、Ｂが
「４」以下であると判断される。そして、同期テーブル
制御部１４はエントリＳ＝Ｓ＋１とし、手続実行部１５
はこのエントリＳ（＝１）がエントリＥ２の値以下であ
るかどうかを判断する（Ｓ３）。ここでは、Ｓ＝１，Ｅ
２＝４であるから、エントリＳ（＝１）がエオントリＥ
２の値以下であると判断され、次に、同期テーブル制御
部１４はエントリＴ＝Ｔ＋１＝２に設定する（Ｓ４）。
手続実行部１５はブロックＢ２の手続ＰT 即ちＰ２を実
行する（Ｓ５）。 (6) ＣＰＵ２も同様に同期テーブル１３にアクセスし、
ＣＰＵ２の手続実行部１５ａはエントリＢが「４」以下
であるかどうか判断するが（Ｓ２）、ここではＢ＝２に
設定されているので、Ｂが「４」以下であると判断され
る。そして、同期テーブル制御部１４ａはエントリＳ＝
Ｓ＋１とし、手続実行部１５ａはこのエントリＳ（＝
２）がエントリＥ２の値以下であるかどうかを判断する
（Ｓ３）。ここでは、Ｓ＝２，Ｅ２＝４であるから、エ
ントリＳ（＝２）がエントリＥ２の値以下であると判断
され、次に、同期テーブル制御部１４ａはエントリＴ＝
Ｔ＋１＝３に設定する（Ｓ４）。手続実行部１５ａはブ
ロックＢ２の手続ＰT 即ちＰ３を実行する（Ｓ５）。図
示を省略したが、第３のＣＰＵ及び第４のＣＰＵもＣＰ
Ｕ２と同様に同期テーブル１３にアクセスして同様な処
理がなされ手続Ｐ４，Ｐ５が実行される。以上のように
してブロックＢ２の手続Ｐ２〜Ｐ５が並列実行される。

【００１４】(7) 手続実行部１５，１５ａ…は該当する
各手続Ｐ２〜Ｐ５の演算処理を終了すると、その終了し
たことを各同期テーブル制御部１４，１４ａ…に連絡す
る。この連絡を受けると、同期テーブル制御部１４，１
４ａ…はエントリＦ＝Ｆ＋１と設定する（Ｓ５）。従っ
て、手続Ｐ２〜Ｐ５が終了するとエントリＦ＝４に設定
される。このようにして手続Ｐ２〜Ｐ５が終了すると、
次に、エントリＦ＝Ｅ２であるどうかが判断される（Ｓ
６）。ここではＦ＝４，Ｅ２＝４であるから一致してい
るものと判断される。このように判断されると、同期テ
ーブル制御部１４はエントリＢ＝Ｂ＋１（＝３）、エン
トリＳ＝Ｆ＝０と設定してブロックＢ３の処理に進む
（Ｓ７）。 (8) そして、ブロックＢ３についても同様な処理がなさ
れ、ブロックＢ３の手続Ｐ６〜Ｐ８を実行し終了する
と、ブロックＢ４について同様な処理がなされる。そし
て、ブロックＢ４の手続Ｐ９〜Ｐ１２を実行し終了する
と、処理（Ｓ７）においてＢ＝５と設定される。そし
て、処理（Ｓ２）においてエントリＢが「４」を越えて
いると判断され、全ての処理が終了する。

【００１５】

【発明の効果】以上のように本発明によれば、実行する
１個のプログラムを複数の手続に分割し、並列実行可能
な手続をブロックという同期のための管理単位で区分し
て同期テーブルを作成するようにしたので、そのエント
リの数は、手続の数によらずに、ブロックの数と実行状
況記録部のエントリの数との和となり、同期テーブルの
エントリの数を手続の数と同数とした従来の方式に比較
して、少数のエントリで同期テーブルを実現することが
可能となり、同期テーブルを小容量のメモリで構成する
ことができるようになった。

【図面の簡単な説明】

【図１】本発明の一実施例に係る同期テーブルを用いた
手続の同期方式の構成を示すブロック図である。

【図２】図１の実施例の手続のブロック区分図である。

【図３】図１の実施例の同期テーブルの構成図である。

【図４】図１の実施例の動作を示すフローチャートであ
る。

【図５】従来の手続の同期方式の原理説明図である。

【符号の説明】

ＭＳ 主記憶装置 １１ プログラム解析部、 １２ 同期テーブル作成部、 １３ 同期テーブル、 １４，１４ａ 同期テーブル制御部、 １５，１５ａ 手続実行部

Claims (1)

【特許請求の範囲】
1. 【請求項１】 共通の主記憶装置と複数のプロセッサを
   所有するデータ処理装置において、 実行する１個のプログラムを複数の手続に分割し、並列
   実行可能な手続を同期のための管理単位であるブロック
   に区分するプログラム解析部と、 前記ブロックの数と同数のエントリを持ち、各エントリ
   には該当するブロック内の手続の数が設定される手続数
   記録部と、現在の手続の実行状況を表すエントリを持つ
   実行状況記録部とからなる同期テーブルを設定する同期
   テーブル作成手段と、 前記同期テーブルの実行状況記録部のエントリの値を手
   続の実施状況に応じて更新する同期テーブル制御手段と
   を有し、 前記複数のプロセッサは前記同期テーブルの手続数記録
   部のエントリの該当する手続をそれぞれ並列実行し、同
   期テーブル制御手段はその実行の度に前記実行状況記録
   部のエントリを更新し、そのエントリの値が前記手続数
   記録部の該当するエントリの値と一定の関係になると、
   次のエントリの各手続の実行を開始するようにしたこと
   を特徴とする同期テーブルを用いた手続の同期方式。