ARMの設計（デザイン）

Oral History of Sophie Wilson（ http://www.computerhistory.org/collections/catalog/102746190 ）から、ARMの設計（デザイン）に関することのメモ

（主に、6502との関係について）

  • ARM以前のほとんどのマシンで6502を使用しており、6502での経験はあった
  • しかし、他のプロセッサを載せるボード（8ビット機時代によくあったもの）で他のプロセッサも使っていた
  • それでも6502が良い、と思っていた。メモリアクセスの帯域を有効に使っている、という所から（他のプロセッサではそこのバランスに問題があった）
  • （ビデオプロセッサが画面表示に間に合ってアクセスするためには、メモリアクセスにある程度の帯域幅が必要であり、その性能をメインプロセッサも生かせるのが、当時の「バランスの良い」デザイン、ということになるのだろう）
  • ARMの設計（デザイン）については、このバスアクセス帯域について以外には、（命令セット等）6502の影響があったというようには読み取れない

ARMの成功要因は何だろうか？（きしもとの私見による分析を含む）

  • 明解で単純な目標の設定、例えば
  • 6502の代替となること
    • (それまでのマシンでは機械語プログラミング等のテクニックの駆使が必要だったことを、高水準言語でできるように）
  • 「IPM PC 互換機の洪水」に対抗すること
  • スローガン「MIPS for the masses」（この「MIPS」は、プロセッサというよりは（それもあるが）性能のことを指している）。当時、他のRISCプロセッサは、ワークステーションを指向していて高価だった
  • 前述の「他のプロセッサを載せるボード」として、まず動くベンチとなるシステムを作ったこと
  • むやみに大きなプロセッサにしなかったこと（最初のプロセッサは25000トランジスタ）もあって、最初からちゃんと動くものを作ったこと。インタビュー中では、ナショセミのNS320xxがいつまでもまともに動かなかったことと比較している

Macr055発表の反省

プロシンでいただいたコメントとかに対するメモ

再帰的なマクロの例が欲しい

（言い訳: 「マクロに展開されるマクロ」がちゃんと再帰的に扱えれば、あとはそのマクロが自分自身でも同じことだ、と思っていたのですが）質疑応答のかなり最後のほうで、「再帰（によるループ）ができても、ifelseのようなことができないと、再帰すると止まらなくなるので結局使えない。一方ifelseがあればそれと再帰でいろいろできる」というように回答したのだけども、ifelseを紹介したついでとして何か簡単な「再帰的なマクロ」の例があればよかった（多分それで時間もバランスが取れたかもしれない）

プッシュバックの様子とかが可視化されるデモみたいなので説明が欲しい

（デモ用途に限らず、マクロプログラミング（特にデバッグ）に有効だろうと考えていて、インタフェイスを考えてるところ）

予稿のリファレンスの番号がズレている

後から確認したら、「LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.」が出てないか注意しましょう、というオチでした（参照番号が［?］になったりはしていなかったので油断した）。

「m55_define」は長くてうっとうしい

（設計者の弁: ユーザが任意の名前を使えるよう、処理系組込みの名前は「予約名前空間」のようなイメージで全てプレフィクスを付けている）

「例えば def という名前にしたりはできないのか」ともコメントされたので簡単に検討したところ、現在の仕様では全く透過的にはできないことがわかり、定義ではなくエイリアスの機能があったほうが良いかも、と思ったのでその後で簡単に実装した（抜けとかあるかもしれないのでそのうちチェックしたらリポジトリを更新する予定）。

『ソフトウェア作法』は「さくほう」

と読むのだ、と訳者の先生ご本人がおっしゃっていた、とのコメントが。（両方を掛けている、とどこかで読んだ記憶があるんだけどなぁ……）

簡易回転計算

というツイートを見て、少し考えてみました。

角度が θ（以下、全てラジアン（弧度法）とする）で、ごく小さい（ θ ≒ 0 ）時、sin(θ) ≒ θ, cos(θ) ≒ 1 という近似もありますが、それとは少し違う感じです。

ピタゴラスの定理から sin2(θ) ＋ cos2(θ) ＝ 1 という関係がありますが、それを変形すると、互いに sin(θ) ＝ √( 1 ー cos2(θ) ), cos(θ) ＝ √( 1 ー sin2(θ) ) となりますので、それをちょっと考えてみます。すると次のように、cos の側から計算するとうまいこと変形できて、

√( 1 - (127/128)2 ) ＝ √( 1 - 16129/16384 ) ＝ √( 255/16384 ) ≒ ( 16/128 ) ＝ 1/8

のように、cosの側を基準にするとsinがわずかに大きくなっている近似と言えます。

ここでもう少し √( 1 - ((N-1)/N)2 ) について考えてみますと、

√( 1 - ((N-1)/N)2 ) ＝ √( 1 - (N-1)2/N2 )

　　　＝ √( 1 - (N2-2N+1)/N2 )

　　　＝ √( (N2-N2+2N-1)/N2 )

　　　＝ √( (2N-1)/N2 )

　　　＝ √(2N-1) / N

となりますので、2N（か、2N-1）がちょうど平方数になり、かつその平方根がNの約数、というような時にうまく上記の場合のような関係になることがわかります（例示の場合では N = 128、平方数が256=162）。

小さい方を考えてみますと、

N = 98 の時 97/98 と 1/7 （平方数が196=142）

N = 72 の時 71/72 と 1/6 （平方数が144=122）

といったようにして同じような関係は（誤差がだんだん大きくなりながらも）成立していますが、うまく2の冪の計算が8ビット機で使えるのは、1/8が出てくる上記の場合だけでしょう。

process reaperの実験

procctlという、プロセスの属性の一部を制御するAPIはFreeBSD 10で追加されたものですが、10.2 でそれに reaper facility と呼ばれている機能が追加されました。基本的な機能性はLinuxを参考に（Linuxでは prctl(2) というAPIです）、APIの設計はDragonflyBSDをベースにしており、manページもFreeBSDのものよりDragonflyのほうがわかりやくす書かれていますから、そちらを参考にすると良いでしょう。こちらのメイルから始まるスレッドもご参考ください https://lists.freebsd.org/pipermail/freebsd-arch/2014-December/016437.html 。

process reaperとは、子プロセスを作った場合の親プロセスのように、子プロセスが終了してゾンビになった後で、それに対応するwaitシステムコールを発行するプロセスのことを指します（ゾンビの魂(？)を、死神の鎌で刈る（reap）というイメージですね）。しかしこれらのAPIでは、Unixにおいて PID 1 の、通常は init が（あるいは近年のmacOSやLinuxでは違いますが）受け持つ、親プロセスが先に終了したようないわゆる orphan プロセスの親となり、それらが終了した後に wait を発行する、という権利と義務（？）について、init になり代わる、という機能を扱っています。

procctlという関数名ですが、manを見るときは同名のコマンドと被ってますので、man 2 procctlのようにして参照する必要があります。

次にサンプルコードを示します。

最後のほうでforkしていて、子プロセスのほうからはxtermを起動していますので（xtermが無い環境の方は適宜修正してお試しください）、そのxtermの中のシェルから sleep 100 & など適当に時間のかかるプロセスを起動しておいてからxtermを終了し、別のターミナルなどから ps -d などで確認すると、orphan プロセスの親になっているのが確認できるかと思います。

この機能、軽量コンテナのインスタンス毎のinitとして、とかに使うためのものだろうかとか思ってますが、どうなんでしょうか？　（あるいはデーモンマネジャのようなものを実装するのにも使えそうですが）

総和の計算は、なぜどのように難しいのか

プログラミング入門で、forループを使う例題としてよく出てきたりするように、総和計算は一見簡単そうですが、実はどのように難しいのか、という点を書いてみます。

まず、対象が整数であれば、大きな問題はありません。昔のようにintが16ビットの場合は、160*160=25600 でぎりぎりに近く 200*200=40000 ではもう 32767 を超えて溢れますから、intではなくlongを使うといった注意が、以前は必要だったというくらいでしょうか。

一方、対象が浮動小数点の総和は、場合によってはそう簡単ではありません。

場合として、まず、符号が正か負の片方だけであれば簡単です（代表的なものとしては内積など）。ソートして絶対値順に並べ、絶対値が小さい側の端2個のペアを取り出して、その和を計算し、結果をソートされている列の入るべき場所に挿入する、という操作を繰り返せば、基本的には問題はありません。

符号が両方ある場合は、正と負に振り分けてそれぞれ計算し、最後に差をとれば良い、と思うかもしれませんが、それではうまくない場合があります。極端な場合として、正側と負側のそれぞれの合計の絶対値が、2倍以内という近い値になってしまうかもしれません。そうなると桁落ちになります。

桁落ちという現象は、しばしば誤解が見られますが、それ自身は誤差を発生させません。正確には、絶対誤差は増えないが、値が小さくなるために相対誤差が（場合によっては文字通り「桁違いに」）大きくなる、という現象です。

そういったような場合、その絶対誤差は、そこに至るまでの計算過程での情報落ちによる誤差の積み残しの集積になっています。

直感的には、桁落ちの英語が「キャンセル」であるように、総和をとる対象中の、正負それぞれの絶対値の大きい値どうしでキャンセルできるものがあれば、それぞれでキャンセルすれば、「桁落ちは起きているが、情報は失われていない」という状態を維持できるので、それを繰り返してゆけば、正確な計算ができるはずです。

しかし、そのようなヒューリスティック的な計算をいちいちやっていては、総和計算に期待されるような Ｏ(n) に近い効率はとても実現できませんから、実際に提案されている手法は、何らかの方法で積み残しを全部残すであるとか、倍精度浮動小数点で表現可能な値の範囲全体をカバーする巨大な固定小数点で計算するとか、そういった手法になっています。

Ruby 2.4 の新機能, Array#sum

Ruby 2.4 で追加されている新機能のひとつに Array#sum があります。

（参: ドキュメントは http://ruby-doc.org/core-2.4.0/Array.html#method-i-sum ）

共立『アルゴリズム辞典』でも「総和計算」を立項しているように、情報落ち*1*2による「積み残し」が場合によっては著しいのが、対象が浮動小数点の時の総和計算の問題点です。

Array#sum は、Kahan summation algorithm（wikipedia:カハンの加算アルゴリズム、summation なので -総和アルゴリズム ないし -総和計算アルゴリズム、としたほうが訳としては正確）の改良版などの手法を実装しており、かなりの高精度な結果が得られます。

次のようなスクリプトで試してみると（実験に適した浮動小数点乱数を生成するため、拙作の RandomFloat を使用）、

# sum sample
require_relative 'random_float'

r_f = RandomFloat.new gt:1, lt:2**38

loop {
  arr = []
  (1000000).times {
    x = r_f.rand
    arr << x
    arr << -x
  }
  arr.shuffle!
  p arr.sum
}

そこそこ過酷な条件の総和計算ですが、次のように、ほぼ正確な結果を得られています（完全に正確ではない結果も、時折出ています）。

$ ruby-trunk -v sum_sample.rb
ruby 2.4.0p0 (2016-12-24 revision 57164) [x86_64-freebsd10.3]
0.0
0.0
0.0
0.0
0.0
-1.3322676295501878e-15
0.0
1.4654943925052066e-14
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0

Python の math.fsum との違い

ネットを捜すと、Python の math.fsum との関連で議論されていることがありますが、両者は基本的なコンセプトの点で別物です。今回実装された Array#sum は、あくまでも「高精度」であり、誤差が発生する可能性自体はあります。一方（現在の？）Python の math.fsum は、たとえて言うなら、入力や途中の計算を全て Rational に変換してから行い（実際の実装は異なります*3）、最後に浮動小数点に戻したような「正確」な結果を返すもので、前述で見たような誤差が発生することはありません。

もしそのような「正確な総和」が Ruby でどうしても必要な場合は、Rational を使ってユーザが実装すれば良いでしょう。そのような sum も（私見では、現在の sum と別の実装として、違う名前でメソッドを追加すべきだと思っています）もしかしたら今後実装されるかもしれません（関連するチケットは存在しています）。

*1:正負の要素があると、桁落ちが発生することもありますが、総和計算における主要な問題は桁落ちではありません。むしろ、正しく計画された桁落ちであれば情報は欠けないのであり、情報が積み残されて消えてしまった、という「結果が露呈する（ことがある）」のが、総和計算における桁落ちです。

*2:この桁落ちに関しては、以前のPythonのドキュメントの和訳に、原文には相当するcancellationという語は実のところ無いのですが、手違いにより「桁落ち」という表現があったため、誤解している人ももしかしたらいるかもしれません。

*3:色々な手法が提案されています。