コンピュータの構成と設計

概要

本

かかった時間

  • 26.3 時間

    • 2 章の途中で読むのやめた（学習内容の重複が多かったため）

読む前の状態

読書メモ

1章: コンピュータの抽象化とテクノロジ

  • コンピュータの利用形態は下記の 3 通り

    • パーソナル・コンピュータ: 個人が使用するように設計されたコンピュータ

      • 単一のユーザーに低いコストで高い性能を提供することに重点が置かれたもの

    • サーバー: 複数ユーザーを対象として大規模なプログラムを実行するために使用するコンピュータ

      • かつての大型コンピュータが新たに形を変えたものであり、通常はネットワークを通じてのみアクセスされる。大量の仕事をこなすことに特化している

      • またスーパーコンピュータ（性能とコストが最高レベルのコンピュータ）もサーバーとして構成される

    • 組み込みコンピュータ: 単一の専用アプリケーションまたはソフトウェア群を実行するために、他の装置の内部に組み込まれて使用されるコンピュータ

      • 自動車に搭載されるマイクロプロセッサ、テレビ内のコンピュータなど。組み込み用途における要求は、性能は最小限でよいがコストや消費電力は厳しく抑えたいという、独特の組み合わせであることが多い

  • 本書で学べること

    • 優秀なプログラマは絶えず自分が作成するプログラムの性能に注意を払う

    • 1960 年代および 1970 年代においては、コンピュータの性能に対する主な制約要因はメモリの容量

    • 現在ではメモリ容量はほとんど制約にならなくなったが、代わりにプロセッサの並列性や記憶の階層性などについて理解する必要がでてきた

    • そのうえ、PMD（Personal Mobile Device）またはクラウドの上で実行されるプログラムのエネルギー効率について、配慮する必要がある

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

    • Moore の法則の設計

    • 設計を単純化するための、抽象化

    • 一般的な場合を高速化する

    • 並列処理による性能向上

    • パイプライン処理による性能向上

    • 予測による性能向上

    • 記憶階層

    • 冗長性による信頼性向上

  • オペレーティング・システムで重要なのは以下の機能

    • 基本的な入出力処理を行う

    • 外部記憶およびメモリを割り当てる

    • コンピュータを同時に使用する複数のアプリケーションの間で、コンピュータ資源の共有を図る

  • コンピュータの古典的な 5 つの構成要素は、入力・出力・記憶・データパス・制御である。データパスと制御をあわせてプロセッサと呼ぶこともある

  • コンピュータをネットワークに接続すれば、下記の利点が得られる

    • 通信: コンピュータ間で情報を高速に交換できる

    • 資源の共有: 個々のコンピュータがそれぞれ独自の入出力を備えるのではなく、ネットワークを通じて複数のコンピュータで入力を共有できる

    • リモート・アクセス: 遠隔地のコンピュータ同士をつなぐことによって、ユーザーは自分のコンピュータのそばにいなくてもよくなる

  • チップの製造はシリコンから始まり、シリコン中の小さな領域に下記の 3 つの性質のいずれかを持たせることができる

    • 電気をよく通す

    • 電気を絶縁する

    • 特定の条件に応じて電気を通したり、絶縁したりする（スイッチの役割をする）

  • PMD では応答時間が重視され、サーバーではスループットが重視される。性能を比較する上で、まず性能を定義する必要がある

  • 性能に関する用語

    • 応答時間: タスクの完了に要した合計時間であり、ディスク・アクセス、メモリ・アクセス、入出力動作、オペレーティング・システムのオーバーヘッドなどのすべてを含む

    • CPU 時間: 該当プログラムのために CPU が費やした時間であり、入出力待ち時間や他のプログラムを実行させるための時間を含まない

      • CPU 時間はさらに 2 つに分けられる

        • ユーザー CPU 時間: プログラム中で費やされた CPU 時間

        • システム CPU 時間: プログラムに代わって、オペレーティング・システムがタスクを遂行するために費やした CPU 時間

    • この本では、他に負荷のかかっていないシステム上での経過時間を指してシステム性能という用語を使用し、ユーザー CPU 時間を指して CPU 性能という用語を使用する

  • CPU 性能とその要因

    • 「あるプログラムの CPU 実行時間」=「そのプログラムの CPU クロック・サイクル数」*「クロック・サイクル時間」

    • 「CPU クロック・サイクル数」=「プログラムの実行命令数」*「命令当たりの平均クロック・サイクル数」

    • 「命令当たりの平均クロック・サイクル数」は CPI（clock cycle per instruction）とも言う

    • 「あるプログラムの CPU 実行時間」=「実行命令数」*「CPI」*「クロック・サイクル時間」とも書ける

    • コンピュータの性能を表す完全かつ信頼性のある唯一の尺度は時間であることを、常に念頭に置く

  • CPI は 1 より小さくなる場合もある（1 サイクルに複数命令を実行する場合）

  • 電力の壁

    • エネルギーは「容量性負荷 * 電圧の 2 乗」に比例する

    • 消費電力は「1/2 * 容量性負荷 * 電圧の 2 乗 * 切り替え周波数」に比例する

  • コンピュータの性能測定を目的としたプログラムをベンチマークと呼ぶ

  • 誤信と落とし穴

    • 落とし穴

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

        • 改善の影響を受けないものもある（参考: Amdahl の法則）

      • 性能の尺度に性能方程式の一部を使用すること

    • 誤信

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

        • 負荷が 10％でもピーク時の 33％の電力を使用していたりするので、利用率が低いときの電力効率は重要

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

