(57)【要約】【課題】データサイズが大きな整数xiに対し、多倍長演算によってR=x1・r1+…+xI・rIの演算を高速で行う。【解決手段】まず、xiを各ビット長がω(j)であるxi(j)毎〔j∈{1,...,J}, Jは2以上の自然数, xiはxi(J),…,xi(1)のビット結合xi=xi(J)|…|xi(1)〕に分割する。そして、α(j)とキャッシュメモリに読み込まれたxi(j)およびriとを用い、T(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行い、T(j)の下位ω(j)ビットをRjとし、T(j)のRj以外のビットを新たなα(j+1)とする処理を、j=1およびα=0を初期値とし、j=1からjを１ずつ増加させながらj=Jまで行う。その後、α(J),RJ,...,R1のビット結合R=α(J)|RJ|…|R1を算出し、Rを出力する。【選択図】図１
2008287489.tif 000002
【特許請求の範囲】
【請求項１】
Iを2以上の自然数とし、i∈{1,...,I}とし、xiを０以上の整数とし、riを整数とした場合における、R=x1・r1+…+xI・rIの演算を行う多倍長演算方法であって、
ビット分割部が、xiを各ビット長がω(j)であるxi(j)毎〔j∈{1,...,J}, Jは2以上の自然数, xiはxi(J),…,xi(1)のビット結合xi=xi(J)|…|xi(1)〕に分割するビット分割過程と、
演算制御部が、jに1を代入し、α(1)に0を代入する初期化過程と、
積和演算部が、α(j)とキャッシュメモリに読み込まれたxi(j)およびriとを用い、T(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行う積和演算過程と、
上記積和演算過程後、シフト部が、T(j)の下位ω(j)ビットをRjとし、T(j)のRj以外のビットを新たなα(j+1)とするシフト過程と、
上記シフト過程後、演算制御部が、j=Jであるか否かを判定する判定過程と、
上記判定過程でj≠Jと判定された場合、演算制御部が、j+1を新たなjとして処理を上記積和演算過程に戻すループ過程と、
上記判定過程でj=Jと判定された場合、ビット結合部が、α(J),RJ,...,R1のビット結合R=α(J)|RJ|…|R1を算出し、Rを出力するビット結合過程と、
を有することを特徴とする多倍長演算方法。
【請求項２】
請求項１に記載の多倍長演算方法であって、
上記キャッシュメモリの記憶容量は、
何れか一つのxiのデータ量とすべてのriのデータ量との合計値よりも小さく、当該xiを分割して得られた一つのxi(j)のデータ量とすべてのriのデータ量との合計値よりも大きい、
ことを特徴とする多倍長演算方法。
【請求項３】
請求項１または２に記載の多倍長演算方法であって、
上記積和演算過程は、上記積和演算部が所定のビット長W単位で演算を行う過程であり、
ω(j)は、上記所定のビット長Wよりも長く、xiのビット長よりも短い、
ことを特徴とする多倍長演算方法。
【請求項４】
請求項１に記載の多倍長演算方法であって、
ω(j)は、すべてのjについて一定である、
ことを特徴とする多倍長演算方法。
【請求項５】
請求項１に記載の多倍長演算方法であって、
上記積和演算過程は、
上記積和演算部が、xi(j)をビット長W−a（W＞a≧0）毎に分割したxi(j,p)〔p∈{1,...,P}, Pは1以上の自然数, xi(j)はxi(j,P),...,xi(j,1)のビット結合xi(j)=xi(j,P)|…|xi(j,1)〕と、riをビット長W−b（W＞b≧0, I≦2a+b）毎に分割したri(q)〔q∈{1,...,Q}, Qは1以上の自然数, riはri(Q),...,ri(1)のビット結合ri=ri(Q)|…|ri(1)〕とを用い、ビット長W単位で演算を行って１組以上のp,qについてx1(j,p)・r1(q)+…+xI(j,p)・rI(q)を算出し、当該演算結果を用いてT(j)=α(j)+x1(j)・r1+…+xI(j)・rIを算出する過程である、
ことを特徴とする多倍長演算方法。
【請求項６】
請求項１に記載の多倍長演算方法であって、
上記ビット分割部で分割された各xi(j)は、
x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でバースト転送可能にメモリに格納され、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序で順次キャッシュメモリに読み込まれる、
ことを特徴とする多倍長演算方法。
【請求項７】
Iを2以上の自然数とし、i∈{1,...,I}とし、xiを０以上の整数とし、riを整数とした場合における、R=x1・r1+…+xI・rIの演算を行う多倍長演算方法であって、
Hを2以上の整数とし、h∈{1,...,H}とし、S(h)を2以上の整数とし、s(h)∈{1,...,S(h)}とし、i(h,s(h))∈{i(h,1),...,i(h,S(h))}⊂{1,...,I}とし、{i(1,1),...,i(1,S(1)),...,i(H,1),...,i(H,S(H))}={1,...,I}とし、R(h)=xi(h,1)・ri(h,1)+…+xi(h,S(h))・ri(h,S(h))とし、J(h)を2以上の自然数とし、j∈{1,...,J(h)}とした場合における、
(a)ビット分割部が、xi(h,s(h))を各ビット長がω(h,j)であるxi(h,s(h))(j)毎〔xi(h,s(h))はxi(h,s(h))(J(h)),…,xi(h,s(h))(1)のビット結合xi(h,s(h))=xi(h,s(h))(J(h))|…|xi(h,s(h))(1)〕に分割するビット分割過程と、
(b)演算制御部が、jに1を代入し、α(h,1)に0を代入する初期化過程と、
(c)hに対応するri(h,1),...,ri(h,S(h))をキャッシュメモリに読み込むキャッシュ過程と、
(d)積和演算部が、α(h,j)とキャッシュメモリに読み込まれたxi(h,s(h))(j)およびri(h,s(h))とを用い、T(h,j)=α(h,j)+xi(h,1)(j)・ri(h,1)+…+xi(h,S(h))(j)・ri(h,S(h))の演算を行う積和演算過程と、
(e)上記積和演算過程後、シフト部が、T(h,j)の下位ω(h,j)ビットをR(h,j)とし、T(h,j)のR(h,j)以外のビットを新たなα(h,j+1)とするシフト過程と、
(f)上記シフト過程後、演算制御部が、j=J(h)であるか否かを判定する判定過程と、
(g)上記判定過程でj≠J(h)と判定された場合、演算制御部が、j+1を新たなjとして処理を上記積和演算過程に戻すループ過程と、
(h)上記判定過程でj=J(h)と判定された場合、ビット結合部が、α(h,J(h)),R(h,J(h)),...,R(h,1)のビット結合R(h)=α(h,J(h))|R(h,J(h))|…|R(h,1)を算出するビット結合過程と、
を各hについて順次実行し、
加算部が、R=R(1)+…+R(H)を算出し、Rを出力する加算過程と、
を有することを特徴とする多倍長演算方法。
【請求項８】
請求項７に記載の多倍長演算方法であって、
上記キャッシュメモリの記憶容量は、
何れか一つのxi(h,s(h))のデータ量とすべてのriのデータ量との合計値よりも小さく、当該xi(h,s(h))を分割して得られた一つのxi(h,s(h))(j)のデータ量と当該hに対応するri(h,1),...,ri(h,S(h))のデータ量との合計値よりも大きい、
ことを特徴とする多倍長演算方法。
【請求項９】
Iを2以上の自然数とし、i∈{1,...,I}とし、xiを０以上の整数とし、riを整数とした場合における、R=x1・r1+…+xI・rIの演算を行う多倍長演算装置であって、
xiを各ビット長がω(j)であるxi(j)毎〔j∈{1,...,J}, Jは2以上の自然数, xiはxi(J),…,xi(1)のビット結合xi=xi(J)|…|xi(1)〕に分割するビット分割部と、
α(j)とキャッシュメモリに読み込まれたxi(j)およびriとを用い、T(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行う積和演算部と、
T(j)の下位ω(j)ビットをRjとし、T(j)のRj以外のビットを新たなα(j+1)とするシフト部と、
j=1およびα=0を初期値とし、j=1からjを１ずつ増加させながらj=Jまで、上記積和演算部と上記シフト部との処理を実行させる演算制御部と、
α(J),RJ,...,R1のビット結合R=α(J)|RJ|…|R1を算出し、Rを出力するビット結合部と、
を有することを特徴とする多倍長演算装置。
【請求項１０】
請求項１から８の何れかに記載の多倍長演算方法の各過程をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多倍長演算を行う技術に関し、特にサイズの大きいデータを対象とした多倍長演算を高速で行う技術に関する。
【背景技術】
【０００２】
CPU（Central Processing Unit）レジスタが扱うことができるデータのビット数には、32ビット,64ビットなどの制限がある。そのため、汎用CPUにおいてCPUレジスタが扱うことができるビット数を超える大きな整数の演算を行う場合、多倍長演算方式と呼ばれる演算方式が利用される。一般に多倍長演算方式では、大きな整数をCPUレジスタが扱うことができるビット長（ワード長）毎に区切った配列を用い、当該ワード長単位で演算を行う。
【０００３】
通常、ＣＰＵ上で演算に利用されるデータは、メインメモリからＣＰＵレジスタにロードされ、ＣＰＵ上で計算がなされた後、計算結果がメインメモリにストアされる。しかし、単純な演算にかかる時間に比べ、データをメインメモリからＣＰＵレジスタにロードする時間のほうが大きい。そのため、一般的なＣＰＵでは、キャッシュメモリと呼ばれる高速にアクセス可能なメモリにメインメモリのデータの一部を複製した後、当該キャッシュメモリからＣＰＵレジスタにデータをロードする。そして、同一データを二回目以降にロードする際にキャッシュメモリのデータを用いることで、高速化を実現している。
【０００４】
また、データがすべてキャッシュメモリに存在する環境で多倍長演算を高速に行うアプローチとして、演算コスト（演算するために必要な時間）が大きい演算を演算コストの小さい演算の組み合わせに変換することによって全体の演算コストを低減させる方法が採られる。例えば、大きな整数同士の乗算を一般的なＣＰＵで行う場合、乗算の演算コストが和算の演算コストよりも大きいため、Karatsuba法（非特許文献１）などのような、積演算を和演算に変換して高速化を図る方法が採られることが一般的である。
【非特許文献１】梅谷  武、“Karatsuba法”、［online］、平成13年2月14日、［平成19年5月8日検索］、インターネット〈URL http://homepage1.nifty.com/~umetani/ims/2001/20010214001/0.html〉
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、従来の方法では、データサイズが大きな整数xiに対し、多倍長演算によってR=x1・r1+…+xI・rI（Iは2以上の自然数、i∈{1,...,I}、riは整数）の演算を行う場合、十分高速に演算を行うことができないことがある。
xiのデータサイズが非常に大きな値（例えば1Mビット程度）であった場合、キャッシュメモリに読み込まれた各xiがキャッシュメモリを溢れ、ＣＰＵがxiを参照するたびにメインメモリにアクセスしなければならない状況となる。一般にキャッシュメモリは高速にアクセス可能なメモリであるが、その記憶容量はメインメモリに比べて非常に小さい。そのため、さらにメインメモリへのアクセス速度が計算速度に比べて遅くなるような環境では、演算コストではなく、メインメモリへのアクセス時間がボトルネックとなって演算速度が低下する。
【０００６】
本発明はこのような点に鑑みてなされたものであり、データサイズが大きな整数xiに対し、多倍長演算によってR=x1・r1+…+xI・rIの演算を高速で行う技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明では上記課題を解決するために、ビット分割部が、xiを各ビット長がω(j)であるxi(j)毎〔j∈{1,...,J}, Jは2以上の自然数, xiはxi(J),…,xi(1)のビット結合xi=xi(J)|…|xi(1)〕に分割するビット分割過程と、演算制御部が、jに1を代入し、α(1)に0を代入する初期化過程と、積和演算部が、α(j)とキャッシュメモリに読み込まれたxi(j)およびriとを用い、T(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行う積和演算過程と、上記積和演算過程後、シフト部が、T(j)の下位ω(j)ビットをRjとし、T(j)のRj以外のビットを新たなα(j+1)とするシフト過程と、上記シフト過程後、演算制御部が、j=Jであるか否かを判定する判定過程と、上記判定過程でj≠Jと判定された場合、演算制御部が、j+1を新たなjとして処理を上記積和演算過程に戻すループ過程と、上記判定過程でj=Jと判定された場合、ビット結合部が、α(J),RJ,...,R1のビット結合R=α(J)|RJ|…|R1を算出し、Rを出力するビット結合過程と、を有する多倍長演算によってR=x1・r1+…+xI・rIの多倍長演算を行う。
【０００８】
ここで、積和演算部が取り扱うxi(j)はxiから分割されたデータであり、Jは2以上の自然数であるため、xi(j)のビット長はxiのビット長よりも短い。そのため、積和演算部がxiを取り扱う場合に比べ、データがキャッシュメモリから溢れてしまう頻度を低減させ、メインメモリへのアクセス回数を低減させることができる。その結果、全体として演算速度を向上させることができる。
【０００９】
また、本発明において好ましくは、上記キャッシュメモリの記憶容量は、何れか一つのxiのデータ量とすべてのriのデータ量との合計値よりも小さく、当該xiを分割して得られた一つのxi(j)のデータ量とすべてのriのデータ量との合計値よりも大きい。この場合、すべてのriをキャッシュメモリ上に格納して演算を行う環境において、データがキャッシュメモリから溢れてしまう頻度を確実に低減させることができる。
【００１０】
また、本発明において好ましくは、上記積和演算過程は、上記積和演算部が所定のビット長W単位で演算を行う過程であり、ω(h)は、上記所定のビット長Wよりも長く、xiのビット長よりも短い。この場合、積和演算部はxi(j)のデータを２回以上参照する必要があるため、本発明によってxi(j)がキャッシュメモリから溢れる頻度を低下させることにより、メインメモリへのアクセス回数を確実に低減させることができる。
【００１１】
また、本発明において好ましくは、ω(j)は、すべてのjについて一定である。これにより、積和演算部は各jについて同一の桁上げ処理を使用でき、全体として演算内容を簡略化できる。その効果の一例として、積和演算部を構成するためのプログラム長を短くすることができる。
【００１２】
また、本発明において好ましくは、上記積和演算過程は、上記積和演算部が、xi(j)をビット長W−a（W＞a≧0）毎に分割したxi(j,p)〔p∈{1,...,P}, Pは1以上の自然数, xi(j)はxi(j,P),...,xi(j,1)のビット結合xi(j)=xi(j,P)|…|xi(j,1)〕と、riをビット長W−b（W＞b≧0, I≦2a+b）毎に分割したri(q)〔q∈{1,...,Q}, Qは1以上の自然数, riはri(Q),...,ri(1)のビット結合ri=ri(Q)|…|ri(1)〕とを用い、ビット長W単位で演算を行って１組以上のp,qについてx1(j,p)・r1(q)+…+xI(j,p)・rI(q)を算出し、当該演算結果を用いてT(j)=α(j)+x1(j)・r1+…+xI(j)・rIを算出する過程である。
【００１３】
ここで、ビット長W−aのxi(j,p)とビット長W−bのri(q)との積xi(j,p)・ri(q)のビット長は必ず２・W以下となり、さらにI≦2a+bであるため、x1(j,p)・r1(q)+…+xI(j,p)・rI(q)のビット長も必ず２・W以下となる。この場合、x1(j,p)・r1(q)+…+xI(j,p)・rI(q)を算出する過程においてビット長２・W以上の桁上げ処理が不要となる。その結果、桁上げ処理数を削減でき、演算速度を向上させることができる。なお、x1(j,p)・r1(q)+…+xI(j,p)・rI(q)の演算結果を用いたT(j)=α(j)+x1(j)・r1+…+xI(j)・rIの算出は、例えば、公知の多倍長演算方法を用いて可能である。
【００１４】
また、本発明において好ましくは、上記ビット分割部で分割された各xi(j)は、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でバースト転送可能にメモリに格納され、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序で順次キャッシュメモリに読み込まれる。
【００１５】
ここで、積和演算部は、j=1からj=JまでのT(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行うに際し、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でxi(j)を使用する。このようにx1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でバースト転送可能にこれらのデータをメモリに格納しておくことにより、ランダム転送よりバースト転送の方が効率がよい環境においてxi(j)の転送速度が向上し、全体として演算速度が向上する。
【００１６】
また、Iを2以上の自然数とし、i∈{1,...,I}とし、xiを０以上の整数とし、riを整数とした場合における、R=x1・r1+…+xI・rIの演算を行う多倍長演算方法であって、Hを2以上の整数とし、h∈{1,...,H}とし、S(h)を2以上の整数とし、s(h)∈{1,...,S(h)}とし、i(h,s(h))∈{i(h,1),...,i(h,S(h))}⊂{1,...,I}とし、{i(1,1),...,i(1,S(1)),...,i(H,1),...,i(H,S(H))}={1,...,I}とし、R(h)=xi(h,1)・ri(h,1)+…+xi(h,S(h))・ri(h,S(h))とし、J(h)を2以上の自然数とし、j∈{1,...,J(h)}とした場合における、(a)ビット分割部が、xi(h,s(h))を各ビット長がω(h,j)であるxi(h,s(h))(j)毎〔xi(h,s(h))はxi(h,s(h))(J(h)),…,xi(h,s(h))(1)のビット結合xi(h,s(h))=xi(h,s(h))(J(h))|…|xi(h,s(h))(1)〕に分割するビット分割過程と、(b)演算制御部が、jに1を代入し、α(h,1)に0を代入する初期化過程と、(c)hに対応するri(h,1),...,ri(h,S(h))をキャッシュメモリに読み込むキャッシュ過程と、(d)積和演算部が、α(h,j)とキャッシュメモリに読み込まれたxi(h,s(h))(j)およびri(h,s(h))とを用い、T(h,j)=α(h,j)+xi(h,1)(j)・ri(h,1)+…+xi(h,S(h))(j)・ri(h,S(h))の演算を行う積和演算過程と、(e)上記積和演算過程後、シフト部が、T(h,j)の下位ω(h,j)ビットをR(h,j)とし、T(h,j)のR(h,j)以外のビットを新たなα(h,j+1)とするシフト過程と、(f)上記シフト過程後、演算制御部が、j=J(h)であるか否かを判定する判定過程と、(g)上記判定過程でj≠J(h)と判定された場合、演算制御部が、j+1を新たなjとして処理を上記積和演算過程に戻すループ過程と、(h)上記判定過程でj=J(h)と判定された場合、ビット結合部が、α(h,J(h)),R(h,J(h)),...,R(h,1)のビット結合R(h)=α(h,J(h))|R(h,J(h))|…|R(h,1)を算出するビット結合過程と、を各hについて順次実行し、加算部が、R=R(1)+…+R(H)を算出し、Rを出力する加算過程と、を有する多倍長演算方法が提供される。
【００１７】
この方法では、R=x1・r1+…+xI・rI=R(1)+…+R(H)とし、R(h)毎に本発明を適用してRを算出する。この方法は、iの値が大きく、すべてのr1,…,rIを一度にキャッシュメモリに格納できない場合に有効である。
【００１８】
また、この場合、上記キャッシュメモリの記憶容量は、何れか一つのxi(h,s(h))のデータ量とすべてのriのデータ量との合計値よりも小さく、当該xi(h,s(h))を分割して得られた一つのxi(h,s(h))(j)のデータ量と当該hに対応するri(h,1),...,ri(h,S(h))のデータ量との合計値よりも大きいことが望ましい。積和演算部がR(h)を算出するために必要なri(h,1),...,ri(h,S(h))を一度にキャッシュメモリに格納できるからである。
【発明の効果】
【００１９】
以上のように、本発明により、データサイズが大きな整数xiに対し、多倍長演算によってR=x1・r1+…+xI・rIの演算を高速で行うことが可能となる。
【発明を実施するための最良の形態】
【００２０】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔第１の実施形態〕
まず、本発明の第１の実施形態について説明する。
＜構成＞
図１は、本形態の多倍長演算装置１の構成を示したブロック図であり、図２は、図１のレジスタファイル５０及び積和演算部６０の詳細構成を例示したブロック図である。なお、図１，２における矢印はデータの流れを示すが、演算制御部９０に対するデータの入出力の流れ、および、レジスタファイル５０へのデータの入出力の流れの一部については、記載を省略している。
【００２１】
図１に例示するように、本形態の多倍長演算装置１は、メインメモリ１０、ビット分割部２０、キャッシュメモリ３０、レジスタ格納部４０、レジスタファイル５０、積和演算部６０、シフト部７０、ビット結合部８０および演算制御部９０を有している。
本形態の多倍長演算装置１は、ＣＰＵ、ＲＡＭ（Random Access Memory）、ＲＯＭ（Compact Disc Read Only Memory）、ハードディスク装置、バス等からなる公知のコンピュータに所定のプログラムが読みこまれ、ＣＰＵがそのプログラムを実行することにより構築されるものである。
【００２２】
すなわち、メインメモリ１０は、例えばＲＡＭやハードディスク装置等に相当する。また、キャッシュメモリ３０は、メインメモリ１０よりも高速にアクセス可能なメモリであり、例えばＣＰＵ内に構成されたキャッシュメモリに相当する。また、図２に例示するようにレジスタファイル５０は、例えばＣＰＵ内に構成され、記憶可能なデータのビット長（レジスタ長）がそれぞれWである複数のレジスタ５１を有している。なお、Wは積和演算部６０の演算処理単位であり、例えばワード長に相当する。また、Wの値としては32ビットや64ビットを例示できるが、本発明はこれに限定されるものではない。
【００２３】
また、ビット分割部２０、積和演算部６０、シフト部７０、ビット結合部８０および演算制御部９０は、例えば所定のプログラムが読み込まれたＣＰＵに相当する。ここで、図２に例示した積和演算部６０はKaratsuba法（非特許文献１参照）によって多倍長の乗算を行う場合のブロック図であり、ビット長W単位で乗算を行う乗算部６１、減算部６２、加算部６３および桁上げ部６４を具備する。
【００２４】
＜多倍長演算方法＞    
次に、本形態の多倍長演算方法を説明する。
［前提］
本形態では、L（Lは２以上の自然数）ビット長のビットデータX∈{0,1}Ｌを所定の手順に従いI（Iは２以上の自然数）個に分割した０以上の整数xi（i∈{1,...,I}、xiはビットデータ）と、与えられた整数ri（i∈{1,...,I}、riはビットデータ）とを用い、R=x1・r1+…+xI・rIの多倍長演算を行う。また、そのための前処理として、整数xiと整数riとがメインメモリ１０に格納されているものとする。
【００２５】
［R=x1・r1+…+xI・rIの多倍長演算］
図４は、本形態の多倍長演算方法を説明するためのフローチャートである。以下、この図を用いて説明を行っていく。
【００２６】
まず、ビット分割部２０が、メインメモリ１０からxiを読み込み、xiを各ビット長がω(j)であるxi(j)毎に分割し、各xi(j)をメインメモリ１０に格納する（ステップＳ１／ビット分割過程）。図３（ａ）は、各xiをxi(j)毎に分割した様子を示した概念図である。ここで、j∈{1,...,J}であり、 Jは2以上の自然数の定数であり、xi=xi(J)|…|xi(1)（xi(J)|…|xi(1)はxi(J),…,xi(1)のビット結合）の関係を満たす。また、ω(j)は、所定のビット長Wよりも長く、xiのビット長よりも短い。また、本形態のキャッシュメモリ３０の記憶容量は、何れか一つのxiのデータ量とすべてのriのデータ量との合計値よりも小さく、当該xiを分割して得られた一つのxi(j)のデータ量とすべてのriのデータ量との合計値よりも大きいものとする。また、前述のように、演算の効率化のためには、ω(j)はすべてのjについて一定であることが望ましい。
【００２７】
ステップＳ１の後、演算制御部９０が、jに1を代入し、α(1)に0を代入し、それらの結果をレジスタ５１に格納する（ステップＳ２／初期化過程）。なお、演算制御部９０は、レジスタ５１に格納されたjおよびα(j)の値を用いて各処理を制御する。
【００２８】
次に、演算制御部９０の制御のもと、メインメモリ１０に格納されたすべてのriがキャッシュメモリ３０に読み込まれる（ステップＳ３）。
【００２９】
その後、積和演算部６０が、メインメモリ１０からキャッシュメモリ３０にxi(j)を読み込みつつ、α(j)とキャッシュメモリ３０に読み込まれたxi(j)およびriとを用い、ワード長Wの多倍長演算によってT(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行い、その演算結果T(j)を出力する（ステップＳ４／積和演算過程）。すなわち、レジスタ格納部４０が、キャッシュメモリ３０に格納されたxi(j)（図３（ａ））をビット長W毎に分割したxi(j,p)〔p∈{1,...,P}, P≧2, xi(j)=xi(j,P)|…|xi(j,1)〕（図３（ｂ））と、キャッシュメモリ３０に格納されたri（図３（ｃ））をビット長W毎に分割したri(q)〔q∈{1,...,Q}, ri=ri(Q)|…|ri(1)〕（図３（ｄ））とを、レジスタ長Wのレジスタ５１に格納しつつ、積和演算部６０、シフト部７０およびビット結合部８０が、ワード長Wの多倍長演算によってT(j)=α(j)+x1(j)・r1+…+xI(j)・rIの演算を行って出力する。以下、積和演算過程（ステップＳ４）の具体例を説明する。
【００３０】
［積和演算過程（ステップＳ４）の具体例］
図５は、図４の積和演算過程（ステップＳ４）の具体例を説明するためのフローチャートである。以下、この図に沿って説明を行う。なお、ここではKaratuba法（非特許文献１）を用いた処理を例示する。しかし、本発明はこれに限定されるものではなく、その他の公知の多倍長演算方法（よく知られた筆算のアルゴリズムや高速フーリエ変換を用いたアルゴリズム等）を使用してステップＳ４を実行してもよい。また、説明の簡略化のため、ここではxi(j)及びriのビット長ω(j)がそれぞれ２ワード（２・W）以下の場合を例示する。
【００３１】
まず、演算制御部９０がiに1を代入し、iをレジスタ５１に格納する（ステップＳ４ａ）。なお、演算制御部９０は、レジスタ５１に格納されたiを用いて各処理を制御する。
【００３２】
次に、演算制御部９０は、キャッシュメモリ３０にxi(j)が存在するか否かを判断する（ステップＳ４ｂ）。ここで、キャッシュメモリ３０にxi(j)が格納されていた場合、演算制御部９０は処理をステップＳ４ｄに移し、キャッシュメモリ３０にxi(j)が格納されていなかった場合、メインメモリ１０からキャッシュメモリ３０にxi(j)を読み込んで処理をステップＳ４ｄに移す。
【００３３】
ステップＳ４ｄでは、xi(j)をビット長W毎に分割したxi(j,p)〔p∈{1,2}, xi(j)=xi(j,2)|xi(j,1)〕と、riをビット長W毎に分割したri(q)〔q∈{1,2}, ri=ri(2)|ri(1)〕とを用い、si(j,1)=xi(j,1)・ri(1), si(j,3)=xi(j,2)・ri(2), si(j,2)={xi(j,2)-xi(j,1)}・(ri(1)-ri(2))+si(j,1)+si(j,3)を算出する（ステップＳ４ｄ）。具体的には、例えば、レジスタ格納部４０が、xi(j,1)及びri(1)をキャッシュメモリ３０から読み込んでレジスタ５１に格納し、乗算部６１（図２）が、格納されたxi(j,1)及びri(1)を用いてsi(j,1)=xi(j,1)・ri(1)を算出し、si(j,1)をレジスタ５１に格納する。また、例えば、レジスタ格納部４０が、xi(j,2)及びri(2)をキャッシュメモリ３０から読み込んでレジスタ５１に格納し、乗算部６１が、格納されたxi(j,2)及びri(2)を用いてsi(j,3)=xi(j,2)・ri(2)を算出し、si(j,3)をレジスタ５１に格納する。さらに、乗算部６１，減算部６２および加算部６３が、レジスタ５１に格納されたデータを用いてsi(j,2)={xi(j,2)-xi(j,1)}・(ri(1)-ri(2))+si(j,1)+si(j,3)を算出し、si(j,2) をレジスタ５１に格納する。なお、本形態のキャッシュメモリ３０の記憶容量は、一つのxi(j)のデータ量とすべてのriのデータ量との合計値よりも大きいため、キャッシュメモリ３０にさらに他の演算やテンポラリ領域が確保できるのであれば、si(j,1)=xi(j,1)・ri(1), si(j,3)=xi(j,2)・ri(2), si(j,2)={xi(j,2)-xi(j,1)}・(ri(1)-ri(2))+si(j,1)+si(j,3)の演算に必要なxi(j)及びriはキャッシュメモリ３０から溢れることはない。この場合、ステップＳ４ｄにおいてメインメモリ１０へアクセスする必要はない（本形態の特徴）。
【００３４】
ステップＳ４ｄの後、演算制御部９０がレジスタ５１に格納されたiがIであるか否かの判断を行い（ステップＳ４ｅ）、i=Iでなければi+1を新たなIとしてレジスタ５１に格納した後（ステップＳ４ｆ）、処理をステップＳ４ｂに戻す。一方、i=Iであれば、加算部６３が、レジスタ５１のデータを用いてs(j,1)=s1(j,1)+...+sI(j,1), s(j,2)=s1(j,2)+...+sI(j,2), s(j,3)=s1(j,3)+...+sI(j,3)を算出し、s(j,1), s(j,2), s(j,3)をレジスタ５１に格納する（ステップＳ４ｇ）。
【００３５】
ステップＳ４ｇの後、加算部６３が、レジスタ５１のデータを用いてs(j,1)+α(j)を算出し、桁上げ部６４が、その演算結果の下位WビットをT(j,1)とし、それ以外のビットをβ(j,2)とし、それらをレジスタ５１に格納する（ステップＳ４ｈ）。次に、加算部６３が、レジスタ５１のデータを用いてs(j,2)+β(j,2)を算出し、桁上げ部６４が、その演算結果の下位WビットをT(j,2)とし、それ以外のビットをβ(j,3)とし、それらをレジスタ５１に格納する（ステップＳ４ｉ）。次に、加算部６３が、レジスタ５１のデータを用いてs(j,3)+β(j,3)を算出し、その演算結果をT(j,3)としてレジスタ５１に格納する（ステップＳ４ｊ）。
【００３６】
その後、ビット結合部８０がレジスタ５１に格納されているT(j,3), T(j,2), T(j,1)のビット結合T(j)=T(j,3)|T(j,2)|T(j,1)を出力する（ステップＳ４ｋ／［積和演算過程（ステップＳ４）の具体例］の説明終わり）。
積和演算過程（ステップＳ４）後、シフト部７０が、T(j)の下位ω(j)ビットをRjとし、T(j)のRj以外のビットを新たなα(j+1)とし、これらを出力する（ステップＳ５／シフト過程）。
【００３７】
シフト過程（ステップＳ５）後、演算制御部９０が、レジスタ５１に格納したjを参照しj=Jであるか否かを判定する（ステップＳ６／判定過程）。ここで、j≠Jと判定された場合、演算制御部９０は、j+1を新たなjとして新たなjをレジスタ５１に格納し、処理を積和演算過程（ステップＳ４）に戻す（ステップＳ７／ループ過程）。一方、判定過程（ステップＳ６）でj=Jと判定された場合、ビット結合部８０が、α(J),RJ,...,R1のビット結合R=α(J)|RJ|…|R1を算出し、Rを出力する（ステップＳ８／ビット結合過程）。
【００３８】
以上のように、本形態では、キャッシュメモリ３０にさらに他の演算やテンポラリ領域が確保できるのであれば、ステップＳ４ｄにおいてメインメモリ１０へアクセスする必要はないため、演算速度が向上する。
【００３９】
〔第２の実施形態〕
次に、本発明の第２の実施形態について説明する。
本形態は、第１の実施形態の変形例であり、積和演算過程（ステップＳ４）において、積和演算部６０が、xi(j)をビット長W−a（W＞a≧0）毎に分割したxi(j,p)〔p∈{1,...,P}, Pは1以上の自然数, xi(j)はxi(j,P),...,xi(j,1)のビット結合xi(j)=xi(j,P)|…|xi(j,1)〕と、riをビット長W−b（W＞b≧0, I≦2a+b）毎に分割したri(q)〔q∈{1,...,Q}, Qは1以上の自然数, riはri(Q),...,ri(1)のビット結合ri=ri(Q)|…|ri(1)〕とを用い、ビット長W単位で演算を行って１組以上のp,qについてx1(j,p)・r1(q)+…+xI(j,p)・rI(q)を算出し、当該演算結果を用いてT(j)=α(j)+x1(j)・r1+…+xI(j)・rIを算出する点のみが第１の実施形態と相違する。以下では、この相違点のみを説明する。
【００４０】
＜実施例１＞
本形態の実施例１は、P=Q=2、b>aとし（図６（ａ），（ｂ））、筆算のアルゴリズムによってビット長W単位の乗算を行う例である。
図７は、第２の実施形態の実施例１におけるステップＳ４の処理を説明するためのフローチャートである。以下、この図に沿って本実施例２におけるステップＳ４の処理を説明する。
【００４１】
本実施例１のステップＳ４ａ〜４ｃは、第１の実施形態と同じであるため説明を省略する。本実施例１では、ステップＳ４ｂまたはＳ４ｃの後、キャッシュメモリ３０に読み込まれた、xi(j)をビット長W-a毎に分割したxi(j,p)〔p∈{1,2}, xi(j)=xi(j,2)|xi(j,1)〕と、riをビット長W-b(b>a)毎に分割したri(q)〔q∈{1,2}, ri=ri(2)|ri(1)〕とを用い、si(j,1)=xi(j,1)・ri(1), si(j,2)=xi(j,1)・ri(2), si(j,3)=xi(j,2)・ri(1), si(j,4)=xi(j,2)・ri(2)を算出する（ステップＳ４ｍ）。
【００４２】
具体的には、例えば、レジスタ格納部４０が、xi(j,1)及びri(1)をキャッシュメモリ３０から読み込んでレジスタ５１に格納し、乗算部６１（図２）が、格納されたxi(j,1)及びri(1)を用いてsi(j,1)=xi(j,1)・ri(1)を算出し、si(j,1)をレジスタ５１に格納する。また、例えば、レジスタ格納部４０が、xi(j,2)及びri(2)をキャッシュメモリ３０から読み込んでレジスタ５１に格納し、乗算部６１が、格納されたxi(j,2)及びri(2)を用いてsi(j,3)=xi(j,2)・ri(2)を算出し、si(j,3)をレジスタ５１に格納する。さらに、乗算部６１が、レジスタ５１に格納されたデータを用いてsi(j,2)=xi(j,1)・ri(2)およびsi(j,3)=xi(j,2)・ri(1)を算出し、si(j,2)およびsi(j,3)をレジスタ５１に格納する。なお、xi(j,p)のビット長はW-aであり、ri(q)のビット長はW-bであるため、si(j,1), si(j,2), si(j,3), si(j,4)は、何れも2・W-(a+b)〔=(W-a)+(W-b)〕ビットのビット列となる。
【００４３】
ステップＳ４ｍの後、演算制御部９０がレジスタ５１に格納されたiがIであるか否かの判断を行い（ステップＳ４ｅ）、i=Iでなければi+1を新たなIとしてレジスタ５１に格納した後（ステップＳ４ｆ）、処理をステップＳ４ｂに戻す。一方、i=Iであれば、加算部６３が、レジスタ５１のデータを用いてs(j,1)=s1(j,1)+...+sI(j,1), s(j,2)=s1(j,2)+...+sI(j,2), s(j,3)=s1(j,3)+...+sI(j,3),s(j,4)=s1(j,4)+...+sI(j,4)を算出し、s(j,1), s(j,2), s(j,3) , s(j,4)をレジスタ５１に格納する（ステップＳ４ｎ）。なお、本形態では、si(j,1), si(j,2), si(j,3), si(j,4)は、何れも2・W-(a+b)〔=(W-a)+(W-b)〕ビットのビット列となり、I≦2a+bを満たすため、s(j,1), s(j,2), s(j,3) , s(j,4)は何れも2・Wビット以下のビット列となる。すなわち、ステップＳ４ｎの演算において2ワード以上の桁上がり処理は不要である（本形態の特徴）。
【００４４】
ステップＳ４ｎの後、加算部６３が、レジスタ５１のデータを用いてs(j,1)+α(j)を算出し、桁上げ部６４が、その演算結果の下位W-bビットをT(j,1)とし、それ以外のビットをβ(j,2)とし、それらをレジスタ５１に格納する（ステップＳ４ｐ）。次に、加算部６３が、レジスタ５１のデータを用いてs(j,2)+β(j,2)を算出し、桁上げ部６４が、その演算結果の下位b-a〔=(W-a)-(W-b)〕ビットをT(j,2)とし、それ以外のビットをβ(j,3)とする（ステップＳ４ｑ）。次に、加算部６３が、レジスタ５１のデータを用いてs(j,3)+β(j,3)を算出し、桁上げ部６４が、その演算結果の下位(W-b)〔=(W-a)+(W-b)-(W-a)〕ビットをT(j,3)とし、それ以外のビットをβ(j,4)とする（ステップＳ４ｒ）。次に、加算部６３が、レジスタ５１のデータを用いてs(j,4)+β(j,4)を算出し、その演算結果をT(j,4)としてレジスタ５１に格納する（ステップＳ４ｓ）。
【００４５】
その後、ビット結合部８０が、レジスタ５１に格納されているT(j,4),T(j,3), T(j,2), T(j,1)のビット結合T(j)=T(j,4)|T(j,3)|T(j,2)|T(j,1)を出力する（ステップＳ４ｔ）。
＜実施例２＞
本形態の実施例２は、P=Q=2、b=aとし（図６（ｃ），（ｄ））、Karatsuba法（非特許文献１）によってビット長W単位の乗算を行う例である。
図８は、第２の実施形態の実施例２におけるステップＳ４の処理を説明するためのフローチャートである。以下、この図に沿って本実施例２におけるステップＳ４の処理を説明する。第１の実施形態と本実施例２との相違点は、ステップＳ４ｄ（図５）がステップＳ４ｔ（図８）に置換される点のみである。
【００４６】
本実施例のステップＳ４ｔでは、xi(j)をビット長W-a毎に分割したxi(j,p)〔p∈{1,2}, xi(j)=xi(j,2)|xi(j,1)〕と、riをビット長W-b毎に分割したri(q)〔q∈{1,2}, ri=ri(2)|ri(1)〕とを用い、si(j,1)=xi(j,1)・ri(1), si(j,3)=xi(j,2)・ri(2), si(j,2)={xi(j,2)-xi(j,1)}・(ri(1)-ri(2))+si(j,1)+si(j,3)を算出する（ステップＳ４ｔ）。ここで、xi(j,p)のビット長はW-aであり、ri(q)のビット長はW-bであるため、si(j,1), si(j,2), si(j,3)は、何れも2・W-(a+b)〔=(W-a)+(W-b)〕ビットのビット列となる。また、I≦2a+bを満たすため、その後のステップＳ４ｇで算出されるs(j,1), s(j,2), s(j,3)は、何れも2・Wビット以下のビット列となる。すなわち、ステップＳ４ｇの演算において2ワード以上の桁上がり処理は不要である（本形態の特徴）。
【００４７】
以上のように、本形態では、x1(j,p)・r1(q)+…+xI(j,p)・rI(q)は何れも2・Wビット以下のビット列となる。よって、x1(j,p)・r1(q)+…+xI(j,p)・rI(q)の演算において2ワード以上の桁上がり処理は不要となり、演算コストを低減させることができる。
【００４８】
〔第３の実施形態〕
本形態は、第１，２の実施形態の変形例である。第１，２の実施形態との相違点は、ビット分割部２０で分割された各xi(j)が、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でバースト転送可能にメインメモリ１０に格納され、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序で順次キャッシュメモリ３０に読み込まれる点である。
【００４９】
図９は、メインメモリ１０に格納されたx1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)を例示した概念図である。図９に例示するように、本形態では、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序で各xi(j)がメインメモリ１０に格納される。これにより、メインメモリ１０に格納されたx1(1)の先頭アドレスを指定するだけで、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でxi(j)を順次キャッシュメモリ３０にバースト転送することができる。図４のステップＳ４では、x1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でxi(j)が必要となるため、各xi(j)をx1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)の順序でバースト転送可能にメインメモリ１０に格納する構成は、本発明にとって好ましい。
【００５０】
〔第４の実施形態〕
本形態は、第１，２の実施形態の変形例であり、R=x1・r1+…+xI・rI=R(1)+…+R(H)とし、R(h)（h∈{1,...,H}，Hは2以上の整数の定数）毎に本発明の手法を適用するものである（本形態の特徴）。本形態は、Iの値が大きく、すべてのr1,...,rIを同時にキャッシュメモリ３０上に格納できない場合にメインメモリ１０へのアクセス回数を削減できる手法である。すなわち、キャッシュメモリ３０の記憶容量が、何れか一つのxi(h,s(h))のデータ量とすべてのriのデータ量との合計値よりも小さく、当該xi(h,s(h))を分割して得られた一つのxi(h,s(h))(j)のデータ量と当該hに対応するri(h,1),...,ri(h,S(h))のデータ量との合計値よりも大きい場合に特に有効な手法である。ただし、S(h)は2以上の整数であり、s(h)∈{1,...,S(h)}であり、i(h,s(h))∈{i(h,1),...,i(h,S(h))}⊂{1,...,I}であり、{i(1,1),...,i(1,S(1)),...,i(H,1),...,i(H,S(H))}={1,...,I}であり、R(h)=xi(h,1)・ri(h,1)+…+xi(h,S(h))・ri(h,S(h))である。
【００５１】
以下では、第１，２の実施形態との相違点を中心に説明を行い、第１，２の実施形態と共通する事項については説明を省略する。
＜構成＞
図１０は、本形態の多倍長演算装置１００の構成を示したブロック図である。なお、図１０における矢印はデータの流れを示すが、演算制御部９０に対するデータの入出力の流れ、および、レジスタファイル５０へのデータの入出力の流れの一部については、記載を省略している。
【００５２】
図１０に例示するように、本形態の多倍長演算装置１００は、メインメモリ１０、ビット分割部２０、キャッシュメモリ３０、レジスタ格納部４０、レジスタファイル５０、積和演算部６０、シフト部７０、ビット結合部８０、演算制御部９０および加算部１１０を有している。なお、図１０において図１と処理機能が同一な部分については、図１と同じ符号を付している。
【００５３】
＜多倍長演算方法＞    
次に、本形態の多倍長演算方法を説明する。
［前提］
第１の実施形態で説明したのと同じである。
［R=x1・r1+…+xI・rIの多倍長演算］
図１１は、本形態の多倍長演算方法を説明するためのフローチャートである。以下、この図を用いて説明を行っていく。
まず、演算制御部９０が、hに1を代入し、hをレジスタファイル５０のレジスタ５１に格納する（ステップＳ１１）。演算制御部９０は、レジスタ５１に格納されたhを用いて各処理を制御する。
【００５４】
次に、ビット分割部２０が、メインメモリ１０からxi(h,s(h))を読み込み、xi(h,s(h))を各ビット長がω(h,j)であるxi(h,s(h))(j)毎に分割し、各xi(h,s(h))(j)をメインメモリ１０に格納する（ステップＳ１２／ビット分割過程）。なお、xi(h,s(h))はxi(h,s(h))(J(h)),…,xi(h,s(h))(1)のビット結合xi(h,s(h))=xi(h,s(h))(J(h))|…|xi(h,s(h))(1)であり、J(h)は2以上の自然数の定数であり、j∈{1,...,J(h)}である。
次に、演算制御部９０が、jに1を代入し、α(h,1)に0を代入し、それらをレジスタファイル５０のレジスタ５１に格納する（ステップＳ１３／初期化過程）。なお、演算制御部９０は、レジスタ５１に格納されたjおよびα(h,1)を用いて各処理を制御する。また、演算制御部９０の制御のもと、hに対応するri(h,1),...,ri(h,S(h))がキャッシュメモリに読み込まれる（ステップＳ１４／キャッシュ過程）。
【００５５】
その後、積和演算部６０が、xi(h,s(h))(j)を順次キャッシュメモリ３０に読み込みながら、α(h,j)とxi(h,s(h))(j)およびri(h,s(h))とを用い、T(h,j)=α(h,j)+xi(h,1)(j)・ri(h,1)+…+xi(h,S(h))(j)・ri(h,S(h))の演算を行い、T(h,j)を出力する（ステップＳ１５／積和演算過程）。積和演算過程後（ステップＳ１５）、シフト部７０が、T(h,j)の下位ω(h,j)ビットをR(h,j)とし、T(h,j)のR(h,j)以外のビットを新たなα(h,j+1)とし、R(h,j)とα(h,j+1)とを出力する（ステップＳ１６／シフト過程）。
【００５６】
シフト過程後（ステップＳ１６）、演算制御部９０が、レジスタファイル５０のレジスタ５１に格納されたjを参照し、j=J(h)であるか否かを判定する（ステップＳ１７／判定過程）。ここで、j≠J(h)と判定された場合、演算制御部９０が、j+1を新たなjとしてjをレジスタ５１に格納し、処理をステップＳ１５に戻す（ステップＳ１８／ループ過程）。一方、判定過程（ステップＳ１７）でj=J(h)と判定された場合、ビット結合部８０が、α(h,J(h)),R(h,J(h)),...,R(h,1)のビット結合R(h)=α(h,J(h))|R(h,J(h))|…|R(h,1)を算出してR(h)を出力する（ステップＳ１９／ビット結合過程）。
【００５７】
次に、演算制御部９０が、レジスタ５１を参照してh=Hであるか否かを判定し、h=Hでなければ、h+1を新たなhとしてレジスタ５１に格納し（ステップＳ２１）、処理をステップＳ１２に戻す。一方、h=Hであれば、加算部１１０が、R=R(1)+…+R(H)を算出し、Rを出力する（ステップＳ２１／加算過程）。
【００５８】
〔第５の実施形態〕
本形態は、第４の実施形態に第３の実施の形態を適用した形態である。すなわち、本形態では、h=1からh=Hまでの順序で、それぞれのhについて各xi(h,s(h))(j)が、xi(h,1)(1),...,xi(h,S(h))(1),xi(h,1)(2),...,xi(h,S(h))(2),...,xi(h,1)(J(h)),...,xi(h,S(h))(J(h))の順序でバースト転送可能にメインメモリ１０に格納され、xi(h,1)(1),...,xi(h,S(h))(1),xi(h,1)(2),...,xi(h,S(h))(2),...,xi(h,1)(J(h)),...,xi(h,S(h))(J(h))の順序で順次キャッシュメモリ３０に読み込まれる(本形態の特徴)。
【００５９】
図１２（ａ）（ｂ）は、メインメモリ１０に格納されたxi(h,1)(1),...,xi(h,S(h))(1),xi(h,1)(2),...,xi(h,S(h))(2),...,xi(h,1)(J(h)),...,xi(h,S(h))(J(h))を例示した概念図である。
【００６０】
図１２（ａ）に例示するように、各xi(h,s(h))(j)は、xi(h,1)(1),...,xi(h,S(h))(1),xi(h,1)(2),...,xi(h,S(h))(2),...,xi(h,1)(J(h)),...,xi(h,S(h))(J(h))の順序でバースト転送可能にメインメモリ１０に格納される。ここで、xi(h,1)(1),...,xi(h,S(h))(1),xi(h,1)(2),...,xi(h,S(h))(2),...,xi(h,1)(J(h)),...,xi(h,S(h))(J(h))が格納されたメインメモリ１０の領域をブロック［h］と呼ぶ。また、ブロック［h］の先頭アドレスをAS(h)と表現し、終了アドレスをAE(h)と表現する。
【００６１】
また、図１２（ｂ）に示すように、各ブロック［h］は、ブロック［1］, ブロック［2］,..., ブロック［H］の順序でバースト転送可能にメインメモリ１０に格納される。これにより、各xi(h,s(h))(j)は、xi(1,1)(1),...,xi(1,S(1))(1),xi(1,1)(2),...,xi(1,S(1))(2),...,xi(1,1)(J(1)),...,xi(1,S(1))(J(1)),...,xi(H,1)(1),...,xi(H,S(H))(1),xi(H,1)(2),...,xi(H,S(H))(2),...,xi(H,1)(J(H)),...,xi(H,S(H))(J(H))の順序でバースト転送可能にメインメモリ１０に格納される。これにより、xi(1,1)(1)の先頭アドレスAS(h)を指定するのみで、メインメモリ１０からキャッシュメモリ３０にxi(1,1)(1),...,xi(1,S(1))(1),xi(1,1)(2),...,xi(1,S(1))(2),...,xi(1,1)(J(1)),...,xi(1,S(1))(J(1)),...,xi(H,1)(1),...,xi(H,S(H))(1),xi(H,1)(2),...,xi(H,S(H))(2),...,xi(H,1)(J(H)),...,xi(H,S(H))(J(H))の順序でバースト転送可能である。
【００６２】
図１１のステップＳ１５では、xi(1,1)(1),...,xi(1,S(1))(1),xi(1,1)(2),...,xi(1,S(1))(2),...,xi(1,1)(J(1)),...,xi(1,S(1))(J(1)),...,xi(H,1)(1),...,xi(H,S(H))(1),xi(H,1)(2),...,xi(H,S(H))(2),...,xi(H,1)(J(H)),...,xi(H,S(H))(J(H))の順序でxi(h,s(h))(j)が必要となるため、この順序でバースト転送可能にメインメモリ１０に格納する構成は、本発明にとって好ましい。
【００６３】
〔実験結果〕
以上のように、上述の各形態では、キャッシュメモリ３０の記憶容量（キャッシュサイズ）を他の演算や演算ｎ途中のテンポラリ領域との合計で超えさせるようなxiと、キャッシュサイズよりもサイズの小さなriに対するR=x1・r1+…+xI・rIの多倍長演算の演算速度を向上させることができる。
【００６４】
図１３に、この効果を示すため実験結果を示す。図１３では、Athlon64x2 2Ghzにおいて本発明を適用することなく「小田哲，山本剛，青木和麻呂，“高速データ検証”，SCIS, Jan.23-26 2007（「参考文献１」）」の演算を行った場合（従来方法）と、Athlon64x2 2Ghzにおいて第１の実施形態を適用して参考文献１の演算を行った場合（第１の実施形態）とでの演算速度の比較を示す。図１３に示すように、従来方法での演算速度は12.5(Gbps)程度であるのに対し、第１の実施形態での演算速度は8(Gbps)程度である。
【００６５】
〔変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各実施形態の構成を適宜組み合わせて本発明を実施してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００７１】
本発明の産業上の利用分野としては、例えば、参考文献１のデータ検証処理等を例示できる。
【図面の簡単な説明】
【００７２】
【図１】図１は、第１の実施形態の多倍長演算装置の構成を示したブロック図である。
【図２】図２は、図１のレジスタファイル及び積和演算部の詳細構成を例示したブロック図である。
【図３】図３は、データ構成を説明するための概念図である。
【図４】図４は、第１の実施形態の多倍長演算方法を説明するためのフローチャートである。
【図５】図５は、図４の積和演算過程（ステップＳ４）の具体例を説明するためのフローチャートである
【図６】図６は、データ構成を説明するための概念図である。
【図７】図７は、第２の実施形態の実施例１におけるステップＳ４の処理を説明するためのフローチャートである。
【図８】図８は、第２の実施形態の実施例２におけるステップＳ４の処理を説明するためのフローチャートである。
【図９】図９は、メインメモリに格納されたx1(1),...,xI(1),x1(2),...,xI(2),...,x1(J),...,xI(J)を例示した概念図である。
【図１０】図１０は、第４の実施形態の多倍長演算装置の構成を示したブロック図である。
【図１１】図１１は、第４の実施形態の多倍長演算方法を説明するためのフローチャートである。
【図１２】図１２は、メインメモリに格納されたxi(h,1)(1),...,xi(h,S(h))(1),xi(h,1)(2),...,xi(h,S(h))(2),...,xi(h,1)(J(h)),...,xi(h,S(h))(J(h))を例示した概念図である。
【図１３】図１３は、本形態の効果を示すため実験結果を示した図である。
【符号の説明】
【００７３】
１，１００  多倍長演算装置
【図１】
2008287489.tif 000003
【図２】
2008287489.tif 000004
【図３】
2008287489.tif 000005
【図４】
2008287489.tif 000006
【図５】
2008287489.tif 000007
【図６】
2008287489.tif 000008
【図７】
2008287489.tif 000009
【図８】
2008287489.tif 000010
【図９】
2008287489.tif 000011
【図１０】
2008287489.tif 000012
【図１１】
2008287489.tif 000013
【図１２】
2008287489.tif 000014
【図１３】
2008287489.tif 000015