フォン・ノイマン・ボトルネック

フォン・ノイマン・ボトルネックとは

フォン・ノイマン・ボトルネックとは、ノイマン型アーキテクチャに存在するボトルネックである。

ノイマン型アーキテクチャとは

そもそも、「コンピュータアーキテクチャ」とはコンピュータシステムの基本設計・構成・仕様、及びそれらに基づいた構造などのことを言う。
すなわち、ソフトウェア・ハードウェアを用いてコンピュータをどのように構成するか、を定めたものがコンピュータアーキテクチャである。
アーキテクチャはあくまで基本設計を指す言葉であり、具体的な実装や規約を指す言葉ではない。
※ソフトウェア=コンピュータを動作させるためのプログラムやデータの集合。
※ハードウェア=システムの物理的な構成要素。例:モニター、HDD、キーボード、マウス、プロセッサ。

上に述べたものは広義のコンピュータアーキテクチャである。狭義のコンピュータアーキテクチャとは、すなわち命令セットアーキテクチャのこと、もしくはソフトウェア側から見たハードウェアの仕様のことである。
命令セットアーキテクチャとは、プロセッサがどのような命令を実行し、どのような結果が得られるかを定めたものである。(cf.マイクロアーキテクチャ=プロセッサの具体的なハードウェア構造)
※プロセッサ=コンピュータのデータ演算やプログラム実行、制御を担う処理装置。≒CPU。

ノイマン型アーキテクチャとは、制御装置・演算装置(処理装置)・記憶装置・入出力装置をもち、ストアドプログラム方式・逐次制御方式を用いる構成のコンピュータアーキテクチャのことである。ノイマン型コンピュータともいう。(尚、他にも線形アドレス空間や2進数演算を行うという特徴がある。)
制御装置は機械語命令を解析、制御信号を出力し各装置の動作を制御する。演算装置は制御装置から与えられる制御に従い演算を行う。制御装置と演算装置はプロセッサに集約される。
記憶装置はキャッシュメモリ・メインメモリのことである。一次記憶装置を指し、二次記憶装置のことは指さない。
入出力装置はキーボード、マウス、スピーカー、プリンターなどのことである。
ストアドプログラム方式(プログラム内蔵方式・プログラム蓄積方式)とは、処理するプログラム・データを予め記憶装置内に格納しておく方式である。
逐次制御方式とは、命令をアドレスの小さい方からメモリから1命令ずつ読みだして逐次実行する方式である。この制御を行うのがプロセッサ内のプログラムカウンタ(PC)である。プログラムカウンタは次に実行するべき命令が入っているアドレスを記憶する専用レジスタである。
※レジスタ=CPU内部にある記憶素子。
※ストアドプログラム方式でない方式として、データフロー制御方式がある。
※命令を制御する方式として、逐次制御方式の他に、パイプライン制御、スーパースカラ等がある。

ノイマン型アーキテクチャ以外のコンピュータアーキテクチャは存在する。具体的には、ハーバードアーキテクチャ等である。

ジョン・バッカスとフォン・ノイマン・ボトルネック

ジョン・バッカスはアメリカの数学者である。Fortran・BNF(バッカス・ナウア記法)の発明者である。
※Fortran=世界初の高級プログラミング言語。数値計算に適している。
※BNF=文脈自由文法を定義するのに用いられる文法。文脈自由文法について述べるとかなり長くなるのでここでは述べない。簡単に言えば、プログラム言語を規定するためのメタ言語。プログラム言語がどのような構文によって構成されるかを示すものがBNFである。昨今、BNFはプログラミング言語の定義だけではなくHTMLやXMLの構文定義にも用いられている。
このような業績から、ジョン・バッカスは1977年のACMチューリング賞を受賞した。
※ACMチューリング賞=計算機科学分野で革新的な功績を残した人物に送られる賞。計算機科学分野におけるノーベル賞とされる。

このACMチューリング賞受賞にあたり、ジョン・バッカスは『プログラミングはフォン・ノイマン・スタイルから解放されうるか?関数型プログラミング・スタイルとそのプログラム代数』という論文を発表した。
ジョン・バッカスはこの論文でこれまでのノイマン型アーキテクチャの問題点を指摘し、FPという言語を例に関数型プログラミング言語の重要性を訴えた。ここで指摘した問題点こそが、フォン・ノイマン・ボトルネックである。
先の論文上では、フォン・ノイマン・ボトルネックについて以下のように述べられている。

フォン・ノイマン式計算機は次の三つの部分をもつ.すなわち中央演算装置(CPU),記憶装置と,この二つの部分を繋いで“1語”を伝送する管である.私はこの管をフォン・ノイマン隘路(von Neumann bottleneck)と呼ぶことを提唱する.

