JPH06318191A - マルチスレッド処理方式 - Google Patents

Abstract

(57)【要約】 【目的】 本発明は、マルチスレッド処理方式に関し、
並列処理部分の終了時点でスレッドを終了させずに、待
機状態にしておき、次の並列処理を開始するときに新た
なスレッドを生成せずに待機状態のスレッドを再開させ
て並列処理を行い、並列動作の開始・終了のオーバーヘ
ッドを削減することを目的とする。 【構成】 スレッド１５と、並列呼出処理１３とを備
え、プログラム中の並列処理開始時に呼び出された並列
呼出処理１３が並列実行可能なプログラム部分を待機中
のスレッド１５があった場合にはこのスレッド１５に並
列実行可能なプログラム部分を割り当て、一方、待機中
のスレッド１５がない場合には新たなスレッド１５を生
成してこのスレッド１５に並列実行可能なプログラム部
分を割り当てて実行させ、処理終了したときに待機中の
スレッド１５として管理するように構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、複数のスレッドによっ
て並列処理を行なうマルチスレッド処理方式に関するも
のである。

【０００２】近年、スレッドと呼ぶ並列動作機構を備え
たＵＮＩＸシステムが現れており、マルチプロセッサ上
で並列処理を効率良く行なうことが望まれている。

【０００３】

【従来の技術】科学技術計算などの性能が要求される応
用プログラムにおいて、ＤＯループやサブルーチンを複
数のＣＰＵで並列に実行することによって、実行性能を
向上することが行われている。例えば図８の（ａ）に示
す２つのＣＰＵ１、ＣＰＵ２や、図８の（ｂ）に示す４
つのＣＰＵ１、ＣＰＵ２、ＣＰＵ３、ＣＰＵ４からアク
セス可能なＭＳＵ（主記憶装置）にプログラムやデータ
をロードし、各ＣＰＵ１、２、更にＣＰＵ３、ＣＰＵ４
がそれぞれ担当すべき部分のプログラムを実行する。こ
れらのシステムでは、理想的には元のプログラムを１つ
のＣＰＵで実行したときの１／２（図８の（ａ）の場
合）、１／４（図８の（ｂ）の場合）の時間でジョブの
実行が終了する。

【０００４】実際には、実行効率がプログラムの構造
（並列実行が可能なループが少ないなど）と並列処理制
御のオーバーヘッドに大きく影響を受けるので、ユーザ
プログラムを並列処理に適した構造に書き直すこと（ユ
ーザプログラムのチューニング）や、並列処理制御のオ
ーバーヘッドを減らすこと（システムのチューニング）
を行なうことによって、理想的な性能に近づけることが
できる。ここでは、並列処理制御のオーバーヘッドにつ
いて以下従来技術を説明する。

【０００５】ジョブはＣＰＵの数に見合った数の複数の
タスクからなる。ＵＮＩＸシステムでは、Ｆｏｒｔｒａ
ｎジョブをプロセス、タスクをスレッドとするマルチス
レッドプログラムとして実行する。

【０００６】ＯＳ（オペレーティングシステム）は、Ｃ
ＰＵとスレッドの割り当てを行なう。スレッドがいつ、
どのプログラム部分を並列処理するかは、実行時ライブ
ラリによって制御する。

【０００７】並列処理するプログラム部分としては、サ
ブルーチンを並列処理の単位としたり、あるいは１００
０回転するＤＯループを２５０回転ずつ４つに分割して
それぞれを並列に実行するなどする。

【０００８】いずれでも、プログラムの実行開始から、
ある部分までは逐次処理部分があり、並列処理を行った
後、再び逐次処理に戻ってプログラムを終了する。図９
の例では、（ａ）までは逐次処理を行なう。（ａ）の時
点で２個のプログラム部分（ｂ）、（ｃ）の並列処理を
開始する。そして、（ｂ）、（ｃ）の演算が両者ともに
終了した時点（ｄ）で、プログラムは再び逐次処理動作
となる。これら（ａ）から（ｄ）までの動作がループに
含まれる場合、並列動作の開始・終了処理のコストもル
ープ回転数と同じだけ増大することとなる。更に、並列
に動作するプログラム部分（ｂ）、（ｃ）の中にも、同
様に並列処理の開始・終了部分が含まれることがある。

