JP2005284749A - 並列処理コンピュータ - Google Patents

Abstract

【課題】実行環境切換の負荷の発生しない並列処理コンピュータを提供する。
【解決手段】排他的に実行可能なスレッドを実行待ちキューに入れるスレッド起動制御部、及び、複数のスレッド実行ユニットと、複数のレジスタを持つ複数のレジスタファイルと、前記実行待ちキューの実行待ちスレッドが実行される前に、空きレジスタファイルを割り付ける先行ロードユニットと、前記スレッド演算ユニットのうちアイドル状態のものがある場合、前記実行待ちスレッドを取り出し、前記アイドル状態のスレッド演算ユニットに割り付け、前記レジスタファイルを前記アイドル状態のスレッド演算ユニットに結合して並列に実行させるスレッド演算ユニット割り付け・起動ユニットとを含むスレッド実行制御部を備える。
【選択図】図１

Description

本発明は、並列処理コンピュータに関するものであり、より詳細には、複数のスレッドを同時並列に実行する並列処理コンピュータに関するものである。

従来のオンチップ・マルチプロセッサでは、ノイマン型の逐次処理がその主体であるため、複数のプロセッサを内蔵したマルチプロセッサであってもプロセッサ資源数を超えた複数の内部演算処理や外部割り込み（イベント）処理を非同期に行うためには、現在走行中のプログラムの実行を中断（プリエンプト）させてプロセッサの実行環境を切り替えるということが頻発する。この実行環境は、例えば、各プロセスごとに生成されたプロセス制御ブロック（ＰＣＢ）などの制御ブロックとしてメモリに格納され、実行時にレジスターなどの非常に高速なメモリにロードされるものであるが、この制御ブロックは、各プロセスで使用されるべき、各レジスタの値、再開時に実行すべき命令のアドレス、メモリ管理用情報、及び入出力関連情報など多くの情報を含むものである。従って、このための制御が複雑となり、オーバーヘッドが大きく、プロセッサの稼働率を高く保つことが困難である。また。非同期並列処理を記述するプログラムの構成が複雑となり、効果的な並列処理プログラムの記述が一般に困難である。

現在、このような問題を解決しようとする方式として、複数のスレッドを同時実行させるマルチスレッド実行方式が種々考案されている。その中で、複数のスレッドを命令レベルで混在させて同時に実行させる複数スレッド混在実行（Simultaneous Multithreading；SMT）方式によるマルチプロセッサが提案されている。ＳＭＴ方式は従来のスーパースカラー・プロセッサ構成法を生かすことができるので開発コストが安くすむという利点がある。しかし、ＳＭＴにおけるスレッドのコードは従来の一般的なコードであり、本願発明のような「走りきり排他実行」タイプのスレッドではく、実行中断を回避する仕組みがないため、一般に実行中断が生じる。スレッドの実行中にＩ／Ｏやメモリアクセスなどにおいてレイテンシ即ち待ち時間が生じ、そのために後続命令の実行が遅れるような場合にはそのスレッドの実行が中断される。実行中断されたスレッドは、プロセッサ資源が空いた時点で実行が再開（レジューム）される。このとき、実行中断されたスレッドの実行状態を退避し、実行再開するスレッドの状態を回復するという処理が必要となり、基本的にはノイマン型逐次実行プロセッサの場合と同様にスレッド間の実行環境切り替えという問題が避けられない。

実行中断はメモリアクセスや外部との交信などでプロセッサをアイドル状態にしているスレッドに対して行われので、いつ実行が中断されるかはスレッドにとっては見えない（即ち、不意打ちを食らう構造である）。このため、スレッド切り替えの予測が不可能である。アイドル状態のプロセッサに実行待ちスレッドを割り付けるのはスケジューラ（即ちディスパッチャー）の仕事であり、アイドル状態の検出はハードウェア機構に依存する。

また、従来のコンピュータにおいて、割り込み処理の効率化を目指した多くの割り込み処理技術が開示されている。例えば、本発明者の雨宮他による割り込み処理技術が開示されている（特許文献１を参照されたい。）。この従来技術は割り込みを所定数保持しておき一括して割り込み処理する技術であるが、このような割り込み処理技術は、既存のプログラムコードをそのままで稼動できるという利点はがあるが、その構成上、重要な優先度の高い割り込み処理もある程度の時間待たされてしまったり、ハードウェア構成が複雑化したりするなどのデメリットがある。
特開２００２−３４２０９３（段落０００６−０００８。図１）

上述したように、従来のコンピュータでは、実行中断の際にプロセッサ環境を切り替えるという操作が避けられないため、以下のようなスレッド切り替えのオーバヘッドが問題となり、プロセッサの稼働率を高く保つことが困難である。
1.いつの実行時点でプリエンプション即ち制御を横取りされるか予測できないので、現実行環境の情報をすべて退避する必要があり、無駄なデータまで退避及び回復の対象となる。
2.演算器とレジスタが固定化されているため、実行中のスレッドが用いているレジスタは実行中断が起こるまでは、他のスレッドで使用することができない。即ち、予測不可能なので実行環境の切り替えを前もってやっておくことができない。

本発明による並列処理コンピュータは、複数のスレッドを同時並列に実行する並列処理コンピュータであって、
排他的に実行可能（即ち、一旦、スレッドが実行を開始すると途中で他のスレッドの処理を待ったり、割り込み処理などで演算器の制御権を失ったりすることなく最後まで走りきることが可能、換言すれば、他の干渉を受けることなく排他的に最後まで完了することが可能）なプログラム断片であるスレッドのそれぞれが実行可能か否かを判定し、実行可能であると判定されたスレッドを実行待ちスレッドとして実行待ちキューに入れる（即ちエンキューする）スレッド起動制御部（ＴＡＣ）と、
先行ロードユニット、スレッド演算ユニット割り付け・起動ユニット、複数のスレッド演算実行ユニット、及び、複数のレジスタを持つ複数のレジスタファイルを含む、スレッド実行制御部（ＴＥＣ）と、
を具える並列処理コンピュータであり、
前記先行ロードユニットが、前記実行待ちキューに収容されている前記実行待ちスレッドが実行される前（好適にはキューの先頭部分にスレッドが配置されたとき、或いは先頭の近くに配置されたとき）に、この実行待ちスレッドに対して、前記複数のレジスタファイルのうちの空きレジスタファイルを割り付け、この実行待ちスレッド用の初期データ（即ち、実行環境であり、当該スレッドが開始から終了まで走り切ることができるデータである。）をメモリから前記割り付けたレジスタファイルにロードし、
前記スレッド演算ユニット割り付け・起動ユニットが、前記複数のスレッド演算ユニットのうちアイドル状態のものがある場合、前記実行待ちキューの先頭から前記実行待ちスレッドを取り出し、この実行待ちスレッドを前記アイドル状態の前記スレッド演算ユニットに割り付け、この割り付けられた実行待ちスレッド用の初期データがロードされている前記レジスタファイルを前記アイドル状態の前記スレッド演算ユニットに結合して、この実行待ちスレッドを起動し、前記複数のスレッド演算実行ユニットが、前記起動されたスレッドを同時並列に実行する、
ことを特徴とする。
本発明によれば、演算ユニットの制御を得て実行を開始した各スレッドは、制御を失うことなく最後まで走り切ることができるようになり、そのため途中で実行環境切替の負荷が全く発生しないことになり、コンピュータ全体としての処理能力が顕著に向上する。即ち、各スレッドが排他的に実行可能になるように、各演算ユニットに大容量かつ高速アクセス可能なレジスタファイルをそれぞれ設けて当該スレッドに必要なデータを全てレジスタにロードし、スレッド実行中はレジスタ内のデータのみを使用することによって、実行環境切替の発生を伴うＩ／Ｏ待ちやメモリアクセスを回避することか可能となる。