2章: 命令:コンピュータの言葉

  • ハードウェアの設計原則 3 つ

    • 単純性は規則性につながる

    • 小さければ小さいほど高速になる

    • 優れた設計には適度な妥協が必要である

  • 各レジスタの役割

    • フレームポインタ: 手続きフレームの先頭の語を示す

      • 手続きフレーム: スタックのうち、手続きによって退避されたレジスタおよびローカル変数が収められている領域

名前

レジスタ番号

用途

呼び出し時に退避？

$zero

0

定数値ゼロ

該当せず

$v0-$v1

2-3

結果および式の評価のための値

no

$a0-$a3

4-7

引数

no

$t0-$t7

8-15

一時

no

$s0-$s7

16-23

退避（変数に対応）

yes

$t8-$t9

24-25

予備の一時

no

$gp

28

グローバルポインタ

yes

$sp

29

スタックポインタ

yes

$fp

30

フレームポインタ

yes

$ra

31

戻りアドレス

yes

  • MIPS では語のアドレスは 4 の倍数でなければならない。これを整列化制約と呼ぶ

  • コンパイラは頻繁に使用する変数をレジスタに保持しておき、それ以外の変数をメモリに置こうとする。使用頻度の低い変数をメモリ上に置くことをスピルアウトという

  • オペランドが定数となるケースは頻繁に発生するので、定数を算術演算命令に含めている（addi など）

  • MIPS のフィールド

    • R 形式（レジスタ用）

      • op: 命令の基本操作、従来から命令操作コードと呼ばれている。6 ビット

      • rs: 第 1 のソース・オペランドのレジスタ。5 ビット

      • rt: 第 2 のソース・オペランドのレジスタ。5 ビット

      • rd: デスティネーション・オペランドのレジスタ。結果を収める先。5 ビット

      • shamt: シフト量。5 ビット

      • funct: 機能。命令操作フィールドのバリエーションを表す。機能コードと呼ばれることもある。6 ビット

    • I 形式（即値およびデータ転送命令用）の場合は op / rs / rt と 16 ビットの constant または address

    • J 形式

  • プログラム内蔵方式は以下の 2 つの基本原理から生まれた

    • 命令は数値として表現される

    • プログラムをメモリ中に格納して、データと同様に読み書きできる

  • ヒープ領域（データ構造のヒープの意味とは異なる）

    • コンピュータプログラムが実行時に使用するメモリ領域の 1 つで、動的に確保や解放を繰り返せるもの

  • ASCII コードでは 1 文字を 8 ビットで表す。Unicode では通常 16 ビットで 1 文字を表す

  • MIPS のアドレシングモード

    • 即値アドレシング: 命令中に指定した定数をオペランドとする

    • レジスタ・アドレシング: オペランドにレジスタをとる

    • ベース相対アドレシング: 命令中に指定した定数とレジスタの和によって、オペランドが記憶されているメモリの位置を示す

    • PC 相対アドレシング: PC と命令中に指定した定数との和によってアドレスを示す。16 ビットのアドレスを 2 ビット左にシフトして、PC と加算する

    • 疑似直接アドレシング: 命令中の 26 ビットと PC の上位ビットを連結したものがジャンプアドレスとなる。26 ビットのアドレスを 2 ビット左にシフトして、PC の上位 4 ビットと連結する

  • 不可分: メモリロケーションの読み出しと書き込みの間に、何も割り込むことができないことを意味する

  • リンカ（リンクエディタともいう）

    • 個別にアセンブルされた機械語プログラムを組み合わせ、未解決のすべてのラベル参照先を解明して、実行ファイルを作成するシステムプログラム

  • ローダ

    • オブジェクトプログラムを主記憶に読み込んで、実行できるようにするシステムプログラム

    • DLL（Dynamically Linked Library）: 実行中にプログラムにリンクされるライブラリルーチン

