計測自動制御学会東北支部第161回研究集会（1996．6．28）
資料番号161−6

データ点数・語長を変えたWSIFFTプロセッサの冗長化設計

RedundancyDe8ignofWSIFFTProce自白Or自VaryingNumberofDataPointsandWordLength0金沢正治，苫米地宣裕
OShyoujiKana2：aWa，NobuhiroTomat）eChi
八戸工業大学

HachinoheInstituteofTechnology
キーワード：冗長化（redundancy），WSI，FFT，高速（high印eed），システム構成（sysbmde6ign）
連絡先：〒031 青森県八戸市大字妙字大開88−1八戸工業大学電気工学科
苫米地研究室金沢正治，Tel．（0178）253111，Faェ．（0178）24−1430

1．はじめに

2．非冗長FFTプロセッサの設計

現在、画像唐号のディジタル化と共に、画像

2．1 FFTの仕様の設定

信号をリアルタイムで処理可能なFFTプロセ

FFTの仕様は表1の様に設定する。

ッサの実現が期待されている。そのような高速FFTプロセッサは、全ての演算をハードウェ

表1 FFTプロセッサの仕様
次元：1次元アで構成する必要があり、WSI規模の集積度

サンプリング周政教壬：10MHzを必要とする。本研究者らは、このWSI規模

データ点数のFFTを、冗長化手法（欠陥救済法）1）の導リアルタイム性入によって、歩留りの低下なしに構成する方法

語長9種類のFFTの冗長化について報告している。

：リアルタイム動作

D：12〜20bit
固定小数点を検討してきた。本稿では、データ点数と、演算精度を表すbit数（語長）を変化させた、

N：512〜2048点

基数r：2

間引き方式

：時間間引き方式

素子：CMOS素子

特に、冗長化設計において、冗長な配線と切り替えスイッチを含めた、冗長なチップ面積の合計が最小となるように条件を求めている。

ここで、データ点数は512点、1024点、2048点、語長は12bit、16bit、20bitとし、計9種類のFFTについて冗長化設計を行う。表1の仕様を満足するには全という構成になり、もしバタフライ1個てのバタフライをハードウェアで構成する必要のレイアウトが正方形ならば、システムがある。バタフライ演算は複素入力A、B及び全体は50対1という極端な長方形とな回転子Wk（ここでWはデータ点数Nに関する複り、制作が困難となる。

素指数関数であり、kは整数である）に対して1 の問題の対策として、本稿ではバタフ

A，＝A＋WkBとB＝AWkBの出力を得る

ライ間の相互配線における信号伝送を8bitものであり、この演算の実現には加算器を6個、直列伝送とすることにしている。信号の直並列乗算器を4個必要とする。データ点数N＝2巾

変換は、バタフライの入出力段に送信・受イ言用点のFFTは、mXN／2個のバタフライを必のバッファレジスタを取り付けて行う。これは要とする。仮に、N＝1024点では、段数がFFTをパイプラインで処理する際に必要なレ10段のバタフライ列（これをパイプラインのジスタの機能と併用できるため、この回路の付列と定義する）が512列必要となる。従って、加によるチップ面積の増加は少ない。バップ7

システムはバタフライを図1の様に配列したもレジスタの動作クロックはFFTの動作クロッのになる。

クの8倍の80MHzとなり、処理時間はFFTのパイプライン処理にマッチしており、信号の直列伝送によるFFT処理時間の増加は無視できる。
2 の問題の対策としては、バタフライのレイアウトを出来るだけ横長に設計することで解決している。この方法は、同時にバタフライ間の相互配線のチップ面積を少なくすることにも寄与している。

2．3 非冗長FFTプロセッサの設計
非冗長なFFTプロセッサの論理設計、回路
国一1 FFTの信号流れ図設計、およぴ、レイアウト設計を行い、各回路

Fig．1SignalfloY graph of FFTの構成とチップ面積を明らかにしている。
FFTは、バタフライの段ごとにパイプライ

2．2 FFTプロセッサの問題と対策ン方式で処理を行う。これにより、システムの全ての演算をハードウェアで実現するFFT動作速度はバタフライ1個の動作速度と等しくなる。バタフライの構成は図2の様になる。

