(57)【要約】【課題】  １つのスレッドの処理時間が非常に長い場合でも、処理速度を向上させ、処理時間を短縮可能なマルチスレッド処理装置を提供する。【解決手段】  マルチスレッド処理装置は、各々フレームを処理する複数のスレッドを同時進行させかつスレッド順に前記フレームを処理する手段（マルチプロセッシング処理部１２）を含む。マルチスレッド処理装置は、予め設定した条件を満たした場合に次フェイズのフレーム処理を先取り処理してスレッドの空転時間を有効活用する手段（マルチプロセッシング処理部１２及び処理済みフレーム用バッファ１３）を有する。【選択図】      図１
2011002913.tif 000002
【特許請求の範囲】
【請求項１】
各々フレームを処理する複数のスレッドを同時進行させかつスレッド順に前記フレームを処理する手段を含むマルチスレッド処理装置であって、
予め設定した条件を満たした場合に次フェイズのフレーム処理を先取り処理して前記スレッドの空転時間を有効活用する手段を有することを特徴とするマルチスレッド処理装置。
【請求項２】
前記次フェイズのフレームの先取り処理を、各フェイズで１回以下とすることを特徴とする請求項１記載のマルチスレッド処理装置。
【請求項３】
前記先取り処理の対象のフレームは、前記空転時間が生じたスレッドにおいて前記次フェイズで処理予定のフレームであることを特徴とする請求項１または請求項２記載のマルチスレッド処理装置。
【請求項４】
前記複数のスレッド各々に対応して現フェイズのフレー及び次フェイズのフレームの処理状況を記録する手段を含むことを特徴とする請求項１から請求項３のいずれか記載のマルチスレッド処理装置。
【請求項５】
前記複数のスレッド各々で処理されたフレームを格納する処理済みフレーム用バッファと、前記処理済みフレーム用バッファに格納されたフレーム各々が送出対象か否かを示すフラグを記録する手段とを含むことを特徴とする請求項１から請求項４のいずれか記載のマルチスレッド処理装置。
【請求項６】
Ｌ２（Ｌａｙｅｒ  ２）スイッチ、Ｌ３（Ｌａｙｅｒ  ３）スイッチ、ルータのいずれかに用いることを特徴とする請求項１から請求項５のいずれか記載のマルチスレッド処理装置。
【請求項７】
各々フレームを処理する複数のスレッドを同時進行させかつスレッド順に前記フレームを処理する手段を含む処理装置に用いるマルチスレッド処理方法であって、
前記処理装置が、予め設定した条件を満たした場合に次フェイズのフレーム処理を先取り処理して前記スレッドの空転時間を有効活用する処理を実行することを特徴とするマルチスレッド処理方法。
【請求項８】
前記次フェイズのフレームの先取り処理を、各フェイズで１回以下とすることを特徴とする請求項７記載のマルチスレッド処理方法。
【請求項９】
前記先取り処理の対象のフレームは、前記空転時間が生じたスレッドにおいて前記次フェイズで処理予定のフレームであることを特徴とする請求項７または請求項８記載のマルチスレッド処理方法。
【請求項１０】
前記処理装置に、前記複数のスレッド各々に対応して現フェイズのフレー及び次フェイズのフレームの処理状況を記録する手段を設けたことを特徴とする請求項７から請求項９のいずれか記載のマルチスレッド処理方法。
【請求項１１】
前記処理装置に、前記複数のスレッド各々で処理されたフレームを格納する処理済みフレーム用バッファと、前記処理済みフレーム用バッファに格納されたフレーム各々が送出対象か否かを示すフラグを記録する手段とを設けたことを特徴とする請求項７から請求項１０のいずれか記載のマルチスレッド処理方法。
【請求項１２】
Ｌ２（Ｌａｙｅｒ  ２）スイッチ、Ｌ３（Ｌａｙｅｒ  ３）スイッチ、ルータのいずれかに用いることを特徴とする請求項７から請求項１１のいずれか記載のマルチスレッド処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はマルチスレッド処理装置及びそれに用いるマルチスレッド処理方法に関し、特にイーサネット（登録商標）フレームのマルチスレッド処理における処理時間の短縮方法に関する。
【背景技術】
【０００２】
現在のマルチスレッドによるイーサネット（登録商標）フレームの処理としては、フレームの処理順序の逆転を生じさせないため、処理時間最長のスレッドの処理終了を待ってから次のフレーム処理に入るという方法がある（以下、第１の方法とする）。
【０００３】
この第１の方法の場合は、各フレームの処理時間が平均しているというような、極めて理想的な状況（図２参照）では、単純で特別な機構を要しないため、最も効率的な方法となる。しかしながら、第１の方法の場合、現実的にはフレーム処理時間のばらつきが必ず生じるので、１つのスレッドの処理時間が非常に長い場合、他のスレッドの動作が止まってしまうことになる（図３参照）。
【０００４】
本発明に関連するマルチスレッド処理方法では、上記の第１の方法が主流であるが、現実的なフレーム処理は図２に示すようにはならず、図３に示すように、スレッドにかなりの空転時間が生じる。
【０００５】
その対処法としては、処理を終了したスレッドに次の処理対象フレームを読み込ませる方法がある（図４参照）（以下、第２の方法とする）。
【０００６】
上記の第１の方法における問題の解決方法としては、第２の方法があるが、その場合、フレームの順序の逆転が生じる可能性があるため、最終的に処理済フレームを整列させる必要が出てくる。
【０００７】
ここで、図２は、第１の方法における理想的な状況下でのフレーム処理の状況を図示したものである。図２において、マルチプロセッシング処理部２２による処理は、４スレッドでの処理であると仮定している。
【０００８】
マルチプロセッシング処理部２２は、メモリ（未処理フレーム用バッファ２１）内に取り込まれたフレームを、スレッド番号の順に処理していく。マルチプロセッシング処理部２２は、処理終了時刻に関係なく、そのフェイズの全スレッド処理が終了した時点で、スレッド番号の小さいものの処理対象データから処理済みフレーム用バッファ２３に出力して行く。
【０００９】
図３は、第１の方法の現実的な状況下でのフレーム処理の状況を図示したものである。図３において、マルチプロセッシング処理部３２による処理は、４スレッドでの処理であると仮定している。
【００１０】
マルチプロセッシング処理部３２は、メモリ（未処理フレーム用バッファ３１）内に取り込まれたフレームを、スレッド番号の順に処理していく。マルチプロセッシング処理部３２は、例えば処理フェイズ＃１の状況で言えば、フレーム＃１，＃３，＃４の処理が終了していても、フレーム＃２の処理終了を待っていて、次処理フェイズ＃２のフレーム処理が開始できない状況である。
【００１１】
図４は、図３に示す第１の方法の現実的な状況でのフレーム処理を第２の方法で改善しようとした場合を図示したものである。図４において、マルチプロセッシング処理部４２は、メモリ（未処理フレーム用バッファ４１）内に取り込まれたフレームを、スレッド番号の順に処理していくが、処理フェイズ＃１で処理の終わった順に、次処理フェイズ＃２での処理対象のフレームを処理させて行く。
【００１２】
図４において、マルチプロセッシング処理部４２は、最初の終了したフレーム＃３に続けてフレーム＃５を処理し、次に終了したフレーム＃１に続けてフレーム＃６を処理している。
【００１３】
同様に、マルチプロセッシング処理部４２は、フレーム＃４に続けてフレーム＃７を処理し、フレーム＃５に続けてフレーム＃８を処理し、フレーム＃２に続けてフレーム＃９を処理し、フレーム＃７に続けてフレーム＃１０を処理し、フレーム＃６に続けてフレーム＃１１を処理している。
【００１４】
フレーム処理のみに言及すれば、図３に示す処理よりも処理フェイズ＃２の終了時刻が早いが、スレッド順にフレームを処理済みフレーム用バッファ４３に出力すると、フレームの逆転が起こってしまう。
【００１５】
この場合は、処理フェイズ＃２のフレームがフレーム＃６，＃５，＃７，＃８の順に出力されてしまうので、整合性を保つためには整列、あるいは処理済みフレーム用バッファ４３に処理済みフレームを格納しておき、フレーム＃２の終了を待ってからその後のフレームを送出させる必要がある。
【００１６】
上記のマルチスレッドによるイーサネット（登録商標）フレームの処理については、下記の特許文献１に記載の技術がある。この特許文献１に記載の技術では、イーサネット（登録商標）専用線網とイーサネット（登録商標）交換網との接続においてＶＬＡＮ（Ｖｉｒｔｕａｌ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）−ＩＤ（ＩＤｅｎｔｉｆｉｅｒ）を利用している。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】特開２００５−０１２６３７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１８】
上述した本発明に関連するマルチスレッド処理方法では、第１の方法における問題を解決するために第２の方法を採用すると、送出時のフレームの整列の処理コストが高く、結果的に処理速度の向上に繋がらないことも多いという課題がある。
【００１９】
尚、上記の特許文献１の記載の技術は、Ｌ２（Ｌａｙｅｒ  ２）スイッチのイーサネット（登録商標）フレームに対するマルチスレッド処理方式を示しているだけであり、上記の課題を解決することはできない。
【００２０】
そこで、本発明の目的は上記の問題点を解消し、１つのスレッドの処理時間が非常に長い場合でも、処理速度を向上させることができ、処理時間を短縮することができるマルチスレッド処理装置及びそれに用いるマルチスレッド処理方法を提供することにある。
【課題を解決するための手段】
【００２１】
本発明によるマルチスレッド処理装置は、各々フレームを処理する複数のスレッドを同時進行させかつスレッド順に前記フレームを処理する手段を含むマルチスレッド処理装置であって、
予め設定した条件を満たした場合に次フェイズのフレーム処理を先取り処理して前記スレッドの空転時間を有効活用する手段を備えている。
【００２２】
本発明によるマルチスレッド処理方法は、各々フレームを処理する複数のスレッドを同時進行させかつスレッド順に前記フレームを処理する手段を含む処理装置に用いるマルチスレッド処理方法であって、
前記処理装置が、予め設定した条件を満たした場合に次フェイズのフレーム処理を先取り処理して前記スレッドの空転時間を有効活用する処理を実行している。
【発明の効果】
【００２３】
本発明は、上記のような構成及び動作とすることで、１つのスレッドの処理時間が非常に長い場合でも、処理速度を向上させることができ、処理時間を短縮することができるという効果が得られる。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施の形態によるマルチスレッド処理装置の構成例を示すブロック図である。
【図２】本発明に関連するマルチスレッド処理の第１の方法における理想的な状況下でのフレーム処理の状況を示す図である。
【図３】本発明に関連するマルチスレッド処理の第１の方法の現実的な状況下でのフレーム処理の状況を示す図である。
【図４】図３に示す第１の方法の現実的な状況でのフレーム処理を第２の方法で改善しようとした場合を示す図である。
【発明を実施するための形態】
【００２５】
次に、本発明の実施の形態について図面を参照して説明する。まず、本発明によるマルチスレッド処理装置の概要について説明する。
【００２６】
本発明によるマルチスレッド処理装置は、あくまでスレッド順にフレームを処理するという、フレーム順の整列コストを発生させないための原則を遵守させつつ、予め設定した条件を満たした場合のみ、スレッドの空転時間を有効活用することを特徴としている。整列の計算量は、整列対象のフレーム数（すなわち、スレッド数）の２乗に比例するので、スレッド数が増えれば増えるほど、本発明の適用時の計算量削減の効果が大きくなる。
【００２７】
本発明によるマルチスレッド処理装置は、Ｌ２（Ｌａｙｅｒ  ２）スイッチのフレームに対するマルチスレッド処理において、各スレッドの処理時間が著しく違う場合、処理が終了した一部のスレッドの空転時間を有効活用し、結果として全体の処理時間を短縮することを特徴としている。
【００２８】
ここで、本発明の用語について説明する。本発明では、ＣＰＵ（中央処理装置）数（スレッドの同時進行数）をｍとする。また、本発明では、Ｌ２スイッチで処理すべきフレームに対し、流入順に全順序集合となる番号を付与し（ここでは自然数とする）、＃１〜＃ｍのクラスに分類する。
【００２９】
クラスの分類は、フレームの順序集合中の番号をｎ、処理対象フレーム全てを集合Ｎとし、
ｎ≡（クラス番号）  ｍｏｄ  ｍ
を同値関係とした場合のＮ／〜で行う。
【００３０】
４ＣＰＵでの処理を行うと仮定すると、ＣＰＵ＃１はクラス＃１のフレーム（＃１，＃５，＃９，・・・）の処理を、ＣＰＵ＃２はクラス＃２のフレーム（＃２，＃６，＃１０，・・・）の処理を、ＣＰＵ＃３はクラス＃３のフレーム（＃３，＃７，＃１１，・・・）、ＣＰＵ＃４はクラス＃４のフレーム（＃４，＃８，＃１２，・・・）の処理を行うことになる。
【００３１】
また、ＣＰＵ＃１の処理対象のフレーム番号の集合をνとすると、ν，ν＋１，ν＋２，・・・，ν＋（ｍ−１）をｍ個のＣＰＵで並列処理すべき対象フレームとなるので、この集合をフェイズ（ν／ｍ）処理対象フレーム、その段階の処理のことを単にフェイズ（ν／ｍ）と呼ぶ。
【００３２】
そして、フェイズ（ν／４）で行うν，ν＋１，ν＋２，・・・，ν＋（ｍ−１）の処理のことを主処理、各スレッドがフェイズ（ν／ｍ）でフェイズ（ν／ｍ＋１）のスレッドを先取りして処理する場合の処理をフェイズ（ν／ｍ）副処理と呼ぶ。
【００３３】
本発明では、上記の第１の方法と同様に、処理開始時のスレッド番号通りに出力をさせるが、各スレッドは現フェイズの主処理が終了時点で、他のスレッドの主処理が終了しているか否かを調べ、他のスレッドの主処理が進行中の場合にのみ次フェイズのフレームを先取りして副処理を開始する。
【００３４】
先取りを行うのは、あくまで次フェイズのフレームのみであり、それ以上の先取りは行わない。また、現フェイズの副処理で終了しなかったフレームは次フェイズで処理するようにする。
【００３５】
図１は本発明の実施の形態によるマルチスレッド処理装置の構成例を示すブロック図である。図１は、図３に示す状況下で本実施の形態による方法を用いたフレーム処理の状況を図示したものである。
【００３６】
また、図１において、本発明の実施の形態によるマルチスレッド処理装置は、未処理フレーム用バッファ１１と、マルチプロセッシング処理部１２と、処理済みフレーム用バッファ１３とを備えており、マルチプロセッシング処理部１２はフレーム処理状況記録部位１２１を備え、処理済みフレーム用バッファ１３は送出対象フラグ記録部位１３１を備えている。
【００３７】
本実施の形態において、次フェイズのフレームの先取りは、各フェイズで多くても１回だけであり、また先取りするフレームはフレーム番号がポイントなのではなく、次フェイズでどのスレッドが処理する予定のフレームなのか（どの処理クラスに属するフレームなのか）がポイントである。
【００３８】
フレーム処理状況記録部位１２１は、各スレッドに現フェイズ・次フェイズのフレームの処理状況を記録し（４スレッド処理ならば４つ）、スレッド毎に３つの状態を持つ。すなわち、現スレッドの主処理が未了、主処理が終了（したので副処理進行中）、主・副処理共終了、の３つである。図１では、最初の状態を「空白」、２番目の状態を「○」、３番目の状態を「●」で示している。
【００３９】
処理済みフレーム用バッファ１３は、クラス＃１主処理済みフレーム用バッファ、クラス＃１副処理済みフレーム用バッファ、クラス＃２主処理済みフレーム用バッファ、クラス＃２副処理済みフレーム用バッファ、クラス＃３主処理済みフレーム用バッファ、クラス＃３副処理済みフレーム用バッファ、クラス＃４主処理済みフレーム用バッファ、クラス＃４副処理済みフレーム用バッファを備えている。
【００４０】
また、処理済みフレーム用バッファ１３は、上記のような各処理済フレーム用バッファに対しても、送出対象か否かのフラグを記録する部位（送出対象フラグ記録部位１３１）を備えている。
【００４１】
フレーム処理状況記録部位１２１と送出対象フラグ記録部位１３１との関連性としては、各フェイズの初期状態において、フラグは「０」となっており、フレーム処理状況記録が主処理終了（「○」状態）となったときに、各クラスの主処理済フレーム用バッファの送出対象フラグが「１」に、更に副処理も終了したとき（「●」状態）、副処理済みフレーム用バッファの送出対象フラグも「１」になる。
【００４２】
現フェイズが終了した時点で２番目の状態（副処理進行中）となっているスレッドに関しては、副処理済フレーム用バッファに一時的に処理を記録して、次フェイズの主処理にまわす。副処理進行中の段階では、副処理済みフレーム用バッファは送出対象となっていないため、このようなことが可能となる。
【００４３】
このように、本実施の形態では、フレームに対するマルチスレッド処理において、各スレッドの処理時間が著しく違う場合、処理が終了した一部のスレッドの空転時間を有効活用することで、結果として全体の処理時間を短縮することができる。つまり、本実施の形態では、１つのスレッドの処理時間が非常に長い場合でも、処理速度を向上させることができ、処理時間を短縮することができる。
【産業上の利用可能性】
【００４４】
本発明は、Ｌ２スイッチのイーサネット（登録商標）フレーム処理に限定されるものではなく、Ｌ３（Ｌａｙｅｒ  ３）スイッチ、ルータのパケット処理に対しても適用可能である。
【符号の説明】
【００４５】
１１  未処理フレーム用バッファ
１２  マルチプロセッシング処理部
１３  処理済みフレーム用バッファ
１２１  フレーム処理状況記録部位
１３１  送出対象フラグ記録部位
【図１】
2011002913.tif 000003
【図２】
2011002913.tif 000004
【図３】
2011002913.tif 000005
【図４】
2011002913.tif 000006