(57)【要約】      （修正有）【課題】切り上げ演算を含む数式の近似計算を高速に行うことができる演算回路及び方法を提供する。【解決手段】所定のｘの関数を所定値で除算した余りをｒとする。数式のｘをｒの関数で置き換えかつ切り上げ演算の代わりに１に近い１未満の値を加算してから小数点以下を切り捨てる演算を行う第１の式から、数式のｘをｒの関数で置き換えかつ切り上げ演算を行わない第２の式を引いたものを関数ｆ（ｒ）とする。ｒに対するｆ（ｒ）の計算結果を予めテーブルにまとめておく。与えられたｘの値に対して切り上げ演算を行わないで数式を計算して近似値ｑを計算する。与えられたｘの値に対してｒを計算する。計算したｒの値に対するｆ（ｒ）の値をテーブルから取り出し、このｆ（ｒ）の値と近似値ｑを足し合わせる。【選択図】図１
2011175433.tif 000002
【特許請求の範囲】
【請求項１】
切り上げ演算を含むｘの関数である数式の近似計算を行う演算回路であって、
所定のｘの関数を所定値で除算した余りをｒとし、前記数式のｘをｒの関数で置き換えかつ前記切り上げ演算の代わりに１に近い１未満の値を加算してから小数点以下を切り捨てる演算を行う第１の式から、前記数式のｘを前記ｒの関数で置き換えかつ前記切り上げ演算を行わない第２の式を引いた関数をｆ（ｒ）とし、ｒに対するｆ（ｒ）の計算結果を予めまとめたテーブルと、
与えられたｘの値に対して前記切り上げ演算を行わないで前記数式を計算して近似値ｑを計算する回路と、
与えられたｘの値に対してｒを計算する回路と、
計算したｒの値に対するｆ（ｒ）の値を前記テーブルから取り出し、このｆ（ｒ）の値と前記近似値ｑを足し合わせる回路とを備えることを特徴とする演算回路。
【請求項２】
切り上げ演算を含むｘの関数である数式の近似計算を行う演算方法であって、
所定のｘの関数を所定値で除算した余りをｒとし、前記数式のｘをｒの関数で置き換えかつ前記切り上げ演算の代わりに１に近い１未満の値を加算してから小数点以下を切り捨てる演算を行う第１の式から、前記数式のｘを前記ｒの関数で置き換えかつ前記切り上げ演算を行わない第２の式を引いた関数をｆ（ｒ）とし、ｒに対するｆ（ｒ）の計算結果を予めテーブルにまとめておく工程と、
与えられたｘの値に対して前記切り上げ演算を行わないで前記数式を計算して近似値ｑを計算する工程と、
与えられたｘの値に対してｒを計算する工程と、
計算したｒの値に対するｆ（ｒ）の値を前記テーブルから取り出し、このｆ（ｒ）の値と前記近似値ｑを足し合わせる工程とを備えることを特徴とする演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、資源の配分量を算出する演算回路及び方法に関し、特に切り上げ演算を含む数式の近似計算を高速に行うことができる演算回路及び方法に関する。
【背景技術】
【０００２】
通信システムでは取り扱うデータ量が急激に増えており、データ伝送速度の更なる高速化が要求されている。これに対して、アルゴリズムを高速に演算する処理回路として様々なものが提案されている（例えば、特許文献１参照）。
【０００３】
また、例えばルータの行うパケット毎の優先制御などにおいて、複数のシステムに資源を効率的に配分することが要求されている。システムが必要とする資源の配分要求量ｘに対して配分すべき配分量ｙを算出する演算の一例を以下に示す。
ｙ＝ＲＯＵＮＤＵＰ［ＲＯＵＮＤＵＰ（ｘ×５／５４，０）×６２／５，０］  （数式１）
ここで、ＲＯＵＮＤＵＰ（Ａ，Ｋ）は数値Ａを指定した桁数Ｋで切り上げる演算関数である。
【０００４】
図３は、従来の演算回路を示すブロック図である。演算回路２０，２２は数式１の乗除算を行い、ＲＯＵＮＤＵＰ回路２１，２３は数式１の切り上げ演算を行う。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−９４６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
切り上げ演算には時間がかかるため、従来の演算回路及び方法は切り上げ演算を含む数式１の計算を高速に行うことができなかった。
【０００７】
本発明は、上述のような課題を解決するためになされたもので、その目的は切り上げ演算を含む数式の近似計算を高速に行うことができる演算回路及び方法を得るものである。
【課題を解決するための手段】
【０００８】
本発明に係る演算回路は、切り上げ演算を含むｘの関数である数式の近似計算を行う演算回路であって、所定のｘの関数を所定値で除算した余りをｒとし、前記数式のｘを前記ｒの関数で置き換えかつ前記切り上げ演算の代わりに１に近い１未満の値を加算してから小数点以下を切り捨てる演算を行う第１の式から、前記数式のｘを前記ｒの関数で置き換えかつ前記切り上げ演算を行わない第２の式を引いた関数をｆ（ｒ）とし、ｒに対するｆ（ｒ）の計算結果を予めまとめたテーブルと、与えられたｘの値に対して前記切り上げ演算を行わないで前記数式を計算して近似値ｑを計算する回路と、与えられたｘの値に対してｒを計算する回路と、計算したｒの値に対するｆ（ｒ）の値を前記テーブルから取り出し、このｆ（ｒ）の値と前記近似値ｑを足し合わせる回路とを備える。
【０００９】
本発明に係る演算方法は、切り上げ演算を含むｘの関数である数式の近似計算を行う演算方法であって、所定のｘの関数を所定値で除算した余りをｒとし、前記数式のｘを前記ｒの関数で置き換えかつ前記切り上げ演算の代わりに１に近い１未満の値を加算してから小数点以下を切り捨てる演算を行う第１の式から、前記数式のｘを前記ｒの関数で置き換えかつ前記切り上げ演算を行わない第２の式を引いた関数をｆ（ｒ）とし、ｒに対するｆ（ｒ）の計算結果を予めテーブルにまとめておく工程と、与えられたｘの値に対して前記切り上げ演算を行わないで前記数式を計算して近似値ｑを計算する工程と、与えられたｘの値に対してｒを計算する工程と、計算したｒの値に対するｆ（ｒ）の値を前記テーブルから取り出し、このｆ（ｒ）の値と前記近似値ｑを足し合わせる工程とを備える。
【発明の効果】
【００１０】
本発明により、切り上げ演算を含む数式の近似計算を高速に行うことができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施の形態に係る演算回路を示すブロック図である。
【図２】各パラーメータについて計算した結果を示す図である。
【図３】従来の演算回路を示すブロック図である。
【発明を実施するための形態】
【００１２】
本発明の実施の形態に係る演算回路及び方法について説明する。この演算回路及び方法は、切り上げ演算を含むｘの関数である数式１の近似計算を行うことで、システムが必要とする資源の配分要求量ｘに対して配分すべき配分量ｙを算出するものである。
【００１３】
まず、以下の数式２を定義する。
ｑ＝ＩＮＴ［（ｘ×７５２４５＋２３０４）÷２１６］  （数式２）
ここで、ｑは正整数を表す。ＩＮＴ（Ｂ）は数値Ｂを超えない最大の整数であり、小数点以下を切り捨てるＩＮＴ演算を行う演算関数である。
【００１４】
ｑは、数式１を切り上げ演算なしで近似した（ｘ×５／５４×６２／５）を１次関数で線形近似したものである。２のｎ乗（この場合ｎ＝１６）の除算で近似しており、ｎが大きい値ほど近似精度がよくなる。この除算は除数が２のｎ乗であるためビットシフトで実現することができる。また、２３０４の数値によりゼロ点をずらすことにより、より近い近似が得られる。
【００１５】
数式２に含まれる数値について説明する。数式１の右辺を切り上げ演算なしで近似した（ｘ×５／５４×６２／５）の１次関数の傾き６２／５４に２１６を乗算すると近似的に７５２４５が算出される。この傾きを近似した値と正確な値の差は、（２１６×６２／５４−７５２４５）×２１６＝２４２７．２５６…である。演算のビット数を抑えるために２のｎ乗で割れる数にすると９×２８＝２３０４が得られる。
【００１６】
また、以下の数式３を定義する。
ｒ＝ＭＯＤ［ＩＮＴ［（ｘ×９７０９＋２５６０）÷２１２］，２７］  （数式３）
ここで、ｒは正整数を表す。ＭＯＤ（Ｃ，Ｄ）は数値Ｃを数値Ｄで割った場合の余りを求める演算関数である。即ち、ｒは、所定のｘの関数［ＩＮＴ［（ｘ×９７０９＋２５６０）÷２１２］を所定値２７で除算した余りである。２のｎ乗（この場合ｎ＝１２）の除算で近似しており、ｎが大きい値ほど近似精度がよくなる。この除算は除数が２のｎ乗であるためビットシフトで実現することができる。
【００１７】
数式３に含まれる数値について説明する。数式１のＲＯＵＮＤＵＰ（ｘ×５／５４，０）は、ｘが５４増えるごとに切り上げた数値が増える。そこで、ｘが５４増えるごとに数値が増えるように、線形近似した１次関数のｘの係数ｍを求める。即ち、ｍ＝（２１２×２７）÷５４＝９７０９．０３７…である。この傾きを近似した値と正確な値の差は、（４０９６×２７／５４−９７０９）×６５５３６＝２４２７．２５８…である。演算のビット数を抑えるために２のｎ乗で割れる数にすると５×２９＝２５６０が得られる。
【００１８】
ｒは０〜１２７の整数値となる。そこで、０〜５３の整数値をとるように以下のｒの関数を定義する。
ＩＮＴ（ｒ×５４／２７＋１／２）  （数式４）
【００１９】
また、以下の数式５を定義する。
ｆ（ｒ）＝ＩＮＴ｛ＩＮＴ［ＩＮＴ（ｒ×５４／２７＋１／２）×５／５４＋６３／６４］×６２／５＋７／８｝−ＩＮＴ［ＩＮＴ（ｒ×５４／２７＋１／２）×６２／５４］  （数式５）
ここで、ｆ（ｒ）は正整数となる。
【００２０】
数式５の６３／６４、７／８は数式１の切り上げ演算をＩＮＴ演算に変換した場合の切り上げの加算値である。従って、数式５の右辺の第１の式は、数式１のｘを数式４で置き換え、かつ切り上げ演算の代わりに１に近い１未満の値を加算してからＩＮＴ演算を行うものである。一方、数式５の右辺の第２の式は、数式１のｘを数式４で置き換え、かつ切り上げ演算を行わないものである。
【００２１】
以下の数式６により数式１の近似計算を行うことができる。
ｙ＝ｑ＋ｆ（ｒ）  （数式６）
ここで、０≦ｘ≦（２１６−１）であれば誤差は生じない。
【００２２】
図１は、本発明の実施の形態に係る演算回路を示すブロック図である。演算回路１０は数式２の乗算、加算、及び除算を行う。ＩＮＴ回路１１は数式２のＩＮＴ演算を行う。演算回路１２は、数式３の乗算、加算、及び除算を行う。ＩＮＴ回路１３は数式３のＩＮＴ演算を行う。ＭＯＤ回路１４は数式３のＭＯＤ演算を行う。テーブル１５には、ｒに対するｆ（ｒ）の計算結果が予めまとめられている。加算回路１６は数式６の加算を行う。
【００２３】
図２は、各パラーメータについて計算した結果を示す図である。ｒはｘが５４増えるごとに周期的に同じ値となる。従って、ｘの数値範囲に関わらず、ｒとｆ（ｒ）の相関関係がまとめられたテーブル１５の内容量は限られる。
【００２４】
ｘの値が与えられると、演算回路１０及びＩＮＴ回路１１は、数式２に従ってｘの値に対して数式２を計算して近似値ｑを計算する。また、演算回路１２、ＩＮＴ回路１３及びＭＯＤ回路１４は、数式３に従ってｘの値に対してｒを計算する。次に、加算回路１６は、計算したｒの値に対するｆ（ｒ）の値をテーブル１５から取り出し、このｆ（ｒ）の値と近似値ｑを足し合わせる。これによりｙの値が求まる。
【００２５】
以上説明したように、本実施の形態は、切り上げ演算を行うことなく、数式１の近似計算を行うことができる。従って、切り上げ演算を含む数式１の近似計算を高速に行うことができる。
【００２６】
また、２つの乗算は並列動作が可能なため、乗算１段分の速度での高速パイプライン処理も可能となる。そして、乗算回路をハードマクロとして内蔵したＦＰＧＡ(Field Programmable Gate Array)を使用することで更なる高速処理が可能である。
【符号の説明】
【００２７】
１０，１２  演算回路
１１，１３  ＩＮＴ回路
１４  ＭＯＤ回路
１５  テーブル
１６  加算回路
【図１】
2011175433.tif 000003
【図２】
2011175433.tif 000004
【図３】
2011175433.tif 000005