【０００９】

【発明が解決しようとする課題】科学技術計算では、並
列処理の単位となる演算量（ＤＯループやサブルーチン
など）は、例えばＰＲＩＮＴ文などの入出力処理の演算
量に比べて１／１０００や１／１００という小さな値と
なり、従来の入出力処理と演算との並列処理とは大きな
違いがある。

【００１０】このため、並列処理単位のコストが小さい
ときでも、効率よく並列処理するためには、並列処理の
制御に要するオーバーヘッドを、並列処理される演算量
よりも、相対的に小さくする必要がある。

【００１１】並列動作の開始処理・終了処理を行なうに
は、ＯＳが備えるスレッド生成処理のシステムコールを
使用して、並列実行を行なうプログラム部分と、スレッ
ドとを１対１に対応させることが考えられる。即ち、並
列動作を開始する段階で、並列動作部分に対応するスレ
ッドを生成する。図９の例では、（ａ）の時点で、
（ｂ）、（ｃ）を並列実行するために、スレッド生成の
システムコール(pthread create)を発行し、直後に
（ｂ）、（ｃ）のそれぞれの終了を待ち合わせるシステ
ムコール(pthread join)を発行する。これにより、
（ｂ）、（ｃ）の並列処理が終わると、phread joinの
待が解除され、（ｄ）に到る。（ｄ）ではスレッドを消
去するためのシステムコール(phread delate)を発行す
る。

【００１２】このように、スレッド生成、スレッド待ち
合わせ、スレッド消去といった処理を順次行って図９の
並列処理を行なったのでは、これらの生成、消去などに
するための処理時間が並列処理を行なう時間に比して無
視できない大きさになってしまい、特にループで繰り返
す場合に大きな時間となってしまう問題があった。

【００１３】本発明は、これらの問題を解決するため、
並列処理部分の終了時点でスレッドを終了させずに、待
機状態にしておき、次の並列処理を開始するときに新た
なスレッドを生成せずに待機状態のスレッドを再開させ
て並列処理を行い、並列動作の開始・終了のオーバーヘ
ッドを削減することを目的としている。

【００１４】

【課題を解決するための手段】図１は、本発明の原理ブ
ロック図を示す。図１において、並列呼出処理１３は、
プログラムから並列処理開始時に呼び出され、並列実行
可能なプログラム部分をスレッド１５に割り当てて実行
させると共に、待機中のスレッド１５を管理などするも
のである。

【００１５】スレッド１５は、並列実行可能なプログラ
ム部分を取り込んで処理を実行するものである。

【００１６】

【作用】本発明は、図１に示すように、プログラムから
呼び出された並列呼出処理１３が並列実行可能なプログ
ラム部分を待機中のスレッド１５があった場合にはこの
スレッド１５に並列実行可能なプログラム部分を割り当
て、一方、待機中のスレッド１５がない場合には新たな
スレッド１５を生成してこのスレッド１５に並列実行可
能なプログラム部分を割り当てて実行させ、処理終了し
たときに待機中のスレッド１５として管理し、並列処理
開始・終了時のスレッド１５の生成・消去の回数を削減
するようにしている。

【００１７】従って、並列処理部分の終了時点でスレッ
ド１５を終了させずに、待機状態にしておき、次の並列
処理を開始するときに新たなスレッド１５を生成せずに
待機状態のスレッド１５を再開させて並列処理を行うこ
とにより、並列動作の開始・終了のオーバーヘッドを削
減することが可能となる。

【００１８】

【実施例】次に、図１から図７を用いて本発明の実施例
の構成および動作を順次詳細に説明する。

【００１９】図１は、本発明の原理ブロック図を示す。
図１において、主記憶装置１１は、複数のＣＰＵ１、２
・・・ｎからアクセス可能な記憶装置であって、プログ
ラムをローディングしたり、データを格納したりなどす
る記憶装置であり、図示のように、ＯＳ１２を格納した
り、並列呼出処理１３や待機中スレッド１４を格納した
り、ユーザプログラム１７やサブルーチンを格納したり
などする記憶装置である。

