結構前に読んだけど読み返したくなったので今日から読む

junyaU 18日前に更新

1.1

昔は、メモリ容量の制約をクリアすることが性能のよいプログラムにおける条件であった。しかし現在は技術の発展によりその制約を気にすることはなくなり、プロセッサの並列性や記憶階層の理解を求められている。

プログラムの性能を左右する要因

プログラムの性能はソフトウェアとハードウェアの両方が影響する。

アルゴリズム

コードのサイズや、実行する入出力命令の数を決定する。

プログラミング言語やコンパイラ

コードに対する、コンピューター命令の数を決定する。

プロセッサ

コンピューター命令の実行の速さを決定する。

入出力装置

入出力の速さを決定する。

1.2

コンピュータアーキテクチャにおける8つの主要なアイデア

Mooreの法則

集積回路の密度が18~24か月ごとに倍増するという法則。
コンピュータの設計は通常長い期間を要するが、設計を始めてから終了するまでに、集積回路の密度が数倍になっているということは大いにあり得る。なので、設計をするときは終了時にどのぐらい密度が上がるのかの見通しを立てておくことが重要。

抽象化

上位レベルの階層では下位レベルの階層の詳細が隠蔽されることによってそれぞれの階層の構造が単純になるというもの。

並列化

コンピュータはどのように並列に処理を行うことによって性能が改善するのかというのが重要。

一般的な場合の高速化

稀なケースの最適化を行うよりも、一般的なケースの改善を行ったほうが性能の向上がしやすいというもの。また、一般的なケースのほうが単純である場合が多い。

パイプライン処理

並列に処理を行う手法としてよく使われるやつ。
火消しのために大勢の人がバケツリレーを行ったほうが、一人一人が行ったり来たりするより良いという例は良い例だなと思った。

予測

物事が確定する前に、予測を付けて先んじて進めるほうが結果的に早いケースが多い。
しかしこれは予測が外れた際に戻るコストが高すぎないことと、正確な予測を行っている前提ではある。

冗長性

コンピューターにおいて信頼性は重要でその手段としての冗長化。
台数を増やすことで信頼性増すよねというやつ。

記憶階層

一般に記憶装置は、高速なほど小容量であり低速なほど大容量である。プログラマが求めているのは、高速かつ大容量な記憶装置であるが、これを階層（低速大容量なほど下層）にすることで、あたかも高速大容量な記憶装置があると錯覚するというのが記憶階層。

1.3

現代のプログラミング言語は非常に多機能で複雑となっている一方、コンピューターは単純な低レベルの命令しか実行することができない。プログラミング言語から機械語に至るまでには、いくつかのソフトウェアの層を経由し翻訳しなければならないが、これは抽象化である。

アプリ → システムソフトウェア（OS、コンパイラ） → ハードウェア

初期のプログラマは二進数を直接読み書きしていた。機械語は人間にとっての可読性が悪いので、機械語と一対一で対応するアセンブリ言語が作られた。またアセンブリ言語から機械語に翻訳するためのアセンブラも開発された。
ただ、アセンブリ言語で開発するというのは、コンピューターの動作に対して１行ずつ命令を書かなければならないので、プログラマはコンピューターのように思考することを強いられた。
そこで高水準言語と、コンパイラがつくられた。
高水準言語の大きな利点は３つ。一つ目は、英語と代数式で表すので自然言語に近い形で思考することができるようになったということ。二つ目はプログラマの生産性の向上。
そして三つめは、プログラムをコンピューターから独立させることができるようになったということ。
コンパイラやアセンブラでは任意のコンピューター向けの機械語を生成できるので、プログラムがコンピューター依存しなくなったというのがかなり大きい。

1.4

メインメモリはDRAMチップで構成されている。RAMはどの位置のデータにアクセスする場合でも読み取り時間は一定である。キャッシュメモリはSRAMで構成されいる。SRAMはDRAMより効果でありアクセス速度が速いが、集積密度が低いのでデータ容量自体は少ない。
これらは揮発性メモリであり、電源を落とすとデータが消える。磁気ディスクなどの不揮発性メモリは電源を落としてもデータが消えない。メインメモリのことを一次記憶と呼び、磁気ディスクを二次記憶と呼んだりする。
記憶階層でこれらを表すと、キャッシュメモリ > メインメモリ > 磁気ディスク

junyaU 18日前に更新

コンピューターの5つの構成要素

入力
出力
記憶
データパス
制御