また、本発明による並列処理コンピュータは、
前記複数のスレッド演算ユニットは、それぞれ専用の命令キャッシュに結合され、
前記並列処理コンピュータは、前記実行待ちスレッドが起動される前に当該スレッドのコードを前記メモリから前記命令キャッシュにロードする第１のメモリ管理部をも具える、
ことを特徴とする。
本発明によれば、スレッド起動前に命令コードが必ずキャッシュにロードされているたため、メモリから命令コードを取り出す時間の節約になり、コンピュータ全体の処理速度即ちスループットをさらに向上させることができるようになる。

さらにまた、本発明による並列処理コンピュータは、
前記並列処理コンピュータがデータキャッシュをも具え、
前記先行ロードユニットは、前記メモリへのアクセスの前に、前記データキャッシュへアクセスし、ヒットした場合はそのデータキャッシュから前記実行用データをロードする、
ことを特徴とする。
本発明によれば、データキャッシュを設けたことによって、先行ロードユニットの処理の円滑化を図ることができ、コンピュータ全体の処理速度即ちスループットをさらに向上させることができるようになる。

さらにまた、本発明による並列処理コンピュータは、
前記データキャッシュは複数のバンクを含み、
前記並列処理コンピュータは、
各スレッドを実行するときに、各スレッドに先行するスレッドによって使用された前記データキャッシュのバンクがある場合は、そのバンクを使用するよう制御する第２のメモリ管理部をも具える、
ことを特徴とする。
本発明によれば、実行の局所性を反映したデータキャッシュアクセスが可能となり、最終的にはコンピュータ全体の処理速度即ちスループットをさらに向上させることができるようになる。

さらにまた、本発明による並列処理コンピュータは、
前記スレッド起動制御部は、同期制御メモリを含み、
前記同期制御メモリは各インスタンスごとにブロックを持ち、この各ブロックには各スレッドごとにスレッド起動同期用カウントフィールド及び先行スレッド数が予め収容されている先行スレッド数フィールド（fan-in）が設けられ、
前記スレッド起動制御部は、前記スレッド起動同期用カウントに初期値として先行スレッド数フィールドにセットされた先行スレッド数をセットし、その値を当該スレッドに対する起動通知を受けるたびに１ずつ減少させゼロになったときに実行可能になったと判定する、
ことを特徴とする。
本発明によれば、スレッドの実行順序の制御を簡易かつ効率的に行うことが可能となり、最終的にはコンピュータ全体の処理速度即ちスループットをさらに向上させることができるようになる。

さらにまた、本発明による並列処理コンピュータは、
前記同期制御メモリの各ブロックは、ロック用フラグをも持ち、
前記複数のスレッド演算実行ユニットは、前記ロック用フラグをロックする命令及び前記ロック用フラグをアンロックする命令をサポートする、
ことを特徴とする。
本発明によれば、後述するようなTest-and-lock命令やUnlock命令によって、各スレッドの排他継続を制御し、排他制御を簡易かつ効率的に行うことが可能となり、最終的にはコンピュータ全体の処理速度即ちスループットをさらに向上させることができるようになる。

さらにまた、本発明による並列処理コンピュータは、
さらに、共有資源にアクセスできる排他制御スレッドと、
前記排他制御スレッドへの排他継続を制御する排他継続制御機構と、
前記共有資源への排他アクセスを制御する排他アクセス制御手段と、
を具える、ことを特徴とする。
本発明によれば、Ｉ／Ｏアクセスや外部イベントの処理を伴うような共有資源への排他アクセスを簡易かつ効率的に行うことが可能となり、最終的にはコンピュータ全体の処理速度即ちスループットをさらに向上させることができるようになる。

本発明は、従来のプロセスをスレッドとよぶ排他的に実行可能なプログラム断片に細分化し、複数のスレッドを同時並列に走行させて並列処理する並列処理コンピュータの方式である。本方式では、スレッド間の実行の同期を継続概念によって制御し、スレッドレベルで並列実行するプロセッサを１チップで実現する。内部演算処理と割り込みなどの外部イベント処理を全てスレッドで統一し、スレッドレベルの非同期並列実行を可能とする。
本発明は、上記のような従来のオンチップ・マルチプロセッサのもつ問題点を解決し、プロセッサの稼働率を高く保ち、かつ内部演算処理と外部割込み処理を統一的に行う並列処理コンピュータをオンチップで実現する方式に関するものである。
本発明の方式では、スレッドとは他からの干渉を受けずに走りきるプログラム片と定義する。ひとつのプログラムは複数のスレッドで構成される。スレッドの間には実行の順序（半順序）関係が与えられ、この順序に従ってスレッドの実行が制御される。あるスレッドの次に実行されるスレッドをそのスレッドの継続スレッドと、よぶ。またあるスレッドの前に実行されるスレッドを先行スレッドとよぶ。先行スレッドの数をFan−inとよび、継続スレッドの数をFan-outとよぶ。あるスレッドの実行終了時（あるいは実行途中において）継続スレッドを起動するとき、その継続スレッドに対して起動通知が発行される（起動通知はFan-out分だけ発行される）。あるスレッド実行は、そのすべての先行スレッドから起動通知を受け取ったとき（Fan-in分だけの起動通知を受け取ったとき）に可能となる。スレッド間の実行順序は半順序なので、そのすべての先行スレッドからの起動通知を受け取り実行可能となるスレッドは複数個存在し得る。したがって、十分な数の演算ユニットがあればその実行可能なスレッドは同時並列に実行することができる。これをマルチスレッド実行とよぶ。

ユーザ記述のプログラムのみならず、外部割込み処理プログラムや通信処理プログラム、ＯＳカーネル・プログラムもすべてスレッドの集合体として与えられる。高級言語で書かれたプログラムはコンパイラによってスレッドに分割され、スレッドの集合体（マルチスレッドとよぶ）として与えられる。
本発明の並列処理コンピュータ（以下、単にプロセッサと称することもある。）は複数個のスレッド演算ユニットと複数個のレジスタファイルを持ち、スレッド集合体として与えられるプログラムをマルチスレッド実行する。個々の演算ユニットには実行可能なスレッドが割り当てられ、割り当てられたスレッドを他からの攪乱を受けずに排他的に逐次実行する。スレッド実行の際にはメモリアクセスは起こさず、すべてレジスタ・アクセスの演算である。このことによりスレッドを高速かつ排他的に実行することができる。スレッドの実行に必要な初期データ（実行環境）はスレッドの実行に先立って使用するレジスタにメモリからあらかじめ読み込んでおく。継続スレッドヘ引き継ぐべきデータ（すなわち実行環境）は継続スレッドヘの起動通知を発行する直前にメモリに書き込む。

プロセッサは、個々のスレッドに対して実行可能条件（Fan-in分だけの起動通知の到着）をチェックする起動制御ユニット（TAC：Thread Activation Control Ｕnit）を持つ。TAC内にはまだ起動通知を受けていない先行スレッドの個数を保持する高速の起動制御メモリ（ACM：Activation Control Memory）を内蔵する。また、起動条件が整い（起動通知未受信数＝0）実行可能となったスレッドを保持する実行待ちスレッド・キュー（Ready Thread Queue）を持つ。
また、プロセッサは個々の演算ユニットの動作とは独立してメモリ・レジスタ間のデータ転送を行うロード／ストア制御ユニット（LSC：Load/Store Control Ｕnit）を持つ。LSCは、実行待ちキューの先頭部分に移動し実行間近となったスレッドに対して空きレジスタファイルを確保し、その実行環境（データ）をロードする。
レジスタファイルの数は演算ユニットの数より多い（1.5倍〜2倍程度）。また個々のレジスタファイルは従来のプロセッサより多くのレジスタを持つ。これはスレッド実行がレジスタ・アクセスのみで行われるため、スレッド実行のステップ数を多くする（粒度を高くする）ことができるようにするためである。
このマルチスレッド実行によって、演算ユニットは現実行中のスレッド実行が終了すると直ちに実行待ちスレッドが新たに割り当てられ、また同時にそのスレッドの実行環境が整っているレジスタファイルも割り当てられるので、間髪を入れずに次のスレッドを実行することができ演算ユニットの稼働率を高く保つことができる。