【００２０】ＯＳ１２は、オペレーティングシステムで
あって、全体を統括制御するものであり、ここではスレ
ッドを作成したり、スレッドを消去したりなどするもの
である。

【００２１】並列呼出処理１３は、プログラムから並列
処理開始時に呼び出され、並列実行可能なプログラム部
分を、待機中のスレット１５あるいは待機中のスレッド
１５がないときは新たに作成させたスレド１５に割り当
てて実行させたり、並列処理の終了したスレッド１５を
待機状態として管理したりなどするものである。

【００２２】待機中スレッド１４は、待機中のスレッド
１５を管理するためのものであって、ここでは管理ブロ
ック１６をリンクあるいはポイントしたりして当該管理
ブロック１６で表されるスレッド１５を管理するもので
ある。

【００２３】スレッド１５は、並列実行可能なプログラ
ム部分を取り込んで処理を実行するものであって、管理
ブロック１６によって特定されるものである。管理ブロ
ック１６は、スレッド１５を特定する情報を管理するも
のであって、ここでは下記の情報を設定して管理するも
のである。

【００２４】・スレッド識別子：ＯＳ１２にスレッド生
成を依頼したときに、ＯＳ１２から通知される当該スレ
ッドの識別子である。 ・次の管理ブロックのアドレス：管理ブロック１６の連
鎖のために使うものである。

【００２５】・実行中フラグ：通常の動作状態である
か、待機状態であるかを識別するためのフラグである。 ・呼出しに関する情報：実行すべきサブルーチンの入口
アドレスや、サブルーチンに渡すパラメタ、パラメタの
個数である。

【００２６】ユーザプログラム１７は、業務処理を行な
うプログラムであって、ここでは、サブルーチン１から
ｎを呼び出して並列処理を行なうものである。ＣＰＵ１
からＣＰＵｎは、複数のＣＰＵであって、ユーザプログ
ラム１７を並列処理するＣＰＵ群である。

【００２７】図２は、本発明の待機中のスレッドの管理
説明図を示す。図２の（ａ）は、待機中スレッド１４か
らリンクで複数の管理ブロック１６を順次管理するとき
の様子を示す。

【００２８】図２の（ｂ）は、待機中スレッドテーブル
からポインタで複数の管理ブロック１６を管理するとき
の様子を示す。以上のように、待機中スレッド１４から
リンクで複数の管理ブロック１６を管理したり、待機中
スレッドテーブルからポインタで複数の管理ブロック１
６を管理したりすることにより、並列呼出処理１３が並
列処理可能なプログラム部分をスレッド１５に割り当て
るときに、当該待機中のスレッド１５があるときにこれ
に割り当てて並列処理を行わせ（並列処理を再開さ
せ）、処理終了後に返却させて待機中のスレッド１５と
して管理し、スレッド１５の生成・消去に要する処理量
よりも、スレッド１５の待機・再開の処理量の方が少な
く、並列処理の開始・終了時のオーバーヘッドを削減す
ることが可能となる。ここで、スレッド１５を作成させ
るにはシステムコール(pthread create)を発行し、スレ
ッド１５を消去させるにはシステムコール(pthread del
ete)を発行する。一方、本願発明では、スレッド１５を
再開させるにはシステムコール(pthread cond signal)
を発行し、スレッド１５を待機させるにはシステムコー
ル(pthread cond wait)を発行する。ここで、後者のス
レッド再開・待機の処理量は、前者のスレッド作成・消
去に比し、少ないので、結果として並列処理の開始・終
了のためのオーバーヘッドを削減することができる。以
下順次詳細に説明する。

【００２９】図３および図４のフローチャートに示す順
序に従い、図１および図２の構成の動作を詳細に説明す
る。図３において、Ｓ１は、初期設定する。これは、装
置の各種初期設定を行い、動作可能な状態にする。