プロセッサは次のような問題がある。
1．バタフライ間の相互配線のチップ面積が、バタフライ自身のチップ面積に比較して無視できない大きさとなる。
2．バタフライの配列が、縦方向と横方向で数が極端に異なり、非対象構造となる。

仮に、データ点数が1024点のFFT
では、縦は512個に対して横が10個

図−2 バタフライの構成
Fig．2Structure of a butterfly
2

16bitでは約1：25、さらに20bit

図示したように、バタフライは、送信シフトレジスタ2個、受信シフトレジスタ2個、加算では約1：26となり、どれも横長に設計され器6個、および乗算器4個により構成されていている。

義2 各回路のチップ面積る。加算器は4bitを単位とするキャリー先見方式、乗算暑引まYallaceTree方式を採用して（単位：12）いる。4bitキャリー先見加算器からバタフ

16ライまでのレイアウト設計結果を図3に示す。

20

受信シフトレジスタ 8．18XlO与 1．36Xlげ 2，07Xlげ送信シフトレジスタ 8．18×105 1．36XlO6 2．OTXlげ
加算器

9．81×1げ l．53×1げ 2．23×1げ乗算罪

6．（氾XlO6 1．17）〈10丁 1．80XlOT

バタフライ 3．74）く10了 6．44XlOT 9．83XlOT

表2の結果を基にデータ点数、語長を変えた9種類の非冗長FFTのチップ面積を求めたものを表3に示す。

表一3 非冗長FFTのチップ面積（単位：12）512

10 24 2048

12凱02XlOlb

16

1．55XlOll 3．56XlOll 乱32×101l

20

2．37XlOll

2．08×1011

5．44XlOll

4．86xlOll

1．27XlO12

表3に記されている非冗長FFTの縦横比は、どの場合でも1：1〜1：3の範囲内であり、非対象構造が解消されている。
園−3 バタフライのレイアウト
2．4 冗長FFT設計の指標

Fig．3Layout of a butterfly

FFTの歩留りを計算するにあたり、基準となるチップを設定する。

固3において、素子はCMOSを用いており、レイアウト設計規則は、Me a dConwa y

ある時点の技術水準で、歩留りがある基準

2）の規則をCMOSに拡張して3）用いている。

値：Y。となるチップ面積を基準チップ面積と呼また、Aは基準寸法単位を表している。

び、A。で表す。本稿ではY。＝0．5ととる。

レイア

ウト設計結果をもとに割り出された、FFTの基準チップ面積を有するLS【を基準LSIと各構成要素のチップ面積を表2に示す。表2に呼ぶ。現在の技術水準では、基準LSIはダイは記 されていないが、この時のバタフライの縦ナミックRAMで8Mbit程度であると考え横比は、語長が12bit時は、約1：23、られる。そのチップ面積を前述の設計ルールを3と置き換える。回路の置き換えには基本回路の入出力信号線をスイッチで切り替えて行う。その際、バタフライ間の相互配線の不良に対処するため、相互配線はその配線を入力とする基本回路に含めて取り壊う。このため入力信号線の切り替えスイッチは、前段の基本回路の出力点の直後に設置する。冗長な回路の乗算器の係数及び切り替えスイッチの制御は、レーザーによってヒューズを切断する方法51射を用いる。入用いて求めると、約3XlO912となる。よって本稿ではA。＝3XlO912と設定する。ある対象となるシステムの歩留りがY。に等しいという条件下で、システムのチップ面積が基準LSIの何倍となるかという倍率Fは チップ拡大率 4）と呼ばれ、冗長化設計の指標となるoF≧100がWSI規模を表すと考えられる。
本稿で考察するFFTプロセッサのチップ面積は、表3よりデータ点数512点の3種類のFFT及びデータ点数1024点、語長12bitのFFT以外はすべてF≧100となり、こ力信号線の切り替えスイッチはヒューズ打とバストランジスタで構成される。出力信号線の切り替えスイッチは2個を1組として、ヒューズれらのFFTはWSI規模になることになるo1個、バストランジスタ2個、及びインバータ

3．FFTプロセッサの冗長化設計1個で構成される。

冗長化を行った彼のFFTプロセッサの全体

3．1冗長化FFTプロセッサの構成法

