計測自動制御学会東北支部弟l 0回研究集会（19賂5．叫
資料番号1甜−14聾択型セルアレイ高速除算器の設計とVtSI評価
Desig血a皿dVISIEYalⅦa血血Of

High−SpeedCelldarArr孔yDiYiderwithSelectionFunction
O日野杉充希♯，恒川佳隆■，吉田等明■，三浦守■OMitsukiHhosu由■，Yoshit血Tsunehwa■，H加akiYoshi血■，MamoruMiⅡa＋■岩手大学■IwateUniversity

キーワード：高速除算器（描かS匹dDi扇d可，セルアレイ（Cdl血A∬町），引放し法印加爬如血g刃富加血m）．Ⅵ一SI評価（Ⅵ．SIEⅦ山慮i皿）
連絡先： 〒0ヱ0 盛岡市上田4・3・5 岩手大学工学部情報工学科
日野杉充希，Tel．01別トヱ1一石亜8，一肌01別ト2ヨー5491，正一ma止血蜘血＠血iⅦ咄叫舶jp

きな閉居点である．

1．はじめに

本論文ではディジタル信号処理などの分これまでに除算器は，ほとんど実用化さ野での実用化を考え，被除数，除数が負のれてこなかった．その理由として，加算や場合でも演算可能であり，また，前行の商減算，乗算などと違い比較一判断をしながビットの生成と次行の部分剰余，CLA信号ら演算が行われるため，回路が複雑となりの生成を並列的に行うという新たな手法をコストに見合った高速性が得られない．ま用いたセルアレイ高速除算器を提案する．

た，普通除算の使用頻度があまり高くない

さらに，単位ゲート遅延を用いて本除算器ことなどが挙げられる．の遅延時間を算出する．そして最後に，しかし現在，ディジタル信号処理やロボⅥ．SI設計システムPAmONを用いてット制御など様々な分野において，高速な本除算器のVLSI評価を行う．

除算暑帥ミ必要とされている．また，膨大なハードウェア土を扱える現在において，従ユ．除算アルゴリズムの選択

来か王．1代表的な除算アルゴリズム

レイ除算器の実現が容易となってきた．
これまでに，いくつかのセルアレイ除算て．遅延時間は語長に比例する値となる．

代表的な除算アルギリズムとして，引戻し法，引放し法．SRT法，反復法などがある句．
引戻し法は，被除軌 除数，共に絶対値表現された正の値しか扱えない．また，部

これが，除算器を設計する上で高速化の大分剰余から除数を引き，その結果を負であ器が提案されているl川．従来の除算器は，各行の演算で部分剰余を必要とするため，1行ずつ逐次的に演算が行われていた．従っ．l．

被除数：〃＝〃。．〃l町・・〝址

るならまた除数を足して元に戻すという操

除数：β＝d。ヰd王・・・d上作を行うため，演算時間が遅くなる．
引放し法は，被除数，除軌 共にユの補部分剰余：P＝几．タl凸・‥几

数表現された負の値でも放え，さらに部分商：e＝恥吼翫・・・亀

剰余：属＝n．1㌢‥巧上剰余から除数を引き過ぎた場合でも，次の演算で部分剰余に除数を足すことにより，とする．なお，添え字の0の付いたものは引戻し陰に比べ元に戻す必要がなく，1行符号ビットである．の演算時間は常に一定である．

以下に，アルゴリズムの手順を示す．

SRT法は，引放し法の演算の加減算に加えシフトだけ行うという演算があるために，ステップ1

引放し法に比べて清算時間は速い．しかし，〃−β むr 〃，βが同符号

書

被除数，除数は．あらかじめ正規化してお＝ ‡かなければならない．また，得られた商は〃＋β むr 〃，βが異符号

ステップ2冗長ヱ進表現されているために，最後に普血rfご＝0如plun也んIdo

通の2進数に変換しなければならない．

h由n

反復法は，乗算器を用いて除算を行うた♪：＝♪血11；

め，乗算器を高速化することにより除算結
鋸＝果も高速に得られる．しかし，直接剰余を求めることが不可能である．また，他の方P，上）が同符号‡ニ富P，βが異符号雄二言法と比べて誤差が大きくなる傾向がある

これらの方法から．ディジタル信号処理，打 飢＝l

打 飢＝0亡nd

ロボット制御などの分野で実用化する場合，ステップ32の補数表現された負の値でも扱えるアル葺＝曾．・飢翫・・・恥＿11

ゴリズムとして，本研究では引放し法を基に考える．

虎＝2￣エ・P

3．従来の引放し法による王．ユ 引放し法アルゴリズム

セルアレイ除算器

本節では引放し法アルゴリズムを鋭明す

これまでに，引放し法によるセルアレイ

