Computer

Computer

格言

「最近、かって自分が作成した素因数分解プログラムと三目並べプログラムをもう一度調べてみたのだが、残念ながらそれらにコメントやドキュメントと言えるものは一切ないのだ」
—Donald E. Knuth

「われわらが観察しているのは自然そのものではなく、我々の探求に対して明らかにされた限りの自然である」
—Werner Heisenberg

「真のバカでも使えるものを設計しようとして人々がよくやるミスは、真のバカのバカさ加減を過小評価することだ」
—Douglas Adams

「実際のところ、データを無視するというのが、精神の安定を保つ上で最も安易に最もよく行われているやり方だ」
—William James

Compared to what we ought to be, we are only half awake. We are making use of only a small part of our mental and physical resources.
—William James

「技術的な理由から、これらの弾頭は上下逆に格納する必要がある。つまり、下面が上、上面が下だ。上下を迷わないように各弾頭の下面に直に『上』と記すことになっている」
—英国海軍規則

「小さなシステムを拡大して作った大きなシステムは、元の小さなシステムと同じようには振る舞わない」
—John Gall

「自然の法則は神の数学的思考にほかならない」
—Euclid

「ドキュメントはセックスに似ている。よいときはすごくよいし、よくないときもないよりはましだ」
—Dick Brandon

「医者は失敗を墓に埋めることができるが、建築家は蔦を植えるようにアドバイスすることしかできない」
—Frank Lloyd Wright

「道具をくれ。道具さえあれば、見事にやってのけてみせよう」
—Winston Churchill

「技術を成功へと導くためには、ＰＲよりも現実を優先させねばならない。自然をあざむくことはできないからだ」
—Richard Phillips Feynman

「ソースコードだけ見ていればいいのなら、人生はずっと楽になるのだが」
—Dave Olson

「世界は、物事を実行しようとする人々と、名声を受けようとする人々とに分かれる。できれば、前者に属するよう努力するとよい。そのほうが競争はずっと少ない」
—Dwight Morrow

「答えは存在しない。クロスリファレンスだけが存在する」
—ワイナーの図書館の法則(「マーフィーの法則」)

「注意：このソフトウエアは世界を救うものではない」
—Jim Crafton

「やり方？やり方なんてあるわけないだろう。何かを生み出そうとしてるんだぞ」
—Thomas Edison

「具体的な方法が存在するとは、チューリング機械にできることだと見なそう」
－－－チャーチ

「あるプログラムが有限時間内に停止するかどうかを判定する具体的方法は存在しない」
－－－アラン・チューリング

「プログラムのテストは、バグの存在を示すことはできるが、不在を証明することはできない」
－－－エドガー・ダイクストラ

「プログラムを書いたことのないシステムエンジニアが威張っているような会社は早晩亡びる。」
－－－竹内郁雄

「コードを削ることで機能を追加しなさい」
－－－ジョン・ベントリー

「デザイナーが自分は完璧に達成したんだと分かるのは、付け加えるものが何もない時ではなく、取り去るべきものが何もない時である」
－－－サン＝テグジュペリ

「簡単なものから複雑なものになるのではなく、複雑なものの後に簡単になる。」
－－－アラン・パリス

「過度にパッケージを細かく分割するのはJavaコードにおいてよくみられるアンチパターンの一つです。」
－－－エリオット・ラスティ・ハロルド

「未熟な段階での最適化は、プログラミングにおける諸悪の根源」
－－－Donald Knuth

「こういった規則は役に立ちます。～中略～　ただ、それが経験則にすぎないことを忘れてしまうと、かえって仇になることがあります。忘れてしまうと、『行っているすべてのこと』は正しいけれど、それにもかかわらず大事な点が欠落してしまうような、そんな設計に終わってしまう可能性があります。」
－－－Michael Feathers

「プログラムが持つ構造すべてのもののうち、最もバグになる傾向が高いのは、入れ子になった条件文である。」
－－－？

「次世代プロセッサを購入すればプログラムはもっと速くなる、という考えに私たちは慣れ親しんで育ってきましたが、その時代はもう過ぎ去ったのです。次世代チップはより多くのＣＰＵを持ちますが、その個々のＣＰＵの速度は前年のモデルより速くはありません。ですから、自分のプログラムをもっと高速に実行したければ、並列プログラムの書き方を学ばなければなりません。」
－－－Herb Sutter and James Larus

「インターネットを使えば通信線でつながったハッカー達は世界じゅうどこからでも仕事ができる、などと言われているけど、そんな吹聴をしている奴等はカリフォルニアのごく狭い場所にあつまっている」
－－－Rishab Ghosh

「この１０年で、生物学は発達して情報科学になりました」
－－－Lincoln Stein

「当時はFortranやAlgolが加速度的に流行しつつある時代で、この新しい考え方に基づくシステムはその流行の陰にかくれてはいたが、それでも消滅することなしに確実に世界中に流布していった。～中略～狂信的ともいえる愛好者を持つことができたからであるといわれている。この一風かわったシステムといわれていたものが本書で述べるLispである.」
－－－中西正和、Lisp入門 1981年刊 近代科学社

「あなたがた各人が、コプロセッサがいくつ売れるか予想して数字を書き、それ以上１個売れるごとに１ドルを私にくれるなら、私は給料をもらわなくても結構です。」
－－－ジョン・パーマー、インテル８０８７の責任者。コプロセッサに市場は無いとみるマーケティング部門に対し。

「それは低俗さが勝利しなかったひとつの例である」
－－－ウイリアム・カーン、IEEE754の開発について

「膨大な数値データを眺めて、幅広く応用できる新しい解決策を引き出すことに大きな満足を覚える」
－－－ロバート・ピクスビー、CPLEXの開発者

「Woz was the first person I met who knew more about electronics than I did」
－－－Steven Jobs, １４歳で初めてスティーブ・ヴォズニャックと会ったときの回想

「There’s no reason we can’t build machines that think.」
－－－John, McCarthy

「シンプレックス法の途方もない威力は、たえず私を驚かせている」
－－－ダンツィグ、シンプレックス法発明者

「浮動小数点区間演算は厳密である」
－－－ファーガソン

「高次元の問題は、いわゆる”次元ののろい”のために、膨大な計算量を必要とし、いかに高速の計算機を使っても、解決に長時間を要するものが多い」
－－－伏見正則

「pull oneself up by one’s (own) bootstrap」
－－－ブートストラップ（他人の助けを借りずに自力で解決する）

「簡潔なのはよいが記号性の高さが災いし、覚えてつかいこなせるようになるまでが大変だ。また、ソースコードからその意味するところを読み解くのも至難の技である～（中略）～そもそもＡＰＬは『個人の思考を助ける』ことが目的の処理系であるため、ソースコードの保存と再利用という観点は重視されていないのだ。」
－－－長谷川裕行、ＡＰＬについて

「男は最初の問題を片付ける前に、次の問題に興味を走らせてしまう」
－－－グレース・マレー・ホッパー女史、COBOL開発の中心人物、海軍少将、79歳で退役。米海軍史上最年長の将軍だった。1992/1/1没。享年85歳。

「難問の解決は数値解析の発達だけでは達成できるものではない」
－－－伊藤剛

「多数のアプリケーションの性能を向上させるような技術でなければ、その技術の有効性は疑わしいものとする」
－－－マイク・ジョンソン

「あらかじめ決められた処理だけを行い、ユーザが機能を追加することが基本的にない計算機システムが組み込みシステムであるといえます」
－－－冨山宏之

「ノイマン・ボトルネックにも長所はある。それは、デバッグがしやすいということである。」
－－－梅尾博司

「計算機科学者と「通常の」科学者・技術者を分ける文化的障壁の一つは、３０%とか５０％とかの速度低下が心配の種になるかどうかに関する相違である。」
－－－ニューメリカルレシピ

「実際的な科学者は明日の問題を昨日のコンピュータで解こうとしているのに、計算機科学者はしばしばこの逆のように思われる」
－－－ニューメリカルレシピ

---

コンピュータサイエンスの体系

※デニング図

☆コンピュータサイエンスのパラダイムと専門分野

理論パラダイム
数学を源とした理論体系
抽象化パラダイム
実験科学的方法を源にしたモデル体系
設計パラダイム
エンジニアリング体系

※専門分野

◎チューリングマシン

※Turing Complete チューリング完全
⇒チューリングマシンでできることと同等のことができること

◎セルラ・オートマトン
ノイマン

並列計算モデル、自己増殖、自己複製
⇒同期型、超細粒度、並列計算モデル
⇒発想された当時は、ハード量が多くなり過ぎ現実になるとは思われなかった

⇒セルラ・アーキテクチャの並列計算機の実現

◆Kung、シストリック・コンセプト、シストリック・コンピュータ

◆DAP610(Active Memory Technology)
4K個のビット・プロセッサをメッシュ結合
超並列画像処理マシン

◆MasPar MP-1
MasPar社
16K個の4ビットプロセッサをメッシュとクロスバー結合で接続

◎超並列/超分散処理

◎コネクショニズム

◎パラレル・プロセッサ

◎ニューロ/ファジイ・コンピュータ

※パーセプトロン
⇒Minsky & Papertによりダメ印となった
⇒ニューロとして復活

※ファジイ理論
KalmanとZadehが論争

◎オプティカル・コンピュータ

◎バイオコンピュータ

☆アルゴリズムとデータ構造

◎グラフ理論
◎計算量理論
◎検証理論

◎フローチャート
◎構造化チャート

☆プログラミング言語

 

◎形式言語理論

※形式言語の規定
生成文法による
文を受理する装置による（オートマトン）

◆チョムスキー階層
Chomsky hierarchy
生成文法を言語学に適用した

句構造文法の書き換え則に３段階の制約を与え、階層的に規定する
０型 句構造
１型 文脈依存 自然言語
２型 文脈自由 プログラミング言語
３型 正規
⇒制約のない０型から制約の強い３型まで
⇒０から３に包含関係

◆言語の定義と種類

文字集合の定義
語の定義
任意の記号の並びの集合
任意の記号の並びの「文法規約を満たす」部分集合を言語と規定する

◆句構造文法
句構造文法のグラマーＧ

G=(N,T,P,S)
N non-terminal symbol 非終端記号の集合、Gによる文を表す
T terminal symbol 終端記号の集合、Nの部分集合、個々の記号。置換不可
P production rule 書き換え規則。N,T間の書き換え規則。
⇒句構造文法ではPの制約はない。
S start symbol 開始記号。最初の非終端記号

◆文脈依存文法
書き換え規則が前後の文脈に依存する

◆文脈自由文法
書き換え規則は前後の文脈に依存しない

＿◇BNF
Backus-Naur Form

①<> <>内の記号列はメタ変数
②::= 左辺は右辺のように定義される
③| または
④その他の記号 記号そのもの
⑤要素の並び 各記号の順に並べられた列

※メタ言語。ある言語の文法を説明するための言語
※対象言語。説明の対象となる言語そのもの

※拡張BNF
{}もしくは[]を使って繰り返しを表現する

◎オートマトン理論
automaton

※アルゴリズムをモデリング化し、定式化したもの
※入出力テープと有限状態制御装置から構成される
→状態遷移にもとづき問題解決手順をモデル化する

◆有限オートマトン
FNA(Finite Automaton)

※正規言語を受理できる
※入力テープと有限状態制御装置からなる。出力はない。

FNA=(Q,Σ,δ,q0,F)
Q 有限個の状態の集合
Σ 入力される有限個の記号
δ 状態遷移関数
q0 初期値状態
F 最終状態

Q={q0, q1, q2, q3}
Σ={s1,s2}
δ{q0,s1}=q2, …
F={q3}

※状態遷移図がかける

◆プッシュダウンオートマトン

※文脈自由言語を受理できる
※有限オートマトンに、プッシュダウンストア（スタック）を加えたもの

◆線形有限オートマトン

※文脈依存言語を受理できる

◆チューリングマシン

※句構造言語を受理できる
※入力だけでなく出力もある
※あらかじめ内部状態が記憶されている
⇒任意のTMとそのデータの入力により、どんなTMの動作も模倣できるチューリング機会を万能機械(UM:Universal Machine)と呼ぶ。

◎各種プログラミング言語

※プログラミング・パラダイム

◆手続き型

◆関数型

◆論理型

◆オブジェクト指向型

 

◎トランスレータとインタプリタ

◆コンパイラ

＿◇解析
①字句解析
字句に分解し記号表に格納
②構文解析
文の構成と文法の検査
算術式
ポーランド記法（前置記法）
逆ポーランド記法（後置記法）

＿◇最適化

＿◇コード生成

☆理論

◎符号理論

※情報を表現する対象そのものを情報担体と呼ぶ
⇒情報担体を記号列に変換することを符号化と呼ぶ

◆２元符号化

＿◇補数
負の数の表現法のひとつ。減算を加算にして扱える。

※ｒ桁のｎ進数の数Ａの補数は
ｎ＾ｒ－Ａ

※２進数の場合
０と１を反転（１の補数）し、１を足すことで２の補数が得られる。

＿◇符号化

①標本化 sampling
②量子化 quantization
③符号化 coding

◆情報源符号化

＿◇情報量
ある事象が起こったときに得られる情報量
⇒事象の起こる確率が小さいほど大きい

＿◇生起確率と情報量

ある事象Ｊが起こる確率Ｐ⇒Ｐ（Ｊ）
実際にＪが起こったときに得られる情報量をＩ（Ｊ）

Ｉ（Ｊ）＝－ｌｏｇ２｛Ｐ（Ｊ）｝

※このときのＩ（Ｊ）の単位をビットと呼ぶ

＿◇平均情報量

※無記憶情報源
生起する事象同士に関連がなく独立している情報源

※平均情報量（エントロピー）
無記憶情報源において、事象Ｊ１～Ｊｎの生起確率からもとまる平均情報量Ｅ

E = P(J1)xI(J1) + … + P(Jn)xI(Jn)

※最小および最大平均情報量
無記憶２元情報源においては
最小⇒一方がおきて、他方がおきない。生起する事象が特定できる場合
Emin=1*(-log2(1))+0*I(J2)=0
最大⇒均等に事象がおき、どの事象が起こるかわからない場合
Emax=…=1

※自然界ではエントロピーが最大になる傾向がある

＿◇マルコフ情報源
記憶情報源のひとつ

ｎ重マルコフ情報源とは、時間的にｎ回前までさかのぼった事象が継続的に関係しながら生起するような情報源

※ｎ＝１の場合を単純マルコフ情報源と呼ぶ
⇒状態遷移図で表すことができる

※事象Ｊ２が生じた後に事象Ｊ１が生じた場合の確立
Ｐ（Ｊ１｜Ｊ２）

＿◇エルゴート情報源

ある情報源からの生起事象を長時間にわたって観察すると、ある値に帰着するような情報源

◆通信路符号化

＿◇通信速度と通信路容量

平均情報量を、通信路を伝達する情報に対して適用する
⇒これに時間の概念を導入することで通信速度と容量を扱うことができる

※事象数N,事象J1,事象J2が起こる。その情報を通信路で送るのに必要となる時間をt1,t2とする。
J1の情報量 -N*P(J1)*log(P(J1))
J1すべてを送るために必要となる時間 t1*N*P(J1)
全情報量E
E = -N*P(J1)*log(P(J1)) -N*P(J2)*log(P(J2))
全伝達T
T = t1*N*P(J1) + t2*N*P(J2)
通信速度 TR
TR = E/T

※通信速度が最大になった値を通信路容量Cとする
⇒２つの情報を扱う場合には、それぞれの情報量と伝達時間の比率が等しいとき
TRの式の両辺をP(J1)で微分し、０とおいて極値を求める
dP(J2)/dP(J1)=-1を代入、整理する
-log(P(J1))/t1 = log(P(J2))/t2 = -C