ノイマン型アーキテクチャでは、バス(論文では管とされている)を通じてプロセッサと主記憶装置が結ばれる。
※バス=データや信号の伝送路。CPUや記憶装置・入力装置はバスで接続される。
プロセッサが命令を実行するためには、バスを通して記憶装置にアクセスしなければならず(ストアドプログラム方式=記憶装置内に命令が入っている)、プロセッサの処理速度と記憶装置のアクセス速度に差があること、また信号伝達速度の高速化には限界があることから、転送性能に制限が生じる。つまり、CPUの処理能力にも限界ができてしまう。これがボトルネックとなる。(ボトルネックとは管自体を指す語である。)これは、ストアドプログラム方式に共通のことであるが、ストアドプログラム方式の代表がノイマン型であるため、このように呼ばれる。
しかも、ここでやり取りされるデータの多くは、意味のあるデータではなくアドレスなのである。C言語ではプログラマがアドレスを意識しなければならないし、Java等の一見アドレスを意識する必要のない言語であっても、それは言語によってアドレスが隠蔽されているだけであり、内部でアドレスを多用していることに変わりはない。
※アドレス=データがどこにあるかを示すもの。アドレス自体は意味のあるデータではない。
アドレスが多用される原因は、変数である。全ての変数はアドレスによって管理される。つまり、変数を用いてデータを扱う手続き型言語は、アドレスから逃れられない。
ノイマン型アーキテクチャは、逐次制御方式を採用しているため、手続き型からは逃れられない。
本来並行性をもつアルゴリズムを逐次実行を基本とするアーキテクチャで実行させるために手続き型で記述していることに対しての問題提起と捉えることもできる。同時実行の際、同期などの問題に直面するのはノイマン型であるが故である。
他にも、副作用が存在したり(我々は状態変化による副作用を利用している)、数学的枠組みの欠如といった問題点がある。
これを解決するため、ジョン・バッカスは関数型プログラミング言語を示した。これならば、変数は排除され、アドレスの多用も抑えられる。更に、プログラマが手続きを記述しなければならないという手続き型プログラミングからの解放への道筋も示したのだ(→非ノイマン型アーキテクチャ)。

関数型プログラミングと手続き型プログラミング

関数型プログラミングとは、全てを関数で記述・処理しようとする手法である。作用順序だけを規定し、内部の実行順序は既定しない。遅延評価を行う。宣言型プログラミングの一つである。(厳密な定義については現在も議論がなされているようで、ここでは述べない)ここでの関数は、数学でいう関数であり、C言語等における関数ではない。例:Haskell、Scheme、F#、(LISP)
※遅延評価=値が実際に必要になるまで式を実行しないこと。

それに対して、手続き型プログラミングとは、コンピュータが実行する命令・手続きを順に記述することでプログラムを構成する手法である。命令型プログラミングの一つである。例:C言語、Java、Python

フォン・ノイマン・ボトルネックの解消に向けて

一般的に、コンピュータの処理速度は速ければ速いほど良いものであり、ボトルネックを解消した方がよいことは自明である。では、現在のコンピュータにはどのような工夫が施されているのだろうか。まず、ボトルネックの完全な解消ではなく影響を弱める工夫、特にCPUの高速化の工夫が施されてきた。

最も単純な方法は、作動周波数を上げることである。だが、一定周波数以上になるとボトルネックにより高速化には繋がらなくなり、また消費電力も大きくなるという欠点が生じる。

次に、キャッシュメモリの導入、すなわち記憶の階層化である。キャッシュメモリは、プロセッサ内にある高速・小容量なメモリで、メインメモリから読み込んだ命令・データを一時的に保存する。プロセッサがメモリにアクセスする際、まずはキャッシュメモリにアクセスし、もし必要なデータがキャッシュメモリにあれば(=キャッシュヒット)それを使い、キャッシュメモリに必要なデータが無ければ(=キャッシュミス)メインメモリにアクセスする。メインメモリを無くし、全てキャッシュメモリにすれば高速化が実現すると思うかもしれないが、キャッシュメモリは非常に高価で、現実的ではない。また、最近は2~3つのキャッシュメモリをもつプロセッサもある。高速・低用量順に1次キャッシュ(プライマリキャッシュ・L1)、2次キャッシュ(セカンダリキャッシュ・L2)、3次キャッシュ(L3)となる。この場合、プロセッサからのアクセス順は1次キャッシュ→2次キャッシュ→3次キャッシュ→メインメモリとなる。