る．語長が2エビットのとき全ての値が符号ビット，除軌 部分剰余，商はエ＋1ビット除算器が提案されている礼3）．セルアレイとは．セルという最小単位の回路をアレイ上に規則正しく並べた構成をいう．よって，である．よって，セルアレイは回路の設計や拡張が容易であビットを持つので，被除数，剰余はヱエ＋lり，ⅥjI向きと言える．その中の高速な除算器として代表されるのが，キャリーセーブ方式とCLA回路を用いたものである．本．ヱ．

（a）Aセル巾）Sセル帥 裳ビット型CLA／キャリーセーブを用いたセルアレイ除算器

図ICL〟キャリーセーブを用いたセルアレイ除算器
章では，こや除算暑削こついて述べる・なお，ている．これが，キャリーセーブ方式であ

この除算器では引政一法を用いているが，る．

被除数，除数ともに正の僻しか扱えない．

また，部分剰余の符号ビットを高速に生成するために，CLA回路を用いて符号ビッ

3．1高速化の手法トー、のキャリーを生成している．
これらの手法を用いたこの除井器の遅延

この除算器では，CLAとキャリーセーブ

時間は，括長〃のときロ（州喝叩の値となる．の手法を用いて高速な除算器を実現している．

3．ヱ1軋成法

除算器を桁上げ伝播加算器で実現する場

合，各演算でキャリーが完全に伝播するこ

前述の手法を用いた除算器は，3種類のとを必要とするため，遅延時間は非常に大セルから構成される．

きなものとなる．しかし，この除算器ではAセルでは，主に和昂とキャリーqのベ部分剰余を和とキャリーのベクトルに分けクトルに分解した部分剰余を，全加算器にることにより．得られたキャリーベクトルよって生成する（図1（a））．また，CLA信をその行で伝播せずに次行の演算で加算し号生成のための生成信号qや伝播信号巧．3−

ヱ．三部のアルゴリズムで説明したように，もここで生成する．

Sセルは各行に1つずつ用いており，仮前述の除算器は．各行で部分剰余と除数のの符号ビットを生成する（図1（叫．そし符号を比較して商ビットを決め．この商ビて，この信号とCLA信号をⅩOR（排他的ットによって次行の演算を決定するため，論理和）をとって符号ビットを生成し，こ演算はl行ずつ順次行われていく．これは，の借号が次行のSセルに入力され商ビット引放し法に限らず，引戻し法，SRT法など￠一を生成する．

前行の部分剰余を必要とする除算法は全てそうである．これが．一般的に他の演算器

CLAセルは各行に1つずつ用いており，各Aセルで生成された生成借号Gや伝播信と比べて除算器が遅いといわれる最大の理号Pがこのセルに入力され，符号ビット生由である．しかし，引放し法において各行成のためのCLA信号Cエを生成する（図の制御信号となる帝ビットはたかだか0と1（c））．

1しかない．よって，前行の商ビットが決

この除算器の語長が8ビットのときの全定する前に商ビットが0と1の場合の演算を行うことにより先行演算が可能となる．

体の構成を囲1（d）に示す．

これが，新たな手法の基本的な考え方であ

4．選択型セルアレイる．

なお，この手法を用いた本除算器を選択高速除算器型セルアレイ高速除井器と名付ける．

4．1新たな高速化の手法

本手法の具体的手順を以下に示す．

墾翠の除算翠
1行目
部分剰余

CIA借号

ヱ行目

繭ビット

CL九倍号

部分剰余

本除算器
1行目

部分剰余

CIA借号

商ビット

ユ行目

固主 部分剰余生成時間削減の実現

−ヰー

ユ行目

商ビット

部分剰余

CIA信号

4．王 構成牡● 部分剰余生成時間の削減
本除算器の構成は4種類のセルで構成すまず本手法の第1段として，前行の商ビる．

ットが決定する前に，商ビットが0とlの8セルでは，商ビットが0の場合の部分場合の次行の部分剰余を先に生成するよう剰余（和叫，キャリーCqI）とlの場合のに考える．これによって，加減算の遅延時部分剰余（和叫，キャリーClノ）をユつの間を削減することができる．この考え方を全加算器によって生成する（図3（a））．そ

図ユに示す．

して，商ビットが決まってから部分剰余をこの実現法として，部分剰余を生成するセレクタによって選択する．また，CLA信セルに加算用と減算用の2つの全加算器を号生成のための生成信号や伝播借号も商ビ用いる．また繭述の除算器では，固1（d）にットが0性成信号G帆伝播信号叫）と示すように，最右端のセルのキャリー入力

1（生成信号Glノ，伝播借号叫）の場合をに腑行の商ビットを入力するようになってAND，0且ゲートを三つずつ用いて生成すいた．しかし，本手法でそうした場合，そる．のセルだけが商ビットが決定しないかぎり

