π 計算機

おじさん工房 TOP へ     APB−2 のページへ     サポート掲示板へ     APB-2 キット頒布中

■ページ履歴

2011/08/26 このページ公開
2011/09/16 π計算機完成
2012/02/15 COM ポート処理のバグフィックス


2011/08/26

以前より FPGA で CPU を作りたいと思っていました。 しかし、世の中にはすでにいろいろな人が CPU を作っていてどうも手を出す気になりませんでした。 FPGA 内部に作らなくても外付けしたほうが簡単だしというのもあります。

ふと見つけたページで TTL で CPU をつくっていてその最終目標が、πの計算となっているのに思わず反応してしまいました。 実は昔からπの計算には興味があり、bit 誌のナノピコ教室でのいろいろなπのatanの計算式に心動かされ、salamin-brent の相加相乗平均でπを計算するという方法にはコペルニクス的転回を感じました。 大学でのプログラム実習(Fortranです)ではπの計算をさせました。

そこで、π計算用の多倍長演算 CPU をつくるプロジェクトを開始しました。

コンピューターによる世界最初のπ計算は、1949年 ENIAC による 2041桁 70時間です。
その5年後の 1954年には IBM の NORC というスーパーコンピューターが 3090桁を 13分で計算しています。

今回は、この記録に挑戦したいと思います。 ざっと見積もると、数秒〜10数秒程度で3000桁の計算ができそうです。
まだ、π計算プログラムと、CPU のインストラクションセットの構想までですが...



■まずはπ計算プログラム


π計算ソースと DOS 実行ファイル 20110826 (ZIP 30KB)


配列は uint16 で格納するようになっていますので、このまま CPU の多倍長演算命令に置き換えられます。
Arctan のいろいろな公式、
   マチンの公式   π = 16*atan(1/5) - 4*atan(1/239)
   ストーマーの公式 π = 24*atan(1/8) + 8*atan(1/57) + 4*atan(1/239)
   ストーマーの公式 π = 176*atan(1/57) + 28*atan(1/239) - 48*atan(1/682) + 96*atan(1/12943)
   ガウスの公式   π = 48*atan(1/18) + 32*atan(1/57) - 20*atan(1/239)
   オイラーの公式  π = 4*atan(1/2) + 4*atan(1/3)
			
を使って最大10000桁まで計算できます。

ENIAC や NORC ではマチンの公式を使ったようです。



■CPU のインストラクションセット


上記π計算プログラムでπ計算に必要な多倍長演算がわかりましたのでそれをハードウェア実装する形でインストラクションセットを設計します。
ただしπの計算では多倍長どうしの掛け算、割算は使わなかったので、掛け算と割算は、多倍長 x uint16、多倍長 ÷ uint16、とします。(多倍長どうしの掛け算、割算はハードウェア実装が面倒というのもあります)


命令は16ビット長、符号なし演算のみ、としました。
アドレス空間は 16bit ですが、JMP、CALL で飛べるのは 4095 までです。 FPGA 内部のメモリーを使うので十分でしょう。

    Register :  r0..15    16bit  r14はSIZE、r15はSP
                size      16bit  多倍長精度指定レジスター
                PC        16bit  プログラムカウンター
  
    Flag :      Z         ゼロ
                C         キャリー
  
       OP(4) OPERAND(12)
     0 MOV   m(2) r(4)   m(2) r(4)
     1 ADD   m(2) r(4)   m(2) r(4)
     2 SUB   m(2) r(4)   m(2) r(4)
     3 CMP   m(2) r(4)   m(2) r(4)
     4 AND   m(2) r(4)   m(2) r(4)      とりあえず不要なので実装しない
     5 OR    m(2) r(4)   m(2) r(4)      とりあえず不要なので実装しない
     6 XOR   m(2) r(4)   m(2) r(4)      とりあえず不要なので実装しない
     7 NADD  m(2) r(4)   m(2) r(4)      とりあえず不要なので実装しない
     8 MUL   m(2) r(4)   m(2) r(4)      多倍長どうしの掛け算は実装しない
     9 DIV   m(2) r(4)   m(2) r(4)      多倍長どうしの割算は実装しない
    10
    11
    12 BRA   c(3)    offset(9)          条件 BRANCH  ±256
    12 PAUSE 100     xxxxxxxxx          一時停止(RUNコマンドを送ると次のアドレスから実行再開)
    13 JMP   adrs(12)                   0..4095
    14 CALL  adrs(12)                   0..4095
    15 RET   c(3) 0  xxxxxxxx           条件 RET
    15 PUSH    00x1  xxxx r(4)          レジスターを PUSH する
    15 POP     10x1  xxxx r(4)          レジスターを POP する
  
    以下複数PUSH/POP/RETは未実装
    15 PUSHL   0101  r7..0              最大8レジスター(対応ビットが1のレジスター)を PUSH する
    15 PUSHH   0111  r15..8              〃
    15 POPL    1101  r7..0              最大8レジスター(対応ビットが1のレジスター)を POP する
    15 POPH    1111  r15..5              〃
    15 RET   c(3) 0  r7..0              条件 POP & RET
  
    m : 00   レジスター直接   r
        01   レジスター間接   *r
        10   レジスターで示すアドレスからsize分が多倍長データ   r[size]
        11   即値   0..14 はレジスターフィールド、15..65535 は次のアドレス
  
    c : 000  always
        001  Z           ==0
        010  C           <0
        011  C or Z      <=0
        100  
        101  NZ          !=0
        110  NC          >=0
        111  NC and NZ   >0
			