【００３０】Ｓ２は、並列処理指示ありか判別する。こ
れは、図６のプログラム（オブジェクト）を順次行毎に
読み込んで実行し、例えば図６の（３）の並列呼出指示
がありか判別する。ＹＥＳの場合には、Ｓ３で並列呼出
処理１３を呼出し、Ｓ４に進む。一方、ＮＯの場合に
は、並列処理指示でないと判明したので、Ｓ１０で次の
行を読み込んで実行し、Ｓ２を繰り返す。

【００３１】Ｓ４は、並列呼出しか判別する。これは、
Ｓ２で呼び出された並列呼出処理１３が現在実行しよう
とするプログラムの行の命令が並列呼出しか判別する。
ＹＥＳの場合には、Ｓ５で待機中のスレッドに空がある
か判別し、ＹＥＳのときにＳ６からＳ９の処理で待機中
のスレッド１５の処理を再開させＳ９に進み、ＮＯのと
きに新たなスレッド１５を生成し、Ｓ９に進む。一方、
Ｓ４のＮＯの場合には、並列呼出しでなく、例えばＥＮ
Ｄ ＰＡＲＣＡＬＬ（並列実行終了）であったので、図
４の（Ｃ）のＳ１５に進む。

【００３２】Ｓ６は、Ｓ５のＹＥＳで待機中のスレッド
１５があると判明したので、管理ブロックを外す（図２
参照）。Ｓ７は、Ｓ６で外した管理ブロックに、呼出し
に関する情報を設定する。

【００３３】Ｓ８は、管理ブロックの実行中フラグをＯ
Ｎにする。Ｓ９は、並列実行を開始する。以上のＳ６か
らＳ９によって、待機中のスレッド１５があった場合、
この待機中のスレッド１５の管理ブロックを外し、この
管理ブロックに呼出しに関する情報を設定すると共に実
行中フラグをＯＮにし、実際の並列処理の実行を開始す
る。これにより、新たなスレッドを再生して開始するよ
りも、待機中のスレッドによる処理を再開させるので、
処理量を削減できる。そして、並列処理が終了した場合
には、Ｓ４に戻ってＮＯとなり、図４の（Ｃ）のＳ１５
以下の並列処理終了に進む。

【００３４】Ｓ１１は、Ｓ５のＮＯで待機中のスレッド
１５がないと判明したので、管理ブロック用領域を獲得
して初期化する（図２参照）。Ｓ１２は、管理ブロック
に、呼出しに関する情報を設定する。

【００３５】Ｓ１３は、管理ブロックの実行中フラグを
ＯＮにする。Ｓ１４は、ＯＳにスレッドの生成を依頼す
る。Ｓ９は、Ｓ１４で新たに生成されたスレッドが並列
処理を実行する。

【００３６】以上のＳ１１からＳ１４、Ｓ９によって、
待機中のスレッド１５がなかった場合、新たに管理ブロ
ックを作成し、この管理ブロックに呼出しに関する情報
を設定すると共に実行中フラグをＯＮにした後、スレッ
ド１５を新たに作成した後、実際の並列処理の実行を開
始する。これにより、待機中のスレッドがない場合に新
たなスレッドを生成した並列処理を実行開始することが
できる。

【００３７】図４のＳ１５は、図３のＳ４のＮＯ、即ち
並列処理終了の場合、サブルーチンが処理を終えたか判
別する。これは、サブルーチンを実行していたスレッド
の実行中フラグがＯＦＦであれば、サブルーチンの処理
が終わったことが判明する。ＹＥＳの場合には、Ｓ１６
に進む。ＮＯの場合には、サブルーチンが処理を終える
のを待機する。

【００３８】Ｓ１６は、管理ブロックを待機中スレッド
１４に戻す。これは、Ｓ１５のＹＥＳで、並列処理を実
行したスレッド１５がサブルーチンの処理を終了したの
で、このスレッド１５を図２の待機中スレッド１４に戻
し、次の並列処理に備える。

【００３９】Ｓ１７は、並列呼出ししたサブルーチンが
全て処理を終えたか判別する。ＹＥＳの場合には、Ｓ１
８で後処理を行い、終了する。ＮＯの場合には、Ｓ１５
以降を繰り返す。