Rセルは各行の最右端に用いるセルであ演算を行うことができない．そこで，新たる個3仲））．動作はBセルとほぼ同じで，に最右端用のセルとしてRセルという新し最下位ビットの部分剰余の生成を目的としいセルを用いる．ている．しかし，この部分にRセルという新しいセルを用いた理由は，4．1飾で述べた● 亡LA信号生成時間の削減

ようにこの部分にBセルを用いてキャリー前述の実現陰によって，部分剰余の生成入力に商ビットを入力するよう設計すると，時間を削減することができた．しかし，さこのセルが最大遅延パスとなり本除算器のらに検討してみた結果，CLA信号の生成時利点が活かされない．よって，全加算器の間が最大遅延パスとなることがわかった．

キャリー入力に加算演算用には 0，を，またそこでCLA借号も，商ビットが0とlの場■減算演算用には 1Iの定数を入力すること合を先行演算するように考える．よって，によって．この間層を解決している．

CLA信号の生成時間を削減することが可

Cuセルは各行に2つずつ用いており，能となる．

それぞれ商ビットが0とlの場合のCu信この実現法として，まず部分剰余を生成

号を生成する．なお，CLAセルは前述の除するセルでCLA信号生成に必要な生成倍算器で使われたCLAセルと全く同様のも号，伝播信号をそれぞれ商ビットが0と1のである（図1（G））．の場合を生成する．そして，各行に商ビッ

qセルは各行に1つずつ用いており，符トが0と1の場合のCu信号生成を行う

号ビット 商ビットの生成を目的としていCLAセルを2つ用いる．

る（固ヨ（仁））．まずqセルでは，商ビットが0と1の場合の最上位ビットの部分剰余・5・

町J亡J・J

血Jd畑

伽 qセル

（a）BセルⅣ●■■■■●■■■■■l〃i 叫

鴫叫 叫l（C）Rセル

R′斤J 句

和 句（朝■ 葛ビット型選択型セルアレイ高速除算器

囲3 選択型セルアレイ高速除算器の構成

一占一／￣ ヱ仏芸ご

従来の除算器
1行。
部分剰余

CL九倍号

3行目

CIA倍音

部分列

商ビット

商ビット

2行目
部分剰余

CLl悟号
ユ行目

部分剰余

CI正信号

商ピサト

図ヰ：遅延時間による比較を生成する．そして，商ビットが0と1の算器の演算プロセスを説明するが，そのた場合の右隣のBセルからのキャリーをセレめに回ヰのl行臥ユ行臥3行目に注目しクタによって遵択し，その結果をⅩOR．ゲていただきたい．

ートによって符号ビット葺を生成する．さ基本的に．従来の除算器と本除算器の各らに，その符号ビットが次行のqセルに入行の演算プロセスはほとんど同じである．

力され，除数の符号と埠較し商ビットぜ

まず1行目の演算は，初回の制御信号の生を生成する．なお，従来の除算器では被除成を待たずに開始している．これは，本除軌 除数が正の値しか扱えないが，本除算算器では制御信号が0と1の場合の部分剰兼では負の値でも扱える機能をこのセルの余を先ヒ演算できるからである．そして1に拡張した．

行目の演算は順次に行われていくが，その本除算器の語長が8ビットのときの全体間にもヱ行目の演算がすでにl行目の部分の構成を図3（t研こ示す．

剰余の生成が終わった時点で開始している．
これは，初回の制御信号がすでに決まって5 遅延時間いるので．三つのパターンの部分剰余を制5．1演算プロセス御信号によらて選択するのみとなっている

本除算器の演算プロセスは，固ヰに示すように従来の除算器と異なる．以下に本除われていく．さらに，その間にもl行目のためである．そしてヱ行目の演算も腑に行商ビットが生成された時点で3行目の演算．7．

10ビット未満のとき6A，10ビット以上の部分剰余生成ときもA（これは最大フアンイン数を8とし1

CLA生成

部分剰余生成

商ビト生成

皿A生成

た場合，CLA回路をヱ段にしなければならないことによる），また，商ビットは10Alとなることからそれぞれの除算器のl行当
商ピッ生成

細分背生成
CLA信号生成部分弄生成l
商ビット生成CLA悟号生成

1たりの遅延時間は．
A山一髄射 ＝21A＋A皿1

A伽休耕馴 ＝23A＋A乱1

1

部分剰余生成となる．なお本除算器と従来の除算器との1CLA生成

差がヱAあるのは，本除算器ではqセルで商ビト生成

商ビットが0と1の場合のCu信号．部分剰余の最上位ビットの和とキャリーを選択