プロセッサ内部で命令を実行するとき、内部ではメモリアドレス設定・命令の読み込み(フェッチ)・命令レジスタへの転送・命令デコード・演算・結果の書き込みと複数の段階を経て一つの命令の実行が行われる。通常は、この一連の流れが全て終わらないと次の命令を処理することはできないが、この各段階を別々の回路で処理することにより複数の命令を並行して処理できる(並列処理)。これをパイプライン方式(もしくはパイプライン処理)という。パイプラインとは、前段階の出力を自身の入力、自身の出力を次段階の入力となるように相互接続されたような仕組みである。特に、プロセッサ内の前述したようなパイプラインは命令パイプラインと呼ばれる。
例えば、命令1と命令2を実行するとしたとき、命令1のメモリアドレスが設定しフェッチに段階が移った後、命令2のメモリアドレス設定を開始することが出来る。
前述したような複数の段階を更に細かく分割した方式を、スーパーパイプライン方式という。

更に、このパイプラインの仕組み(論理回路)を複数個並べ、同時に複数の命令を実行する方式として、スーパースカラ方式がある。依存関係にある命令は同時に実行できない。

CPUが命令を読み込む際、複数の命令を長い1つの命令として同時に実行するプロセッサの方式をVLIWという。スーパースカラ方式と異なり、コンパイラにより予め依存関係のない命令となっているためプロセッサ側の動作が簡略化できる。

パイプラインを用いて複数の命令を実行している際、途中に分岐命令が含まれると分岐先が確定するまでその先の命令を実行することが出来ない。このとき、どちらに分岐するかを予測し(分岐予測)、予測先の命令を実行することを投機的実行という。結果的に間違った分岐先に進んだ場合、分岐後の処理は取り消される。だが、投機的実行及びアウトオブオーダー実行(後述)には「Spectre」・「Meltdown」と呼ばれる脆弱性を抱えており、2018年に問題となった。

一台のコンピュータに複数のCPUを搭載し処理を分散させる技術をマルチプロセッサという。1つのプロセッサ内に複数のプロセッサコア(CPUコア)を搭載し並列処理を可能としたプロセッサをマルチコアプロセッサという。

CPUの高速化に限らず、別の観点からボトルネックを解消しようとしたアーキテクチャもある。命令とデータでメモリを分けるアーキテクチャをハーバードアーキテクチャという。メモリを2分割し、バスも2分割する。組込マイクロコントローラで採用されることが多い。単一のプログラムしか動かさない場合によく用いられる。

フォン・ノイマン型アーキテクチャからの脱却

フォン・ノイマン・ボトルネックが生じるならば、情報処理の高速化・高度化のためにその根本的な原因であるノイマン型アーキテクチャからの脱却を試みるのは自然な流れだろう。これを非ノイマン型アーキテクチャという。これらの定義については議論のなされる部分である。多くの場合、非ノイマン型アーキテクチャはある特定の問題に特化して設計されている。

データフローアーキテクチャは、データの流れに従って処理を行い、必要なデータが揃った演算命令から順に命令が実行されるというアーキテクチャである。このような計算方式をデータ駆動という。これは、部分的にアウトオブオーダー実行としてプロセッサ内で用いられている。イメージとしては、Excelで他のセルを参照して計算する、といったものに近い。

量子コンピュータは、量子力学的な重ね合わせを用いて並列処理を行うものである。大きく、量子ゲート方式と量子アニーリング方式の二つに分けられる。

他にも、データフローマシンやニューロコンピュータ等が非ノイマン型アーキテクチャとして知られている。

参考

電子情報通信学会 知識ベース 6群4編1章(http://www.ieice-hbkb.org/files/06/06gun_04hen_01.pdf
電子情報通信学会 知識ベース 6群4編3章(http://www.ieice-hbkb.org/files/06/06gun_04hen_03.pdf
日立ソリューションズ IT用語辞典(https://it-words.jp/w/E382B3E383B3E38394E383A5E383BCE382BFE383BBE382A2E383BCE382ADE38386E382AFE38381E383A3.html:リンク切れ)
IT用語辞典 e-Words(http://e-words.jp/w/%E3%83%8E%E3%82%A4%E3%83%9E%E3%83%B3%E5%9E%8B%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF.html
Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs(https://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf
JOHN BACKUS著、米澤明憲訳 『プログラミングはフォン・ノイマン・スタイルから解放されうるか?関数型プログラミング・スタイルとそのプログラム代数』『ACMチューリング賞講演集』 共立出版 1989年
非フォンノイマン型計算機(https://www.jstage.jst.go.jp/article/ieejjournal1888/105/8/105_8_741/_pdf/-char/ja

 

何か間違っていたら教えて下さい。

# 課題でボトルネックについてまとめろ…みたいな小レポ(クリスマスプレゼント?)が出た人はこんなの見ずに自分で考えた方が良いと思います。頑張って下さい。

コメント

タイトルとURLをコピーしました