解答メモ

1章

1.1

  • パーソナル・コンピュータ: 個人が使用するように設計されたコンピュータ。通常はグラフィック・ディスプレイ、キーボード、マウスを備えている

  • サーバー: 複数ユーザーを対象として大規模なプログラムを実行するために使用するコンピュータ。ユーザーは同時にかつネットワークを通じてのみアクセスすることが多い

  • スーパーコンピュータ: 性能とコストが最高レベルのコンピュータ）もサーバーとして構成されており、通常は数億ドルもする

  • 組み込みコンピュータ: 単一の専用アプリケーションまたはソフトウェア群を実行するために、他の装置の内部に組み込まれて使用されるコンピュータ

1.2

  • Moore の法則に則って設計する: f

  • 設計を単純化するために抽象化する: h

  • 一般的な場合を高速化する: d

  • 並列処理を通じた性能の向上: b

  • パイプライン処理を通じた性能の向上: a

  • 予測を通じた性能の向上: c

  • 記憶階層: e

  • 冗長性を通じた信頼性: g

1.3

  • 高水準言語がコンパイラによって、アセンブリ言語に変換される。アセンブリ言語がアセンブラによって、機械語に変換される

1.4

a

  • 3.9MB

    • 1280 * 1024 * 8 * 3 / 8 = 3932160

b

  • 0.31 秒

    • 3932160 * 8 / 100000000 = 0.3145728

1.5

a

  • MIPS を計算する

    • P1: 3.0 * 10^9 / 1.5 / 10^6 = 2.0 * 10^3

    • P2: 2.5 * 10^9 / 1.0 / 10^6 = 2.5 * 10^3

    • P3: 4.0 * 10^9 / 2.2 / 10^6 = 1.8 * 10^3

    • よって、P2 の性能が最高

b

  • サイクル数は「クロック周波数」*「実行時間」

    • P1 のサイクル数: 30 * 10^9

    • P2 のサイクル数: 25 * 10^9

    • P3 のサイクル数: 40 * 10^9

  • 10 秒なので命令数は MIPS の 10 倍

    • P1 の命令数: 20 * 10^9

    • P2 の命令数: 25 * 10^9

    • P3 の命令数: 18 * 10^9

c

  • クロック周波数を 1.2 / 0.7 = 1.714 倍にしなければならない

    • P1: 5.1 * 10^9

    • P2: 4.3 * 10^9

    • P3: 6.9 * 10^9

1.6

a

  • P1: 1 * 0.1 + 2 * 0.2 + 3 * 0.5 + 3 * 0.2 = 2.6

  • P2: 2

b

  • 命令数は 1.0 * 10^6 なので P1 は 2.6 * 10^6、P2 は 2.0 * 10^6

  • 速さについて

    • P1: 2.6 * 10^6 / (2.5 * 10^9) = 1.04 * 10^-3

    • P2: 2.0 * 10^6 / (3 * 10^9) = 0.67 * 10^-3

    • なので P2 のほうが速い

1.7

a

  • P1

    • 1.1 = 10^9 * 10^-9 * CPI なので CPI は 1.1

  • P2

    • 1.5 = 1.2 * 10^9 * 10^-9 * CPI なので CPI は 1.25

b

  • A のクロック周波数を a、B のクロック周波数を b とする

  • 10^9 * 1.1 / a = 1.2 * 1.25 * 10^9 / b なので b / a = 1.2 * 1.25 / 1.1 = 1.36

  • A は B より 1.36 倍遅い

c

  • 新しいコンパイラを使用した場合の実行時間は 6.0 * 10^8 * 1.1 * 10^-9 = 0.66

  • 1.1 / 0.66 = 1.67 より A を使用した場合に比べて、1.67 倍速い

  • 1.5 / 0.66 = 2.27 より B を使用した場合に比べて、2.27 倍速い

1.8