以下に本発明の並列処理コンピュータの特徴を整理して示す。
（1） スレッド間の実行の同期を実行継続概念によって内部演算処理ならびに外部割込み処理をすべてスレッド処理で統一し、スレッドレベルの非同期並列実行を行う。
（2） 複数のスレッド演算ユニットと複数の大容量レジスタファイルをもち、複数のスレッドを同時並列に実行する、
（3） スレッド実行において割り付けられたスレッドは、スレッド演算ユニットとレジスタファイルを占有し、途中で実行中断を起こすことなくスレッド実行が完了するまで走りきる。スレッドの演算はレジスタのみを用いメモリヘのアクセスはない。
（4） スレッド実行に際して、スレッド演算ユニットと大容量レジスタファイルとの結合を動的に行い、スレッド実行が終了するとそのスレッド演算ユニットおよびレジスタファイルを解放する。（スレッド演算ユニットおよびレジスタファイルの半固定割り付け）
（5） スレッド間の実行順序制御を行うためのスレッド同期カウンタを内蔵したスレッド起動制御ユニットを持つ。
（6） 起動条件（同期）が整い実行可能となった実行待ちスレッドを保持するキューをもち、スレッド実行が終了し解放されたスレッド演算ユニットに実行待ちスレッドを割り付ける。
（7） ロード／ストア制御ユニットをもち、実行待ちキューの先頭部分にある実行待ちスレッドに対して、その実行に先立って。空きレジスタファイルを割り付けて実行環境（初期データ）をメインメモリからそのレジスタファイルに読み込む（実行環境の先行設定）。またスレッド実行終了後必要なデータをメインメモリへ書き込む。
（8） 外部割込み処理などにおいて生ずる共有資源への排他アクセス制御機能（臨界領域制御機能）を持つ。
（9） 複数モジュールからなるデータキャッシュをもち、種々のデータキャッシュ・モジュールヘのアクセスをスレッド環境（実行インスタンス）ごとに行う。このことによって、実行の局所性を反映したデータキャッシュアクセスを可能とする。
（10）以上の機能を持つプロセッサを１チップ上に構成する。

以降、諸図面を参照しつつ、本発明の実施態様を詳細に説明する。
図１は、本発明による、細粒度マルチスレッド実行可能な並列処理コンピュータの一実施態様を示すブロック図である。
本発明による並列処理コンピュータ１０は、スレッド起動制御部１２（TAC：Thread Activation Control Ｕnit）、スレッド実行制御部１４（TEC；Thread Execution Control Ｕnit）、メモリアクセス制御部１６（MAC: Memory Access Controller）、およびメインメモリ１８（MEM；Main Memory）、入出力制御部２０、及び、通信制御部２２を具える。ＴＡＣ１２はスレッド間同期管理用の高速メモリＡＣＭ１２ａ（Activation Control Memory）を持ち、スレッド実行の起動を制御する。ＴＥＣ１４は複数のスレッド演算実行ユニット１４ａ（ＥＵ；Execution Ｕnit）と複数のレジスタファイル１４ｂ（Register File）をもち、個々のスレッド実行を並列に行う。ＴＡＣ１２とＴＥＣ１４の間は実行待ちスレッドキュー１３（Ready-Thread Queue）を通してつながれ、ＴＡＣ１２は実行可能となったスレッドコードを実行待ちキュー１３の後尾に置く。ＴＥＣ１４はキュー１３の先頭にある実行待ちスレッドコードを取りだす。各ＥＵ１４ａはそれぞれ命令キャッシュ１４ｃを持ち、実行中のスレッドコードを保持する。また。レジスタファイル群１４ｂとメインメモリ１８の間には複数バンクのデータキャッシュ１６ａを持ち、データアクセスの高速化を図る。メモリアクセス制御部１６はメモリ１８からレジスタファイル１４ｂヘのデータの読み込み、およびレジスタファイル１４ｂからメモリ１８へのデータの書き出しを制御する。また、ＭＡＣ１６は、メモリ管理部１６ｂ、ロード／ストア制御ユニット１６ｃ、及びＤＭＡ制御部１６ｄをも具える。

スレッド実行制御部１４内の先行ロードユニット１４ｄ（Pre−load Ｕnit）は、実行待ちキュー１３の実行待ちスレッドコードに対してその実行前にあらかじめ空きレジスタへのデータの読み込みを制御する。また、スレッド実行制御部１４は、スレッド演算ユニット（ＥＵ）割り付け・起動ユニット１４ｅ（これについては後で詳細に述べる。）をも具える。

図２は、マルチスレッドプログラムの構造の一例を示す説明図である。本実施態様では、言語処理系（例えばコンパイラなど）によって既存のプログラムコードが図２のような構造に変換され、プログラムローダによってメモリにロードされているプログラム（これをスレッド化されたプログラム、あるいは単にスレッドプログラム（Threaded-program）であることを前提とする。図２に示すように、プログラムＡはスレッドコード（Thread−code）Thread1,…Thread６からなるスレッドプログラム（Thread−program）の例である。このプログラムは実行中のスレッドプログラム・インスタンスから起動され、（このとき、まずこのスレッドプログラム実行のためのインスタンスが生成される。インスタンスについては後で詳細に述べる。）、Thread１が実行される。Thread１の実行中Thread１内の継続命令（continue）が実行されると、起動シグナルがThread１とThread２とThread３に伝わる。Thread２のFan-in値は1なのでThread２は他からの起動シグナルを待つことなく直ちに実行される。Thread２の実行中に継続命令（continue）が実行されその起動シグナルがThread３とThread４に伝わる。Thread３のFan-in値は２なのでThread１とThread３からの起動シグナルの到着によって（同期がとられ）実行が開始される。以下同様にしてThread４とThread５が実行されていく。最後にThread６の実行中に他のスレッドプログラムへの継続命令を発行して、計算がそのスレッドプログラム（のインスタンス）へ引き継がれる。Thread６の実行が終了するとこのスレッドプログラムの実行インスタンスは終了し、このインスタンスは消滅する。ここで、スレッドの起動は起動シグナルによって制御され、並行的な実行となることに注意されたい。

プログラムＡは、マッピングされ命令メモリＢ内に展開されるが、個々のスレッドプログラムのスレッドコードとスレッドコード間のスレッドリンク情報Ｃ（先行スレッド・継続スレッド間の関係、Fan-in値、スレッドコードのエントリーアドレス）は、図に示すようにメモリ内では区別して置かれ、個々のスレッドリンク情報はこのプログラム（Treaded-Program）のインスタンス実行が開始されるときにそのインスタンスに対応するＡＣＭ（Activation Control Memory）ブロックＤの各スレッドエントリーフィールドにロードされる。即ち、スレッドリンク情報Ｃは、インスタンス生成時にＡＣＭインスタンスブロックＤの各スレッドエントリフィールドに上から順にセットされる。

