Synthesijer入門1

どうもSynthesijer でステップバイステップで入門できる，チュートリアル的なサイトがないなーという印象なので，自分で書いてみることにしました．流れとしては，以下の通りです．

# 目次
1. 前提条件
2. JavaでQuickSortを書く
3. QuickSortをSynthesijer向けに書き直す
4. QuicksortをFPGAボードに実装する

続編の[Synthesijer入門2](http://qiita.com/TanigawaHCU/items/5b14f655ee927bb8e5bc)ではマルチスレッド版に変更する内容となっています．


# 前提条件
このページでは以下のような方を前提としています．
- Javaのプログラミングの知識はある．
- HDLもある程度は書ける． 
- FPGAツールの使い方も分かる．
- Synthesijerの環境設定

最初にJavaでのプログラミングにおいて，クラス，メソッド，コンストラクタ，フィールド変数などの用語は理解していて，簡単なプログラムであれば，Javaでスラスラとプログラミングできる事を想定しています．

2つ目にHDL(Hardware Description Language)についてもある程度書けることを想定しています．具体的には，このページではVerilog-HDLを使いますが，モジュールの呼び出しや接続の方法が読める／書ける，くらいを想定しています．alwaysを用いた回路記述は分からなくても問題ありません（その辺りはSynthesijerに任せちゃいます）．

3つ目にFPGAツールの使い方が分かることを前提としています．これは少し敷居が高いかもしれませんが，少なくともFPGA用のプロジェクトを作って，デバイスを選んで，ピンアサインして，必要なHDLファイルを登録して，論理合成＆配置配線して，FPGA用の構成情報を作って，それをダウンロードして動かす，という事が分かっていないと実際の作業は難しいと思います．また，解説ではFPGA用のCADを使って説明するところもあるので知っていた方がベターですが，その辺りは読み流してくれても問題ないと思います．

4つ目にSynthesijerのインストールと環境設定は各自にお任せします．これらの情報は既に色々なサイトにあるように思えますので．

# JavaでQuickSortを書く

最初にソフトウェア版のQuickSortを書いてみたいと思います．
QuickSortをJavaで書いたものが以下のSortTop.javaとQuickSort.javaになります．

```java:Main.java
public class Main {
	public static void main(String... args) {

		SortTop sort = new SortTop();

		sort.start();
	}

}
```

```java:SortTop.java
import java.util.Random;

public class SortTop extends Thread{
	public static int NUM = 100;

	public void run() {
		 Random rand = new Random();
         int[] values = new int[NUM];
         for (int i = 0; i < values.length; i++) {
                 values[i] = rand.nextInt();
                 System.out.println(values[i]);
         }

         QuickSort qsort = new QuickSort();

         System.out.println("Start sorting");
         qsort.quickSort(0, values.length-1, values);

         for( int i=0; i< values.length; i++) {
        	 System.out.println(values[i]);
        	 if( i!=0 && (values[i-1]>values[i])) {
        		 System.out.println("Sort Error!!");
        		 System.exit(1);
        	 }
         }
         System.out.println("Done.");
	}
}

```

```java:QuickSort.java
public class QuickSort {

	public void quickSort(int left, int right, int [] arr) {
        int index = partition(left, right, arr);
        if (left < index - 1)
              quickSort(left, index - 1, arr);
        if (index < right)
              quickSort(index, right, arr);
	}

	private int partition(int left, int right, int [] arr) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
              while (arr[i] < pivot)
                    i++;
              while (arr[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                    j--;
              }
        };

        return i;
	}

}
```

ここでのキーポイントは以下になります．
- ハードウェアにしたい処理は独立したスレッドクラスにする

SynthesijerではJavaのスレッド記述をハードウェア(HDL）に変換します．そのためSortTopクラスはスレッドをextendして，runメソッドが呼ばれたときに実行開始するようにしています．そのSortTopに対してrunメソッドを呼ぶのは，ハードウェアの外部から信号として送る必要があるので，別途Mainクラスを用意しました．このmainメソッドをSortTopクラスに書いて，mainメソッドのみハードウェア化の対象から外すこともSynthesijerではできますが，別クラスに分けた方が考えやすいかなと思いますので，別クラスにしました．

SortTopとQuickSortを別クラスにしたのは，Synthesijerの色々な特徴を理解するにはハードウェア化の対象のクラスが複数のクラスに別れていた方が都合が良いからです．

まとめますと，今回の例ではSortTopとQuickSortをハードウェア化します．そして，Mainクラスでやっているsort.start()に相当する処理はスイッチなどを使って，作成されたハードウェアに信号を入力することで実現します．

# QuickSortをSynthesijer向けに書き直す
## 変換に必要な知識（ノウハウ）
私はQuickSortをSynthesijerで動かしただけなので，全てのノウハウがあるわけではないのですが，とりあえずSynthesijer向けに変換しないといけない内容をリストアップし，その後で具体例を用いて説明します．
### 標準クラス
+ 標準クラスの多くは使用できません（論理回路に変換できません）．

### 配列・クラス
+ 配列，クラスをメソッドの引数に指定できない．
+ 配列，クラスは実行時にインスタンス化できない．
+ 結果として，配列，クラスはフィールド変数（インスタンス変数）として用意し，定義と同時にインスタンス化する．
+ クラスの配列も定義できない．なぜなら，フィールド変数の定義と同時にインスタンス化しないといけないが，フィールドの定義時にfor文などを使用できないため．
+ フィールド変数として定義された配列のハードウェアのイメージは，そのモジュールが独立して持つローカルメモリです．

### アクセス修飾子について
+ publicなフィールド変数，メソッドは他のクラスからアクセスできます．つまりトップのクラスのpublicな変数などは外部から値を読んだり，変更したりするための配線が用意されます．
+ publicな変数を１つ用意すると，そこに対して，read要求線，write要求線，入力値，出力値などアクセスに必要な信号が外部ピンとして用意されますので，外部からアクセスする必要のないフィールド変数，メソッドはできる限りprivateにするのがお勧めです．
+ アクセス修飾子をつけない場合はどうなるのか不明です．

### その他
+ 再帰呼び出しは末尾再帰のみサポートされている．
+ コンストラクタはサポートされていない．さらに，初期化はフィールド変数の定義と同時に行えない．なので，初期化は別途，初期化用のメソッドを定義し，そこで全ての変数の初期化を行い，その初期化用のメソッドを実行時の最初に呼び出すようにする．
+ 式による定数の評価はSynthesijerでは正しく認識してくれない．例えば，「static final int NUM=100/2;」というような記述がある場合，コンパイルエラーになる．
+ SynthesijerでHDLへの変換ができない記述があった場合，変換中にエラーが出力されてコンパイルが停止するが，どの記述で止まったか分からない場合も多い．
+ SynthesijerでHDLへ変換できた場合でも正しく動作する論理回路が生成されない場合もある．そのような場合にはHDLレベルのシミュレーションなどにより動作を検証する必要がある．

## SortTop.javaの記述の変更
### System.out.printlnを用いた入出力の変更
SortTop.javaではSystem.out.printlnを用いて，ソートを開始したとか，ソート結果にエラーがあるなど，実行状態を標準出力に文字列として表示しています．しかし，FPGAボードには標準出力という便利なものはありません（LCDやUARTを使って出すこともできますが，標準では使えず，プログラマがそれら用の記述をする必要があります）．

そこで，多くの入門向けのFPGAボードに搭載されているLEDに，実行状態を出力するようにします．具体的には，ソートを開始したらLED0を点灯させ，ソート結果にエラーがある場合にはLED2を点灯する，という具合です．これを実現するために，各状態を表すフラグを用意します．各フラグはLEDの点灯，消灯で状態を表すので，boolean型の変数をフィールド変数として用意し，外部から値を参照できるようにpublic宣言をつけます．これらのフィールド変数ですが，初期値を定義時にセットすることができないので，privaiteな初期化メソッドinitを作成し，そこで初期値をセットするようにします．

これらの変更をした，SortTop.javaを以下に示します．

```java:SortTop.java
import java.util.Random;

public class SortTop extends Thread{
	public static int NUM = 100;

	// 実行状態を表すためのフラグを追加
	public boolean start_flag;
	public boolean error_flag;
	public boolean done_flag;

	public void run() {
		/* フィールド変数の定義時の初期化はサポートされていないので，
		 * init()メソッド内で初期化の処理を追加する */
		init();

		Random rand = new Random();
		int[] values = new int[NUM];
		for (int i = 0; i < values.length; i++) {
			values[i] = rand.nextInt();
			System.out.println(values[i]);
         }

		QuickSort qsort = new QuickSort();

		//System.out.println("Start sorting");
		start_flag = true;

		qsort.quickSort(0, values.length-1, values);

		for( int i=0; i< values.length; i++) {
			//System.out.println(values[i]);
			if( i!=0 && (values[i-1]>values[i])) {
				//System.out.println("Sort Error!!");
				//System.exit(1);
				error_flag = true;
        	 }
         }
         //System.out.println("Done.");
         done_flag = true;
	}

	/* フィールド変数の定義時の初期化はサポートされていないので，
	 * init()メソッド内で初期化の処理を追加する */
	private void init() {
		start_flag = false;
		error_flag = false;
		done_flag = false;
	}
}
```

この変更により，正常に終了したときは，done_flagとstart_flagが1でかつ，error_flagが0になるはずです．逆にソート結果が正しくないときは，done_flag, error_flag, start_flagの3つとも1になります．

### Randomクラスを用いた記述の変更
Randomクラスも（自分で乱数回路を記述しない限り）論理回路に変換できないので，今回は静的に乱数値を代入することにします．

### 動的なインスタンス化を静的に変更
SortTop.javaにおいて，配列valuesとインスタンスqsortが実行時にインスタンス化されているので，それぞれをフィールド変数として静的にインスタンス化するように変更します．また，配列valuesの初期値データはRandomクラスを用いていましたが，Randomクラスも（自分で乱数回路を記述しない限り）論理回路に変換できないので，今回はinitメソッドで乱数値を直接，代入することにします．

以上の変更をしたSortTop.javaを以下に示します．

```java:SortTop.java
public class SortTop extends Thread{
	public static int NUM = 100;

	// 実行状態を表すためのフラグを追加
	public boolean start_flag;
	public boolean error_flag;
	public boolean done_flag;

	/* Randomクラスは論理回路に変換できない，かつ，
	 * 配列も動的にインスタンス化できないので，
	 * 配列valuesをフィールド変数として宣言する．
	 */
	private int [] values = new int[NUM];

	/* QuickSortクラスのインスタンス化も静的にする */
	private QuickSort qsort = new QuickSort();

	public void run() {
		/* フィールド変数の定義時の初期化はサポートされていないので，
		 * init()メソッド内で初期化の処理を追加する */
		init();


		//System.out.println("Start sorting");
		start_flag = true;

		qsort.quickSort(0, values.length-1, values);

		for( int i=0; i< values.length; i++) {
			//System.out.println(values[i]);
			if( i!=0 && (values[i-1]>values[i])) {
				//System.out.println("Sort Error!!");
				//System.exit(1);
				error_flag = true;
        	 }
         }
         //System.out.println("Done.");
         done_flag = true;
	}

	/* フィールド変数の定義時の初期化はサポートされていないので，
	 * init()メソッド内で初期化の処理を追加する */
	private void init() {
		start_flag = false;
		error_flag = false;
		done_flag = false;

        values[0] = -580072087;
        values[1] = -301572182;
        values[2] = 1671928837;
        values[3] = 917935597;
        values[4] = 191647674;
        values[5] = -899353241;
        （省略）
        values[99] = -400747481;

	}
}

```

## QuickSort.javaの記述の変更（QuickSort2.javaの記述）
QuickSort.javaの記述の変更だが，SortTop.javaの記述の変更のように簡単にはいきません．その理由は以下の通りです．
1. Synthesijerでは「末尾再帰」の再帰呼び出ししかHDLに変換できない
2. メソッドの引数に配列を指定することができない

そのため，それらに対する修正が必要です．

### 再帰呼び出しをやめてループで実現
Quicksortのような再帰的なアルゴリズムをループを用いて実現します．考え方としては，再帰呼び出しがある場合はコンパイラがスタックを用いて再帰呼び出しを実現してくれているのですが，それをプログラム自身に書いてしまうことで，再帰呼び出しをループの形に変換します．例えば，以下で示すQuicksortでは，ソート対象の左と右の添字番号をスタックで管理し，そのスタックに積まれた添字番号を全て処理したら，プログラムを終了するように変更されています（詳細な説明は他のサイトに譲ります）．

今回はアルゴリズムの実装方法を大幅に変更しているので，クラス名をQuickSort2とします（そのため，SortTop.javaでのQuickSortクラスのインスタンス化の処理も名称変更が必要です）．

今回のように大きくソースコードを変更した際には，コメントアウトしたSystem.out.printlnやEclipseのデバッグ環境などを使用して，プログラムとして正しく動作することを確認して下さい．

```java:QuickSort2.java

public class QuickSort2 {
	private int [] left_stack = new int [SortTop.NUM];
	private int [] right_stack = new int [SortTop.NUM];
/*
	public void quickSort(int left, int right, int [] arr) {
        int index = partition(left, right, arr);
        if (left < index - 1)
              quickSort(left, index - 1, arr);
        if (index < right)
              quickSort(index, right, arr);
	}
*/
    public void quickSort(int left, int right, int [] arr) {
        int sp;

        sp = 0;
        left_stack[0] = 0;
        right_stack[0] = arr.length-1;
        sp = 1;

        /* スタックが空になるまで繰り返す */
        while( sp > 0 ) {
        	/* スタックPOP */
        	sp--;
        	left = left_stack[sp];
        	right = right_stack[sp];

        	int index = partition(left, right, arr);
        	/* スタックPUSH */
        	if( left < index-1 ) {
        		left_stack[sp] = left;
        		right_stack[sp++] = index-1;
        	}
        	if( index < right ) {
        		left_stack[sp] = index;
        		right_stack[sp++] = right;
        	}
        }

   }

	private int partition(int left, int right, int [] arr) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
              while (arr[i] < pivot)
                    i++;
              while (arr[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                    j--;
              }
        };

        return i;
	}

}

```

### メソッドの引数の配列指定をなくす
これも結構大きな変更なのですが，メソッドの引数で配列を使用している場合，SynthesijerではHDLに変換できません．なぜ変換できない仕様なのかを推測すると，通常のJavaプログラムでは配列などは参照渡しなので，配列を渡している時はアドレスしか渡していません．この参照渡しは全てのデータが同じメモリ空間にあるという前提なら問題ない方法なのです．しかし，ハードウェア回路では大きなメモリを1つ持って全てのユニットで共有するよりも，小さなメモリをたくさん分散的に持った方が効率がよいので，Synthesijerでは配列を個別のメモリユニットにマッピングします．そうすると，メソッドなどでやりとりする配列はあるメモリにあるデータ全てを別のメモリに全てコピーするイメージになります．このコピー操作は処理のオーバーヘッドが大きく，また配列を渡すときに全ての場合で必要とは限らないので，あえて非サポートにして，必要に応じてプログラマが実装できる仕様にしているのだと思います．

そこでメソッドの引数に配列を用いている場合には以下のように変更します．
- 配列はフィールド変数として用意し，フィールド変数の配列を直接，参照するようにする．
- 他のインスタンスから配列の値をセットしたり，読み出したりする必要がある場合には，それらを実現するメソッド（Getter/Setter)を用意する．具体的にはgetValue(int index)というメソッドで配列arr[index]の値を返し，setValue(int index, int data)というメソッドで配列arr[index]に値dataをセットするようにします．

これらの変更を加えたQuickSort2.javaを以下に示します．

```java:QuickSort2.java

public class QuickSort2 {
	public int [] arr = new int [SortTop.NUM];

	private int [] left_stack = new int [SortTop.NUM];
	private int [] right_stack = new int [SortTop.NUM];
/*
	public void quickSort(int left, int right, int [] arr) {
        int index = partition(left, right, arr);
        if (left < index - 1)
              quickSort(left, index - 1, arr);
        if (index < right)
              quickSort(index, right, arr);
	}
*/

	public int getValue(int index) {
		return arr[index];
	}

	public void setValue(int index, int data) {
		arr[index] = data;
	}

    public void quickSort(int left, int right) {
        int sp;

        sp = 0;
        left_stack[0] = 0;
        right_stack[0] = arr.length-1;
        sp = 1;

        /* スタックが空になるまで繰り返す */
        while( sp > 0 ) {
        	/* スタックPOP */
        	sp--;
        	left = left_stack[sp];
        	right = right_stack[sp];

        	int index = partition(left, right);
        	/* スタックPUSH */
        	if( left < index-1 ) {
        		left_stack[sp] = left;
        		right_stack[sp++] = index-1;
        	}
        	if( index < right ) {
        		left_stack[sp] = index;
        		right_stack[sp++] = right;
        	}
        }

    }

	private int partition(int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
              while (arr[i] < pivot)
                    i++;
              while (arr[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                    j--;
              }
        };

        return i;
	}

}

```

またQuickSort2.javaのquickSortメソッドが配列を引数に取らなくなったので，SortTopクラスではソートを開始する前に，配列データのセットを行い，ソートが終了した後に配列データをゲットする処理を追加します．そのような変更を加えたSortTop.javaを以下に示します．

```java:SortTop.java
public class SortTop extends Thread{
	public static int NUM = 100;

	// 実行状態を表すためのフラグを追加
	public boolean start_flag;
	public boolean error_flag;
	public boolean done_flag;

	/* Randomクラスは論理回路に変換できない，かつ，
	 * 配列も動的にインスタンス化できないので，
	 * 配列valuesをフィールド変数として宣言する．
	 */
	private int [] values = new int[NUM];

	/* QuickSortクラスのインスタンス化も静的にする */
	private QuickSort2 qsort = new QuickSort2();

	public void run() {
		/* フィールド変数の定義時の初期化はサポートされていないので，
		 * init()メソッド内で初期化の処理を追加する */
		init();

		/*
		Random rand = new Random();
		int[] values = new int[NUM];
		for (int i = 0; i < values.length; i++) {
			values[i] = rand.nextInt();
			System.out.println(values[i]);
         }
         */

		/* qsortに配列データをセットする */
		for( int i=0; i<values.length; i++) {
			qsort.setValue(i, values[i]);
		}

		//System.out.println("Start sorting");
		start_flag = true;

		qsort.quickSort(0, values.length-1);

		/* qsortから配列データをゲットする */
		for( int i=0; i<values.length; i++) {
			values[i] = qsort.getValue(i);
		}

		for( int i=0; i< values.length; i++) {
			//System.out.println(values[i]);
			if( i!=0 && (values[i-1]>values[i])) {
				//System.out.println("Sort Error!!");
				//System.exit(1);
				error_flag = true;
        	 }
         }
         //System.out.println("Done.");
         done_flag = true;
	}

	/* フィールド変数の定義時の初期化はサポートされていないので，
	 * init()メソッド内で初期化の処理を追加する */
	private void init() {
		start_flag = false;
		error_flag = false;
		done_flag = false;

        values[0] = -580072087;
        values[1] = -301572182;
        values[2] = 1671928837;
        （省略）
        values[99] = -400747481;

	}
}

```

### 他のクラス変数（staticなフィールド変数）の参照をなくす
QuickSort2.javaで，SortTopクラスのNUMというクラス変数を参照していますが，このような参照がある場合，SynthesijerではHDLへの変換に失敗するようです．ですので，自クラス内のクラス変数に変更します．

```java:QuickSort2.java

public class QuickSort2 {
	private static final int NUM = 100;
	public int [] arr = new int [NUM];

	private int [] left_stack = new int [NUM];
	private int [] right_stack = new int [NUM];
/*
	public void quickSort(int left, int right, int [] arr) {
        int index = partition(left, right, arr);
        if (left < index - 1)
              quickSort(left, index - 1, arr);
        if (index < right)
              quickSort(index, right, arr);
	}
*/

	public int getValue(int index) {
		return arr[index];
	}

	public void setValue(int index, int data) {
		arr[index] = data;
	}

    public void quickSort(int left, int right) {
        int sp;

        sp = 0;
        left_stack[0] = 0;
        right_stack[0] = arr.length-1;
        sp = 1;

        /* スタックが空になるまで繰り返す */
        while( sp > 0 ) {
        	/* スタックPOP */
        	sp--;
        	left = left_stack[sp];
        	right = right_stack[sp];

        	int index = partition(left, right);
        	/* スタックPUSH */
        	if( left < index-1 ) {
        		left_stack[sp] = left;
        		right_stack[sp++] = index-1;
        	}
        	if( index < right ) {
        		left_stack[sp] = index;
        		right_stack[sp++] = right;
        	}
        }

    }

	private int partition(int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
              while (arr[i] < pivot)
                    i++;
              while (arr[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                    j--;
              }
        };

        return i;
	}

}
```

### 2のべき乗の乗算，除算をシフト演算に変更する
QuickSort2.javaで，pivotを計算するのに「(left+right)/2」という計算をしています．これは，Altera系のFPGAボードを使っている場合，適切なライブラリがSynthesijer用に用意されていないため，FPGA用の配置配線ツールでうまく動作しない問題があります．またXilinx系のFPGAボードを使っている場合は正しく回路を作成してくれると思いますが，このような２のべき乗の乗算・除算はシフト演算に置き換えた方がリソースが少なくてすむので，置き換えた方がよいです．以下に，「(left+right)/2」の演算をシフト演算で置き換えた場合のQuickSort2.javaを示します．

```java:QuickSort2.java

public class QuickSort2 {
	private static final int NUM = 100;
	public int [] arr = new int [NUM];

	private int [] left_stack = new int [NUM];
	private int [] right_stack = new int [NUM];
/*
	public void quickSort(int left, int right, int [] arr) {
        int index = partition(left, right, arr);
        if (left < index - 1)
              quickSort(left, index - 1, arr);
        if (index < right)
              quickSort(index, right, arr);
	}
*/

	public int getValue(int index) {
		return arr[index];
	}

	public void setValue(int index, int data) {
		arr[index] = data;
	}

    public void quickSort(int left, int right) {
        int sp;

        sp = 0;
        left_stack[0] = 0;
        right_stack[0] = arr.length-1;
        sp = 1;

        /* スタックが空になるまで繰り返す */
        while( sp > 0 ) {
        	/* スタックPOP */
        	sp--;
        	left = left_stack[sp];
        	right = right_stack[sp];

        	int index = partition(left, right);
        	/* スタックPUSH */
        	if( left < index-1 ) {
        		left_stack[sp] = left;
        		right_stack[sp++] = index-1;
        	}
        	if( index < right ) {
        		left_stack[sp] = index;
        		right_stack[sp++] = right;
        	}
        }

    }

	private int partition(int left, int right) {
        int i = left, j = right;
        int tmp;
        //int pivot = arr[(left + right) / 2];
        int pivot = arr[(left + right) >> 1];


        while (i <= j) {
              while (arr[i] < pivot)
                    i++;
              while (arr[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                    i++;
                    j--;
              }
        };

        return i;
	}

}
```

# QuicksortをFPGAボードに実装する
## トップファイルのHDLファイルを用意する．
SynthesijerでHDLにしたモジュール（ここではSortTop）をハードウェア化したい回路のトップモジュールにしてもよいのですが，以下の理由から，別途トップモジュールを用意した方が楽になります．
1. Synthesijerにより生成された回路を正しく動作させるための論理を追加する必要がある
2. FPGAボードの入出力信号の動作と，Synthesijerの入出力論理の違いを吸収する
3. FPGAボードのピンアサインと入出力信号の対応付けが楽になる

重要度としては上記の順番なのですが，トップファイルのHDL（ここではVerilog-HDLで記述し，top.vとします）を書く上では逆順がやりやすいので，3番目から順番に説明していきます．

### FPGAボードの入出力信号とのSynthesijerで生成された入出力信号を対応づける
FPGAボードのLEDやスイッチ類はある特定のFPGAのピン番号（PIN_AB28など）に接続されています．そのため，通常はHDLのトップモジュールのどの信号をどのピン番号に割り当てるかを手動で設定する必要があります（これをピンアサインと言います）．このピンアサインは回路を変更する毎に，また，FPGAボードを変更する毎にする必要があるのですが，ピン番号はアルファベットと数字の羅列でピンアサインは間違いやすいです．そこで，FPGAボードベンダーはピン番号に分かりやすい信号名を割り振ったピンアサインファイルを配布している場合が多いです．この場合 **トップファイルの信号名をピンアサインファイルと同じ信号名** にすれば，ピンアサインファイルをFPGA用のツールに読み込ませるだけで，適切なピンアサインが完了します．

そこで，トップファイルの入出力信号をピンアサインファイルの信号名にし，トップファイルからSynthesijerでHDLモジュールにした回路をインスタンス化し，必要な信号の割り当てを行います．尚，ここではFPGAボードにAltera社のDE2-115開発教育ボードを使用することにします．

### FPGAボードの入出力信号の動作とSynthesijerの入出力論理の違いを吸収する
Synthesijerで生成される論理回路は，リセット信号が１になったときにリセットがかかる正論理となっています．それに対してFPGAボードの押しボタンスイッチなどは押したときに０になるような仕様のボードが多いです．そこで論理を反転する必要があるので，それをトップファイルで実現することで，スイッチの動作と論理回路の動作の違いを吸収します．

### Synthesijerにより生成された回路を正しく動作させるための論理の追加
これは主にトップクラス（SortTop.java）のpublicなフィールド変数に関する処理です．publicなフィールド変数はクラス外に値を出力できるようになっている一方，Synthesijerにより生成された論理回路はクラス外から値を書き込むための制御線（ライトイネーブル，we）を入力ポートとして持っています．特に何もしない場合，このライトイネーブルが不定値となり，publicな変数へのアクセスが正しく行えなくなります．そこで，特に書き込みなど行わないのであれば，このライトイネーブルを0にしておく必要があります．

### トップモジュール(top.v)の記述
以上を踏まえて記述したトップモジュールが以下になります．

```v:top.v
module top(input CLOCK_50,
	   input [3:0] KEY,
	   output [7:0] LEDG,
	   output [17:0] LEDR );

   SortTop sort(
		.clk(CLOCK_50),
		.reset(~KEY[0]),
		
		.run_req(~KEY[1]),
		.run_busy(LEDG[7]),

		.start_flag_we(1'b0),
		.start_flag_out(LEDG[0]),
		
		.done_flag_we(1'b0),
		.done_flag_out(LEDG[1]),
		
		.error_flag_we(1'b0),
		.error_flag_out(LEDR[0])
		
		);
   
endmodule

```

以下，トップモジュールの記述内容の解説です．

+ FPGAボードから供給されたクロック信号CLOCK_50を生成された論理回路のクロック入力にしています．
+ FPGAボードの押しボタンスイッチの0番目(KEY[0]）をリセットボタンにしていますが，論理を反転させるために，~KEY[0]としてリセット入力に接続しています
+ 記述したソートのプログラムははrun methodを実行することで動作を開始しますが，それはrun_reqに1を入力したときに動作を開始するような論理回路になっています．そこで押しボタンスイッチの1番目を押したときにrun_reqが１になり，論理回路の動作をスタートさせるようにしています．
+ run_busyは動作中かどうかを示す信号として，緑色LEDの7番目に出力させています
+ publicなフィールド変数として用意したstart_flag, done_flag, error_flagの値はそれぞれ緑色LEDの0番目，1番目，赤色LEDの0番目に出力させています．
+ publicなフィールド変数に，生成された論理回路が正しく書き込みが出来るように，start_flag, done_flag, error_flagに対するライトイネーブル（we）に0を入れています．


## 必要なHDLファイルをライブラリから用意する
Synthesijerにより生成されたHDLファイル（SortTop.v, QuickSort2.v）と上記で作成したトップファイルtop.vをFPGA用の配置配線ツールに入力し，配置配線など行うと，singleportramやdualportramなど，Synthesijerが生成したHDLで使用しているモジュールが不足しているため，エラーで停止するはずです．そこで，Synthesijerが使用しているHDLを~/synthesijer/sinthesijer_lib_20xxxxxx/verilog/　の下からコピーしてきます．VHDLを使用している人はsynthesijer_libの下のVHDLというディレクトリからコピーすればOKです．

## FPGAボードでの実行
無事，FPGAの配置配線ツールで構成情報が作成できて，FPGAボードにソート回路をダウンロードできたら，run_reqを割り当てた押しボタンを押して，ソートを開始させて下さい．その結果，start_flagとdone_flagに割り当てたLEDが点灯し，error_flagを割り当てたLEDが消灯したままであれば，おそらく正しく動作していると思います．