(57)【要約】  商を分配するための配線長が短い除算回路及びこれを備えた半導体集積回路並びにその製造方法を提供する。  ビットスライス部５は、上位ビット側の演算を司る第１のビットスライス部群５ａと下位ビット側の演算を司る第２のビットスライス部群５ｂとに分割されており、第１及び第２のビットスライス部群の間に商選択回路１が配置されており、第１のビットスライス部群５ａは、上位ビットの下半分に対応するビットスライス部５と上半分に対応するビットスライス部５とが交互に、上半分に対応する分は商選択回路１側から順に、下半分に対応する分は商選択回路１とは反対側から順に配列されており、第２のビットスライス部５ｂは、下位ビットに対応するビットスライス部５が商選択回路１側から順に配列されている。
2009119484.tif 000002
【特許請求の範囲】
【請求項１】
半導体集積回路に組み込まれる除算回路であって、
商を生成する商選択回路と、除数及びその倍数、入力部分剰余、及び前記商選択回路の出力である商が入力され、出力部分剰余を生成するビットスライス部とを有し、
前記ビットスライス部は、演算フォーマットで必要とされる分だけ水平方向に配列させたレイアウトであって、上位ビット側の演算を司る第１のビットスライス部群と下位ビット側の演算を司る第２のビットスライス部群とに分割されており、
前記第１及び第２のビットスライス部群の間に前記商選択回路が配置されており、
前記第１のビットスライス部群は、前記上位ビットの下半分に対応するビットスライス部と上半分に対応するビットスライス部とが交互に、前記上半分に対応する分は前記商選択回路側から順に、下半分に対応する分は前記商選択回路とは反対側から順に配列されており、
前記第２のビットスライス部群は、前記下位ビットに対応するビットスライス部が前記商選択回路側から順に配列されていることを特徴とする除算回路。
【請求項２】
前記演算フォーマットで必要とされるビット数の上位の略半分のビットが前記第１のビットスライス部群によって処理され、下位の略半分のビットが前記第２のビットスライス部群によって処理されることを特徴とする請求項１記載の除算回路。
【請求項３】
前記演算フォーマットで必要とするビット数をｎビットとし、前記第１のビットスライス部群での前記ビットスライス部の配列順序は、上位ビット側では前記商選択回路の反対側から、ｎ／４、ｎ／４＋１、ｎ／４−１、ｎ／４＋２、ｎ／４−２、・・・、ｎ／２−２、２、ｎ／２−１、０であり、
前記第２のビットスライス部群での前記ビットスライスの配列順序は、前記商選択回路側から、ｎ／２、ｎ／２＋１、ｎ／２＋２、・・・、ｎ−１、ｎであることを特徴とする請求項２記載の除算回路。
【請求項４】
前記ビットスライス部は、商から除数の倍数を生成するためのセレクタと、前記入力部分剰余から除数の倍数を減算して前記出力部分剰余を生成する桁上げ保存加算器とを有することを特徴とする請求項１から３のいずれか１項記載の除算回路。
【請求項５】
繰り返し法を採用し、
前記商選択回路と、前記ビットスライス部とを繰り返し単位ごとに有し、
任意の繰り返し単位におけるビットスライス部が生成する出力部分剰余を次の繰り返し単位におけるビットスライス部への入力部分剰余とすることを特徴とする請求項１から４のいずれか１項記載の除算回路。
【請求項６】
請求項１から５のいずれか１項記載の除算回路が組み込まれた半導体集積回路。
【請求項７】
商を生成する商選択回路と、除数及びその倍数、入力部分剰余、及び前記商選択回路の出力である商が入力され、出力部分剰余を生成するビットスライス部とを有する除算回路を半導体集積回路に組み込む半導体集積回路の生成方法であって、
上位ビット側の演算を司る第１のビットスライス部群と下位ビット側の演算を司る第２のビットスライス部群との間に前記商選択回路を配置し、
前記第１のビットスライス部群は、前記上位ビットの下半分に対応するビットスライス部と上半分に対応するビットスライス部とを交互に、前記上半分に対応する分は前記商選択回路側から順に、下半分に対応する分は前記商選択回路とは反対側から順に配列し、
前記第２のビットスライス部群は、前記下位ビットに対応するビットスライス部を前記商選択回路側から順に配列することを特徴とする半導体集積回路の製造方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル回路に関し、特に、除算を実現する半導体集積回路に関する。
【背景技術】
【０００２】
近年のＬＳＩの高性能化に伴い、高速な除算部の実現が求められてきている。ＬＳＩで除算を実現するためのアルゴリズムとしては、
（１）減算引き戻し／引き離し法やＳＲＴ除算アルゴリズムに代表される繰り返し法。
（２）Goldschmidt法に代表される乗算器を用いる収束法。
とに分類される。【０００３】
これらのうち、繰り返し法は、面積が小さく実装コストが低いため、プロセッサに広く採用されている。これらの手法については非特許文献１に開示されている。【０００４】
繰り返し法は、本質的に筆算と同じ手順を繰り返す手法であり、３段階の手順から構成される。
（ａ）部分剰余と除数の上位数ビットとを参照して商を決定する。
（ｂ）決定した商から除数の倍数を生成する。
（ｃ）加算器により部分剰余から除数の倍数を減じて次のステップで用いる部分剰余を算出する。
繰り返し法では、上記（ａ）〜（ｃ）の三つの処理を繰り返し実行する。【０００５】
次に、ＬＳＩへの実装を考える。
上記（ａ）を行う回路は、部分剰余と除数の上位数ビットとを参照して商を決定する小規模な回路（以下、商選択回路という）である。これに対し、上記（ｂ）を行う回路はセレクタであり、ビットごとの論理回路をビット数だけ繰り返す、いわゆるビットスライス構造が可能である。また、（ｃ）を行う回路は、加算器を用いるため単純にはビットスライス構造とはならないが、部分剰余の数表現として冗長表現を用い、さらに加減算に通常の加算器ではなく桁上げ保存加算器（Carry Save Adder：ＣＳＡ）を用いることで、桁上げの伝播を高々１ビットに限定することが可能である。この場合には、レイアウトは（ｂ）のセレクタと同様にビットスライス構造をとることが可能である。従って、除算の繰り返し手順一回分は概ね一つの商選択回路と、ビット数分のセレクタ及びＣＳＡとで構成される。【０００６】
図４に、除算器のレイアウトの一例を示す。これは演算の基数が２である最も基本的な除算器である。演算のフォーマットとしては、ＩＥＥＥ−７５４基準の倍精度浮動小数点フォーマットを念頭に、５６ビット長を仮定した。図中“Ｑ”で示される矩形は上記（ａ）を行う商選択回路１１、“Ｓ”で示される矩形は上記（ｂ）を行うセレクタ１２、“Ｃ”で示される矩形は上記（ｃ）を行うＣＳＡ１３である。また、Ｒｉ［ｋ］で示される信号が部分剰余であり、Ｄｉ［ｋ］で示される信号が除数である。なお、部分剰余は冗長表現のため、本来は一桁を２ビットで表現する。しかし、ここでは説明の簡略化のため、単一の一点破線で示す。【０００７】
基数２の除算器の場合、部分剰余の上位３ビットを参照することで商を決定できるため、商選択回路１１へは部分剰余の上位３ビットが接続される。商選択回路１１で生成された商は、バッファ１２を介して各ビットスライス構造内のセレクタ１２へ分配される。ビットスライス部１５ではセレクタ１２によって選択された除数の倍数が出力され、次段のＣＳＡ１３によって部分剰余からの減算処理が実行される。【０００８】
ここまでが除算の繰り返し一回分であり、この一回で商が１ビット生成される。また、図４に示すように、この一回分の構造を縦方向に接続することにより、除算の繰り返し処理を順次実行し、商を次々に生成することが可能である。このような縦続接続を行う場合、部分剰余の冗長表現を利用することで、桁上げの伝播を高々１ビットに限定でき、規則性を保ったままのレイアウトが可能であるだけでなく、桁上げ伝播による遅延増を抑制できる。一般にこのようなレイアウトはアレイ型のレイアウトと称される。【０００９】
除算機能の実装には、アレイ型のレイアウトが多く採用されている。例えば、非特許文献１に開示された除算器は、規則正しい配列（アレイ）型除算器の構成を示している。また、特許文献１にはアレイ型除算器が開示されており、上位ビットから下位ビットに向けて規則正しいレイアウトを採用していることが見て取れる。さらに、特許文献２には、浮動小数点除算器の実装に関し、倍精度の浮動小数点除算器を分割し、さらに付加回路を付け加えることで、短精度の浮動小数点除算を二つ並列に実行できる除算器が示されている。
【特許文献１】特開２００５−９２３７２号公報（図２）
【特許文献２】ＷＯ２００２／０２９５４６（図１）
【非特許文献１】「算術演算のＶＬＳＩアルゴリズム」、コロナ社、高木直史（ｐ７１，図４．１１）
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、上記特許文献１、２に開示された半導体集積回路には、除数の倍数を選択するために、生成した商を上位ビットから下位ビットまで全ビットに亘って分配しなければならないという問題がある。このため、例えば最上位ビットから最下位ビットへ商を分配する配線が長くなってしまう。これにより、演算速度が低下してしまう。【００１１】
この問題は、各特許文献に開示された手法が上位ビット→下位ビット方向に論理回路を配置していることに起因する。これらの特許文献に提案される手法では、ビット順序を順守したアレイ型の構造レイアウトを採用しているためである。【００１２】
このように、各特許文献に記載の発明は、商の分配距離が長くなってしまうという問題があった。【００１３】
本発明は係る問題に鑑みてなされたものであり、商を分配するための配線長が短い除算回路及びこれを備えた半導体集積回路並びにその製造方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するため、本発明は、第１の態様として、半導体集積回路に組み込まれる除算回路であって、商を生成する商選択回路と、除数及びその倍数、入力部分剰余、及び商選択回路の出力である商が入力され、出力部分剰余を生成するビットスライス部とを有し、ビットスライス部は、演算フォーマットで必要とされる分だけ水平方向に配列させたレイアウトであって、上位ビット側の演算を司る第１のビットスライス部群と下位ビット側の演算を司る第２のビットスライス部群とに分割されており、第１及び第２のビットスライス部群の間に商選択回路が配置されており、第１のビットスライス部群は、上位ビットの下半分に対応するビットスライス部と上半分に対応するビットスライス部とが交互に、上半分に対応する分は商選択回路側から順に、下半分に対応する分は商選択回路とは反対側から順に配列されており、第２のビットスライス部群は、下位ビットに対応するビットスライス部が商選択回路側から順に配列されていることを特徴とする除算回路を提供するものである。【００１５】
また、上記目的を達成するため、本発明は、第２の態様として、上記本発明の第１の態様に係る除算回路が組み込まれた半導体集積回路を提供するものである。【００１６】
また、上記目的を達成するため、本発明は、第３の態様として、商を生成する商選択回路と、除数及びその倍数、入力部分剰余、及び商選択回路の出力である商が入力され、出力部分剰余を生成するビットスライス部とを有する除算回路を半導体集積回路に組み込む半導体集積回路の生成方法であって、上位ビット側の演算を司る第１のビットスライス部群と下位ビット側の演算を司る第２のビットスライス部群との間に商選択回路を配置し、第１のビットスライス部群は、上位ビットの下半分に対応するビットスライス部と上半分に対応するビットスライス部とを交互に、上半分に対応する分は商選択回路側から順に、下半分に対応する分は商選択回路とは反対側から順に配列し、第２のビットスライス部群は、下位ビットに対応するビットスライス部を商選択回路側から順に配列することを特徴とする半導体集積回路の製造方法を提供するものである。
【発明の効果】
【００１７】
本発明によれば、商を分配するための配線長が短い除算回路及びこれを備えた半導体集積回路並びにその製造方法を提供できる。
【発明を実施するための最良の形態】
【００１８】
図２に示すように、本発明に係る除算回路は、商を生成する商選択回路１と、除数及びその倍数、入力部分剰余、及び商選択回路１の出力である商が入力され、出力部分剰余を生成するビットスライス部５とを有し、ビットスライス部５は、演算フォーマットで必要とされる分だけ水平方向に配列させたレイアウトであって、上位ビット側の演算を司る第１のビットスライス部群５ａと下位ビット側の演算を司る第２のビットスライス部群５ｂとに分割されており、第１及び第２のビットスライス部群の間に商選択回路１が配置されており、第１のビットスライス部群５ａは、上位ビットの下半分に対応するビットスライス部５と上半分に対応するビットスライス部５とが交互に、上半分に対応する分は商選択回路１側から順に、下半分に対応する分は商選択回路１とは反対側から順に配列されており、第２のビットスライス部群５ｂは、下位ビットに対応するビットスライス部５が商選択回路１側から順に配列されていることを特徴とする。【００１９】
このような構成とすることにより、商を分配するための配線長が短くなるため、演算速度を向上する。【００２０】
以下、本発明の好適な実施の形態について図面を用いて説明する。【００２１】
〔第１の実施形態〕
本発明の好適な実施の形態について説明する。
図３に、本実施形態に係る半導体集積回路を示す。セレクタ２及びＣＳＡ３で構成されるビットスライス部５は、概ね全ビットの半分となるビット数で分割されている。例えば全５６ビットであれば、上位２８ビットと下位２８ビットとに分割されている。
レイアウト上中央の位置に商選択回路１が配置されている。商選択回路１で生成された商は、バッファ４を介して各ビットスライス構造内のセレクタ２へ分配される。ビットスライスではセレクタ２によって選択された除数の倍数が出力され、次段のＣＳＡ３によって部分剰余からの減算処理が実行される。【００２２】
商選択回路１は、下位２８ビット分については、一般的なレイアウトが採用され、商選択回路１の右側に配置されている。上位２８ビットについては、さらに半分に分割されており、後半の１４〜２８ビットまでは１ビットずつ間を空けて配置されている。前半の０〜１３ビットは、同じく１ビットずつ間隔をあけて、配置するビット順方向を逆向きとし、中央の商選択回路１の側に０ビット目が位置するように配置されている。
図４に、ビット位置のみに着目してその配置を示す。【００２３】
このようなレイアウトを採用したことにより、商選択回路１の出力である商を分配する配線長は、図１に示した構成と比較して約半分に限定されている。【００２４】
また、商以外の配線について、図１に示した構成と比較しつつ説明する。
下位ビット側半分については図１に示した構成と同様である。上位ビット側半分については、下位ビット側が１ビット分の距離しか配線されないのに対して、２ビット分の配線長となる。しかしながら、各ビットスライスは高々セレクタ１個及びＣＳＡ１個で構成されるものであり、１ビットスライス分配線長が伸びたとしても、商の分配距離を半分にすることと比較するとその影響は軽微であり、これに起因する遅延の影響は無視できる。【００２５】
このように、本実施形態に係る半導体集積回路は、除数選択セレクタ及びＣＳＡで構成されるビットフライス部分を二分割して商生成回路をレイアウト上の中央に配置しているため、商を分配する配線長が図１に示す構成の約半分であり、演算速度が向上する。【００２６】
〔第２の実施形態〕
本発明を好適に実施した第２の実施形態について説明する。
本実施形態に係る半導体集積回路の構成は第１の実施形態と同様であるが、演算の基数として“４”が採用されている点が相違する。【００２７】
基数が“２”の除算器と基数が“４”の除算器とを比較すると、下記の点で相違する。
（Ａ）除数の倍数のバリエーションが増えるため、ビットごとに３倍数を必要とする場合があり、セレクタ２のウェイ数が増加する。
（Ｂ）商選択回路１に入力する部分剰余のビット数が増え、また、除数の上位ビットを必要とする場合がある。【００２８】
しかしながら、上記（Ａ）については、ビットスライス部分の入力・出力が全ビットとも同様に変化し、ビットスライス部分の論理が全体として同様に変化するため、レイアウトとしてはビットスライス構造を維持することが可能である。
また、（Ｂ）については、非特許文献１の第７４頁に記載されているように、部分剰余の上位７ビットと、除数の上位４又は５ビットとを参照すれば、商を算出することが可能であり、基数“２”の場合と比較して、参照ビットが高々９ビット増加するのみである。
このように、上記（Ａ）、（Ｂ）の相違を考慮しても、ビットスライス構造を維持することが可能であり、図３に示した第１の実施形態と同様の構成を採用することが可能である。【００２９】
この他の点に関しては第１の実施形態と同様であるため、重複する説明は省略する。【００３０】
なお、上記各実施形態は本発明の好適な実施の一例であり、本発明はこれらに限定されることなく、様々な変形が可能である。【００３１】
この出願は、２００８年３月２５日に出願された日本出願特願２００８−０７８７９１を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図面の簡単な説明】
【００３２】
【図１】除算器のレイアウトの一例を示す図である。
【図２】本発明に係る除算回路の構成を示す図である。
【図３】本発明を好適に実施した第１の実施形態に係る半導体装置の構成を示す図である。
【図４】ビットスライス部の配置を示す図である。
【符号の説明】
【００３３】
１、１１    商選択回路
２、１２    セレクタ
３、１３    ＣＳＡ（桁上げ保存加算器）
４、１４    バッファ
５、１５    ビットスライス部
【図１】
2009119484.tif 000003
【図２】
2009119484.tif 000004
【図３】
2009119484.tif 000005
【図４】
2009119484.tif 000006
【国際調査報告】
2009119484.tif 000007
2009119484.tif 000008