プロセッサ = データパス&制御
データパスは手足の役割、制御は神経系とたとえられている。
データパスは演算処理を行う。制御はプログラムの機械語命令に従って何を行うべきかをメモリやデータパスに伝える。

junyaU 18日前に更新

DRAM、フラッシュメモリ、磁気ディスクの比較

揮発性

DRAM : 揮発
フラッシュメモリ : 不揮発
磁気ディスク : 不揮発

アクセス時間

DRAM : 50㎱
フラッシュメモリ : 5~50㎲
磁気ディスク : 5~20㎳

コスト（2012年における）

DRAM : ギビバイトあたり5~10ドル
フラッシュメモリ : ギビバイトあたり0.75~1ドル
磁気ディスク : ギビバイトあたり0.05~0.1ドル

junyaU 18日前に更新

命令セットアーキテクチャ（ISA）は、OSとハードウェア間のインターフェースである。OSがハードウェアの詳細を理解する必要はなくISAを通じてハードウェアを操作することができる。アーキテクチャ（ISA）を知っていればアーキテクチャの実装方式（ハードウェアの詳細）を知らなくてもよいという抽象化であるといえる。アプリとOS間のインターフェースであるABIもこの抽象化に当てはまる。

アプリ → ABI ← OS → ISA ← ハードウェア

このような抽象化によってアプリケーションはOSから独立することができ、OSもハードウェアから独立することができる。またそれぞれの詳細を知らなくてよいので、それぞれの層をシンプルにすることができる。

コンピュータって改めてすごいなあ

junyaU 15日前に更新

クロックサイクル数 = プログラムの実行で発生したクロックの数
クロックサイクル時間 = クロックごとの間隔
クロック周波数 = 1秒間で発生したクロックの数

クロック周波数はクロックサイクル時間の逆数だといえる。

CPU時間 = クロックサイクル数 * クロックサイクル時間
or
CPU時間 = クロックサイクル数 / クロック周波数

コンパイラはプログラムから機械語命令を生成し、ハードウェアはその機械語を実行するわけだから、少なからずプログラムの実行時間は機械語命令の数に左右されるはずである。

クロックサイクル数 = プログラムの実行命令数 * 1命令あたりのクロックサイクル数（CPI）

junyaU 14日前

1.6

コンピュータ性能を測定するとき、愚直にプログラム実行の開始から終了時間を取って性能を計測するのは一概に正しいとは言えないなと思った。
プログラムの性能評価に時間を用いることは正しい。
しかし、ユーザーが知覚するプログラムの経過時間には他のタスクの実行も含まれているはず。なぜならOSのマルチタスクスケジューリングによってCPU時間が色々なタスクに割り与えられそれぞれのタスクを少しずつ実行しているからである。
経過時間の計測だと、タスクの待ち行列が混雑しているかによって結果が左右されるはずなので、プログラムの実際のCPU時間を計測し、それを基に性能を評価すべきである。

ユーザーCPU時間 : プログラムに実際に費やしたCPU時間
システムCPU時間 : プログラム実行以外のOSの実行部分のCPU時間

システム性能 : システム上でのプログラムの経過時間
CPU性能 : ユーザーCPU時間

クロックはシステムで何か動作を起こすときのタイミングとなる。

クロックサイクル数 : プログラムの実行で何回クロックが発生したか
クロックサイクル時間 : クロックの間隔の時間
クロック周波数 : 1秒間で何回クロックが発生したか（クロックサイクル時間の逆数）
CPI = 1命令あたりの平均のクロックサイクル数

CPU時間 = 実行命令数 * CPI * クロックサイクル時間 or 実行命令数 * CPI / クロック周波数

コンピュータの性能を測定するときの信頼できる測定基準は時間である。

プログラムの性能は以下に左右される。

アルゴリズム : 命令数,CPIに影響
プログラミング言語 : 命令数,CPIに影響
コンパイラ : 命令数,CPIに影響
命令セットアーキテクチャ(ISA) : 命令数,CPI,クロック周波数に影響

junyaU 12日前に更新

1.7

電力が消費されると、ジュール熱として発散されるためプロセッサが熱くなる。

クロック周波数と消費電力は相関関係がある。
クロック周波数は消費電力の高さと発熱の問題によってこれ以上上げるのには限界がある。クロック周波数を一定の閾値以上に引き上げてしまうと、冷却技術が追い付かなくなる。
この熱は、プロセッサの性能に影響を与えるだけでなく寿命も短くする。
このような電力と冷却性能の壁に突き当たってしまったため、シングルプロセッサからマルチプロセッサに転換することを強いられた。