1.8.1

  • 消費電力 = 1/2 * 容量性負荷 * 電圧の 2 乗 * 切り替え周波数

  • Pentinum 4 Prescott

    • 90 = 1/2 * 容量性負荷 * 1.25^2 * 3.6 * 10^9

    • よって容量性負荷は 90 * 2 / (1.25^2 * 3.6 * 10^9) = 3.2 * 10^-8 F

  • Core i5 Ivy Bridge

    • 40 = 1/2 * 容量性負荷 * 0.9^2 * 3.4 * 10^9

    • よって容量性負荷は 40 * 2 / (0.9^2 * 3.4 * 10^9) = 2.9 * 10^-8 F

1.8.2

  • Pentinum 4 Prescott

    • 合計消費電力に対するパーセンテージ: 10 / 100 = 10%

    • 動的電力に対する割合: 1:9

  • Core i5 Ivy Bridge

    • 合計消費電力に対するパーセンテージ: 30 / 70 = 43%

    • 動的電力に対する割合: 3:4

1.8.3

  • 消費電力 = 電圧 * 電流で、電流を同じに保つので、電圧を 90％にする

1.9

1.9.1

  • クロックサイクル数

    • コアの数が 1 の時: 2.56 * 10^9 + 12 * 1.28 * 10^9 + 5 * 2.56 * 10^8 = 19.2 * 10^9

    • コアの数が n の時（n > 1）: 2.56 * 10^9 * (0.7 * n) + 12 * 1.28 * 10^9 * (0.7 * n) + 5 * 2.56 * 10^8 = (25.6 / n + 1.28) * 10^9

  • コアの数: 1

    • 実行時間は 19.2 * 10^9 / (2 * 10^9) = 9.6 秒

  • コアの数: 2

    • 実行時間は (25.6 / 2 + 1.28) * 10^9 / (2 * 10^9) = 7.04 秒

    • 相対速度向上率は 9.6 / 7.04 = 1.36 倍

  • コアの数: 4

    • 実行時間は (25.6 / 4 + 1.28) * 10^9 / (2 * 10^9) = 3.84 秒

    • 相対速度向上率は 9.6 / 3.84 = 2.5 倍

  • コアの数: 8

    • 実行時間は (25.6 / 8 + 1.28) * 10^9 / (2 * 10^9) = 2.24 秒

    • 相対速度向上率は 9.6 / 2.24 = 4.29 倍

1.9.2

  • クロックサイクル数

    • コアの数が 1 の時: 5.12 * 10^9 + 12 * 1.28 * 10^9 + 5 * 2.56 * 10^8 = 21.76 * 10^9

    • コアの数が n の時（n > 1）: 5.12 * 10^9 * (0.7 * n) + 12 * 1.28 * 10^9 * (0.7 * n) + 5 * 2.56 * 10^8 = (29.257 / n + 1.28) * 10^9

  • コアの数: 1

    • 実行時間は 21.76 * 10^9 / (2 * 10^9) = 10.88 秒

  • コアの数: 2

    • 実行時間は (29.257 / 2 + 1.28) * 10^9 / (2 * 10^9) = 7.95 秒

  • コアの数: 4

    • 実行時間は (29.257 / 4 + 1.28) * 10^9 / (2 * 10^9) = 4.30 秒

  • コアの数: 8

    • 実行時間は (29.257 / 8 + 1.28) * 10^9 / (2 * 10^9) = 2.47 秒

1.9.3

  • ロードストア命令の CPI を k とすると (2.56 * 10^9 + k * 1.28 * 10^9 + 5 * 2.56 * 10^8) / (2 * 10^9) = 3.84 を満たす

  • k = (3.84 * (2 * 10^9) - 2.816 * 10^9) / (1.28 * 10^9) = 3.8 より CPI を 3.8 まで減らせばよい

1.10

1.10.1

  • 1 つ目

    • ダイの面積は 7.5^2 * 3.14 / 84 = 2.103

    • 歩留まりは 1 / (1 + (0.020 * 2.103 / 2))^2 = 0.96

  • 2 つ目

    • ダイの面積は 10^2 * 3.14 / 100 = 3.14

    • 歩留まりは 1 / (1 + (0.031 * 3.14 / 2))^2 = 0.91

1.10.2

  • ダイ当たりのコスト = ウエーハ当たりのコスト / (ウエーハ当たりのダイの数 * 歩留まり)

  • 1 つ目

    • 12 / (84 * 0.96) = 0.15

  • 2 つ目

    • 15 / (100 * 0.91) = 0.16