構成を、基本回路を単位とする一般的な形で表

本稿で提案するシステムの冗長化の方法を図したものを図5に示している。

4に示している。

図一5 冗長化FFTプロセッサの全体構成
Fig．50verallstructure of the redundant
FFT processor
図において冗長な回路は、各々がシステム内の任意の回路と置き換えられるよう結線されている。また、基本回路は相互配線を含むので、
図一4 冗長化システムの構成法

その寸法は横方向に行く程大きくなる。

Fig．4Structure of the redundant syste皿

FFTプロセッサの基本回路としてはバタフライを設定するのが最も冗長なチップ面積が小まず、システムを等しい機能を有する基本回

さく、．効率が良くなることをすでに確認してい路に分割し、さらに基本回路と等しい機能を有する予備の回路（冗長な回路）を用意する。不る。従って、本稿では基本回路としてバタフライを用いることにしている。

良となった基本回路がある場合は、冗長な回路
43．2 冗長化FFTの歩留り計算式

冗長な回路のnp個の回路が不良でM−np個の回路が正常］

本稿では、次の仮定と条件のもとに歩留り計算を行っている。

∑（〟C。（l一群

仮定1：欠陥分布はランダム7）とする。

皿）〔l㍍｛〟、刷l／d。x叫＋円1＋｝●＋〃∬＋叩p≦尺

仮定2：電源配願、クロック配線の切断やショ〟C唱（l一軒／」ヅ㍍（叫）肌xートの様な広範囲の障害を生ずる欠陥は生じないとする。
条件1：冗長な配線と切り替えスイッチは、冗長な回路に所属するとして取り扱う。

〟C〝．（1一打抽）〃骨叫）Jf仇m叫￣両

仮定1の下での非冗長なLSlチップの歩留りYは次のように与えられる8）。

＝†m拙富■￣打〝甘苦乃ガ〃1＝0y＝ピー瑚

x〟C岬〟（l一差J〟／」り ∬範（仙㌦〝／止血【壬＝0打〝＝0〃′＝0（1）‡〟C叫（1一打刷）nl打叫）佃ox

ただし、D。は平均欠陥密度を、Aはチップ面積を表している。まず、P r［］は確率を、Hは〟C聖（l一軒／爪）巧乾（叫）硯x

基本回路の横方向の数、Mは基本回路の縦方向の数、Rは冗長な基本回路の数、Aiは横方向ix〟C〃〟（1−範ん／木）月璃〟￣打〟）仙番目の基本回路のチップ面積、Apは冗長な基本〟Cけ．（l一打♪／木） ′打叫）仰○回路のチップ面積、MC。はM個の中からn個を選択する組み合わせの数を表すことにする。こ）（2）のとき、冗長化を行ったFFTプロセッサの歩上式において、min（M，n）は、R＞Mの場合に、留りYRは、次のようになるg）。ただし、nl，n2，‥■，nH≦Mとするための処置である。常に∑ は、n．＋n2＋…・nH＋n。≦Rとなる、R≦Mが成り立っならば、式（2）は次のよう

月l日工＋●……∬川′≦月に簡単化出来る。

叶し抽1■月nl，n2，・■■ ，nH，n。の全ての組み合わせにつ㌔＝…・いて加算を行うことを表している。さらに、叫＝叫l＝0 唱＝0

血in（W，n）は変数M、nの内で小さい方の値を出力する演算を表している。
乾＝

月∬＝0

〝＝0

（〟C叫（1一打ノ」ヅ乾（叫）」1休x〟C。（ト軒／」。r乾（叫）舶×∑pr［叫＋喝−＝＋〝〃相p≦月

1番目の行のnl個の回路が不良でM−n．

xMC〃〟（1−㍍んりヅ〝打山〝〕仙個の回路が正常、かつ、〟C卑（1一打刷）卑範（叫）仙

2番目の行のn2個の回路が不良でM−n2個の回路が正常、かつ、（3）

式（2）または式（3）の計算では、M、H、●●Rの値が大きくなると、計算時間が非現実的な■H番目の行のnH個の回路が不良でMnH値となる。この場合は、いくつかの行を1つに個の回路が正常、かつ、まとめて、そこに含まれる基本回路のチップ面
積は皆等しい（平均のチップ面積を有する）と5‡して計算している。この場合は、行のまとめ方線に起因する制約が生ずる。すなわち、バタフを適切に行うと、近似計算を行っても充分な精ライ演算の最後段のバタフライ1行では、バタ度が得られることが確認されている。

