実験 7: 素数計算プログラムの作成

2013/10/17, 第1.2版

実験の概要

本実験では、3以上「キーボード入力された数」以下の素数をディスプレイに次々表示する処理を、Cプログラムとプロセッサにより行う。

素数計算プログラムの作成

3以上「キーボード入力された数」以下の素数をディスプレイに次々表示する処理を、Cプログラムとプロセッサにより実現せよ。

本実験を下記の 1, 2, 3, 4, 5, 6 の手順で行いなさい。
1. クロスコンパイル
2. MIPSマシン・コードからのメモリ・イメージファイルの作成
3. 命令メモリに格納される命令列の確認
4. 論理合成
5. FPGAを用いた回路実現
6. Cプログラムの変更

なお、本実験で使用するCプログラムsosuu.cは、下記のURLからダウンロードできる。

Cプログラムsosuu.c：
http://www.ice.nuie.nagoya-u.ac.jp/jikken/hard/j2hard-mips/k07_sosuu/sosuu.c
（実験7用のCプログラム）

1. クロスコンパイル

本実験では、図1の sosuu.c を使用する（ダウンロード）。

#define EXTIO_SCAN_ASCII (*(volatile unsigned int *)0x0310)
#define EXTIO_SCAN_REQ (*(volatile unsigned int *)0x030c)
#define EXTIO_SCAN_STROKE (*(volatile unsigned int *)0x0308)

#define SCAN_STRORING (unsigned int)0xffffffff

#define EXTIO_PRINT_STROKE (*(volatile unsigned int *) 0x0300)
#define EXTIO_PRINT_ASCII  (*(volatile unsigned int *) 0x0304)

#define TRUE 	0x1
#define FALSE	0x0

unsigned int sosuu_check(unsigned int kouho);
unsigned int my_a2i();
void my_i2a();
void my_print();
void my_scan();

main() {
  unsigned int i;
  unsigned int k;
  unsigned int str1[16];
  unsigned int str2[16];

  /* "HELLO" を print */
  str1[0] = 'H';  str1[1] = 'E';
  str1[2] = 'L';  str1[3] = 'L';
  str1[4] = 'O';  str1[5] = '\n';
  str1[6] = '\0';
  my_print(str1);

  while (1) {	
    /* "NUM=" を print */
    str1[0] = 'N';  str1[1] = 'U';
    str1[2] = 'M';  str1[3] = '=';
    str1[4] = '\0';
    my_print(str1);

    /* キーボードから入力された文字列（数字）を str2[] に記憶 */
    my_scan(str2);

    /* "ECHO " を print */
    str1[0] = 'E';	str1[1] = 'C';
    str1[2] = 'H';	str1[3] = 'O';
    str1[4] = ' ';	str1[5] = '\0';
    my_print(str1);

    /* str2[] を print */
    my_print(str2);

    /* '\n' を print */
    str1[0] = '\n';  str1[1] = '\0';
    my_print(str1);
    
    /* 文字列（数字） srt2[] を unsigned int に変換 */
    k = my_a2i(str2);
    
    for (i = 3; i <= k; i++) {
      /* 素数判定 */
      if ( sosuu_check(i) ) {  
	/* unsigned int i を文字列（数字）に変換して print */
	my_i2a(i);
      }
    }

    /* '\n' を print */
    str1[0] = '\n';  str1[1] = '\0';
    my_print(str1);
  }
}

/* unsigned int kouho の素数判定を行う関数 */
/* 素数なら TRUE を返す */
/* 素数でないなら FALSE を返す */
unsigned int sosuu_check(unsigned int kouho) {
  unsigned int t, tester, result;

  if ((kouho % 2) == 0) {
    /* kouho は偶数である == TRUE */
    return FALSE;
  } else {
    result = TRUE;
    for (tester = 3; tester < kouho/2; tester += 2) {
      /* kouho が本当に素数かどうかをチェック */
      if ((kouho % tester) == 0) {
        /* kouho は tester の倍数である */
        result = FALSE;
      }
    }
    return result;
  }
}

