赤げふの数学

数学の高校生 赤げふのBLOG

計算機のアルゴリズム上のコンパクト化

lobiでの解説。


アルゴリズムの観点からどういった高速化・コンパクト化(究極を目指すにあたり、同義ともいえる)を施せるかを見ていこうと思いく、アセンブリ言語がわかりやすい為使用する。
ざっくり解説挟みますが、分からない場合は個チャにて聞いてください(ここに貼ると文献の著作権に抵触する恐れがあるので)

アセンブリは、デカい命令が書いてある主記憶装置、演算を行う部分、演算結果を記憶する部分(以下Acc)、の3つに分かれる。命令はadd・subで番地指定した所の値をAccに加えたり引いたり

基本番地が低い所から命令を実行していく。
loadは指定した番地から値を引き出し、Accに上書き。
atoreは指定した番地にAccの値を上書き。
jumpは指定した番地から処理を始める。
jump minusはAccの値が負ならjumpと同じことをする。
本当は無いけど、面倒なのでmultipleとdivideという命令を追加し、それぞれ掛ける、割る の命令としました。

実際に乗除算のアルゴリズムを見ていきます。
乗除算のアルゴリズムなのになんで乗除算の命令が入っとんねん!ってなるかも知れませんが、

10進数で100を掛ける事は左に2回数字をずらし、0を付け加える操作と等価なのでまぁ書いてます。
あと除算はマシンの性能を規定して、一定の桁以下は切り捨てするとします。

図を見よ。

f:id:AkaGhef:20180426070302j:image

部分剰余や、部分和は筆算の途中に出てくる数字だなと思えばいいです(ニコッ)
乗算の都合上、除算は非回復型になるんですが、本筋と関係ないのでポイっ。
BとIを入れ替えたような構図になっています。これがパイプライン化(あとで話す)と組み合わさり、演算クロック(演算を行うリズム)をずらすだけで乗除算を切り替える事ができます。

実装の観点の高速化はまだワイがゴミクズでまだ出来てないので、完成したらちゃんと解説出そうと思います。数式バンバン出ます(笑)

パイプラインってこれのことだな(言い忘れた)
「Minecraft」の攻略「Minecraft 装置開発所+雑談」での「赤げふฅ^•ω•^ฅニャー」の投稿「ゲニキ理論(仮)の講義 ~パ...」 | Lobi

あとstopはstopするって事です(おい

一旦解説打ち切りです
衒学的ですいませんでしたm(*_ _)m