読者です 読者をやめる 読者になる 読者になる

kivantium活動日記

プログラムを使っていろいろやります

浮動小数点数の加減算

この記事はkivantium Advent Calendarの15日目です。

このページは移動しました。https://kivantium.net/cpu-faddを見てください。

バレルシフタ

この記事はkivantium Advent Calendarの14日目です。

昨日浮動小数点数の乗算をやりました。
今日は浮動小数点数の加減算をするのに必要な部品であるバレルシフタを紹介します。

シフトの使い道

シフト演算は高速なのでビット演算テクニックとしてよく使われますが、ハードウェア実装は意外と難しいです。

1bitのシフトならシフトレジスタを用意して隣に移動すればよいのですが、任意のbit数シフトするにはバレルシフタと呼ばれる回路が必要になります。

浮動小数点数の加減算を行う際にもシフトが必要です。浮動小数点数仮数部は最上位が1になるように格納されているため、指数部が異なる場合は小数点の位置を合わせる必要があります。
1.01 \times 2^01.11\times 2^{-3}を足し算するためには

1.01
0.00111
--------
1.011111

のようにずらさないといけません。

そこでバレルシフタの実装を見ていきます。

バレルシフタの作り方

バレルシフタは、入力がシフトされる数字Aと何bitシフトするかを表すS、出力がシフトした数字Bという形の回路です。
中身はマルチプレクサをたくさん集めて作られています。

Aが8bitの場合、Sは0~7なので3bitとなります。
このとき、

tmp1 = A         if S[2] == 0
     = A << 4    if S[2] == 1
tmp2 = tmp1      if S[1] == 0
     = tmp1 << 2 if S[1] == 1
B    = tmp2      if S[0] == 0
     = tmp2 << 1 if S[0] == 1

となるようにマルチプレクサをつなげば2進数に対応した分だけシフトされるので目的の回路が作れます。

実際にはVerilogのシフト演算子を使えば任意のシフトができるのでおそらく内部でバレルシフタを合成しているのだと思いますが、本当かどうかは分かりません。

きんモザ・ごちうさ聖地巡礼記

この記事はまんがタイムきらら Advent Calendar 2016きんいろモザイク Advent Calendar 2016ごちうさ Advent Calendar 2016の14日目です。(さすがに欲張りすぎた)

9月にきんいろモザイクの聖地であるイギリスと、ご注文はうさぎですか?の聖地とされるフランスに行ってきたので、そのときの写真と今後行く人向けに役立つかもしれない情報を書いていこうと思います。行った場所は以下の地図に書いてあります。(ルートはGoogleマップの制約で全て徒歩になっていますがもちろん鉄道や車を併用しました)

また、旅行中のツイートは
togetter.com
にまとめてあるので、より詳しい記録を見たい人は参照してください。

きんいろモザイク聖地巡礼

きんいろモザイク聖地巡礼をするために行くべき場所は

  • Heathrow空港(1期1話で忍が使った空港)
  • Paddington駅(1期1話で忍が電車に乗った駅)
  • Kemble駅(1期1話で忍が降りた駅)
  • Fosse Farmhouse(アリスの実家)
  • Cirencester(1期1話でアリスと忍が観光していた場所)
  • Bibury(1期EDで5人が訪れていた場所)
  • ロンドンの観光名所(2期EDで5人がロンドンを巡っていた)

などたくさんあります。それぞれを確実に巡るためにはそれなりの計画が必要となります。以下僕たちが行ったルートと写真を掲載していきます。後の人たちの参考になれば幸いです。

Heathrow空港→Paddington駅→ロンドン観光(1泊)→Kemble駅→Bibury→Cirencester→Fosse Farmhouse(1泊)という順に回りました。
その後はChippenham駅→King's Cross駅→フランスという感じの移動でした。

Heathrow空港

1期1話で忍が降りた空港です。忍が降りたのは第五ターミナルなのですがここを利用しているのはBritish Airwaysという航空会社のみらしく、それ以外の会社を使った場合は別のターミナルに降りることになります。幸いなことに空港内には地下鉄が走っていてターミナル内は無料で移動することができました。


第五ターミナル内に入ることはできませんが以下のような写真を撮ることができます。

## Paddington駅とロンドン観光
Heathrow空港からPaddington駅への移動は地下鉄、Heathrow Connect、Heathrow Expressなどの方法があります。Oyster cardというプリペイドカードを使うとCappingというシステムが適用されて最大額の£8.60(条件によって異なる)で地下鉄とバスなら指定区間内をいくらでも移動できるシステムがあるのでうまく活用すると交通費を抑えることができます。僕たちは地下鉄を利用してPaddington駅まで移動しました。