＿◇誤り訂正符号化

※冗長検査 余分な符号を付加する

パリティ検査（奇偶検査）

CRC Cyclic Redundancy Code

◆暗号
cryptosystem

平文 plaintext
暗号化 encrypt encryption
暗号文 ciphertext
暗号解読 cryptanalyze, cryptanalysis

＿◇DES
Data Encryption Standard

＿◇FEAL
Fast Data Encipherment Algorithm

---

◎命題論理

◆記号論理学
（数理論理学）

古典論理学
命題論理
述語論理

非古典論理
多値論理
直観論理
様相論理

＿◇命題論理
命題の持つ真理値のみに着目する

※命題
真か偽か規定できる叙述
⇒判定の論拠は論理(logic)でなく理論(theory)

※真理値
truth value

※命題変数
命題を組み合わせるときに、命題となる叙述を変数として扱う

※基本命題　ひとつだけの命題変数で構成されるもの

※論理記号　命題変数同士を組み合わせるために用いる記号
論理和 ＋、∨
論理積 ・、∧
論理否定 ￢
含意 ⊃
命題１が真ならば命題２も真のとき、真
命題１が偽ならば命題２にかかわらず真

※複合命題　２つ以上の命題変数を論理記号によって組み合わせたもの

＿◇論理代数
ブール代数

※命題の論理演算を代数的に処理する

＿◇述語論理
命題があらわす事象の関係や性質に着目する

変数の具体的な値を与えることで真偽性が定まる述語に対する推論形式

※述語論理の構文
述語と限定作用素

※述語
「ｘはｙである」
個体変数ｘにある値を与えることによりｙであるの真偽がきまる
⇒y(x)と表す

※限定作用素
①全称作用素
ある個体変数(x)に対してすべてのxにおいてという意味を付加する
∀

例）すべての自然数は整数である
(∀a)(N(a)→I(a))

②特殊作用素
ある個体変数(x)に対して「。。。となるようなxが存在する」
∃

例）a<bを満たすべてのaとbについて、a>t*bとなるtが存在する
(∀a)(∀b)(∃t)(L(a,b)→G(a,M(t,b)))

※導出原理

 

１階述語論理
２階述語論理
高階述語論理

＿◇Prolog

※ホーン節
論理を条件と結論の関係として記述する際に、結論部が一つだけで構成される

---

◎ノイマン・アーキテクチャ

John von Neumann

◆ノイマン・ボトルネック
Neumann bottleneck

ノイマン型計算機は、CPU、メモリ、両者をつなぐバスからなる。
メモリは多量にあり、それらはビンに詰め込まれている
バスはビンの狭い口を経由してビンの外側にあるCPUとつながっている。

◆ノイマン・サイクル

CPUはプログラムカウンタとよばれる逐次的に動作するカウンタをもち、一つの命令を次の４つの動作に分解して処理する

①命令フェーズ
instruction phase
フェッチとデコード

②オペランド・フェーズ
operand phase
オペランドの番地を計算し、メモリから取ってくる

③実行フェーズ
execution phase
命令を実行する

④オペランド・フェーズ
operand phase
結果をメモリに格納する

---

☆数値、記号計算

◎数値解析
◎線形計算

 

---

☆オペレーティングシステム

◎システム理論
◎オブジェクトモデル

 

---

☆ソフトウエア工学

◎プログラミングパラダイム

---

☆データベースおよび情報検索システム

◎集合論

集合：１つ以上の同じ属性を持つ要素の集まり

◆集合と要素の関係

集合Sに要素sが含まれる
S∋s

集合Sに要素sが含まれない
S∋/s

要素がまったくない集合＝空集合S*
S*=φもしくは{}

ある集合のすべての要素を含んだもの＝全体集合U
（普遍集合）

集合X以外の集合Uの要素で構成されている集合＝Xの補集合 X^C

集合Xのすべての要素が集合Yに含まれている場合
⇒集合Xは集合Yの部分集合
X⊆Y

集合Xのすべての要素が集合Yに含まれていて、集合Xに含まれない要素が少なくとも一つ存在する場合
⇒集合Xは集合Yの真部分集合
X⊂Y

◆集合演算
集合演算：集合をもとにした演算

①積演算
X1∩X2 = {x | x∈X1 ∧ x∈X2}

②和演算
X1∪X2 = {x | x∈X1 ∨ x∈X2}

③差演算
X1－X2 = {x | x∈X1 ∧ x∈/X2}
⇒X2⊂X1において、X1-X2をX1におけるX2の補集合と呼ぶ

◆集合における直積演算

直積：各集合がもつ要素同士のすべての組み合わせを並べたもの
⇒要素同士の組み合わせを関係の組という
⇒組の個数を次数という
⇒次数ｎ個のものをｎ項リレーションとよぶ
⇒個々の要素は関係の属性と呼ぶ
⇒２次元的にあらわしたものをリレーション・テーブル（関係表）
横が組、縦が属性

※リレーション・テーブルをデータベースのスキーマモデルとして採用したもの
⇒リレーショナル・データベース

◆関係演算
リレーショナルデータベース特有の演算

①射影演算
該当する属性のみを取り出す。（テーブルの縦方向切り出し）

②選択演算
属性がある条件を満たす組だけを取り出す。（横方向）

③結合演算
関係表同士について、共通する属性において値が一致する組同士を取り出して結合し、新たな組を生成する操作

④商演算
関係表同士について、共通する属性の値を持つものだけを抽出する

※上記の関係演算と、集合演算をあわせたものを関係代数と呼ぶ
演算相互の等価性により、
和
差
直積
射影
選択
の５演算で構成できる

◎関係代数論

◎データモデル
◎データベーススキーマ
◎ＲＤＢ

◎ＳＱＬ

◆SQLと関係代数

---

☆人口知能、ロボティクス

◎述語論理
◎知識表現
◎知識モデル
◎Prolog
◎エキスパートシステム

---

☆マンマシン間インタフェース

◎認知科学
◎パターン認識

---

☆言語プロセッサ

◎概要

◆処理ステップ

＿◇言語の定義、文法の記述

※字句解析も構文解析も文法が定義されていなければ行えない。

※BNF
Backus-Normal Form
Backus-Naur Form

ALGOL60の報告書で初めて用いられた文法表現法
⇒通常、この拡張記法を用いる

定義例）
<変数名>::=<英字>
<英字>::=A|B|C|D|E|F|G|
H|I|J|K|L|M|N|
O|P|Q|R|S|T|U|
V|W|X|Y|Z

※| は「または」

再帰的定義例）
<変数名文字列>::=<変数名>|
<変数名文字列><英字>

※{} 繰り返し
例）
{<英数字>}99
⇒英数字０～９９個

※[] 省略可能
例）
[STEP <式>]
⇒中かっこの後の数字が1と同じ

＿◇字句解析
lexical analysis
lexical scan

①プログラム文字列がどこで区切られるのか知る
②固定長のシンボルに直して並べる
⇒変数名ならば変数名表のインデックスに変換する

＿◇構文解析
syntax analysis

※算術式の構文解析
⇒つぎにどの演算を行うか優先順位の決定のために先読みが必要
２項演算
左から評価していって発見した演算子α1
左側の被演算子はその時点で定義済みβ1
右側の被演算子β２
単純変数
定数
算術式
⇒β２に続く演算子α２の優先順位が高ければ、
α１の実行は保留
β３を見つける作業に入る必要がある
⇒内部表現形式への変換の必要性

①逆ポーランド記法
⇒非常に簡単なアルゴリズムで行える。
⇒演算子の優先順位表を用いる
β１α１β２α２β３の形でα１を先にするか、α２か判断するスイッチ表
優先順位には（と）も含める

逆ポーランド記法への変換
スタック初期化
S） ソースを走査 無ければ⇒ 終了
ｘは変数か？ 変数ならｘを出力しS)へ
ｘは（か？ （をスタックに積んでS)へ
A) ｘは演算子か？
演算子のときはスタックトップのｙを見る）
ｙは（か？ ｘをスタックに積んでS)へ
ｘとｙではｘ優先 ｘをスタックに積んでS)へ
ｙ優先 ｙをスタックから降ろして出力、A)へ
演算子でないときは）
B)
ｘは）か？
ｙが演算子） ｙを出力、Bへ
ｙは（である ｘの）とｙの（を相殺し、S)へ
ｙが（でない エラー、S)へ

②木構造表現
⇒より効率のよいオブエジェクトを作りやすい

---

コーディング規約

◎Indian Hill C Style and Coding Standard

◎indent
①/*- */
生計プログラムindentに対して、そのコメントの内容の書式を変えないように指示する働きがある。

◎コメント
①FALLTHROUGH
lintに対して、意図的なcase文のスルーであると知らる
②NOTREACHED
プログラムの制御フローが決してその点に到達しないことを示す（警告を避けるため）
③リビジョン管理システムのタグ
$識別子$
%文字%
④コメント用の慣用語
XXX ただしくないが、ほぼ機能するコード
FIXME 間違っていて修正の必要のあるコード
TODO 将来機能拡張を図る場所

 

☆GNUコーディング標準

◎書式
中カッコを別個の行に書く

if (ia-ia_maddr !_ MADDRUNK)
{
sc->pPacketPagePhys = ia->ia_maddr;
}

