(57)【要約】【課題】コンテキスト切り替えが起こったときの切り替え前プログラム用のデータの待避および復帰、自由度のあるキューの構成、およびキューが満になったときの拡張を行うことができるキューを主に中間結果格納用メモリとして使うキュープロセッサを提供する。【解決手段】キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、キュー語を入れ替え、入れ替えたキュー語を順番にならべることによってキューを構成することを特徴とする。【選択図】図１
2005293083.tif 000002
【特許請求の範囲】
【請求項１】
キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、キュー語を入れ替え、入れ替えたキュー語を順番にならべることによってキューを構成することを特徴とするキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項２】
キュー語を入れ替え、入れ替えたキュー語を順番にならべ、各語の名前をそのまま用いることによって主に中間結果格納用キューとして使うことを特徴とする請求項１記載のキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項３】
キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、割り込みが起こったときなどのコンテキスト切り替えにおいて、切り替え前プログラム用のキューの中間結果を待避するとき、そのキュー語の名前とキューポインタのみを待避し、キュー語の中身を残して、残りのキュー語で切り替え後プログラムのキューを構成することを特徴とするキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項４】
キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、割り込みが起こったときなどのコンテキスト切り替えにおいて、切り替え前プログラム用のキューの中間結果を待避するとき、待避されたキュー語部分を詰めることによって、切り替え後プログラムのキューを構成することを特徴とするキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項５】
キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、ＱＴとＬＱＨ間にキュー語を入れることによってキューを拡張することを特徴とするキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項６】
キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、バッファを設けここにＱＴを作ることによってキューを拡張することを特徴とするキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項７】
バッファが一杯になったとき、バッファの内容を待避用メモリに待避してからバッファにＱＴを作ることによってキューを拡張することを特徴とする請求項６記載のキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項８】
前記待避されたデータを復帰させるとき、待避用メモリからキューにデータを戻すことを特徴とする請求項７記載のキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【請求項９】
キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、ページテーブルを用い、その内容を書き換えることによって物理キュー語を指定する仮想キューを構成することを特徴とするキューを主に中間結果格納用メモリとして使うキュープロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キューを主に中間結果格納用メモリとして使うキュープロセッサに係り、並列キュープロセッサにおける論理キュー構造、特に、ジェネラルレジスタの代わりにキューを使用することで、命令の高度な並列実行を実現しようとするキュープロセッサに関するものである。
【背景技術】
【０００２】
従来、キュープロセッサに関する先行技術としては、以下に示すようなものがあった。
【０００３】
（１）共用バッファメモリのＡＴＭ交換モジュールとその重複モジュールを用いてアクティブ・スタンバイモードで動作する故障許容性システムにおいて、各メモリが受信した情報をバッファに入れるためのキューを備えている（下記特許文献１参照）。
【０００４】
（２）命令長およびプログラム長を短くするとともに、並列実行を可能にし、プロセッサを高速化することができるキュープロセッサが提供されている（下記特許文献２参照）。
【０００５】
（３）ＶＬＩＷ（Ｖｅｒｙ  Ｌｏｎｇ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｗｏｒｄ）命令長を長くし、メモリやプロセッサのハードウェアが少なくてすむコンピュータが提供されている（下記特許文献３参照）。
【０００６】
（４）命令長の違いからくる複雑性を取り除き、ハードウェアを簡単化し、高速化するファンクション・オペランド分割型プロセッサが提供されている（下記特許文献４参照）。
【０００７】
（５）プログラムサイズを小さく保ったまま高速化が可能なキュー仮想マシンシステムが提供されている（下記特許文献５参照）。
【特許文献１】特開平０７−１４３１２６号公報
【特許文献２】特開平１４−３５１６５９号公報
【特許文献３】特開平１５−０２２１８３号公報
【特許文献４】特開平１５−０２２１７９号公報
【特許文献５】特開平１５−０２２１９４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
従来のキューを中間結果格納用メモリとして使うキュープロセッサにおいては、以下のような問題があった。
【０００９】
（１）割り込みなどでコンテキスト切り替えが起こったときの、切り替え前プログラム用のデータの待避、復帰方法が確立されていない。
【００１０】
（２）自由度のあるキューの構成方法が確立されていない。
【００１１】
（３）キューが満になったときどのようにして拡張するかが明らかにされていない。
【００１２】
本発明は、上記状況に鑑みて、コンテキスト切り替えが起こったときの切り替え前プログラム用のデータの待避および復帰、自由度のあるキューの構成、およびキューが満になったときの拡張を行うことができるキューを主に中間結果格納用メモリとして使うキュープロセッサを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、上記目的を達成するために、
〔１〕キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、キュー語を入れ替え、入れ替えたキュー語を順番にならべることによってキューを構成することを特徴とする。
【００１４】
〔２〕上記〔１〕記載のキューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、キュー語を入れ替え、入れ替えたキュー語を順番にならべ、各語の名前をそのまま用いることによって主に中間結果格納用キューとして使うことを特徴とする。
【００１５】
〔３〕キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、割り込みが起こったときなどのコンテキスト切り替えにおいて、切り替え前プログラム用のキューの中間結果を待避するとき、そのキュー語の名前とキューポインタのみを待避し、キュー語の中身を残して、残りのキュー語で切り替え後プログラムのキューを構成することを特徴とする。
【００１６】
〔４〕キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、割り込みが起こったときなどのコンテキスト切り替えにおいて、切り替え前プログラム用のキューの中間結果を待避するとき、待避されたキュー語部分を詰めることによって、切り替え後プログラムのキューを構成することを特徴とする。
【００１７】
〔５〕キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、ＱＴとＬＱＨ間にキュー語を入れることによってキューを拡張することを特徴とする。
【００１８】
〔６〕キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、バッファを設けここにＱＴを作ることによってキューを拡張することを特徴とする。
【００１９】
〔７〕上記〔６〕記載のキューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、バッファが一杯になったとき、バッファの内容を待避用メモリに待避してからバッファにＱＴを作ることによってキューを拡張することを特徴とする。
【００２０】
〔８〕上記〔７〕記載のキューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、前記待避されたデータを復帰させるとき、待避用メモリからキューにデータを戻すことを特徴とする。
【００２１】
〔９〕キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、ページテーブルを用い、その内容を書き換えることによって物理キュー語を指定する仮想キューを構成することを特徴とする。
【発明の効果】
【００２２】
本発明によれば、以下のような効果を奏することができる。
【００２３】
（１）割り込みなどでコンテキスト切り替えが起こったときの、切り替え前プログラム用のデータの待避、復帰方法を確立した。
【００２４】
（２）自由度のあるキューの構成方法を確立した。
【００２５】
（３）キューが満になったとき確実に拡張させることができる。
【発明を実施するための最良の形態】
【００２６】
（１）キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、キュー語を入れ替え、入れ替えたキュー語を順番にならべることによってキューを構成する。
【００２７】
（２）キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、割り込みが起こったときなどのコンテキスト切り替えにおいて、切り替え前プログラム用のキューの中間結果を待避するとき、（ａ）そのキュー語の名前とキューポインタのみを待避しその内容を残し、残りのキュー語で切り替え後プログラムのキューを構成する。また、（ｂ）待避されたキュー語部分を詰めることによって、切り替え後プログラムのキューを構成する。
【００２８】
（３）キューを主に中間結果格納用メモリとして使うキュープロセッサにおいて、（ａ）ＱＴとＬＱＨ間にキュー語を入れることによってキューを拡張することを特徴とする。また、（ｂ）バッファを設けここにＱＴを作ることによってキューを拡張する。
【実施例】
【００２９】
以下、本発明の実施の形態について詳細に説明する。
【００３０】
〔１〕キュー内のデータ待避とキューの拡張概要について説明する。
【００３１】
図１は本発明にかかるサーキュラーキューの使い方を示す模式図である。
【００３２】
キュープロセッサでは、汎用のレジスタに相当する中間結果格納用記憶装置として、図１（ａ）に示すような円形のサーキュラーキューと呼ばれるキューが使われる。図１において、ＬＱＨ（ライブキューヘッダ）とＱＴ（キューテイル）に囲まれた斜線部分がキューにデータが格納されている部分である。各データが格納されている部分をキュー語と呼び、各キュー語には１、２、３などの名前が付けられている。命令は原則としてＱＨ（キューヘッダ）が示すデータを取り出し、計算した結果を（ＱＴ＋１）が示す語に挿入する。データを取り出したり挿入したりしたときにはＱＨやＱＴ、ＬＱＨはそれに応じて右に動く。
【００３３】
コンテキストスイッチの例として、割り込みが起こった場合を例に説明する。
【００３４】
図１（ｂ）に示すように、コンテキストスイッチ発生前（被割り込みプログラム）のキュー内のデータを待避して、そこをコンテキストスイッチ後のプログラム（割り込み処理用のプログラム＝割り込みハンドラ）で使えるようにし、割り込みハンドラの実行が終わったときには待避してあったデータを再ロードして図１（ａ）に示すように復旧させなければならない。
【００３５】
また、プログラムの実行が進んで、図１（ｃ）に示すようにキューのすべての語にデータが挿入されてキューが満になったとき、なおもデータを挿入しなければならない場合、このまま新たなデータを書き込むと、未使用のデータ（図では０番のデータ）を破壊するので、その前にこのキューを拡張する必要がある。
【００３６】
〔２〕次に、キューテーブル法による割り込み時のキューの取り扱いについて説明する。
【００３７】
図２は本発明にかかるキューの構成図である。
【００３８】
この方法では、図２に示すようにキューを構成する。図２中Ｖフラグはキュー語が有効かどうかを示し、ＱＰはキューポインタ、ＰＱはキュー語の名前を示す。また、Ｃｏｎｔはキュー語の中身（中間結果）である。図２（ａ）は、実行中のプログラムがＬＱＨからＱＴ間に中間結果を入れて用いている様子を示す。割り込みが起こると、図２（ｂ）に示すように、今まで使っていたキューのＱＰ部とＰＱ部がメモリに待避され、この部分のＶフラグが０とされ無効化される。残りの９，１０，…１５，０，１，２，３が、割り込みハンドラが使えるサーキュラーキュー部分となる。図２（ｃ）は、この部分を割り込みハンドラが使っている様子を示す。割り込み処理プログラムの実行が終わると〔図２（ｄ）〕、待避してあったＱＰ部とＰＱ部が戻され、Ｖフラグを１にして元のキューに戻る〔図２（ｅ）〕。
【００３９】
この方法は、キューから被割り込みキューのＱＰとＰＱを待避するのみで、キューの内容を待避しないので、それだけ割り込み処理が早くなる。
【００４０】
〔３〕キューを構成するレジスタの並べ替えによるキューの構成について説明する。
【００４１】
図３は、割り込みが起こって、割り込みを処理中にキューが満となり不足した場合、どのようにそれを取り扱うかを示す図である。
【００４２】
この図において、ＱＰ欄はキューを構成するためのライブキューヘッドＬＱＨ、キューヘッドＱＨ、キューテイルＱＴを示す欄、論理欄は論理的な順番、物理欄は物理キューの名前、内容は物理キューの内容（斜線部）を示す。
【００４３】
図３において、図３（ａ）は割り込み前、図３（ｂ）は割り込まれた後、被割り込みプログラムのキューが退避された様子を、図３（ｃ）は割り込みハンドラのキューを、図３（ｄ）は割り込みハンドラのキューが満になった様子を、図３（ｅ）はＱＴの後に空きスペースを作る様子を、図３（ｆ）は被割り込みプログラム用のキューレジスタを、割り込みハンドラ用のキューの拡張に使う様子を、図３（ｇ）は割り込みハンドラの実行終了の様子を、図３（ｈ）は被割り込みプログラムのキューを復興させた様子をそれぞれ示す図である。
【００４４】
図３（ａ）に示すように、実行中のプログラムがキューを使っているときに割り込みが起こったとする。このとき割り込みハンドラを実行するために、割り込まれたプログラム（被割り込みプログラム）が使っていたキューの内容をメモリに待避し、割り込みハンドラ用のキューを作る。その結果のキューの図は図３（ｂ）のようになる。ここでは物理キュー０，１，…３，１０，１１，…１７がキューとなる。ここではＬＱＨ，ＱＨ，ＱＴはまとめてＱＰＲとして表現されている。割り込みハンドラの実行が進むと、図３（ｃ）に示すようにキューにはデータが格納される。図３（ｄ）は割り込みハンドラの実行が進んですべてのキューにデータが格納された状態を示す。この場合、図３（ｅ）に示すように物理キューを移動させ、開いた空間に被割り込み用のキューとして使われていた物理キューのレジスタを、図３（ｆ）に示すように置き、０，１，２，３，１０，１１，１２，４，５…９，１３，１４，１５をキューとする。この場合は物理レジスタ名の並び順が変わるが、キュー計算方法の特性上、プログラムの実行には何ら問題を起こさない。割り込みハンドラの処理が終わった時には、キューは図３（ｇ）のように空になる。この状態で、待避してあったキューの内容を図３（ｈ）のように復旧する。
【００４５】
〔４〕次に、キューの拡張について説明を行う。
【００４６】
図４は本発明にかかるキューの拡張の説明のための模式図、図５はそのキューの拡張の戻しの模式図である。
【００４７】
キューが不足したときキューを拡張するための仕組みとして、図４に示すように、キューと、そのキューを拡張するためのバッファと、バッファが一杯になったときそれを待避する待避用メモリを設ける。
【００４８】
計算が進んで、図４（ａ）のように、ＱＴがＬＱＨに近づき、図４（ｂ）に示すようにすべてのキューにデータが入ったとき、バッファ上にＱＴをつくる。なおも計算が進んでバッファが一杯になったとき〔図４（ｃ）〕、図４（ｄ）に示すようにバッファの内容を待避用メモリに待避し、バッファ上に次のＱＴを作る。図４（ｅ）は、なおも計算が進んでバッファの３／４までデータが格納された状態を示している。
【００４９】
その後、計算が進んで図５（ａ）に示すようにキューに空き語ができたとき、図５（ｂ）に示すように、待避用メモリに待避してあったデータをキューに戻す。なおも計算が進んでキューに空きができたとき〔図５（ｃ）〕、バッファの内容をキューに戻す。その結果、図４（ｄ）に示すようにキューは普通の状態に戻る。
【００５０】
図４（ｅ）の後なおもバッファが一杯になったときは、図４（ｃ）、図４（ｄ）を繰り返し、バッファの内容を待避用メモリに待避する。このようにバッファが一杯になったときはこのことを繰り返す。
【００５１】
〔５〕次に、仮想キューシステム（ｖｉｒｔｕａｌ  ｑｕｅｕｅ  ｓｙｓｔｅｍ）について説明する。
【００５２】
図６は本発明にかかる仮想キューシステムのメカニズムの模式図である。
【００５３】
図６（ａ）が論理キューレジスタ、図６（ｂ）が仮想キューのページテーブル、図６（ｃ）が物理キューレジスタ、図６（ｄ）がキューの内容を待避するためのメモリで、ＶＱＰ（Ｖｉｒｔｕａｌ  Ｑｕｅｕｅ  Ｐｏｉｎｔｅｒ）レジスタが示すメモリ番地から始まっている。図６（ｄ）は論理メモリと同じ構造で同じ内容を保持している。すなわち、論理キューは概念上のもので実体はメモリ上にある。この図では物理キューは４ワードで１ページを構成しており、８ページで構成されている。キューレジスタ（キュー語）ネームは８ビットで示され、これは６ビットのページ名指定部分と２ビットのページ内語を示す部分からなっている。例では、１０番のキュー語名がページテーブルの２番地とページ内語の２によって、物理キューの１ページ目の２番地が示される図となっている。
【００５４】
この方法によって、物理キューの大きさを拡張できるとともに、物理キューを構成する語の順番をページ単位で変えることができる。
【００５５】
キューへのアクセスが失敗（キューページフォールト）に終わったとき、ＱＴを含む物理ページの内容がメモリに待避され、そこに今失敗したキューページの内容がメモリから書き込まれ新しい物理キューページとなる。ＱＴを含む物理ページが追い出されるのは、キュー計算ではＱＴのデータが一番後に使われるからである。
【００５６】
図７は本発明にかかる連想ページテーブルを有する仮想キューレジスタの模式図である。
【００５７】
図７（ａ）は論理キューレジスタ、図７（ｂ）は連想ページテーブル、図７（ｃ）は物理キューレジスタ、図７（ｄ）はキューの内容を待避するためのメモリをそれぞれ示している。
【００５８】
もし、ページテーブルに連想メモリを使えば、図７のように、物理ページ数だけのページテーブル語数が必要になるだけである。
【００５９】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づき種々の変形が可能であり、これらを本発明の範囲から排除するものではない。
【産業上の利用可能性】
【００６０】
本発明のキューを主に中間結果格納用メモリとして使うキュープロセッサは、命令の高度な並列実行を実現するインターネット時代に即した高速の通信処理ツールに適している。
【図面の簡単な説明】
【００６１】
【図１】本発明にかかるサーキュラーキューの使い方を示す模式図である。
【図２】本発明にかかるキューの構成図である。
【図３】本発明にかかる、割り込みが起こって、割り込みを処理中にキューが満となり不足した場合、どのようにそれを取り扱うかを示す図である。
【図４】本発明にかかるキューの拡張の説明のための模式図である。
【図５】本発明にかかるキューの拡張の戻しの模式図である。
【図６】本発明にかかる仮想キューシステムのメカニズムの模式図である。
【図７】本発明にかかる連想ページテーブルを有する仮想キューレジスタの模式図である。
【符号の説明】
【００６２】
なし
【図１】
2005293083.tif 000003
【図２】
2005293083.tif 000004
【図３】
2005293083.tif 000005
【図４】
2005293083.tif 000006
【図５】
2005293083.tif 000007
【図６】
2005293083.tif 000008
【図７】
2005293083.tif 000009