1.8

シングルプロセッサの時は、ハードウェア、アーキテクチャ、コンパイラの性能向上が直接プログラムの性能向上につながった。ムーアの法則により集積回路の密度が18か月ごとに上昇したのでその恩恵をそのまま得ることができた。
しかし、マルチコアプロセッサの時代に突入してからは、性能を上げたければプログラマがマルチコアの恩恵を受けられる（つまり並列処理）プログラムの組み方をする必要が出てきた。

並列処理の隠蔽
コンピュータの性能向上に並列処理を用いるというのは、古くから使われてきた手法であった。しかしそれは表に出すものではなかった。パイプライン処理などがまさにそう。パイプライン処理はコンピューター命令を並列で実行できる技術のことだが、プログラマは、ハードウェアが逐次的にプログラムを実行できると思い込んでいる。並列処理は人間が扱うには複雑な要素なので隠蔽することが常であったが、マルチコアプロセッサの登場によりこのタブーは破られることとなった。

並列処理の難しさは大きく二つある。

性能の向上にフォーカスする必要があるから
タスクを並列に実行できるように分割する難しさ

例えば処理を三つに分割しても、一つの処理が重すぎるのなら結果的に待つことになり並列化のメリットはあまり得られない。またどこか一つの処理が別の処理の結果に依存するのならば待ち合わせの必要も出てくるので良い結果は得られない。
スケジューリング、負荷平準化、意思疎通のオーバーヘッドの抑制が大事になる。

1.9

プログラムの実行はコンピュータにとって負荷であり、この負荷をもとにコンピュータの性能を評価することができる。こうした場合、任意のユーザーアプリケーションを使用するのではなく性能を測定するためのプログラム（ベンチマーク）が使用される。
SPEC(System Performance Evaluation Cooperative)はコンピューターシステム用のベンチマークスイートを開発することを目的とした団体である。

junyaU 12日前に更新

1.10

誤信や落とし穴にはまってしまう主要な原因は、一定の条件で成り立つ原理を一般化してしまうこと。
コンピューターにおいて誤解しがちなことを列挙する。

コンピュータのある面を改善することによって、その改善度に等しい性能向上が得られる

コンピューターのある面を50%改善しても、50%の性能があがることはほとんどない。
例えば、処理時間が10秒かかる乗算の処理が80%を占めるプログラムの乗算処理を5倍速くするために乗算処理の改善を試みる場合を考える。

2 = \frac{8}{n} + 10 - 8

結果は 0 = 8/n となり、これはいくら乗算を改善しても結果の速度が5倍以上にならないことを示唆する。
性能の向上は、その改善した機能の使用されている割合に制限されてしまう。このような事象を経済学では収穫逓減と呼ぶらしい。

コンピュータの利用率が低ければ、消費電力は少ない

利用率ピーク時の電力が100%だとすると、利用率10%の時の電力は10%とはならないらしい。

性能を上げる設計とエネルギー効率を上げる設計は目標的に無関係

性能を上げる = 実行速度を上げるということであり、実行速度が速いということは負荷がかかる時間が少なるということである。たとえ実行速度を速くしたことで実行時の消費電力が多少上がっても、エネルギー効率は上がる。

性能の尺度に性能方程式の一部を用いる

性能方程式の要素は、命令実行数・CPI・クロックサイクル時間であるが、3つを使わず1or2個の要素を使って性能を測るというのは正しい結果が反映されない。
MIPS(Million Instructions Per Seconed)は秒あたりの命令数（百万単位）だが、時間の尺度が反映されていない。MIPS値は命令セットの違うコンピューター同士の比較は命令数が違うためできない。

MIPSは単に多くの命令を高速に実行できることを示すものであり、それらの命令が単純で実行効果が低い場合、処理性能が高いわけではないのでMIPSでコンピューターを評価することは誤解を招くケースが多い。

junyaU 12日前に更新

ここまでのまとめ

コンピュータシステムは階層的に構成されており、下位水準の詳細を上位水準は見せないようにする。この抽象化がコンピューターを理解する上での基本である。抽象化の中でも特に重要なのが、OSとハードウェア間のインターフェースであるISA（命令セットアーキテクチャ）である。
ハードウェアは定義されたISAに準拠することで、新しいハードウェアや古いハードウェアの上でも同じようにプログラムを動かすことが可能になる。逆に言えば、この決められたインターフェースのせいで、インターフェースの変更を必要とする技術革新を阻害する可能性はある。