図３は、本発明による並列処理コンピュータにおけるマルチスレッド実行制御部（ＴＥＣ）およびメモリアクセス制御部（ＭＡＣ）の詳細な実施態様を示すブロック図である。ＴＥＣはｎ個のスレッド演算実行ユニット３０ａ（ＥＵ；Tread Execution Ｕnit）およびｍ個のレジスタファイル３０ｂからなる。ここで、ｍ＞ｎ（たとえばｍ／ｎ＝1.5〜2）である。さらに命令キャッシュ３０ｃ（Ｉ−Cache）とデータキャッシュ３０ｄ（Ｄ−Cache）を持つ。Ｉ−Cacheは個々のＥＵ毎にもち、Ｄ−Cacheは複数ユニットで構成する。実行可能なスレッドコード（具体的にはエントリーアドレス）は実行待ちスレッドキュー３２に繋がれている。以下、実行可能なスレッドを実行待ちスレッドとよぶ。ＥＵ割り付け・起動ユニット３４（ＥＵ Allocate and Trigger Ｕnit）はＥＵのどれかがアイドルになったときキュー３２の先頭からスレッドを取り出し、アイドル状態のＥＵ３０ａをこのスレッドに割り付けて起動する。このとき後述するようにこのスレッドの実行環境（実行に必要なデータ）はすでにいずれかのレジスタファイル３０ｂにロードされているので、そのレジスタファイル３０ｂとＥＵ３０ａを結合して起動する。

ＥＵ３０ａでのスレッド実行が終了し使用されていたレジスタファイル３０ｂが解放されたとき、先行ロードユニット３６（Pre−Load unit）はキュー３２中の先頭に近づいている実行待ちスレッドに対応する実行環境データをその開放されたレジスタファイル２０ｂにロードし、いつでもそのスレッドの実行が開始できるように準備する。この先行ロード操作により、アイドルＥＵが生じたときに即座にそのＥＵにキュー３２先頭の実行待ちスレッドを割り付けて実行を開始することができる。
先行ロードユニット３６によるデータのロードおよびスレッド実行後のデータのストアに際しては直接メモリへの読み書きを行う前にデータキャッシュ３０ｄ（Ｄ−Cache）へのアクセスが行われる（これは通常のメモリへの読み書きにおけるデータキャシュアクセス制御と同じである）。命令キャッシュ３０ｃ（Ｉ−Cache）へのアクセスについては、実行待ちスレッドのコードがメモリからＩ−Cacheヘロードされ、以後そのスレッド実行中は命令キャッシュ３０ｃに対して命令コードの読み出しを行う。データキャッシュ３０ｄ、命令キャッシュ３０ｃ及びメモリへのアクセス制御はロード／ストア制御ユニット３８（Load／Ｓtore Control Ｕnit）がメモリ管理ユニットＭＭＵ４０を介して行う。

図４は、本発明による並列処理コンピュータにおける先行スレッドから継続スレッドへの制御移行およびデータ引渡しの機構を示す説明図でる。図に示すように、先行スレッドから継続スレッドヘの制御移行には次の２つの場合がある。
（1）継続スレッドのFan-inが1の場合
この場合は。先行スレッドＡで継続命令（continue）が実行され。継続スレッドＢへの起動シグナルが発行されたとき、その制御は直ちに継続スレッドＢに移行する。具体的には、継続スレッドＢのコードエントリー・ポインタを実行待ちキュー（Ready−Tｈread Queue）に繋ぎこむ。
（2）継続スレッドのFain-inが2以上の場合
図ではFain-inが２の場合について示しているが３以上の場合も同じである。図は、先行スレッドＡでの継続命令の実行および外部からのイベントによって、あるいはスレッドＡの継続命令実行およびＢの継続命令実行によって、スレッドＢへの起動シグナルが到着したときにスレッドＢの起動条件（同期）が整いスレッドＢは実行可能となることを示している。起動条件（同期）のチェックはスレッド起動制御部（TAC）で行われる。

ＴＡＣに同期制御メモリ（ACM）を設ける。図５は、本発明による並列処理コンピュータにおけるＡＣＭの構成例を示すメモリマップ図である。ＡＣＭは多数のブロックで構成される。ＡＣＭブロックは前述したようにインスタンスが生成されるごとに割り付けられ、そのインスタンスの実行が終了すると解放される。インスタンス割り付けに際して、ＡＣＭブロックにはそのインスタンス実行のスレッドプログラム内各スレッドコードのリンク情報（スレッドコードのエントリーアドレスおよびFain-in値）が初期値としてロードされる。
ＡＣＭブロックヘのアクセスは［インスタンス＋スレッドエントリー］によって行われる。ここで、［インスタンス＋スレッドエントリー］はインスタンス番号とスレッド番号を上位・下位フィールドに連結した値を表し、インスタンス番号をＡＣＭブロックの先頭アドレス、スレッド番号をそのＡＣＭブロック内局所エントリーアドレスとする。ＡＣＭ内のスレッドエントリーはスレッド番号に対応してＡＣＭブロック内の局所アドレスとして与えられる。（スレッド番号はコンパイル時に当該スレッドプログラムを生成するときに決定されていることに注意されたい。）各スレッドエントリーは、排他制御用のロックビット（ロック用フラグ）、スレッド起動のための同期カウント（Sync−count），Fain-in値、スレッドコードエントリー（Code-entry）の各フィールドで構成される。なお、各ＡＣＭブロック先頭のBase addressは仮想メモリ管理のためのベースアドレスとして用いられ、当該インスタンス実行時のデータ領域の先頭アドレス（物理アドレス）を保持する。

図６は、本発明による並列処理コンピュータにおけるＴＡＣの動作の一例を示す説明図である。同期カウントは初期値としてスレッドのFan-in値（先行スレッド数）がセットされ、当該スレッドヘの起動シグナルが到着するごとに1減じられる。1減じた際に同期カウント＝0となれば、当該スレッドの起動条件が整ったことになり、このスレッドを実行可能スレッドとして実行待ちキュー（Ready-Thread-Queue）につなぎ込む。当核スレッドヘの起動シグナルの発行は、他の（あるいは自）スレッド実行中に継続命令（continue）が実行されたときであり、このときこの継続命令のオペランドとして与えられている継続スレッド（すなわち当惑スレッド）の番号および現実行中のインスタンス番号［Instance ＋ Thread-entry］が（ＥＵからＴＡＣに対して）発行される（インスタンス番号は他インスタンスの番号を指定することもできる。）。他インスタンス番号を指定した場合は、処理がそのインスタンスヘ継続することになる。これを受け取ったＴＡＣは［Instance ＋ Thread-entry］によってＡＣＭ内の当該スレッドエントリーの同期カウントを1減じる。なお、自スレッドへ継続するときは当該スレッドの実行を排他制御する必要が生じる場合があるが、このときはロックビットを用いて排他制御する（詳細については後述する）。

図７Ａは、本発明による並列処理コンピュータがサポートする継続命令の機能を示す説明図である。
（1）Direct-Continue（直接継続）命令
この命令は継続スレッドのFan-inが1の場合に用いる命令である。
この命令の実行では、継続スレッドに対応するＡＣＭブロック内スレッドエントリーから（同期カウントの値は変更せずに）直ちにスレッドコードエントリーを実行待ちスレッドキューにつなぎこむ。あるいは、Direct−Continueのオペランドに継続スレッドのコードエントリーを直接埋め込んでおき、ＡＣＭブロックへのアクセスを行わずに実行待ちスレッドキューにつなぎこむ（図４ではこの場合を示している）。
（2）Continue（継続）命令
この命令はFan-inが２以上の通常の継続スレッドへ制御移行する場合に用いる命令である。この命令の動作ステップは次のとおりである。
1. 継続スレッドに対応するＡＣＭブロック内スレッドエントリーの同期カウントを1減じる。
2. もし同期カウント＝0ならば、そのスレッドコードエントリーを実行待ちスレッドキューにつなぎこむ。