図5 本除算器の演算プロセスするためである．
よって，各除算器は〃り行あるので，が開始している．これもすでにユつのパターンの部分剰余はユ行目の演算ですでに生A従兼＝（ユ1A＋A皿．岬／2＋8A…（1）成されており，1行目の商ビットによってA神事♯三（エコA＋A皿．）〃／4−2A…（2）i畢択するのみとなっているためである．
よって，土の固から容易に2行目，4行となる．なお，従来の除算器では〃／ヱかけ目など偶数行の遅延時間が削減できることているのに対し本除算器で〃／イかけていがわかる（固5）．このことから，従来のるのは，5．1師で述べたように本除算器は偶除算器の遅延時間は籍長に比例する値とな数行の遅延時間が削減されるためである．

るが，本除算器では蒔長の半分に比例する

よって，（1），（2）の式から容易に，値となる．
血相鼎＃A桝／2

5．ユ 単位ゲート遅延を用いた遅延時間の算出となることがわかる．

次に，本除算器の遅延時間を単位ゲート遅延を用いて算出する5）．

．PARTHENONによるVl別評価

基本的に本除算器と従来の除算器の各行町演算プロセスは同じであり．部分剰余の本研究ではさらに，Ⅵ．Sl設計システム

生成，亡u信号の生成，商ビットの生成とPARTHENONにより本除算器を設計し，いう順に行われてい〈．それぞれの生成時

Ⅵ．SI評価を行った．

間は，部分剰余はTA，Cu信号は語長が．♯−．1VLSI設計に行うという新たな手法を用いた選択型セルアレイ高速除算器を提案した．さらに，本除算器を設計するために，本除算器をVLSI設計システムPARTHENONによってSFL言語で記述した．PARTHENONで時ト

本除算器を設計しⅥ一Sl評価することによップダウン設計が可能であるので，各セルって，従来の除算器よりユ倍以上高速なもをサブモジュールとして扱うことにより容のを実現できた．

易に設計することができる句．ま．た，本除算器を任意の語長に設計できるよう，本除参考文献

算器のSFLソースを自動作成するプログラl）Dcaql，K．J∴BharyDivisionUshgaData

ムをC昔話によって実現した．

Dep仇dentIteradYeArrays，ELectT・OnicsLetFerT，丘．王 VLSI評価

Vol，4，ユ8ヨ／284（19朗）

SFL言語で記述した本除算器を回路シミ

2）Guild，H．H．：Som∈CcllularLogicATrayS血rュレータSECONDSによって動作確認し，Nonr∈或0血gB血町Divisio叫乃g血亜￠α靴JさらにシンセサイザSFLEXPで論理合成し，

曲c．血gれ，Vol．39，345／34糾1970）

最適化ユーティリティOPTJMAPによって3）C叩pa，M‥皿d H抑Ⅶ血町 Ⅴ．C．：A皿

テクノロジ・マッピングと回路の最適化を

An卯ICnt6dItcratiYC Array for High−Speed

行った．さらに．本除算器を語長を6ビッ

B血ⅣDil鹿io叫戯Eg加．州Cロ叩P打相和，トから3エビットまで変えてVLSI評価した．

Vol．C・22，1Tヱ／1丁5（19丁3）

評価対象を消費奄九面積，ゲート軌 商の生成時間，剰余の生成時間とし，結果をヰ）高木直史，安浦寛人，矢島修三：冗長2

囲6に示す．なお，用いた設計ルールは進表現を利用したVLSl向き高速除算器，

0．叫mCMOSスタンダードセル（VLSIテク

電子通信学会論文誌，Ⅴ01．J6丁−D N0．ヰ，ノロジー社）である．

450／45丁（1！柑4）

囲叫d）の商の生成の遅延時間からみても，

5）K．伽mg：Comp山町ArithmcticIPrincipl∈S，

本除算器は従来の除算器より2倍以上高速

Architecturc，and Dcsi騨1，Jolm Wilcyになったことがわかる．具体的に，語長がSo耶（19丁9）ヱ4ビットのときで従来の除算器よりもヱ．35
倖の高速化を図ることができた．しかも，

6）pARTHENONUs訂消斉電力，ゲート数ともに1．了5借，面積は通信（株）（1990）

1．糾借と，いずれも2借以下となる．

丁．おわりに本研究において，前行の商ビットの生成と次行の部分剰余．CLA信号の生成を並列

一9一sMmal，mデータ

180（抑1脚O14∝巾

消1別刷）
♯t

10000

匡宝冠

方8000
6000
40（XI
ユ000
0610141＝ユユ6卸6101418ユ王ユ＝0 匝叫tb呵

ビット長ビット曇伽 面積（可 ＝掛費電力

匡宝冠l（l lヰ l嚢 ユ王 ユ古 30

后 l0 1ヰ 1書 王ユ 王占 ユ0

ビット暮ビット轟（d）遅延時間（商の生成時間）（可 ゲート数101ヰ18ユユ王占ユ0 匹叫
ビット長㈱・遅延時間（剰余の生成時間）

図占 従来の除算器と本除算器のⅥ一SI評価

ー10−