1期1話で写っていた場所は探すのが難しいですが、2期EDはごく普通の観光名所なのでバスや地下鉄を駆使して移動すれば回れます。

Oxford Street(1期1話冒頭でちらっと写る)


いい感じのパブ

ピカデリーサーカス(1期1話の冒頭でカメラがぐるっと回るシーン)

ビッグベン(2期EDで忍たちがアリスたちを探していた場所、エイプリルフール回でも出てきた)

ロンドン塔(2期EDで陽子がアリスを抱っこしていた場所)

バッキンガム宮殿(2期EDで5人が兵隊さんごっこをしていた場所。もちろん中には入れない)

Paddington駅からKemble駅へ

イギリスの鉄道は時間帯によって値段がだいぶ異なり、混雑する時間を避けると安くなります。駅員と時間と相談して安いチケットを選ぶといいでしょう。

また、チケットを買ってもどのプラットフォームに電車が来るのかは直前まで分からないので案内板をよく見て表示されたらそのホームまで急いで移動する必要があります。

Kemble駅に行くためにSwindon駅で乗り換えました。何番ホームに乗りかえるのか分からないのでGoogleの経路検索が役立ちました。

Kemble駅


忍が降りた側にバスが来ると思って待っていたのですが、バスが来るのは反対側でした。1日に4本くらいしか来ないので事前によく調べないと大変なことになります。Kemble駅周辺のマップは http://www.nationalrail.co.uk/posters/KEM.pdf などを参考にしてください。バスの時間は https://www.rome2rio.com/s/Kemble/Bibury を見るといいでしょう。
バスを逃して完全敗北した僕たちはタクシーでBiburyに向かいました。

Biburyにて

Biburyは1期EDのカットに使われている場所がたくさんあります。

1期1話でカレンがアリスに変な人形をあげている場所

一期1話の別れのシーン

その横のアリスの家があるはずの場所は公衆トイレになっている

1期EDに出てくる公衆電話と椅子

Biburyはネットが一切入らないので地図を印刷して、行くべき場所をオフラインで確認できるようにしておくのがおすすめです。

BiburyからCirencesterに行くバスは1日に数本しか来ません。アイスクリーム屋の向かい側の道に来るのですがバス停はなくバスが来たら手を挙げて止める必要があります。このバスは停留所名を読み上げてくれることもないのでGPSをにらんで自分のいる位置を把握して適切なタイミングで降りる必要がありました。難易度高いです。

バスが来る場所の向かいにあるアイス屋。"Probably the Best Icecream in the World!"というだけあって確かにおいしかったです。

Cirencesterにて

Cirencesterも1期1話でアリスと忍が遊びに来た場所です。

教会

本屋

サブウェイ

CirencesterからFosse Farmhouseに向かったのですが、公共交通機関を使うと3時間かかるのでおとなしくタクシーを使いました。
Fosse Farmhouseへは鉄道でSwindonからChippenhamに行き、バスでCastle Combeへ行ってから歩くというルートが一番安そうなのですが、そうするとBiburyなどへのアクセスが悪くなるので最適なルートは分かりません。

Fosse Farmhouseにて

アリスの実家のモデルとなったB&Bです。

メールで予約すると忍の部屋とアリスの部屋のどちらがいいか聞かれます。忍の部屋に泊まったのですが、アリスの部屋も見せてもらえました。

Fosse Farmhouse

アリスの寝室

忍の寝室 西明日香さんのサイン入りシノ2号が置いてあります。

浴室

1Fのゲストハウスにはファンがおいていった大量のグッズがありました。

別料金になりますが、頼めば夕食やスコーンも出してもらえるので興味のある人は頼むとよいでしょう。

Castle Combeにて

Fosse Farmhouseの近くにはイギリスで一番美しい村といわれるCastle Combeがあります。スタッフから地図をもらったので行ってみました。

「大きな鉄の門」この右側を通る

こういう道なき道を進む

「木でできた踏み越し」通ってはいけない雰囲気を醸し出しているが、この門を開けて進まないと迷う(体験談)

街並みはこんな感じ



行ったのが朝早すぎてどの店も開いていなかったのでちょっと見てすぐに戻りました。

Fosse Farmhouseでタクシーを呼んでもらった後、Chippenham駅に行き、Oxford大学を見学したのち鉄道でKing's Cross駅に行きました。
隣接しているSt. Pacros駅からユーロスターに乗ってパリ北駅へ。