図７Ｂは、本発明による並列処理コンピュータがサポートする継続命令の機能を示す説明図である。
（3）Wait-and-Continue命令
この命令は、排他制御等で臨界領域（Critical Region）やセマフオーの管理に用いる命令である（排他制御の詳細は実施例６で述べる）。この命令の動作ステップは次のとおり。
1.もし、継続スレッドに対応するＡＣＭブロック内スレッドエントリーの同期カウント＝0ならば同期カウントがfan-in値にリセットされるまでウェイトする（busy wait）
2.同期カウントを1減じる。
3.もし同期カウント＝0ならば、そのスレッドコードエントリーを実行待ちスレッドキューにつなぎこむ。
（4）Reset-and−Continue命令
この命令も臨界領域（Critical Region）やセマフオーの管理に用いる命令である（排他制御の詳細は後述する）。この命令の動作ステップは次のとおりである。
1.継続スレッドに対応するＡＣＭブロック内スレッドエントリーの1ock−bitを0ff（unlocked）にし、同期カウントをfan-in値にリセットする。
2.継続スレッドの同期カウントを1減じる。
3.もし同期カウント＝0ならば、そのスレッドコードエントリーを実行待ちスレッドキューにつなぎこむ。

図８は、本発明による並列処理コンピュータにおけるスレッド間の制御移行及びデータ引渡しの動作を示す説明図である。これば、ふたつのスレッドThread１およびThread２からThread３へ継続する場合にThread１内のレジスタr5、ｒ7のデータ、およびThread２内のレジスタr５、ｒ６のデータをThread３へ引き渡す例を示している。これらのスレッドはいまインスタンスiで実行されているとすると、インスタンスiに割り付けられているデータ領域にアクセスすることができる。なぜなら、このデータ領域はインスタンス生成時にこのインスタンス実行に必要な領域が確保され、ＡＣＭブロックiのベースアドレス値として与えられているからである。Thread１では、レジスタr5およびr7の値をインスタンスiのデータ領域中のxおよびx＋1番地にストアする。また、Thread1では、レジスタr5およびr6の値をインスタンスiのデータ領域中のyおよびy＋1番地にストアする。Thread３では、同じくインスタンスiのデータ領域中のx、ｘ＋1、y、y＋1番地からレジスタｒ1、r2、ｒ3、ｒ4にそれぞれロードする。かくして、Thread1およびThread２からThread３へのデータ引渡しが行なわれる。

次に、本発明における並列処理コンピュータにおける並行プロセス処理機構の一実施態様を示す。これは、複数プロセス（あるいはサブルーチンや関数）を動的に並列処理する機構である。サブルーチンや関数などあるまとまった単位のプログラムコードの実行は一般にプロセスとよばれ、実行される個々のプロセスは特にインスタンスとよばれている。並列処理環境ではプロセス実行の概念は不可欠なものである。たとえば、オペレーティングシステムなど一般の並列処理を実現するためには、同一のプログラムコードを共有しつつ異なる処理データや資源に対して同時並行的な処理ができなければならない、この処理概念は一般に並行プロセスの処理とよばれる。

本発明では、あるまとまったプログラム単位はスレッドプログラムとして扱うので、動的に起動されたプロセス（あるいは関数）をインスタンスとよび、そのプログラム実行のことをインスタンスの実行とよぶ。本方式ではサブルーチンや関数も並列処理の対象とするので、これらの実行も含めて統一してインスタンスとよぶことにする。
あるインスタンスの実行中にそのインスタンスは他のインスタンスを起動する。起動するインスタンスを親インスタンス（あるいはcaller）とよび、起動されたインスタンスを子インスタンス（あるいはcallee）とよぶ、並行インスタンスの処理では、複数のインスタンスが起動され、並行して実行される。このとき実行中のインスタンスは互いに干渉を起こさず独立に実行できなければならない。このため個々のインスタンスの実行環境を区別し、独立に管理することが必要である。実行中のインスタンスは子インスタンスを起動する際、その子インスタンスの実行に先立って、実行環境（作業用のデータエリアなど）を動的に生成し、実行が終了するとその実行環境は消滅する。

このような並行インスタンスの実行を以下のようにして制御する。
ルーチン（あるいは関数）呼び出しの制御
図９は、本発明における並列処理コンピュータがサポートするルーチン（関数）起動のマクロ及び引数の引渡し法を示す説明図である。
まずマクロ命令callを用いて呼び出し制御の概略を説明する。以下では、呼び出すルーチン(あるいは関数)をcaller、呼び出されるルーチン（あるいは関数）をcalleeとよぶ。マクロ命令callはつぎのように与えられる。
Call func,param,curins,cont,retval
パラメータは
func:callee instance + callee function name（注：＋記号は連結演算）
param：パラメータスロットアドレス
curins：callerインスタンス
cont：caller側継続スレッド
retval：caller側の戻り値受け取りスロットへのポインタ

(1)callee function nameはcalleeの先頭スレッドのコードアドレスとしてあたえられる。
Funcにはcalleeインスタンスとcallee function nameがパックされている。calleeの実行はこの先頭スレッドより開始される。
(2)引数データはcallee側のデータエリアに書き込まれている。そのアドレスはparameter−slot addressとして与えられ、calleeに引き渡される。
(3)curinsはcallerのインスタンスで、これはcalleeからcallerへの戻りのために用いられる。
(4)Ｃontはcalleeから戻ったときに起動されるスレッドコードのエントリーである。
(5)Retvalはcaller側に用意された戻り値受け取りスロットのアドレス。callee側で戻り値をこのスロットに書き込む。

call命令の動作は次のとおりである。
１．呼ばれ側スレッドプログラムの実行に際して子インスタンスが生成される。インスタンスの生成では、ＡＣＭブロックを割り付け、そのスレッドプログラムを構成するスレッドコードの初期値がＡＣＭブロックの各スレッドエントリーにロードされる。（各スレッドコードの初期値は実施例1に述べたように、プログラムローダーによってスレッドテーブルに設定されている。）
ハードウェア実現上は、次の操作を行うnew-instance命令（newins）を用意する。
A. ＡＣＭの空きブロックを確保し、確保したＡＣＭブロックの番号を戻り値として返す（ブロック番号＝インスタンス番号）以後、ＡＣＭブロックへのアクセスは、その値を利用して行われる。
B. 確保したＡＣＭブロックに次の値をセットする。
-Base addressをＡＣＭブロックの先頭にセットする。
-各スレッド毎のリンク情報（Fan-in値、スレッドコードエントリーアドレス）を各スレッドエントリーにセットする。

２．継続命令（continue）を用いて、現実行インスタンスから生成された子インスタンスへ制御移行する。このとき継続命令のオペランドは新たに生成された子インスタンスのインスタンス番号(callee instance)と子インスタンスが実行するスレッドプログラムの先頭スレッドコードのエントリー（callee function name）によって与えられる（ユーザはこれらをパックしたデータ［callee-instannce + callee-function-name］として任意のレジスタにセットしておく。）なお、子インスタンスに引き渡す引数データは親インスタンス内のプログラム中でストア命令を用いて子インスタンス用のデータエリア（この領域をパラメータスロットアドレスと呼ぶ。）に書き込んでおく。
３．子インスタンス（callee instance）内でスレッドプログラムを実行する。子インスタンス内スレッドコードの実行において、現実行スレッドから継続スレッドへの制御移行は継続命令（continue）によって行う。このときのインスタンスはすべて子インスタンス（callee instance ）である。
４．子インスタンスから親インスタンス(caller instance)への制御移行（リターン処理）も継続命令（continue）によって行う。このときインスタンスは子インスタンス（callee instance）から親インスタンス(caller instance)へ変換される。継続スレッドはCall時に引き渡された親インスタンス内の戻り先スレッド（caller side continuation thread）として与えられている。
５．子インスタンスの実行が完了するときに、delete-instance命令(deliens)によって、そのインスタンス（ＡＣＭブロック）を解放する。