【００４０】以上によって、並列実行処理を行い、呼び
出されたサブルーチンが処理を終えたときに待機中スレ
ッド１４に戻すことを繰り返し、並列呼出しした全ての
サブルーチンが処理を終了するのを待ち合わせ、全てが
処理終了したときに後処理を行って終了する。これらに
より、並列処理を行ったスレッド１５を管理ブロックに
リンクして管理し、次の並列処理時にこのスレッド１５
を取り出して並列処理を実行（再開）させることによ
り、並列処理の開始・終了毎にスレッドの生成・消去を
繰り返す必要がなくなり、並列処理の開始・終了時の処
理量を削減してオーバーヘッドを少なくできる。

【００４１】次に、図４のＳ２１からＳ２４によって、
別スレッドによる並列実行処理について説明する。図４
のＳ２１は、別スレッドがＳ９の並列実行開始まで待
つ。

【００４２】Ｓ２２は、管理ブロックから呼出しに関す
る情報を取り出す。Ｓ２３は、ユーザサブルーチンを呼
び出す。Ｓ２４は、管理ブロックの実行中フラグをＯＦ
Ｆにする。

【００４３】以上によって、別スレッドが他のスレッド
によるＳ９の並列実行開始まで待ち、並列実行開始され
たときに管理ブロックから呼出しに関する情報を取り出
し、この情報をもとにユーザサブルーチンを呼出して処
理を依頼した後、自身のスレッドの管理ブロックの実行
中フラグを呼出し元から非同期にＯＦＦにする。そし
て、Ｓ１５に進み、呼び出されたサブルーチンが処理を
終えたときに管理ブロックを待機中スレッドに戻す。

【００４４】図５は、本発明の並列処理プログラムの動
作概念図を示す。ここで、（１）から（７）は、図６の
（１）から（７）に対応している。ここでは、図示のよ
うに、並列処理プログラムのＭＡＩＮが（１）で並列処
理開始し、スレッド１５を作成してサブルーチンＳ１の
実行と、スレッド１５を作成してサブルーチンＳ２の実
行を並列に開始する。

【００４５】並列実行開始したサブルーチンＳ１の中で
更に（３）で並列処理開始し、スレッド１５を作成して
サブルーチンＳ３の実行と、スレッド１５を作成してサ
ブルーチンＳ３の実行を並列に開始する。そして、
（７）の並列処理をそれぞれ実行して処理を終了し、
（４）でサブルーチンＳ３の並列処理をそれぞれ終了
し、サブルーチンのＳ１の処理に戻る。

【００４６】同様に、並列実行開始したサブルーチンＳ
２の中で更に（５）で並列処理開始し、スレッド１５を
作成してサブルーチンＳ３の実行と、スレッド１５を作
成してサブルーチンＳ３の実行を並列に開始する。そし
て、（７）の並列処理をそれぞれ実行して処理を終了
し、（６）でサブルーチンＳ３の並列処理をそれぞれ終
了し、サブルーチンのＳ２の処理に戻る。

【００４７】次に、（２）でサブルーチンＳ１およびサ
ブルーチンＳ２の並列処理を終了し、ＭＡＩＮに戻る。
これらの際に、並列実行を開始する（１）、（３）、
（５）で待機中のスレッド１５がないときに作成して並
列実行させ、並列実行を終了する（４）、（２）、
（６）のときにスレッド１５を待機中として管理し、次
回以降の繰り返しループなどのときに（１）、（３）、
（５）のときに待機中のスレッド１５を割り当てて使用
することにより、従来のスレッドの生成・消去をその都
度行なう場合に比し、スレッド１５を待機中に管理およ
び並列処理を再開させる本願ではその処理量を削減で
き、特に並列呼出時のオーバーヘッドを削減できる。

【００４８】図６は、本発明のプログラム例を示す。こ
れは、図５の動作概念図を実際のプログラムのイメージ
で記述したものであって、（１）から（７）、ＭＡＩ
Ｎ、Ｓ１、Ｓ２、Ｓ３は図６のそれぞれのものに対応し
ている。

