(57)【要約】  分割回路は、３２ビットの被除数（１６９５）を、被除数の最下位ビットから順に４ビットで分割し、９個の分割被除数（Ｘ０〜Ｘ８）を出力する。最下位ビットを含む分割被除数からの各分割被除数の配列位置をｉ（ｉ＝０〜８）とする。各除算回路は、第１の出力回路によって分割被除数の下位に４の整数倍ビット分の０が付与された値が３（２n−１，ｎ＝２）で除算された８ビットの商を出力する。各除算回路は、第２の出力回路によって、該８ビットの商のうちの上位４ビットの第１のビット列と、８ビットの商のうちの下位４ビットをｉ個並べられた第２のビット列と、を出力する。商加算回路は、除算回路ごとに除算回路から出力された第１のビット列を上位のビット列とし、除算回路から出力された第２のビット列を下位のビット列とした値の合計値を、１６９５が３で除算された商として算出する。
2012086073.tif 000002
【特許請求の範囲】
【請求項１】
２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商を出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
を備えることを特徴とする割り算回路。
【請求項２】
前記第１の出力回路は、
前記分割被乗数の値ごとに２k通りの前記２ｋビットの商を保持し、前記分割被除数ごとに前記分割被除数に応じた前記２ｋビットの商を出力することを特徴とする請求項１に記載の割り算回路。
【請求項３】
２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商と余りとを出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
前記第１の出力回路から前記分割被除数ごとに出力された余りの合計値を算出する余り加算回路と、
前記余り加算回路によって算出された余りの合計値を前記特定の除数で除算した商と余りを出力する余り除算回路と、
前記商加算回路から出力された加算結果と前記余り除算回路から出力された商とを加算する繰り上げ加算回路と、
を備えることを特徴とする割り算回路。
【請求項４】
前記第１の出力回路は、
前記分割被乗数の値ごとに２k通りの前記２ｋビットの商と余りとを保持し、前記分割被除数ごとに前記分割被除数に応じた前記２ｋビットの商と余りを出力することを特徴とする請求項３に記載の割り算回路。
【請求項５】
複数のメモリモジュールが２n−１（ｎ≧２の整数）のチャネルに分割されているメモリモジュール群へのアクセスを制御するメモリコントローラであって、
前記チャネルの数である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商と余りとを出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
前記第１の出力回路から前記分割被除数ごとに出力された余りの合計値を算出する余り加算回路と、
前記余り加算回路によって算出された余りの合計値を前記特定の除数で除算した商と余りを出力する余り除算回路と、
前記商加算回路から出力された加算結果と前記余り除算回路から出力された商とを加算する繰り上げ加算回路と、
前記余り除算回路から出力された余りに応じて前記２n−１のチャネルから１個のチャネルを選択し、前記１個のチャネルに属する複数のメモリモジュールから、前記繰り上げ加算回路から出力された加算結果に応じて１個のメモリモジュールを選択する選択回路と、
を備えることを特徴とするメモリコントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、被除数を特定の除数で除算する割り算回路、およびメモリコントローラに関する。
【背景技術】
【０００２】
従来より、デジタル回路の割り算において、除数が２n（ｎ≧１の整数）の場合、被除数を２進数とすれば、下位ｎビットが余り、それより上位のビットが商となる。除数が２n（ｎ≧１である整数）であれば、高速に割り算を行うことができるが、除数が２n以外の除数には適用できない。【０００３】
除数が２n以外の除数の場合の割り算手法については、引き放し法（従来技術１）や引き戻し法（従来技術２）が知られている。従来技術１は、被除数の上位桁から除数を複数回引いた時の余りの符号が負になれば、その下位の桁では除数を加えていく方法である。従来技術２は、筆算で除算を行う方法と同一であり、被除数の上位桁から順に除数を引き、引けたら商に1を立て、引けなければ商に０を立て、次の桁に進んでいく方法であり、最終的に、商と余りが得られる。【０００４】
従来技術１，２のいずれの方法を用いたとしても、割り算を行うためには、少なくとも（被除数のビット数）−（除数のビット数）分のビット数をシフトさせなければならない。従来技術１，２において、除数が固定の整数値の場合、被除数と除数のビット数差が大きければ大きいほど、シフト数が増加し、シフトのためのクロック数が増加し、計算時間が増大してしまう問題点があった。【０００５】
そこで、シフト数を減らすことにより、計算時間を削減する技術（従来技術３）が知られている（たとえば、下記特許文献１参照。）。従来技術３では、シフト数を減らすために、被除数を複数に分割する。そして、従来技術３では、該分割された分割被除数ごとに順に選択し、分割被除数を特定の除数で除算し、商と余りをそれぞれ商レジスタと余りレジスタに保持している。これにより、従来技術１，２では被除数のビット幅のクロック数が除算処理に必要であるが、従来技術３では分割数だけのクロック数で除算処理を行うことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１−１６６１２９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術３では分割数に応じてクロック数がかかるため、被除数が大きい値の場合、分割数が多くなり、クロック数が増大するという問題点があった。また、従来技術３では、クロック数を増大させないために分割数を減らすと、各分割被除数のビット幅が大きくなるため、分割被除数のビット分の商レジスタや余りレジスタが大きくなり、回路規模が大きくなる問題点があった。【０００８】
本発明は、上述した従来技術による問題点を解消するため、回路規模を大きくせずに、２n−１（ｎ≧２の整数）である除数による２進数の割り算を高速化できる割り算回路を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一観点によれば、２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商を出力する第１の出力回路と、前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べられた第２のビット列と、を出力する第２の出力回路と、前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした値の合計値を、前記被除数が前記特定の除数で除算された商として算出する商加算回路と、を備える割り算回路が提供される。
【発明の効果】
【００１０】
本割り算回路およびメモリコントローラによれば、回路規模を大きくせずに、２n−１（ｎ≧２の整数）である除数による２進数の割り算を高速化できるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、割り算回路の一例を示す説明図である。
【図２】図２は、除算回路１１０と除算回路１１５の一例を示す説明図である。
【図３】図３は、第１の出力回路に関する変換テーブルの一例を示す説明図である。
【図４】図４は、余り除算回路１０４に関する変換テーブルの一例を示す説明図である。
【図５】図５は、実施例１を示す説明図である。
【図６】図６は、実施例２を示す説明図である。
【図７】図７は、メモリコントローラにおけるメモリアクセス時間の一例を示す説明図である。
【図８】図８は、メモリコントローラにおける３チャネルインターリーブの一例を示す説明図である。
【発明を実施するための形態】
【００１２】
以下に本発明にかかる割り算回路およびメモリコントローラの好適な実施の形態を詳細に説明する。実施の形態で示す割り算回路は、ｈビットの被除数を入力とし、該入力されたｈビットの被除数を特定の除数である２n−１で除算した場合の商と、余りとを出力する。実施の形態では、ｈ＝３４ビットとし、被除数であるＸが３４ビットの値であり、ｎ＝２で特定の除数であるＹが３である場合を例に挙げて説明する。
【００１３】
（実施の形態）
図１は、割り算回路の一例を示す説明図である。割り算回路１００は、被除数分割回路１０１と、除算回路１１０〜除算回路１１８と、商加算回路１０２と、余り加算回路１０３と、余り除算回路１０４と、繰り上げ加算回路１０５と、バッファ１０６と、を有している。
【００１４】
被除数分割回路１０１は、被除数であるＸ［３３：０］を下位のビットからｋビット（ｎの整数倍）ごとに分割する。３４ビットのＸを最下位ビットから順に４ビットで分割し、９（ｈ／ｋで小数点以下切り上げ。）個の分割被除数を出力する。ｍ＝８である。
【００１５】
たとえば、（ｍ＋１）個に区切られた分割被除数を下位から順番にＸ０，Ｘ１，・・・，Ｘ（ｍ−１），Ｘｍとする。Ｘ［３：０］がＸ０［３：０］となり、Ｘ［７：４］がＸ１［３：０］となり、Ｘ［１１：８］がＸ２［３：０］となり、Ｘ［１５：１２］がＸ３［３：０］となり、Ｘ［１９：１６］がＸ４［３：０］となる。Ｘ［２３：２０］がＸ５［３：０］となり、Ｘ［２７：２４］がＸ６［３：０］となり、Ｘ［３１：２８］がＸ７［３：０］となり、Ｘ［３３：３２］がＸ８［１：０］となる。
【００１６】
除算回路１１０〜除算回路１１８は、第１の出力回路と第２の出力回路を有している。ここで、最下位ビットを含む分割被除数からの各分割被除数の配列位置をｉ（ｉ＝０〜８）とする。ここで、Ｘ０とＸ５に関する除算回路１１０と除算回路１１５とを例に挙げて説明する。
【００１７】
図２は、除算回路１１０と除算回路１１５の一例を示す説明図である。除算回路１１０は、第１の出力回路２０１と、第２の出力回路２０２と、を有している。除算回路１１５は、第１の出力回路２５１と、第２の出力回路２５２と、を有している。
【００１８】
第１の出力回路２０１は、分割回路１０１から出力されたＸ０［３：０］が３で除算された８ビットの商（４ビットのＡ０と４ビットのＢ０）と、２ビットの余りを出力する。
【００１９】
第１の出力回路２５１は、分割回路１０１から出力されたＸ５［３：０］の下位に２０ビット分の０が付与された値が３で除算された８ビットの商（４ビットのＡ５と４ビットのＢ５）と、２ビットの余りを出力する。
【００２０】
本実施の形態では、第１の出力回路２０１と第１の出力回路２５１は、具体的には、たとえば、８ビットのビット列のうちの下位４ビットが０である値を３で除算された１６通りの計算結果をあらかじめ変換テーブルとして保持していることとする。変換テーブルは、具体的には、たとえば、論理素子を用いて実現される。ここで、以降、２進数表記については、２桁の２進数の値を表す場合には２’ｂとし、２’ｂに続いて具体的な数値を表記する。具体的には、たとえば、５を２進数で表すと、３’ｂ１０１とする。
【００２１】
図３は、第１の出力回路に関する変換テーブルの一例を示す説明図である。変換テーブル３００では、Ｘｍの入力に応じてＡとＢと余りが出力される。たとえば、Ｘｍが４’ｂ００００であれば、８ビットの商のうちの上位４ビットであるＡは４’ｂ００００であり、８ビットの商のうちの下位４ビットであるＢは４’ｂ００００であり、余りが２’ｂ００である。たとえば、Ｘｍが４’ｂ０１１１であれば、８ビットの商のうちの上位４ビットであるＡは４’ｂ００１０であり、８ビットの商のうちの下位４ビットであるＢは４’ｂ０１０１であり、余りが２’ｂ０１である。
【００２２】
また、４ビットごとに分割された分割被除数は０（４’ｂ００００）〜１５（４’ｂ１１１１）であり、分割被除数が特定の除数である３で除算された場合、余りは０（２’ｂ００）〜２（２’ｂ１０）のいずれかである。
【００２３】
図２に戻って、第２の出力回路２０２では、第１の出力回路２０１から出力された８ビットの商（４ビットのＡ０と４ビットのＢ０）のうちの上位４ビットのビット列（Ａ０）と、２ｋビットの商のうちの下位４ビット（Ｂ０）が０個並べられたビット列と、を出力する。Ｘ０の場合、ｉ＝０となるため、第２の出力回路２０２では、Ａ０がバッファを介してＸ０の商として出力され、Ｂ０は出力されない。
【００２４】
第２の出力回路２５２では、第１の出力回路２５１から出力された８ビットの商（４ビットのＡ５と４ビットのＢ５）のうちの上位４ビットのビット列（Ａ５）と、２ｋビットの商のうちの下位４ビット（Ｂ５）が５個並べられたビット列と、を出力する。
【００２５】
除数が２n−１の場合、ｋビットの分割被除数にｋの整数倍（ｚ）ビット分の０が付与されて特定の除数で除算されたｋ（ｚ＋１）ビットの商のうちの下位ｋｚビットはｋビットごとに同一値が繰り返される。
【００２６】
たとえば、４’ｂ１０１０にｋ＝４の５倍である２０ビット分の０が付与された値が３で除算された除算結果は２４’ｂ００１１０１０１０１０１０１０１０１０１０１０１である。上位４ビットは４’ｂ００１１であって、下位２０ビットは４ビットごとに４’ｂ０１０１が５回繰り返されている。
【００２７】
たとえば、８’ｂ１０１０１１０１にｋ＝８の３倍である２４ビット分の０が付与された値が３で除算された３２ビットの商は３２’ｂ１１１００１１０１０１０１０１０１０１０１０１０１０１０１０１０である。上位８ビットは８’ｂ１１１００１１０であって、下位２４ビットは８ビットごとに８’ｂ１０１０１０１０が３回繰り返されている。
【００２８】
図１に戻って、商加算回路１０２は、各除算回路の第２の出力回路から出力された第１のビット列を上位のビット列とし、第２の出力回路から出力された第２のビット列を下位のビット列とした値の合計値を算出する。
【００２９】
余り加算回路１０３は、各除算回路の第１の出力回路から分割被除数ごとに出力された余りをすべて加算する。さらに、余りの合計値が特定の除数を超えることがあるため、余り除算回路１０４は、余り加算回路１０３から出力された加算結果が特定の除数で除算された余りの商を出力する。さらに、余り除算回路１０４は、余り合計値の余りを被除数が特定の除数で除算された余りとしてバッファ１０６を介して出力する。
【００３０】
上述のように特定の除数が３（２’ｂ１１）であれば、余りは最大でも２（２’ｂ１０）である。すなわち、分割被除数ごとの第１の出力回路から出力されたすべての余りが２（２’ｂ１０）であっても、余りの合計値は、最大で１８（５’ｂ１００１０）である。余り除算回路１０４は、具体的には、たとえば、余りの合計値が０（５’ｂ０００００）〜１８（５’ｂ１００１０）のそれぞれが特定の除数である３で除算された場合の商（余りの合計の商と称する。）と、余り（余りの合計の余りと称する。）と、をあらかじめ変換テーブルとして保持していることとする。変換テーブルは、具体的には、たとえば、論理素子を用いて実現される。
【００３１】
図４は、余り除算回路１０４に関する変換テーブルの一例を示す説明図である。変換テーブル４００では、余りの合計値に応じて、余りの合計値の商と余りの合計値の余りとが出力される。上述のように、余りの合計値は０（５’ｂ０００００）〜１８（５’ｂ１００１０）のいずれかである。余りの合計値の商は、余りの合計値が除数である３で除算された商であり、商の加算回路によって算出された合計値の最下位ビットへの繰り上がりの値である。
【００３２】
余りの合計値の余りは、余りの合計値が除数である３で除算された余りであり、被除数が特定の除数で除算された余りとして出力される。０（５’ｂ０００００）〜１８（５’ｂ１００１０）が３で除算された余りは０（２’ｂ００）〜２（２’ｂ１０）である。たとえば、余りの合計値が５’ｂ０００１１であれば、余りの合計値の商が３’ｂ００１であり、余りの合計値の余りが２’ｂ００である。
【００３３】
図１に戻って、繰り上げ加算回路１０５は、商の加算回路から出力された商の合計値と余りの合計値の商とを加算する。そして、繰り上げ加算回路１０５は、加算結果を被除数が特定の除数で除算された商として出力する。
【００３４】
ここで、３４ビットの具体的な被除数を用いて例を挙げる。
・実施例１：Ｘ÷Ｙ＝１６９５（３４’ｂ０００００００００００００００００００００００１１０１００１１１１１）÷３（２’ｂ１１）
・実施例２：Ｘ÷Ｙ＝１７７１４７（３４’ｂ００００００００００００００００１０１０１１００１１１１１１１０１１）÷３（２’ｂ１１）
【００３５】
（実施例１）
図５は、実施例１を示す説明図である。分割回路１０１が、３４’ｂ０００００００００００００００００００００００１１０１００１１１１１を最下位ビットから４ビットごとに順に分割する。
・Ｘ０＝４’ｂ１１１１
・Ｘ１＝４’ｂ１００１
・Ｘ２＝４’ｂ０１１０
・Ｘ３＝４’ｂ００００
・Ｘ４＝４’ｂ００００
・Ｘ５＝４’ｂ００００
・Ｘ６＝４’ｂ００００
・Ｘ７＝４’ｂ００００
・Ｘ８＝２’ｂ００
【００３６】
Ｘ０として４’ｂ１１１１が除算回路１１０へ与えられると、除算回路１１０からはビット列である４’ｂ０１０１が出力され、余りとして２’ｂ００が出力される。Ｘ１として４’ｂ１００１が除算回路１１１へ与えられると、除算回路１１１からはビット列である８’ｂ００１１００００が出力され、余りとして２’ｂ００が出力される。
【００３７】
Ｘ２として４’ｂ０１１０が除算回路１１２へ与えられると、除算回路１１２からはビット列である１２’ｂ００１０００００００００が出力され、余りとして２’ｂ００が出力される。Ｘ３として４’ｂ００００が除算回路１１３へ与えられると、除算回路１１３からはビット列である１６’ｂ００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００３８】
Ｘ４として４’ｂ００００が除算回路１１４へ与えられると、除算回路１１４からはビット列である２０’ｂ００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。Ｘ５として４’ｂ００００が除算回路１１５へ与えられると、除算回路１１５からはビット列である２４’ｂ００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００３９】
Ｘ６として４’ｂ００００が除算回路１１６へ与えられると、除算回路１１６からはビット列である２８’ｂ００００００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。Ｘ７として４’ｂ００００が除算回路１１７へ与えられると、除算回路１１７からはビット列である３２’ｂ００００００００００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００４０】
Ｘ８として２’ｂ００が除算回路１１８へ与えられると、除算回路１１８からはビット列である３４’ｂ００００００００００００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００４１】
商加算回路１０２は、分割被除数ごとの除算回路から出力されたビット列をすべて加算する。加算結果は３４’ｂ００００００００００００００００００００００００１０００１１０１０１である。分割被除数ごとの除算回路から出力された余りはすべて０であるため、余りはなしである。すなわち、余りからの繰り上がりがないため、１６９５÷３の商は、５６５（３４’ｂ００００００００００００００００００００００００１０００１１０１０１）である。２n−１の除数で除算された際に余りが無い値のみが被除数である場合、余り加算回路１０３と、余り除算回路１０４と、繰り上げ加算回路１０５と、は、なくても良い。
【００４２】
（実施例２）
図６は、実施例２を示す説明図である。分割回路１０１が、３４’ｂ００００００００００００００００１０１０１１００１１１１１１１０１１を最下位ビットから４ビットごとに順に分割する。
・Ｘ０＝４’ｂ１０１１
・Ｘ１＝４’ｂ１１１１
・Ｘ２＝４’ｂ００１１
・Ｘ３＝４’ｂ１０１１
・Ｘ４＝４’ｂ００１０
・Ｘ５＝４’ｂ００００
・Ｘ６＝４’ｂ００００
・Ｘ７＝４’ｂ００００
・Ｘ８＝２’ｂ００
【００４３】
Ｘ０として４’ｂ１０１１が除算回路１１０へ与えられると、除算回路１１０からはビット列である４’ｂ００１１と、余りとして２’ｂ１０が出力される。Ｘ１として４’ｂ１１１１が除算回路１１１へ与えられると、除算回路１１１からはビット列である８’ｂ０１０１００００と、余りとして２’ｂ００が出力される。Ｘ２として４’ｂ００１１が除算回路１１２へ与えられると、除算回路１１２からはビット列である１２’ｂ０００１００００００００と、余りとして２’ｂ００が出力される。
【００４４】
Ｘ３として４’ｂ１０１１が除算回路１１３へ与えられると、除算回路１１３からはビット列である１６’ｂ００１１１０１０１０１０１０１０と、余りとして２’ｂ１０が出力される。Ｘ４として４’ｂ００１０が除算回路１１４へ与えられると、除算回路１１４からはビット列である２０’ｂ００００１０１０１０１０１０１０１０１０と、余りとして２’ｂ１０が出力される。
【００４５】
Ｘ５として４’ｂ００００が除算回路１１５へ与えられると、除算回路１１５からはビット列である２４’ｂ００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。Ｘ６として４’ｂ００００が除算回路１１６へ与えられると、除算回路１１６からはビット列である２８’ｂ００００００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。
【００４６】
Ｘ７として４’ｂ００００が除算回路１１７へ与えられると、除算回路１１７からはビット列である３２’ｂ００００００００００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。Ｘ８として４’ｂ００００が除算回路１１８へ与えられると、除算回路１１８からはビット列である３４’ｂ００００００００００００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。なお、除算回路１１８は、３６ビットの０を出力してもよい。
【００４７】
そして、商加算回路１０２が、分割被除数ごとの除算回路から出力されたビット列をすべて加算する。加算結果が３４’ｂ００００００００００００００００００１１１００１１０１０１００１１１である。
【００４８】
さらに、余り加算回路１０３が、分割被除数ごとの除算回路から出力された余りをすべて加算する。余りの合計値は、５’ｂ００１１０である。
【００４９】
余り除算回路１０４は、余りの合計値が５’ｂ００１１０であるため、変換テーブル４００に基づいて余りの合計値の商として３’ｂ０１０を出力し、余りの合計値の余りとして２’ｂ００を出力する。
【００５０】
繰り上げ加算回路１０５は、商加算回路１０２から出力された加算結果に余り除算回路１０４から出力された余りの合計値の商を加算する。すなわち、繰り上げ加算回路１０５は、３４’ｂ００００００００００００００００００１１１００１１０１０１００１１１に３’ｂ０１０を加算する。繰り上げ加算回路１０５による加算結果（１７７１４７を３で除算した商）は、５９０４９（３４’ｂ００００００００００００００００００１１１００１１０１０１０１００１）である。
【００５１】
つぎに、割り算回路１００の使用例について説明する。割り算回路１００では２n−１が除数の場合において、高速に除算することができる。たとえば、ＤＩＭＭ（Ｄｕａｌ  Ｉｎｌｉｎｅ  Ｍｅｍｏｒｙ  Ｍｏｄｕｌｅ）を接続するメモリコントローラＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）において、ＤＩＭＭのチャネル数が３（ｎ＝２，２n−１＝３)であった場合、従来技術では３チャネルにまたがるメモリインターリーブを行う際に高速にチャネルを切り替えることが出来なかった。メモリインターリーブとは、ブロック分けされたメモリモジュールの複数に対して同時・並行的にアクセスすることにより、メモリへのアクセスを高速化する技術である。
【００５２】
しかしながら、上述した本発明の実施例を用いれば、除数が３の場合に最短で１クロックで算出が終了するため、高速にチャネルを切り替えることができる。
【００５３】
図７は、メモリコントローラにおけるメモリアクセス時間の一例を示す説明図である。図７では、理解の容易化のため、チャネルインターリーブ無しと、チャネルインターリーブ有りと、を示す。（１）チャネルインターリーブ無しでは、ＣＰＵの処理時間に比べてメモリアクセスにかかる時間が長いため、全体の処理時間がメモリアクセスにかかる時間のほぼ総和となる。一方、（２）チャネルインターリーブ有りの場合、メモリアクセスが並列に行われるため、全体の処理時間が（１）チャネルインターリーブ無しから大幅に短縮される。
【００５４】
図８は、メモリコントローラにおける３チャネルインターリーブの一例を示す説明図である。図８では、複数のＤＩＭＭがチャネル０〜チャネル２に分けられている。チャネル０は、ＤＩＭＭ０１〜ＤＩＭＭ０ｊ（ｊ≧１）を有し、チャネル１は、ＤＩＭＭ１１〜ＤＩＭＭ１ｊを有し、チャネル２は、ＤＩＭＭ２１〜ＤＩＭＭ２ｊを有している。
【００５５】
メモリコントローラ８００は、メモリアドレスに基づいていずれのチャネルにアクセスするか、該チャネルのうちのいずれのＤＩＭＭへアクセスするかを制御する。メモリコントローラ８００は割り算回路１００と選択回路８０１とを有する。割り算回路１００は、除数がチャネル数（３）である。メモリコントローラ８００は、選択されたメモリアドレスを被除数として割り算回路１００へ入力する。割り算回路１００は、メモリアドレスを３で除算し、商と余りを選択回路８０１へ出力する。割り算回路１００の余り除算回路から出力された余りがメモリアドレスを３で除算した余りであり、割り算回路１００の繰り上げ加算回路１０５から出力された加算結果がメモリアドレスを３で除算した商である。
【００５６】
選択回路８０１は、割り算回路１００から出力された余りに基づいてチャネルを選択する。そして、選択回路８０１は、割り算回路１００から出力された商に基づいて該選択したチャネル内のＤＩＭＭを選択する。たとえば、指定されたメモリアドレスが３で除算された余りが０であれば、選択回路８０１がチャネル０を選択し、指定されたメモリアドレスが３で除算された商が２であれば、ＤＩＭＭ０２を選択する。メモリコントローラ８００は、メモリアドレスを順に選択し、チャネルを切り替えることにより、ＤＩＭＭを並列して選択することができる。
【００５７】
以上説明したように、割り算回路によれば、被除数をｋビットごとに分割する。そして、分割被除数ごとに該分割被除数の下位にｋの整数倍ビット分の０を付与した値を２n−１の除数で除算する。そして、分割被除数ごとの除算結果をすべて加算し、加算結果を、被除数を除数で除算した商とする。ｋビットの分割被除数にｋの整数倍ビット分の０を付与して特定の除数で除算した商のうち、下位ｋの整数倍ビットはｋビットごとに同一値が繰り返される特性を用いることにより、除算を並列化することができる。さらに、同一の除算が並列化されているため、回路を縮小化することができる。２n−１を除数とする除算の商を最短１クロックで行うことができ、除算処理を高速化することができる。さらに、商レジスタが不要となり、組合せ回路のみで計算を実現することができるため、割り算回路を縮小化することができる。
【００５８】
また、分割被除数の値ごとに、分割被除数の下位にｋの整数倍ビット分の０を付与した値を２n−１の除数で除算した２ｋビットの商を２k通り保持し、各分割被除数に応じて２ｋビットの商を出力することにより、割り算回路を縮小化することができる。
【００５９】
さらに、分割被除数の値ごとに、分割被除数の下位にｋの整数倍ビット分の０を付与した値を２n−１の除数で除算した余りを算出し、分割被除数ごとの余りをすべて加算する。そして、余りの合計が除数を超える場合、余りの合計値をさらに２n−１である特定の除数で除算することによって、被除数を除数で割った商と余りを算出する。これにより、２n−１を除数とする除算の商と余りの算出を最短１クロックで行うことができ、除算処理を高速化することができる。さらに、商レジスタと余りレジスタが不要となり、組合せ回路のみで計算を実現することができる。
【００６０】
また、分割被除数の値ごとに、分割被除数の下位にｋの整数倍ビット分の０を付与した値を除数で除算した２ｋビットの商と余りを２k通り保持し、各分割被除数に応じて２ｋビットの商と余りを出力する。
【００６１】
また、２n−１個のチャネルに分割されたメモリモジュールへアクセスする場合、メモリアドレスが２n−１で除算された余りに応じてチャネルを選択し、除数が２n−１の除数で除算された商に応じて選択したチャネルに属するメモリモジュールを選択する。最短１クロックで除算処理を行うことができる除算回路を用いることで、メモリアクセスの高速化を図ることができる。
【符号の説明】
【００６２】
１００  割り算回路
１０１  分割回路
１０２  商加算回路
１０３  余り加算回路
１０４  余り除算回路
１０５  繰り上げ加算回路
１１０〜１１８  除算回路
２０１，２５１  第１の出力回路
２０２，２５２  第２の出力回路
８００  メモリコントローラ
８０１  選択回路
【図１】
2012086073.tif 000003
【図２】
2012086073.tif 000004
【図３】
2012086073.tif 000005
【図４】
2012086073.tif 000006
【図５】
2012086073.tif 000007
【図６】
2012086073.tif 000008
【図７】
2012086073.tif 000009
【図８】
2012086073.tif 000010
【手続補正書】
【提出日】平成25年6月7日(2013.6.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商を出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
を備えることを特徴とする割り算回路。
【請求項２】
前記第１の出力回路は、
前記分割被除数の値ごとに２k通りの前記２ｋビットの商を保持し、前記分割被除数ごとに前記分割被除数に応じた前記２ｋビットの商を出力することを特徴とする請求項１に記載の割り算回路。
【請求項３】
２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商と余りとを出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
前記第１の出力回路から前記分割被除数ごとに出力された余りの合計値を算出する余り加算回路と、
前記余り加算回路によって算出された余りの合計値を前記特定の除数で除算した商と余りを出力する余り除算回路と、
前記商加算回路から出力された加算結果と前記余り除算回路から出力された商とを加算する繰り上げ加算回路と、
を備えることを特徴とする割り算回路。
【請求項４】
前記第１の出力回路は、
前記分割被除数の値ごとに２k通りの前記２ｋビットの商と余りとを保持し、前記分割被除数ごとに前記分割被除数に応じた前記２ｋビットの商と余りを出力することを特徴とする請求項３に記載の割り算回路。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、被除数を特定の除数で除算する割り算回路に関する。
【背景技術】
【０００２】
従来、デジタル回路の割り算において、除数が２n（ｎ≧１の整数）の場合、被除数を２進数とすれば、下位ｎビットが余り、それより上位のビットが商となる。除数が２n（ｎ≧１の整数）であれば、高速に割り算を行うことができるが、除数が２n以外の除数には適用できない。
【０００３】
除数が２n以外の除数の場合の割り算手法については、引き放し法（従来技術１）や引き戻し法（従来技術２）が知られている。従来技術１は、被除数の上位桁から除数を複数回引いた時の余りの符号が負になれば、その下位の桁では除数を加えていく方法である。従来技術２は、筆算で除算を行う方法と同一であり、被除数の上位桁から順に除数を引き、引けたら商に1を立て、引けなければ商に０を立て、次の桁に進んでいく方法であり、最終的に、商と余りが得られる。
【０００４】
従来技術１，２のいずれの方法を用いたとしても、割り算を行うためには、少なくとも（被除数のビット数）−（除数のビット数）分のビット数をシフトさせなければならない。従来技術１，２において、除数が固定の整数値の場合、被除数と除数のビット数差が大きければ大きいほど、シフト数が増加し、シフトのためのクロック数が増加し、計算時間が増大してしまう問題点があった。
【０００５】
そこで、シフト数を減らすことにより、計算時間を削減する技術（従来技術３）が知られている（たとえば、下記特許文献１参照。）。従来技術３では、シフト数を減らすために、被除数を複数に分割する。そして、従来技術３では、該分割された分割被除数ごとに順に選択し、分割被除数を特定の除数で除算し、商と余りをそれぞれ商レジスタと余りレジスタに保持している。これにより、従来技術１，２では被除数のビット幅のクロック数が除算処理に必要であるが、従来技術３では分割数だけのクロック数で除算処理を行うことができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平１−１６６１２９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、従来技術３では分割数に応じてクロック数がかかるため、被除数が大きい値の場合、分割数が多くなり、クロック数が増大するという問題点があった。また、従来技術３では、クロック数を増大させないために分割数を減らすと、各分割被除数のビット幅が大きくなるため、分割被除数のビット分の商レジスタや余りレジスタが大きくなり、回路規模が大きくなる問題点があった。
【０００８】
本発明は、上述した従来技術による問題点を解消するため、回路規模を大きくせずに、２n−１（ｎ≧２の整数）である除数による２進数の割り算を高速化できる割り算回路を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一観点によれば、２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商を出力する第１の出力回路と、前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、を備える割り算回路が提供される。
【発明の効果】
【００１０】
本割り算回路によれば、回路規模を大きくせずに、２n−１（ｎ≧２の整数）である除数による２進数の割り算を高速化できるという効果を奏する。
【図面の簡単な説明】
【００１１】
【図１】図１は、割り算回路の一例を示す説明図である。
【図２】図２は、除算回路１１０と除算回路１１５の一例を示す説明図である。
【図３】図３は、第１の出力回路に関する変換テーブルの一例を示す説明図である。
【図４】図４は、余り除算回路１０４に関する変換テーブルの一例を示す説明図である。
【図５】図５は、実施例１を示す説明図である。
【図６】図６は、実施例２を示す説明図である。
【図７】図７は、メモリコントローラにおけるメモリアクセス時間の一例を示す説明図である。
【図８】図８は、メモリコントローラにおける３チャネルインターリーブの一例を示す説明図である。
【発明を実施するための形態】
【００１２】
以下に本発明にかかる割り算回路の好適な実施の形態を詳細に説明する。実施の形態で示す割り算回路は、ｈビットの被除数を入力とし、該入力されたｈビットの被除数を特定の除数である２n−１で除算した場合の商と、余りとを出力する。実施の形態では、ｈ＝３４ビットとし、被除数であるＸが３４ビットの値であり、ｎ＝２で特定の除数であるＹが３である場合を例に挙げて説明する。
【００１３】
（実施の形態）
図１は、割り算回路の一例を示す説明図である。割り算回路１００は、被除数分割回路１０１と、除算回路１１０〜除算回路１１８と、商加算回路１０２と、余り加算回路１０３と、余り除算回路１０４と、繰り上げ加算回路１０５と、バッファ１０６と、を有している。
【００１４】
被除数分割回路１０１は、被除数であるＸ［３３：０］を下位のビットからｋビット（ｎの整数倍）ごとに分割する。３４ビットのＸを最下位ビットから順に４ビットで分割し、９（ｈ／ｋで小数点以下切り上げ。）個の分割被除数を出力する。ｍ＝８である。
【００１５】
たとえば、（ｍ＋１）個に区切られた分割被除数を下位から順番にＸ０，Ｘ１，・・・，Ｘ（ｍ−１），Ｘｍとする。Ｘ［３：０］がＸ０［３：０］となり、Ｘ［７：４］がＸ１［３：０］となり、Ｘ［１１：８］がＸ２［３：０］となり、Ｘ［１５：１２］がＸ３［３：０］となり、Ｘ［１９：１６］がＸ４［３：０］となる。Ｘ［２３：２０］がＸ５［３：０］となり、Ｘ［２７：２４］がＸ６［３：０］となり、Ｘ［３１：２８］がＸ７［３：０］となり、Ｘ［３３：３２］がＸ８［１：０］となる。
【００１６】
除算回路１１０〜除算回路１１８は、第１の出力回路と第２の出力回路を有している。ここで、最下位ビットを含む分割被除数からの各分割被除数の配列位置をｉ（ｉ＝０〜８）とする。ここで、Ｘ０とＸ５に関する除算回路１１０と除算回路１１５とを例に挙げて説明する。
【００１７】
図２は、除算回路１１０と除算回路１１５の一例を示す説明図である。除算回路１１０は、第１の出力回路２０１と、第２の出力回路２０２と、を有している。除算回路１１５は、第１の出力回路２５１と、第２の出力回路２５２と、を有している。
【００１８】
第１の出力回路２０１は、分割回路１０１から出力されたＸ０［３：０］が３で除算された８ビットの商（４ビットのＡ０と４ビットのＢ０）と、２ビットの余りを出力する。
【００１９】
第１の出力回路２５１は、分割回路１０１から出力されたＸ５［３：０］の下位に２０ビット分の０が付与された値が３で除算された８ビットの商（４ビットのＡ５と４ビットのＢ５）と、２ビットの余りを出力する。
【００２０】
本実施の形態では、第１の出力回路２０１と第１の出力回路２５１は、具体的には、たとえば、８ビットのビット列のうちの下位４ビットが０である値を３で除算された１６通りの計算結果をあらかじめ変換テーブルとして保持していることとする。変換テーブルは、具体的には、たとえば、論理素子を用いて実現される。ここで、以降、２進数表記については、２桁の２進数の値を表す場合には２’ｂとし、２’ｂに続いて具体的な数値を表記する。具体的には、たとえば、５を２進数で表すと、３’ｂ１０１とする。
【００２１】
図３は、第１の出力回路に関する変換テーブルの一例を示す説明図である。変換テーブル３００では、Ｘｍの入力に応じてＡとＢと余りが出力される。たとえば、Ｘｍが４’ｂ００００であれば、８ビットの商のうちの上位４ビットであるＡは４’ｂ００００であり、８ビットの商のうちの下位４ビットであるＢは４’ｂ００００であり、余りが２’ｂ００である。たとえば、Ｘｍが４’ｂ０１１１であれば、８ビットの商のうちの上位４ビットであるＡは４’ｂ００１０であり、８ビットの商のうちの下位４ビットであるＢは４’ｂ０１０１であり、余りが２’ｂ０１である。
【００２２】
また、４ビットごとに分割された分割被除数は０（４’ｂ００００）〜１５（４’ｂ１１１１）であり、分割被除数が特定の除数である３で除算された場合、余りは０（２’ｂ００）〜２（２’ｂ１０）のいずれかである。
【００２３】
図２に戻って、第２の出力回路２０２では、第１の出力回路２０１から出力された８ビットの商（４ビットのＡ０と４ビットのＢ０）のうちの上位４ビットのビット列（Ａ０）と、２ｋビットの商のうちの下位４ビット（Ｂ０）が０個並べられたビット列と、を出力する。Ｘ０の場合、ｉ＝０となるため、第２の出力回路２０２では、Ａ０がバッファを介してＸ０の商として出力され、Ｂ０は出力されない。
【００２４】
第２の出力回路２５２では、第１の出力回路２５１から出力された８ビットの商（４ビットのＡ５と４ビットのＢ５）のうちの上位４ビットのビット列（Ａ５）と、２ｋビットの商のうちの下位４ビット（Ｂ５）が５個並べられたビット列と、を出力する。
【００２５】
除数が２n−１の場合、ｋビットの分割被除数にｋの整数倍（ｚ）ビット分の０が付与されて特定の除数で除算されたｋ（ｚ＋１）ビットの商のうちの下位ｋｚビットはｋビットごとに同一値が繰り返される。
【００２６】
たとえば、４’ｂ１０１０にｋ＝４の５倍である２０ビット分の０が付与された値が３で除算された除算結果は２４’ｂ００１１０１０１０１０１０１０１０１０１０１０１である。上位４ビットは４’ｂ００１１であって、下位２０ビットは４ビットごとに４’ｂ０１０１が５回繰り返されている。
【００２７】
たとえば、８’ｂ１０１０１１０１にｋ＝８の３倍である２４ビット分の０が付与された値が３で除算された３２ビットの商は３２’ｂ１１１００１１０１０１０１０１０１０１０１０１０１０１０１０１０である。上位８ビットは８’ｂ１１１００１１０であって、下位２４ビットは８ビットごとに８’ｂ１０１０１０１０が３回繰り返されている。
【００２８】
図１に戻って、商加算回路１０２は、各除算回路の第２の出力回路から出力された第１のビット列を上位のビット列とし、第２の出力回路から出力された第２のビット列を下位のビット列とした値の合計値を算出する。
【００２９】
余り加算回路１０３は、各除算回路の第１の出力回路から分割被除数ごとに出力された余りをすべて加算する。さらに、余りの合計値が特定の除数を超えることがあるため、余り除算回路１０４は、余り加算回路１０３から出力された加算結果が特定の除数で除算された余りの商を出力する。さらに、余り除算回路１０４は、余り合計値の余りを被除数が特定の除数で除算された余りとしてバッファ１０６を介して出力する。
【００３０】
上述のように特定の除数が３（２’ｂ１１）であれば、余りは最大でも２（２’ｂ１０）である。すなわち、分割被除数ごとの第１の出力回路から出力されたすべての余りが２（２’ｂ１０）であっても、余りの合計値は、最大で１８（５’ｂ１００１０）である。余り除算回路１０４は、具体的には、たとえば、余りの合計値が０（５’ｂ０００００）〜１８（５’ｂ１００１０）のそれぞれが特定の除数である３で除算された場合の商（余りの合計の商と称する。）と、余り（余りの合計の余りと称する。）と、をあらかじめ変換テーブルとして保持していることとする。変換テーブルは、具体的には、たとえば、論理素子を用いて実現される。
【００３１】
図４は、余り除算回路１０４に関する変換テーブルの一例を示す説明図である。変換テーブル４００では、余りの合計値に応じて、余りの合計値の商と余りの合計値の余りとが出力される。上述のように、余りの合計値は０（５’ｂ０００００）〜１８（５’ｂ１００１０）のいずれかである。余りの合計値の商は、余りの合計値が除数である３で除算された商であり、商の加算回路によって算出された合計値の最下位ビットへの繰り上がりの値である。
【００３２】
余りの合計値の余りは、余りの合計値が除数である３で除算された余りであり、被除数が特定の除数で除算された余りとして出力される。０（５’ｂ０００００）〜１８（５’ｂ１００１０）が３で除算された余りは０（２’ｂ００）〜２（２’ｂ１０）である。たとえば、余りの合計値が５’ｂ０００１１であれば、余りの合計値の商が３’ｂ００１であり、余りの合計値の余りが２’ｂ００である。
【００３３】
図１に戻って、繰り上げ加算回路１０５は、商の加算回路から出力された商の合計値と余りの合計値の商とを加算する。そして、繰り上げ加算回路１０５は、加算結果を被除数が特定の除数で除算された商として出力する。
【００３４】
ここで、３４ビットの具体的な被除数を用いて例を挙げる。
・実施例１：Ｘ÷Ｙ＝１６９５（３４’ｂ０００００００００００００００００００００００１１０１００１１１１１）÷３（２’ｂ１１）
・実施例２：Ｘ÷Ｙ＝１７７１４７（３４’ｂ００００００００００００００００１０１０１１００１１１１１１１０１１）÷３（２’ｂ１１）
【００３５】
（実施例１）
図５は、実施例１を示す説明図である。分割回路１０１が、３４’ｂ０００００００００００００００００００００００１１０１００１１１１１を最下位ビットから４ビットごとに順に分割する。
・Ｘ０＝４’ｂ１１１１
・Ｘ１＝４’ｂ１００１
・Ｘ２＝４’ｂ０１１０
・Ｘ３＝４’ｂ００００
・Ｘ４＝４’ｂ００００
・Ｘ５＝４’ｂ００００
・Ｘ６＝４’ｂ００００
・Ｘ７＝４’ｂ００００
・Ｘ８＝２’ｂ００
【００３６】
Ｘ０として４’ｂ１１１１が除算回路１１０へ与えられると、除算回路１１０からはビット列である４’ｂ０１０１が出力され、余りとして２’ｂ００が出力される。Ｘ１として４’ｂ１００１が除算回路１１１へ与えられると、除算回路１１１からはビット列である８’ｂ００１１００００が出力され、余りとして２’ｂ００が出力される。
【００３７】
Ｘ２として４’ｂ０１１０が除算回路１１２へ与えられると、除算回路１１２からはビット列である１２’ｂ００１０００００００００が出力され、余りとして２’ｂ００が出力される。Ｘ３として４’ｂ００００が除算回路１１３へ与えられると、除算回路１１３からはビット列である１６’ｂ００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００３８】
Ｘ４として４’ｂ００００が除算回路１１４へ与えられると、除算回路１１４からはビット列である２０’ｂ００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。Ｘ５として４’ｂ００００が除算回路１１５へ与えられると、除算回路１１５からはビット列である２４’ｂ００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００３９】
Ｘ６として４’ｂ００００が除算回路１１６へ与えられると、除算回路１１６からはビット列である２８’ｂ００００００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。Ｘ７として４’ｂ００００が除算回路１１７へ与えられると、除算回路１１７からはビット列である３２’ｂ００００００００００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００４０】
Ｘ８として２’ｂ００が除算回路１１８へ与えられると、除算回路１１８からはビット列である３４’ｂ００００００００００００００００００００００００００００００００００が出力され、余りとして２’ｂ００が出力される。
【００４１】
商加算回路１０２は、分割被除数ごとの除算回路から出力されたビット列をすべて加算する。加算結果は３４’ｂ００００００００００００００００００００００００１０００１１０１０１である。分割被除数ごとの除算回路から出力された余りはすべて０であるため、余りはなしである。すなわち、余りからの繰り上がりがないため、１６９５÷３の商は、５６５（３４’ｂ００００００００００００００００００００００００１０００１１０１０１）である。２n−１の除数で除算された際に余りが無い値のみが被除数である場合、余り加算回路１０３と、余り除算回路１０４と、繰り上げ加算回路１０５と、は、なくても良い。
【００４２】
（実施例２）
図６は、実施例２を示す説明図である。分割回路１０１が、３４’ｂ００００００００００００００００１０１０１１００１１１１１１１０１１を最下位ビットから４ビットごとに順に分割する。
・Ｘ０＝４’ｂ１０１１
・Ｘ１＝４’ｂ１１１１
・Ｘ２＝４’ｂ００１１
・Ｘ３＝４’ｂ１０１１
・Ｘ４＝４’ｂ００１０
・Ｘ５＝４’ｂ００００
・Ｘ６＝４’ｂ００００
・Ｘ７＝４’ｂ００００
・Ｘ８＝２’ｂ００
【００４３】
Ｘ０として４’ｂ１０１１が除算回路１１０へ与えられると、除算回路１１０からはビット列である４’ｂ００１１と、余りとして２’ｂ１０が出力される。Ｘ１として４’ｂ１１１１が除算回路１１１へ与えられると、除算回路１１１からはビット列である８’ｂ０１０１００００と、余りとして２’ｂ００が出力される。Ｘ２として４’ｂ００１１が除算回路１１２へ与えられると、除算回路１１２からはビット列である１２’ｂ０００１００００００００と、余りとして２’ｂ００が出力される。
【００４４】
Ｘ３として４’ｂ１０１１が除算回路１１３へ与えられると、除算回路１１３からはビット列である１６’ｂ００１１１０１０１０１０１０１０と、余りとして２’ｂ１０が出力される。Ｘ４として４’ｂ００１０が除算回路１１４へ与えられると、除算回路１１４からはビット列である２０’ｂ００００１０１０１０１０１０１０１０１０と、余りとして２’ｂ１０が出力される。
【００４５】
Ｘ５として４’ｂ００００が除算回路１１５へ与えられると、除算回路１１５からはビット列である２４’ｂ００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。Ｘ６として４’ｂ００００が除算回路１１６へ与えられると、除算回路１１６からはビット列である２８’ｂ００００００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。
【００４６】
Ｘ７として４’ｂ００００が除算回路１１７へ与えられると、除算回路１１７からはビット列である３２’ｂ００００００００００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。Ｘ８として４’ｂ００００が除算回路１１８へ与えられると、除算回路１１８からはビット列である３４’ｂ００００００００００００００００００００００００００００００００００と、余りとして２’ｂ００が出力される。なお、除算回路１１８は、３６ビットの０を出力してもよい。
【００４７】
そして、商加算回路１０２が、分割被除数ごとの除算回路から出力されたビット列をすべて加算する。加算結果が３４’ｂ００００００００００００００００００１１１００１１０１０１００１１１である。
【００４８】
さらに、余り加算回路１０３が、分割被除数ごとの除算回路から出力された余りをすべて加算する。余りの合計値は、５’ｂ００１１０である。
【００４９】
余り除算回路１０４は、余りの合計値が５’ｂ００１１０であるため、変換テーブル４００に基づいて余りの合計値の商として３’ｂ０１０を出力し、余りの合計値の余りとして２’ｂ００を出力する。
【００５０】
繰り上げ加算回路１０５は、商加算回路１０２から出力された加算結果に余り除算回路１０４から出力された余りの合計値の商を加算する。すなわち、繰り上げ加算回路１０５は、３４’ｂ００００００００００００００００００１１１００１１０１０１００１１１に３’ｂ０１０を加算する。繰り上げ加算回路１０５による加算結果（１７７１４７を３で除算した商）は、５９０４９（３４’ｂ００００００００００００００００００１１１００１１０１０１０１００１）である。
【００５１】
つぎに、割り算回路１００の使用例について説明する。割り算回路１００では２n−１が除数の場合において、高速に除算することができる。たとえば、ＤＩＭＭ（Ｄｕａｌ  Ｉｎｌｉｎｅ  Ｍｅｍｏｒｙ  Ｍｏｄｕｌｅ）を接続するメモリコントローラＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）において、ＤＩＭＭのチャネル数が３（ｎ＝２，２n−１＝３)であった場合、従来技術では３チャネルにまたがるメモリインターリーブを行う際に高速にチャネルを切り替えることが出来なかった。メモリインターリーブとは、ブロック分けされたメモリモジュールの複数に対して同時・並行的にアクセスすることにより、メモリへのアクセスを高速化する技術である。
【００５２】
しかしながら、上述した本発明の実施例を用いれば、除数が３の場合に最短で１クロックで算出が終了するため、高速にチャネルを切り替えることができる。
【００５３】
図７は、メモリコントローラにおけるメモリアクセス時間の一例を示す説明図である。図７では、理解の容易化のため、チャネルインターリーブ無しと、チャネルインターリーブ有りと、を示す。（１）チャネルインターリーブ無しでは、ＣＰＵの処理時間に比べてメモリアクセスにかかる時間が長いため、全体の処理時間がメモリアクセスにかかる時間のほぼ総和となる。一方、（２）チャネルインターリーブ有りの場合、メモリアクセスが並列に行われるため、全体の処理時間が（１）チャネルインターリーブ無しから大幅に短縮される。
【００５４】
図８は、メモリコントローラにおける３チャネルインターリーブの一例を示す説明図である。図８では、複数のＤＩＭＭがチャネル０〜チャネル２に分けられている。チャネル０は、ＤＩＭＭ０１〜ＤＩＭＭ０ｊ（ｊ≧１）を有し、チャネル１は、ＤＩＭＭ１１〜ＤＩＭＭ１ｊを有し、チャネル２は、ＤＩＭＭ２１〜ＤＩＭＭ２ｊを有している。
【００５５】
メモリコントローラ８００は、メモリアドレスに基づいていずれのチャネルにアクセスするか、該チャネルのうちのいずれのＤＩＭＭへアクセスするかを制御する。メモリコントローラ８００は割り算回路１００と選択回路８０１とを有する。割り算回路１００は、除数がチャネル数（３）である。メモリコントローラ８００は、選択されたメモリアドレスを被除数として割り算回路１００へ入力する。割り算回路１００は、メモリアドレスを３で除算し、商と余りを選択回路８０１へ出力する。割り算回路１００の余り除算回路から出力された余りがメモリアドレスを３で除算した余りであり、割り算回路１００の繰り上げ加算回路１０５から出力された加算結果がメモリアドレスを３で除算した商である。
【００５６】
選択回路８０１は、割り算回路１００から出力された余りに基づいてチャネルを選択する。そして、選択回路８０１は、割り算回路１００から出力された商に基づいて該選択したチャネル内のＤＩＭＭを選択する。たとえば、指定されたメモリアドレスが３で除算された余りが０であれば、選択回路８０１がチャネル０を選択し、指定されたメモリアドレスが３で除算された商が２であれば、ＤＩＭＭ０２を選択する。メモリコントローラ８００は、メモリアドレスを順に選択し、チャネルを切り替えることにより、ＤＩＭＭを並列して選択することができる。
【００５７】
以上説明したように、割り算回路によれば、被除数をｋビットごとに分割する。そして、分割被除数ごとに該分割被除数の下位にｋの整数倍ビット分の０を付与した値を２n−１の除数で除算する。そして、分割被除数ごとの除算結果をすべて加算し、加算結果を、被除数を除数で除算した商とする。ｋビットの分割被除数にｋの整数倍ビット分の０を付与して特定の除数で除算した商のうち、下位ｋの整数倍ビットはｋビットごとに同一値が繰り返される特性を用いることにより、除算を並列化することができる。さらに、同一の除算が並列化されているため、回路を縮小化することができる。２n−１を除数とする除算の商を最短１クロックで行うことができ、除算処理を高速化することができる。さらに、商レジスタが不要となり、組合せ回路のみで計算を実現することができるため、割り算回路を縮小化することができる。
【００５８】
また、分割被除数の値ごとに、分割被除数の下位にｋの整数倍ビット分の０を付与した値を２n−１の除数で除算した２ｋビットの商を２k通り保持し、各分割被除数に応じて２ｋビットの商を出力することにより、割り算回路を縮小化することができる。
【００５９】
さらに、分割被除数の値ごとに、分割被除数の下位にｋの整数倍ビット分の０を付与した値を２n−１の除数で除算した余りを算出し、分割被除数ごとの余りをすべて加算する。そして、余りの合計が除数を超える場合、余りの合計値をさらに２n−１である特定の除数で除算することによって、被除数を除数で割った商と余りを算出する。これにより、２n−１を除数とする除算の商と余りの算出を最短１クロックで行うことができ、除算処理を高速化することができる。さらに、商レジスタと余りレジスタが不要となり、組合せ回路のみで計算を実現することができる。
【００６０】
また、分割被除数の値ごとに、分割被除数の下位にｋの整数倍ビット分の０を付与した値を除数で除算した２ｋビットの商と余りを２k通り保持し、各分割被除数に応じて２ｋビットの商と余りを出力する。
【００６１】
また、２n−１個のチャネルに分割されたメモリモジュールへアクセスする場合、メモリアドレスが２n−１で除算された余りに応じてチャネルを選択し、除数が２n−１の除数で除算された商に応じて選択したチャネルに属するメモリモジュールを選択する。最短１クロックで除算処理を行うことができる除算回路を用いることで、メモリアクセスの高速化を図ることができる。
【００６２】
上述した実施の形態に関し、さらに以下の付記を開示する。
【００６３】
（付記１）２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商を出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
を備えることを特徴とする割り算回路。
【００６４】
（付記２）前記第１の出力回路は、
前記分割被除数の値ごとに２k通りの前記２ｋビットの商を保持し、前記分割被除数ごとに前記分割被除数に応じた前記２ｋビットの商を出力することを特徴とする付記１に記載の割り算回路。
【００６５】
（付記３）２n−１（ｎ≧２の整数）である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商と余りとを出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
前記第１の出力回路から前記分割被除数ごとに出力された余りの合計値を算出する余り加算回路と、
前記余り加算回路によって算出された余りの合計値を前記特定の除数で除算した商と余りを出力する余り除算回路と、
前記商加算回路から出力された加算結果と前記余り除算回路から出力された商とを加算する繰り上げ加算回路と、
を備えることを特徴とする割り算回路。
【００６６】
（付記４）前記第１の出力回路は、
前記分割被除数の値ごとに２k通りの前記２ｋビットの商と余りとを保持し、前記分割被除数ごとに前記分割被除数に応じた前記２ｋビットの商と余りを出力することを特徴とする付記３に記載の割り算回路。
【００６７】
（付記５）複数のメモリモジュールが２n−１（ｎ≧２の整数）のチャネルに分割されているメモリモジュール群へのアクセスを制御するメモリコントローラであって、
前記チャネルの数である特定の除数のビット幅より大きいｈビットの被除数を、前記被除数の最下位ビットから順にｋビット（ｋ＝ｎの整数倍）で分割し、ｈ／ｋ個の分割被除数を出力する分割回路と、
前記分割回路から出力された分割被除数ごとに、前記分割被除数の下位にｋの整数倍ビット分の０が付与された値が前記特定の除数で除算された２ｋビットの商と余りとを出力する第１の出力回路と、
前記最下位ビットを含む前記分割被除数からの前記各分割被除数の配列位置をｉ（ｉ＝０〜ｈ／ｋ−１）とした場合、前記分割被除数ごとに、前記第１の出力回路から出力された２ｋビットの商のうちの上位ｋビットの第１のビット列と、前記２ｋビットの商のうちの下位ｋビットをｉ個並べた第２のビット列と、を出力する第２の出力回路と、
前記第２の出力回路から出力された第１のビット列を上位のビット列とし、前記第２の出力回路から出力された第２のビット列を下位のビット列とした前記分割被除数ごとの値をすべて加算する商加算回路と、
前記第１の出力回路から前記分割被除数ごとに出力された余りの合計値を算出する余り加算回路と、
前記余り加算回路によって算出された余りの合計値を前記特定の除数で除算した商と余りを出力する余り除算回路と、
前記商加算回路から出力された加算結果と前記余り除算回路から出力された商とを加算する繰り上げ加算回路と、
前記余り除算回路から出力された余りに応じて前記２n−１のチャネルから１個のチャネルを選択し、前記１個のチャネルに属する複数のメモリモジュールから、前記繰り上げ加算回路から出力された加算結果に応じて１個のメモリモジュールを選択する選択回路と、
を備えることを特徴とするメモリコントローラ。
【符号の説明】
【００６８】
１００  割り算回路
１０１  分割回路
１０２  商加算回路
１０３  余り加算回路
１０４  余り除算回路
１０５  繰り上げ加算回路
１１０〜１１８  除算回路
２０１，２５１  第１の出力回路
２０２，２５２  第２の出力回路
８００  メモリコントローラ
８０１  選択回路
【国際調査報告】
2012086073.tif 000011
2012086073.tif 000012