マクロ命令Callは次のプリミティブ命令を実行することによって実現される。
1.Newins命令の実行
インスタンスを生成する（インスタンス用のＡＣＭブロックの割り付け）。
割り付けられたＡＣＭブロック番号が指定したレジスタに返される。
2.New−data−area命令の実行
インスタンス用のデータ領域（New instance data area）を割り付ける。
メモリ管理部が新たなデータ領域を確保し、確保されたデータ領域のbase addressが指定したレジスタに返される。
3.Store処理
calleeに引き渡される情報は[caller-instance ＋ caller-side-continuation-thread]とparametersおよびreturn-value-slotのアドレス（retval）である。
[caller-instance ＋ caller-side-continuation-thread]とparametersは割り付けられたデータ領域のparameters slotに書き込まれる。
・retvalのアドレスをparameters slotに書き込む。
・これらの引数情報はあらかじめparameters slotに書き込んでおく。
4.Contiune命令を実行
New instance data areaのparameters addressを引数として、
[callee-instance ＋ callee-function-name(thread name)]に制御を渡す。

ルーチンあるいは関数からの戻り制御
図１０は、本発明における並列処理コンピュータにおけるルーチン（関数）からの戻り制御を示す説明図である。
マクロ命令Returnを用いてcalleeからcallerへの戻りの制御の概略を以下に示す。
マクロ命令: Return retins cont-thread,retval
オペランドは、
retins：caller instance
cont-theread：return thread
retval：return value slot
(1)retins はcallerインスタンスである。呼び側のインスタンス環境へ戻る。
(2)cont−threadは戻り先（caller side）のスレッドのコードエントリーである。
戻り先ではcontで指定されたスレッドが駆動される。
(3)retvalは戻り値を保持する戻り値スロット(return value slot)のアドレスである。
戻り値はcaller側のデータ領域に用意された戻り値スロットに書き込まれる

Return処理は下記のプリミティブ命令で実行する。
Ｉ Store命令の実行
戻り値の書き込み処理：ストア命令を用いて、戻り値をcaller側のデータ領域中のreturn value slotに書き込む。
ＩＩ Continue命令の実行
［caller instance ＋ return thread］に制御移行する。
ＩＩＩ Delins命令の実行
Current instanceを解放する。

以下に繰り返し実行のプログラム構造とその実行機構の一実施態様を示す。繰り返し実行の操作には次の３通りの方法がある。
1. 関数インスタンスレベル
2. インスタンス内スレッドレベル
3. スレッド内ループ
図１１は、本発明による並列処理コンピュータにおける繰り返し実行のプログラムの概念図である。以下、これらの方法について本発明における実現法を説明する。
1.関数インスタンスレベル
これは再帰関数の実行である。本発明の方式では、通常の再帰関数の実行は上述した方法によって、再帰ごとに新たに関数インスタンスを生成して実行することで可能である。しかし、このままでは再帰ごとにインスタンスの生成が必要であり、膨大なインスタンスを消費することになる。（再帰関数の実行では既存のプロセッサにおいてはインスタンスの代わりにスタックが使用されるが、膨大なスタックメモリを消費とするという点で同様の問題が生じる。）
一般に、関数ボディの末尾において再帰呼び出しを起こす末尾再帰関数についてはコンパイラによってループ実行のプログラム構造に変換できることが知られている。ここでは、本発明によって、特にコンパイラによるループ実行プログラム構造に変換することなく、末尾再帰関数を直接ループ実行制御する方法を示す。
図１２は、本発明による並列処理コンピュータにおける権限委譲（delegation）実行及びループ実行を示す説明図である。
図の（a）では、はじめにインスタンスiのスレッドth1より再帰関数の起動（そのボディはth0）を行っている。このとき、［ｉ＋tｈ2］を引数としてこの関数に引き渡す。（これは、再帰関数からの戻り先をインスタンスiの継続スレッド（th2）とすることを意味している。）関数はインスタンスi1で実行され、関数ボディth0でその末尾において［i＋th2］を引数として再帰（自分自身を再度起動）する。このとき、インスタンスi1はもはや不要となるので、直ちに解放される。同様にして、戻り先［i＋th2］を順次引き渡しつつ必要な分だけ再帰実行が進み、最後に実行が戻り先［i＋th2］に継続する。（このことが権限委譲と名づける所以である。）再帰ごとに生成されたインスタンスはその再帰起動が起こるごとに解放され再利用可能となる。

2.インスタンス内スレッドレベル
関数インスタンスレベルにおける権限委譲法は、図１２に示すように、最適化を施すことができる。権限委譲法では再起起動ごとに新たにインスタンスを生成していたが、新たなインスタンスを生成する代わりに、起動側のインスタンスiをそのまま使いまわすことにより、新たなインスタンスを生成する必要がなくなる。これは、同一インスタンス内での継続スレッドへの制御移行という構造であり、インスタンス内でのスレッドレベル・ループ実行法である。

3.スレッド内ループ
図１２の(b)に示すように、スレッド内ループはスレッド内にジャンプ命令を置き、ループを実行することである。これは、従来プログラムと同様のループ実行法である。

次に、スレッド問の非同期排他実行制御の制御機構の一実施態様を説明する。即ち、オペレーティングシステムなどにおける共有資源の排他制御を実現する機構について説明する。この機構は、実用的な並行処理システムを実現するために不可欠なものである。
前述したインスタンス内スレッドレベルのループ実行ではこのスレッドレベル・ループが、（シングルプロセス内処理のように）ただひとつのインスタンスから起動され他との干渉を起こさないような単純なループ実行の場合は問題ないが、オペレーティングシステムなどにおける共有資源の排他制御（これはいわゆる臨界領域（Critical Region）問題とよばれている）を実現しようとする場合、このスレッドレベル・ループ実行を行うスレッド自体が共有されることになり、このスレッドの排他制御が必要となる。

図１３は、本発明による並列処理コンピュータにおける排他制御の一実施態様を示す概念図である。スレッドthrad0スレッドレべル・ループを実行する。このインスタンスはシステムの起動時に生成され、以後システムが処理終了するまで、永続的（persistent）に存在し続ける。Thread OのFan-inが2であるとし、ひとつは自分自身からの継続であり、他の一つは並行に実行している複数のインスタンス（中のスレッド）Thread1、Thread2、…、Thread nからの継続であるとする。このとき、Thread1、…、Thread nは排他的にどれかひとつだけにThread Oへの継続を許し、他はThreadOの実行が終わり再帰するまで待たせることになる。このようなことは、例えば、共有メモリヘの読み書き動作（readres−writers）問題、や生産者・消費者(producer−consumer)問題、キュー管理など多くの並行プロセス管理において生じる。

この排他制御を3通りの方法によって実現する。
第1の方法は、実施例3で説明した継続スレッドヘの制御移行の命令（継続命令）のうち、（3）Ｗait-and−Continue命令と（4）Reset-and-Continue命令を用いる方法である。
第２の方法は、前述したロックビット（Lock−bit）を操作するTest-and-1ock命令およびReset-and-Continue命令を用いる方法である。
第3の方法は、第1の方法と第2の方法を組み合わせる方法である。この方法によりlock区間をできるだけ小さく設定することができる。

以下3つの方法の詳細を説明するが、その前に、まず、本発明による並列処理コンピュータで実行可能な、即ち本コンピュータでサポートされるTest-and-1ock命令とun1ock命令について説明する。
図１４は、本発明による並列処理コンピュータでサポートされるTest-and-1ock命令とun1ock命令の仕様例を示す説明図である。
（1）Test-and-1ock命令
オペランドで指定された継続スレッドに対応するＡＣＭブロック内スレッドエントリー［instance ＋ thread-name］）のLock-bit（ロック用フラグ）をチェックし、1ock-bitがon（locked）なら1ockが解かれるまで待つ。Lock−bitがoffなら（unlockedなら）直ちに1ock-bitをonにして動作を終了する。
Test-and-1ock命令の仕様として、別の仕様を定めることもできる。別法では、オペランドに任意のregisterを与え、Test-and-1ock命令の動作において、1ock-bitがon（1ocked）のときには待つ代わりに、registerに値0をセットして動作を終了する。Lock−bitがoffのときは直ちに1ock−bitをonにし、registerに1をセットして終了する。この方法では、Test-and-1ock命令の動作中にbusy-waitすることがない。
代わりにプログラム側で、registerの値をチェックすることによってbusy*wait制御をすることになる。
複数のインスタンス・スレッドから排他実行をするスレッドへ継続する場合、それぞれのインスタンス・スレッド中でTest-and-1ock命令を用いることにより、それらの継続要求は排他制御される。