1.10.3

  • 1 つ目

    • ダイの面積は 7.5^2 * 3.14 / (84 * 1.1) = 1.91

    • 歩留まりは 1 / (1 + (0.020 * 1.15 * 1.91 / 2))^2 = 0.96

  • 2 つ目

    • ダイの面積は 10^2 * 3.14 / (100 * 1.1) = 2.85

    • 歩留まりは 1 / (1 + (0.031 * 1.15 * 2.85 / 2))^2 = 0.91

1.10.4

  • 1 つ目

    • 改善前

      • 欠陥数を a とする

      • 0.92 = 1 / (1 + (a * 2 / 2))^2 なので a = 1 / 0.92^0.5 - 1 = 0.043

    • 改善後

      • 欠陥数を b とする

      • 0.95 = 1 / (1 + (b * 2 / 2))^2 なので b = 1 / 0.95^0.5 - 1 = 0.026

1.11

1.11.1

  • 750 = 2.389 * 10^12 * CPI * 0.333 * 10^-9 なので CPI = 750 / (2.389 * 10^12 * 0.333 * 10^-9) = 0.94

1.11.2

  • 9650 / 750 = 12.87

1.11.3

  • 10％増加する

1.11.4

  • 1.1 * 1.05 = 1.155 なので、15.5％増加する

1.11.5

  • 新しい SPECratio は 9650 / (750 * 1.155) = 11.14

  • (11.14 - 12.87) / 12.87 = -0.134 なので、13.4％悪化する

1.11.6

  • 700 = 2.389 * 10^12 * 0.85 * CPI * 0.25 * 10^-9 なので、CPI = 700 / (2.389 * 10^12 * 0.85 * 0.25 * 10^-9) = 1.38

1.11.7

  • CPI とクロック周波数は反比例する

1.11.8

  • (750 - 700) / 750 = 0.067 より 6.7％削減した

1.11.9

  • 4GHz の時の実行時間は 960 * 0.9 = 864ns

  • 864 * 10^-9 = 命令数 * 1.61 * 0.25 * 10^-9 なので、命令数 = 864 * 10^-9 / (1.61 * 0.25 * 10^-9) = 2147

1.11.10

  • 1.1 倍にする

1.11.11

  • クロック周波数を a とすると

  • 960 * 10^-9 * 0.8 = 2147 * 1.61 * 0.85 / a なので a = 2147 * 1.61 * 0.85 / (960 * 10^-9 * 0.8) = 3.8 GHz

1.12

1.12.1

  • P1 の実行時間は 5.0 * 10^9 * 0.9 / (4 * 10^9) = 1.125

  • P2 の実行時間は 1.0 * 10^9 * 0.75 / (3 * 10^9) = 0.25

  • なので、クロック周波数は P1 のほうが高いが、性能は P2 のほうが高い

1.12.2

  • 「P1 と P2 の CPI が変わらないとして」の意味は、P1 の CPI が 0.9 のまま、P2 の CPI が 0.75 のままという意味と解釈

  • 実行時間 = 1.0 * 10^9 * 0.9 / (4 * 10^9) = 0.225

  • なので、0.225 = 命令数 * 0.75 / (3 * 10^9) より、命令数 = 0.225 / (0.75 / (3 * 10^9)) = 9.0 * 10^8

1.12.3

  • MIPS は、クロック周波数 / CPI / 10^6

  • P1 の MIPS は 4 * 10^9 / 0.9 / 10^6 = 4.44 * 10^3

  • P2 の MIPS は 3 * 10^9 / 0.75 / 10^6 = 4.00 * 10^3

  • なので、MIPS は P1 のほうが高いが、性能は P2 のほうが高い

1.12.4

  • P1 の MFLOPS は 4.44 * 10^3 * 0.4 = 1.78 * 10^3

  • P2 の MFLOPS は 4.00 * 10^3 * 0.4 = 1.60 * 10^3

1.13

1.13.1

  • 70 * 0.2 = 14 秒速くなる

  • 14 / 250 = 5.6％短縮される

1.13.2

  • 合計時間の 20％は 250 * 0.2 = 50 秒

  • 50 / 70 = 71.4％短縮される

1.13.3

  • 分岐命令だけで 50 秒短縮することはできないので、不可能

1.14