/* 文字列（数字） srt[] を unsigned int に変換する関数 */
/* unsigned int result を返す */
unsigned int my_a2i(str)
     unsigned int *str;
{
  unsigned int *str_tmp;
  unsigned int k;
  unsigned int result;

  str_tmp = str;
  for (k = 0; *str_tmp != '\0'; k++) {
    str_tmp++;
  }

  result = 0;
  str_tmp = str;
  
  if (k == 1) {
    result = *str_tmp - '0';
  } else if (k == 2) {
    for (k = 0; k < (*str_tmp - '0'); k++) {
      result = result + 10;
    }
    str_tmp++;
    result = result + (*str_tmp - '0');
  } else if (k == 3) {
    for (k = 0; k < (*str_tmp - '0'); k++) {
      result = result + 100;
    }
    str_tmp++;
    for (k = 0; k < (*str_tmp - '0'); k++) {
      result = result + 10;
    }
    str_tmp++;
    result = result + (*str_tmp - '0');
  }

  return result;
}

/* unsigned int i を文字列（数字）に変換して print する関数 */
void my_i2a(unsigned int i) {
  unsigned int counter;
  unsigned int s[4];

    for (counter = 0; i >= 10; counter++) {
        i -= 10;
    }
    s[0] = counter + '0';
    s[1] = i + '0';
    s[2] = ' ';
    s[3] = '\0';

    my_print(s);
}

/* キーボードから入力された文字列を str[] に記憶する関数 */
void my_scan(str)
     unsigned int *str;
{
    EXTIO_SCAN_STROKE = (unsigned int)0x00000000;
    EXTIO_SCAN_REQ = (unsigned int)0x00000001;
    EXTIO_SCAN_STROKE = (unsigned int)0x00000001;

    EXTIO_SCAN_STROKE = (unsigned int)0x00000000;
    EXTIO_SCAN_STROKE = (unsigned int)0x00000001;
    while (EXTIO_SCAN_ASCII == SCAN_STRORING) {
      EXTIO_SCAN_STROKE = (unsigned int)0x00000000;
      EXTIO_SCAN_STROKE = (unsigned int)0x00000001;
    }

    while ((*str = EXTIO_SCAN_ASCII) != (unsigned int)0x3e) {    // 0x3e=RETURN
      if ((*str >= 1) && (*str <= 26)) {
	*str = 'A' + *str - 1;
      } else if ((*str >= 48) && (*str <= 57)) {
	*str = '0' + *str - 48;
      } else {
	if (*str == 0) {
	  *str = '@';
	} else if (*str == 27) {
	  *str = '[';
	} else if (*str == 29) {
	  *str = ']';
	} else if ((*str >= 32) && (*str <= 47)) {
	  *str = ' ' + *str - 32;
	} else if (*str == 58) {
	  *str = '?';
	} else if (*str == 59) {
	  *str = '=';
	} else if (*str == 60) {
	  *str = ';';
	} else if (*str == 61) {
	  *str = ':';
	} else if (*str == 62) {
	  *str = '\n';
	} else {
	  *str = '@';
	}
      }
      EXTIO_SCAN_STROKE = (unsigned int)0x00000000;
      EXTIO_SCAN_STROKE = (unsigned int)0x00000001;
      str++;
    }
    *str = '\0';

    EXTIO_SCAN_STROKE = (unsigned int)0x00000000;
    EXTIO_SCAN_REQ = (unsigned int)0x00000000;
    EXTIO_SCAN_STROKE = (unsigned int)0x00000001;

    EXTIO_SCAN_STROKE = (unsigned int)0x00000000;
}

