FC2カウンター FPGAの部屋 同期FIFOと非同期FIFO
FC2ブログ

FPGAやCPLDの話題やFPGA用のツールの話題などです。 マニアックです。 日記も書きます。

FPGAの部屋

FPGAの部屋の有用と思われるコンテンツのまとめサイトを作りました。Xilinx ISEの初心者の方には、FPGAリテラシーおよびチュートリアルのページをお勧めいたします。

同期FIFOと非同期FIFO

”Spartan3A Starter KitのDDR2 SDRAMコントローラIOテストモジュールのシミュレーション2”でCore Generatorで生成したFIFOがフリーランクロックでないとおかしくなる件だが、結局、XilinxCoreLibフォルダのFIFO_GENERATOR_V4_4.vを見てもよくわからなかった。
この上は、自分で非同期FIFOを作ろうか?と思って、調べていたら、Asynchronous FIFO(verilogのサンプル)を見つけたが、これを非同期リセットに書き換えてやってみたが、まだシミュレーション結果がおかしい。
そのほかに、非同期FIFOの資料はSunburst Design, Inc.のSimulation and Synthesis Techniques for Asynchronous FIFO Designがあったが、結構長いので、あまり読む気がせずに困っていた。
検索していると、なつたんさんの”FPGAで非同期のクロックを扱う方法”がヒット。そういえば、私も"Advanced FPGA Design: Architecture, Implementation, and Optimization"を買ったんだった。
さっそく、職場にあったので、取りにって見てみると、96ページにありました。そのものばっちりの図が。Figure 6.14 Simplified asynchronous FIFO.です。図を見たら一発でわかりました。(誤解しているかもしれませんが。。。)初めてこの本を買ってよかったと思いました。

ちょっと説明を加えると、非同期FIFOはWriteのクロックとReadのクロックが非同期だ。なので、普通の同期FIFOの構成だと、たぶんたまに動作がおかしくなる。
私の考える同期FIFOは下の図のように、Dual-Port Memoryがあって、そのアドレスはBinaryカウンタのWrite CounterとRead Counterから入力している。各カウンタの値でEmptyかFullかを判定するロジックがある。
Synchronus_FIFO_090418.png

ここで、例えば、書き込み側のWrite Counterの値と読み出し側のRead Counterの値が等しくなるときはEmpty、 Read Counter - 1 = Write CounterのときにFullとする。ここで各Counterは4ビットアドレスだとmodulo=16で演算されているのでリングバッファになる。(この辺で図がほしいところだが、面倒なので割愛する)
さて、この同期FIFOの回路でWriteとReadのクロック領域を分けると、Wirte Counterのアドレスの変化とRead Counterのアドレスの変化が同期しなくなる。バイナリカウンタは例えば、"0111"という値の次は"1000"になる。その時に、配線遅延などのために、ビット2~0が"111"から"000"に変化するj時間よりも、ビット3番目の0が1に変わるのが速かったとしよう。そのような仮定に基づくと、ある時間カウンタの値が"1111"に見えるときが出てきてしまう。同期クロックの場合はそのような時間はクロックのすぐ後となり、次のクロックまでには"1000"に安定している。しかし、非同期クロックの場合はタイミングによってはそのような状況が反対側のクロック領域へ影響してしまう。なので、1カウントに1ビットしか変化しないグレイコードを用いる。グレイカウンタならば、一回に1ビットしか変わらないので、"0111"の次を"1111"に間違うようなことは起こらない。よって、非同期FIFOはグレイコードカウンタを使う可能性が大きい。
私の考えた非同期FIFOは以下のようになった。これは上記の本の図を参考にしている。
Asynchronus_FIFO_090418.png

ここで、わざわざグレイコードをバイナリに直して演算しなくてもいいかも?とは思った。4ビットなのでテーブル持っていてもそんなに大変じゃないと思う。とりあえず上図で作ってみることにしようと思う。
バイナリ-グレイコード変換についてはここグレイコード‐バイナリ変換についてはここを参照する。

ちなみに、相手側のクロック領域のカウンタのカウント値がFFが2つ入ることになる。それによって、Full flagやEmpty flagにどんな影響が出てくるかを考えてみよう。Full GeneratorやEmpty Generatorに入力されるカウント値が遅れるわけだ。Full Generatorで考えると、Read Counter値が遅れてくる。その間にWrite Counterが進むとするとFullが出力されるのが速くなって、Write側の書き込みが、必要以上に早期に止まる可能性がある。これは、フェールセーフの面から言っても安全方向に振れているわけで不正に書き込みができるということはない。Empty Generatorはどうかというと、これも同様で必要以上に早期にEmptyとなる可能性はあっても、データがないのにReadする可能性はない。かくして安全面に振れるのでどちらもOKということになる。