フライの相互配線は、行の上半分の位置にあるバタフライと下半分の位置にあるバタフライの4．冗長化FFTプロセッサの設計間で結線されるので、この1行はサブシステム4．1 設計手順分割をすることが出来ない。同様に後ろから2行目については、2個に分割できるが3個以上本稿では、次の条件の下に最適なシステム構に分割することは出来ない。以下、一般に、後成の冗長化FFTプロセッサを設計している。

ろからn列目は、2h−1以上に分割することは条件2：最適なシステム構成とは冗長なチップ出来ない。このようなサブシステム分割を行っ面積が最小となる構成をいう。

た場合の設計は、手順1を以下のように修正す条件3：冗長化彼の歩留りYRは基準LSIのる。まず、サブシステム分割数をB、i番目の歩留りY。に等しくとる。

サブシステム部分の冗長化後の歩留りをYいi

設計手順は次のようになる。

番目のサブシステムの非冗長なチップ面積の合手順1：式（2）または式（3）を用いてYR＝計値をAti、i番目のサブシステムで必要な、Y。を与える冗長な基本回路（バタフラ冗長な配線、切り替えスイッチを含めた冗長なイの個数Rを求め、冗長なチップ面積バタフライ1個分のチップ面積をA。iとする。

AR＝RApを計算する。

このとき、条件3より、次式が成り立っ必要が手順2：手順1を繰り返し、ARが最′トとなるRある。の値を求める。Rが定まれば、H、M、雪ち…㌔＿．f忘＝㌔

Ai（i＝1〜H）など、システム構成（4）

各Y−の選択には自由度が存在するが、ここでは、を示すパラメータが一意に定まる。

YiはAtlによって決まる次のような値に取る

FFTプロセッサを冗長化する場合、システことにする。

ム全体を一体として冗長化を行うと、1個の冗長な回路が、システム内の全ての基本回路に対4＝d‖＋d∫ヱ＋＝ヰ4臥l＋d鱈して結線する必要があり、一般に冗長な配線のγ＝群山（i＝1〜B）チップ面積の合計値が非常に大きくなる。条件

手順1を、次の手順に置き換える。

2を満たすには、この冗長な配線のチップ面積

手順1 −1：1個のサブシステムについて、式を出来る限り小さくする必要がある。そこで、（2）または式（3）を用いてYR

システム全体を、いくつかのサブシステムに分＝Yiとなる冗長な基本回路の個割し、サブシステムごとに冗長化を行う方法を数Rを求め、これをR．とおく。

検討している。この場合、冗長な回路は特定の手順1 ▼2：手順2 ＿1をi＝1〜Bの間繰り返サブシステムに所属し、そのサブシステム内のす。

回路とだけ置き換えが可能とする。この方法で

手順1

は冗長な回路の個数、および冗長な配線の本数

3＝冗長なチップ面積AR＝RIA。l＋R2Ap2＋‥・＋RBApBとする。

がいくらか増加するが、冗長な配線1本の長さが大きく減少するので、冗長なチップ面積の合4．2 冗長化設計結果計は減少する可能性がある。ただし、縦方向の表4に冗長化設計結果を示している。表には、1行のバタフライを、いくつかのサブシステムシステムを一休としたときと、最適なサブシスに分割しようとすると、バタフライ問の相互配
6（5）テム分割を行ったときの、冗長なチップ面積のFFTの面積」を表している。

また、サブシス内訳、すなわち、冗長なバタフライの面積、冗テム分割の例として、データ点数1024点、長な配線の面積、および切り替えスイッチのチ演算精度16bitのFFTの最適なサブシスップ面積を示している。また、同表の冗長な面

テム分割の詳細を図6に示している。

積の増加率は、「冗長な面積の合計／非冗長な表−4 冗長化設計結果
サブシ 冗長なバ 冗長なバタ 冗長な配線 スイッチの 冗長な面積 冗長な面

データ語長点数

ステム タフライ フライのの面積面積の合計積の増加