☆BSDスタイルガイド(apache,Perl準用）

◎記述順序
◆インクルード
①カーネルヘッダファイル
②/usrヘッダファイル
③ユーザーヘッダファイル

◎インデント
８文字幅のタブ

継続行はスペース４個でインデント
制御ブロック要素はスペース８個でインデント

◎書式
ステートメントと同じ行で中カッコを開き、そのインデントレベルで中カッコを閉じる

if ((cp = strchr(*argv,’:’) != NULL) {
*cp++ = ‘\0’;
a_gid(cp);
}

☆Javaコーディング規約

◎記述順序

①クラス変数
②インスタンス変数
③コンストラクタ
④メソッド

※変数とメソッドは、以下の順で定義する
private
protected
public

◎インデント
４個のスペース
もしくは８文字幅のタブ

◎コメント
①/** */
javadocツールに対してソースコードドキュメントを生成するように指示する。javadocキーワードは@文字で始まる

☆ハンガリアン記法

☆一般的なファイル名

README
プロジェクトの概要
MANIFEST
簡単な説明の付いたプロジェクトファイルのリスト
INSTALL
インストール手順
LICENSEまたはCopying
ライセンス情報
TODO
将来の拡張についての「欲しい物リスト」
NEWS
ユーザの目に見える変更に関するドキュメント
ChangeLogまたはChanges
コード変更サマリ
configure
プラットフォーム設定スクリプト
Makefile
ビルド指定
Makefile.SH
上記のものを生成するシェルスクリプト
config.h
プラットフォーム設定定義
config.h.SH
上記のものを生成するシェルスクリプト
version.hまたはpatchlevel.h
プロジェクトリリースバージョン

☆Seiwaldのプリティコードの７か条

1. 1. 「本のよう」であること
   2. 似たものは似て見えるようにすること
   3. 字下げを克服すること
   4. コードをもつれさせないこと
   5. コードにコメントをつけること
   6. ごちゃごちゃにしないこと
   7. 既存のスタイルに融け込むこと

---

Data

☆meta data

メタデータとは、データについての情報を記述したデータである。膨大なデータの山の中から目的のデータを探し出す手助けとするために作成される。インターネット上にある膨大な情報も、現実には、単純なキーワード検索しかできないため、壮大なゴミの山と称されることもあるが、個々の情報にメタデータを付けることにより、よりデータの性質を的確に反映した検索が可能となる。特に、画像データなどは、そのままでは単純なキーワード検索を行うこともできず、メタデータの恩恵を大きく受ける。

☆文字コード

◎概念

◆符号化文字集合
CCS: Coded Character Set

文字コードで表現可能な文字の範囲

※代表的な日本語の符号化文字集合

1. JIS X0201 + 0208 + 0212
⇒ISO-2022-JP, Shift JIS, EUC-JPが用いる
ASCII文字、日本語文字、少数の記号

2. UCS (ISO-10646)
⇒Unicodeの文字集合。日本語を含む各国語含まれる

◆エンコーディング
CES: Character Encoding Scheme
文字を実際のバイト列に落とすときの計算式

＿◇ワイドキャラクタ
wide character

全ての文字に対して同じバイト数を使う
⇒処理が簡単

※libcにはANSI Cで規定されているワイドキャラクタ文字列APIが含まれる。

＿◇マルチバイトキャラクタ
multibyte character

文字の種類によって使うバイト数を変える
⇒保存や転送の効率が良い

＿◇文字コードへの対処方法

①文字コード決めうち
簡単だが、用途限定される
②適当に推測
Unicode含めると現実的ではない
③文字コード名を受け渡す
今のところいつもできるわけではない

※GNU libcには相互変換のための iconv ライブラリが含まれる。

※鬼車
EUC-JP, Shift JIS, UTF-8対応の正規表現ライブラリ
Perl5拡張含む

http://www.geocities.jp/kosako3/oniguruma/

◆多言語化
multilingualization

処理対象にする文字コードを増やす

※M17N

◆地域化
localization

プログラムの動作を地域の慣習に合わせる

※L10N

◆国際化
internationalization

実行時に対応地域を切り替えられるように作る

※I18N

※gettext
プログラムのメッセージを国際するためのライブラリ

http://www.gnu.org/software/gettext/

＿◇ロケール
locale

国と言語と文字コードの組み合わせ

例）
ja_JP.eucJP
ja 日本語
JP 日本
eucJP EUC-JP文字コード

※環境変数
LANG
LC_ALL
LC_TIME
などで指定する

※setlocale(3)により、ライブラリ関数の挙動がロケールにあわせて変化する
printf(3)
scanf(3)
strtol(3)
strftime(3)
など

◎ASCII
7bit ASCII
ANSIが1963年にデータ交換用の標準文字コードして規定したもの
⇒ANSI X3.4-1986

0x00~0x1F 通信制御用
0x20 SPACE
0x21~0x2F 記号
0x30~0x39 数字
0x3A~0x3F 記号
0x40 @
0x41~0x5A A-Z
0x5B~0x60 記号
0x61~0x7A a-z
0x7B~0x7E 記号
0x7F DEL

0x00 NULL
0x09 HT
0x0A LF
0x0B VT
0x0C FF
0x0D CR
0x0E SO
0x0F SI
0x1B ESC

◎ISO646
7ビットコード化文字集合。7ビットASCIIの部分集合となっている。各国の国内規格によりかわらない文字を既定した不変コード集合と0x23,0x24を当てはめた基本符号表、国際標準版の3レベルある。

※各国での文字コードの入れ替えを許可した部分
ASCII JIS-X0201
0x23 #
0x24 $
0x40 @
0x5B [
0x5C ＼ \
0x5D ]
0x5E ^
0x60 _
0x7B {
0x7C |
0x7D }
0x7E ~ (上棒）

ISO646英国 #->ポンド記号
ISO646ドイツ、フランスでは８，１０文字変更

＿◇JIS X0201
JISの定めたASCIIに相当する文字セット
ASCIIに加えて半角のカタカナを規定

~ が ￣（こちらは９７年の改定で~でも良くなった）
＼ が \

に割り当てられたために、表示が混乱した

※ISO8859に相当する8ビット部分の定義もあり

0x89-0x9F 定義なし
0xA0-0xDF 半角カナなど
0xE0-0xFF 定義なし

….◎ISO8859
◎ISO8859
7bitのISO646を8ビットに拡張したもの
前半はISO646のままで、広範に各国固有の文字を割り当て

ISO8859-1 Latin1 西ヨーロッパ
⇒英語版Windowsのデフォルト文字コードとほぼ同じ
ISO8859-2 Latin2 東ヨーロッパ
ISO8859-3 Latin3 南ヨーロッパ
ISO8859-4 Latin4 北ヨーロッパ
ISO8859-5 Latin/Cyrillic キリル文字
他にもLatinには10まで変種あり

※地域の各国の文字を１文書の中で混在させることができる

※コードとして利用さているのは
0xA0-0xFF

※日本語はISO8859規格に含まれておらず、JIS X 0201がISO8859を考慮して制定された。

◎コードページ437
英語版MS-DOSなどで使われていた８ビットコード

◎コードページ1252
英語版Windowsの標準

◎JIS C 6226
1978年に韓国された日本国内の最初の漢字コード規格
通称：旧JIS

◎JIS X0208
通称 新JISだが
-1983
-1990
-1997 （シフトＪＩＳ符号化も規格化）
のバージョンがあり。-1983は旧JISとの互換性の無さが問題になった。

２バイト文字（漢字）セット
第１バイト　21h～7Eh
第２バイト　21h～7Eh
を２つ組み合わせて１文字を表す。２バイト文字への切り替えは、３文字エスケープシーケンスによる。
ESC $ B ->２バイト文字
ESC ( B ->１バイト文字
第１バイトが21h～4Fhまでが第１水準。第２バイトが50h～7Ehまでが第２水準。

＿◇文字コードとエスケープシーケンス
必ず文章の最後では、半角文字に戻す規約がある。

ASCII 1B 28 42
JIS X 0201-1976 Roman 1B 28 42
JIS X 0201-1976 カタカナ 1B 28 42
JIS C 6226-1978 1B 28 40
JIS X 0208-1983 1B 28 42
JIS X 0208-1990 1B 28 42 / 1B 28 40
JIS X 0208-1997 1B 28 42 / 1B 28 40
JIS X 0212-1990 1B 24 28 44

◎JIS X0212
JIS X0208に含まれない漢字を補うための符号化文字集合。補助漢字セット。

◎ISO 2022-JP
JISコードを国際規格として表現した名前
主としてインターネットメールで使われる。

※マルチバイト

◎EUC Extended Unix Code
0～127まではASCIIと一致する。MSB=1となるコードは２バイト文字。
漢字コードはJISコードに0x8080を足す。
半角カナは0x8E00を足して２バイトにする。

マルチバイト

◎SJIS
マイクロソフトがエスケープシーケンスを使用せず、半角文字と漢字文字を識別するために、JIS X0201の半角文字が使っていない領域にJIS漢字コードをシフトさせたもの
0x8140~0x9FFC, 0xE040~0xFCFCの２ヶ所に分離

第１バイト　81h～9Fh, E0h～FCh
第２バイト　40h～7Eh, 80h～FCh
F040以降は多く外字領域として使われる。
ＪＩＳコード2121hを8140h起点にそのまま流しこんだ形。JISが94×94の空間なのに対して、SJISは188x(31+16+13)

※WindowsとMacOS(9)以前で使われていた

※JIS Xに機種依存も維持を含めた符号化文字集合を使っているので、厳密にはＪＩＳとは異なる
Windows-31J
CP932

※マルチバイト

※CP932
コードページ932
日本語版Windowsの標準文字コード
JIS X 0209:1990のキャラクタセットに加えて、NEC PC-9801特殊文字とIBM拡張文字を含む
⇒NEC特殊文字とIBM拡張文字は、異なる文字が同じUnicode文字にマップされることがありえるので、可逆変換が保証されない。

◎EBCDIC Extended Binary Coded Decimal Interchange Code
IBM System/360 で使用するために開発された英数字8ビットコード体系。
0xC0~C9 A..I
0xD0~D9 J..R
0xE0~E9 S..Z
0xF0~F9 0..9

◎ISO 10646
世界中の文字を取り込むためにISOが開発を進めたが、後にUnicodeと統一され、ISOからは

ISO 10646-1

Unicode Consortumからは、

Unicode 1.1

として内容一致した形で策定された

＿◇ISO 10646 UCS-4
４バイトコード
文字を３１ビットで符号化

全１２８群、各群２５６面
１面は２５６ｘ２５６
ただし、第１群(0)の第０面は、BMPと呼ばれる基本多言語面。各群で独自に使えるのは１～２５５面

BMP: Basic Multilingual Plane
⇒ISO/IEC 10646-1で既定
英数字、記号、日本／中国／韓国の漢字、ハングルなども含む

※UCS: Universal Multiple-Octet Coded Character Set

＿◇ISO 10646 UCS-2
２バイトコード。Unicode(UTF-16)とほぼ同一、ただし多言語面は１面のみ

UCS-4のBMPを取り出して１６ビット化したものに近い。

第０面BMPは１０２４ｘ１０２４サイズ

※半角文字も２バイトとなる

….◎Unicode
◎Unicode
IBM, Microsoft, Appleなどが中心となって Unicode Consortiumが制定。ISO 10646-1と内容一致

＿◇UTF-16
UCS-2と一部のUCS-4の文字をコード化
２バイトコード。

※サロゲート・コードにより２個の１６ビット値を使って拡張をおこなっている
⇒２バイトの文字の割り当てのない0xd800から0xdfffを2個組み合わせて1024*1024（約100万)の文字を表す
⇒ここにUCS-4のBMPより後ろの16面を格納する

半角文字も２バイトとなる
⇒ワイドキャラクタ

※Javaと.NETは内部的にUTF-16

※合成文字 combining characterがある
フランス語などのアクセント記号

※２バイトコードのため、既存のライブラリなどにそのまま通そうとすると、問題が起こる。(ASCIIコードも上位バイトに０が入っている）

※エンディアン
UTF-16 little endianとUTF-16 big endianがある。

＿◇UTF-8
UCS Transfer Format-8

UTF-16を8ビット単位可変長で表現したもの
１文字は１バイト～６バイトになる
⇒マルチバイト
⇒アスキーコードはそのまま１バイト

※アルファベットや数字。。。ASCIIと同一の１バイト
日本語は３バイト

※XMLはUTF-8を推奨。PerlもUTF-8

※文字集合はＵＣＳ－２

※エンコーディング
ISO/IEC 10646
0x01～0x7f 最上位ビット”0″の１バイト
0x80～0x7ff 最上位”110″の第１バイト＋
最上位”10″の第２バイト
0x800～0xffff 最上位”1110″の第１バイト＋
最上位”10″の第２バイト＋
最上位”10″の第３バイト
0x10000～0x1fffff
最上位”11110″の第１バイト＋
最上位”10″の第２バイト＋
最上位”10″の第３バイト＋
最上位”10″の第４バイト

＿◇BOM
Byte Order Mark

リトル/ビッグの判別の判別のためにファイル先頭に付加される

UTF-16 ２バイト
リトル FF FE
ビッグ FE FF

UTF-8 ３バイト
EF BB BF

＿◇ハン・ユニフィケーション
China, Japan, Koreaの頭文字でCJK
BMPの中に漢字を押し込めるために意味が同じで字形だけ違う異体字を同じコードに押し込めてしまった

※1つの言語であればあまり問題ないが、複数言語を取り扱う場合には複数のフォントの切替が必要になる。

---

☆GRAPHICS

◆三原色

＿◇光の三原色
赤
マゼンタ
青
シアン
緑
黄

全部重ねると白

＿◇印刷の三原色
シアン(Cyan: 青緑）
青
マゼンタ(Magenta: 赤紫）
赤
黄（Yellow）
緑

全部重ねると黒

＿◇マンセル表色系
A.H.Munsell

色相(hue)
明度(brightness)
彩度(chromaticness)

※HSV方式、HSL方式

＿◇RGB
Red
Green
Blue

３原色の加法混色混合

＿◇sRGB
standard RGB

IECが定めたRGB
⇒一般的デジカメなどで採用

RGB各０～２５５、16777216色

＿◇HSI

Hue 色相
Saturation 彩度
Intensity 明度

＿◇フルカラー

※２４ビット画像
ＲＧＢ各８ビット

※３２ビット画像
２４ビット画像＋マスクチャンネル８ビット
⇒アルファチャンネル

◆2D描画

＿◇曲線

1. 1. Spline curve
   2. Bezier curve

＿◇ブラシ処理

1. 1. tint paint
      ブラシの色と背景の色をまぜ、水彩の重ね塗りのような効果を得る
   2. value paint
      ブラシで描いた部分の明るさを変化させる

＿◇Aliasing
Jaggyが生じることをAliasingという。これを目立たなくする処理がアンチエイリアシング

＿◇トーンカーブ
明るさの補正

＿◇フィルタ
フィルタ行列をつかって画素の値を再計算する。

ボカシ 周囲画素の値と平均化
シャープ化 中央5で上下、左右-1…明るさの変化大
エッジ抽出 ((1 0)(0 -1))…斜めに隣り合う画素
エンボスはエッジ抽出後に濃度調整

※フィルタの前後で明るさが変わらないようにするためには、フィルタ行列の係数の和が１でないとならない。

＿◇レイヤ

＿◇マスク
画像の任意の部分を透明にする機能
.

◆3D描画

＿◇座標系
右手系：右手の親指ｘ、人差し指Ｙ，中指ｚ
ＣＡＤ

左手系：左手の親指ｘ、人差し指Ｙ，中指ｚ
３ＤＣＧ

※ワールド座標、ローカル座標

※アフィン変換
平行移動
拡大、縮小
回転
せん断（スキュー）

※回転
右手の親指を回転軸の方向にむけたとき、他の指の方向が＋となる。

＿◇モデリング
立体オブジェクトを作り、立体空間の任意の位置に配置していく作業

①ワイヤフレームモデル
頂点のデータおよび各頂点の組み合わせとしてあらわされる線分のデータからなる。

②サーフェスモデル
ワイヤフレームモデルに加えて線分の組み合わせで面を表す。

ポリゴン(polygon)
立体を表現するために使われるひとつひとつの多角形。通常３角形。

複数の曲面（パッチ）
Bスプライン曲面
ベジェ曲面
NURBS曲面

③ソリッドモデル
球、立方体、円筒等の基本的な形の立体（プリミティブ）を組み合わせて立体を作る。ソリッドモデルの足し算、引き算、掛け算も論理演算（ブーリアン）とよぶ。

CSG表現 Constructive Solid Geometry representation

④立体モデルの生成

回転

スイープ。
ポイントスイープ

ベベル（カドに丸みを持たせる）

メタボール
電荷と等電位面を使って曲面を表現する。

フラクタル図形

※フリーソフト
POB-Ray レイトレーシング
DOGA CGアニメ、初心者OK
六角大王

＿◇モデリング：Extrusion
平面図の積み重ねで立体をつくる

＿◇モデリング：Rathe
平面図を回転させて立体をつくる

＿◇モデリング：デフォルトオブジェクト
部品を組み合わせて立体をつくる

※球や立方体などのプリミティブを組み合わせ変形される。

＿◇テクスチャマッピング

①Surface Texture Mapping
２次元の画像を３次元の物体に貼り付ける。

②バンプマッピング
デコボコの形状をマッピングするためにシェーディングをかけるときの面の向きを変化させる→陰影の付き方が変化し、デコボコに見える。

③環境マッピング
リフレクションマッピング（反射）reflection
映りこみを表現。マッピングしたい物体のまわりに球や円筒をおき映りこませる背景をマッピング。視点から物体を反射して到達したマッピング背景の色を物体の色とする。
リフラクションマッピング（屈折）refraction

④ソリッドテクスチャ
Solid Texture Mapping
３次元空間中に模様データを作成しておく。ここから立体を切り出すと模様が現れる。
⇒フラクタルなどを使って数式で生成する

＿◇ライティング
Lighting

＿◇シェーディング

陰　光の方向と面の向きにより面の明るさが変化する
シェーディング
影　物体が光をさえぎって光があたらない部分
シャドウイング

拡散反射（ディヒューズ）＜＞鏡面反射（スペキュラ）

環境光（アンビエント）

屈折

フラットシェーディング（ポリゴン平面のまま）
つなぎ目が目立つ
スムースシェーディング
なめらかに変化させる
グローシェーディング
ポリゴンの頂点の明るさと距離から計算
計算量すくないがハイライト表現など苦手
フォンシェーディング
法線のむきを補完して明るさを計算する。

光源
平行光源 太陽、光源からの距離で明るさ変わらない

点光源 ランプ、遠ざかると暗くなる、一枚の平面でも明るさが一様にならない

スポット光源 スポットライト

＿◇レイトレーシング（光線追跡法）
視点からビューウインドウの全ての画素に向かって視線を伸ばす。物体にぶつかったら、その面でのテクスチャ情報から色を、照明と面の関係から明るさを決める。反射があればさらに光線を追跡し、屈折があれば、屈折した光線を追跡する。

ラジオシティ
レイトレーシングのシャープすぎる画像を面素ごとの光の相互反射を考慮してぼかすことで自然にしたもの

＿◇レンダリング

投影

①透視投影
視点から、投影面（ビューウインドウ）ごしに３Ｄ物体を見る形
座標系を右Ｘ，上Ｙ，手前Ｚとし、
物体の３次元座標を(x,y,z)とし、視点は、(0,0,f)にあったとするとビューウインドウ上に投影される位置(x*,y*)は、

x* = x * (f /(f-z))
y* = y * (f /(f-z))

※視点を頂点としてビューウインドウの対角の２点がなす角を視覚という。
※視点を頂点とする４角錐をビューボリュームという。
※視点、ビューウインドウ間の距離を焦点距離と呼ぶ。焦点距離が短ければ広い範囲が写り物体は小さく見え、焦点距離が長ければ物体は大きく見える
※写らない文体を切り取る処理をクリッピングという。

②平衡投影
平行光線で投影面に投影

陰線消去、陰面消去
①Zソート法
一番奥にあるポリゴンから書いていく。上塗りされることで隠れる。複雑な図形の場合はうまく表示できない場合あり。②Zバッファ法
画素毎に奥行きの情報を一時的に記憶しておき、もっとも近いポリゴンの色でその画素を塗る。
③スキャンライン法
スキャンライン毎に面の奥行きを調べる。透明物体やアンチエイリアシングの処理も行えるので、Zバッファ法よりリアルだが時間がかかる。

＿◇ボリュームレンダリング

ボクセル(voxel)

雲や霧、立体の内部透視なども表現可能。

◆アニメーション

＿◇morphing

クロスディゾルブ

ワーピング

＿◇パーティクル

煙や炎などを小さな粒子の集まりで表現する

＿◇モーションブラー

＿◇モーションキャプチャ

＿◇インバースキネマティクス

◆ソフトウエア

＿◇OpenGL

＿◇Direct3D

＿◇VRML (Virtual Reality Modeling Language)

◆BMP
①ファイル先頭の２文字は”BM”である。

②以下にファイルヘッダがくる。intは４バイト、shortは２バイト。

typedef struct
{
/* File Header */
unsigned int fileSize;
unsigned short unused0;
unsigned short unused1;
unsigned int rasterOffset;

/*Infomation Header */
unsigned int headerSize;
unsigned int picWidth;
unsigned int picHeight;
unsigned short plane;
unsigned short colorBit;
unsigned int Compression;
unsigned int ImageSize;
unsigned int resolutionW;
unsigned int resolutionH;
unsigned int numOfidxCol;
unsigned int numOfimpCol;
} bmpFileHeader;

③インデックスカラーの場合、以下のCLUTが続く。１エントリ４バイト。

typedef struct
{
unsigned char B;
unsigned char G;
unsigned char R;
unsigned char filler;
} bmpCLUT;

④ラスタデータ（４バイトの倍数にパック）。左下隅が原点。左から右へ、下から上へ。ピクセル内では画像左がＬＳＢ。

---

☆Audio/Video

◎Audio

◆μ-Law, A-Law
コンバインディング・アルゴリズム

携帯、IP電話のコーデックで使われた
サンプリング8kHz, １サンプル1バイト

＿◇PCMU(G.711 mu-Law; μ-Law)
日米

＿◇PCMA(G.711 A-Law; A-Law)
欧州

◎Video

◆AVI
Windows系OSの標準的動画フォーマット。元々はVideo for Windows向けに開発

＿◇バージョンと種類
①AVI 1.0
ファイルサイズ上限2GB。ファイルヘッダ、音声、映像が一つのブロックに

②AVI 2.0
ファイルサイズ上限はOSの扱えるファイルサイズ。Video for Windowsでなく、DirectShowでアクセスする

③参照AVI
ファイルヘッダと音声が一つのブロックだが、映像は複数の別ブロックにいれることができ、擬似的にファイルサイズの上限を撤廃。AVI 1.0と大差ないアクセスが可能。

◆WMV
ストリーミング念頭にMPEG4をもとにしている。固定ビットレートと可変ビットレートに対応。
320×240 … 400Kbps
640×480 … 800Kbps~1Mbps
Windows Media Player必須。ＭＳの独自フォーマット。

 

---

☆概念、用語

◆プログラミング

＿◇手続き型プログラミング

FORTRAN, COBOL, Cなど

①データと処理が分かれている
②アルゴリズムで決められた順にデータを処理する

※発展
機械語 Machine Language
アセンブリ語 Assembly Language
高級言語 High-Level Language

＿◇オブジェクト指向
object oriented

※オブジェクトを使ってデータ処理をおこなう考え方
※プログラミング技法⇒オブジェクト指向プログラミング(Object Oriented Programming)

※オブジェクト
状態
ふるまい
識別性

※分散オブジェクト
Distributed Object
オブジェクトをネットワーク上のコンピュータに配置して連携動作させる
⇒例：クライアント側の代理オブジェクト（プロキシ）を通じてサーバ側のオブジェクトと通信する

※主な分散オブジェクト技術
DCOM, COM+, CORBA, JavaRMI, HORB

①クラスというオブジェクトの「型」
Class
⇒オブジェクトの実体であるインスタンス
Instance
C#: newによるインスタンスの作成
参照変数へnull代入による参照の解放
②オブジェクト
フィールド Field
プロパティ Property
メソッド Method
イベント Event
インタフェースを使った呼び出し方の定義
Interface
シグネチャを定義するだけ
③クラスの継承
Inheritance
基本クラス（基底クラス、スーパクラス）
派生クラス（サブクラス）
再定義によるポリモーフィズム
Polymorphism（多態性）
派生クラスで継承したメンバを再定義
Override
④カプセル化による隠蔽
Encapsulation

＿◇バリアント（variant)
ループインバリアント
ループの開始時と終了時の両方で成り立つもの
バリアント
ループの繰り返しごとにゴールに向かって変化するもの

◆数値計算

＿◇桁落ち
計算結果の有効数字の桁数よりも、得られた結果の有効数字の桁数が少なくなること。

※おおきさの小さい２つの数を引き算すると桁落ちが生じる。例）２次方程式の根の公式
4acがb^2にくらべて非常に小さい場合はけた落ちの危険がある。

◆シリアライズ
１リソースの利用の調整、一つの主体だけが利用できるようにする（逐次化）
（マルチスレッドプログラミングにおける）⇒排他制御

２オブジェクトをバイト列やＸＭＬに変換すること（直列化）＜＞デシリアライズ（直列化復元）
⇒オブジェクトを直列化してファイルなどの永続記憶に保存すること（永続化）

◆スレッドセーフ
複数のスレッドから呼び出してもよいように設計されていること

☆問題

◆算術

＿◇バベッジの問題
その数の平方が269696で終わる最小の値を求めよ

バベッジの解 99736（階差計算を繰り返した得た）
クラインの解 25264 (暗算で３分で解いたといわれる）

＿◇アッカーマン関数
非負の整数 m と n に対し
{n+1, if m=0
Ack(m,n)= {Ack(m-1,1), if n=0
{Ack(m-1,Ack(m,n-1)), otherwise

☆接頭語

①k 1000をあらわすSI接頭語
②K 情報処理分野で1024を示す接頭語
③M 10^6をあらわすSI接頭語.
情報処理分野で1048576を示す接頭語

---

☆デザインパターン

◆マルチスレッド
＿◇Single Threaded Execution
＿◇Immutable
＿◇Guarded Suspension
＿◇Balking
＿◇Producer-Consumer
＿◇Read-Write Lock
＿◇Thread-Per-Message
＿◇Worker Thread
＿◇Future
＿◇Two-Phase Termination
＿◇Thread-Specific Storage
＿◇Active Object

☆デバッグ

①失敗を観察する
②その失敗の原因について仮説を提案する
③予測をする。
④その予測をテストする
⑤適切な結論を出す

※過程は明示的に述べること。仮定と観察の記録を書き留めること。
※系統立っている。明確な仮設や仮説に基く予測がないまま、ランダムに何かを変えてはいけない。
※一番可能性の高い原因から調べる。

---

☆バグ

◆ハードウエアバグ

◇ペンティアムのバグ (1994)
X=4195835, Y=3145727
X-(X/Y)*Y が 256となった。

---

Architecture

☆分類

◆アキュムレータマシン

PDP-8
命令語長12ビット
メモリアドレス指定7ビット。先頭128語を介する間接アドレッシング

◆汎用レジスタマシン

※x86
レジスタ8個

※VAX
レジスタ16個

※RISC
レジスタ32個の場合が多い

※Itanium
レジスタ128個

◆エンディアン

※Big Endian
IBM System360, PowerPC, SPARC

※Little Endian
DEC, Intel

☆命令セット

◆EDSACのコード系

例）
An: 累算機の内容に記憶装置上のn番地の内容を加算し、結果を累算機に格納
Un: 累算機の内容を記憶装置上のn番地に格納

A 加算
S 減算
V 積の加算
N 積の減算
U 記憶
C 論理積加算
I 入力
O 出力
R 右シフト
L 左シフト

◆CISC
Complex-instruction-set computer

＿◇CISCの前提
ある利用可能なテクノロジを仮定したとき、１命令あたりの所要サイクル数が命令フェッチに要するサイクル数で決まる
⇒実行命令数を減らす
⇒１個の命令により多くのことを行わせるようにエンコード

※一般にCISCのバイナリコードはRISCのバイナリコードにくらべて20～30%程度小さい。

◆RISC
Reduced-instruction-set computer

＿◇RISCの前提
命令数が多少増加しても良いが、命令の実行に要するサイクル数を減少させる

＿◇遅延分岐
delayed branch

遅延分岐の実行⇒プロセッサは現在の命令流の実行をインプリに依存する数継続すると同時に分岐先の命令流をとりこむ

※命令数
分岐決定に要するサイクル数と分岐先命令をフェッチするのに要する命令数
⇒通常のＲＩＳＣでは分岐の決定はデコードステージ

※コンパイラ
分岐命令の後に来る命令をスケジューリングする必要がある

◆VLIW

＿◇Itanium

128ビットが命令バンドル
41ビット長の命令を３つ格納
のこり5ビットがテンプレート
⇒テンプレートによりどのタイプの命令がどの命令スロットに入っているか示す

☆メモリアクセス

◆メモリアクセス順序
メモリオーダリング

※同一アドレスに対するアクセス順序の問題
⇒ほとんどのプロセッサでプログラム通り実行される
⇒IA-64ではそうではない

※異なるアドレスに対するアクセス順序の問題
⇒ほとんどのプロセッサで問題となる

Write After Read(WAR)
Read After Write(RAW)
Read After Read(RAR)
Write After Write(WAR)

①Strong Ordering
全てのパターンで順序が守られる
Sequential Ordering
Program Ordering
⇒i386, PA-RISC

②Total Store Ordering
RAR, WAR, WAWでオーダ守られるが、RAWでは逆転の可能性あり
⇒IBM370, SPARC(normal), i486, Pentium

③Parial Store Ordering
RAR, WARではオーダ守られるが、WAW、RAWでは守られない可能性あり
⇒SPARC(PSOモード）

④Speculative Processor Ordering
WAWではオーダ守られるが、RAR, WAR, RAWでは守られない可能性あり
⇒PentiumPro, Pentium4

⑤Weak Ordering
全てのパターンで順序の入れ替えを認める
Relaxed Memory Ordering
⇒IA-64, Alpha, POWER, SPARC(RMOモード)

◆ストアバッファとメモリバリア命令

＿◇ストアバッファ

①同じアドレスにストア命令が２回実行される場合、最初のストア命令がキャッシュへ書き込むのをキャンセルする

②同じアドレスにストア命令→ロード命令が連続する場合、後ろのロード命令はストアバッファからデータをもらい、キャッシュ読み込みをパスする

＿◇メモリバリア命令

フェンス命令
シリアライズ

※x86のメモリバッファ命令
①sfence PentiumIII
ストア命令のシリアル化 WAWを順序化
②lfence Pentium4
ロード命令のシリアル化 RARを順序化
③mfence Pentium4
すべてのパターンのシリアル化

※IA-64
mf
⇒独特の機構あり、主にそちらで解決

※PowerPC & Power
sync, lwsync, eieio, isync

※SPARC
stbar, membar

※PA-RISC
sync
⇒基本strong ordering、キャッシュ制御などでゆるい

※Alpha
mb, wmb

※MIPS
sync
⇒アーキテクチャレベルでは決まっていないので、使用はチップによる

☆BUS

◎バストランザクションの5つの基本動作

(1)調停
次に使用する装置を決定する。時分割によって複数の装置がバスを使用できるようにする。各装置からの要求信号をとりまとめて、要求度が重なったときは、所定の方法に従って次に使用する装置を決定する。バスを使用する装置のことをバスマスタと呼ぶ。

(2)アドレス転送
転送対象を指定する。バスマスタはアドレスをバス上に出し、転送相手とその装置内の転送対象を指定する。転送相手をバススレーブと呼ぶ。転送相手が主記憶の場合、アドレスは主記憶のアドレスとなり、転送相手が入出力装置の場合は装置内のレジスタを選択する。

(3)データ転送
実際のデータ転送。

(4)応答
指定した転送対象が正常に動作したか、送られたデータに誤りがなかったかなどを連絡し合う。

(5)終了
バスを解放し、次の装置にバスの使用権を渡す。

☆評価方法

◆シミュレーション

抽象度：
膨大なケースを調査できるほど高く
＜＞
詳細設計における意思決定を反映できるほど低く

⇒トレードオフに関する評価は実験の様相を呈する
⇒個々の選択肢の長所と短所を相対的に判断する必要あり

※最適化されているコードに対して評価

＿◇トレース駆動シミュレーション
trace-driven simulation

ベースマシンが実行したウログラムの命令列に対して、性能を与える機能をシミュレーションし、性能を評価する

◆性能に関する法則

＿◇アムダールの法則

1967 アムダール

プログラムの処理時間 T
高速化可能な処理の割合 r
高速化できない処理の割合 (1-r)

T = T*r + T*(1-r)

rの処理について処理時間を 1/n にできるとすれば

Tn = (T*r/n) + T*(1-r)

実行速度の向上比は

T/Tn = 1/{(1-r)+(r/n)}

lim[n->∞]T/Tn = 1/(1-r)

※アムダールの法則はプログラムが対象とする問題の規模や作業負荷を固定

＿◇グスタフソンの法則

1988 グスタフソン

※マルチコア化により問題の規模や作業負荷を増やせる

ｎ個のコアで実行したときに
Tn = Tn*r + Tn*(1-r)
と表せるならば、１個のCPUコアでは
T1 = Tn*r*n + Tn*(1-r)

T1/Tn = n – (1-r)*(n-1)

※扱う処理のデータ量が増加⇒並列処理の割合も増やすことができる
⇒ＣＰＵコアを多く投入するのは有効

◆ベンチマーク

＿◇最適化
コンパイラによる最適化＜＞ハードウエアの命令並列性の活用、ハードウエアの性能をみるためには十分なコンパイラ最適化の行われたコードを使用する

＿◇キャッシュの影響

キャッシュ・ローディングのオーバヘッドを測定結果に含めること

※マルチタスキング環境では、プロセスはある一定時間実行されてからサスペンドされ、再びキャッシュデータが存在しない状態で実行を再開する
⇒ある程度の実行命令数を経過すると性能はあまり変化しなくなる。

＿◇速度向上比
Speedup
基準クロック数／向上したケースのクロック数

※あるプロセッサ構成に関する測定値は全ベンチマークの速度向上比の最大、平均、最小で表す

※調和平均
harmonic mean
複数のベンチマークの平均をとるときには、全ベンチマークの総実行時間を反映するために調和平均をとる
ｎ
－－－－－－－－－－
Σ[i=1:n]{ 1/x_i }

＿◇代表的ベンチマークテスト

①5diff
テキストファイル比較

②awk
パターン走査、パターン処理

③ccom
最適化Ｃコンパイラ

④compress
Lempel-Ziv符号化、ファイル圧縮

⑤doduc
モンテカルロ・シミュレーション（倍精度浮動小数点）

⑥espresso
論理圧縮

⑦gnuchess
チェス

⑧grep
複数のテキストファイル中のストリング出現回数

⑨irsim
VLSI、レイアウトの遅延付きシミュレータ

⑩latex
文書聖書

⑪Linpack
汎用ではない。浮動小数点演算。命令並列性小
線形代数解法（倍精度浮動小数点）

⑫nroff
テキスト・フォーマッタ

⑬simple
流体力学コード

⑭spice2g6
回路シミュレータ

⑮troff
テキストフォーマッタ

⑯wolf
スタンダード・セルの配置、シミュレーテッド・アニーリング解法

⑰Whetstone
汎用ではない。浮動小数点演算ベンチマーク。命令並列性小。（倍精度浮動小数点）

⑱yacc
文脈自由文法からＬＲ（１）解析テーブルへのコンパイル

◆限界の見極め

命令並列性が、性能要求に対する限界を与える
⇒真の依存関係によってのみ決まる命令並列性
⇒資源競合：無限の資源により解消
⇒メモリ競合：名前替えにより解消
⇒手続き依存：分岐命令の結果が分かれば解消

※真の依存関係
０命令発行サイクルと１命令発行サイクルの発生
⇒サイクル数は機能ユニットのレイテンシによって決まる

※一般的なベンチマークの平均性能では、レイテンシ０を仮定しても１サイクルあたり３．３命令発行という限界がある。（真の依存関係による）

※キャッシュミスのレイテンシも含めないと現実的な数値とならない。

☆整数演算器

◆加算器
Adder

※アダーを高速にするには、最適な論理だけでなくゲートやバッファサイズの最適化などのチューニングも重要

＿◇リップルキャリーアダー

キャリを最下位から最上位にまで伝播させる
⇒多ビットの加算では伝搬遅延時間が問題となる

＿◇キャリールックアヘッドアダー
Carry Lookahead

P: Propagate
外からのキャリーが伝搬するか内部で発生する
G: Generate
キャリーが発生する
２つの信号を発生し、手前でキャリー相当の信号を作り出す。
後段のＳＵＭ回路にキャリーを与えるが、ＳＵＭ回路のキャリーは伝播させない。
⇒パスを短くすることができる。

※実例
TI 74S181, 74S182

＿◇パラレルプリフィックスアダー
Parallel Prefix

キャリーをプリフィックス計算として並列に計算するアダーの総称

キャリールックアヘッド型の一般形
前段で各ビットのXORと、P、G信号を求める
中段で各ビットへのキャリーを求め
後段でキャリー込の和を求める

※ビット分割は任意

①Sklansky Adder
2^nビットのアダーで最大ｎ段のボックス通過でキャリーインを計算できる。最少構成。しかし、ファンナウトが大きい欠点がある。

②Kogge-Stone Adder
プリフィックスボックスの数が多くなるが、各ファンナウトは２とできる。
ただし後段になるほど、遠くからの配線が必要。

③Ladner-Fischer Adder
Sklanskyアダーにもう一段のボックス追加で、ファンナウトを半減させたもの
ビット数が多くなると有利

④Han-Carlson Adder
Kogge-Stoneアダーにもう一段のボックス追加で、ファンナウト２をキープしたまま、配線とボックス数を減少させたもの

※６４ビットのようなビット数の多いアダーでは、Kogee-Stone系のアダーの方がファンナウトが小さく高速にできる傾向がある。

＿◇Lingアダー

リングキャリー
H_i = C_i + C_i-1
を使う（C_iなどは通常のキャリー）
⇒Lingキャリーの方が通常のキャリーより高速に計算できるが、和の計算は複雑となる。
※Lingアダーにも Sklansky型とKogge-Stone型の両方がある

◆乗算器
Multiplier

被乗数(Multiplicand)
乗数(Multiplier)

＿◇原理

原理は筆算と同じ、２進であるので、乗数の各桁について、1ならば被乗数の1倍を加え、0ならば何も加えないという選択を行う。
これと積と乗数の右シフトを組み合わせる
⇒アダーの幅はＮビットで済む
⇒機械式のタイガー計算機は１０進であることを除けば原理は同じ

※乗数レジスタの各ビットを順に検査するのではなく、複数ビットを同時に検査し、ゼロがつづく場合はその分シフトしてしまうようにすると高速化が可能
⇒２ビット処理の場合は、乗数の値に対応し、被乗数の０～３倍の値を足しこむ

＿◇Boothのアルゴリズム

例）
乗数=01110の場合
01110=10000-00001
１回め：被乗数を引き右シフト
２～４回目：右シフトのみ
５回目：被乗数を足す

※オリジナルBooth　２ビットずつ乗算ビットをみて、場合により被乗数の加算、減算をおこなってから１ビット右シフトをする

※Modified Booth 乗数を２ビット単位、３ビット単位などで処理する
２ビット処理の場合
乗数の最下位ビットの下に０、最上位ビットの上に００を補い
３ビット分をみて加算値を決める（次回と１ビットのオーバラップあり）
２ビット＝４ずつ乗数を処理する
⇒Radix-4アルゴリズム
部分積
000 +0
001 +M
010 +M
011 +2M
100 -2M
101 -M
110 -M
111 -0
⇒M,2Mは１ビットずらすだけでつくれ、２ビット単位処理により部分積の数をN/2+1とほぼ半減できる。

＿◇リニアアレイ
部分積の加算を並列化して高速化する
⇒１ビットずつ処理する乗算器のループを物理的に展開

※ただし、アダーの通過時間が展開した段数だけ長くなるので、物量をつぎ込むわりには高速化の効果がすくない

＿◇パラレルアダー
乗数のビット数分の部分積を、２分木構造に接続したアダーでトーナメント方式で加算を行う。アダーの通過時間はlog2(N)段で済む

※アダーの段ごとにFFをおけば、パイプライン化することもできる。

※パラレルアダーとModified Boothアルゴリズムを組み合わせることが行われる

＿◇Wallace Tree
筆算で、各部分積をならべてから桁を合わせて桁毎に加算をおこなうやりかたを実現したもの。
⇒部分積の加算毎にキャリーを伝播させる必要がない

⇒加算結果をサムとキャリーで求めるCarrySaveAdder
⇒最終的な席をキャリー伝搬型のアダーで加算

※Booth Encoder+Wallace Treeが乗算器の定番

※カウンタエレメント
３つの入力の１の個数を数えてサムとキャリーの２ビットで出力

※負の部分積の処理
２の補数表示の場合、上位に１が並ぶ。
Booth Encoderを用いる場合には-M, -2Mの加算もあるので、上位桁でも入力は０にならない。（符号付きの乗算でも同様）
⇒Gray Bewickのアルゴリズム：最上位の上に１、T（部分積の符号ビットの否定）、最下位に部分積の符号ビットを付加することで負の部分積の上位桁のためのカウンタエレメントを減らす。

＿◇４－２コンプレッサー

４入力を２出力にするので４－２コンプレッサーとよばれる
⇒実際にはキャリーインとキャリーアウトがあるので５入力３出力

※下位の桁からのキャリーインはその桁のサムとキャリーには影響するが、キャリアウトには影響しない

※４－２コンプレッサーを用いると規則的な接続で部分積の加算回路が構成できる

◆割り算器

原理：筆算同様
部分商１を仮定して引き算を行い、結果がマイナスになれば引き算を元に戻して部分商を０にすることを繰り返す。

＿◇引き戻し法
Restoring Division

２新数１ケタずつを処理
徐数(Divisor), 被除数(Dividend) Nビット
⇒ハードは
除数レジスタ Nビット
商(Quotient)レジスタ Nビット（左シフト可
被除数レジスタ２Nビット（左シフト可
⇒商を被除数レジスタの左シフトで空いた下位ビットに詰めていけばレジスタは共用できる。

※筆算では商を立てる桁と部分剰余(Partial Remainder)が右の下位にずれるが、ハードウエアで計算する場合は左シフト。

※引き算の結果がマイナスならば引き過ぎなので、部分剰余に除数を足して元に戻す
⇒引き戻し

※一般に引き戻し法は２Ｎサイクルかかり、引き放し法はＮ＋１なので引き放し法の方が早いということになっているが、演算結果がマイナスならば元の被除数を書き戻すようにすればＮサイクルで割り算ができる。その際必要なＭＵＸは、引き放し法でも必要なのでハード量も大差ない

＿◇引き放し法
Non Restoring Division

部分剰余がプラスの場合は除数Ｄを引くが、部分剰余がマイナスの場合は、次の桁で除数を加える。
最終結果はプラスの部分商からマイナスの部分商を引いて（マイナスを引くので合計）もとめる（実際にはプラスの部分商を<<1して最下位に１を入れる）
⇒最後の余りが負になる場合があり、その場合は商を１減じて、剰余に除数を加える必要がある。

※Ｎと補正の１サイクルで商と剰余を求めることができる。

＿◇ゼロスキップ

初期状態で被除数レジスタの上位半分はゼロ
また、被除数も語長を一杯に使うケースはまれ
⇒被除数の上位のゼロをスキップすれば処理時間を短縮できる
⇒１検出の論理を単純化するために、最上位の数ビットの検査をする方法が一般的

＿◇１サイクル複数ビットの商をもとめる回路

ｂビットの部分商を求めるには、引き算器とマルチプレクサ入力が
（２＾ｂ）-１
必要。
⇒ビット数を増やすと物量が急激に増える。

※１ステップ１ビットの部分商の場合、単位は２の１乗なのでRadix-2とよぶ
以下２ビットならRadix-4, 3ビットならRadix-8…

＿◇ＳＲＴ法
現代のマイクロプロセッサの定番
IBMのSweeney、イリノイ大のRobertson、インペリアルカレッジのTocherがほぼ同時に考案した。

①部分剰余Piと除数Dの一部の上位ビットから部分商Qiの値を予測
②Pi-Qi*Dを計算し、部分剰余Pi+1を求める

ここで、冗長度のある状態割り当てによりPDプロットにどちらの値でもよいという領域をつくり、これを利用してP,Dの少数の上位ビットで索引する荒いマスのテーブルを作ってQiを求める。
⇒Quotient Selection Table
⇒Quotient Selection Logic

Radix-4のSRT法のステップ数はN/2+1

※最少冗長(Minimally Redundant)状態割り当て
⇒ｒ偶数に対して、-r/2~+r/2,0を含めて全体ではr+1個の値がとりうる
1個の冗長シンボルがある

※最大冗長(Maximally Redundant)状態割り当て
⇒-(r-1)~(r-1)の値を許容。2*r-1状態。

※冗長度を大きくするとPDプロットのマスを荒くでき、部分商選択テーブルが小さくなるが、加算器やマルチプレクサが増える

※キャリーセーブアダーによる高速化
⇒サムとキャリーに分かれると部分商選択テーブルは引けないので、テーブルを引くのに十分な精度のビット幅のキャリープロパゲーションアダーを別に設ける

※整数の場合は商を１の桁まで求めると終わりだが、浮動小数点の場合はレジスタのビット幅の範囲までループを繰り返す必要がある。

◆シフタ

シフト命令の種別

①左右
②シフトして溢れたビットを捨てるか、リング状につないでシフトするか（サーキュラーシフト、ローテイト）
③右シフトの場合、符号ビットを保存するか、否か

※論理的には単純な構成だが、長い配線が多数必要となり、遅延時間が長くなる

☆浮動小数点演算器

仮数 Mantissa
指数 Exponent

◆浮動小数点加算器

＿◇基本構造とノーマライズ
ビットの重みが指数部によって変わるので、ＥＸＰの値の差によって桁合わせを行う必要がある。

①比較回路で２オペランドの指数の大小を比較、小さい方のオペランドの仮数部が右シフタを通るようにスイッチを設定する。
⇒スイッチをでるところではHidden Bitが補われていること
②桁わせのためのシフト数を大指数から小指数を引き算器で引いてもとめ、右シフタに設定し、桁合わせをする
③桁がそろったので加算器で仮数どおしを加算する
⇒ガードビットとラウンドビットを含めて２ビット余計に計算する
⇒スティッキービットは、右シフトされたオペランドの下位桁に１があったかどうかを検出して求める。

※符号ビットによっては、加算でなく引き算をする必要がある

※正規化数以外は取り扱えないので、処理できない入力の場合にはトラップを上げる

④演算結果をノーマライズする
桁上がりの結果でＥＸＰを大きくする必要があることがある
オペランドの符号が異なる場合はＥＸＰが小さくなることもある
⇒左１ビットシフトではガードビットがあるので精度を保てる。その下のラウンドビットとスティッキービットで丸めも行える。

※多数ビットの桁落ちが発生するケース
絶対値がほぼ同じで、符号が異なるケース
⇒多くの上位ビットがゼロになってしまう。
⇒最上位の１がHidden Bitの位置にくるようにＥＸＰを調整する
⇒リーディングゼロカウンタと左シフタにより１サイクルでノーマライズ

※ノーマライザ
リーディングゼロカウンタ⇒２進でシフト数を示す
⇒上記のシフト数で動く２進Ｎ段のスイッチをつかう

※EXPの同じ引き算で符号が反転するケース⇒結果の変換必要
⇒それをさけるためのEXP同一時のFrac比較器を使うことががある。
⇒XORとってリーディングゼロカウンタで上位ビットを除き、最初の1で見分ける

＿◇丸め

IEEE754の丸め

①Nearest（最近似値）
⇒無限精度での計算結果と一番近い、表現可能な数に丸める
⇒表現可能な数の丁度中央の場合は、最下位ビットがゼロになる方に丸める
⇒誤差が同一ならばビット数を減らす方向の方が後々有利
⇒四捨五入とは異なる
②切り上げ
③切り捨て
④+∞
⑤-∞

※０．５ＬＳＢの上方向への丸めのためにフルビット長の＋１回路が必要になる
⇒ＥＸＰ値の＋１も必要となる。

＿◇２パス浮動小数点加算器

①ＥＸＰの値の差が０か１で、実質引き算となる場合にのみ多ビットのシフトによるノーマライズが必要となる
⇒桁合わせのシフトは高々１ビット
⇒ノーマライズは多数
②それ以外のケースでは、左右１ビット程度のノーマライズが必要になる程度
⇒桁合わせシフトが大きい
⇒ノーマライズは軽い

そこで①、②を別々のデータパスとし、
①
ＥＸＰを比較し、オペランドを入れ替える
加算
リーディングゼロカウントと左シフト

②
ＥＸＰの差の計算とオペランドの入れ替え
桁合わせシフト
加算

その後の加算は共通

※２パス化により長いシフタを２回通過する必要がなくなり高速化できる（ハード量は増える）

＿◇パイプライン処理

※浮動小数点演算⇒処理ステップ多い⇒１クロックで実行しようとするとパスが長くなり過ぎ、周波数低くなる
⇒パイプライン処理

例１）
１）ＥＸＰ計算＋オペランド入れ替え
２）桁合わせシフト
３）加算
４）丸め

例２）
１）ＥＸＰ比較＋オペランド入れ替え
２）加算
３）リーディングゼロカウントと左シフト
４）丸め

※毎クロック計算をスタートできる
※後続の演算が前の演算結果を要求する場合にはパイプラインバブルが入る

◆浮動小数点乗算器

仮数部（ヒドンビットの１を補った）の積の計算
指数部の加算
⇒だだし、バイアスが含まれている場合は、単純足し算するとバイアスが２回含まれることになるので、バイアス分を引く必要がある。
⇒IEEE754倍精度の例ではバイアス1023なので-1024+1する

符号は両オペランドの符号のＸＯＲ

※乗算では、桁合わせのための長い右シフトや、桁落ち後の正規化のための長い左シフトは不要
⇒正規化された入力オペランドは1.0以上2.0未満
⇒CPA出力は1.0以上4.0未満
⇒2.0以上の場合と丸め処理での桁上がりが最上位まで伝搬した場合に正規化必要
（ただし丸めを行っても結果が4.0を超えることはない）

※IEEE754倍精度52ビットFractionの場合、ヒドンビットを加えて53ビットなので、最終段のＣＰＡは106ビット分のサムとキャリーを加算する必用がある。

※乗算器もパイプライン化されるのが普通

※IEEE754規格準拠とするためには、積の指数部がオーバーフローして表現できる最大値を超えたときの∞や、正規の数で表現できる数値より小さくなった場合のデノーマル数処理をハードウエアもしくは、ソフトウエアで処理する必要がある。

◆浮動小数点積和演算器

※積和を必要とする算法は多い
※積と和の演算それぞれで丸め処理をおこなうより、両方行ってから一回丸め処理を行う方が有利
※Fused Multiply-Add
⇒IEEE754-1985準拠の場合は、積の結果を丸めたのちCを加えるという操作とは結果が異なる場合があるので使ってはならない
⇒IEEE754-2008では積和演算が規格に入ったので、準拠となった。

※積和演算
D=AxB+C
入力３、出力１の指定が必要

※３オペランドの積和命令
C=AxB+C

＿◇倍精度積和演算器の構造

ブースエンコーダーと、ウォレスツリーまでは乗算器と同じ、
ウォレスツリーの結果の加算のＣＳＡに加算するためのＣも加える
ただし、加算のためにはＡｘＢに桁合わせする必要があるので、左右シフタが必要となる。
⇒Cの最下位とAxBの最上位が１ビット重なるときが一番長い加算が必要となる
⇒ＣＳＡの後段のＣＰＡのビット長は長くなる
⇒Cが大きすぎて重ならない場合は、AxBの結果はガードビット以下のビットへの反映のみ。Cが小さすぎる場合もそのまま足してしまえばよい

※一般的実装６～７段パイプライン
①Booth Encoder
②～③Wallace Tree
④ＣＰＡ
⑤正規化シフタ
⑥丸め

◆浮動小数点除算器

※仮数の割り算と指数部の引き算

※最上位の１の位置がそろっているのでゼロスキップの必要がない
※小数点以下の商はガードビットやラウンドビットを含め有効数字の最下位まで求める必要がある
⇒回路としては整数の割り算と同様
⇒仮数部は1.0以上2.0未満なので、割り算結果は0.5より大きく、2.0未満
⇒1未満の結果のときに、1ビットの左シフトと、指数部の-1が必要となる
⇒指数部の引き算でバイアスが無くなってしまうので、バイアスを加算する

◆平方根演算器

※平方根により指数の値は元の数の指数の半分になる。
⇒結果の指数が整数であるために、元の指数が奇数（IEEE754ではバイアスが奇数なのでEXPの表記的には偶数）のとき、に指数を偶数とする（＋１）ために仮数を１ビット右シフトする。
⇒元の指数が偶数のときは、仮数を２ビット右シフトする
⇒上記の処理により仮数部の値は0.25以上、1.0未満となる

※SRT割り算のPD-Plotに似たR-PR-Plotを使った計算で求めることができる
⇒部分残差とCSA,CPAは除算回路と共用できる

◆反復法
商や平方根の近似値を初期値⇒誤差を計算⇒誤差を補正
このプロセスを繰り返す

＿◇Newton-Raphson法

※ a / b の商 Q
Q=a * (1/b)
とかける。ところで関数
f(x)=(1/x)-b
は、f(x)=0のときx=1/bとなる
⇒このxをつかえばa * (1/b)なる計算ができる
⇒割り算はf(x)=0となるxを見つけるという問題に帰着できる

※Newton-Raphson法
x_i+1 = x_i – (f(x_i)/f'(x_i))
により現在のx_iより、x_iの補正量を計算させて収束させる
f(x)=(1/x)-b
f'(x)=1/x^2
から
x_i+1 = x_i * (2-b*x_i)

⇒２から引く＝２の歩数＝各ビット反転し＋１
⇒＋１の誤差は小さいので、各ビットの否定だけの実装が多い

※繰り返し毎に有効ビット数は２倍となる
⇒最初の値はROMなどで表引きで与える

⇒単精度の除算性能はRadix-4のSRT法の方が有利

＿◇Goldschmidt法

☆RAM

◆RAMセル

※トランジスタよりも配線の方が面積を食う
⇒記憶セルのサイズは水平と垂直の配線の本数で決まる
⇒ポート数が多くなるとポート数の二乗にほぼ比例する。

※シングルエンドビット線方式
差動ビット線とくらべると同時書き込みに制限があるが、読み出しは平行して行える

※レジスタファイルのポート数が多くなるとR/Wの速度も遅くなる
⇒周波数を上げにくくなる

☆Disk

◆ディスクアクセス時間

【例】
平均シーク時間：15ms、
回転速度：3600rpm、転送速度：10MB/s
4Kバイトアクセスするときに要する平均時間。

平均回転待ち時間 ＝ 0.5 / ( 3600 / 60 ) ＝ 8.3ms
転送時間 ＝ 4Kバイト / 10Mバイト ＝ 0.4ms
全体の時間 ＝ 平均シーク時間 ＋ 平均回転待ち時間 ＋ 転送時間
＝ 15 ＋8.3 ＋ 0.4 ＝ 23.7ms

※ディスクアクセスに要する時間の大半は、シーク時間と回転待ち時間によるもの

◎ディスクアレイ
ハードディスクを複数台用意し、並列にアクセスすることによって高速化する方法。しかし、単純ディスクアレイには装置の増加にしたがって信頼性が低下するという欠点があった。

複数のディスクにデータを巡回的に配置し、高速性を向上する方法をストライピングと呼ぶ。また、別の方法として、複数のディスクに同じデータを書き込むことによって信頼性を向上する方法をミラーリングと呼ぶ。

◆RAID
Redundant Array of Inexpensive Disks

①RAID0
ストライピング=ブロック、故障検出=ディスク固有、データ復元=無、冗長ディスク構成=無

②RAID1
ミラードディスク
２台のハードディスクに同じデータを書き込む（ミラーリング）
ストライピング=無、故障検出=ディスク固有、データ復元=２重化、冗長ディスク構成=固定

③RAID2
ハミング符号によるエラー訂正符号を書き込む
ストライピング=ビット、故障検出=ハミングコード、データ復元=ハミングコード、冗長ディスク構成=固定

※ストライピング＝分割

④RAID3
パリティを用いたエラー訂正符号を書き込む
冗長デスクにより１台のドライブに障害発生しても処理を継続できる
ストライピング=ビット、故障検出=ディスク固有、データ復元=パリティ、冗長ディスク構成=固定

⑤RAID4
セクタ単位でインターリーブ
パリティを１台のディスクに書き込む
ストライピング=ブロック、故障検出=ディスク固有、データ復元=パリティ、冗長ディスク構成=固定

⑥RAID5
セクタ単位でインターリーブ
パリティを等分分散
冗長デスクにより１台のドライブに障害発生しても処理を継続できる
ストライピング=ブロック、故障検出=ディスク固有、データ復元=パリティ、冗長ディスク構成=分散

☆中間コード

◆Javaバイトコード

ドキュメントに書かれた命令順に１番から順にOPコードが割り振られている

☆パイプライン処理

pipelining

異なる命令の異なるステップをオーバラップさせる

◎基礎

◆プロセッサの実行時間の三要素

①プログラムを実行するのに必要な命令の数

②１個の命令を実行するのに必要な平均プロセッサ・サイクル数

③プロセッサのサイクル時間

◆スカラプロセッサ

※スカラプロセッサ
１度に高々１個の命令しか実行しないプロセッサ

◆パイプラインステージ

パイプラインステージ間で何倍も処理時間に差があるような場合は、長い処理を複数段のステージに分割して、各パイプラインステージの処理時間を均一とする

あるいは、
長いステージの回路を一部、短いステージに移動させる

※処理時間
ステージを区切るFFのクロックエッジから出力までの遅延時間Td
処理を行う論理回路の遅延時間Talu
FFのセットアップ時間Tsetup
クロックズレのTskew

これに対してサイクルタイムTcycleが

Tcyles≧Td+Talu+Tsetup+Tskew
⇒Td, Tsetup, Tskewは、各ステージにもれなく含まれる

※パイプライン段数増
⇒段数だけの異なる命令が実行されている
⇒構造的ハザード、データハザードの発生の可能性高まる
⇒分岐によるコントロールハザードのサイクルも増

※パイプライン段数２倍で周波数２倍弱を達成すると
⇒FF２倍、周波数２倍弱で、クロックの電力消費は４倍弱

＿◇データ依存性のチェック

※レジスタエントリのバリッドビッド

＿◇実行資源の予約

先のサイクルの状況をサイクルの進行とともに管理する必要がある
⇒シフトレジスタで予約表を作るとよい

※各資源ごとに予約表が必要。

◆パイプラインの制御

制御を行う情報も処理するデータとともにパイプラインを流していく

※例外処理はパイプライン処理でバグの出やすい部分なので注意

＿◇遅延分岐
Delayed Branch

※投機実行を行う場合にはかえって問題となることもある

＿◇ＰＣ

どのパイプラインステージの命令を指すべきか

＿◇例外処理

パイプライン処理の「例外」部分なので、バグが出やすい。

◎ハザード条件、依存性

◆データ依存

＿◇真のデータ依存関係
true data dependency

※ある命令が先行命令の実行結果を使用する場合、当該命令はその先行命令に対して真のデータ依存関係を持つ

⇒一般に、命令の実行に必要な全ての入力データが得られるまで当該命令の実行は送らされる

＿◇主記憶装置命令競合によるデータ依存
ストア命令の書込み先が、次に実行する命令である場合、ストア命令の書込み完了まで命令の読出しを待たねばならない。
⇒一種の依存関係、競合ともいえる

※命令を変更した直後の命令実行
⇒命令キャッシュの無効化
⇒該当アドレスから主記憶装置データの読出し
⇒命令レジスタへの書込みと命令キャッシュへの書込み処理時間が必要

＿◇主記憶装置データ競合によるデータ依存
書換えデータを直後の数命令で使う場合は、古いデータが先読みされている可能性がある
⇒論理的な依存関係⇒競合ともいえる

＿◇レジスタデータ競合によるデータ依存
レジスタデータ競合には次の3つがある

①書込み後の読出し　（RAW）
②読出し後の書込み　（WAR）
③書込み後の書込み　（WAW）

⇒読出しどうしでは情報に変化がないので競合は起こらない
⇒逐次的なパイプライン制御で生じるのは
書込み後の読出し競合のみ
※他の2つは命令の並列処理や追越し制御を行うときに起こりえる。

＿◇レジスタバイパス

※Forwarding

演算器の出力を演算器の入力に直接入力するためのバイパスマルチプレクサが必要

※バイパスを利用するためには、レジスタ状態にValid/Invalid以外に、Bypass0,Bypass1などの状態も必要。
⇒レジスタ読み出しステージで、それら状態に応じたレジスタあるいはFFからのデータを読み出すようにバイパスマルチプレクサを切り替える
⇒あるいはバイパスに読み出し対象のオペランドレジスタへの書き込みデータが乗っていることを別途チェックして切り替える

◆制御依存

＿◇手続き依存関係
procedural dependency

ある分岐命令に後続する命令を当該分岐命令に対して手続き依存関係を有するという

⇒１個の命令の１回の実行は、それ以前の各分岐命令に対して手続き依存関係を持つ

※ＣＩＳＣプロセッサの可変長デコードは一種の手続き依存関係でもある

＿◇分岐命令の待ちによる制御依存

※分岐命令
分岐先命令が入っている主記憶装置アドレスの計算
⇒そのアドレスから命令を読み出す
⇒この間の待ちが必要となる

※コントロールハザード
⇒データハザードに比べて性能ロスが大きい

※高速化
分岐方向が決まる前に、分岐しない場合の実行されるべき先の命令の実行を初めてしまう（書き込みまではしない）
⇒分岐が決まったら、命令を中断してパイプラインフラッシュ

※ディレードブランチ
Delayed Branch
⇒分岐命令の次の命令は無条件に実行、分岐はその先から
⇒Delayスロットの有効利用率は50～60%
⇒投機実行を行うプロセッサではかえってじゃまになる

＿◇プログラムカウンタ
パイプラインステージのどこを指すべきか
⇒プログラムカウンタをステージ毎に分離すべき場合がある

＿◇割込みの状態設定による制御依存

※割込み
⇒命令の実行を完了
⇒それ以降の命令実行を停止
⇒制御装置に命令実行管理を預ける
⇒割込み制御は、プログラムカウンタPCの値を主記憶装置に書込み、制御レジスタの内容などを退避したあと、主記憶装置の所定番地からアドレスを取り込んでその番地へ分岐する

※分岐命令の途中での例外発生には注意

＿◇制御命令の状態設定による制御依存

※制御レジスタを設定する命令では、割込みによる初期設定と同様なプロセッサ内部状態の初期設定が必要となる

◆資源依存

＿◇資源競合
resourece conflict

同一のハードウエア資源を２命令以上が同時に使用する場合に生じる
⇒競合する命令の一方の実行遅らせれば解消できる
⇒一般に競合の解消には、余分なサイクルが必要
⇒パイプラインストール（Stall)
⇒パイプラインバブル（Bubble)

※資源競合は資源の多重化によって解消できる

※処理に時間がかかる資源の場合、必要な機能ユニットをパイプライン化しても資源競合を軽減できる
⇒完全な多重化より安上がり

※構造的ハザート Structural Hazard

＿◇演算回路の競合による資源依存
同一演算回路を前後の命令で使う場合
⇒先の命令が演算回路を複数クロック使用する場合
⇒後の命令は、前の命令の実行完了を待つ

＿◇キャッシュミスヒットによる資源依存
命令キャッシュやデータキャッシュのデータがないときに主記憶装置へその内容を取りに行く
⇒この間、キャッシュアクセスは主記憶装置データが到着するまで待ち状態となる

＿◇アドレス変換テーブルミスヒットによる資源依存
仮想記憶方式では、ページテーブルやセグメントテーブルによって仮想空間アドレスから実空間アドレスへと動的にアドレス変換が行われる
⇒TLBはアドレステーブル情報を保持するキャッシュメモリであり、このバッファにアドレス情報がないTLBミスのときには待ちが生ずる。

☆並列性とプログラム

並列処理 parallel processing
多数のプロセッサが互いに通信 communicate
協調 cooperate
⇒大きな問題を再分割して超高速に解決

並列計算機 parallel processor

….◎Flynnによる計算機構の分類
◎Flynnによる計算機構の分類

※計算機構内に存在するデータの流れ(data stream)と命令の流れ(instruction stream)に注目する

{Single, Multiple} Instruction Stream
x
{Single, Multiple} Data Stream

組み合わせの頭文字をとって

SISD 通常ノイマン型
MISD
SIMD 単一命令ストリーム、複数データストリーム
MIMD 複数命令ストリーム、複数データストリーム

◎SIMDアーキテクチャ

SIMD型並列計算機
１個のコントロールユニット（control unit, CU)
N個の同一プロセッサ(processing element, PE)
相互結合網

◆並列計算機の構成

※並列計算機は多数の基本プロセッサ(element processor)、メモリ(memory)、それらを接続する相互結合網(interconnetion network)から構成される

＿◇基本プロセッサ

①並列計算機を構成するプロセッサ数を並列計算機の並列度と呼ぶ
②粒度(granularity)とは並列処理の単位
⇒基本プロセッサの規模、性能、能力、複雑度
⇒粒度の大小
粗粒度(coarse grain)
中粒度(medium grain)
細粒度(fine grain)

＿◇メモリ

※共有メモリ
shared memory
⇒複数個のプロセッサで共有
⇒バスへのアクセス頻度をさげる⇒キャッシュメモリ
⇒共有メモリへの読み書きによりプロセッサ間通信を行う
⇒共有メモリを持つ並列計算機＝密結合マルチプロセッサ
tightly coupled

※疎結合マルチコンピュータ
loosely coupled
⇒プロセッサ毎に分散してメモリを持つ並列計算機
⇒各プロセッサのもつメモリ＝局所メモリ
local memory
⇒共有メモリに対する場合は分散メモリとも呼ばれる
distributed memory

※局所メモリのサイズ
各プロセッサの粒度で変わる

※プロセッサ間通信
⇒メッセージパシング(message passing)

＿◇相互結合網
interconnection network

※評価基準
①埋め込み可能性(embeddability)、他のトポロジーの
②拡張容易性：スケーラビリティ(scalability)
③通信直径(communication diameter)
④耐故障性(fault tolerance)
⑤２分割幅(bisection width)

※代表的な単一段(single stage)結合網
１次元メッシュ結合
２次元メッシュ結合
木結合
ハイパーキューブ結合
シャフル・エクスチェンジ結合

※多段結合網(multi-state network)
クロスバー
ベースレアイン
オメガ網

＿◇同期式と非同期式

※同期式
synchronous
全プロセッサが共通のグローバルクロックのもとで動作
⇒一般的SIMD

※非同期式
asynchronous
グローバルクロックが存在しない
⇒一般的MIMD

＿◇ルータ
分散メモリアーキテクチャで用いられるプロセッサ間データ通信装置

＿◇並列プログラミング環境
parallel programming envionment

 

◆SIMDの概要

CU：プログラムカウンタをもち、ノイマン型に近い構成をとる
⇒すべてのPEと直接接続
⇒ブロードキャスト
各PE:単純な制御回路、演算装置、局所メモリ、データレジスタ、アドレスレジスタ、状態レジスタなどをもつ
局所メモリ⇒CUからブロードキャストされたものを記憶
アドレスレジスタ⇒各PEのアドレス
状態レジスタ⇒各PEの活性/不活性(active/inactive)状態保持
⇒ブロードキャスト命令に付与されるマスクにより活性/不活性制御

※lock-step-operation
全てのプロセッサが共通のグローバルクロックにより同期して動作

※アドレスマスク
ブロードキャストされる命令がどのプロセッサ上で実行されるべきかCUが指示
⇒計算開始前に決まる
⇒パラレル・ソーティング、ハイパーキューブ上でのアルゴリズム記述に多様

※データ・コンディショナル・マスク
⇒プロセッサのもつ個々の局所情報にもとづく
⇒データ条件による処理

◆細粒度SIMDと中粒度MIMDの比較

SIMD MIMD
制御 プログラムカウンタ１ 各プログラムカウンタ
動作 同期 非同期
粒度 細粒度 中粒度
応用分野 特定用途 汎用
スケーラビリティ 大規模 中規模
負荷分散 不必要 必要
ルータ 必要 必要
アルゴリズム設計 比較的容易 困難
アルゴリズム解析 容易 困難
検証性 比較的容易 困難
実行再現性 存在 保障されない

◆並列処理の記述

＿◇パラレルコンパイラを用いる方法
parallel compiler

自動並列化ソフトウエア

※源流
ベクトル型スパコン向けベクトル化コンパイラ
⇒同様な発想⇒逐次プログラムを並列計算機用のパラレルコードに自動変換する
⇒プロセッサ数が少ない特定のアーキテクチャでは成功

＿◇ユーザが並列処理を陽にプログラムとして記述する方法

※並列プログラミング言語
並列に処理される部分をユーザが陽に記述するための言語
Occam, Ada, Modula
CやFORTRANなどに並列制御コードを追加したもの
“in parallel”
doループ、forループなどを並列に実行

＿◇並列アルゴリズム
parallel algorithm

並列計算機上で動作するアルゴリズム
⇒並列アルゴリズムの設計はターゲットとする並列計算機アーキテクチャを考慮にいれなければならない
⇒並列アルゴリズムの性能は、アーキテクチャの影響が非常に大きい
⇒アーキテクチャが異なれば、アルゴリズムは一般に使用できないか性能悪くなる

＿◇並列アルゴリズムの性能評価指標

※ｎは入力データサイズ

①並列時間計算量T(n)
parallel time complexity
⇒並列アルゴリズムの動作開始から終了までの経過時間
プロセッサ内部の処理時間
プロセッサ間通信に要する時間
データの入出力に要する時間

※速度向上比(speed-up ratio) s
最高逐次アルゴリズムの最悪時実行時間
ｓ＝－－－－－－－－－－－－－－－－－－
並列アルゴリズムの最悪時実行時間

ｓ＝Ｔ１／Ｔｎ
Ｔ１は１個の計算機で処理に要する時間
Ｔｎはｎ個のプロセッサからなる並列計算機で処理に要する時間
一般にｓ≦ｎ
⇒速度向上比が大きくなればなるほどアルゴリズムは良いといえる

※線形速度向上(lenear speed-up)
s=n
⇒実際はｎの増大にｓがついていけない
負荷分散のアンバランス
プロセッサ間通信のオーバヘッド

②使用プロセッサ数S(n)
サイズｎの問題を解くときに使用したプロセッサ数

※空間計算量
(space complexity)
一般にS(n)=n

※プロセッサ利用率u
u=s/n
一般に0≦u≦1

※並列時間計算量と使用プロセッサ数との積をその並列アルゴリズムのコストと呼ぶ

※効率(efficiency)
並列アルゴリズムのコスト＝並列時間計算量ｘプロセッサ数
最速逐次型アルゴリズムの最悪実行時間
効率＝－－－－－－－－－－－－－－－－－－
並列アルリズムのコスト
⇒効率は１に近いほどよい

＿◇計算量の定義と記法
逐次計算機の場合と同様

①上界(upper bound)
O(f(n))
ある問題Pを解くアルゴリズムAを考える。
Aが答えを出すまでにf(n)時間かかるとき、Aの性能はO(f(n))という
f(n)は小さい方が良い

②下界(lower bound)
Ω(f(n))
問題Pを解くにはどんなアルゴリズムをつかってもf(n)時間がかかると分かったとき
PはΩ(f(n))であるという
f(n)は問題の難しさをとらえている

③最適(tight bound)
θ(f(n))
問題Pを解くO(f(n))のアルゴリズムAが得られ
かつPがΩ(f(n))であるとわかったとき
Aはθ(f(n))であるという
⇒Aは最適アルゴリズム

◎並列処理を考える指針

ジェイムス・レインダース
Think Parallel
並列処理を考える指針

1. 1. Think Parallel
      並列性を見出してすべての問題解決を試みる
   2. 抽象化を使用してプログラミングする
      並列化を実現するコードを記述することに注力する
      スレッドやプロセッサの制御に気をとられるのは避ける
   3. スレッドではなくタスクをプログラミングする
      マッピングはコード上で分離する
      管理が自動的に行われるような抽象化を利用する
   4. 並列処理をオフにできるオプションを付けて設計する
      デバッグ用
   5. ロックの使用を避ける
      ロックはプログラムの動作を遅くし、スケーラビリティを損ね、バグを混入させる原因となる。ロックは最後の手段。
   6. 並列化に役立つツールやライブラリを使用
      スレッドフリーなライブラリを求める
   7. スケーラブル・メモリ・アロケーターを使う
   8. 作業負荷に応じてスケーリングするよう設計する

◎マルチプロセス、マルチスレッド

1.  ◆マルチプロセス

＿◇タイムシェアリング

◆マルチスレッド

※スレッド間でメモリ空間を共有する
⇒スレッド間のデータのやりとりはプロセス間通信やメモリ共有を必要としない

◆並行と並列

＿◇並行処理
concurrent
同時に複数の動作や処理が行われている状態を示す
⇒複数の処理がバラバラの内容であってもよい

＿◇並列処理
parallel
同時に関係や類似のある複数の動作や処理が行われている
⇒一つの計算結果を複数スレッドで求める処理など

※並列処理とは、多数のプロセッサが互いに通信し協調しながら、一つの巨大なサイズの問題を再分割して超高速に解決する手法

◎並列化のアプローチ

◆データ並列性
data parallelism

計算の異なる部分の間で双方向の通信がほとんど必要ないか、あったとしても一方向のデータは他方向のデータに依存しないという性質

※データ並列化
処理の対象となるデータ⇒分割⇒複数の実行主体に分担させて並列処理
⇒複数の実行主体の処理内容は一緒
⇒分割されたデータは相互に依存関係なしが前提

※典型的実装例
ループによる処理⇒複数のスレッドに分割

※リダクション（縮約）演算
多数のデータ組から１つの値を求める演算

◆タスク並列化

異なる処理を別々の実行主体に割り付けて並列に処理

※パイプライン処理
⇒データを得るタイミングを調節することで、お互いのデータ依存性の問題をクリア

◆排他制御

データ参照、更新の順序の制御の問題

＿◇ロックによる同期

※ロック、アンロック

※ロックによる処理結果の整合性の保証を同期とよぶ

＿◇data race

データにアクセスするタイミングが問題で、並列処理のパフォーマンス、あるいは処理結果の整合性の統一に影響が懸念される状態

◎マシン並列性

◆資源の多重化

＿◇整数ＡＬＵの多重化
もっとも実行頻度が高い整数ＡＬＵ命令
⇒全体の４０～５０％
⇒ＡＬＵを２重化する効果を発揮するためにはレジスタ名前替えなどの対策が必要
⇒命令ウインドウサイズ１６～３２のときアウトオブオーダー発行が最大の効果を発揮する

＿◇ロード・ストア・ユニットの二重化
それほど大きくないわりに、２重化のために必要とされるリソースが大きい（デュアルポートメモリ、２重のヒット検出回路などが必要）

◆アウト・オブ・オーダー発行

＿◇命令ウインドウ
命令デコーダと機能ユニットとの間のバッファ
命令発行部はウインドウ内の命令を検索し、機能ユニットに発行可能な適切な命令を選択する

①集中ウインドウ方式
各機能ユニット宛の命令すべてを１個の共通ウインドウにバッファリングする

②リザベーション・ステーション
reservation station
各機能ユニットの入力段にバッファする
１個の命令を対応する１個の機能ユニットに対して発行

※実行ユニットは平均の命令実行速度より高いピーク命令発行速度に対応する必要がある。
⇒集中ウインドウ方式でフラットにしてしまうとオペランドデータの転送に要するリソースが大
⇒リザベーション・ステーション方式であれば、平均の命令実行速度で分配できればよく、オペランドデータの転送に要するリソースを減らすことができる

＿◇リザベーション・ステーションでの実行

①デコーダは１サイクルあたり複数の命令を同時にデコード
⇒命令とソースオペランドを対応する機能ユニットのリザベーションステーションに入れる
②依存関係が無く、機能ユニットが空いていれば当該命令を発行する
③依存関係が在るか、機能ユニットがビジーならば、②の状態になるまで待たされる
④複数同時に発行可能となった場合は、命令列で最も早く現れた命令を選択する

 

◆レジスタ名前替え

※逆依存関係と出力依存関係を消去できる

＿◇リオーダ・バッファ
reorder buffer

⇒各機能ユニットに持たせる
⇒命令デコード段階で１エントリを割り当てる
⇒デスティネーション・レジスタ番号とエントリを対応づけることで名前替えする
⇒タグを格納する
⇒後続命令がソースオペランドを得ようとする場合
名前替えされたエントリの内容（オペランド値）かタグを得る

※リオーダバッファ
一種の連想メモリ(content-addressable memory)
⇒エントリ内に書き込まれたレジスタ番号を使ってエントリを識別（連想検索: associative lookup)
⇒リオーダバッファとレジスタファイルのアクセスは並行
⇒値がまだ確定していなければタグが返る
⇒同一のデスティネーション・レジスタを指す複数のエントリがあた場合は、最新のエントリの値が返る。
⇒古いエントリも保存しないと正確な割り込みは保証できない。
⇒１サイクルあたり複数個の結果受け取り、複数個のリタイア可能で、１サイクルでデコードされる命令すべてにソースオペランドを供給できる読み出しポート

※実行結果
⇒リオーダバッファに書き込まれると同時に、タグを含むリザベーションステーションにも書き込まれる

＿◇リタイア
レジスタ・ファイルへの書き戻し
本来の命令の順番で行われる
割り込みや例外に対してイン・オーダー完了状態を保証する

＿◇マッピングテーブルを使う別案
mapping table

◆ロード／ストア

※真の依存関係、逆依存関係、出力依存関係が存在するが、その数はレジスタ上に比べて大きくない
⇒ロード／ストア命令は全命令の２５～３０％
⇒１命令で１メモリロケーション
⇒メモリ空間の大きさ

※ロード命令とストア命令が競合した場合
⇒ストア命令をストア・バッファ(store buffer)で待たせる

※ストア命令の実行順
ロード命令を含む全ての先行命令が完了してから実行
⇒データキャッシュでのプロセッサのイン・オーダー状態の保証のため（ストア命令間での出力依存は存在しない）（ストア命令はロード命令を追い越せないので逆依存関係も存在しない）
⇒ロード命令は先行ストア命令をバイパスできるので、ロード命令は先行ストア命令からデータを得る必要がある
⇒仮想アドレスでの比較（１仮想アドレス＝１物理アドレス前提）
⇒後続ロード命令のロードアドレスがストアバッファ内のストア命令のストアアドレスと一致すれば、ストア・バッファから値を得る
⇒先行するストア命令のストアアドレスが未計算であれば、依存関係を持つ可能性があるのでロードはできない

※ロード命令は他のロード命令に対してプログラム順にアクセスする（アウトオブオーダにしてもほとんど性能向上しないが、順序を守ることでリザベーションステーションの構成を簡単にできるため）

---

☆Superscalar

１個のプログラム・カウンタで指し示される命令を先頭とする複数の命令を同時にフェッチおよびデコードし、そして、機能ユニットに対して複数命令を同時に発行する

※１命令当たりの平均サイクル数を減らすために、命令並列性を利用

※データ並列性がほとんど無いような「汎用」アプリケーションに適する

◎並列性

◆ハザード条件の影響

＿◇０命令発行、１命令発行、レイテンシ
先行する命令にたいするデータ依存関係と、先行する命令のレイテンシのために新たな命令の開始ができない
⇒０命令発行
zero-issue

１命令しか発行できない（後続がこんどは新たに発行される１命令に依存するため）
⇒１命令発行
single-issue

※レイテンシ
latency
命令の実行に要する時間
⇒スーパースカラ・プロセッサの効果を大きく左右する

◆命令並列性とマシン並列性

命令並列性とマシン並列性の適切なバランスを達成すること

＿◇命令並列性
instruction parallelism

同時に実行できる平均命令数を表す指標
⇒真の依存関係の数、他の命令に対する分岐命令の相対的な数によって決まる
⇒レイテンシが真の依存関係の数を決める

＿◇マシン並列性
machine parallelism

命令レベルの並列性をプロセッサが利用できる能力尺度

◆命令発行

＿◇命令発行
instruction issue

命令をプロセッサの機能ユニットで実行開始する過程

※命令発行ポリシー
instruction issue policy
命令発行に用いるプロトコル
⇒プロセッサの先見（lookahead)能力を決定
⇒命令の実行順序と完了順序を決定
⇒命令のフェッチ順序、実行順序、状態変更順序をバラバラにすることで高性能化

＿◇インオーダー発行、インオーダー完了

※インオーダ発行
in-order issue
プログラムの順序通りに命令発行
⇒命令デコードが止まるのは
デコードした命令が資源競合
未完了の命令に対して依存関係が存在する

※インオーダ完了
in-order completion
プログラムの順序通りに結果書き込み
⇒単純だが長い命令が性能を制限する

＿◇インオーダー発行、アウトオブオーダー完了

※アウトオブオーダー完了
out-of-order comletion
⇒もともとレイテンシの長い命令の性能向上のために導入
⇒全ての機能ユニットのパイプラインステージが埋まるまで命令を発行できる
⇒命令発行が止まるのは
機能ユニットの競合
発行された命令が未完了の結果に依存している場合
出力依存関係

※結果の書き戻し時に結果書き込みバスおよびレジスタファイル書き込みポートの調停を行う必要がある

※アウト・オブ・オーダ完了
⇒例外とその再開が難しい
⇒正確な割り込み（例外）をサポートするか否か

＿◇アウトオブオーダ発行、アウトオブオーダ完了

※命令ウインドウ
instruction window

命令は元のプログラム順序とほとんど無関係に命令ウインドウから発行される

※アウトオブオーダ発行
インオーダ同様、資源競合と依存関係が消滅した時点で命令を発行する
⇒発行の対象となる命令を数多くすることで並列実行可能な命令を発見しやすくする

＿◇正確な割り込み（例外）
precise interrupt
※正確な例外
precise exception

⇒インオーダー完了と同様な再開状態を備えること

＿◇出力依存関係
output dependency

実行時間の長い先行する命令によって、後続の命令が先に生成した値を上書きしてしまうような矛盾関係

※アウトオブオーダー完了で発生する

＿◇逆依存関係
antidependency
先行命令が使う値を後続命令が破壊してしまう

※アウトオブオーダー完了で発生する

◆メモリ競合とレジスタリネーミング

＿◇命令間依存関係

①真の依存関係
WAR(write-after-read)

②逆依存関係
RAW(read-after-write)

③出力依存関係
WAW(write-after-write)

※WARは情報の流れによるが、RAWとWAWはメモリ競合(storage conflict)

＿◇レジスタリネーミング
register renaming

実行時に動的に割り当てられる付加的なレジスタ
⇒レジスタへの代入が新しいインスタンスを生成
⇒その値が他の値にとって変わられ、その値に対する未完了参照がなくなればインスタンス消滅

◆レイテンシ

＿◇発行レイテンシ
issue latency
ある機能ユニットに命令を発行した後、次の命令を当該機能ユニットに発行できるまでの最小サイクル時間

＿◇結果レイテンシ
result latency
結果を生成するのに機能ユニットが要するサイクル数

◆命令フェッチ

分岐命令を実行するまでその先をフェッチしないようなアプローチで汎用アプリケーションを実行した場合、手続き依存関係の存在のため並列実行を行うのに十分な数の命令数が得られない。
⇒実行ユニットをビジーに保ち続けられるだけの命令を供給しなければならない
⇒シーケンシャルな命令列については所望の命令バンド幅を供給することは容易
⇒分岐予測と幅の広い命令デコーダが必要
⇒命令のミスアライメントの影響も大きい

※命令キャッシュとデコーダの間のパスは多くのプロセッサにとってクリティカルパスである

※複数パスの並列実行(IBM370/168, IBM3033)はハードウエアコスト大

＿◇命令ランとランレングス
命令ラン(instruction run)
ラン・レングス(run length)

※汎用プログラム⇒命令ランは非常に短い
⇒分岐命令の割合、総実行命令数の２０％（RISC)
⇒平均ラン・レングスは約６命令

＿◇分岐遅延
branch delay

分岐命令をデコードしてから、最初の分岐先命令をデコードするまでの時間
⇒スーパスカラ・プロセッサでは分岐遅延が相対的に長くなる。

※遅延分岐命令はスーパスカラでは有効ではない

＿◇分岐予測

※ハードウエア分岐予測
hardware branch-prediction
⇒分岐遅延のペナルティに対処できる

※ソフトウエア分岐予測
software branch-prediction
⇒分岐予測情報をプログラム中に含ませる
⇒分岐予測の精度はハードウエアと同等程度だが、ハードウエア分岐予測のように分岐遅延ペナルティを隠蔽できない

※分岐先バッファ(branch-target buffer)
命令アドレスによりアクセス
分岐命令ならば、分岐予測結果と分岐先アドレスを出力

※命令キャッシュに分岐予測情報を持たせてもよい
⇒フェッチャで処理
通常のアドレスタグ以外に
後続インデックス(successor index)
次にフェッチすべきキャッシュブロックと命令の先頭を示す
命令フェッチャが参照する
分岐ブロックインデックス(branch block index)
当該ブロックでの分岐命令の位置
⇒分岐命令以降は実行されないと予測
命令デコーダが有効な命令を求めるために使用
通常どおり最初は命令キャッシュにエントリ
⇒分岐不成立と予測しておく
⇒分岐予測ミスによりインデックスを変更
⇒分岐予測の場合は、後続インデックスで示されるエントリのアドレスタグから求める

※プロシージャからのリターン（無条件の間接分岐）
⇒分岐先情報が書き換えられている可能性がある
⇒しかし何度も繰り返し呼ばれるならば一定期間変化しないので分岐予測する価値はある

※分岐予測の精度は、分岐ヒストリ情報の容量を増加させることで向上できる

※未解決、未実行の分岐命令を多数保持することになる
⇒未解決の分岐命令を４個まで許すと最高性能が得られる

※分岐予測が正しければ、どんな順序で分岐命令を実行しても、同時に複数個実行しても問題ない。しかし、分岐予測が間違っていたら当該分岐命令の後続命令の結果は全て無効化されなければならない。

※分岐命令の分岐先アドレスの計算はデコードステージで済ませるべき、また、命令フェッチ機構で分岐命令を識別させるべき
⇒１サイクルあたり複数の分岐命令をデコードするよりも、分岐遅延を小さくする方が重要。また、分岐予測をつかって命令フェッチャは遅延なしに命令ランをフェッチできなければならない

＿◇命令の整列化
命令のミスアライメントには幅の広いデコーダの方が対処できる

※命令のマージ
分岐予測によりメイレイフェッチャが複数の命令ランを１つにマージすること

◆例外回復

※投機的実行(speculative execution)
例外(exception)が発生しないという仮定のもとで命令をフェッチおよび発行する。先行命令の実行完了を待たずに命令実行を進める。
⇒例外発生時に
回復(recovery)および再開(restart)の機構が必要

＿◇ステート情報

◆命令デコーダ

※４命令デコーダは２命令デコーダよりも命令の並び方に影響を受けにくい。

※レジスタファイルポートの調停
⇒デコーダはレジスタ名を優先順位をつけて指定する必要がある
⇒デコードしたレジスタの最初のものからレジスタファイルのポートを割り当てる。全ポートが塞がってしまったらそのデコードはストール。

◆競合解消のための調停回路

２段回路
ｍ＊ｎ＾３
のオーダーのゲート数が必要

ｍ：競合している資源の数
ｎ：競合者の数

ｍ＊ｎ：競合者および対応資源にイネーブル信号を生成するため
ｎ＾２：競合者間の調停

⇒優先順位付け回路は一般に遅い

---

☆VLIWプロセッサ

Very-Long-Instruction-word
超長形式機械命令プロセッサ

※命令数を削減するために、命令並列性を利用

１個の命令内に１個以上の並列に動作可能なオペレーションを指定
⇒オペレーションは互いに独立
⇒複数オペレーションのエンコードに多くのビットを使う

※ソフトウエアが命令並列性を検出してコンパクションを行うので、ハードウエアで命令並列性を検出する必要がない
⇒命令並列性は、プロセッサのインプリに依存するレイテンシで決定されるので、バイナリレベルで互換性を保持するのが難しい。
⇒命令並列度が低いコード部では多くの命令が無駄になる

---

☆スーパーパイプライン・プロセッサ

※サイクル時間の短縮のために命令並列性を利用

命令パイプラインの各ステージをサブステージに分割
⇒サイクル時間を短縮する

※スーパーパイプライン度
degree of superpipelining
元のパイプライン・ステージに対するサブステージの数

※真の依存関係があれば、性能低下はスーパースカラより大きい。
⇒同程度のハードウエアコストであれば、スーパースカラの方が資源競合を発生しやすい。

※パイプライン・ラッチのオーバヘッド
⇒スーパーパイプライン度が高まるほど厳しくなる

※クロックスキュー
clock skew
⇒スキューを小さく保ちつつ、クロックサイクルを上げねばならずデバイス技術に依存する

※資源を多重化するコストが高く、スキューを制御しやすい場合に、スーパパイプラインが適する

---

☆ベクトル・プロセッサ

※データ並列性を利用する
data parallelism

---

☆共有バス・マルチプロセッサ

※データ並列性を利用する
data parallelism

---

☆メッシュ・アーキテクチャ

mesh architecture

並列計算モデル
①多数のプロセッサを整数格子点上に配置
②近傍プロセッサのみを接続

※MCC mech-connected computer
網目結合計算機

※自然科学の多くの問題がメッシュ構造に写像可能
※規則正しいグリッド構造がVLSI化に適する

※通信直径 D
communication diameter
⇒アレイ上における任意の２つのプロセッサ間の最小コミュニケーション・リング数の最大値
⇒ｎ個のプロセッサからなる１次元MCC D=n-1
⇒サイズnxnの2次元MCC, D=2n-2
⇒ボトルネックの克服のため、網目構造に第２の通信路を付与するアーキテクチャ
ピラミッド結合
木結合
網目木結合
共通グローバルバス

◆MCCファミリー

＿◇セルラオートマトン
各プロセッサは有限オートマトン
並列入出力
同期処理

＿◇イテラティブアレイ
各プロセッサは有限オートマトン
逐次的入出力
同期処理

＿◇シストリックアレイ
各プロセッサは実数の四則演算などを定数時間で実行可能
逐次的入出力
同期処理
パイプライン処理

＿◇木マシン、ピラミッドマシン
ローカルバス結合に、木結合、プラミッド結合などの補助結合を付加
同期処理

＿◇網目結合MIMD
非同期動作
メッセージパシング

 

---

☆シストリック・アレイ

systolic array

※データ並列性を利用する
data parallelism

“And the smooth stream in smoother number flows: by Alexander Pope”

※Kung & Leisersonにより提案された
⇒systolic=心臓収縮の
⇒心臓に見立てた単純なプロセッサを多数個規則的に結合してできる並列計算システム
⇒個々のプロセッサは周辺のプロセッサにデータを送り出し、かつ受け取る作業を規則的に繰り返す

＿◇シストリックアレイの特徴

①アレイへのデータの入出力＝逐次的
②アレイ上での処理＝並列
③動作はパイプライン化＝重畳的(overlapped)

※サブルーチン・パッケージに代わる特定用途向けハードウエア付加装置として考案された。

＿◇代表的なシストリックアレイの基本結合形態

①一次元ＳＡ
②正方形ＳＡ
③三角形ＳＡ
④木結合ＳＡ
⑤六角形ＳＡ

＿◇１次元シストリックアレイＭ

      ┌────┐　┌─┐　┌─┐　┌─┐　┌─┐　┌─┐       │┌──┐│　│Ｃ│　│Ｃ│　│Ｃ│　│Ｃ│　│Ｃ│ ────→┤│Ｒ１││　│１│　│２│　│３│　│４│　│５│ ホスト　　│└──┘├─┤　├─┤　├─┤　├─┤　├─┤　├─┤├─ 計算機　　│┌──┐│　│　│　│　│　│　│　│　│　│　│ ────←┤│Ｒ０││　│　│　│　│　│　│　│　│　│　│       │└──┘│　│　│　│　│　│　│　│　│　│　│       └────┘　└─┘　└─┘　└─┘　└─┘　└─┘ バッファＢ

※左端のバッファでのみ入出力を行う
※各セルＣｉ（ｉ≧１）は左右に隣接するセルとのみ直接接続
⇒局所結合
⇒隣接セルを近傍とよぶ
⇒単位時間で直接通信できるのは近傍内のセルに限定される⇒局所通信
（local communication)
⇒グローバル線
電源
接地
クロック

※特徴

①均一構造
すべてのセルは単純、同一構造
各セルは有限個のレジスタを持つ
実数の４則演算なども１ステップで実行可能な場合もある

②静止状態
t=0、すべてのセル上のレジスタは空＝静止状態
⇒静止状態のセル、近傍も静止状態なら静止状態を保つ

③逐次的入出力
処理に必要なデータはホスト計算機上に
ホストからバッファBのR1レジスタ経由で入力される
⇒入力のレート：入力パイプラインインタバル(input pipeline interval)
入力は、入力パイプラインインタバルに従って与えられる
出力も逐次的にアレイからR0を経由して出力
⇒出力パイプラインインタバル

④同期モデル
時刻tにおけるCiのレジスタRjの内容をR_t_j(i)と示す
t≧0, i≧1, j≧1
各セルは同期して動作する
⇒意味のある計算は非静止状態のセルで行われる
⇒非静止状態のセル集合は動作開始と同時に右方向に広がりt=nのときにｎ個が非静止
S_t_i={R_t_j(i)|1≦j≦k}
B_t={R_t_1(B), R_t_0(B)}

⑤計算量
※並列時間計算量(parallel time complexity) T(n)
最初の入力a1を与えてから最後の出力$が得られるまでのステップ数
（nは入力サイズ）

※応答時間(response time) R(n)
最初の入力を与えてから最初の出力b1が得られるまでの時間

※周期時間(period time) P(n)
異なるデータセットを入力するまでにホスト計算機が待機すべき時間

※空間計算量(space complexity) S(n)
使用するセル数

T(n),R(n),P(n),S(n)は解くべき問題とアーキテクチャ、アルゴリズムに依存する
⇒望ましいのは
T(n)=c*n 線形時間
R(n)=O(1)
P(n)=O(1)⇒スループット高い
S(n)=O(n)

※時間空間図式(time-space diagram)
水平方向にセル空間
垂直方向に時間軸

＿◇シストリック点対検査アルゴリズム

※点対検査問題
ｎ個の点要素a1,a2,…,anが与えられる。このとき自分自身との点対を除くすべての点対(a1,a2),(a1,a3),(a1,a4)…(a1,an),(a2,a1),…,(a2,an),…,(an,an-1)を列挙せよ

⇒点対の総数n(n-1)個⇒ノイマン型逐次計算機O(n^2)時間を要する
⇒ソーティング、計算幾何学、信号・画像処理などの並列アルゴリズムを１次元ＳＡ上で設計する場合に基本的

※アルゴリズム

---

☆ＳＩＭＤプロセッサ

※データ並列性を利用する
data parallelism

◆細粒度SIMD

コントローラ一つ
＿◇メッシュ結合

※通信直径が大きい

※グローバルバス、木結合、ピラミッド結合などのネットワークと併用される

＿◇MCC
mesh connected computer

＿◇ハイパーキューブ結合

※効率的なアルゴリズム設計が可能
⇒インプリが高価
⇒Thinking Machinesのコネクションマシン

---

☆MIMDプロセッサ

◆中粒度MIMD

プロセッサ数と同数のコントローラを持つ

---

☆ハイパーキューブ

※データ並列性を利用する
data parallelism

---

☆データフロー

※データ並列性を利用する
data parallelism

---

☆DSP

◆DSPの特徴

①ハードウエア乗算器or積和演算器、ALU、シフタ（スケーリング、汎用）をもつ。ＡＬＵと積和演算も並行動作

②ハーバードアーキテクチャでマルチバス、プログラムフェッチとデータオペランドの転送を並列におこなう

③アドレス計算部は独立

④ゼロ・オーバヘッド・ループ

⑤パイプライン

⑥オンチップメモリ、オンチップペリフェラル

◆TIPS

※１６ビット２個並列→ビタビアルゴリズムの顔ｓ区

---

☆画像認識向けマルチコアプロセッサ

◆PVP
Pipelined Vision Processor

Blackfinシリーズ固定小数点DSPに搭載の画像認識用プロセッサ

◆Visconti
東芝

＿◇Visconti2

◆CEVA

＿◇MM3101

◆eyeSight Mobile Technologies

---

Hardware

☆組み立て

＿◇放熱
放熱グリース

---

Reference

独習Java 第3版　ジョセフ・オニール著
トップスタジオ訳、SHOEISHA

http://www.unicode.org/

新ANSI C言語辞典 平林雅英著、技術評論社

コードリーディング　Diomidis Spinellis
トップスタジオ訳、毎日コミュニケーションズ

増補改定版 Java言語で学ぶデザインパターン入門
マルチスレッド編 結城浩著、ソフトバンク 2006/3/31

Elementary functions: algorithms and implementation, Jean-Michel Muller. – 2nd ed., 2006, Birkhauser

http://www.dspguru.com/info/faqs/cordic.htm

プログラミング・テクニック 多治見寿和 ASCII 2003/12/2

ビューティフルコード B.Kernighan他 Andy Oram, Greg Wilson編 久野禎子、久野靖訳 オライリー・ジャパン 2008/4/22

http://www9.plala.or.jp/sgwr-t/c/sec11-2.html

ケプラー予想 ジョージ・Ｇ・スピーロ 青木訳 新潮社 2005/4/30

Portraits of Success, Carolyn Caddes, Tioga publishing, 1986

Linux カーネル解析入門 平田豊 2006/1/20 工学社

岩波講座 応用数学11 確率的方法とシミュレーション 伏見正則著 岩波書店 1994/3/24

ソフトウエアの20世紀 2000/12/1 長谷川裕行 翔泳社

最新ファイル形式と文字コードの基本と仕組み 2003/2/1 若林 秀和システム

やさしくわかる３Ｄ入門 2000/3/20 山中修 日本実業出版

コンピュータ科学の基礎 2003/1/10 河村一樹 ナツメ社

http://www.eb.waseda.ac.jp/murata/masako.yoshimura/openhouse/method11.php

http://www.yobology.info/text/viterbi/viterbi.htm

http://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/dynamic/dynamic.htm

土木工学における数値解析/基礎編 1974/11/10 土木学会編 サイエンス社

スーパースカラ・プロセッサ 1994/8/15 日経BP出版センター マイク・ジョンソン著 村上監訳

DSPのハードウエアと信号処理の実際 1999/11/10 CQ出版

コンピュータ設計の基礎 Hisa Ando 2010/11/20 毎日コミュニケーションズ

数値計算の基礎 森他 1993/5/14 岩波書店

超並列計算機アーキテクチャとそのアルゴリズム　梅尾博司　1991/11/10 共立出版

http://akita-nct.jp/yamamoto/lecture/2006/5E/Linear_eauations/concrete_relax_html/node2.html

岩波講座 応用数学15 離散最適化法とアルゴリズム　茨木俊秀 1993/4/15 岩波書店