コンピュータの性能を測るうえで、唯一信頼することができるのは実行時間である。ほかの尺度で性能を測定する試みは、一定条件下で成り立つ原理の一般化（拡大解釈）であることが多い。
実行時間の求め方

\text{実行時間} = \text{実行命令数} \times \left(\frac{\text{クロックサイクル数}}{\text{命令}}\right) \times \left(\frac{\text{秒数}}{\text{クロックサイクル}}\right)

クロックサイクル時間の逆数であるクロック周波数を用いることもできる。

マイクロプロセッサの設計における重要な要因は、ダイの面積から電力に変化していった。

性能向上しながら電力を節減するために、マルチコアプロセッサへの転換を余儀なくされた。これによってソフトウェア業界でも、並列プログラミングに切り替えざるを得なくなった。

コンピュータの五大要素

データパス
制御
記憶
入力
出力

junyaU 10日前に更新

コンピュータの一部をどれだけ高速化しようと、高速化されなかった部分が高速化の制約となる。
→ 確かに考えてみれば、アムダールの法則と収穫逓減は同じことを言ってるな

junyaU 10日前に更新

2.1

コンピュータの言語 → 命令
コンピュータの語彙 → 命令セット

命令セットは色々種類があるものの内容としては類似している。
類似している理由としては、ハードウェアの根本原理は同じように設計されていること、性能を上げて消費電力とコストは減らしたいという共通の目標があるから結果として同じようなものになることが多い（方言みたいな）。

2.2

MIPSのアセンブリ言語について。
MIPSではどの命令でも必ず3つのオペランドを取るようになっている。そのように統一することで単純にできるからである。逆にオペランドが可変長だとより複雑なものになってしまう。
これはハードウェアの設計原則の一つである「単純性が規則性につながる」の最たる例。

junyaU 8日前に更新

2.4

最上位ビット = MSB
最下位ビット = LSB

コンピュータで正と負の数を表現するために、今までいろいろな案が出されてきた。
例えば符号付き絶対値表現は、符号を表す1ビットを用意しそれを別に追加する方法。
一見よさそうに見える方法だが、いろいろなデメリットがある。

0に正と負の概念ができてしまう。
計算後の数値の符号は計算しないと求められないので、加算器で余分なステップ（符号設定）が必要になる。
その符号用のビットをどこに配置すべきかが明確でない。

二の補数表現は、今日に至るまで使用されている符号の表現方法。
最上位ビットを符号ビットとし、符号ビットが1の場合は負の数、0の場合は正の数とする。
例えば、5と-5を二進数で表現する場合、以下のようになる。
5 = 0000 0101
-5 = 1111 1011

負の数を求めたい場合すべてのbitを反転し、その結果に1加算した結果が負の数となる。

a + ~a ≡ -1
a + ~a + 1 = 0
~a + 1 = -a

例えば、16bit幅の数値を32bit幅のレジスタに読みだす場合、空いている上位16ビットを符号ビットに合わせる必要がある。これを符号拡張と呼ぶ。

1111 1111 1111 1101 (16bit)
↓ load
1111 1111 1111 1111 1111 1111 1111 1101 (32bit)

レジスタのビット幅から計算結果の数値がはみ出てしまうことをオーバーフローと呼ぶ。

junyaU 7日前に更新

2.5

優れた設計では適度な妥協が必要。

MIPSではレジスタの数は32である。レジスタは増やし得かと思っていたが、増やせば増やすほど機械語の長さが長くなってしまう。レジスタ数が32なら5bit(2^5)でレジスタを表現することができるが、一つでも増やそうとするならば、少なくとも6bitは必要になってしまい命令長が長くなる。
命令長が長くなるといろいろなデメリットが生じる。

プロセッサとメモリ間のデータ転送量の増加
プログラムサイズの増加
命令キャッシュの効率低下

...etc

命令長を小さくしたいという要求と十分なレジスタの数が必要という要求の結果、大抵の命令セットの汎用レジスタ数は16~32となっている。
確かに、x64も汎用レジスタ16個ぐらいだったな。

今日のコンピューターの基本原理

命令は数値で表現できる。
プログラムはメモリに格納でき、数値と同様に読み書きができる。

これらのおかげでプログラム内蔵方式が成り立っている。