分割数 の数 面揮［121

【12】

［12】

［12］率【％］12 28．24XlO86．23XlO9735

1．31XlO9

1．57×109

8．11×10丁40

2．58×1伊1．89XlO10

7．79XlO8

2．22×1010

15

8 2

5．28×10g

2．78×109

1．15XlO甘8．17×10g
5．3

16 5

6．39×109

4．66×1010

1．58XlO9

5．45×1010

10 9

1．07×1010

5．66XlOg

1．92×108

15 62．09）く109

3．52XlO10

1．82XlO91594

3．52XlO91106

6．83×109
16125121620121024

153112031
112202

1．30×1010

18 526 3

2．59×1010

15 75．87×109

3．91XlOlO

18．8

3．9

1．22XlOll

34．3

2．14XlO106．0

1．00×1010

5．52×108

2．17×1011

14．3

1．66×1010
7．0

4．59×109

2．94XlOll

1．62×1010

2．96XlO9
3．3乱08XlO93．33XlO8

8．2

3．23XlOll

59．4

4．26XlOlO
7．8

1．12XlOlO

2．34XlOll

48．1

6 3 3 20 1．20×1010 9．81XlO9 5．06×1が 2．23×1010
4．6
6 320

8．07XlO9

7．37XlOg

2．24XlO8

1．11XlOll

1．82×1010

3 3 72048

4．34XlO93．21XlO＄

2．17×1010
16495

3．19XlOlO

6836．71×1010

7．77XlO11

2．58XlO10

3．21×1010

1．06XlO9

2．39×1012

8．31XlO11

5．87xlO18

8．12XlOlO

7．1

2．54XlO1263 649 6．38XlOlO 5．38×1010 1．83XlO9 1．19XlOll9．4

799．9

200．0

謝辞

ご指導頂いた、八戸工業大学松坂知行教授に感謝致します。

参考文献
1）SwaltェIander E．E，：Wafer ScaleIntegraTtion，Kluwer AcadezDic Publishers（1989）．
2）Mead．C，Conway．L：lntroduction to VLSISyStemS，Addison−Wesley Publishing CoⅡ）
panyInc（1980）．

3）松山泰男，富沢孝：VLSI設計入門，，共立出版社（1983）．
4）苫米地宣裕：冗長化WSlシステムの歩留

l〜6th，7th，8th，9th，10thstageり評価指標，信学論（D−Ⅰ），．丁78−D一I
同一6 FFTプロセッサの最適サブシステム
分割（1028点16bit）
Fig・60ptimumSubsystetA dividing of theNo，3，383／392（1995−03）．
5）RaffelJ．Ⅰ．：Laserlinking for defectavoidance and custotnimt，ion．Proc．SPIE．

FFT processor（1028points，16bits）

Vol．774，93／100（1987）．

6）池田正幸，藤岡知夫他：レーザプロセス技術

5．まとめ
本稿では、画像信号をリアルタイムで処理可

ハンドブック．朝倉書店（1992）．
7）Stapper C．H．：Defect Density Distri−

能なWSI規模のFFTプロセッサを、データ

bution for LSIYield Calculation，IEEE

点数と語長を変化させて冗長化設計を行った結Trans．，ED−20No．7，655／657（1973）．

果を報告した。その際、バタフライ間の相互配線、冗長な配線、及び切り替えスイッチのチップ面積を重視した冗長化を行っている。通常、システムの冗長化の検討には、相互配線の面積、

8）柳井久義，永田譲：集積回路工学（2），コロナ社（1979）．

9）苫米地宣裕：ブロック構造VLSIの冗長化による歩留り向上とその冗長化設計法：

特に冗長な相互配線の面積は無視されることが

信 学 論（D−Ⅰ）lJT91D−I No．5，289／298多い。

（1996）．

冗長化設計の結果、WSI規模のチップ面積を有するFFTプロセッサは、冗長化によるチップ面積の増加が、最大でも非冗長なチップ面積の9．4％あれば、基準チップ面積の歩留り50％で構成できることが明らかとなった。

なお、本稿では欠陥分布はランダムと仮定して設計を行っているが、LSlの欠陥は集中的に発生する傾向があり、このような場合については今後検討する予定である。
8