キュー（queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し(FIFO: First In First Out)のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー（Enqueue）、取り出すことをデキュー（Dequeue）という。
現在一般的に使われているコンピュータ（レジスタコンピュータ）は、レジスタを高速な中間結果格納用メモリとして計算を行う”レジスタ計算モデル”を用いている。スーパスカラコンピュータはその代表で、並列性をプロセッサ内で抽出する事によって高速化をはかっている。
ただし、レジスタの数は限られているので、“レジスタの内容を使い終わってからしかそのレジスタを再利用できない”という偽従属性問題を持ち込み、それが並列実行を阻害していた。偽従属性問題は実質的にレジスタ数を増やすというレジスターリーネーミング手法によって解決を図る試みがなされているが、そのためのハードウエアが複雑になり、また、並列性の抽出にも限界があり、それが高性能化を妨げていた。
キューコンピュータは、中間結果格納用にキュー(先入れ先出しFIFOレジスタ）を用いる”キュー計算モデル”を用いるプロセッサである。キュー計算モデルではキューを中間結果格納用に使うので、命令表記にオペランドとしてのキューレジスタの記述が不要で、プログラムは問題が持っているすべての並列度を表現でき、同時に実行可能な命令が必ず連続して現れるという特徴を持っている。たとえば、現在の計算機ではr3←r2 + r1を行う命令は”add r3,r1,r2”と書くが、キュー計算方法では”add”と書くだけでよい。
キューコンピュータは、命令長とプログラム長が短く、並列発見が容易で問題が持つすべての並列性を発見でき、その並列度でプログラムを実行でき、簡単なハードウエアで高性能で省電力なコンピュータである。当然、現在のコンピュータにおけるようなレジスタに関するハザードが起こらない。
すなわち、キューコンピュータは、
プログラム量が少ない（約1/2）
並列度が大きく高いパフォーマンス
レジスタリネーミングが不必要
並列性抽出が簡単
ハザードが起こらない
ハードウエアが簡単
小さなハードウエアで消費電力が少ない
クロック周波数が高くできる
キャッシュメモリや主メモリが少なくて良い
メモリとプロセッサ間のデータのトラフィックが少ない
などの特徴がある。
キューコンピュータの研究は1985年カナダで始められたが、研究が現在「生産消費順序型キュー計算モデル」と言われるモデルに基づいていたので、その特徴を発見できずその後研究されることはなかった。しかし、最近では「消費順序遵守型キュー計算モデル」、「生産順序遵守型キュー計算モデルが提案されたことにより、並列化による高性能化の可能性と短いプログラム長に注目が集まり、実用化に向かっての研究が特に日本で盛んになりつつある。
プリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。
キューの変形として、先頭と末尾の両端から入出力を行えるものを両端キュー(double-ended queue, deque)という。
キューとは逆にLIFO（後入れ先出し）のリスト構造を持つデータバッファをスタックと呼ぶ。
キューの応用
メッセージキュー: メッセージのキュー
メッセージ・キュー (UNIX): msgsnd() および msgrcv() システム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。
メッセージ・キュー (Windows): GUI プログラムへイベントを送信するのに用いる。これをイベント駆動型プログラミングという。プログラムはメッセージ・ループでイベントを受信し、適切な動作を行うように作られる。
プログラミング言語のライブラリでの実装: プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。
ミドルウェアによる実装: 主にあるプログラムから他のプログラムへデータを送信するためにキューを利用しているミドルウェアが作られている。
外部リンク
⇒キューの可視化（まとめ）
して下さる人を求めています（Portal:コンピュータ）。
カテゴリ: データ構造 | データ型 | コンピュータ関連のスタブ項目
更新日時:2008年7月1日(火)18:54
取得日時:2008/09/21 04:46