既存の命令セットとの互換性があれば、コンピュータは既存のソフトウェアを継承することができる。
このような「バイナリ互換性」を求めることは、少数のISA（x64,arm,risc-vとか）を軸にして業界が連携することにつながる。

junyaU 6日前に更新

2.6

論理演算の例をいくつか書いておく

シフト

ビットを右か左にずらすこと。
例えば 0000 1001 (9)を左に4bitシフトすると、1001 0000 (144)となる。
これは元の数（9）に2^4を掛けたものになる。10進数で100を左に2ずらしたら10000（100 * 10^2）となるのと同じ。
1 << n (1 * 2^n) はにのべきを表すのに高速で便利なのでめっちゃよく使う（バディシステムでもお世話になった）。

論理積

AND。比較ビット同士がお互いに1の部分が1になり、それ以外は0になる。
強制的に特定ビットを0にしたいときによく使う。この操作をビットマスクといったりする。

論理和

OR。比較ビットの片方が1であれば1になり、どちらも0の場合のみ0。
こっちは強制的に特定ビットを1にするときによく使う。

論理否定

NOT。ビット反転

2.7

MIPSの条件分岐命令
beq (branch if equal)
bne (branch if not equal)
無条件分岐命令
j (jump)

コンパイラは元のコードにないラベル付けや分岐を行うことが良くある。これによって高級言語でプログラムを書く際にそれらを明示的に書かなくてよくなる。

基本ブロック

プログラムの制御が入ると、出る際に分岐しない一連の命令シーケンスのこと。
以下のような特徴を持つ

単一入口 : 一つの開始地点（ラベルとか）しか持たない。
単一出口 : 出口も一つだけでそこからのみブロックから出られる。
分岐しない : ブロック中で分岐が行われることはない。

コンパイラはプログラムを基本ブロックに分解するところから始まる。

効率的な配列のインデックス境界違反のチェック方法

配列の長さがn,インデックスがiとするときのインデックス境界違反は、
i >= nまたは、i < 0の場合である。これらのチェックをする効率的な方法は下記である。
sltu $result, i, n
beq $result, $zero, error
これは、単純にiのほうがnより大きい場合でも0になるし、符号付き表記でマイナスの値は符号なしにするとかなり大きな値（nより大きい）になるので、どちらのパターンも符号なし整数のless thanで一気に検出できる。

junyaU 5日前に更新

2.8

関数（手続き）をスパイと表現していたのが面白かった。
スパイは秘密裏に計画を立て情報を取るという任務を遂行するように、関数も呼び出し元から依頼されたら秘密裏に情報を取得し呼び出し元に返す。その際の証拠は一切残さない（つまり関数の実行が終われば関数呼び出し前のレジスタの状態が復元されている）。
関数はソフトウェアにおける抽象化の最たる例。

スピルアウト → レジスタの値をメモリに退避すること。

caller-saved（呼び出し元保存）レジスタとcallee-saved（呼び出し先保存）レジスタは呼び出し先と呼び出し元どちらがレジスタの値を保存しておくかを取り決めたルールである。
これを守ることで、無駄なレジスタをスピルアウトする必要なく効率よくスピルアウトすることができる。

スタックフレーム内の変数を参照したいとき、スタックポインタを用いて変数のアドレスを割り出すのは難しい。なぜならプッシュやポップを行うことでスタックポインタが変動するので、その点を考慮しなければならないからである。一方ベースポインタはそのスタックフレーム内では一定なので、この用途に適しているといえる。

junyaU 5日前に更新

2.9

ASCIIの正称知らんかった → American Standard Code for Information Interchange

当たり前だけど、データのタイプがデータ自体に保存されているわけではなく、プログラムの解釈によってデータタイプは変わりうる。
01100010 01100001 01010000 00000000
上記のデータは以下のように多様に解釈することができる。
符号なし整数と扱う場合 : 1650544640
符号あり整数と扱う場合 : +1650544640
ASCII文字列と扱う場合 : "baP"
また、機械語命令として解釈もできるだろう。
このように処理プログラムによって、同じデータでもデータの解釈が変わるのがプログラム内蔵方式コンピュータの特徴である。

junyaU 4日前に更新

2.10

16ビットを超える即値の扱い方（MIPS）

MIPSのI形式の命令では即値に充てられたbitは16なので、そのままでは2^16を超える数値を表現することができない。表現したい場合はlui(load upper immediate)命令を使う必要がある。
これは指定したレジスタの上位16ビットに即値を書き込む命令である。
lui命令を使って上位ビットを埋め、OR命令で下位ビットも埋めれば32ビットの即値が表現できるようになる。