（2）unlock命令
オペランドで指定された継続スレッドに対応するＡＣＭブロック内スレッドエントリー（［instance ＋ thread-name］）のLock-bitをoff（unlocked）にする。
なお、Reset-and−Continue命令もLock-bitをoffにすることに注意されたい。

次に、本発明による並列処理コンピュータでサポートされる上述した諸命令を用いて排他制御を行う具体的な方法を３つ挙げる。
図１５は、本発明における並列処理コンピュータにおける第１及び第２の排他制御方法を示す説明図であり、図１６は、本発明における並列処理コンピュータにおける第３の排他制御方法を示す説明図である。
第１の排他制御方法
図１５の（a）は、インスタンスi、j、kが並行して動作しており（iは永続インスタンスである）、インスタンスjとkがそれぞれthread l、thread2からインスタンスiのthread Oへ継続する状況を示している。このとき、インスタンスiは排他的にしか動作できない臨界領域なので排他制御が必要となる、今jとkがほとんど同時にiに継続しようとし、それぞれＷait-and−Continue命令を実行したとする。この命令の実行自体排他的（Atomic操作）なので、どちらかが先に（たとえばjが）ＡＣＭブロックにアクセスしその同期カウントを1ずつ減らす。その結果同期カウント=0となれば、スレッドは実行を開始する。このときkは〈すでに同期カウントが0となってしまっているので同期カウントの値がfain-in値にリセットされるまでＴＡＣ内で待たされることになる。iのthreadOの実行が終わりReset-and-Continue命令を実行するときに同期カウントの値をfain−inn値にリセットするので、この段階でkの待ちが解かれ、iのthreadOに継続できることになる。

第２の排他制御方法
図１５の（b）は、第1の方法の場合と同様、インスタンスi、j、kが並行して動作しており、インスタンスjとkがそれぞれthread l、thread 2からインスタンスiのthread Oへ継続する状況を示している。この図では、Data areaが共有資源として用いられており、インスタンスj、kがそれぞれ処理した結果をｘにストアし、インスタンスiのthread 0がxからロードしてそれぞれの結果に処理を施すという状況を表している。このとき、xへのストア操作は排他的でなければならない。そこで、第２の方法ではLock−bit操作によってストアおよびロード操作が行われる領域を臨界領域にしてLockを掛ける。インスタンスjおよびkは、ｘにストアする前にTest-and−lock命令によって1ock−bitをチェックし、unlockなら直ちに1ockし、Store命令を実行してデータをxにストアし、Continue命令の実行を行ってインスタンスiのthread Oに継続する。いまjのthread1が先に命令をTest-and-1ock命令を実行したとすると、続いてstore r8、ｘも実行できてr8のデータがｘにストアされ、実行がインスタンスiに継続する。一方、インスタンスkのthread 2はTest-and-1ock命令実行において1ock-bitがlockされているので、これがunlockされるまで待たされstore命令も先延ばしとなる。実行がインスタンスjからiに継続するとthread Oは1oad r4、xを実行してxからデータをロードしてインスタンスjの結果を処理する。thread OがRest-and-Continue命令を実行すると、Lock−bitがunlockされる。この結果インスタンスkでの1ock解除待ちが解かれ、Store r5、xの実行によってインスタンスkの結果がxにストアされた後、実行がインスタンスiに継続する。

第３の排他制御方法
第２の方法では臨界領域がTest-and-1ockで1ockされReset-and-Continueで1ockが解かれるまでの区間となる、この方法では1ock区間が長すぎて並列処理の効果がうまく生かされないという場合が生じる。
第３の方法は1ock区間を必要最小限にとどめるという方法である。図１６の(c)に示すように、この方法では共有資源へのアクセスを排他制御するのにTest-and-1ock 命令とUnlock命令による1ock-bit操作を用い、インスタンスiへの継続を排他制御するのにWait-and-Continue命令とReset-and-Continue命令を用いる。インスタンスj、k、1では、共有メモリxへのstore命令実行の直前にTest-and-1ock命令を実行して1ockを掛け、インスタンスiでは1ock命令実行直後にUnlock命令を実行して、lockを解除している。またインスタンスj、k、1ではインスタンスiのthreadOへの継続を排他的に行うためにWait-and-Continue命令を実行し、thread Oは自分自身へ継続する際にReset-and-Continue命令を実行して、待ち状態にある継続要求を受けいれる。
第3の方法では共有資源へのlock区間がTest-and-1ock命令とUnkock命令の間に狭められ、臨界領域を必要最小限に押さえることができる、

次に、本発明における並列処理コンピュータがサポートするデータキャッシュ方式を説明する。図１１は、本発明における並列処理コンピュータがサポートするデータキャッシュ（D-Cache）制御の概念を示す概念図である。図ではD−Cacheが4バンク構成の場合で下3ビットによってバンク・アクセスする状況を示している。
D−Cache制御においては、
(1) 各スレッド演算ユニット（EU）内に、先行スレッドのインスタンスIDおよび現走行インスタンスIDの下（あるいは上nビット）を保持する内部レジスタInSID1、InSID2を設ける。
(2) D−Cacheは複数バンク（２ⁿ個）で構成し、それぞれのEUにおけるメモリアクセスに際してInSID1あるいはInSID2の値によって、アクセスすべきD−Cacheバンクを決定する。

上述したデータキャッシュ制御をさらに詳細に説明する。
1. 継続スレッドへ制御移行する際に現行のスレッドのインスタンス番号の下（あるいは上）ｎビットの値（すなわちD−Cashのバンク番号；以下Cache-bank Numberとよぶ）を継続スレッドに渡す。
2. 先き読み制御部（Ｐre-1oad Ｕnitt）では実行待ちスレッドキュー中の継続スレッドからCache-bank Numberを取り出してそのD−Cacheバンクヘアクセスする。
3. 継続スレッドの実行開始時にCache−bank Numberおよび現実行スレッドのインスタンス番号の下(あるいは上)nビット分をそれぞれInSID₁およびInSID₂にセットする。
4. スレッド実行において、ロード（読み込み）の際のメモリアクセスにはD−Cache バンク番号をロード／ストア制御ユニット（ＬＳＣ）に渡す。ＬＳＣは渡されたD−Cacheバンク番号によってそのD−Cacheバンクにアクセスする。
5. 2.および4.でのキャッシュ制御の手順は通常の（たとえばMSCマシン）方法と同様の方法をとる。
6. ストア（書き出し）の際のメモリアクセスには、現走行スレッドのインスタンス番号を保持しているInSID₂を用いて3.と同様のことを行う。
本方法の利点は、スレッド間に渡る実行においてインスタンス番号を引き継ぐことによってデータアクセスの局所性を保持することができるという本発明方式の特徴を生かし、先行スレッドでストアされたデータを継続スレッドがロードする場合に先行スレッドのインスタンスに対応するキャッシュ・バンクを用いることによってキャッシュのヒット率を向上させることにある。