/* 文字列 str[] を表示する関数 */
void my_print(str)
     unsigned int *str;
{
  while (*str != '\0') {
    EXTIO_PRINT_STROKE = (unsigned int)0x00000000;

    if ((*str >= 'A') && (*str <= 'Z')) {
      EXTIO_PRINT_ASCII = *str - 'A' + 1;
    } else if ((*str >= 'a') && (*str <= 'z')) {
      EXTIO_PRINT_ASCII = *str - 'a' + 1;
    } else if ((*str >= '0') && (*str <= '9')) {
      EXTIO_PRINT_ASCII = *str - '0' + 48;
    } else {
      if (*str == '@') {
        EXTIO_PRINT_ASCII = (unsigned int)0;
      } else if (*str == '[') {
        EXTIO_PRINT_ASCII = (unsigned int)27;
      } else if (*str == ']') {
        EXTIO_PRINT_ASCII = (unsigned int)29;
      } else if ((*str >= ' ') && (*str <= '/')) {
        EXTIO_PRINT_ASCII = *str - ' ' + 32;
      } else if (*str == '?') {
        EXTIO_PRINT_ASCII = (unsigned int)58;
      } else if (*str == '=') {
        EXTIO_PRINT_ASCII = (unsigned int)59;
      } else if (*str == ';') {
        EXTIO_PRINT_ASCII = (unsigned int)60;
      } else if (*str == ':') {
        EXTIO_PRINT_ASCII = (unsigned int)61;
      } else if (*str == '\n') {
	EXTIO_PRINT_ASCII = (unsigned int)62;
      } else {
        EXTIO_PRINT_ASCII = (unsigned int)0x00000000;
      }
    }
   
    EXTIO_PRINT_STROKE = (unsigned int)0x00000001;
    str++;
  }
}

図1： sosuu.c
クロスコンパイルには、「cross_compile.sh」を使用する。指導書2.2.1節に示した環境設定を行ったのち、図2のようにして、sosuu.cからMIPSマシン・コードを作成せよ。

cross_compile.sh sosuu.c

図2： cross_compile.shを使ったMIPSマシン・コードの生成
クロスコンパイルにより、MIPSマシン・コードsosuu.binが得られる。

2. MIPSマシン・コードからのメモリ・イメージファイルの作成

本実験では、MIPSマシン・コードsosuu.binを使用する。また変換には、変換プログラムbin2vを使用する。図3のようにして、MIPSマシン・コードsosuu.binからメモリ・イメージファイルを作成せよ。

bin2v sosuu.bin

図 3： bin2vを使ったMIPSマシン・コードのメモリ・イメージファイルへの変換
この変換により、論理合成用のメモリ・イメージファイルrom8x1024_DE2.mifと、機能レベルシミュレーション用の命令メモリのVerilog HDL記述rom8x1024_sim.vが得られる。

3. 命令メモリに格納される命令列の確認

本実験では、プロセッサの命令メモリに格納される命令列の確認を行う。この確認には、bin2vにより生成された機能レベルシミュレーション用のVerilog HDL記述rom8x1024_sim.vを使用する。

図4にrom8x1024_sim.vの一部を示す。図4のcaseブロック内の各行は、本実験で設計するプロセッサにおける、命令メモリの 10-bit アドレスとそこに格納される 32-bit 命令の機械語の記述である。また、各行の // 以降のコメント部には、その行に記述されているアドレスと命令に関する説明が記述されている。コメント部には、実際のMIPSの命令メモリにおけるアドレスと、命令名、命令の意味が記述されている。命令の意味の記述では、シンボルREG[0],REG[1],...,REG[31]により、レジスタ0番から31番、$s0,...,$s31を表す。また、シンボルRAM[w]により、データメモリのw番地を表す。

<省略>
10'h00b: data = 32'h03a0f021; // 0040002c: ADDU, REG[30]<=REG[29]+REG[0];　　ここが PC=0x002c の命令
<省略>
10'h081: data = 32'h14400002; // 00400204: BNE, PC<=(REG[2] != REG[0])?PC+4+2*4:PC+4;
10'h082: data = 32'h0062001b; // 00400208: R type, unknown. func=27(10)　　ここが命令メモリ 0x082 の命令
10'h083: data = 32'h0007000d; // 0040020c: R type, unknown. func=13(10)
10'h084: data = 32'h00001010; // 00400210: R type, unknown. func=16(10)
10'h085: data = 32'h14400002; // 00400214: BNE, PC<=(REG[2] != REG[0])?PC+4+2*4:PC+4;
<省略>