1.14.1

  • 実行時間 = (50 * 10^6 * 1 + 110 * 10^6 * 1 + 80 * 10^6 * 4 + 16 * 10^6 * 2) / (2 * 10^9) = 0.256

  • 2 倍にするには 0.128 秒縮める必要があるが、浮動小数点命令では 0.025 秒しか縮められないので不可能

1.14.2

  • ロードストア命令はもともと 0.16 秒

  • (0.16 - 0.128) / 0.16 = 20％ なので、80％短縮しなければならない

1.14.3

  • 短縮される時間は (50 * 10^6 * 0.4 * 1 + 110 * 10^6 * 0.4 * 1 + 80 * 10^6 * 0.3 * 4 + 16 * 10^6 * 0.3 * 2) / (2 * 10^9) = 0.0848

  • 0.0848 / 0.256 = 33.1％ 短縮される

1.15

  • 2 台の場合

    • 100 / 2 + 4 = 54 秒

    • 速度向上比は 100 / 54 = 1.85

    • 理想との比較は 1.85 / 2 = 0.93

  • 4 台の場合

    • 100 / 4 + 4 = 29 秒

    • 速度向上比は 100 / 29 = 3.45

    • 理想との比較は 3.45 / 4 = 0.86

  • 8 台の場合

    • 100 / 8 + 4 = 16.5 秒

    • 速度向上比は 100 / 16.5 = 6.06

    • 理想との比較は 6.06 / 8 = 0.76

  • 16 台の場合;

    • 100 / 16 + 4 = 10.25 秒

    • 速度向上比は 100 / 10.25 = 9.76

    • 理想との比較は 9.76 / 16 = 0.61

  • 32 台の場合

    • 100 / 32 + 4 = 7.125 秒

    • 速度向上比は 100 / 7.125 = 14.04

    • 理想との比較は 14.04 / 32 = 0.44

  • 64 台の場合

    • 100 / 64 + 4 = 5.5625 秒

    • 速度向上比は 100 / 5.5625 = 17.98

    • 理想との比較は 17.98 / 64 = 0.28

  • 128 台の場合;

    • 100 / 128 + 4 = 4.78125 秒

    • 速度向上比は 100 / 4.78125 = 20.92

    • 理想との比較は 20.92 / 128 = 0.16

2章

2.1

addi t0, h, -5
add f, g, t0

2.2

  • f = i + (g + h)

2.3

sub $t0, $s3, $s4
sll $t0, $t0, 2
add $t0, $t0, $s6
lw $t1, 0($t0)
sw $t1, 32($s7)

2.4

  • t2 には A[f] のアドレスから 4 つ進んだ値が入るので B[g] = A[f] + A[f+1]

2.5

  • 6 行目の addi 命令が冗長なので、以下のようになる

sll $t0, $s0, 2 // $t0 = f * 4
add $t0, $s6, $t0 // $t0 = &A[f]
sll $t1, $s1, 2 // $t1 = g * 4
add $t1, $s7, $t1 // $t1 = &B[g]
lw  $s0, 0($t0) // f = A[f]
lw  $t0, 4($t0) // $t0 = A[f + 1]
add $t0, $t0, $s0 // $t0 = A[f] + A[f + 1]
sw  $t0, 0($t1) // B[g] = $t0

2.6

2.6.1

  • 38 のアドレスは 28 の誤植だと思われる。28 の前提で解く

int Array[5];
int t0, t1;

Array[0] = 2;
Array[1] = 4;
Array[2] = 3;
Array[3] = 6;
Array[4] = 1;

t0 = Array[0];
t1 = Array[1];

Array[0] = Array[4];
Array[1] = t0;
Array[4] = Array[3];
Array[3] = t1;

2.6.2

lw $t0, 0($s6) // t0 = Array[0]
lw $t1, 4($s6) // t1 = Array[1]
lw $t2, 16($s6) // t2 = Array[4]
sw $t2, 0($s6) // Array[0] = t2
sw $t0, 4($s6) // Array[1] = t0
lw $t0, 12($s6) // t0 = Array[3]
sw $t0, 16($s6) // Array[4] = t0
sw $t1, 12($s6) // Array[3] = t1

2.7

  • リトルエンディアン

アドレス

データ

バイナリデータ

0

0x12

0001 0011

1

0xef

1110 1111

2

0xcd

1100 1101

3

0xab

1010 1011

  • ビッグエンディアン

アドレス

データ

バイナリデータ

0

0xab

1010 1011

1

0xcd

