(57)【要約】      （修正有）【課題】キャッシュメモリを用いずに共有メモリに同時アクセス可能なマルチプロセッサシステムを構成し、高性能かつ低コストのマルチプロセッサシステムを提供する。【解決手段】共有メモリを複数バンクに分割し、各メモリバンクに個別のプロセッサ要素を接続する。プロセッサ要素は接続されたメモリバンクから命令コードとオペランドを受け取り、演算を実行した後、演算結果を隣接するプロセッサ要素に送付し、次の命令実行時のアキュムレータの値とする。プロセッサ要素は、レジスタファイルがないためプロセッサ要素間で必要となるデータ転送はアキュムレータとプログラムカウンタおよび少数の制御信号のみである。複数のプロセッサが通常の演算命令を順次実行する限りにおいて命令コードおよびオペランドの同時読み出しアクセスが衝突することはなく、調停が必要となるのは共有メモリのランダムアクセス時およびジャンプ命令実行時のみである。【選択図】図１
2014016773.tif 000002
【特許請求の範囲】
【請求項１】
複数のプロセッサバンクを有するマルチプロセッサシステムにおいて、各プロセッサバンクは、対応するメモリバンクをそれぞれ有し、各プロセッサバンクは、前記対応するメモリバンクからのメモリ出力信号線を介して、命令コード及び１語長のオペランドが即値として読みこまれ、更なるレジスタを介することなく第１の処理を実行することを特徴とするマルチプロセッサシステム。
【請求項２】
請求項１において、複数のメモリバンクは、１つのメモリユニットからなり、このメモリユニットにおいて下位ビットが異なるアドレスが付されることによって、各プロセッサバンク毎にメモリバンクが割り当てられていることを特徴とするマルチプロセッサシステム。
【請求項３】
請求項１または２において、各プロセッサは、第１の処理の実行後、ジャンプ命令及び状態信号の結果をプログラムカウンタ信号として、かつ、演算命令の結果をアキュムレータ信号として、次のプロセッサに送信することを特徴とするマルチプロセッサシステム。
【請求項４】
請求項１乃至３のいずれかにおいて、プログラムカウンタの下位ビットを除いた部分が予め次のメモリバンクに送信され、次のアドレスに対する命令及びオペランドのフェッチの際に用いられることを特徴とするマルチプロセッサシステム。
【請求項５】
請求項１乃至４のいずれかににおいて、前記第１の処理は、アキュムレータの値とオペランドの値の２項演算に基づいて行われ、演算結果がアキュムレータ信号として次のプロセッサに出力されることを特徴とするマルチプロセッサシステム。
【請求項６】
請求項１乃至５のいずれかにおいて、メモリバンク上のオペランドを読み込み前に書き換えておくことにより、汎用レジスタとして用いることが可能であることを特徴とするマルチプロセッサシステム。
【請求項７】
請求項１乃至６のいずれかにおいて、メモリバンク上のオペランドの書き換えの際、対象メモリバンクにおけるオペランドの読み込みまでライトバック処理を遅延させることを特徴とするマルチプロセッサシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のプロセッサが同時に共有メモリにアクセスするためのメモリバンク分割法および、それを低コストで実現するためのプロセッサアーキテクチャに関する。特に、資源制約の厳しい組み込み型装置やマイクロコントローラにおけるマルチプロセッサ応用に関する。
【背景技術】
【０００２】
従来より、共有メモリを有するマルチプロセッサシステムにおいて、命令フェッチ等に伴うメモリの同時アクセスを確保するために、プロセッサ要素毎にキャッシュメモリを実装する方式が広く用いられてきている。
【０００３】
プロセッサ間通信のため、各キャッシュメモリは全体で同一のメモリイメージを保持する必要があり、これをキャッシュ一貫性と呼ぶ。このキャッシュ一貫性の確保のため、他のプロセッサによるメモリアクセスを監視し、対応する箇所のキャッシュを更新または無効化する必要がある。これはバススヌーピングと呼ばれる技法であるが、事実上マルチポートメモリを構成することになり、回路実装のハードウェアコストは相応に大きい。
【０００４】
シングルプロセッサ構成のマイクロコントローラ等の応用において、マルチタスクによるサービスはイベントあるいはタイマーに起因する割り込みにより処理が実施される場合が多い。割り込み処理においては状態の退避に伴うレジスタ等の保存と復帰が必要であり、相応の負荷が生じる。
【特許文献１】特開平５−２３３４４３
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来よりシングルプロセッサ構成のマイクロコントローラ等の応用において、マルチタスクによるサービスはイベントあるいはタイマーに起因する割り込みにより処理が実施される場合が多いが、割り込みが一時的に集中した場合に要求したタイミング条件を満たせない、また割り込み発生時および復帰時の状態保存および復帰のオーバーヘッドによりシステムの処理性能が低下するといった問題が発生していた。
【０００６】
マルチプロセッサによるマルチタスク処理は割り込み処理に伴う負荷が軽減され、さらに並列処理による性能向上が期待されることから、組み込み型装置やマイクロコントローラへの応用においてメリットが大きいと考えられる。しかし、現状ではハードウェア規模の制約等により、大半はシングルプロセッサ上での割り込み処理によるマルチタスクに留まっている。
【０００７】
現状において、共有メモリを持つマルチプロセッサシステム上でのメモリアクセスは、プロセッサ毎に専用のキャッシュメモリを持ち、キャッシュ一貫性を保持することでメモリアクセスのバンド幅を確保している。しかしこれはハードウェア資源に余裕のある大規模なシステム向けの構成であり、小規模な構成においてハードウェアコストを上回るメリットを得ることは難しい。
【０００８】
資源制約の厳しいマイクロコントローラや組み込みシステムにおいて、キャッシュ一貫性に伴うコストは重要な問題であり、マルチプロセッサシステムの導入において最大の障害である。もしこの障害の除去が可能であれば、産業上大きな利益をもたらすであろう。
【０００９】
本発明は、前記の事情に鑑みてなされたもので、共有メモリをレジスタとして利用できるアーキテクチャのプロセッサ要素を用いることにより、ハードウェア規模の限定された状況においても利用可能である、高性能かつ低コストであるマルチプロセッサシステムを提供することを目的とする。
【００１０】
なお、本発明はハイパフォーマンスコンピューティングへの応用においても、プロセッサ間接続バスの単純化および、共有メモリアクセス調停回路の単純化の技術として応用が可能である。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために、本発明のマルチプロセッサシステムにおいて共有メモリはアドレス空間の下位ビットに応じて複数バンクに分割され、各メモリバンクには個別のプロセッサ要素が接続される。
【００１２】
実行状態にあるプロセッサ要素は接続されたメモリバンクから命令コードと１語長のオペランドを読出し、付属の演算装置にてアキュムレータとオペランドの値を入力とした２項演算を実行する。
【００１３】
演算を実行したプロセッサ要素は次の命令アドレスに対応するメモリバンクに接続されたプロセッサ要素に演算結果および次のプログラムカウンタ値を送出し、実行状態を委譲する。演算結果を受け取ったプロセッサ要素は実行状態となり、受け取った演算結果をアキュムレータの値として次の命令実行時に２項演算を実行する。
【００１４】
演算結果、プログラムカウンタ値、実行状態の委譲等に伴うデータ送付は、プロセッサ要素間を直接接続したバス配線を通して実施される。当該バス配線は隣接したアドレスに対応するバンクのプロセッサ同士のみが接続され、全体で環状の接続構造となる。
【００１５】
本発明におけるプロセッサ要素は従来のプロセッサの構造とは異なり、アキュムレータやプログラムカウンタ等の最小限のレジスタを除き、巨大なレジスタファイルを持たない。この構造により、少数のバス接続のみで他のプロセッサ要素に全ての内部状態を委譲することができる。
【００１６】
プロセッサ要素の命令コードには、演算命令の他に指定したアドレスのオペランド値を書き換える命令がある。この命令により任意のオペランド値を実行前に変更できることから、全てのオペランドをレジスタとして利用することが可能となる。
【００１７】
各メモリバンクは読み出し専用のポートを持ち、命令コードとオペランドの読み出しはそのポートから行う。そして、これとは別に書き込み可能なポートを持ち、これらのポートは同時にアクセスが可能であるものとする。このようなデュアルポート構成のメモリは、現状において市販されているＦＰＧＡ内部の埋め込みメモリによく見られるものである。
【００１８】
通常の演算処理において、プロセッサ要素は対応するバンクのメモリからの命令及びオペランドの読み出しのみを行うため、互いにアクセスが衝突することはない。命令実行のサイクルが全てのプロセッサにおいて同期する限り、スレッドを実行するプロセッサが全体で回転しながら互いに別々のメモリバンクをアクセスする状態が持続される。
【００１９】
ランダムアクセス書き込みに関しては、同一スレッド内で対象メモリバンクに対する読み出しが行われるまでライトバックを遅延してもスレッド内でのメモリ一貫性は失われない。この場合、プロセッサ内部状態としてプログラムカウンタ及びアキュムレータに加え、ライトバック遅延のための情報が付加されるが、アクセス調停のための回路が大幅に簡略化される。
【００２０】
ジャンプ命令についてはプログラムカウンタの書き換えのみを行い、プログラムカウンタの下位ビットがメモリバンクのアドレスと一致する場合にのみ命令の実行を行う。下位ビット不一致の際に隣接アドレスのバンクに内部状態をそのまま委譲することでジャンプの衝突に関する調停回路が不要となるが、最大１周分の回転待ちが生じる。実行性能を重視する場合には、調停のための回路を必要とするが、ショートカットによる回転待ちの短縮を図る構成も可能である。
【００２１】
ライトバック遅延を行う場合、ジャンプの回転待ちにおいてもライトバック処理を行うことで、スレッド内でのメモリ一貫性は保たれる。回転待ちのショートカットを行う場合、ライトバック遅延情報に対するショートカット回路も必要となるが、ライトバックが全て完了した場合にのみショートカットを実行することで、この追加回路のコストを軽減することも可能である。
【００２２】
ライトバック遅延によりランダムアクセス書き込みに関する調停が不要となる代償として、スレッド間におけるメモリ一貫性を確保するための機構が必要となる。これは例えばハードウェアミューテクスにより、スレッド間通信を構築することで実現可能である。
【発明の効果】
【００２３】
マルチプロセッサシステムにおいて共有メモリへのアクセスにキャッシュメモリを介する必要がなく、キャッシュメモリおよびキャッシュ一貫性のためのハードウェアリソースが不要となる。
【００２４】
複数スレッドの実行アドレスの下位ビットを異なる値にすることで共有メモリへのアクセスが別個のバンクに分離され、調停機能を全く必要とせずに同時アクセスが可能となり、メモリアクセスの帯域幅が向上する。
【００２５】
メモリへのランダムアクセスおよびジャンプ命令実行に際し、調停回路を必要とせず小規模なハードウェアで実現可能な実施形態がある。性能を重視するような場合、調停回路やショートカット回路等を追加することにより、適切なハードウェアの規模と性能を選択ことが可能である。
【００２６】
この新たな形態によるマルチプロセッサシステムは従来の構成とは大きく異なるものであるが、市販のＦＰＧＡ等のハードウェアでも容易に実現可能である。この新たな形態のプロセッサに関する効率的なハードウェア実装の構築や応用のみならず、このアーキテクチャにおけるソフトウェア開発、言語開発といった新たな興味深い研究開発の分野を切り拓くことになると期待される。
【発明を実施するための最良の形態】
【００２７】
以下、本発明の実施例について図面を参照して説明する。なお、以下の実施例は、本発明の実施の一形態であって、本発明の範囲を限定するものではない。
【実施例１】
【００２８】
図１は、本発明の実施例１に係るマルチプロセッサシステム１００の構成を示すブロック図である。
【００２９】
本発明の実施例１に係るマルチプロセッサシステム１００は、４個のプロセッサ１０２Ａ〜Ｄを有する４プロセッサ構成である。
【００３０】
各メモリバンク１０１Ａ〜Ｄは共有メモリ全体のアドレス空間のうち下位２ビットが００、０１、１０、１１となる部分のイメージを保持し、各プロセッサ１０２Ａ〜Ｄが同時に異なるメモリバンクにアクセスを行う分散共有メモリを構成する。
【００３１】
各プロセッサ１０２Ａ〜Ｄは、対応するメモリバンク１０１Ａ〜Ｄからメモリ出力信号１０３Ａ〜Ｄを通して命令コード１０３Ｐ及び１語長のオペランド１０３Ｙを同時に受け取り、対応する処理を実行する。図２において、メモリ出力データ１０３のビット構成を示す。
【００３２】
プロセッサは命令処理を実行後、内部状態を信号線を通して次のバンクに対応するプロセッサに転送する。ジャンプ命令及び制御命令の結果はプログラムカウンタ及び状態信号１０４Ａ〜Ｄ、演算命令の結果はアキュムレータ信号１０５Ａ〜Ｄに送出される。
【００３３】
信号１０４Ａ〜Ｄよりプログラムカウンタの下位２ビットを除いた部分が次のメモリバンクに接続され、次のアドレスに対する命令及びオペランドのフェッチの際に利用される。
【００３４】
各プロセッサは入力されたプログラムカウンタ信号１０４Ａ〜Ｄの下位２ビットが対応するメモリバンクと一致するか比較を行い、バンクが異なる場合には回転待ち状態として命令の実行を行わずに内部状態をそのまま次のプロセッサに引き渡す。この機構により、ジャンプ命令の実行はプログラムカウンタの値を変更するのみで実現可能である。ジャンプ命令実行の際、最大３命令分の回転待ちが発生する可能性があるが、コンパイラによるメモリ配置調整により軽減が可能である。
【００３５】
ジャンプ命令のオペランドの上位２ビットを利用してジャンプの条件を指定することが出来る。図３はオペランドの上位２ビットで指定された条件コードとジャンプ条件との対応の例である。条件コードにより無条件ジャンプ及び停止（ＨＡＬＴ）命令を表現することが可能である。
【００３６】
図２において示される様に、アキュムレータ１０５は１語長のレジスタ１０５Ｘ及びその上位のキャリーフラグ１０５Ｆで構成される。論理演算はレジスタ１０５Ｘに対してのみ実行され、加減算はキャリーフラグを含めたアキュムレータ全体について実行される。キャリーフラグは特殊命令実行時の結果通知にも利用され、条件ジャンプ命令実行時の条件としても利用される。
【００３７】
演算命令に於いてはアキュムレータ１０５とオペランド１０３Ｙの間で２項演算が実行され、演算結果がアキュムレータ信号１０５Ａ〜Ｄを通して次のプロセッサに送出され、新たなアキュムレータの値として反映される。
【００３８】
命令コード１０３Ｐと同時にオペランド１０３Ｙが即値としてプロセッサに読み込まれるため、レジスタファイルアクセスのためのオーバーヘッド無しに即座に命令実行が可能である。即値とレジスタアクセスの区別が不要であるため、必要となる命令コード数は著しく減少し、４ビット程度で基本的な命令はカバー可能である。図３は命令コード割り当ての例である。
【００３９】
メモリ上のオペランド１０３Ｙを読み込み前に予め書き換えておくことにより、任意のオペランドを汎用レジスタとして使用することが可能となる。この機能は、オペランド１０３Ｙで指定されたアドレスのメモリに格納されたオペランド１０３Ｙを、レジスタ１０５Ｘの値に書き換えるランダムアクセス書き込みを実行するＰＵＴ命令を実装することで実現可能である。この命令により、任意の演算ツリーを構成することが可能となる。図５は（Ａ−Ｂ）＋（Ｃ−Ｄ）を計算するコード列の例である。
【００４０】
ランダムアクセス書き込みは、同一バンクに対するメモリ読み込みまで遅延しても、スレッド内に於けるメモリ一貫性を損なうことはない。そのため書き込み信号としてバンク０書き込み信号１０６Ａ〜Ｄ、バンク１書き込み信号１０７Ａ〜Ｄ、バンク２書き込み信号１０８Ａ〜Ｄ、バンク３書き込み信号１０９Ａ〜Ｄが、書き込みアドレス、データ及びイネーブル信号を保持する。書き込み信号はプロセッサ内部状態と並行してプロセッサ間を移動し、対象バンク到着時に信号１０６Ａ、１０７Ｂ、１０８Ｃ、１０９Ｄに於いてバンクメモリへのライトバック処理を実行する。
【００４１】
命令及びオペランドのフェッチとライトバックが同一のアドレスに対して実行された場合、ライトバックの際に書き込まれたデータが即座に命令及びオペランドとして読み込まれるものとする。この構成により、命令の直後の番地への書き込みも次のフェッチの際に反映され、問題なく実行される。ＦＰＧＡ内部のデュアルポートメモリを利用する場合、異なるポートからの同一アドレスに対する同時読み書きの結果が不定となるものがあるが、メモリ周辺にバイパス回路を実装することで、この問題を回避することが可能である。
【００４２】
ランダムアクセス書き込み命令実行時、対象バンクの書き込み信号入力が既にイネーブルである場合、書き込み命令の実行を一旦中止し、同一アドレスへのジャンプを実行して書き込み命令の再試行を行う。ジャンプ命令の回転待ちの際にもライトバックが実行されるため、再試行時には全てのライトバックが実行済みで書き込みの衝突が起きることはない。書き込みの再試行は４命令分のペナルティとなるため、コンパイル時に同一バンクへの連続した書き込みを避けることと、直後にライトバックが実行されるバンクへの書き込みを優先して配置することで、この書き込みの再試行を防ぐことができる。
【００４３】
同一アドレスへの書き込みを故意に連続して実行することで、書き込みの衝突による回転待ちが発生し、同一スレッドの全てのライトバックが実行され、他のスレッドに対するメモリ内容が確定する。これをスレッド間通信に於けるメモリバリアとして利用することができる。
【００４４】
ランダムアクセス書き込みの際、アドレスを指定するオペランド１０３Ｙの上位４ビットを命令コードの書き込みに利用することが可能である。具体的には、メモリ空間のアドレスが（語長−４）ビット以内で表現可能な場合、ライトバック時にオペランドの上位４ビットの値を命令コードメモリ１０３Ｐに同時に書き込みを行う。コンパイル時に書き込み先アドレスの命令コードは既に決定しており、命令コード付きアドレスは実行前に確定するため実行中のオーバーヘッドはない。これはスレッド間通信で命令コードとオペランドをアトミックに同時書き換えする際に有効である。
【００４５】
ランダムアクセス書き込みに於けるライトバックの遅延により、通常は異なるスレッド間でメモリの一貫性が保持されないが、ＬＯＣＫ命令の利用により安全なスレッド間通信を実現することができる。ＬＯＣＫ命令は命令を実行するプロセッサに割り当てられたミューテクスを操作する命令で、プロセッサが既にロック状態にある場合には同一番地へのジャンプを実行することでスピンロックを構成し、ロック成功時にはプロセッサがロック状態に移行し、ＵＮＬＯＣＫ命令実行までロック状態を保持する。プロセッサのロック状態が影響するのはＬＯＣＫ命令に対してのみであり、他の命令実行には影響しない。
【００４６】
ＵＮＬＯＣＫ命令はＬＯＣＫ命令と同じ命令コードであるが、オペランドの値により両者は区別される。ＬＯＣＫ命令のオペランドには０を指定し、命令を実行したプロセッサバンクのミューテクスのロックを実行する。ＵＮＬＯＣＫ命令のオペランドは、下位４ビットでアンロックするプロセッサのバンクを指定する。ＵＮＬＯＣＫ命令は任意のプロセッサバンクで実行が可能であり、同時に実行されたＵＮＬＯＣＫ命令は、パラメータが全て論理和された上でそれぞれのプロセッサバンクにアンロックを通知する。この通知はロック解除信号バス１１０を通して行われる。
【００４７】
ＬＯＣＫ命令によるロックはプロセッサ毎に割り当てられる粒度の粗いミューテクスであり、ある程度長期のロックが想定されるクリティカルセクション等の応用に於いては、状態遷移時のみの短期ロックに利用することが望ましい。図６は、ＬＯＣＫ命令を利用したスピンロックによるクリティカルセクションの構成例である。
【００４８】
新規スレッドの生成はＦＯＲＫ命令により実行される。スレッド生成時、プロセッサ内の起動待ち行列に新規スレッドの起動アドレス及び初期アキュムレータ値を登録するが、待ち行列が満杯の場合スレッド生成は失敗となる。スレッド生成の成否はキャリーフラグにて通知されるため、ソフトウェアによるリトライ及び待ち行列の構成が可能である。この場合、ハードウェア待ち行列の長さを１にすることで回路規模の削減が可能である。
【００４９】
プロセッサが停止状態で起動待ち行列が空でない場合、新規のスレッドが生成される。具体的には、待ち行列先頭の起動アドレス及び初期アキュムレータ値がプロセッサ内のプログラムカウンタ及びアキュムレータに代入され、プロセッサが実行状態に移行する。
【００５０】
配列や構造体、スタック等のデータ構造を利用する場合、メモリに対するランダムアクセス読み出しの処理が必要となる。この処理はＧＥＴ命令及びＤＡＴＡ命令により実現できるが、これらの命令の実行内容は同じであり、命令コードも同一のものを使用する。ＧＥＴ命令はレジスタＸで指定された番地へのジャンプ及びオペランドＹのレジスタＸへの代入を行う。レジスタＸで指定された番地にＤＡＴＡ命令がある場合、ＤＡＴＡ命令はＧＥＴ命令と同様にレジスタＸで指定された番地へのジャンプ及びオペランドＹのレジスタＸへの代入を行う。ＤＡＴＡ命令実行時のレジスタＸの値はＧＥＴ命令に於けるオペランドＹの値であるため、全体としてＧＥＴ命令はレジスタＸで指定された番地にあるＤＡＴＡ命令のオペランドＹの値をレジスタＸに代入し、ＧＥＴ命令のオペランドＹで指定される番地にジャンプする命令となる。
【００５１】
データ専用メモリやメモリマップドＩ／Ｏに関しては、読み出し時に命令コードとしてＤＡＴＡ命令を補うことにより利用が可能である。特に、メモリや周辺回路を特定のプロセッサにのみ接続することで、同時アクセス調停の回路を省略することが可能となる。
【図面の簡単な説明】
【００５２】
【図１】本発明の実施例１に係るマルチプロセッサシステム１００の構成を示すブロック図である。
【図２】本発明の実施例１に係るメモリ出力データ１０３及びアキュムレータ１０５のビット構成を示す図である。
【図３】本発明の実施例１に係るジャンプ命令の条件コードとジャンプ条件の対応を示す図である。
【図４】本発明の実施例１に係る命令コードの割り当て例とその実行内容を示す図である。
【図５】本発明の実施例１に係る演算ツリーを構成するコード列の例を示す図である。
【図６】本発明の実施例１に係るＬＯＣＫ命令を利用したクリティカルセクションの実装例を示す図である。
【符号の説明】
【００５３】
１００  マルチプロセッサシステム
１０１Ａ〜Ｄ  デュアルポートメモリ
１０２Ａ〜Ｄ  プロセッサ
１０３  メモリ出力データ
１０３Ａ〜Ｄ  メモリ出力信号
１０３Ｐ  命令コードＯＰ
１０３Ｙ  オペランドＹ
１０４Ａ〜Ｄ  プログラムカウンタ及び状態信号
１０５  アキュムレータ
１０５Ａ〜Ｄ  アキュムレータ信号
１０５Ｆ  キャリーフラグＣ
１０５Ｘ  レジスタＸ
１０６Ａ〜Ｄ  メモリバンク０書込み信号
１０７Ａ〜Ｄ  メモリバンク１書込み信号
１０８Ａ〜Ｄ  メモリバンク２書込み信号
１０９Ａ〜Ｄ  メモリバンク３書込み信号
１１０  ロック解除信号バス
【図１】
2014016773.tif 000003
【図２】
2014016773.tif 000004
【図３】
2014016773.tif 000005
【図４】
2014016773.tif 000006
【図５】
2014016773.tif 000007
【図６】
2014016773.tif 000008