ご注文はうさぎですか?聖地巡礼

ごちうさの舞台となっている街のモデルはコルマール旧市街を中心とする東フランス一帯とされています。そのためイギリスの次はフランスに向かいました。

ユーロスターでフランスに入ってパリ観光をした後、パリ東駅からTGVコルマールに向かいました。


コルマール駅から目的の旧市街までは少し歩きます。

個性的な街並みが広がっています。

うさぎの看板の店もありました。

アニメイトTVによるとラビットハウスのモデルとされる店

※窓です

2期EDで写っていた橋

コルマールは基本フランス語ですがメニューなどは英語・ドイツ語が併記されていることが多いです。ホテルの人には英語が通じましたが、パン屋で全く英語が伝わらない(How much?すらダメ)店があったので若干のフランス語知識はあったほうがよさそうです。

甘兎庵のモデルと言われる建物はRiquewihrにあります。Riquewihrにはコルマール駅を出て右側のバス停からの106というバスを使っていきました。時刻表はこのサイトの106を見てください(PDFへのリンク

甘兎庵とされる建物

ここも朝早く行くとどこも開いていなかったのでお昼くらいに行くのがいいかもしれません。

Riquewihrを見た後はTGVでパリに戻って、飛行機で日本に帰ってきました。

あってよかったアプリ

成田空港でWi-Fiを借りて持っていきましたが、ところどころ通じないことがありました。インターネットから遮断されても戦える環境を整備しておくことが重要です。

Google翻訳アプリ

辞書データを入れておけばオフラインでも翻訳ができる上にOCR機能などがついているので非常に便利です。フランス語→英語の変換は精度が高いのでおすすめです。

Navitime Transit UK・FR

Navitimeの海外旅行用乗り換え検索アプリです。これのよいところはオフラインでも乗り換え検索ができることです。駅の路線図を見てもどういう接続なのか分からないことが多いので、アプリがあると助かります。

舞台めぐり

きんいろモザイクの聖地の場所が登録されているので巡礼がはかどります。ネットにつながっていないとデータが確認できない・チェックインできない、若干場所がずれているなどの不便な点はあります。

Rome2rioはルート検索のときに非常に役立ちました。

聖地巡礼という理由で普通はあまり行かない外国のマイナー都市を観光するのは不便もありますが、楽しい経験になることでしょう。良い旅行を!

浮動小数点数の乗算

この記事はkivantium Advent Calendarの13日目です。

昨日浮動小数点数のフォーマットについて説明しました。
今日は浮動小数点数の乗算をやります。

仕組み

浮動小数点数仮数と指数で表されるので

  • 指数の和を取る
  • 仮数の積を取る
  • 仮数を丸めてフォーマットを整える

をやれば計算できることになります。

入力を正規化数のみの計算に絞って、最近接丸めを採用したコードは以下のようになります。

module testbench;
  logic clk, start;
  logic [31:0] a, b, c;
  int i;
  fmul fm(.a(a), .b(b), .c(c));

  initial begin
    a = 32'b01000000010010001111010111000011; // 3.14
    b = 32'b00111101110011001100110011001101; // 0.1
    start = 1'b1;
    clk = 1'b0;
    for(i=0; i<5; i=i+1) begin
      clk = 1'b1; #10; clk=1'b0; #10;
    end
    $display("%b %b %b", c[31], c[30:23], c[22:0]);
    $finish;
  end
endmodule

module fmul(
  input [31:0] a, b,
  output logic [31:0] c
);
  logic c_sign;
  logic [7:0] c_exp;
  logic [23:0] c_frac;
  assign c = {c_sign, c_exp, c_frac[22:0]};

  logic [8:0] c_exp_0, c_exp_1;
  logic [47:0] c_frac_0; // 48bit = 2 * 24bit
  logic [23:0] c_frac_1; // 24bit

  logic guard_bit, round_bit, sticky_bit;
  logic guard_bit1, round_bit1, sticky_bit1;


  always @* begin
    c_sign = a[31] ^ b[31];
    c_exp_0 = a[30:23] + b[30:23];
    c_frac_0 = {1'b1, a[22:0]} * {1'b1, b[22:0]};
    guard_bit = c_frac_0[23];
    round_bit = c_frac_0[22];
    sticky_bit = |c_frac_0[21:0];

    if(c_frac_0[47] == 1'b1 || &c_frac[46:24] == 1'b1) begin
      c_frac_1 = c_frac_0[46:23];
      c_exp_1 = c_exp_0 + 1;
      sticky_bit1 = sticky_bit;
      round_bit1 = round_bit;
    end else begin
      c_frac_1 = c_frac_0[47:24];
      c_exp_1 = c_exp_0 + 1;
      sticky_bit1 = sticky_bit | round_bit;
      round_bit1 = guard_bit;
    end

    if(c_exp_1 < 127) begin
      c_exp = {9{1'b0}};
    end else begin
      c_exp = c_exp_0 - 127;
    end

    if(round_bit1 == 1'b1 && (sticky_bit1 == 1'b1 || c_frac_1[0] == 1'b1)) begin
      c_frac = c_frac_1 + 1;
    end else begin
      c_frac = c_frac_1;
    end
  end
endmodule

出力は

0 01111101 01000001100010010011100

となって昨日のプログラムで求めた3.14*0.1の答えと一致しました。

丸めを適当にやっていて、Inf, NaNにも対応していないひどいコードなので後日ちゃんとしたものを書きます。

浮動小数点数

この記事はkivantium Advent Calendarの12日目です。

昨日までで整数の四則演算のやり方を紹介しました。
今日からは浮動小数点数の使い方を紹介します。

IEEE-754

浮動小数点数の表し方はコンピュータの歴史の中で何種類かありましたが、現在主流となっているのはIEEE-754と呼ばれるフォーマットです。

特によく使われるのは単精度と倍精度の2種類です。
どちらも符号部・指数部・仮数部からなり、精度によって大きさが異なります。
有効数字を保つために科学では$1.234\times10^3$のような表し方をしますが、それを2進数で行ったのがこのIEEE-754です。

単精度

単精度は32bitからなり、以下のようなフォーマットを持ちます。

  • 符号部 (sign) は0が正、1が負を表します。
  • 指数部 (exponent) は127をゼロとするバイアス付きの値として表され、-128から127を表します。
  • 仮数部 (fraction)は精度を上げるために最上位の1を省略した2進数として表します。 1.f_1f_2f_3\dots
  • このフォーマットで表される値は (-1)^{\text{sign}}(1+\sum _{{i=1}}^{{23}}\ f_{{i}}2^{{-i}})\times 2^{{(\text{exponent}-127)}}となります。

倍精度

倍精度も基本は単精度と同じです。指数部のバイアスは1023に変わるので、表す値は (-1)^{\text{sign}}(1+\sum _{{i=1}}^{{52}}\ f_{{i}}2^{{-i}})\times 2^{{(\text{exponent}-1023)}}となります。

非正規化数

浮動小数点数では正規化数(さっきの式で表される数)の範囲を超えたときのためにいくつか正規化数以外の数の表現方法が用意されています。単精度の場合は

種類 指数部 仮数
ゼロ 0 0
非正規化数 0 0以外
正規化数 1〜254 任意
無限大 255 0
NaN 255 0以外

となります。

  • 非正規化数は正規化数で表される範囲よりも0に近いときに使われ、 (-1)^{\text{sign}}(\sum _{{i=1}}^{{23}}\ f_{{i}}2^{{-i}})\times 2^{{(-126)}}を表します。
  • 無限大はとても大きい数を表すときに使います。
  • NaNはNot a Numberの意味で0÷0のような不正な演算の結果として使われることがあります。

ビット表現を覗いてみる

ビット表現を確認する方法として、共用体を使う方法があります。
これは共用体の実装依存の挙動を利用しているほか、floatが32bitであることを前提としているなどお行儀の良くないコードなのですが多くの環境で動くようです。

#include <stdio.h>
#include <stdint.h>

union Float2Int {
    uint32_t int_value;
    float float_value;
};

int main (int argc, char *argv[]) {
    union Float2Int a;
    a.float_value = 1.25;
    for (int i=31; i>=0; i--) {
        printf("%d", (a.int_value >> i) & 1);
        if(i==31 || i==23) printf(" ");
    }
    printf("\n");
    printf("exponent: %d\n", (a.int_value >> 23) & 0xff);
}

僕の環境では

0 01111111 0100000000000000000000
exponent: 127

と出力されました。
2進数での`1.01`は10進数の1.25に対応するのでIEEE-754フォーマットに従って格納されていそうだと分かります。

次回は浮動小数点数同士の足し算をします。

除算器 その2

この記事はkivantium Advent Calendarの11日目です。

昨日は回復法を用いた除算器の設計を説明しました。回復法は符号付き整数を扱えないという欠点がありました。今日はこれを克服する非回復法を説明します。

非回復法(引き放し法)

回復法では引き算の結果にキャリーが発生するかどうかを見て、レジスタに元の値を入れるか減算器の出力を入れるかを決定していました。非回復法ではキャリーが発生した場合もそのまま減算器の出力を入れ、次の桁では加算を行います。回復法における「D桁目は引かずにD-1桁目で引く」という動作は、非回復法で「D桁目で引きD-1桁目で足す」という操作に相当します。どちらも結果として同じ数を引いていることが分かると思います。
符号なし整数で10÷3を行う例を示します

    (+1)(-1)(+1)
011)-------
    01010
   -011   <- 同符号なので引く
    ----
    11110 <- -2 (=10-3x2^2)
    +011  <- 異符号なので足す
    -----
    00100 <- 4 (=10-3x2^2+3x2^1)
     -011 <- 同符号なので引く
   ----
    00001 <- 1 (=10-3x2^2+3x2^1-1)

(+1)(-1)(+1)は3に相当するので3余り1という正しい演算結果が出ることが分かりました。

このように各商がbitが±1の値を持つ形で与えられるのを元に戻すコストなどが必要ですが、符号付きでも扱えるというメリットが大きいです。

実装は厳しいので今日のところは省略します‥‥

SRT法

今まで説明した方法による割り算の実行には被除数bit数と同じサイクルが必要になります。これを減らすには数bitずつ一気に割ることでサイクル数を減らすことが考えられます。2bitずつ割る方法をRadix-4、4bitずつ割る方法をRadix-16と呼びます。

引き戻し法が商を{0, 1}から選び、引き放し法が{-1, 1}から選んでいたのは2進数で1bitずつ見ていたからでした。複数bitずつ見た時にも候補を瞬時に確定することができれば1サイクルで複数bit分の商を確定することができます。
このアイデアに基づいて数bitずつ割り算を実行するのがSRT法です。
Radix-4の場合には商の候補として{-2, -1, 0, 1, 2}が存在しますが、詳細に分析すると部分剰余の上位5bitと除数の上位3bitのみから決定することができ、引き放し法と同じ要領で正しい2進数として復元すれば商を被除数のbit数の1/2のサイクルで求めることができます。

PentiumまではRadix-4が、Core2シリーズからはRadix-16が利用されているようです。

(図は http://www.intel.com/content/dam/www/public/us/en/documents/research/2008-vol12-iss-3-intel-technology-journal.pdf p.188より)

SRT法は商を決定するテーブルの決定が難しく、Pentium浮動小数点演算のバグはこのテーブルの埋め方に問題があったのが原因とされています。

Intelがバグらせるものを締め切りまでのあと10分で書けるとは思えないので実装は省略します……。

次回は引き算の繰り返しではない別の割り算アプローチを見ていきます。

除算器 その1

この記事はkivantium Advent Calendarの10日目です

昨日までで四則演算のうち3つが揃ったので今日からは最難関の割り算をやります

回復法(引き戻し法)

話を簡単にするため、まずは符号なし整数の割り算を考えます。
割り算の場合も基本の考え方は筆算です。
10進数の場合は

   14
7)-----
  100
   7
  ---
   30
   28
  ----
    2

のように、商として取れる最大の値を推測して掛け算し、その値を引いていくことで計算を進めます。
筆算で一番難しいのは「最大の値」を推測することですが、2進数の場合は可能性が0と1しかないので注目している部分が除数より大きいか小さいかだけ調べれば商が決まります。大小比較は引き算してみてキャリーが発生しなければ大きい、発生したら小さいと確定するので、キャリーのNOTがその桁の商になります。そこでA÷Bを計算する回路として次のような設計が考えられます。


  • 被除数の左側にBと同じbit数の0をつめたシフトレジスタを用意し、左から順にBのbit数ずつ取り出して、減算器に入れます。
  • キャリーの否定をシフトレジスタの右側の入力として商とします。
  • キャリーが0(=引くことができる)のときは差が、キャリーが1(=引くことができない)のときは元の値がシフトレジスタの左側に入るようにします。
  • 1サイクルごとにシフトレジスタを左にシフトしていけば、Aのbit数と同じサイクル数でシフトレジスタで元Aがあった位置に商が入ります。

しかし、この方法ではAのbit数と同じサイクル数が必要となるため時間がかかります。また、符号なし整数の除算にも対応できません。そこで次回はこれを克服する非回復法について説明します。

今日は帰宅即おふとんしてたので内容が短いです‥‥