1100 1101

2

0xef

1110 1111

3

0x12

0001 0011

2.8

  • 10 * 16^7 + 11 * 16^6 + 12 * 16^5 + 13 * 16^4 + 14 * 16^3 + 15 * 16^2 + 1 * 16 + 2 = 2882400018

2.9

sll $t0, $s3, 2
add $t0, $t0, $s6
lw $t0, 0($t0)
sll $t1, $s4, 2
add $t1, $t1, $s7
lw $t1, 0($t1)
add $t0, $t0, $t1
sw $t0, 32($s4)

2.10

A[1] = &A[0]
f = 2 * &A[0];

2.11

  • 2.10 の各命令に対して記載する

  • addi $t0, $s6, 4

    • op: 8

    • rs: 22（s6）

    • rt: 8（t0）

    • address / immediate: 4

  • add $t1, $s6, $0

    • op: 0

    • rs: 22（s6）

    • rt: 0

    • rd: 9（t1）

    • shamt: 0

    • funct: 32

  • sw $t1, 0($t0)

    • op: 43

    • rs: 8（t0）

    • rt: 9（t1）

    • address / immediate: 0

  • lw $t0, 0($t0)

    • op: 35

    • rs: 8（t0）

    • rt: 8（t0）

    • address / immediate: 0

  • add $s0, $t1, $t0

    • op: 0

    • rs: 9（t1）

    • rt: 8（t0）

    • rd: 16（s0）

    • shamt: 0

    • funct: 32

2.12

2.12.1

  • オーバーフローが発生する。その値を切り捨てると 0x50000000

2.12.2

  • オーバーフローが発生する

2.12.3

  • 符号付き整数として解く

  • 最初の 4 桁は 1011 なので 0xB0000000

2.12.4

  • オーバーフローは発生しない

2.12.5

  • 0x50000000 + 0x80000000 なので 0xD0000000

2.12.6

  • オーバーフローが発生する

2.13

  • 32 ビットレジスタで考える

  • 2^31 = 2147483648 なので 32 ビットレジスタで表現できるのは -2147483648 〜 2147483647

2.13.1

  • 2147483647 - 128 = 2147483519 なので、2147483520 <= s0 <= 2147483647

2.13.2

  • -2147483519 の場合、ぎりぎりセーフ。-2147483648 <= s0 <= -2147483520

2.13.3

  • -2147483648 + 128 = -2147483520 なので、-2147483648 <= s0 <= -2147483521

2.14

  • 最初 6 桁が 000000 なので R 形式、最後 6 桁が 100000 なので add 命令

  • rs が 10000、rt が 10000、rd が 10000、shamt が 00000

  • add $s0, $s0, $s0

2.15

  • sw は 101011、$t1 が 01001、$t2 が 01010

  • 1010 1101 0100 1001 0000 0000 0010 0000

2.16

  • R 形式

  • sub $v1, $v1, $v0

  • 0000 0000 0110 0010 0001 1000 0010 0010

2.17

  • I 形式

  • lw $v0, 4($at)

    • アドレス 1 は $at を指す

  • 1000 1100 0010 0010 0000 0000 0000 0100

2.18

2.18.1

  • レジスタの指定に 7 ビット必要になる（rs / rt / rd）

  • また、命令の数も 4 倍になるので、8 ビット必要になる

  • 残り 3 ビットを shamt と funct で分けることになるので、shamt 2 ビットかつ funct 1 ビット、または shamt 1 ビットかつ funct 2 ビット

2.18.2

  • R 形式と同様に、op の指定に 8 ビット、レジスタの指定に 7 ビット必要になる（rs / rt）

  • なので、address / immediate の指定が 16 ビットから 10 ビットになる

2.18.3

  • 小さくする方向

    • R 形式

      • 命令・レジスタの数の数が増えるので、既存の複数命令を 1 つにまとめることができる

    • I 形式

      • 命令・レジスタの数が増えるので、既存の複数命令を 1 つにまとめることができる

  • 大きくする方向

    • R 形式

      • シフト量と機能コードへの割り当てが減ったため、命令が冗長化する

    • I 形式

      • アドレスの指定範囲が狭くなるので、命令が冗長化する

2.19

  • 0xAAAAAAAA は 1010 1010 1010 1010 1010 1010 1010 1010

  • 0x12345678 は 0001 0010 0011 0100 0101 0110 0111 1000

2.19.1

  • シフト後は 0x00000000 となるので、答えは 0x12345678