PC相対アドレッシング

MIPSの条件分岐命令ではアドレスの表現に2^16しか充てることができない。これだとプログラムの大きさを2^16以上にすることができなくなってしまう。しかしPCの値 + 相対的な距離を指定することで、2^32まで距離を広げることができる。これをPC相対アドレッシングと呼ぶ。
条件分岐命令はループやif文に使われる命令だがこれらの分岐先は距離が近いことが一般的なので、PCからの相対距離にすれば短い距離を指定するだけで済む。
PCの値から±128K（2^16 * 4を半分にしたもの）までのアドレスにジャンプすることができる。

MIPSでのアドレッシングモード

即値アドレッシング : 命令中に指定した即値をオペランドとする
レジスタアドレッシング : レジスタをオペランドとする
ベース相対アドレッシング : 定数と指定したレジスタの和をオペランドとする
PC相対アドレッシング : PCの値と命令中の即値の和をオペランドにする
疑似直接アドレッシング : 命令中の26ビットとPCの上位ビットを連結したものをオペランドにする

junyaU 4日前に更新

2.11

マルチコアプロセッサにおいて、データ競合を起こさないように同期を実現することは特に重要である。
あるタイミングにおいて単一のプロセッサのみが該当のデータへのアクセスできるような相互排除の機構がハードウェアには必要である。
これを実現するためのシンプルな方法として不可分な交換がある。あるメモリロケーションにデータの読み書きをする際にそのメモリロケーションのロックの取得を試みる。0が返されたらロックを取得できて1が返されたらほかのプロセッサが使用中というような仕組み。
交換の操作は分断することができないので、不可分な操作を実現できるようになる。

MIPSではll命令とsc命令で不可分な操作を実現できる。

ll(load linked)命令

指定されたメモリアドレスから値を読み取り、レジスタに格納する。格納した後はほかのプロセッサがこのメモリアドレスに対して変更を行ったかどうかを監視する。

sc(store conditional)命令

他のプロセッサが、ll命令の実行後から該当のメモリアドレスに書き込みを行っていなければメモリへの書き込みは成功し、1を返す。逆に書き込みが行われていた場合は失敗し0を返す。

addi $t0, $zero, 1
ll $t1, 0($s0) ; メモリから値を読みだして$t1に格納後監視する。
sc $t0, 0($s0) ; メモリに$t0の値の書き込みを試みる。
beq $t0, $zero, FAIL ; scが0を返した場合、ほかのプロセッサが介入したと判断し書き込みは失敗する。

junyaU 3日前に更新

2.12

高級言語が実行可能なファイルになるまで
高水準言語プログラム（例えばC）はコンパイラによってコンパイルされて、アセンブリ言語に変換される。その後アセンブリはアセンブラによってオブジェクトファイルに変換される。リンカによって複数のオブジェクトファイルをつなぎ合わせて最終的な実行ファイルが作成される。
今ではコンパイラから直接機械語を作れたりできるが、上図が基本的なステップとなる。

コンパイラ

C言語をアセンブリ言語に変換する。アセンブリ言語は機械語に一対一で紐づくものであり、機械語(バイナリ)を記号で記して人間にわかりやすくしたもの。
昔は、メモリサイズの問題や性能の問題からOSは直接アセンブリ言語で書かれていた。しかし、DRAMチップの集積度の向上によってメモリの制限はないに等しいものとなり、コンパイラの性能向上によってアセンブリ言語の直書きに引けを取らなくなったので、OSも高水準言語(C/C++,今ではRustもかな)で書かれるようになった。

アセンブラ

アセンブリ言語をオブジェクトファイル（機械語）に変換する。
アセンブリ言語では疑似命令というものが用意されている。ISAには用意されていない命令だが、アセンブラがそれを解釈して該当のISAの命令に置き換えてくれる。
例えばMIPSの疑似命令にはmoveというものがある。

move $t0, $t1

これはMIPSで用意された命令ではないので、アセンブラによって以下の命令に変換される。

add $t0, $t1, $zero

疑似命令を使えば、簡潔にアセンブリ言語が書けるようになる。

また、アセンブリ中のラベルをメモリアドレスに変換するのもアセンブラの役目である。
シンボルテーブルというラベルとメモリアドレスの対応表を記録する（tetris本で作った記憶あるな懐かしい）。

