計算資源
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/24 05:33 UTC 版)
計算資源（けいさんしげん、英語: computational resource）とは、コンピュータ科学などで、計算機（具体的なコンピュータ、そこで動くプロセスやジョブ、あるいは抽象的な計算模型）が「計算量」のために費す、具体的あるいは抽象的な「資源」である。計算機資源と言うこともあるが、その場合はプロセッサ時間や記憶装置などコンピュータのハードウェアの占有量のような具体的なものを指していることが多い。
その他に、アプリケーションプログラムの設定データのような情報をデスクトップ環境などのシステムが保存しているものを「リソース」と呼ぶことがある。詳細は、最後の#その他の節のリンク先を参照のこと。
計算資源の例
プロセッサ時間とメモリ使用量が代表的な資源である。
そのほか、2次記憶、入出力装置など、情報処理のためのあらゆる機器が資源となる。物理機器に限らず、ファイルやネットワーク接続、メモリ空間なども仮想資源である。
計算資源と計算複雑性理論
最も単純な計算資源は、計算時間とメモリ使用量である。計算時間は問題を解くのに要するステップ数で表され、メモリ使用量は問題を解くのに要する記憶領域の量で表される。これらよりも複雑な資源も定義されている。
計算問題は一般に、妥当な入力を与えられたときの動作によって定義される。例えば、「整数 n を与えられたとき、n が素数かどうかを判定せよ」という問題、「2つの数 x と y を与えられたとき、積 x*y を求めよ」という問題などがある。入力が大きくなれば、必要な計算資源の量も増える。従って、問題を解くのに要する計算資源の量は、入力の長さや大きさの関数として表される。
問題を解くのに要する計算資源の量を研究することは重要であり、それによって、ある問題を解くアルゴリズムが最適かどうかを判断できる。ある一定の量の計算資源を使って解ける問題の集合を複雑性クラスと呼び、異なる複雑性クラス間の関係が計算複雑性理論での重要な話題となっている。
計算能力の定量化についても、様々な努力がなされてきた。制限されたチューリングマシンを使って計算をモデル化し、状態遷移数やアルファベットの大きさで特定の問題を解くのに要する計算能力を表す[1] [2]。
計算資源の管理
システム資源管理
OSがジョブやプロセスの資源使用を管理する機能をシステム資源管理 (system resource management = SRM) という。SRMの管理下にある資源をシステムリソース (system resource) と言う。
リソースハンドルは現にアクセス中の資源の識別子である。リソースハンドルは整数値やさらなる情報へのポインタなどで表される。代表的なリソースハンドルとしてファイル識別子やソケットがある。
オペレーティングシステムや仮想機械などは確保され使用された後で解放されていない資源へのアクセスを完了させる機能がある。これをリソーストラッキングと呼ぶ。仮想機械で実装する際にはガベージコレクションの形をとることが多い。
メモリ空間へのアクセスはセマフォで制御することが多いが、それがデッドロックと呼ばれる異常状態を引き起こすことがある。それは例えば複数のスレッドやプロセスの間で、他が確保している資源を互いに確保しようとしたときに発生する。デッドロックが発生するとプログラムは応答不能の状態となることが多い。
資源へのアクセスはキューを使って制限されることがある。CPUの計算時間の場合、タスク (コンピュータ)キューの制御アルゴリズムをスケジューリングと呼ぶ。
ユーティリティコンピューティング
ユーティリティコンピューティングは、機器自体ではなくそれが提供する計算資源を売買することである。
その他
- X Window SystemのXリソース（en:X resources）
- Mac OSのリソースフォーク
- Windowsのリソースとシステムリソース
出典
- ^ Gregory J., Chaitin (1966年). “On the Length of Programs for Computing Finite Binary Sequences”. Journal of the ACM (JACM) Volume 13 (Issue 4): 547 - 569 2007年9月25日閲覧。.
- ^ Sow, Daby; Alexandros, Eleftheriadis (1998年). "Representing Information with Computational Resource Bounds" (PDF). Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar. Vol. 1. pp. 452–456. ISBN 0780351487. 10.1109/ACSSC.1998.750904. 2007年9月25日閲覧。
計算資源
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/12/06 00:17 UTC 版)
「交替性チューリング機械」の記事における「計算資源」の解説
上述の定義を使って、ある ATM の構成が受理状態なのか拒絶状態なのかを決定する場合、現在の構成から到達可能なあらゆる構成を全て調べる必要はない。特に存在的構成は、そこから遷移する構成に受理状態のものが1つでもあれば、受理状態であると言えるし、全称構成は、そこから遷移する構成に拒絶状態のものが1つでもあれば、拒絶状態であると言える。 ATM は、長さ n {\displaystyle n} の任意の入力が特定の形式言語に属するかを時間 t ( n ) {\displaystyle t(n)} で決定する。すなわち、初期構成が受理状態か拒絶状態かを決定するのに、高々 t ( n ) {\displaystyle t(n)} ステップまで構成を調べればよい。また、必要な領域は s ( n ) {\displaystyle s(n)} で十分である。 ATM で、時間 c ⋅ t ( n ) {\displaystyle c\cdot t(n)} （ c > 0 {\displaystyle c>0} は定数）で決定される言語は、クラス A T I M E ( t ( n ) ) {\displaystyle {\rm {ATIME}}(t(n))} に属し、領域 c ⋅ s ( n ) {\displaystyle c\cdot s(n)} で決定される言語は、クラス A S P A C E ( s ( n ) ) {\displaystyle {\rm {ASPACE}}(s(n))} に属する。
※この「計算資源」の解説は、「交替性チューリング機械」の解説の一部です。
「計算資源」を含む「交替性チューリング機械」の記事については、「交替性チューリング機械」の概要を参照ください。
計算資源
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 20:32 UTC 版)
計算複雑性理論は計算問題の難しさを様々な計算資源の観点で分析する。時間、空間、無作為性、反復性、その他のより直観的でない尺度などで必要とする計算資源量によって、同じ問題を説明する。複雑性クラスはある特定の計算資源をある特定の量つかって解くことができる全計算問題の集合である。 最も研究が進んでいる計算資源は決定性時間(DTIME) と決定性空間(DSPACE) である。これらの資源はそれぞれ、決定性のある計算機（例えば実在する普通の計算機）で問題を解くのに必要な「計算時間（演算回数）」と「記憶装置」の量に対応している。これらの資源の使用量を求めることは実用的な意味もあり、研究が進んでいるのである。 いくつかの計算問題は非現実的な量の資源を想定すれば、より容易に解析可能である。例えば、非決定性チューリング機械は、分岐して様々な可能性を同時にチェックできるという計算モデルである。したがって、非決定性チューリング機械はアルゴリズムを使って具体的に計算する作業とは全く関係ないが、その分岐によって分析したい計算モデルの大部分を捉える。このため非決定性時間は計算問題を分析するにあたって非常に重要な資源である。 計算複雑性理論では他にもいろいろな計算資源を考慮する。技術的には、複雑性尺度として計算資源量が扱われ、これに関してはブラムの公理で非常に一般的な定義が与えられている。
※この「計算資源」の解説は、「計算複雑性理論」の解説の一部です。
「計算資源」を含む「計算複雑性理論」の記事については、「計算複雑性理論」の概要を参照ください。
計算資源と同じ種類の言葉
固有名詞の分類
- 計算資源のページへのリンク