2.19.2

  • シフト後は 0xAAAAAAA0 となる

  • -1 は 1111 1111 1111 1111 1111 1111 1111 1111 なので答えは 0xAAAAAAA0

2.19.3

  • シフト後は 0001 0101 0101 0101 0101 0101 0101 0101

  • 0xFFFF は 0000 0000 0000 0000 1111 1111 1111 1111 なので andi 後は 0000 0000 0000 0000 0101 0101 0101 0101 となり、答えは 0x00005555

2.20

  • シフト演算を使う

srl $t0, $t0, 11
sll $t0, $t0, 26
srl $t1, $t1, 6
sll $t1, $t1, 6
or $t1, $t1, $t0

2.21

  • nor を使う

  • nor $t1, $t2, $zero

2.22

  • lw $t2, 0($s1)

  • sll $t1, $t2, 4

2.23

  • ELSE にジャンプした後、2 を足して答えは 3

2.24

  • ジャンプ命令の場合、命令中の 26 ビットを 2 ビット左にシフトして、PC と連結する

  • 0x20000000 から 0x400000000 に移動する場合、0x200000000 を指定する必要があるが、これは 28 ビットでは表現できない

  • よって不可能

2.25

2.25.1

  • I 形式

2.25.2

  • t2 が R[rs] と対応しているとする

LOOP: slt $t0, $0, $t2
      beq $t0, $0, EXIT
      addi $t2, $t2, -1
      j LOOP
EXIT:

2.26

2.26.1

  • 10 回ループが周り、それぞれ 2 ずつ足されるので 20

2.26.2

while (i > 0) {
  i = i - 1;
  B = B + 2;
}

2.26.3

  • 最後の LOOP での命令実行数が 2（DONE に飛ぶ時）、そこまでに 5N 回実行しているので、5N + 2

2.27

        add $t0, $zero, $zero // i = 0
LOOP1:  slt $t2, $t0, $s0
        beq $t2, $zero, EXIT
        add $t1, $zero, $zero // j = 0
LOOP2:  slt $t2, $t1, $s1
        beq $t2, $zero, INCR1
        add $t2, $t0, $t1 // t2 = i + j
        sll $t3, $t1, 4 // t3 = 4 * j * 4（最後の 4 倍は word に変換する分）
        add $t3, $t3, $s2
        sw $t2, 0($t3) // D[4*j] = i + j
        addi $t1, $t1, 1
        j LOOP2
INCR1:  addi $t0, $t0, 1
        j LOOP1
EXIT:

2.28

  • 2.27 では i と j を初期化しているが、その必要はなくなる

  • b が 1 なので、i が 1 増えるごとに 13 + 2 = 15 回の処理が必要

    • 最初に 1 回、最後に 2 回必要

  • 153 回

2.29

  • 0($s0) で MemArray[0] を取得できる

for (int i = 0; i < 100; i++) {
  result = result + MemArray[i];
}

2.30

  • i（t1）ではなく、s0 を使って比較する

      addi $s3, $0, 400
LOOP: $s1, 0($s0)
      add $s2, $s2, $s1
      addi $s0, $s0, 4
      bne $s0, $s3, LOOP

2.31

  • 使用するレジスタ

    • 結果レジスタ: $v0

    • 引数レジスタ: $a0

    • 一時レジスタ: $t0

    • 退避レジスタ: $s0

    • 戻りアドレスレジスタ: $ra

    • スタックポインタ: $sp

fib:  addi $sp, $sp, -12
      sw $ra, 8($sp)
      sw $a0, 4($sp)
      sw $s0, 0($sp)
      bne $a0, $0, ELIF
      addi $v0, $zero, $zero
      j EXIT
ELIF: addi $t0, $zero, 1
      bne $a0, $t0, ELSE
      addi $v0, $zero, $zero
      j EXIT
ELSE: addi $a0, $a0, -1
      jal fib // fib(n-1)
      add $s0, $v0, $zero // s0 = fib(n-1)
      addi $a0, $a0, -1
      jal fib // fib(n-2)
      add $v0, $v0, $s0 // v0 = fib(n-1) + fib(n-2)
EXIT: lw $s0, 0($sp)
      lw $a0, 4($sp)
      lw $ra, 8($sp)
      addi $sp, $sp, 12
      jr $ra

  • 22 行なので、命令の数は 22

PreviousPendingNext30日でできる! OS自作入門

Last updated