アセンブラが作るオブジェクトファイルは最終的に以下のような構造になる

ヘッダ : オブジェクトファイルのメタ情報
テキストセグメント : 機械語コードを格納
データセグメント : プログラムの実行に使うデータを格納
リロケーション情報 : プログラムをメモリにロードしたときに変更しなければならない値（アドレス）を示す
シンボルテーブル : 未定義のラベル（ほかのオブジェクトファイルで定義されている物）を保持する
デバッグ情報 : デバッグ情報

リンカ

複数のオブジェクトファイルをリンクして一つの実行ファイルを作り出す。
リンカがないとプログラムの1行を修正しただけですべてをコンパイル、アセンブルしなおす必要がありめっちゃ無駄なコストがかかってしまう。リンカがあれば修正した部分のオブジェクトファイルのみ対応すればよくなる。
リンカは具体的に以下を行う。

オブジェクトファイルをすべてメモリに置く
外部参照しているデータや命令のアドレスを判明させる
内部及び外部参照をすべて解決させる
これらのステップを踏んでできるものが実行ファイル。

あとはローダがプログラムをメモリに配置すればプログラムの実行が可能になる。

junyaU 3日前に更新

Javaは実行速度よりもいかなる環境でも安全に実行できることに主眼が置かれている。どうやってそれを実現しているのかを見てみる。

Javaはコンパイルによってバイトコードという中間コードに変換される。
Javaバイトコード用のインタープリタがバイトコードを解釈し実行を行うことでJavaは動作する。このJavaバイトコード用のインタープリタのことをJVMと呼ぶ。つまり、マシンにJVMさえ入っていればJavaは動作が可能になる。（数億台の機器にJVMが入ってるらしい）
インタプリタ方式には移植性が高いというメリットがあるものの、実行が遅いという明確な欠点がある。

インタープリタ方式 : バイトコードを特定操作（システムコールなどを用いた）に変換 → それに対応した機械語を実行
コンパイル方式 : 機械語 → 実行

インタープリタ方式では、バイトコードをJVM上で特定操作に変換しその操作を実行する。「JVM上で特定操作に変換」という中間解釈のコストが発生するので遅くなる。
そこで、JIT(Just In Time)コンパイラを使うことでこの欠点を軽減することができる。JITコンパイラは、プログラムのホットスポットと呼ばれる頻繁に実行されるコードを検出し、その部分をリアルタイムで機械語にコンパイルする。そうするとその部分の中間解釈のコストはなくなるので、インタープリタの柔軟性と事前コンパイルの効率を兼ね備えた実行が可能になる。

junyaU 3日前

スマホからMIPSアセンブリ書けるんだ...w

junyaU 2日前に更新

2.13

色々アセンブリを書く章だったのでリポジトリ作って書いた。

ソートプログラムの検証で、最適化していないCのコードのほうがインタープリタ方式のJavaより約8倍速いという結果は面白いなと思った。

最適化されていないコードのほうがCPIが良いという結果が出ていたが、それは単純に命令数が多いからであって、実行速度が速いわけではない。このことから実行時間の尺度が唯一信頼できるものであって、CPIなどの一つの観測値を鵜呑みにした性能検証がいかに危険であるかを読み取ることができる。

junyaU 2日前に更新

2.14

配列を用いたループとポインタを用いたループをアセンブリ視点から眺めた。
以下は、要素をクリアするコードとそれに対応したアセンブリを手動で書いたもの。

clear.c

void clear_1(int array[], int size) {
  int i;
  for (i = 0; i < size; ++i) {
    array[i] = 0;
  }
}

void clear_2(int *array, int size) {
  int *p;
  for (p = &array[0]; p < &array[size]; ++p) {
    *p = 0;
  }
}

clear.asm

clear_1:
    move $t0, $zero
loop_1:
    sll $t1, $t0, 2
    add $t1, $t1, $a0
    sw $zero, 0($t1)
    addi $t0, $t0, 1
    slt $t2, $t0, $a1
    bne $t1, $zero, loop_1

clear_2:
    move $t0, $a0
    sll $t1, $a1, 2
    add $t1, $t1, $a0
loop_2:
    sw $zero, 0($t0)
    addi $t0, $t0, 4
    slt $t2, $t0, $t1
    bne $t2, $zero, loop_2