何か間違いがあったら、指摘してください。
  1. 2009年04月18日 22:05 |
  2. IP
  3. | トラックバック:0
  4. | コメント:9

コメント

 こんにちは。
まあ、グレイ・コードとバイナリ・コードは1対1対応ですから、一旦グレイ・コードに変換した後は、グレイ同士で書き込み読み出しポインタの比較を行えば、条件は一致するかしないかですから問題はありません。Dual Portメモリのアドレスに生成したグレイ・コードを直接使っても問題ありません。データが隣り合うアドレスに連続して記憶される必要性もないですから。で、書き込み読み出しポインタの一致・不一致でempty full 判定を行うわけですが、full 判定条件が読み出しポインタが「周回遅れ」で、書き込みポインタと一致したときに・・・というのが条件で、問題は、 一致だけではempty 判定と区別が付かないということですね。で、Sunburst Design, Incの資料では、もう1ビット付け足して、ポインタの奇数回の周回と偶数回の周回を区別し、で、これを別に受け渡すと、またクロック境界の問題が発生するから、全体をグレイ・コードで渡して、で、これが、また別な問題を引き起こしてー・・・と、まあ、キリがないですなー。
 私は、あんまりケチケチせずに、通常は almost full の条件(即ち1個前)で、full 判定を出すとかしています。こうすれば、empty と full の判定条件が異なりますから、余分な付加ビットを付ける必要がありませんし、「FIFOの深さは2のべき乗でなければならない」なんて法律もありませんから^^)。
 でも、結局は、クロック境界を乗り越えてデータを送る際に、間違ったデータが送られることがある・・・っていうのが根本的な問題なんですよね。で、間違っても1ビットしか違わないグレイ・コードに変換して送り込むと。でも結局、間違ったら、emptyおよびfull判定のニゲートが遅れるペナルティがある訳ですから、逆に言えば、送られたデータが間違って伝えられたことが分かれば、安全な方に判定するということで、同様なことが出来るハズです。で、ワン・ホットなシフト・レジスタで、書き込み読み出しポインタ(ビットが立っている位置がポイント位置)を作り、このレジスタ値を渡すことにより(受け渡しが正常ならば、ビットが立っているのは1ビットだけ、間違っていれば、2ビット立っているかゼロ・ホット)非同期FIFOを作ったことがあります。ついでに、このシフト・レジスタ値をアドレス値としてダイレクトに使ったりして(オモイッキリ無駄使い^^;)。
 FIFO深さが浅い場合だけでしょうが、ロジック簡単、高速、しかも、同期用のFFを少なくできるなど・・・、まあ、保証の限りではありませんが。
  1. 2009/04/19(日) 18:04:05 |
  2. URL |
  3. くり #mQop/nM.
  4. [ 編集 ]

くりさん、コメントで教えていただいてありがとうございます。

まあ大丈夫そうということですね。ありがとうございます。自信がつきました。
私もFIFOの深度は2のn乗-1の予定です。シンプルにwrite pointer = Read pointerの時にempty、write pointer +1 = read pointerのときにfull判定の予定です。
グレイコードカウンタの出力をそのままDual-Port RAMに入れても大丈夫だなと思っていましたが、グレイコードで演算する方法が分からなかったので、バイナリに直そうという結論になりました。

くりさん独自の非同期FIFOを紹介していただいて、ありがとうございました。たしかにワンホットを使うというのは良いですね。もっとFIFOの深度が深い場合は、誤り訂正、検出符号を使っても良いかもしれませんね?将来の課題としたいと思います。
  1. 2009/04/20(月) 05:37:08 |
  2. URL |
  3. marsee #f1oWVgn2
  4. [ 編集 ]

おはようございます。いつもこちらのサイトで勉強させていただいてます。

さて、非同期FIFOでしばしばグレイコードが使われるのは、コードの性質上非同期で読み取っても必ず正しい値(更新前の値か後の値かのどちらか)が得られるからですよね。グレイコードを使う限り、シミュレーションでは前か後かが決まらず X が出ることがあったとしても、実際に動かすときには同期用の2段 FF は必要ないのだと思っていたのですが、上記回路の FF の意味はどのようなものでしょうか?勉強不足ですみません。もしよろしければ教えて下さい。(ワンホットだと2ビット操作なので非同期読み取り自体ができないのは理解しているのですが)

逆に、もし2段 FF + バイナリ変換程度の遅延を許すのであれば、始めからバイナリコードでポインタを持たせ、異なるクロック間をハンドシェーク (request ビットを立てて ack で応える形) で受け渡せば、グレイコードとバイナリの変換は必要無いように思えます。

何か私が根本を理解していないのかもしれないのですが・・・
  1. 2010/05/10(月) 07:04:17 |
  2. URL |
  3. takeuchi #-
  4. [ 編集 ]