【００４９】図６において、並列呼出処理１３は、並列
実行開始で呼び出され、並列実行終了で復帰するもので
あって、図５の（１）、（３）、（５）でスレッド１５
を割り当て（待機中のスレッド１５があるときはこれを
割り当て、待機中のスレッド１５がないときは新たに生
成したスレッド１５を割り当て）、サブルーチンを並列
実行させるものである。

【００５０】ＭＡＩＮは、メインプログラムであって、
並列呼出処理１３を呼び出してサブルーチンＳ１、サブ
ルーチンＳ２を並列実行させるものである。Ｓ１は、サ
ブルーチンであって、ここではＭＡＩＮから並列呼び出
されたものであり、並列呼出処理１３を呼び出して２つ
のサブルーチンＳ３を並列実行させるものである。

【００５１】Ｓ２は、サブルーチンであって、ここでは
ＭＡＩＮから並列呼び出されたものであり、並列呼出処
理１３を呼び出して２つのサブルーチンＳ３を並列実行
させるものである。

【００５２】Ｓ３は、サブルーチンであて、演算処理を
行なう中核となるものであり、サブルーチンＳ１、サブ
ルーチンＳ２からそれぞれ並列に呼び出されて並列実行
処理を行なうものである。

【００５３】図７は、本発明のスレッドとサブルーチン
の概念図を示す。図７において、プロセスは、ＯＳによ
った作成されたプロセス（ジョブ）である。

【００５４】ｔ１は、当初新たに作成されたスレッド１
である。ｔ２は、ｔ１のスレッド１の実行中のシステム
コール時に生成されたスレッドである。また、ｔ２のス
レッド２は並列実行終了時にシステムコールによってこ
こでは消滅させる（ループを形成して繰り返すときは既
述した待機中スレッド１５にしておき、次回以降この待
機中のスレッド１５を割り当て並列処理を実行（再開）
させる。

【００５５】

【発明の効果】以上説明したように、本発明によれば、
並列処理部分の終了時点でスレッド１５を終了させず
に、待機状態にしておき、次の並列処理を開始するとき
に新たなスレッド１５を生成せずに待機状態のスレッド
１５を割り当てて再開させて並列処理を行う構成を採用
しているため、並列動作の開始・終了のオーバーヘッド
を削減することができる。

【図面の簡単な説明】

【図１】本発明の原理ブロック図である。

【図２】本発明の待機中のスレッドの管理説明図であ
る。

【図３】本発明の動作説明フローチャート（その１）で
ある。

【図４】本発明の動作説明フローチャート（その２）で
ある。

【図５】本発明の並列処理プログラムの動作概念図であ
る。

【図６】本発明のプログラム例である。

【図７】本発明のスレッドとサブルーチンの概念図であ
る。

【図８】並列処理のハードウェア構成図である。

【図９】並列プログラムの構造例である。

【符号の説明】

１１：主記憶装置 １２：ＯＳ（オペレーティングシステム） １３：並列呼出処理 １４：待機中スレッド １５：スレッド １６：管理ブロック １７：ユーザプログラム

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数のスレッドによって並列処理を行なう
   マルチスレッド処理方式において、 並列実行可能なプログラム部分を取り込んで処理を実行
   するスレッド（１５）と、 プログラム中の並列処理開始時に呼び出され、並列実行
   可能なプログラム部分を上記スレッド（１５）に割り当
   てて実行させると共に、待機中のスレッド（１５）を管
   理する並列呼出処理（１３）とを備え、 プログラム中の並列処理開始時に呼び出された上記並列
   呼出処理（１３）が並列実行可能なプログラム部分を待
   機中のスレッド（１５）があった場合にはこのスレッド
   （１５）に並列実行可能なプログラム部分を割り当て、
   一方、待機中のスレッド（１５）がない場合には新たな
   スレッド（１５）を生成してこのスレッド（１５）に並
   列実行可能なプログラム部分を割り当てて実行させ、処
   理終了したときに待機中のスレッド（１５）として管理
   するように構成したことを特徴とするマルチスレッド処
   理方式。