図 4： rom8x1024_sim.v の一部
(a) 命令メモリの0x082番地の命令は、実験6-2で作成したプロセッサでは未実装な命令である。これはどのような命令か、参考書[3]（または、参考書[1]）の表紙の次のページ、緑紙、MIPSリファレンスデータ、丸3の表、参考書[3]のp.222,pp.257-258（または、参考書[1]のp.175,pp.207-208）の表を参考に、調査せよ（0x082番地の命令についてのみよい）。なお、func=27(10)はfuncが10進で27を表している。

(b) 3(a)の命令は、Cソースsosuu.c 中の関数sosuu_check()の処理を行う命令の一つである。具体的に、sosuu_check()のどの記述に対応しているかを予想せよ。

4. 論理合成

本実験では、プロセッサならびに命令メモリ、その他周辺回路の論理合成を行う。論理合成には、bin2vにより生成された論理合成用のメモリ・イメージファイルrom8x1024_DE2.mifと実験6-2で完成させたプロセッサのVerilog HDL記述一式を使用する。

命令メモリのメモリ・イメージファイルrom8x1024_DE2.mifをディレクトリmips_de2-115にコピーし、ディレクトリmips_de2-115にcdして、図5のように論理合成を行う。

quartus_sh --flow compile DE2_115_Default

図5： quartus_sh を使ったプロセッサの論理合成
なお、論理合成には計算機の性能により5分から20分程度の時間がかかる。論理合成が完了すると、ディレクトリmips_de2-115内にFPGAにダウンロード可能なプロセッサ等の回路一式のストリーム・アウト・ファイルDE2_115_Default.sofが生成される。

5. FPGA を用いた回路実現

本実験では、実験6-2で作成したプロセッサでsosuu.binを実行するとどのような動作をするかを観察する。本実験には、論理合成により生成されたプロセッサなど回路一式のストリーム・アウト・ファイルDE2_115_Default.sofを使用する。 DE2_115_Default.sof を quartus_pgm を用いて DE2-115 ボード上の FPGA にダウンロードし、動作させよ。

今回プロセッサが実行するマシン・コードsosuu.binは、３以上「キーボードから入力された数」以下の素数を次々とディスプレイに表示するプログラムである。
(a) クロック供給モードを1000Hzに設定し、ディスプレイ下部に"HELLO\n", "NUM="と表示されたら、キーボードから20\nを入力する（\nは改行）。 3 以上 20 以下の素数が次々と表示されてほしいが、そうはならないはずである。その結果を観察せよ。

(b) 5(a)で観察された正しくない動作の原因は3(a),(b)にある。この問題を解決する方法を２つ考えよ。

6. Cプログラムの変更

本実験では、おそらく２つの解決法のうちの１つである、Cプログラムの変更を行う。

Cプログラムの変更は、次の２点に注意して行ってください。
１.　switch 文は使用しない（今のところ、cross_compile.sh, 又は、bin2v, プロセッサが対応していません）。if 文を使ってください。
２.　Cプログラムのソースにおいて、main 関数の記述は、他のどの関数の記述よりも先に書く（今のところ、プロセッサが実行する順番が、記述順に依存しています）。

3 から「キーボード入力された数」までの素数をディスプレイに表示する処理が正しく行えるように、sosuu.cを変更し、実際に動作させて動作を確認せよ。

なお、本実験におけるソフトウェア開発環境では、switch 文を含む C プログラムが正しく動作しないので、switch 文のかわりに、if 文を使用してください。
また、本実験におけるソフトウェア開発環境では、C ソースの記述において、main 関数が、他の関数の記述より前にないと正しく動作しないので、C ソース中で main 関数を最初に書いてください。

参考書

[1] パターソン＆ヘネシー著（成田光彰訳）：「コンピュータの構成と設計（上巻）第３版」, 日経ＢＰ社
[2] パターソン＆ヘネシー著（成田光彰訳）：「コンピュータの構成と設計（下巻）第３版」, 日経ＢＰ社
[3] パターソン＆ヘネシー著（成田光彰訳）：「コンピュータの構成と設計（上巻）第４版」, 日経ＢＰ社

中村一博