本発明は、マルチスレッド処理の原理を通用した新規な概念に基づいて多重並行処理する並列処理コンピュータの方式とその構成法に関する基本的な技術であり、各種の並列分散処理のための並列処理コンピュータの基本方式として一般的に適用可能である。例えば、ネットワークノードに設置してメッセージ処理・転送などの各種トランザクション処理を行う並列処理コンピュータやネットワークの端末コンピュータとして各種の並列・分散処理応用に利用されるものである。また、本発明を諸図面や実施例に基づき説明してきたが、当業者であれば本開示に基づき種々の変形や修正を行うことが容易であることに注意されたい。従って、これらの変形や修正は本発明の範囲に含まれることを留意されたい。

本発明による、細粒度マルチスレッド実行可能な並列処理コンピュータの一実施態様を示すブロック図である。 マルチスレッドプログラムの構造の一例を示す説明図である。 本発明による並列処理コンピュータにおけるマルチスレッド実行制御部（ＴＥＣ）およびメモリアクセス制御部（ＭＡＣ）の詳細な実施態様を示すブロック図である。 本発明による並列処理コンピュータにおける先行スレッドから継続スレッドへの制御移行およびデータ引渡しの機構を示す説明図でる。 本発明による並列処理コンピュータにおけるＡＣＭの構成例を示すメモリマップ図である。 本発明による並列処理コンピュータにおけるＴＡＣの動作の一例を示す説明図である。 本発明による並列処理コンピュータがサポートする継続命令の機能を示す説明図である。 本発明による並列処理コンピュータがサポートする継続命令の機能を示す説明図である。 本発明による並列処理コンピュータにおけるスレッド間の制御移行及びデータ引渡しの動作を示す説明図である。 本発明における並列処理コンピュータがサポートするルーチン（関数）起動のマクロ及び引数の引渡し法を示す説明図である。 本発明における並列処理コンピュータにおけるルーチン（関数）からの戻り制御を示す説明図である。 本発明による並列処理コンピュータにおける繰り返し実行のプログラムの概念図である。 図本発明による並列処理コンピュータにおける権限委譲（delegation）実行及びループ実行を示す説明図である。 本発明による並列処理コンピュータにおける排他制御の一実施態様を示す概念図である。 本発明による並列処理コンピュータでサポートされるTest-and-1ock命令とun1ock命令の仕様例を示す説明図である。 本発明における並列処理コンピュータにおける第１及び第２の排他制御方法を示す説明図である。 本発明における並列処理コンピュータにおける第３の排他制御方法を示す説明図である。 本発明における並列処理コンピュータがサポートするデータキャッシュ（D-Cache）制御の概念を示す概念図である。

符号の説明

１０ 並列処理コンピュータ
１２ スレッド起動制御部（ＴＡＣ）
１２ａ スレッド間同期管理用の高速メモリＡＣＭ
１３ 実行待ちスレッドキュー
１４ スレッド実行制御部（ＴＥＣ）
１４ａ 複数のスレッド演算実行ユニット（ＥＵ）
１４ｂ 複数のレジスタファイル
１４ｃ 命令キャッシュ
１４ｄ 先行ロードユニット
１４ｅ スレッド演算ユニット（ＥＵ）割り付け・起動ユニット
１６ メモリアクセス制御部（ＭＡＣ）
１６ａ 複数バンクのデータキャッシュ
１６ｂ メモリ管理部
１６ｃ ロード／ストア制御ユニット
１６ｄ ＤＭＡ制御部
１８ メインメモリ
２０ 入出力制御部
２２ 通信制御部
３０ａ スレッド演算実行ユニット
３０ｂ レジスタファイル
３０ｃ 命令キャッシュ（Ｉ−Cache）
３０ｄ データキャッシュ（Ｄ−Cache）
３２ 実行待ちスレッドキュー
３４ ＥＵ割り付け・起動ユニット
３６ 先行ロードユニット
３８ ロード／ストア制御ユニット
４０ メモリ管理ユニット

Claims (7)

1. 複数のスレッドを同時並列に実行する並列処理コンピュータであって、
   排他的に実行可能なプログラム断片であるスレッドのそれぞれが実行可能か否かを判定し、実行可能であると判定されたスレッドを実行待ちスレッドとして実行待ちキューに入れるスレッド起動制御部と、
   先行ロードユニット、スレッド演算ユニット割り付け・起動ユニット、複数のスレッド演算実行ユニット、及び、複数のレジスタを持つ複数のレジスタファイルを含む、スレッド実行制御部と、
   を具える並列処理コンピュータであり、
   前記先行ロードユニットが、前記実行待ちキューに収容されている前記実行待ちスレッドが実行される前に、この実行待ちスレッドに対して、前記複数のレジスタファイルのうちの空きレジスタファイルを割り付け、この実行待ちスレッド用の初期データをメモリから前記割り付けたレジスタファイルにロードし、
   前記スレッド演算ユニット割り付け・起動ユニットが、前記複数のスレッド演算ユニットのうちアイドル状態のものがある場合、前記実行待ちキューの先頭から前記実行待ちスレッドを取り出し、この実行待ちスレッドを前記アイドル状態の前記スレッド演算ユニットに割り付け、この割り付けられた実行待ちスレッド用の初期データがロードされている前記レジスタファイルを前記アイドル状態の前記スレッド演算ユニットに結合して、この実行待ちスレッドを起動し、
   前記複数のスレッド演算実行ユニットが、前記起動されたスレッドを同時並列に実行する、
   並列処理コンピュータ。
2. 請求項１に記載の並列処理コンピュータにおいて、
   前記複数のスレッド演算ユニットは、それぞれ専用の命令キャッシュに結合され、
   前記並列処理コンピュータは、前記実行待ちスレッドが起動される前に当該スレッドのコードを前記メモリから前記命令キャッシュにロードする第１のメモリ管理部をも具える、
   ことを特徴とする並列処理コンピュータ。
3. 請求項１または２に記載の並列処理コンピュータにおいて、
   前記並列処理コンピュータはデータキャッシュをも具え、
   前記先行ロードユニットは、前記メモリへのアクセスの前に、前記データキャッシュへアクセスし、ヒットした場合はそのデータキャッシュから前記実行用データをロードする、
   ことを特徴とする並列処理コンピュータ。
4. 請求項３に記載の並列処理コンピュータにおいて、
   前記データキャッシュは複数のバンクを含み、
   前記並列処理コンピュータは、
   各スレッドを実行するときに、各スレッドに先行するスレッドによって使用された前記データキャッシュのバンクがある場合は、そのバンクを使用するよう制御する第２のメモリ管理部をも具える、
   ことを特徴とする並列処理コンピュータ。
5. 請求項１〜４のいずれか１項に記載の並列処理コンピュータにおいて、
   前記スレッド起動制御部は、同期制御メモリを含み、
   前記同期制御メモリは各インスタンスごとにブロックを持ち、この各ブロックには各スレッドごとにスレッド起動同期用カウントフィールド及び先行スレッド数が予め収容されている先行スレッド数フィールドが設けられ、
   前記スレッド起動制御部は、前記スレッド起動同期用カウントに初期値として先行スレッド数フィールドにセットされた先行スレッド数をセットし、その値を当該スレッドに対する起動通知を受けるたびに１ずつ減少させゼロになったときに実行可能になったと判定する、
   ことを特徴とする並列処理コンピュータ。
6. 請求項５に記載の並列処理コンピュータにおいて、
   前記同期制御メモリの各ブロックは、ロック用フラグをも持ち、
   前記複数のスレッド演算実行ユニットは、前記ロック用フラグをロックする命令及び前記ロック用フラグをアンロックする命令をサポートする、
   ことを特徴とする並列処理コンピュータ。
7. 請求項１〜６のいずれか１項に記載の並列処理コンピュータにおいて、
   さらに、共有資源にアクセスできる排他制御スレッドと、
   前記排他制御スレッドへの排他継続を制御する排他継続制御機構と、
   前記共有資源への排他アクセスを制御する排他アクセス制御手段と、
   を具える、ことを特徴とする並列処理コンピュータ。

Images