普通の CPU に比べるとずいぶんシンプルなものになりました。 しかし、普通の CPU では多倍長演算をするにはループで回す必要がありますが、この CPU では1命令で実行できます。




2011/09/16

VHDL で CPU をつくるのは初めての経験でしたが、思ったより簡単にできてしまいました。
とは言っても無駄なところや、改善できるところはたくさんあると思いますが、目標であるπの計算はできましたのでこれでとりあえず完成とします。



■ハードウェア準備


CN2 の 10番ピンに CPU の実行状態(RUNNING)を出してありますので、ここに LED をつけておくと実行時に点灯するようになります。

実行時間を測定するのにも使えます。



■ソフトウェア


MC9S08JS16 はバイナリー転送をサポートしたバージョンが必要です。  MC9S08 Bootloader を起動し、ロジアナのページにある「実行ファイル 20110801 (ZIP 111KB)」を解凍した中にある CDC_monitor.abs.s19 を書き込んでください。

バージョンは、MC9S08JS 20110725_1640 になります。



実行ファイル一式には実行に必要な以下のファイルが入っています。
   APB-2_pai.exe      PC 実行ファイル(Visual C#プロジェクトでコンパイルしたもの)
   apb_2_pai.bit      FPGA コンフィグファイル(Xilinx ISEプロジェクトで作成したもの)
   cpu_assembler.xls    Excel で作ったアセンブラ(π計算プログラムも入っています)
   pai_100.hex       上記アセンブラで作ったπ100桁計算プログラム16進ファイル
   pai_1000.hex       同 π1000桁計算プログラム16進ファイル
   pai_3005.hex       同 π3005桁計算プログラム16進ファイル
   pai_9551.hex       同 π9551桁(最大桁数)計算プログラム16進ファイル
   pai_9951実行結果.txt
		
まずはこれをダウンロードして、以下に示す手順で実行してみてください。 πの計算をするだけなのであまりおもしろくはないかも、ですが....



■PC 側のソフト起動


実行ファイル一式に入っている APB-2_pai.exe を実行します。 PC 側のソフト

左側の薄く茶色になっている部分の上側が CPU の内部状態(レジスターやフラグ)を、下側はメモリー内容を表示します。
右側は上が実行制御関連ボタン、下がメモリー関連ボタンです。

まだ APB-2 基板との USB 接続もしていないのでこのままでは何もできません。
そこで、右下にある Load Program ボタンを押して、

  1.COM ポート選択画面がでますので APB-2 の COM 番号を選択
  2.FPGA を CONFIG するファイル(apb_2_pai.bit)を選択
  3.FPGA CPU にロードするプログラムファイル(pai_3005.hex)を選択

します。


PC 側のソフト プログラムがロードされた

メモリー表示部分にロードしたプログラムが表示されます。
π計算プログラムは 107 words アドレス 0x006B までなのでメモリー表示部分に全部収まってしまいます。

これで実行準備はできたので、右上の「実行」ボタンを押すと CPU が実行開始します。

ロードしたプログラムは 3005 桁のπ計算プログラムです。
3005 桁の実行時間は 0.8 秒なので画面に実行中という赤い文字がでてすぐに消えてしまいます。
LED をつないでいれば、0.8秒間 LED が点灯します。


左下のメモリー表示部分のアドレスを 100 にします。(直接 100 と入れても、上下矢印ボタンを使ってもよいです)


PC 側のソフト 実行終了

π計算結果はアドレス 0100 から BCD で入っていますので、3141 5926 ... となっています。

PC の表示 0019 は止まったアドレスではなく、その次のアドレスを示しています。 つまり、実際に止まったのはアドレス 0018 の pause 命令です。(cpu_assembler.xls のアセンブリリストを見てください)


・画面の右側にある、「Step実行」ボタンでは1機械語ごとの実行ができます。
・BreakPoint を設定すると、そこまで実行して中断します。
・中断したところから「実行」ボタンで再開、「Step実行」ボタンで1機械語ごとの実行ができます。 再度 BreakPoint を設定することもできます。



■アセンブラ


実行ファイル一式に入っている Excel ファイルの cpu_assembler.xls がアセンブラーです。

すでにπ計算プログラム(マチンの公式)が入っていますので参考にしてください。
2 行目、アドレス 0002 の mov size 624 の部分を変更すると計算する桁数を変えることができます。
最大値 1983(下記メモリーマップ参照)で 9551 桁まで計算できます。(9551=1983*log(65536))

コメント部分をみるとわかるようにほとんど C 言語と一対一で対応しています。



■プログラムメモリーマップ


PC 側のソフト プログラムがロードされた

CPU のメモリーは 8192 words(16384 bytes)です。 XC3S200A の Block RAM の半分を使いました。

メモリーの最初の 256 Words をプログラムとスタックに使います。
残り、7936 words を 1984 Words の 4 つの領域に分け、ワークアリアや計算結果格納に使います。
1番最後の領域には 2 進数でのπ計算結果が入ります。
それを 10 進数(BCD)に変換して、1番目と2番目の領域に入れます。



■閑話休題


2012/02/15

別の USB シリアル変換をつないでいると COM 番号がずれてしまい正常にオープンできなくなるというバグがあることがわかりました。



実行ファイル以外は以前のものをそのまま使います。






inserted by FC2 system