takeuchiさん、こんにちは。
>非同期FIFOでしばしばグレイコードが使われるのは、コードの性質上非同期で読み取っても必ず正しい値(更新前の値か後の値かのどちらか)が得られるからですよね。
これは、違うと思います。異なるクロック間の伝送では、クロックのどのタイミングで入力が変化するかわからないので、FFのセットアップ時間が間に合わない場合は、メタステーブル状態になる可能性があります。グレイコードで受け渡しするにしても、この状態は避けられないわけです。そこでFFを2段(1段でも良いと思いますが、念のため。10万回に1回間違って嫌なので。。。)いれて、メタステーブル状態を回避しています。

>逆に、もし2段 FF + バイナリ変換程度の遅延を許すのであれば、始めからバイナリコードでポインタを持たせ、異なるクロック間をハンドシェーク (request ビットを立てて ack で応える形) で受け渡せば、グレイコードとバイナリの変換は必要無いように思えます。
この実装もありだと思います。ただ、その場合は、requestビットを立てるタイミングはバイナリカウンタのFFを駆動するクロックよりも位相を遅らせるか、もしくは、バイナリカウンタが変化した1クロック後にする必要があると思います。requestを解除するタイミングは、位相を早めるか、もしくはバイナリカウンタを変化させる1クロック前までですね。私はハンドシェークをするロジックを実装するよりも、(ステートマシンを実装したりすると、思いもかけずにレアなケースでミスる場合もありますし。。。)グレイコードで実装しました。
  1. 2010/05/10(月) 08:51:11 |
  2. URL |
  3. marsee #f1oWVgn2
  4. [ 編集 ]

お返事ありがとうございます。
回路設計はまだ初心者で、メタステーブルについても本で読んだ記憶はあるものの、実感として身についていないためによくおかしなコードを書いてしまいます(困

前半部分、FFを省略できないという点について、よく分かりました。

後半部分も、ハンドシェーク用の信号をFF二段で受ける回路をまじめに考えると、遅延時間はまだしも更新頻度ががた落ちになってしまいますね。
そんなものを非同期 FIFO に使ったのでは、marsee さんの回路にはとうてい及ばない性能になってしまうことが理解できました。

大変勉強になりました。今後ともよろしくお願いいたします。
  1. 2010/05/10(月) 11:43:04 |
  2. URL |
  3. takeuchi #-
  4. [ 編集 ]

はじめまして

はじめまして、参考になる情報ありがとうございます。
これはGlayのカウンター(4bit)を相手のクロックドメインのF/Fに
渡しているように見えるのですが、4bitのバスがF/Fに同時に
到達するという保証をどこかでしていますでしょうか?
  1. 2012/06/14(木) 23:23:16 |
  2. URL |
  3. CH4 #ayvbiZiw
  4. [ 編集 ]

はじめまして。
Glayカウンタの4ビットは異なるクロックドメインの領域に同時に到着しなくても良いんです。だからGlayカウンタを使用しています。Glayカウンタは1度に1ビットのみ変化します。つまり他のビットは変化がないので、とんでもない数に間違うことはありません。
相手方のFFのセットアップ時間を考慮する必要はありますが、ここでは4ビットGlayカウンタの各ビットの遅延差が、相手側のクロックドメインのクロック周期の2倍未満に収まっていれば非同期FIFOは動作します。
  1. 2012/06/15(金) 04:49:51 |
  2. URL |
  3. marsee #f1oWVgn2
  4. [ 編集 ]

FIFOのアドレス

有用な記事ありがとうございます。
参考にさせていただきました。自身で調べて追加で分かったことがあります。
FIFOのポインターですがグレイコードのままアドレスとして使用できます。
FULL/EMPTYの判定ののみであればアドレスの一致検出でいいので
グレイコードのまま比較できます。
もし、オールモーストFULL/EMPTYの判定をする場合は
比較の時だけバイナリーコードにする必要があります。
高速非同期FIFOはこの構造が一般的なようです。
  1. 2014/09/09(火) 17:29:34 |
  2. URL |
  3. けんちゃん #JaZ96dNU
  4. [ 編集 ]

Re: FIFOのアドレス

けんちゃんさん、ご指摘ありがとうございます。その通りですね。
多分、元本は、ALMOST_FULL, ALMOST_EMPTY の事も考えに入っているんだと思います。
  1. 2014/09/10(水) 21:03:26 |
  2. URL |
  3. marsee #f1oWVgn2
  4. [ 編集 ]

コメントの投稿


管理者にだけ表示を許可する

トラックバック URL
http://marsee101.blog.fc2.com/tb.php/1085-9e86fbc1
この記事にトラックバックする(FC2ブログユーザー)