(57)【特許請求の範囲】
【請求項１】
共有メモリに対する順序付けられたアクセス要求を複数のプロセッサ又はスレッドから受信して、これらのアクセス要求を並列処理する共有メモリ制御方法であって、
前記共有メモリを複数のメモリ領域に分割し、
前記メモリ領域毎に前記プロセッサ又はスレッドから順序付けられた前記アクセス要求を受け付け、
前記アクセス要求に記載された記載順序番号とアクセス対象の前記メモリ領域が期待する期待順序番号とが一致しているときは、当該アクセス要求を実行すると共に、
前記アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を所定の数だけ増減させ、
前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、
前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行することを特徴とする共有メモリ制御方法。
【請求項２】
共有メモリに対する順序付けられたアクセス要求を複数のプロセッサ又はスレッドから受信して、これらのアクセス要求を並列処理する共有メモリ制御方法であって、
前記複数のプロセッサ又はスレッドからアクセス可能な前記共有メモリを複数のメモリ領域に分割し、
前記メモリ領域毎に前記プロセッサ又はスレッドから順序付けられた前記アクセス要求を受け付け、
前記アクセス要求に記載された記載順序番号とアクセス対象の前記メモリ領域が期待する期待順序番号とが一致しているときは、当該アクセス要求を実行すると共に、
前記アクセス要求の種別が「将来の書き込みを伴う読み出し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を改変せず、
前記アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を所定の数だけ増減させ、
前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、
前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行することを特徴とする共有メモリ制御方法。
【請求項３】
種別が「書き込み」以外の前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、
前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行することを特徴とする請求項２記載の共有メモリ制御方法。
【請求項４】
種別が「書き込み」であるアクセス要求を前記プロセッサ又はスレッドから受信して、当該アクセス要求を実行したことで、アクセス対象の前記メモリ領域が期待する前記期待順序番号が更新されたことを契機に、前記メモリ領域に対応する待ち行列に保存された１つ以上のアクセス要求を連続して実行するとき、前記メモリ領域からデータを読み出す代わりに、種別が「書き込み」である前記アクセス要求に含まれる書き込みデータを参照して処理し、最後に実行されたアクセス要求の種別が「読み出しのみ」又は「操作無し」であるときは、種別が「書き込み」である前記アクセス要求に含まれる書き込みデータを前記メモリ領域に書き込み、最後に実行されたアクセス要求の種別が「将来の書き込みを伴う読み出し」であるときは、種別が「書き込み」である前記アクセス要求に含まれる書き込みデータを前記メモリ領域に書き込まないことを特徴とする請求項２記載の共有メモリ制御方法。
【請求項５】
種別が「読み出しのみ」又は「操作無し」であるアクセス要求を前記プロセッサ又はスレッドから受信して、当該アクセス要求を実行したことで、アクセス対象の前記メモリ領域が期待する前記期待順序番号が更新されたことを契機に、前記メモリ領域に対応する待ち行列に保存された１つ以上のアクセス要求を連続して実行するとき、前記メモリ領域を参照する際に、前記メモリ領域からデータを読み出したか否かを示すフラグを参照して、当該フラグが過去に一度でも読み出していることを示すときは、新たな読み出しを行わずに過去に読み出したデータを参照して処理することを特徴とする請求項２記載の共有メモリ制御方法。
【請求項６】
共有メモリを区分する複数のメモリ領域に対する、順序付けられたアクセス要求を複数のプロセッサ又はスレッドから受信してこれらのアクセス要求を並列処理する共有メモリ制御回路であって、
前記メモリ領域毎に、前記メモリ領域が期待する期待順序番号と前記メモリ領域の待ち行列識別子とを記憶するメモリ領域情報メモリと、
前記プロセッサ又はスレッドから受信した前記アクセス要求をアクセス対象のメモリ領域毎に保存可能な待ち行列の集合と、
前記プロセッサ又はスレッドからアクセス要求を受信する度に、アクセス対象の前記メモリ領域が期待する期待順序番号とアクセス対象の前記メモリ領域の前記待ち行列識別子を前記メモリ領域情報メモリから読み出し、前記アクセス要求に記載された記載順序番号とアクセス対象の前記メモリ領域が期待する期待順序番号が一致しているときは、当該アクセス要求を実行すると共に、
前記アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を所定の数だけ増減させ、
前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、
前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行するアクセス調停部とを備えてなることを特徴とする共有メモリ制御回路。
【請求項７】
共有メモリを区分する複数のメモリ領域に対する、順序付けられたアクセス要求を複数のプロセッサ又はスレッドから受信してこれらのアクセス要求を並列処理する共有メモリ制御回路であって、
前記メモリ領域毎に、前記メモリ領域が期待する期待順序番号と前記メモリ領域の待ち行列識別子とを記憶するメモリ領域情報メモリと、
前記プロセッサ又はスレッドから受信した前記アクセス要求をアクセス対象のメモリ領域毎に保存可能な待ち行列の集合と、
前記プロセッサ又はスレッドからアクセス要求を受信する度に、アクセス対象の前記メモリ領域が期待する期待順序番号とアクセス対象の前記メモリ領域の前記待ち行列識別子を前記メモリ領域情報メモリから読み出し、前記アクセス要求に記載された記載順序番号とアクセス対象の前記メモリ領域が期待する期待順序番号が一致しているときは、当該アクセス要求を実行すると共に、
前記アクセス要求の種別が「将来の書き込みを伴う読み出し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を改変せず、
前記アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を所定の数だけ増減させ、
前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、
前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行するアクセス調停部とを備えてなることを特徴とする共有メモリ制御回路。
【請求項８】
前記アクセス調停部は、
種別が「書き込み」以外の前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、
前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行することを特徴とする請求項７記載の共有メモリ制御回路。
【請求項９】
前記アクセス調停部は、
種別が「書き込み」であるアクセス要求を前記プロセッサ又はスレッドから受信して、当該アクセス要求を実行したことで、アクセス対象の前記メモリ領域が期待する前記期待順序番号が更新されたことを契機に、前記メモリ領域に対応する待ち行列に保存された１つ以上のアクセス要求を連続して実行するとき、前記メモリ領域からデータを読み出す代わりに、種別が「書き込み」である前記アクセス要求に含まれる書き込みデータを参照して処理し、最後に実行されたアクセス要求の種別が「読み出しのみ」又は「操作無し」であるときは、種別が「書き込み」である前記アクセス要求に含まれる書き込みデータを前記メモリ領域に書き込み、最後に実行されたアクセス要求の種別が「将来の書き込みを伴う読み出し」であるときは、種別が「書き込み」である前記アクセス要求に含まれる書き込みデータを前記メモリ領域に書き込まないことを特徴とする請求項７記載の共有メモリ制御回路。
【請求項１０】
前記アクセス調停部は、
種別が「読み出しのみ」又は「操作無し」であるアクセス要求を前記プロセッサ又はスレッドから受信して、当該アクセス要求を実行したことで、アクセス対象の前記メモリ領域が期待する前記期待順序番号が更新されたことを契機に、前記メモリ領域に対応する待ち行列に保存された１つ以上のアクセス要求を連続して実行するとき、前記メモリ領域を参照する際に、前記メモリ領域からデータを読み出したか否かを示すフラグを参照して、当該フラグが過去に一度でも読み出していることを示すときは、新たな読み出しを行わずに過去に読み出したデータを参照して処理することを特徴とする請求項７記載の共有メモリ制御回路。
【請求項１１】
コンピュータに請求項１乃至５の何れか１つに記載の共有メモリ制御方法の各処理を実行させるための共有メモリ制御プログラム。
【請求項１２】
請求項６乃至１０の何れか１つに記載の共有メモリ制御回路の動作を制御するためのプログラムであって、コンピュータを前記アクセス調停部として機能させるための共有メモリ制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、共有メモリの制御回路、制御方法及び制御プログラムに係り、詳しくは、複数のプロセッサが存在する環境下で順序依存性を有する処理を並列実行する際に好適な共有メモリの制御回路、制御方法及び制御プログラムに関する。
【背景技術】
【０００２】
半導体技術の進化と共に、マイクロプロセッサのクロック周波数と性能も飛躍的に向上してきた。しかし、近年、半導体プロセスの微細化が限界に近づきつつあり、マイクロプロセッサのクロック周波数の伸びも鈍化してきている。
このような状況下で、半導体業界は、クロック周波数を高める代わりに、１つのマイクロプロセッサのダイに複数のプロセッサコア（ＣＰＵ、以下、単にコアともいう）を搭載して、複数のコアがマイクロプロセッサの処理を分担して行う構成とすることで、マイクロプロセッサの処理速度の向上化に努めている。例えば、１つのダイに２〜４個のコアを内蔵するマルチコアプロセッサは、一般向けのパーソナルコンピュータ用として既に流通しており、さらに、数十個以上のコアを搭載するメニイコアプロセッサの研究開発も盛んに行われている。
【０００３】
シングルコアプロセッサからマルチコアプロセッサ、さらにはメニイコアプロセッサへの変遷は、プログラミング手法にも変革をもたらしつつある。マルチコアプロセッサ又はメニイコアプロセッサの能力を最大限に引き出すためには、広く認知されているように、複数のプロセッサによる並列処理に適したプログラミング手法が必要である。なお、この明細書で、「プロセッサ」というときは、論理的なプロセッサを指すものとする。すなわち、物理的な１個のプロセッサの中に複数のコアが存在する場合、それぞれのコアを「プロセッサ」と呼称する。
【０００４】
ここで、複数のプロセッサに並列処理を実行させる並列化手法としては、時分割並列化手法と、空間分割並列化手法とが知られている。
まず、時分割並列化では、図１２に示すように、各プロセッサ８０−１、８０−２、８０−３は、自身に割り当てられた1つの処理、すなわち、リソースａにアクセス処理を伴うステップＡ、リソースｂにアクセス処理を伴うステップＢ、又はリソースｃにアクセス処理を伴うステップＣの実行に専念し、さながら製品組み立て工場におけるベルトコンベアを利用した流れ作業のように処理が並列実行される。それゆえ、時分割並列化は、パイプライン方式とも呼ばれる。ここで、リソースａ、ｂ、ｃは、例えば、メモリやＩ／Ｏ等である。
【０００５】
一方、空間分割並列化では、図１３に示すように、プロセッサ９０−１、９０−２、９０−３群の前段で入力が１つずつプロセッサ９０−１、９０−２、９０−３に分配され、各プロセッサ９０−１、９０−２、９０−３は、１つの入力に対して徹頭徹尾すべての処理、すなわち、リソースａにアクセス処理を伴うステップＡ、リソースｂにアクセス処理を伴うステップＢ、又はリソースｃにアクセス処理を伴うステップＣを実行する。
【０００６】
複数のプロセッサに並列処理を実行させる並列化手法として、時分割並列化と空間分割並列化とのどちらが好ましいかは、並列化対象の処理の性質に依存して決定される問題であるが、通信処理においては、時分割並列化が用いられることが多い。
【０００７】
この理由は、通信処理の順序依存性のためである。
すなわち、情報通信においては、通信メッセージはパケット（又はフレーム）という入れ物に収められて伝送される。このパケットの長さには上限が設けられているため、この上限を超える長いメッセージは複数のパケットに分割されて伝送される。パケットの長さに上限が存在する主な理由は、１つのパケットが通信回線を長時間占有する状況を防ぐためと、通信装置内のメモリの量が有限であるためである。
【０００８】
例として、通信メッセージが「ＨＥＬＬＯ」であり、パケット長の上限が３文字であるとする。また、受信側は、受け取ったパケットの内容をメモリに記録してメッセージを再構築すると仮定する。この事例では、送信側は「ＨＥＬ」と「ＬＯ」にそれぞれ対応する２つのパケットを順に送信する。ここで、もしも、受信側がこれら２つのパケットを逆順に処理すれば、受信側のメモリには「ＬＯＨＥＬ」と記録され、メッセージを正しく復元することはできない。すなわち、通信において、パケットの順序を入れ替えて処理することは不可能もしくは不適切である。
【０００９】
これに対して、時分割並列化では、全ての入力は入力された順序通りに処理されるため、処理順序の逆転は本質的に起こり得ない。それゆえ、受信側が時分割並列化を採用しているときは、２つのパケットが「ＨＥＬ」→「ＬＯ」の順に受信側に到着すると、受信側のメモリには、必ず「ＨＥＬ」→「ＬＯ」の順でパケットの内容が記録されるので、正しいメッセージ「ＨＥＬＬＯ」が構成される。
【００１０】
一方、空間分割並列化では、入力が各プロセッサ９０−１、９０−２、９０−３に分配された後は、リソースａ、ｂ、ｃの使用時にプロセッサ９０−１、９０−２、９０−３間で順序を意識した排他制御を行わない限り、入力の処理順序性は保証されない。つまり、受信側が空間分割並列化を採用しているときは、２つのパケットが「ＨＥＬ」→「ＬＯ」の順に連続して受信側に到着すると、「ＬＯ」の処理が「ＨＥＬ」の処理よりも先行する可能性がある。この状況が発生すると、受信側のメモリには「ＬＯ」→「ＨＥＬ」の順にメッセージが記録されてしまうので不都合である。このような事態を防ぐには、受信側のメモリに「ＬＯ」→「ＨＥＬ」の順にパケットの内容が記録されようとしたら、「ＬＯ」の記録を保留し、先に「ＨＥＬ」の記録を優先して実施するような、順序を意識した高度なアクセス排他制御が必要になる。
【００１１】
共有リソースを使用する際の混乱を避けるための排他制御としては、従来から、セマフォを用いる排他制御が知られている。しかし、セマフォは、同時に複数のプロセッサ（広義にはスレッド）が少数のリソースの使用権を主張する競合状態を解決するためのものであって、リソースの使用に順序性が存在する場合にリソースの使用権をその順序通りにプロセッサに与える能力までは有していない。したがって、空間分割並列化の際に必要となる、順序を意識した共有リソース排他制御をセマフォにて実現することはできない。このように、空間分割並列化には、共有リソース排他制御に課題が存在するため、通信処理のような順序依存性を有する処理には時分割並列化が採用されることが多い。
【００１２】
次に、消費電力の観点から、時分割並列化と空間分割並列化との優劣を比較考量する。一般に、ある処理を複数のステップ（例えば、ステップＡ、ステップＢ、ステップＣ）に分割して行う場合、それぞれのステップは互いに独立にはならず、前のステップが計算した途中結果を次のステップが引き継ぐ形で処理が進行する。このため、時分割並列化では、図１２に示すように、プロセッサと次段のプロセッサとの間でデータＤ１、Ｄ２の引渡しが発生する。
【００１３】
プロセッサの個数が増えるに従って、プロセッサ間を流れる引渡しデータの総量が増加し、プロセッサ間通信によって消費される電力が増える。それゆえ、メニイコアプロセッサの開発では、プロセッサ間のデータ通信によって消費される電力の過大化が、無視できない問題となっている。
【００１４】
省電力の点では、空間分割並列化は時分割並列化よりも有利である。この理由は、図１３から明らかなように、空間分割並列化では、ある１つの入力に対する処理（例えば、ステップＡ、ステップＢ、ステップＣ）が、１つのプロセッサ内に閉じて、実行されるため、プロセッサ間の通信量は時分割並列化よりも少ないためである。
【００１５】
以上をまとめると、次のようになる。消費電力を考慮しなければ、通信処理のような順序依存性を有する処理には、空間分割並列化よりも時分割並列化の方が適している。この理由は、上記したように、時分割並列化は順序性を常に保証できるのに対し、空間分割並列化では順序を意識した共有リソース排他制御が必要となるためであり、これは、従来のセマフォでは実現できないためである。一方、プロセッサ間のデータ通信量は、時分割並列化よりも空間分割並列化の方が少ない。上記したように、データ通信量は消費電力に密接に関わっているため、消費電力の点では、時分割並列化よりも空間分割並列化の方が有利である。
【特許文献１】特開２０００−０９００５９
【特許文献２】特開２００１−２２２４６６
【特許文献３】特開２００２−２２９８４８
【特許文献４】特開平１１−３３８８３３
【発明の開示】
【発明が解決しようとする課題】
【００１６】
上記したように、複数のプロセッサが存在する環境下での通信処理のように、順序依存性を有する処理を並列実行する際、従来は、順序を意識した共有リソース排他制御の実現手段が存在していなかったため、空間分割並列化を採用できず、電力効率の点で不利な時分割並列化を利用せざるを得ない、という不都合な問題があった。
【００１７】
この発明は、上述の事情に鑑みてなされたもので、複数のプロセッサが存在する環境下での並列通信処理でも、プロセッサ間のデータ通信量を削減でき、低消費電力を達成しつつ、順序を意識した共有リソース排他制御を行うことができる共有メモリの制御回路、制御方法及び制御プログラムを提供することを目的としている。
【課題を解決するための手段】
【００１８】
上記課題を解決するために、この発明の第１の構成は、共有メモリに対する順序付けられたアクセス要求を複数のプロセッサ又はスレッドから受信して、これらのアクセス要求を並列処理する共有メモリ制御方法に係り、前記共有メモリを複数のメモリ領域に分割し、前記メモリ領域毎に前記プロセッサ又はスレッドから順序付けられた前記アクセス要求を受け付け、前記アクセス要求に記載された記載順序番号とアクセス対象の前記メモリ領域が期待する期待順序番号とが一致しているときは、当該アクセス要求を実行すると共に、前記アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を所定の数だけ増減させ、前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行することを特徴としている。
【００１９】
また、この発明の第２の構成は、共有メモリを区分する複数のメモリ領域に対する、順序付けられたアクセス要求を複数のプロセッサ又はスレッドから受信してこれらのアクセス要求を並列処理する共有メモリ制御回路に係り、前記メモリ領域毎に、前記メモリ領域が期待する期待順序番号と前記メモリ領域の待ち行列識別子とを記憶するメモリ領域情報メモリと、前記プロセッサ又はスレッドから受信した前記アクセス要求をアクセス対象のメモリ領域毎に保存可能な待ち行列の集合と、前記プロセッサ又はスレッドからアクセス要求を受信する度に、アクセス対象の前記メモリ領域が期待する期待順序番号とアクセス対象の前記メモリ領域の前記待ち行列識別子を前記メモリ領域情報メモリから読み出し、前記アクセス要求に記載された記載順序番号とアクセス対象の前記メモリ領域が期待する期待順序番号が一致しているときは、当該アクセス要求を実行すると共に、前記アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象の前記メモリ領域が期待する前記期待順序番号を所定の数だけ増減させ、前記アクセス要求に記載された前記記載順序番号とアクセス対象の前記メモリ領域が期待する前記期待順序番号とが不一致のときは、前記メモリ領域毎に独立に割り当てられた待ち行列に当該アクセス要求を退避させ、前記待ち行列に保存された前記アクセス要求に記載されている記載順序番号と、前記待ち行列に対応する前記メモリ領域が期待する期待順序番号とが一致し続ける限り、前記アクセス要求を前記待ち行列から連続的に取り出して実行するアクセス調停部とを備えてなることを特徴としている。
【発明の効果】
【００２０】
この発明の構成によれば、複数のプロセッサが存在する環境下での通信処理のように、順序依存性を有する処理を並列実行する際に必要となる、順序を意識した共有リソース排他制御の機能を、共有メモリ内に用意された領域の数だけ、独立に提供できる。それゆえ、プロセッサ間のデータ通信量を削減でき、低消費電力を達成しつつ、順序を意識した共有リソース排他制御を行うことができる。
【発明を実施するための最良の形態】
【００２１】
この発明を実施するための最良の形態としては、アクセス要求の種別が「読み出しのみ」、「書き込み」、又は「操作無し」であるときは、アクセス対象のメモリ領域が期待する期待順序番号を所定の数だけ増加又は減少させるようにする。好適には、「１」だけ増加させるようにすれば良いが、これに限定されない。
この発明は、例えば、ソフトウェアの助けを借りて、コンピュータに共有メモリ制御方法の各処理を実行させることで実現できる。具体的には、この発明は、コンピュータをアクセス調停部として機能させる制御プログラムによって実現できる。
【実施形態１】
【００２２】
以下、図面を参照して、この発明の実施形態について詳細に説明する。
図１は、この発明の第１の実施形態である共有メモリ制御部１が組み込まれた処理システム６の電気的構成を示すブロック図である。
この形態の処理システム６は、複数のプロセッサが存在する環境下で順序依存性を有する通信データ処理を並列実行する通信データ処理システムに係り、同図に示すように、共有メモリ制御部１と、共有メモリ２と、フロー識別部１０と、分配器１１と、Ｐ個（Ｐは２以上の自然数）のプロセッサ１２（１２−１、１２−２、…、１２−Ｐ）と、接続網１３とから概略構成されている。これらの構成各部については、順次説明する。
【００２３】
図１に示すように、上記共有メモリ制御部１は、接続網１３を介して、Ｐ個のプロセッサ１２と接続され、各プロセッサ１２（１２−１、１２−２、…、１２−Ｐ）からメモリアクセスのリクエスト５３、５３、…を受理して共有メモリ２にアクセスし、必要に応じて、リプライ５４、５４、…をプロセッサ１２に返信する。ここで、接続網１３の形態は、例えば、バス、リング、メッシュ、又はクロスバー等の公知のものであって良い。
【００２４】
プロセッサ１２は、共有メモリ２に対するアクセス要求を表すリクエスト５３を発行する際に、リクエスト５３が処理されるべき順番を示すシーケンス番号６２を共有メモリ制御部１に提示する。共有メモリ制御部１は、シーケンス番号６２の小さいリクエスト５３から順にアクセス要求を処理する。
【００２５】
このシーケンス番号６２は、フロー識別部１０が決定する。フロー識別部１０は、入力されたパケット５０のフローを識別し、図１に示すように、各フローに対して固有の値であるフロー番号５１を採番する。フローとは、互いに意味的な繋がりを持つパケットの集まりであり、フロー番号５１は、この実施形態の説明を容易にするため、非負整数とする。さらに、フロー識別部１０は、フロー毎にパケット５０の入力数の累計を計数し、同図に示すように、この累計値をシーケンス番号５２としてフロー番号５１と共にパケット５０に付与して、分配器１１に送出する。なお、フローの識別とパケット個数の計数は、いずれも通信分野では、ごく一般的な技術である。
【００２６】
図５は、フロー識別部１０の動作の具体例を示す図である。図５には、メッセージＸを構成する２つのパケットｘ１、ｘ２と、メッセージＹを構成する３つのパケットｙ１、ｙ２、ｙ３が、ｘ１→ｙ１→ｘ２→ｙ２→ｙ３の順にフロー識別部１０に入力され、それぞれのパケット５０にフロー番号５１とシーケンス番号５２が付与されて出力される様子が示されている。
【００２７】
図５の例では、メッセージＸに割り振られたフロー番号５１は１１１であり、メッセージＹのフロー番号５１は２２２である。また、メッセージＸに属するパケットｘ１とｘ２に与えられたシーケンス番号５２は順に０、１であり、メッセージＹに属するパケットｙ１とｙ２、ｙ３のシーケンス番号５２は順に０、１、２である。
【００２８】
上記したように、フローは、互いに意味的な繋がりを持つパケットの集まりであるので、この例では、メッセージＸとメッセージＹの２つのフローが存在している。メッセージには、同一のフローに属するパケットとパケットの間には順序的な依存関係があるが、異なるフローとフローとの間には依存関係は通常存在しない。
つまり、この例においては、下記の３つの条件が全て満たされていれば、メッセージＸとメッセージＹとは、正しく復元される。
条件１：パケットｘ１が処理されるタイミングはパケットｘ２より前であること。
条件２：パケットｙ１が処理されるタイミングはパケットｙ２より前であること。
条件３：パケットｙ２が処理されるタイミングはパケットｙ３より前であること。
例えば、処理システム６が、パケットｙ１→ｘ１→ｙ２→ｘ２→ｙ３のように、入力順とは異なる順序でパケット５０を処理したとしても、上記の条件が満たされているため不都合は生じない。換言すれば、処理システム６は、上記の条件を満たしている限り、パケット５０の処理順序を変更できる。この性質を利用することで、処理の並列度を上げることができ、処理システム６の性能を向上させることができる。
【００２９】
分配器１１は、フロー識別部１０から入力されたパケット５０を、フロー番号５１とシーケンス番号５２と共に、プロセッサ１２（１２−１、１２−２、…、１２−Ｐ）に分配する。配送先を選択するアルゴリズムとしては、例えば、実装の容易なラウンドロビン方式や、プロセッサ１２の負荷を計測して最も負荷の低いプロセッサ１２を配送先とする負荷分散方法等が広く知られている。
【００３０】
各プロセッサ１２は、自身に割り当てられたパケット５０を処理する。この処理の過程で、各プロセッサ１２は、共有メモリ２にアクセスするためにリクエスト５３を発行しても良い。各プロセッサ１２が、アクセス可能な共有メモリ２の領域は、自身が現在処理しているパケット５０に付与されたフロー番号５１に対応する領域に限られる。フロー番号５１とアクセス可能な領域との対応関係については後述する。
【００３１】
共有メモリ２は、図２に示すように、処理システム６に入力されたパケット５０のフローに関するデータを格納するメモリであり、同図に示すように、Ｎ個（Ｎ≧２）のブロック２０（２０−１、２０−２、…、２０−Ｎ）に領域分割され、これらのブロック２０に、フローに関する情報が格納される構成となっている。ここで、ある１つのフローの情報が、複数のブロック２０に分散して存在していても良い。パケット５０を処理しているプロセッサ１２は、パケット５０のフロー番号５１に対応するフローの情報が収容されている１つ以上のブロック２０にアクセスできる。
【００３２】
ここで、リクエスト５３の種別及びフォーマットについて説明する。
共有メモリ２へのアクセスは、全てリクエスト５３の形式で表現される。共有メモリ制御部１が受理するリクエスト５３には、「ＲＥＡＤ」、「ＲＥＡＤ＿ＯＮＬＹ」、「ＷＲＩＴＥ」、「ＮＯＰ（No Operation）」の４種類が存在する。
【００３３】
図６は、「ＲＥＡＤ」、「ＲＥＡＤ＿ＯＮＬＹ」、「ＷＲＩＴＥ」、「ＮＯＰ」の各リクエスト５３とリプライ５４のフォーマットを示している。
「ＲＥＡＤ」、「ＲＥＡＤ＿ＯＮＬＹ」、及び「ＮＯＰ」の各リクエスト５３は、図６に示すように、発行元６０と対象ブロック番号６１とシーケンス番号６２種別６３とから構成されている。「ＷＲＩＴＥ」のリクエスト５３は、同図に示すように、対象ブロック番号６１と種別６３と書き込みデータ６４とから構成されている。
【００３４】
リクエスト５３の対象ブロック番号６１の値がＸ（０≦Ｘ＜Ｎ）であるとき、そのリクエスト５３のアクセス対象は、共有メモリ２のブロック２０のうち、第［２０−（Ｘ＋１）］番目のブロック２０−（Ｘ＋１）である。したがって、パケット５０を処理しているプロセッサ１２は、そのパケット５０のフロー番号５１に対応するフローの情報がブロック２０−（Ｘ＋１）に収容されているとき、リクエスト５３を発行する際、その対象ブロック番号６１をＸにする。フロー番号５１に対応するフローの情報を格納するブロック２０が複数存在するときは、各プロセッサ１２は、それぞれのブロック２０に対して独立にリクエスト５３を発行する。
【００３５】
リクエスト５３の種別６３は、「ＲＥＡＤ」、「ＲＥＡＤ＿ＯＮＬＹ」、「ＷＲＩＴＥ」、「ＮＯＰ」のいずれかの値をとる。なお、この実施形態では、種別６３を文字列で表現しているが、これは可読性を高めるための形式的な措置である。実際には、種別６３を数値やフラグビットで表現する方が効率的であることは言うまでもない。
【００３６】
発行元６０は、そのリクエスト５３を発行したプロセッサ１２（１２−１、１２−２、…、１２−Ｐ）のいずれかを指す。ただし、この実施形態では、プロセッサ１２上で複数のスレッドが動作しているときは、リクエスト５３を発行したスレッドを特定するための情報も発行元６０が持つものように構成されている。
【００３７】
上記シーケンス番号６２は、リクエスト５３が共有メモリ制御部１によって処理される順序を決定付けるものである。ただし、処理の順序関係は、同一の対象ブロック番号６１を持つリクエスト５３の間にのみ成立する。共有メモリ制御部１は、互いに異なる対象ブロック番号６１を持つ２つ以上のリクエスト５３の間には、順序依存性が存在しないとみなし、異なる対象ブロック番号６１に跨るリクエスト６３間の処理順序を制御しない。各プロセッサ１２は、リクエスト５３を発行する際、当該プロセッサ１２が処理しているパケット５０のシーケンス番号５２（図５）を、リクエスト５３のシーケンス番号６２（図６）に代入する。
【００３８】
次に、図６を参照して、「ＲＥＡＤ」、「ＲＥＡＤ＿ＯＮＬＹ」、「ＷＲＩＴＥ」、「ＮＯＰ」の各リクエスト５３に対する共有メモリ制御部１（アクセス調停部５）が行う動作について述べる。
まず、ＲＥＡＤリクエスト５３に対する動作から説明する。
共有メモリ制御部１は、任意のプロセッサ１２からＲＥＡＤリクエスト５３を受けると、共有メモリ２の対象ブロック番号６１に対応するブロック２０に格納されているデータを読み出し、読み出したデータをリプライ５４中の読み出しデータ７１に収めて、ＲＥＡＤリクエスト５３を送信した発行元６０にリプライ５４を返信する。
【００３９】
ここで、ＲＥＡＤリクエスト５３は、将来の書き込みを伴う読み出しリクエストであり、常にＷＲＩＴＥリクエスト５３を伴うように構成されている。すなわち、ＲＥＡＤリクエスト５３に対するリプライ５４を受信した発行元６０は、更新後のブロック２０の内容を作成し、これをＷＲＩＴＥリクエスト５３中の書き込みデータ６４に収めてから、このＷＲＩＴＥリクエスト５３を発行して共有メモリ２のブロック２０にデータを書き戻さなければならない。発行元６０がブロック２０の内容を書き換えないときは、リプライ５４中の読み出しデータ７１の内容をＷＲＩＴＥリクエスト５３中の書き込みデータ６４に代入してから、このＷＲＩＴＥリクエスト５３を発行しなければならない。
【００４０】
ペアとなるＲＥＡＤリクエスト５３とＷＲＩＴＥリクエスト５３の対象ブロック番号６１は同一でなければならない。なお、はじめからブロック２０の内容を参照するのみで更新する意図が無い場合は、ＲＥＡＤリクエスト５３の代わりに、次述のＲＥＡＤ＿ＯＮＬＹリクエスト５３を使用することが推奨される。
【００４１】
次に、ＲＥＡＤ＿ＯＮＬＹリクエスト５３に対する動作について説明する。
共有メモリ制御部１は、任意のプロセッサ１２からＲＥＡＤ＿ＯＮＬＹリクエスト５３を受けると、共有メモリ２の対象ブロック番号６１に対応するブロック２０に格納されているデータを読み出し、読み出したデータをリプライ５４中の読み出しデータ７１に収めて、ＲＥＡＤ＿ＯＮＬＹリクエスト５３を送信した発行元６０にリプライ５４を返信する。ここで、ＲＥＡＤ＿ＯＮＬＹリクエスト５３とＲＥＡＤリクエスト５３との違いは、ＲＥＡＤ＿ＯＮＬＹリクエスト５３のときは、発行元６０がリプライ５４に呼応してＷＲＩＴＥリクエスト５３を発行することができないという点だけである。
【００４２】
ＷＲＩＴＥリクエスト５３は、上記したように、常にＲＥＡＤリクエスト５３と組み合わせて使用される。また、ＮＯＰリクエスト５３は、共有メモリ２の対象ブロック番号６１に対応するブロック２０に対して何の操作も行わないことを、共有メモリ制御部１に通知するために用意されている。
【００４３】
次に、ＮＯＰリクエスト５３の必要性について説明する。
上記した通り、共有メモリ制御部１はシーケンス番号６２の小さいリクエスト５３から順にこれらを処理しようとする。このため、あるプロセッサ１２がリクエスト５３を発行しなかった場合、シーケンス番号６２の「抜け」が生じ、この失われたシーケンス番号６２よりも大きいシーケンス番号６２を持ち、かつ、同一のブロック２０にアクセスするリクエスト５３は永久に処理されなくなる。この結果、処理システム６はスタック状態に陥ってしまう。この不都合な事態を防止するため、この実施形態では、各プロセッサ１２は、パケット５０を処理する過程で、ブロック２０に「ＲＥＡＤ」リクエスト、「ＲＥＡＤ＿ＯＮＬＹ」リクエスト、「ＷＲＩＴＥ」リクエスト等のアクセスをしないことを選択したときでも、このパケット５０のシーケンス番号５２をＮＯＰリクエスト５３のシーケンス番号６２に代入し、このＮＯＰリクエスト５３を発行する。このような構成とすることで、共有メモリ制御部１におけるシーケンス番号６２の連続性を保つことができるようにしている。
【００４４】
共有メモリ制御部１は、図１に示すように、ブロックプロパティメモリ３と、待ち行列メモリ４と、アクセス調停部５とから構成されている。図３は、ブロックプロパティメモリ３の内部構造を示す概念図であり、図４は、待ち行列メモリ４の内部構造を示す概念図である。
【００４５】
待ち行列（キュー）メモリ４は、実行が保留されているリクエスト５３を保持するためのメモリである。共有メモリ制御部１は、下記の２つの条件を同時に満たすリクエスト５３を受信したときは、リクエスト５３を即座に実行せずに、待ち行列メモリ４に一時的に退避する。すなわち、共有メモリ制御部１は、条件１として、種別６３が「ＷＲＩＴＥ」以外であるリクエスト５３を受信したときであって、条件２として、受信したリクエスト５３が、その対象ブロック番号６１に対応するブロックプロパティ３０のシーケンス番号の期待値３３とは異なるシーケンス番号６２を持つときは、リクエスト５３を即座に実行せずに、待ち行列メモリ４に一時的に退避する。
【００４６】
上記待ち行列メモリ４は、最大Ｍ個の待ち行列（キュー）４０から構成され、各待ち行列４０（４０−１、４０−２、…、４０−Ｍ）には、同一の対象ブロック番号６１を持つリクエスト５３が数珠繋ぎされて待機する構成となっている。ここで、待ち行列４０の個数Ｍは、Ｐ個のプロセッサ１２が同時に発行する可能性のあるリクエスト５３の最大数に等しい数値に設定されている。例えば、プロセッサ１２の上で３つのスレッドがそれぞれ動作しており、各スレッドが、リクエスト５３を発行する可能性があるときは、Ｍの値は、Ｍ＝３×Ｐに設定される。
【００４７】
実際には、メモリを節約するため、待ち行列４０の要素はリクエスト５３そのものではなく、リクエスト５３のサブセットである。このサブセットを待機中リクエスト４１と呼ぶ。待機中リクエスト４１は、発行元４２と、シーケンス番号４３と、種別４４とから構成され、これらは、元となったリクエスト５３の発行元６０と、シーケンス番号６２と、種別６３とにそれぞれ対応している。
【００４８】
待ち行列４０においては、待機中リクエスト４１がそのシーケンス番号４３が昇順になるように整列されて配置される。
【００４９】
次に、上記ブロックプロパティメモリ３には、共有メモリ２の各ブロック２０（２０−１、２０−２、…、２０−Ｎ）の状態が、Ｎ個のブロックプロパティ３０（３０−１、３０−２、…、３０−Ｎ）の配列形式で、保持されている。ブロックプロパティ３０−Ｘ（１≦Ｘ≦Ｎ）は、ブロック２０−Ｘに対応している。各ブロックプロパティ３０は、４つの要素（ブロック先頭アドレス３１、ブロック長３２、シーケンス番号の期待値３３、待ち行列へのポインタ３４）からなる構造体である。
【００５０】
ブロックプロパティ３０−Ｘ（１≦Ｘ≦Ｎ）のブロック先頭アドレス３１とブロック長３２には、共有メモリ２におけるブロック２０−Ｘの先頭アドレスとサイズが、それぞれ収容されている。なお、Ｘ（１≦Ｘ≦Ｎ）の値からブロック２０−Ｘの先頭アドレスとサイズを決定できるように構成されているときは、メモリを節約するため、ブロックプロパティ３０−Ｘのブロック先頭アドレス３１とブロック長３２を省略しても良い。省略可能な場合は、例えば、共有メモリ２において、Ｎ個のブロック２０（２０−１、２０−２、…、２０−Ｎ）のサイズが全て等しく、これらが等間隔に配置されているとき等は、ブロック先頭アドレス３１とブロック長３２とを省略できる。
【００５１】
ブロックプロパティ３０−Ｘ（１≦Ｘ≦Ｎ）のシーケンス番号の期待値（期待順序番号）３３は、ブロック２０−Ｘに対するアクセスが許可されるリクエスト５３のシーケンス番号６２である。言い換えると、対象ブロック番号がＸ（０≦Ｘ＜Ｎ）であるリクエスト５３のシーケンス番号６２が、ブロックプロパティ３０−（Ｘ＋１）のシーケンス番号の期待値３３と一致するときに限り、共有メモリ制御部１のアクセス調停部５（図１）に対して、このリクエスト５３の実行が許可される、ということを意味している。
【００５２】
各ブロックプロパティ３０において、ＲＥＡＤ以外のリクエスト５３の実行が完了する度に、その対象ブロック番号６１に対応するブロックプロパティ３０のシーケンス番号の期待値３３に「１」が加算される。説明を容易にするため、シーケンス番号の期待値３３の初期値を０とする。
【００５３】
ブロックプロパティ３０−Ｘ（１≦Ｘ≦Ｎ）の待ち行列へのポインタ３４には、ブロック２０−Ｘへのアクセスが保留されているリクエスト５３を保持している待ち行列４０の、待ち行列メモリ４におけるアドレス（待ち行列（キュー）識別子）が格納されている。実行が保留されているリクエスト５３が存在しないとき、待ち行列へのポインタ３４はＮＵＬＬ（無効値）を指す。待ち行列へのポインタ３４の初期値はＮＵＬＬである。
【００５４】
共有メモリ制御部１において、上記アクセス調停部５（図１）は、所定のアルゴリズムに従って受信したリクエスト５３を処理し、シーケンス番号６２による順序を意識した共有メモリ２への排他的なアクセスを実行する。この際、ブロックプロパティメモリ３と待ち行列メモリ４にアクセスする。また、必要に応じてリプライ５４を生成して発行元６０に返送する。
【００５５】
次に、図７乃至図１１参照して、アクセス調停部５の動作処理手順について説明する。
この例では、図１０に示す５つのリクエスト５３が、上から順に共有メモリ制御部１に入力されると仮定する。簡単のため、これら５つのリクエスト５３の対象ブロック番号６１は全て０とし、共有メモリ２のブロック２０−１のみがアクセス対象となるようにする。なお、図１０中には、共有メモリ制御部１が返送するリプライ５４も併記されている。
【００５６】
図１１は、初期状態及び各リクエスト５３の処理が完了した時点での、ブロックプロパティ３０−１、ブロック２０−１、待ち行列４０−１の内容を示す。この例では、初期状態におけるブロック２０−１の内容を「ＤＯＧ」とする。
【００５７】
始めに、図１０の１番目のＮＯＰリクエスト５３の処理を、図７のフローチャートのステップＳ２００から開始する。ステップＳ２００では、リクエスト５３の到着を待つ。ここでは、ＮＯＰリクエスト５３が受信される。
アクセス調停部５は、リクエスト５３を受信すると、ステップＳ２０１へ進み、受信したリクエスト５３の各要素を変数に代入する。具体的には、受信したリクエスト５３の発行元６０をＳｏｕｒｃｅに、対象ブロック番号６１をＢｌｏｃｋＮｕｍｂｅｒに、シーケンス番号６２をＳｅｑｕｅｎｃｅＮｕｍｂｅｒに、種別６３をＴｙｐｅに、書き込みデータ６４をＤａｔａに、それぞれ代入する。なお、リクエスト５３の種類によっては、発行元６０、シーケンス番号６２、書き込みデータ６４が存在しない場合があるが、その際には存在しない要素に対応する代入は行われない。この例のこの時点では、Ｓｏｕｒｃｅ＝プロセッサ１２−１、ＢｌｏｃｋＮｕｍｂｅｒ＝０、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝１、Ｔｙｐｅ＝ＮＯＰ、Ｄａｔａ＝不定となる。
【００５８】
アクセス調停部５は、次に、ステップＳ２０２へ進み、ブロックプロパティ３０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）をブロックプロパティメモリ３から読み出す。この後、読み出されたブロックプロパティ３０の各要素を変数に代入する。具体的には、ブロックプロパティ３０のブロック先頭アドレス３１をＢｌｏｃｋＡｄｄｒｅｓｓに、ブロック長３２をＢｌｏｃｋＬｅｎｇｔｈに、シーケンス番号の期待値３３をＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒに、待ち行列へのポインタ３４をＰｏｉｎｔｅｒに、それぞれ代入する。この例のこの時点では、ＢｌｏｃｋＡｄｄｒｅｓｓ＝共有メモリ２におけるブロック２０−１の先頭アドレス、ＢｌｏｃｋＬｅｎｇｔｈ＝ブロック２０−１の長さ、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０（初期値）、Ｐｏｉｎｔｅｒ＝ＮＵＬＬ（初期値）、となる。
【００５９】
アクセス調停部５は、次に、ステップＳ２０３へ進み、Ｔｙｐｅが「ＷＲＩＴＥ」であるか否かを判定し、真であれば、図８のステップＳ２４０に遷移し、偽であれば、図８のステップＳ２２０に遷移する。この例のこの時点では、Ｔｙｐｅ＝ＮＯＰであるから、この判定結果は偽となり、ステップＳ２２０に遷移する。
【００６０】
ステップＳ２２０では、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒとＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒが同値であるか否かを判定し、真であれば、ステップＳ２２４に進み、偽であれば、アクセス調停部５は、ステップＳ２２１に進む。この例のこの時点では、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝１、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０であるから、この判定結果は偽となり、ステップＳ２２１へ進む。
【００６１】
ステップＳ２２１では、ＰｏｉｎｔｅｒがＮＵＬＬであるか否かが判定される。ＰｏｉｎｔｅｒがＮＵＬＬ、すなわち、ブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）に対するアクセスが保留されているリクエスト５３が存在しないときはステップＳ２２２へ進み、Ｐｏｉｎｔｅｒが、ＮＵＬＬでなければ、ステップＳ２２３に進む。この例のこの時点では、ＰｏｉｎｔｅｒはＮＵＬＬであるから、ステップＳ２２２へ進む。
【００６２】
ステップＳ２２２において、アクセス調停部５は、待ち行列メモリ４に新たな待ち行列４０を作成し、作成した待ち行列４０のアドレスをＰｏｉｎｔｅｒに代入する。この例のこの時点では、待ち行列メモリ４における待ち行列４０−１のアドレスがＰｏｉｎｔｅｒに代入される。
【００６３】
アクセス調停部５は、ステップＳ２２３に進み、待ち行列メモリ４内の、Ｐｏｉｎｔｅｒが指し示す待ち行列４０に、待機中リクエスト４１を追加する。この際、追加される待機中リクエスト４１の発行元４２がＳｏｕｒｃｅに、シーケンス番号４３がＳｅｑｕｅｎｃｅＮｕｍｂｅｒに、種別４４がＴｙｐｅに等しくなるようにする。上記の通り、待ち行列４０中の待機中リクエスト４１は、そのシーケンス番号４３が昇順になるように整列されている必要がある。この条件が満たされるように、待機中リクエスト４１を待ち行列４０の適切な位置に追加あるいは挿入する。
【００６４】
この例のこの時点では、待ち行列４０−１に待機中リクエスト４１は１つも存在しないため、このステップでは下記内容の待機中リクエスト４１を待ち行列４０−１の先頭に追加するだけで良い。追加される待機中リクエスト４１の内容は以下の通りである：発行元４２＝プロセッサ１２−１、シーケンス番号４３＝１、種別４４＝ＮＯＰ。この後、図７のステップＳ２０４に遷移する。
【００６５】
アクセス調停部５は、ステップＳ２０４では、ブロックプロパティ３０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）のシーケンス番号３３と、待ち行列へのポインタ３４を最新の値に更新する。具体的には、シーケンス番号３３をＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒに、待ち行列へのポインタ３４をＰｏｉｎｔｅｒに更新する。この例のこの時点では、ＢｌｏｃｋＮｕｍｂｅｒ＝０であるので、更新対象は、ブロックプロパティ３０−１である。また、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０、Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレス、であるので、ブロックプロパティ３０−１のシーケンス番号３３の値は「０」のままになり、待ち行列へのポインタ３４の値がＮＵＬＬから「待ち行列４０−１のアドレス」に変化する。
【００６６】
以上の動作で、１番目のＮＯＰリクエスト５３の受信処理が完了する。１番目のＮＯＰリクエスト５３の受信処理が完了すると、ステップＳ２００に戻って新たなリクエスト５３の受信を待つ。この時点でのブロックプロパティ３０−１、ブロック２０−１、待ち行列４０−１の内容は、図１１の上から２行目のようになる。１番目のＮＯＰリクエスト５３のシーケンス番号６２は「１」であり、この値は、ブロック２０−１のシーケンス番号の期待値３３の値「０」に一致していないため、１番目のＮＯＰリクエスト５３の実行は保留されている。
【００６７】
アクセス調停部５は、次に、図１０の２番目のＲＥＡＤリクエスト５３の処理を、図７のフローチャートのステップＳ２００から開始する。冗長な説明を避けるため、１番目のＮＯＰリクエスト５３の処理との相違点のみを記載する。
アクセス調停部５は、ステップＳ２００において、２番目のＲＥＡＤリクエスト５３の受信を確認すると、ステップＳ２０１へ進み、受信したリクエスト５３の各要素を変数に代入する。
ステップＳ２０１を実行すると、Ｓｏｕｒｃｅ＝プロセッサ１２−２、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝３、Ｔｙｐｅ＝ＲＥＡＤになる。ステップＳ２０２を実行すると、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０、Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレスになる。ステップＳ２０３の判定は偽となるので、図８のステップＳ２２０に進む。ステップＳ２２０の判定も偽となるので、ステップＳ２２１に到達する。
【００６８】
ステップＳ２２１では、現在のＰｏｉｎｔｅｒはＮＵＬＬではないため、前回の実行時とは異なり判定は偽となる。ステップＳ２２２をスキップしてステップＳ２２３へと進む。つまり、既に待ち行列４０は作成されているため、ステップＳ２２２において待ち行列４０を新規作成する必要がない。
アクセス調停部５は、ステップＳ２２３において、下記内容の待機中リクエスト４１を待ち行列４０−１に追加する。追加される待機中リクエスト４１の内容は以下の通りである：発行元４２＝プロセッサ１２−２、シーケンス番号４３＝３、種別４４＝ＲＥＡＤ。
ただし、待ち行列４０−１には、シーケンス番号４３＝１、種別４４＝ＮＯＰの待機中リクエスト４１が既に存在している。このため、シーケンス番号４３が昇順になるように、新たな待機中リクエスト４１は既存の待機中リクエスト４１の直後に追加される。この後、図７のステップＳ２０４に遷移する。
【００６９】
ステップＳ２０４において、ブロックプロパティ３０−１のシーケンス番号３３と待ち行列へのポインタ３４の更新が行われるが、この例のこの時点では、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０、Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレスであり、これらはブロックプロパティメモリ３の内容と同一であるので、このステップでは、そのメモリの内容は変化しない。
【００７０】
以上の動作で、２番目のＲＥＡＤリクエスト５３の受信処理が完了する。２番目のＲＥＡＤリクエストリクエスト５３の受信処理が完了すると、アクセス調停部５は、ステップＳ２００に戻って新たなリクエスト５３の受信を待つ。この時点でのブロックプロパティ３０−１、ブロック２０−１、待ち行列４０−１の内容は、図１１の上から３行目のようになる。前回と同様に、２番目のＲＥＡＤリクエスト５３の実行も保留されている。
【００７１】
次に、アクセス調停部５は、図１０の３番目のＲＥＡＤ＿ＯＮＬＹリクエスト５３の処理を、図７のフローチャートのステップＳ２００から開始する。処理の流れは、２番目のＲＥＡＤ＿ＯＮＬＹリクエスト５３と基本的に同一である。図８のステップＳ２２３の処理のみ若干異なるため、それを説明する。アクセス調停部５は、ステップＳ２２３において、下記内容の待機中リクエスト４１を待ち行列４０−１に追加する。追加される待機中リクエスト４１の内容は以下の通りである：発行元４２＝プロセッサ１２−３、シーケンス番号４３＝２、種別４４＝「ＲＥＡＤ＿ＯＮＬＹ」。
ただし、待ち行列４０−１には、シーケンス番号４３＝１、種別４４＝ＮＯＰの待機中リクエスト４１と、シーケンス番号４３＝３、種別４４＝ＲＥＡＤの待機中リクエスト４１が既に存在している。このため、新たな待機中リクエスト４１は既存の２つの待機中リクエスト４１の間に挿入される。
【００７２】
以上で、３番目のＲＥＡＤ＿ＯＮＬＹリクエスト５３の受信処理が完了する。３番目のＲＥＡＤ＿ＯＮＬＹリクエスト５３の受信処理が完了すると、アクセス調停部５は、ステップＳ２００に戻って新たなリクエスト５３の受信を待つ。この時点でのブロックプロパティ３０−１、ブロック２０−１、待ち行列４０−１の内容は、図１１の上から４行目のようになる。前回と同様に、３番目のＲＥＡＤ＿ＯＮＬＹリクエスト５３の実行も保留されている。
【００７３】
次に、図１０の４番目のＲＥＡＤリクエスト５３の処理を、図７のフローチャートのステップＳ２００から開始する。図８のステップＳ２２０の直前までの処理は、これまでと同様である。この例では、ステップＳ２２０の直前における変数の設定値又は設定状態は次の通りである：
Ｓｏｕｒｃｅ＝プロセッサ１２−４
ＢｌｏｃｋＮｕｍｂｅｒ＝０
ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０
Ｔｙｐｅ＝ＲＥＡＤ
Ｄａｔａ＝不定
ＢｌｏｃｋＡｄｄｒｅｓｓ＝共有メモリ２におけるブロック２０−１の先頭アドレス
ＢｌｏｃｋＬｅｎｇｔｈ＝ブロック２０−１の長さ
ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０
Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレス
【００７４】
ステップＳ２２０では、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒとＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒの同値判定が行われる。この例のこの時点では両者ともに０であり、判定結果は真になるため、ステップＳ２２４に進む。これが意味するところは、リクエスト５３のシーケンス番号６２が、ブロックプロパティ３０のシーケンス番号の期待値３３と一致したため、そのリクエスト５３の実行が許可されたということである。
【００７５】
ステップＳ２２４では、図９に示すＲＥＡＤ、ＲＥＡＤ＿ＯＮＬＹ、ＮＯＰ処理サブルーチンが呼び出される。このサブルーチンの大部分は、後述するＷＲＩＴＥ処理サブルーチンと共用されているため、サブルーチンの実行開始位置は２箇所存在している。このサブルーチンが、ステップＳ２２４から呼び出されるときは、ステップＳ２６０が開始位置となる。
【００７６】
アクセス調停部５は、ステップＳ２６０において、ＤａｔａＲｅａｄｙフラグを偽にする。このフラグは、共有メモリ２の二度読みを防止するためのもので、ブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）の内容がＤａｔａに反映された時点で、このフラグは真になる。ステップＳ２６０の実行時点では、Ｄａｔａは不定であるから、このフラグは偽にセットされる。
【００７７】
次に、アクセス調停部５は、ステップＳ２６１に進み、ＴｙｐｅがＮＯＰであるか否かを判定し、判定結果が真であれば、ステップＳ２８１に遷移し、偽であれば、ステップＳ２６２に遷移する。この例のこの時点ではＴｙｐｅ＝ＲＥＡＤであるから、この判定結果は偽になり、ステップＳ２６２に進む。
【００７８】
ステップＳ２６２では、ＤａｔａＲｅａｄｙフラグの真偽が判定される。アクセス調停部５は、真であれば、ステップＳ２６５へジャンプし、偽であれば、ステップＳ２６３に進む。この例のこの時点ではＤａｔａＲｅａｄｙは偽であるから、アクセス調停部５は、ステップＳ２６３に進む。
【００７９】
アクセス調停部５は、ステップＳ２６３では、共有メモリ２のブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）の内容を読み出し、それをＤａｔａに格納する。読み出しを開始するアドレスと読み出す長さは、それぞれＢｌｏｃｋＡｄｄｒｅｓｓとＢｌｏｃｋＬｅｎｇｔｈによって示される。この例のこの時点では、ブロック２０−１の内容が読み出されてＤａｔａ＝「ＤＯＧ」となる。次に、アクセス調停部５は、ステップＳ２６４に進み、ＤａｔａＲｅａｄｙフラグを真にする。
【００８０】
次に、アクセス調停部５は、ステップＳ２６５に進み、宛先７０がＳｏｕｒｃｅであって、読み出しデータ７１がＤａｔａであるリプライ５４を作成し、ステップＳ２６６でそのリプライ５４を送信する。この例のこの時点では、Ｓｏｕｒｃｅ＝プロセッサ１２−４、Ｄａｔａ＝ＤＯＧであるから、４番目のＲＥＡＤリクエスト５３の発行元６０であるプロセッサ１２−４に向けて読み出しデータ７１として「ＤＯＧ」を含むリプライ５４が返送される。
【００８１】
アクセス調停部５は、ステップＳ２６７に進み、Ｔｙｐｅが「ＲＥＡＤ」であるか否かが判定される。真であれば、ステップＳ２６８に遷移し、偽であれば、ステップＳ２８１に遷移する。この例のこの時点では、Ｔｙｐｅ＝ＲＥＡＤであるから判定結果は真であり、ステップＳ２６８に進む。
【００８２】
ステップＳ２６８では、ＷｒｉｔｅＢａｃｋフラグが偽にセットされる。このフラグはＷＲＩＴＥリクエスト５３の処理に限って意味を持つため、ここでは、その説明を省略する。アクセス調停部５は、ステップＳ２６９に進み、このサブルーチンを抜けて呼び出し元に復帰する。この例のこの時点では、このサブルーチンは、図８のステップＳ２２４から呼び出されている。ステップＳ２２４の次のステップは、先の図７のステップＳ２０４である。
【００８３】
ステップＳ２０４において、ブロックプロパティ３０−１のシーケンス番号３３と待ち行列へのポインタ３４の更新が行われるが、この例のこの時点では、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０、Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレスであり、これらはブロックプロパティメモリ３の内容と同一であるので、このステップでは、そのメモリの内容は変化しない。
【００８４】
以上で、４番目のＲＥＡＤリクエスト５３の処理が完了する。４番目のＲＥＡＤリクエスト５３の処理が完了すると、アクセス調停部５は、ステップＳ２００に戻って新たなリクエスト５３の受信を待つ。この時点でのブロックプロパティ３０−１、ブロック２０−１、及び待ち行列４０−１の内容は、図１１の上から５行目のようになる。４番目のＲＥＡＤリクエスト５３は実行されたが、待ち行列４０−１の中に３つの待機中リクエスト４１が残存したままになる。この状態は、ＷＲＩＴＥリクエスト５３がアクセス調停部５に到着し、それが処理されるまで継続する。
【００８５】
最後に、アクセス調停部５は、図１０の５番目のＷＲＩＴＥリクエスト５３の処理を、図７のフローチャートのステップＳ２００から開始する。ステップＳ２０３の直前までの処理は、これまでと同様である。この例では、ステップＳ２０３の直前における変数の設定値又は設定状態は次の通りである：
Ｓｏｕｒｃｅ＝不定
ＢｌｏｃｋＮｕｍｂｅｒ＝０
ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝不定
Ｔｙｐｅ＝”ＷＲＩＴＥ”
Ｄａｔａ＝「ＣＡＴ」
ＢｌｏｃｋＡｄｄｒｅｓｓ＝共有メモリ２におけるブロック２０−１の先頭アドレス
ＢｌｏｃｋＬｅｎｇｔｈ＝ブロック２０−１の長さ
ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝０
Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレス
【００８６】
ステップＳ２０３では、Ｔｙｐｅが「ＷＲＩＴＥ」であるか否かが判定される。この例のこの時点では、Ｔｙｐｅ＝ＷＲＩＴＥであるので、この判定結果は真となり、アクセス調停部５は、図８のステップＳ２４０に遷移する。
【００８７】
ステップＳ２４０では、図９に示すＷＲＩＴＥ処理サブルーチンが呼び出される。このサブルーチンがステップＳ２４０から呼び出されるときは、ステップＳ２８０が開始位置となる。
【００８８】
アクセス調停部５は、ステップＳ２８０において、ＤａｔａＲｅａｄｙフラグを真にセットし、ＷＲＩＴＥリクエスト５３の処理が完了するまでの間、共有メモリ２のブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）の読み出しを禁止してＤａｔａの内容が破壊されることを防止する。この読み出しを禁止する理由は、ブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）の現内容よりも、ＷＲＩＴＥリクエスト５３の書き込みデータ６４、すなわちＤａｔａの方が新しいからである。
【００８９】
アクセス調停部５は、ステップＳ２８１に進み、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒに「１」を加算する。この例のこの時点では、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒは「０」から「１」に変化する。
【００９０】
次に、ステップＳ２８２に進み、ＰｏｉｎｔｅｒがＮＵＬＬであるか否かが判定される。ＮＵＬＬであれば、アクセス調停部５はステップＳ２８６に遷移し、ＮＵＬＬでなければ、ステップＳ２８３に遷移する。この例のこの時点では、Ｐｏｉｎｔｅｒ＝待ち行列４０−１のアドレスであってＮＵＬＬではないため、アクセス調停部５はステップＳ２８３に進む。
【００９１】
アクセス調停部５は、ステップＳ２８３では、Ｐｏｉｎｔｅｒが指し示す待ち行列４０の先頭の待機中リクエスト４１を読み出し、その各要素を変数に代入する。具体的には、待機中リクエスト４１の発行元４２をＳｏｕｒｃｅに、シーケンス番号４３をＳｅｑｕｅｎｃｅＮｕｍｂｅｒに、種別４４をＴｙｐｅに、それぞれ代入する。なお、このステップは、待機中リクエスト４１の内容を読み出すのみであって待ち行列４０を改変しない。この例のこの時点では、Ｐｏｉｎｔｅｒが指す待ち行列４０−１の先頭の待機中リクエスト４１が読み出され、Ｓｏｕｒｃｅ＝プロセッサ１２−１、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝１、Ｔｙｐｅ＝ＮＯＰになる。
【００９２】
ステップＳ２８４では、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒとＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒの同値判定が行われる。同値であれば、アクセス調停部５はステップＳ２８５に遷移し、同値でなければ、ステップＳ２８６に遷移する。この例のこの時点では、両者ともに「１」であり、判定結果は真になるため、アクセス調停部５はステップＳ２８５に進む。これは、待機中リクエスト４１のシーケンス番号４３が、ブロックプロパティ３０のシーケンス番号の期待値３３と一致したため、その待機中リクエスト４１の実行が許可されたことを意味する。
【００９３】
次に、アクセス調停部５はステップＳ２８５へ進み、Ｐｏｉｎｔｅｒが指し示す待ち行列４０の先頭の待機中リクエスト４１を削除する。さらに、削除の結果、その待ち行列４０が空になった場合、ＰｏｉｎｔｅｒにＮＵＬＬを代入する。この例のこの時点では、削除しても待ち行列４０−１に待機中リクエスト４２が２つ残るため、Ｐｏｉｎｔｅｒは待ち行列４０−１を指したままになる。この後、アクセス調停部５はステップＳ２６１に戻る。
【００９４】
このように、このサブルーチンにはループが構成されており、ステップＳ２６８又はステップＳ２８６に到達するまで、このサブルーチン内の処理は繰り返される。基本的には、Ｐｏｉｎｔｅｒが指し示す待ち行列４０の中に待機中リクエスト４１が存在し、かつ、その待ち行列４０の先頭の待機中リクエスト４１のシーケンス番号４３がＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒと一致し続ける限り、その待ち行列４０内の待機中リクエスト４１は先頭から順次実行されていく。ただし、ＲＥＡＤリクエスト５３の実行が完了すると、そのときの待機中リクエスト４１の有無に関わらずループから必ず抜ける（ステップＳ２６７）。
【００９５】
次に、ＲＥＡＤを例外扱いとしている理由について説明する。
ＲＥＡＤリクエスト５３の動作説明で述べたように、ＲＥＡＤリクエスト５３が実行されてリプライ５４が発行元６０に返送されると、その発行元６０は、ＷＲＩＴＥリクエスト５３を必ず発行しなければならない。このＷＲＩＴＥリクエスト５３によって共有メモリ２の内容が書き換わる可能性がある。したがって、ＲＥＡＤリクエスト５３に対応するＷＲＩＴＥリクエスト５３の処理が完了する前に、待機中リクエスト４１を先行して実行することは、処理の正当性を失わせる畏れがあるため許容すべきではない。それゆえ、この実施形態では、ＲＥＡＤリクエスト５３の実行が完了した時点でループを終了し、後続の待機中リクエスト４１が実行されないようにしている。
【００９６】
ステップＳ２６１の説明に復帰する。ステップＳ２６１では、ＴｙｐｅがＮＯＰであるか否かが判定される。この例のこの時点では、Ｔｙｐｅ＝ＮＯＰであるから、この判定結果は真になり、アクセス調停部５はステップＳ２８１に進む。ステップＳ２８３の直前までは前回と同様であるので、説明を省略する。ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒは「２」になる。
【００９７】
ステップＳ２８３では、Ｐｏｉｎｔｅｒが指す待ち行列４０−１の先頭の待機中リクエスト４１が読み出され、Ｓｏｕｒｃｅ＝プロセッサ１２−３、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝２、Ｔｙｐｅ＝ＲＥＡＤ＿ＯＮＬＹになる。
【００９８】
ステップＳ２８４において、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒとＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒの同値判定が行われる。この例のこの時点では、両者ともに「２」であり、判定結果は真になるため、アクセス調停部５はステップＳ２８５に進む。
【００９９】
ステップＳ２８５において、Ｐｏｉｎｔｅｒが指し示す待ち行列４０の先頭の待機中リクエスト４１が削除されるが、削除後も待ち行列４０−１に待機中リクエスト４２が１つ残るため、Ｐｏｉｎｔｅｒは待ち行列４０−１を指したままになる。この後、アクセス調停部５はステップＳ２６１に戻る。
【０１００】
ステップＳ２６１では、ＴｙｐｅがＮＯＰであるか否かが判定される。この例のこの時点では、Ｔｙｐｅ＝ＲＥＡＤ＿ＯＮＬＹであるから、この判定結果は偽になり、アクセス調停部５はステップＳ２６２に進む。
【０１０１】
ステップＳ２６２では、ＤａｔａＲｅａｄｙフラグの真偽が判定される。この例のこの時点では、ＤａｔａＲｅａｄｙは真であるから、アクセス調停部５はステップＳ２６３とステップＳ２６４をスキップし、ステップＳ２６５にジャンプする。
【０１０２】
ステップＳ２６５とステップＳ２６６において、リプライ５４の生成と送信が行われる。この例のこの時点では、Ｓｏｕｒｃｅ＝プロセッサ１２−３、Ｄａｔａ＝「ＣＡＴ」であるから、３番目のＲＥＡＤ＿ＯＮＬＹリクエスト５３の発行元６０であるプロセッサ１２−３に向けて読み出しデータ７１として「ＣＡＴ」を含むリプライ５４が返送される。
【０１０３】
ステップＳ２６７に進み、Ｔｙｐｅが「ＲＥＡＤ」であるか否かが判定される。この例のこの時点では、Ｔｙｐｅ＝ＲＥＡＤ＿ＯＮＬＹであるから判定結果は偽であり、アクセス調停部５はステップＳ２８１に進む。ステップＳ２８３の直前までは前回と同様であるので、説明を省略する。ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒは「３」になる。
【０１０４】
ステップＳ２８３では、Ｐｏｉｎｔｅｒが指す待ち行列４０−１の先頭の待機中リクエスト４１が読み出され、Ｓｏｕｒｃｅ＝プロセッサ１２−２、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝３、Ｔｙｐｅ＝ＲＥＡＤになる。
【０１０５】
ステップＳ２８４において、ＳｅｑｕｅｎｃｅＮｕｍｂｅｒとＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒの同値判定が行われる。この例のこの時点では、両者ともに３であり、判定結果は真になるため、アクセス調停部５はステップＳ２８５に進む。ステップＳ２８５において、Ｐｏｉｎｔｅｒが指し示す待ち行列４０の先頭の待機中リクエスト４１が削除される。この結果、待ち行列４０−１に待機中リクエスト４２が１つも存在しない状態になるため、Ｐｏｉｎｔｅｒは、ＮＵＬＬにセットされる。この後、アクセス調停部５はステップＳ２６１に戻る。
【０１０６】
ステップＳ２６１では、ＴｙｐｅがＮＯＰであるか否かが判定される。この例のこの時点では、Ｔｙｐｅ＝ＲＥＡＤであるから、この判定結果は偽になり、アクセス調停部５はステップＳ２６２に進む。ステップＳ２６２では、ＤａｔａＲｅａｄｙフラグの真偽が判定される。この例のこの時点では、ＤａｔａＲｅａｄｙは真であるから、アクセス調停部５は、ステップＳ２６３とステップＳ２６４をスキップし、ステップＳ２６５にジャンプする。
【０１０７】
ステップＳ２６５とステップＳ２６６において、リプライ５４の生成と送信が行われる。この例のこの時点では、Ｓｏｕｒｃｅ＝プロセッサ１２−２、Ｄａｔａ＝「ＣＡＴ」であるから、２番目のＲＥＡＤリクエスト５３の発行元６０であるプロセッサ１２−２に向けて読み出しデータ７１として「ＣＡＴ」を含むリプライ５４が返送される。
【０１０８】
ステップＳ２６７に進み、Ｔｙｐｅが「ＲＥＡＤ」であるか否かが判定される。この例のこの時点では、Ｔｙｐｅ＝ＲＥＡＤであるから判定結果は真であり、アクセス調停部５は、ループを抜けてステップＳ２６８に進む。ステップＳ２６８では、ＷｒｉｔｅＢａｃｋフラグが偽にセットされる。このフラグは、共有メモリ２のブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）にＤａｔａの内容を書き込む必要があるとき、真にセットされる。
【０１０９】
次に、アクセス調停部５は、ステップＳ２６９に進み、このサブルーチンを抜けて呼び出し元に復帰する。この例のこの時点では、このサブルーチンは図８のステップＳ２４０から呼び出されているため、次のステップはステップＳ２４１になる。
【０１１０】
ステップＳ２４１では、ＷｒｉｔｅＢａｃｋフラグの真偽判定が行われる。真であれば、アクセス調停部５はステップＳ２４２に進み、偽であれば、ステップＳ２４２はスキップされる。この例のこの時点では、ＷｒｉｔｅＢａｃｋは偽であるから、アクセス調停部５は、ステップＳ２４２はスキップされ、図７のステップＳ２０４に遷移する。
【０１１１】
ステップＳ２０４において、ブロックプロパティ３０−１のシーケンス番号３３と待ち行列へのポインタ３４の更新が行われる。この例のこの時点では、ＥｘｐｅｃｔｅｄＳｅｑｕｅｎｃｅＮｕｍｂｅｒ＝３、Ｐｏｉｎｔｅｒ＝ＮＵＬＬであるから、ブロックプロパティ３０−１のシーケンス番号３３と待ち行列へのポインタ３４は、３とＮＵＬＬにそれぞれ更新される。
以上で５番目のＷＲＩＴＥリクエスト５３の処理は完了し、アクセス調停部５は、ステップＳ２００に戻って新たなリクエスト５３の受信を待つ。この時点でのブロックプロパティ３０−１、ブロック２０−１、待ち行列４０−１の内容は、図１１の上から６行目のようになる。
【０１１２】
この例では、図８のステップＳ２４２及び図９のステップＳ２８６が実行されなかったので、次に、これらの処理内容について説明する。
アクセス調停部５は、ステップＳ２４２において、共有メモリ２のブロック２０−（ＢｌｏｃｋＮｕｍｂｅｒ＋１）にＤａｔａの内容を書き込む。書き込みを開始するアドレスと書き込む長さは、それぞれＢｌｏｃｋＡｄｄｒｅｓｓとＢｌｏｃｋＬｅｎｇｔｈによって示される。この後、アクセス調停部５は、図７のステップＳ２０４に進む。一方、ステップＳ２８６では、アクセス調停部５は、ＷｒｉｔｅＢａｃｋフラグを真にセットした後、ステップＳ２６９に遷移する。
【０１１３】
ここで、アクセス調停部５の性質について述べる。
この例では、書き込みデータ６４が「ＣＡＴ」であるＷＲＩＴＥリクエスト５３を処理した。しかし、図１１から明らかなように、共有メモリ２のブロック２０−１の内容は「ＤＯＧ」のままである。一見すると、「ＣＡＴ」という情報が失われてブロック２０−１の内容に不整合が生じているようであるが、実際にはそうではない。「ＣＡＴ」という情報は、図１０に示すように、共有メモリ制御部１が最後に送信した３番目のリプライ５４の中に読み出しデータ７１として保存されている。３番目のリプライ５４は、２番目のＲＥＡＤリクエスト５３に対応するものである。
【０１１４】
２番目のＲＥＡＤリクエスト５３の発行元６０は、３番目のリプライ５４の受信後に、ＷＲＩＴＥリクエスト５３（図１０には図示されていない）を発行する責任を負う。つまり、ＲＥＡＤリクエスト５３に対応するリプライ５４が返送された時点で、ＷＲＩＴＥリクエスト５３の受信が確定する。このＷＲＩＴＥリクエスト５３によって共有メモリ２の内容が後になって書き換わることが既知であれば、それより前に共有メモリ２の同じ領域を書き換える必要が無いことは明白である。むしろ、共有メモリ２の負荷を下げて性能を向上させるため、共有メモリ２への冗長なアクセスを抑制すべきである。
【０１１５】
この目的のためにアクセス調停部５は、ＷＲＩＴＥリクエスト５３の到着を契機として実行された待機中リクエスト４１のうち、最後に実行された待機中リクエスト４１の種別４４が「ＲＥＡＤ」であったとき、そのＷＲＩＴＥリクエスト５３による共有メモリ２の更新処理（ステップＳ２４２）をスキップするようにしている。
【０１１６】
また、この例では、共有メモリ２へのアクセスを発生させる可能性のあるリクエスト５３が計４回発行されているが（ＲＥＡＤが２回、ＲＥＡＤ＿ＯＮＬＹが１回、ＷＲＩＴＥが１回）、実際に発生したアクセスは１回だけである。共有メモリ２へのアクセスが１回しか発生しなかった理由は、アクセス調停部５がＷＲＩＴＥリクエスト５３の到着を契機として３つの待機中リクエスト４１を連続して実行し、これらの実行の際に共有メモリ２からデータを読み出す代わりに、受信したＷＲＩＴＥリクエスト５３の中の書き込みデータ６４を参照したからである。
【０１１７】
一般化すると、アクセス調停部５においては、ＷＲＩＴＥに限らず、何らかのリクエスト５３の到着を契機として１つ以上の待機中リクエスト４１が連続して実行されるとき、共有メモリ２へのアクセスは、合計で高々１回しか発生しない。このことについて、アクセス調停部５の動作のフローチャート（図７乃至図９）を参照して説明する。共有メモリ２からの読み出しアクセスは図９のステップＳ２６３にて、書き込みアクセスは図８のステップＳ２４２にて、それぞれ行われる。
【０１１８】
まず、共有メモリ２からの読み出しに着目する。上記したように、図９のサブルーチンにはループが存在し、待ち行列４０の先頭の待機中リクエスト４１の実行条件が満たされ続ける限り、ステップＳ２８５からループの先頭であるステップＳ２６１に戻って処理が継続する。ここで、共有メモリ２からの読み出しを行うステップＳ２６３が実行されるためには、ＤａｔａＲｅａｄｙフラグが偽でなければならない（ステップＳ２６２）。ステップＳ２６３が実行されると、ＤａｔａＲｅａｄｙフラグは必ず真にセットされる（ステップＳ２６４）。したがって、何度ループしてもステップＳ２６３は一度しか実行されない。また、ＷＲＩＴＥリクエスト５３の処理中に図９のサブルーチンが呼び出された場合、冒頭でステップＳ２８０が実行されてＤａｔａＲｅａｄｙフラグが真にセットされるため、ＷＲＩＴＥリクエスト５３の処理中にステップＳ２６３が実行されることは有り得ない。したがって、ＷＲＩＴＥリクエスト５３の処理中に共有メモリ２からの読み出しは一度も発生せず、ＷＲＩＴＥ以外のリクエスト５３の処理中に共有メモリ２からの読み出しは高々１回しか発生しない。
【０１１９】
次に、共有メモリ２への書き込みに着目する。共有メモリ２への書き込みを行うステップＳ２４２が実行されるためには、アクセス調停部５が受信したリクエスト５３の種別６３が”ＷＲＩＴＥ”でなければならない（図７のステップＳ２０３）。すなわち、ステップＳ２４２はＷＲＩＴＥリクエスト５３の固有の処理の一部である。さらに、ステップＳ２４１の判定結果次第ではステップＳ２４２の実行がスキップされる可能性がある。したがって、ＷＲＩＴＥリクエスト５３の処理中に共有メモリ２への書き込みは高々１回しか発生せず、ＷＲＩＴＥ以外のリクエスト５３の処理中に共有メモリ２への書き込みは一度も発生しない。
【０１２０】
それゆえ、アクセス調停部５においては、何らかのリクエスト５３の到着を契機として１つ以上の待機中リクエスト４１が連続して実行されるとき、共有メモリ２へのアクセスは合計で高々１回しか発生しないことになる。
【０１２１】
上述のように、共有メモリ制御部１は、複数の待機中リクエスト４１をまとめて処理可能な状況が発生すればするほど、共有メモリ２の負荷を低下させてリクエスト５３の処理能力を向上させることができる。このような状況は、処理システム６においてプロセッサ１２−１〜１２−Ｐがリクエスト５３を共有メモリ制御部１に頻繁に発行し、待ち行列メモリ４の待ち行列４０に複数の待機中リクエスト４１が滞留している場合に起きやすい。つまり、処理システム６全体の負荷が高いとき、共有メモリ制御部１の処理効率は相対的に上がる傾向があると言える。
【０１２２】
アクセス調停部５の動作説明の具体例においては、説明を容易にするため、共有メモリ２のブロック２０−１のみをアクセス対象としたが、実際には、プロセッサ１２（１２−１、１２−２、…、１２−Ｐ）は同時に複数のブロック２０にアクセス可能である。この際、アクセス対象のブロック２０、すなわち、対象ブロック番号６１が互いに異なる２つ以上のリクエスト５３の間では、排他制御は一切行われない。
【０１２３】
以上、この発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更等があってもこの発明に含まれる。例えば、上述の実施形態では、この発明をパケット入力の通信システムに適用する場合について述べたが、これに限らず、順序依存性を有する処理である限り、他用途の並列処理システムにも適用できる。
【０１２４】
例えば、この実施形態では、共有メモリ制御部１のアプリケーションとして通信を仮定したが、本質的には通信に限定されない。処理システム６の入力であるパケット５０を「処理対象」に、通信におけるフローを「互いに関連する処理対象の集合」にそれぞれ読み替えれば、順序依存性を有する何らかの処理を処理システム６を用いて実現できる。
【０１２５】
また、この実施形態による共有メモリ制御部１は、順序を意識した共有メモリアクセス排他制御の機能を提供するものであるが、改変なしにメモリ以外の共有リソースについても順序を意識した排他制御を行うことができる。その際の共有メモリ制御部１の利用方法を説明する。
【０１２６】
まず、共有メモリ２のブロック２０と共有リソースとを対応付ける。排他制御される共有リソースが複数存在する場合は、それぞれの共有リソースに異なるブロック２０を重複なく、割り当てる。次に、共有リソースの使用権を獲得したいプロセッサ１２は、その共有リソースに対応するブロック２０を対象としたＲＥＡＤリクエスト５３を共有メモリ制御部１に発行する。そのプロセッサ１２は、共有メモリ制御部１からのリプライ５４の受信をもって、共有リソースの獲得に成功したと判断する。共有リソースを利用した後、そのプロセッサ１２は、共有リソースに対応するブロック２０を対象としたＷＲＩＴＥリクエスト５３を発行して共有リソースを解放する。
【産業上の利用可能性】
【０１２７】
この発明は、複数のプロセッサが存在する環境下で順序依存性を有するデータ処理を並列実行するデータ処理システムに広く適用できる。
【図面の簡単な説明】
【０１２８】
【図１】この発明による共有メモリ制御方法を実現する構成の例を示すブロック図である。
【図２】共有メモリ２の内部構造の一例を示す説明図である。
【図３】ブロックプロパティメモリ３の内部構造の一例を示す説明図である。
【図４】待ち行列メモリ４の内部構造の一例を示す説明図である。
【図５】フロー識別部１０の動作例を示す説明図である。
【図６】リクエスト５３及びリプライ５４のフォーマットの一例を示す説明図である。
【図７】アクセス調停部５の動作例を示すフローチャートである。
【図８】アクセス調停部５の動作例を示すフローチャートである。
【図９】アクセス調停部５の動作例を示すフローチャートである。
【図１０】アクセス調停部５に入力されるリクエスト５３とアクセス調停部５が出力するリプライ５４の具体例を示す説明図である。
【図１１】アクセス調停部５が図１０のリクエスト５３を処理する際の、共有メモリ２、ブロックプロパティメモリ３、待ち行列メモリ４の内容を時系列順に示す説明図である。
【図１２】時分割並列化の説明図である。
【図１３】空間分割並列化の説明図である。
【符号の説明】
【０１２９】
１      共有メモリ制御部
２      共有メモリ
３      ブロックプロパティメモリ
４      待ち行列メモリ
５      アクセス調停部
６      処理システム
１０      フロー識別部
１１      分配器
１２−１、１２−２、…、１２−Ｐ      プロセッサ
１３      接続網
２０−１、２０−２、…、２０−Ｎ      ブロック
３０−１、３０−２、…、３０−Ｎ      ブロックプロパティ
３１      ブロック先頭アドレス
３２      ブロック長
３３      シーケンス番号の期待値
３４      待ち行列へのポインタ
４０−１、４０−２、…、４０−Ｍ      待ち行列
４１      待機中リクエスト
４２      発行元
４３      シーケンス番号
４４      種別
５０      パケット
５１      フロー番号
５２      シーケンス番号
５３      リクエスト
５４      リプライ
６０      発行元
６１      対象ブロック番号
６２      シーケンス番号
６３      種別
６４      書き込みデータ
７０      宛先
７１      読み出しデータ
【図１】
0005309703.tif 000002
【図２】
0005309703.tif 000003
【図３】
0005309703.tif 000004
【図４】
0005309703.tif 000005
【図５】
0005309703.tif 000006
【図６】
0005309703.tif 000007
【図７】
0005309703.tif 000008
【図８】
0005309703.tif 000009
【図９】
0005309703.tif 000010
【図１０】
0005309703.tif 000011
【図１１】
0005309703.tif 000012
【図１２】
0005309703.tif 000013
【図１３】
0005309703.tif 000014