アセンブリを見ると、ポインタを用いたコードのほうがループ中で2命令分削減できていることがわかる。
配列の方は、iが加算されるたびに乗算と加算を行って次の要素のアドレスを計算しなおす必要がある。
一方でポインタの方は、ポインタに直接オフセットを加算しているだけなので、配列の方で行われていた乗算と加算(sllとadd)が不要になり命令数を削減することができる。
今では配列のループを使用してもコンパイラが最適化して命令数を減らしてくるので、こんなことを知らなくてもよいんだろうけど知っておいて損はないなと思った。

junyaU 2日前に更新

2.16

ARMv7のISAについて軽く触れた。ほぼ触ったことなかったので初めて知ったことをメモ。

ARMはAdvanced RISC Machineの略。特に組み込み機器でよく使われるISA。
ARMの命令形式では先頭（オペコードの前）に4ビットのフィールドが用意されている。このフィールドによってその命令を無効にする（nop命令として扱う）ことができるらしい。これによって無条件分岐命令を条件分岐として機能させることができる。一行だけjumpしなきゃいけない時にすごく便利そう。
ARMにおけるフラグレジスタ的なやつではNegative,Zero,Carry,Overflowのフラグビットが用意されている（x86と同じだ）。x86と同じくcmp命令(減算結果をフラグレジスタに反映する命令)もある。

junyaU 12時間前に更新

2.17

ARMv8について。
命令セットでの潜在的な問題の中で克服しにくいものにアドレス空間が小さいことにあった。そこでx86は64bitモードを設計した。ARMでも64bit版となるv8が設計されたがv7とv8間には大きな刷新があり、「両者の類似点は名前だけ」と言われるほど違う命令セットになっているらしい。
以下のような変更があった。

レジスタが32個に増えた。
条件付き実行フィールド(先頭4bit)の廃止。
PCに直接書き込みができないようにした。

etc...

v8はよりMIPSに近いISAになっているので、MIPSを学んでおけばARMv8を理解することが容易になる。

junyaU 11時間前に更新

2.18

RISC-Vについて。
MIPSと非常に似ているISAである。ARMやx86,MIPSなどはベンダーによって管理されているのに対して、RISC-Vはオープンソースのアーキテクチャとなっている。

MIPSとRISC-Vの共通点

命令幅は32bit。
汎用レジスタの数は32個。
load,store命令を介さないとメモリにアクセスすることはできない。

etc...

等しい等しくない以外の条件分岐命令は少し異なる。RISC-Vの命令では、２つのレジスタを比較して分岐を行う。一方MIPSでは、比較した結果をレジスタに格納する命令と、その結果がゼロかどうかで分岐を行う命令を組み合わせて条件分岐命令が実現される。これはMIPSが最低限のことしか行わないという思想のもとで設計されているからである。

junyaU 6時間前に更新

2.19

x86について。
MIPSやARMは機能を最小限にしてにしてアーキテクチャを単純に保つ設計がみられた。
一方、x86アーキテクチャは長年にわたり多くの機能拡張が行われてきた。後方互換性を維持するために多くの古い機能が残されており、また次々と機能拡張を行った結果アーキテクチャは複雑になり。パッチワークのようになってる印象を受けた。やっぱりMIPSとかARMと比べると命令の種類が多すぎるんだよな...

Intelは1978年に8086プロセッサを発表した。これがx86シリーズの始まりとなる。このアーキテクチャは32ビットまで拡張(i386)され、長い間業界の標準となっていた。
2000年代初頭、AMDはx86アーキテクチャを64ビットまで拡張することを発表した。この技術は2003年に「AMD64」として市場に導入され、後にIntelもこれに追随して「Intel 64」として同様の技術を採用した。
IntelがAMDの技術を継承したことは、技術の発展と市場の要求に応じた戦略的な判断であり、両社間の競争だけでなく、業界全体の技術標準を形成する上で重要な役割を果たしたと考えられる。
このおかげで、x86-64とかx64とかAMD64とか名前が紛らわしくなったんだな😇

逆にIntelやAMDのような大手プロセッサ製造企業の共同の産物であるが故、複雑になってしまった部分もあるんじゃないかなと個人的に思った。お互いの思想が混じり合うわけだし、互換性を維持するために色々妥協しなきゃいけない部分も出てきそう。

このように複雑なので、x86はARMやMIPSと比べると製造コストが高くなっている。スマホとかだとx86は競争力を発揮できていない。（コストのせいなのかな）
色々ネガなことを書いちゃったけどx86アーキテクチャは好き。