(57)【要約】乗算ユニットが拡張精度アキュムレータを含む。拡張アキュムレータの１つのポーションの内容を汎用レジスタに移動するためのインストラクション（「ＭＦＬＨＸＵ」）、及び汎用レジスタの内容を拡張アキュムレータの１つの部分に移動するためのインストラクション（「ＭＴＬＨＸ」）を含む、マイクロプロセッサのインストラクションが、拡張精度アキュムレータの部分を操作するために提供される。【特許請求の範囲】
【請求項１】
所定数のビットを格納するための少なくとも１つの汎用レジスタを持つマイクロプロセッサ内で使用される乗算ユニットにおいて、
乗算ユニットによって１以上の入力オペランドを受け取る少なくとも１つの入力データ経路と、
１以上の入力オペランドを受け取るよう接続され、かつ該１以上の入力オペランドを用いて乗算を実行するマルチプライヤと、
マルチプライヤの出力を受け取るよう接続され、かつ１以上の入力オペランドの長さの合計よりも大きい数のビットを含む、拡張精度累計された出力データの経路と
を含むことを特徴とする乗算ユニット。
【請求項２】
請求項１記載の乗算ユニットにおいて、該ユニットはさらに、拡張精度累計された出力経路からのデータが格納される拡張精度アキュムレータを含むことを特徴とする乗算ユニット。
【請求項３】
請求項１記載の乗算ユニットにおいて、マルチプライヤは、乗算及び加算の演算を提供することによって、少なくとも２つのオペランドが乗算され、かつ拡張精度アキュムレータの内容に加算されるよう構成されていることを特徴とする乗算ユニット。
【請求項４】
請求項１記載の乗算ユニットにおいて、マルチプライヤは、
算術マルチプライヤと、
多項式マルチプライヤと
を含むことを特徴とする乗算ユニット。
【請求項５】
請求項１記載の乗算ユニットにおいて、算術マルチプライヤは２補数２進算術マルチプライヤであり、多項式マルチプライヤは多項式原理の算術マルチプライヤであることを特徴とする乗算ユニット。
【請求項６】
請求項４記載の乗算ユニットにおいて、多項式マルチプライヤは、乗算加算の演算を提供することによって、少なくとも２つのオペランドが多項式原理で乗算され、拡張精度アキュムレータの内容に加算されるよう構成されていることを特徴とする乗算ユニット。
【請求項７】
請求項１記載の乗算ユニットにおいて、マルチプライヤは、拡張精度アキュムレータにどの値を取り込むかを選定するための計算結果ロジックを含むことを特徴とする乗算ユニット。
【請求項８】
請求項７記載の乗算ユニットにおいて、計算結果ロジックはマルチプレクサであることを特徴とする乗算ユニット。
【請求項９】
請求項１記載の乗算ユニットにおいて、拡張精度累計された出力データ経路からのデータがアキュムレータに格納され、アキュムレータは、
拡張レジスタと、
上位レジスタと、
下位レジスタと
を含むことを特徴とする乗算ユニット。
【請求項１０】
請求項９記載の乗算ユニットにおいて、拡張レジスタ、上位レジスタ、及び下位レジスタは各々、少なくとも１つの汎用レジスタであることを特徴とする乗算ユニット。
【請求項１１】
請求項９記載の乗算ユニットにおいて、拡張レジスタは８ビットの値を格納し、上位レジスタは３２ビットの値を格納し、下位レジスタは３２ビットの値を格納することを特徴とする乗算ユニット。
【請求項１２】
請求項１記載の乗算ユニットにおいて、マイクロプロセッサは、拡張精度アキュムレータの内容を操作するための少なくとも１つのインストラクションを含むことを特徴とする乗算ユニット。
【請求項１３】
請求項１２記載の乗算ユニットにおいて、少なくとも１つのインストラクションは、値を拡張精度アキュムレータから汎用レジスタへ移動するインストラクションを含むことを特徴とする乗算ユニット。
【請求項１４】
請求項１３記載の乗算ユニットにおいて、インストラクションがさらに、拡張精度アキュムレータの内容をシフトするインストラクションを含むことを特徴とする乗算ユニット。
【請求項１５】
請求項１４記載の乗算ユニットにおいて、拡張精度アキュムレータの内容は、拡張精度アキュムレータから汎用レジスタに移動された値の大きさによって、右側にシフトされることを特徴とする乗算ユニット。
【請求項１６】
請求項１２記載の乗算ユニットにおいて、少なくとも１つのインストラクションは、値を汎用レジスタから拡張精度アキュムレータに移動するインストラクションを含むことを特徴とする乗算ユニット。
【請求項１７】
請求項１６記載の乗算ユニットにおいて、インストラクションはさらに拡張精度アキュムレータの内容をシフトするインストラクションを含むことを含むことを特徴とする乗算ユニット。
【請求項１８】
請求項１７記載の乗算ユニットにおいて、拡張精度アキュムレータの内容は、汎用レジスタから拡張精度アキュムレータに移動された値の大きさによって、左側にシフトされることを特徴とする乗算ユニット。
【請求項１９】
少なくとも１つの汎用レジスタを持つマイクロプロセッサ・コア内で、算術演算を実行するための方法において、
演算を実行するためのインストラクションをデータ・ストアから取り出すステップと、
１以上のレジスタを読み取るステップと、
乗算ユニットを用いて演算を実行するステップと
を含み、該乗算ユニットが、
乗算ユニットによって１以上の入力オペランドを受け取るための少なくとも１つの入力レジスタと、
１以上の入力オペランドを受け取るよう接続され、１以上の入力オペランドを用いて乗算を実行するためのマルチプライヤと、
マルチプライヤの出力を受け取るよう接続され、１以上の入力オペランドの長さの合計以上の数のビットを含んでいる拡張精度累計された出力データ経路と
を含むことを特徴とする方法。
【請求項２０】
請求項１９記載の方法において、該方法はさらに、拡張精度アキュムレータ内に、拡張精度累計された出力経路からのデータを格納するステップを含むことを特徴とする方法。
【請求項２１】
請求項１９記載の方法において、該方法はさらに、マルチプライヤを使用して、少なくとも２つのオペランドを乗算し、かつ拡張精度アキュムレータの内容に乗算の結果を加算することによって、乗算加算の演算を実行するステップを含むことを特徴とする方法。
【請求項２２】
請求項１９記載の方法において、マルチプライヤは、
算術マルチプライヤと、
多項式マルチプライヤと
を含むことを特徴とする方法。
【請求項２３】
請求項１９記載の方法において、算術マルチプライヤは、２補数２進算術マルチプライヤであり、多項式マルチプライヤが多項式原理の算術マルチプライヤであることを特徴とする方法。
【請求項２４】
請求項２２記載の方法において、該方法はさらに、多項式マルチプライヤを使用して、少なくとも２つのオペランドを乗算し、かつその乗算の結果を拡張精度アキュムレータの内容に加算することによって、乗算加算の演算を実行するステップとを含むことを特徴とする方法。
【請求項２５】
請求項１９記載の方法において、マルチプライヤは、拡張精度アキュムレータにどの値を取り込むかを選定するための計算結果ロジックを含むことを特徴とする方法。
【請求項２６】
請求項２５記載の方法において、計算結果ロジックはマルチプレクサであることを特徴とする方法。
【請求項２７】
請求項１９記載の方法において、該方法はさらに、
拡張レジスタと、
上位レジスタと、
下位レジスタと
を含むアキュムレータ内に、拡張精度累計された出力データ経路からのデータを格納するステップを含むことを特徴とする方法。
【請求項２８】
請求項２７記載の方法において、拡張レジスタ、上位レジスタ、及び下位レジスタは各々、少なくとも１つの汎用レジスタからなることを特徴とする方法。
【請求項２９】
請求項２７記載の方法において、拡張レジスタが８ビットの値を格納し、上位レジスタが３２ビットの値を格納し、下位レジスタが３２ビットの値を格納することを特徴とする方法。
【請求項３０】
請求項１９記載の方法において、該方法はさらに、拡張精度アキュムレータの内容を操作するステップを含むことを特徴とする方法。
【請求項３１】
請求項３０記載の方法において、内容を操作するステップは、値を拡張精度アキュムレータから汎用レジスタへ移動するステップを含むことを特徴とする方法。
【請求項３２】
請求項３１記載の方法において、内容を操作するステップはさらに、拡張精度アキュムレータの内容をシフトするステップを含むことを特徴とする方法。
【請求項３３】
請求項３２記載の方法において、内容をシフトするステップは、拡張精度アキュムレータから汎用レジスタに移動された値の大きさによって、拡張精度アキュムレータの内容を、右側にシフトするステップを含むことを特徴とする方法。
【請求項３４】
請求項３０記載の方法において、内容をシフトするステップは、値を汎用レジスタから拡張精度アキュムレータに移動するステップを含むことを特徴とする方法。
【請求項３５】
請求項３４記載の方法において、内容をシフトするステップはさらに、拡張精度アキュムレータの内容をシフトするステップを含むことを特徴とする方法。
【請求項３６】
請求項３５記載の方法において、内容をシフトするステップはさらに、汎用レジスタから拡張精度アキュムレータに移動された値の大きさによって、拡張精度アキュムレータの内容を左側にシフトするステップを含むことを特徴とする方法。
【請求項３７】
ソフトウェアで具現化され、かつ少なくとも１つの汎用レジスタ及び１つの乗算ユニットを含むマクロプロセッサ・コアを格納したコンピュータ読み取り可能な記憶媒体において、前記乗算ユニットが、
乗算ユニットによって１以上の入力オペランドを受け取るための少なくとも１つの入力データ経路と、
１以上の入力オペランドを受け取るよう接続され、該１以上の入力オペランドを用いて乗算を実行するためのマルチプライヤと、
マルチプライヤの出力を受け取るよう接続され、かつ１以上の入力オペランドの長さの合計以上の数のビットを含む拡張精度累計された出力データ経路と
を含むことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項３８】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、該記憶媒体はさらに、拡張精度累計された出力経路からのデータが格納される拡張精度アキュムレータを含むことを特徴とする記憶媒体。
【請求項３９】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、マルチプライヤは、乗算加算の演算を実行することによって、少なくとも２つのオペランドを乗算して、拡張精度アキュムレータの内容に加算するよう構成されていることを特徴とする記憶媒体。
【請求項４０】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、マルチプライヤは、
算術マルチプライヤと、
多項式マルチプライヤと
を含むことを特徴とする記憶媒体。
【請求項４１】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、算術マルチプライヤが２補数２進算術マルチプライヤであり、多項式マルチプライヤが多項式原理の算術マルチプライヤであることを特徴とする記憶媒体。
【請求項４２】
請求項４０記載のコンピュータ読み取り可能な記憶媒体において、多項式マルチプライヤは、乗算加算の演算を行って、少なくとも２つのオペランドを多項式原理で乗算して、拡張精度アキュムレータの内容に加算することを特徴とする記憶媒体。
【請求項４３】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、マルチプライヤは、拡張精度アキュムレータにどの値を取り込むかを選定するための計算結果ロジックを含むことを特徴とする記憶媒体。
【請求項４４】
請求項４３記載のコンピュータ読み取り可能な記憶媒体において、計算結果ロジックはマルチプレクサであることを特徴とする記憶媒体。
【請求項４５】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、拡張精度累計された出力データ経路からのデータはアキュムレータに格納され、アキュムレータは、
拡張レジスタと、
上位レジスタと、
下位レジスタと
を含むことを特徴とする記憶媒体。
【請求項４６】
請求項４５記載のコンピュータ読み取り可能な記憶媒体において、拡張レジスタ、上位レジスタ、及び下位レジスタは各々、少なくとも１つの汎用レジスタからなることを特徴とする記憶媒体。
【請求項４７】
請求項４５記載のコンピュータ読み取り可能な記憶媒体において、拡張レジスタが８ビットの値を格納し、上位レジスタが３２ビットの値を格納し、下位レジスタが３２ビットの値を格納することを特徴とする記憶媒体。
【請求項４８】
請求項３７記載のコンピュータ読み取り可能な記憶媒体において、マイクロプロセッサは拡張精度アキュムレータの内容を操作するための少なくとも１つのインストラクションを含むことを特徴とする記憶媒体。
【請求項４９】
請求項４８記載のコンピュータ読み取り可能な記憶媒体において、少なくとも１つのインストラクションは、値を拡張精度アキュムレータから汎用レジスタに移動するインストラクションを含むことを特徴とする記憶媒体。
【請求項５０】
請求項４９記載のコンピュータ読み取り可能な記憶媒体において、インストラクションはさらに、拡張精度アキュムレータの内容をシフトするインストラクションを含むことを特徴とする記憶媒体。
【請求項５１】
請求項５０記載のコンピュータ読み取り可能な記憶媒体において、拡張精度アキュムレータの内容は、拡張精度アキュムレータから汎用レジスタに移動された値の大きさによって右側にシフトされることを特徴とする記憶媒体。
【請求項５２】
請求項４８記載のコンピュータ読み取り可能な記憶媒体において、少なくとも１つのインストラクションが、値を汎用レジスタから拡張精度アキュムレータに移動するインストラクションを含むことを特徴とする記憶媒体。
【請求項５３】
請求項５２記載のコンピュータ読み取り可能な記憶媒体において、インストラクションはさらに、拡張精度アキュムレータの内容をシフトするインストラクションを含むことを特徴とする記憶媒体。
【請求項５４】
請求項５３記載のコンピュータ読み取り可能な記憶媒体において、拡張精度アキュムレータの内容は、汎用レジスタから拡張精度アキュムレータに移動された値の大きさによって左側にシフトされることを特徴とする記憶媒体。
【請求項５５】
マイクロプロセッサにおいて、
拡張レジスタ、上位レジスタ及び下位レジスタを含む拡張精度アキュムレータと、
汎用レジスタと、
第１の移動インストラクションに応じてデータの第１の移動を促進することができるインストラクション実行ユニットであって、データの第１の移動が、（ｉ）下位レジスタの内容を汎用レジスタに移動すること、（ｉｉ）上位レジスタの内容を下位レジスタに移動すること、及び（ｉｉｉ）拡張レジスタの内容を上位レジスタに移動することを含む、インストラクション実行ユニットと
を含むことを特徴とするマイクロプロセッサ。
【請求項５６】
請求項５５記載のマイクロプロセッサにおいて、インストラクション実行ユニットは、第２の移動インストラクションに応じてデータの第２の移動を促進することができ、データの第２の移動は、（ｉ）上位レジスタの内容を拡張レジスタに移動すること、（ｉｉ）下位レジスタの内容を上位レジスタに移動すること、及び（ｉｉｉ）汎用レジスタの内容を下位レジスタに移動することを含むことを特徴とするマイクロプロセッサ。
【請求項５７】
請求項５５記載のマイクロプロセッサにおいて、拡張レジスタ、上位レジスタ、及び下位レジスタは各々、汎用レジスタを含むことを特徴とするマイクロプロセッサ。
【請求項５８】
データを移動するための方法において、
拡張レジスタ、上位レジスタ及び下位レジスタを含む拡張精度アキュムレータを提供するステップと、
汎用レジスタを提供するステップと、
第１のインストラクションに応じて、データを（ｉ）下位レジスタから汎用レジスタに、（ｉｉ）上位レジスタから下位レジスタに、及び（ｉｉｉ）拡張レジスタから上位レジスタに移動するステップと
を含むことを特徴とする方法。
【請求項５９】
請求項５８記載の方法において、該方法はさらに、第２のインストラクションに応じて、データを（ｉ）上位レジスタから拡張レジスタに、（ｉｉ）下位レジスタから上位レジスタに、（ｉｉｉ）汎用レジスタから下位レジスタに移動するステップを含むことを特徴とする方法。
【請求項６０】
請求項５８記載の方法において、拡張レジスタ、上位レジスタ、及び下位レジスタは各々、汎用レジスタを含むことを特徴とする方法。
【請求項６１】
伝送記憶媒体内で具現化されるコンピュータ・データ信号において、
拡張精度アキュムレータを提供するためのコンピュータ読み取り可能な第１のプログラムコードであって、アキュムレータが拡張レジスタ、上位レジスタ、及び下位レジスタを含んでいる、第１のプログラムコードと、
汎用レジスタを提供するためのコンピュータ読み取り可能な第２のプログラムコードと、
第１の移動インストラクションに応じてデータの第１の移動を促進することができるインストラクション実行ユニットを提供するためのコンピュータ読み取り可能な第３のプログラムコードであって、データの第１の移動が、（ｉ）下位レジスタの内容を汎用レジスタに、（ｉｉ）上位レジスタの内容を下位レジスタに、及び（ｉｉｉ）拡張レジスタの内容を上位レジスタに移動することを含む、第３のプログラムコードと
を含むことを特徴とするデータ信号。
【請求項６２】
請求項６１記載のコンピュータ・データ信号において、インストラクション実行ユニットが、第２の移動インストラクションに応じてデータの第２の移動を促進することができ、データの第２の移動が、（ｉ）上位レジスタの内容を拡張レジスタに、（ｉｉ）下位レジスタの内容を上位レジスタに、及び（ｉｉｉ）汎用レジスタの内容を下位レジスタに移動することを含むことを特徴とするデータ信号。
【請求項６３】
請求項６１記載のコンピュータ・データ信号において、拡張レジスタ、上位レジスタ、及び下位レジスタは各々、汎用レジスタを含むことを特徴とするデータ信号。
【請求項６４】
データを移動するための方法において、
拡張精度アキュムレータを提供するステップであって、該アキュムレータが、拡張レジスタ、上位レジスタ及び下位レジスタを含む、ステップと、
汎用レジスタを提供するステップと、
単独のインストラクションに応じて、データを（ｉ）上位レジスタから拡張レジスタに、（ｉｉ）下位レジスタから上位レジスタに、及び（ｉｉｉ）汎用レジスタから下位レジスタに、移動するステップと
を含むことを特徴とする方法。
【請求項６５】
請求項６４記載の方法において、拡張レジスタがＸビット幅で、上位レジスタがＹビット幅であり、かつＸがＹ未満であることを特徴とする方法。
【請求項６６】
請求項５８記載の方法において、拡張レジスタがＸビット幅で、上位レジスタがＹビット幅であり、かつＸがＹ未満であることを特徴とする方法。
【請求項６７】
請求項６６記載の方法において、拡張レジスタから上位レジスタに移動されるデータは、ゼロ拡張されることを特徴とする方法。
【請求項６８】
請求項６７記載の方法において、拡張レジスタは、データが移動された後に、クリアされることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マイクロプロセッサ・マルチプライヤに関し、特に、拡張精度アキュムレータを備えたマイクロコンピュータ・マルチプライヤに関する。
【背景技術】
【０００２】
産業傾向がより大きくより複雑なインストラクションセットに傾いていくにつれ、縮小インストラクション・セット・コンピュータ（ＲＩＳＣ）アーキテクチャが開発された。インストラクション・セット設計の単純化によって、ＲＩＳＣアーキテクチャは、パイプライン化（ｐｉｐｅｌｉｎｉｎｇ）及びキャッシング（ｃａｃｈｉｎｇ）等の技術の使用を容易にして、その結果、システム性能を増大させている。
ＲＩＳＣアーキテクチャは、通常、インストラクション形式に少しのバリエーションしか持たない固定長インストラクション（例えば１６ビット、３２ビット又は６４ビット）を持つ。インストラクション・セット・アーキテクチャ（ＩＳＡ）の各インストラクションは、常に同じ記憶位置にソースレジスタを持つ。例えば、３２ビットのＩＳＡは、常にビット１６−２０及び２１−２５に指定されたソースレジスタを持つ。こうすることで、指定されたレジスタが、いかなる複雑なインストラクションを解読することもなく、すべてのインストラクションに対して取り出されることが可能になる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
暗号化システム（「暗号システム」）は、トランザクションを保護し、通信を暗号化し、ユーザを認証し、かつ情報を守るためにますます使用されている。デジタル・エンクリプション・スタンダード（ＤＥＳ）のような多くの秘密鍵暗号方式は、計算が比較的単純で、かつデータのブロック上で一連のＸＯＲ、ローテーション及び入替えを実行するハードウェア・ソリューションを縮小することが可能である。しかしながら、公開鍵暗号システムは、秘密鍵システムより数学的に難解で、計算がより困難である。
【０００４】
異なる公開鍵暗号化スキームは、数学的に異なる基盤を持つだけでなく、１０２４ビットという非常に大きな範囲の値での整数計算を一般的に必要とする傾向がある。この拡張精度算術は、多くの場合、モジュール方式（すなわち、ある値範囲を法として演算が実行される）であり、そして、ある場合には、２の補数ではなく多項形態である。例えば、ＲＳＡ公開鍵暗号システムは、情報を暗号化し復号化するために拡張精度モジュールの指数化を使用し、楕円曲線暗号システムは拡張精度モジュールの多項式乗算を使用する。
秘密鍵暗号システムは、通信チャンネルを暗号化するために広範囲に使用されており、一方、公開鍵暗号システムは、ユーザ認証及び保護キーの交換に対して広範囲に使用されている。しかしながら、公開鍵暗号システムの使用が増加するにつれて、拡張精度モジュールの算術計算の性能を増大させることが望まれるようになった。
【課題を解決するための手段】
【０００５】
１つの一般的な側面において、乗算ユニットが、所定の（事前に決められた）数のビットを格納するための少なくとも１つの汎用レジスタを持つマイクロプロセッサ内での使用のために提供される。乗算ユニットは、汎用レジスタの各々よりも多くのビットを含む、マルチプライヤ及び拡張精度アキュムレータを含む。
実施例は、乗算ユニットへのオペランドを乗算して、拡張精度アキュムレータの内容に加算するようにした、乗算加算の演算を提供するマルチプライヤを使用することを含む。マルチプライヤは、算術マルチプライヤ及び多項式マルチプライヤを含む。
多項式マルチプライヤの実施例では、乗算加算の演算が、２つのオペランドを乗算し、排他的論理和演算を使用して、その結果を拡張精度アキュムレータの内容に加算する。いくつかの実施例では、マルチプライヤが、拡張精度アキュムレータにどの値を取り込むべきかを選定するための計算結果ロジックを含む。例えば、計算結果ロジックはマルチプレクサとして実現される。
【０００６】
いくつかの実施例では、拡張精度アキュムレータが、拡張レジスタ、上位レジスタ、及び下位レジスタを含む。例えば、拡張レジスタは８ビット値を格納し、他の２つのレジスタは３２ビット値を格納する。拡張精度アキュムレータの内容を操作するためのインストラクションが提供される。１つのインストラクションは、拡張精度アキュムレータからの値を汎用レジスタに移動し、また逆のインストラクションは、汎用レジスタからの値を拡張精度アキュムレータに移動される。インストラクションは、さらに拡張精度レジスタの内容をシフトする。
１以上の実施例の詳細を、添附図面及び以下において説明する。他の機能及び利点は、その説明及び図面、並びに特許請求の範囲から明白になるであろう。
【発明を実施するための最良の形態】
【０００７】
多くの公開鍵暗号システムは、データを暗号化し復号化するために、拡張精度モジュール算術を使用する。例えば、多くの楕円曲線（ＥＣ）暗号システムは、データを暗号化し復号化するために、広範囲に多項式の乗算及び加算を使用する。楕円曲線暗号システムの性能は、プログラム可能なＣＰＵマルチプライヤを、多項式演算専用に新しく定義されたインストラクションに応答するように修正することによって向上する。
【０００８】
ＧＦ（２１６３）（ＩＥＥＥ１３６３−２０００基準によって推奨されるような）上で定義された楕円曲線を使用する時、必要とされる主要な演算は、フィールドＧＦ（２１６３）上での乗算である。２１６３のエレメントの各々は、０又は１に等しい係数を備えた多くて１６３項の多項式として表現されることができる。この表現では、２つのエレメントが単純なビットＸＯＲ（排他的論理和）を使用して加算され、また、２つの多項式ａ（Ｘ）及びｂ（Ｘ）が、ａ（Ｘ）ｂ（Ｘ）  ｍｏｄ  Ｐ（Ｘ）を計算することによって乗算されるが、ただし、積ａ（Ｘ）ｂ（Ｘ）は３２６項の多項式であり、Ｐ（Ｘ）はＩＥＥＥ１３６３−２０００基準によって特定されるような既約多項式である。
多項式乗算は、（１）通常の加算がＸＯＲに置き換えられること、及び（２）通常の３２ビット乗算が３２ビットの桁上げフリー乗算に置き換えられることを除いては、整数上で、ａｂ  ｍｏｄ  ｐというモジュール乗算と同じ形式を持つ。従って、多項式モジュール乗算は、シフト及び加算の代わりに、シフト及びＸＯＲを使用して実行される。
【０００９】
暗号化システム及び他のシステムの性能を増大させるために、高速の多項式乗算及び様々な他の演算をサポートする乗算ユニットを提供することが望ましい。
拡張精度モジュールの算術及び多項式演算をサポートすることが、暗号システムの性能を増大させる。ＲＳＡ暗号署名認証を実行するというような、いくつかの暗号化システムは、連続して拡張精度モジュール乗算を実行し、その結果の合計を累計する。これらのシステムの性能は、２つのオペランドを乗算し、かつアキュムレータにその結果を加算するインストラクションに対するサポートを乗算ユニット内で提供することによって、増大する。連続して乗算／加算が実行される時、アキュムレータがオーバーフローする可能性がある。暗号システム及び他のシステム内の性能を増大させるために、拡張精度アキュムレータを提供することが望ましい。
【００１０】
図１を参照して、多項式乗算を実現するために使用される典型的なマイクロプロセッサのアーキテクチャは、インストラクションがクロック・サイクル毎に発行され、かつ例えば４クロック・サイクルのような固定時間の中で実行される５段パイプラインを含む。各インストラクションの実行は、インストラクション・フェッチ（ＩＦ）ステージ１００１、レジスタ読み取り（ＲＤ）ステージ１００２、算術／論理ユニット（ＡＬＵ）ステージ１００３、メモリ（ＭＥＭ）ステージ１００４、及びライトバック（書き戻し）（ＷＢ）ステージ１００５の５ステージに分割される。ＩＦステージ１００１では、指定されたインストラクションが、インストラクション・キャッシュから取り出される。取り出されたインストラクションの一部が、インストラクションを実行するのに使用されるソースレジスタを指定するために使用される。読み取りレジスタ（ＲＤ）ステージ１００２では、システムが、指定されたソース・レジスタの内容を取り出す。これらの取り出された値は、ＡＬＵステージ１００３内の算術演算あるいは論理演算を実行するために使用される。ＭＥＭステージ１００４では、実行インストラクションが、データ・キャッシュ内のメモリを読み出し／書き込む。最後に、ＷＢステージ１００５では、インストラクションの実行によって得られた値が、レジスタにライトバックされる。
【００１１】
浮動小数点計算及び整数の乗算／除算のようないくつかの演算は、必ずしも単一クロック・サイクルで実行できるとは限らないので、いくつかのインストラクションはただインストラクションの実行を始めるためだけのものである。十分なクロック・サイクルが経過した後、別のインストラクションが結果を取り出すために使用される。例えば、整数乗算インストラクションが５つのクロック・サイクルを取る場合、１つのインストラクションが乗算計算を開始し、乗算が完成した後、別のインストラクションがその乗算の結果をレジスタに取り込む。結果が要求される時までに乗算が完了していない場合、結果が利用可能となるまで、パイプラインは時間を引き延ばす。
【００１２】
図２は、典型的なＲＩＳＣアーキテクチャを例示している。プロセッサ・コア２０００（又は「マイクロプロセッサ・コア」とも呼ばれる）は、実行ユニット２０１０、乗算／除算ユニット（ＭＤＵ）２０２０、システム制御コプロセッサ（ＣＰＯ）２０３０、メモリ管理ユニット２０４０、キャッシュ・コントローラ２０５０、及びバス・インターフェース・ユニット（ＢＩＵ）２０６０を含む。
【００１３】
実行ユニット２０１０は、プロセッサ・コア２０００内のインストラクションを実行するための主要なメカニズムである。実行ユニット２０１０は、レジスタ・ファイル２０１１及び算術論理ユニット（ＡＬＵ）２０１２を含む。１つの実施例では、レジスタ・ファイル２０１１が、例えば、スカラ整数演算及びアドレス計算に使用することができる３２個の３２ビット汎用レジスタを含む。２つの読み取りポート及び１つの書き込みポートを含むレジスタ・ファイル２０１１は、パイプライン内の演算待ち時間を最小限にするために完全にバイパスされる。ＡＬＵ２０１２は、加算、減算及びシフトのような論理と算術の両方の演算をサポートする。
【００１４】
ＭＤＵ２０２０は、以下に説明されるＤＩＶ、ＤＩＶＵ、ＭＡＤＤ、ＭＡＤＤＵ、ＭＦＨＩ、ＭＦＬＯ、ＭＳＵＢ、ＭＳＵＢＵ、ＭＴＨＩ、ＭＴＬＯ、ＭＵＬ、ＭＵＬＴ、ＭＵＬＴＵ、ＭＦＬＨＸＵ、ＭＴＬＨＸ、ＭＡＤＤＰ、ＭＵＬＴＰ、及びＰＰＥＲＭのようなインストラクションの幾つか又は全てを含む様々な演算を実行するために使用される。
【００１５】
１つの実施例では、ＬＯレジスタ２０２３及びＨＩレジスタ２０２２は、各々３２ビット幅で、ＭＤＵ２０２０の専用出力レジスタとして機能する。１つの実施例では、ＡＣＸレジスタ２０２１が、ＨＩ／ＬＯレジスタ対によって提供されるもの以上の、８ビットのさらなる整数精度を提供する。望ましい最小サイズは８ビットであるが、適切なビット数は実施例に依存する。３２ビットのデータ経路を備えたプロセッサにとっては、ＡＣＸレジスタの望ましい最大サイズは３２ビットである。一方、６４ビットのデータ経路を備えたプロセッサにとっては、ＡＣＸレジスタの望ましい最大サイズは６４ビットである。従って、３２ビット幅のＨＩ及びＬＯレジスタを備えたプロセッサでは、レジスタＡＣＸ／ＨＩ／ＬＯの組合せは、６４ビット以上になる連結された値を保持することができる。
【００１６】
図２及び３に示される実施例では、ＭＤＵ２０２０は除算ユニットを含む。しかしながら、他の実施例は、乗算ユニット、除算ユニット、又は、乗算と除算の両方のユニットのいずれかにおいて、拡張アキュムレータを実現する別個の乗算及び除算ユニットを提供する。
【００１７】
インストラクションＭＵＬ、ＭＵＬＴ及びＭＵＬＴＵは、２つの３２ビットの数を互いに乗算するために使用される。その結果は、ＭＵＬに対しては指定されたレジスタに、ＭＵＬＴ及びＭＵＬＴＵに対してはＨＩ／ＬＯレジスタに格納される。例えば、インストラクション「ＭＵＬ＄７、＄６、＄５」は、レジスタ＄６及び＄５の内容を互いに乗算し、その結果をレジスタ＄７に格納する。インストラクション「ＭＵＬＴ＄６、＄５」は、レジスタ＄６及び＄５の内容を互いに乗算し、その結果をＨＩ／ＬＯレジスタに格納する。ＭＵＬＴＵインストラクションは、ＭＵＬＴと同じ演算を実行するが、ＭＵＬＴＵは正負符号なしのオペランドに適応され、ＭＵＬＴは正負符号付きオペランドに適応される。さらに、ＭＵＬＴＵインストラクションは、ＡＣＸレジスタをすべてゼロにクリアする。
【００１８】
インストラクションＤＩＶ及びＤＩＶＵは、除算演算を実行し、その結果をＡＣＸ／ＨＩ／ＬＯレジスタに格納する。例えば、「ＤＩＶ＄６、＄５」は、レジスタ＄６の内容をレジスタ＄５の内容で除算し、その結果をＡＣＸ／ＨＩ／ＬＯレジスタに格納する。ＤＩＶＵインストラクションは、その同じ演算を、正負符号なしのオペランド上で実行する。
【００１９】
インストラクションＭＳＵＢ、ＭＳＵＢＵ、ＭＡＤＤ、及びＭＡＤＤＵは、２つのレジスタの内容を乗算し、次に、ＡＣＸ／ＨＩ／ＬＯレジスタの内容を加算するか、減算するために使用される。例えば、「ＭＳＵＢ＄６、＄５」は、レジスタ＄６及び＄５の内容を互いに乗算し、その結果からＡＣＸ／ＨＩ／ＬＯレジスタの内容を減算し、次に、その値をＡＣＸ／ＨＩ／ＬＯレジスタに格納する。ＭＡＤＤインストラクションは、同様に２つのレジスタの内容を乗算し、その結果をＡＣＸ／ＨＩ／ＬＯレジスタに加算し、その結果をＡＣＸ／ＨＩ／ＬＯレジスタに格納する。ＭＳＵＢＵ及びＭＡＤＤＵは、正負符号なしのオペランド上で、同じ演算を実行する。いくつかの実施例では、ＡＣＸレジスタがいくつかの演算で使用されず、そのような演算に付随するＡＣＸレジスタの内容は定義されない。
【００２０】
ＭＦＨＩ、ＭＦＬＯ、ＭＴＨＩ、ＭＴＬＯ、ＭＦＬＨＸＵ、及びＭＴＬＨＸインストラクションは、ＡＣＸ／ＨＩ／ＬＯレジスタと汎用レジスタとの間で、データを移動するために使用される。第１のインストラクションＭＦＨＩは、ＨＩレジスタの内容を汎用レジスタに取り込む。例えば、「ＭＦＨＩ＄５」は、ＨＩレジスタの内容をレジスタ＄５に取り込む。同様に、ＭＦＬＯは、ＬＯレジスタの内容を汎用レジスタに取り込む。反対に、インストラクションＭＴＨＩ及びＭＴＬＯは、汎用レジスタの内容をＨＩ又はＬＯのレジスタに取り込むために使用される。例えば、「ＭＴＨＩ＄５」は、レジスタ＄５の内容をＨＩレジスタに取り込む。
【００２１】
より一般的に、ＭＦＬＨＸＵ（“Ｍｏｖｅ  Ｆｒｏｍ  Ｅｘｔｅｎｄｅｄ  Ｃａｒｒｙ、  Ｈｉ  ａｎｄ  Ｌｏ（Ｕｎｓｉｇｎｅｄ）”（「拡張桁上げ、Ｈｉ及びＬｏからの移動（正負符号なし）」））に対するインストラクション・フォーマットは、図１０Ａで示される。実行されると、ＬＯレジスタ２０２３内の値は、図１０Ａに示されるように、インストラクションによって指定された汎用レジスタ「ｒｄ」に書き込まれる。その後、ＨＩレジスタ２０２２内の値は、ＬＯレジスタ２０２３に書き込まれ、ＡＣＸレジスタ２０２１内のビットはゼロ拡張されて、ＨＩレジスタ２０２２にコピーされ、ＡＣＸレジスタのビットがクリアされる。ＡＣＸレジスタのビットの数は実施例に依存し、例えば、０〜６４ビットの範囲である。特定の実施例において、ＡＣＸレジスタのビットが実行されない場合、ＡＣＸレジスタの値はゼロであると見なされる。
【００２２】
同様に、ＭＴＬＨＸ（“Ｍｏｖｅ  ｔｏ  Ｌｏ，Ｈｉ  ａｎｄ  Ｅｘｔｅｎｄｅｄ  Ｃａｒｒｙ”（「Ｌｏ、Ｈｉ及び拡張桁上げへの移動」））が図１０Ｂに示される。実行されると、ＨＩレジスタ２０２２内の値のビットの適切な数（例えば８）が、ＡＣＸレジスタ２０２１に書き込まれる。その後、ＬＯレジスタ２０２３内の値がＨＩレジスタに書き込まれ、汎用レジスタ「ｒｓ」（図１０Ｂに示されるように、インストラクションによって指定される）内の値がＬＯレジスタに書き込まれる。これはＭＦＬＨＸＵインストラクションの演算の逆である。この場合も、ＡＣＸレジスタ・ビットの数は実施例に依存し、例えば０〜６４ビットの範囲である。ＨＩレジスタ２０２２がＡＣＸレジスタ２０２１内に実行された数より大きいビットを保持している場合、その情報は例外なく廃棄される。いかなるＡＣＸレジスタのビットも実行されない場合、ＨＩレジスタからＡＣＸレジスタへの移動は「ノーオペレーション（演算無し）」と見なされる。
【００２３】
１つの実施例では、ＡＣＸレジスタの内容は、ダイレクトにアクセス可能ではない。説明する目的のために、本実施例では、ＡＣＸレジスタは８ビット幅で、ＨＩとＬＯのレジスタは各々３２ビット幅である。間接的にＡＣＸレジスタにアクセスするために、ＡＣＸ／ＨＩ／ＬＯレジスタに格納された値は、左又は右へシフトされる。例えば、「ＭＦＬＨＸＵ＄５」は、ＬＯレジスタの内容をレジスタ＄５に取り込んで、ＡＣＸ、ＨＩ及びＬＯレジスタの内容を１レジスタ位置だけ右へシフトさせる。従って、その演算が実行された後は、ＡＣＸレジスタはゼロで、ＨＩレジスタはＡＣＸレジスタの前の内容を保持し、ＬＯレジスタはＨＩレジスタの前の内容を保持し、＄５レジスタはＬＯレジスタの前の内容を保持する。８ビットのＡＣＸレジスタの内容が３２ビットのレジスタに取り込まれるので、８ビットの値は、ＨＩレジスタを取り込む前に、３２ビットにゼロ拡張される。
【００２４】
ＭＴＬＨＸは逆の演算を実行する。例えば、「ＭＴＬＨＸ＄５」は、ＨＩレジスタの前の内容をＡＣＸレジスタに取り込み、ＬＯレジスタの前の内容をＨＩレジスタに取り込み、＄５レジスタの内容をＬＯレジスタに取り込む。
【００２５】
ＰＰＥＲＭ演算は、レジスタ中で指定されるような入替えを実行し、その結果をＡＣＸ／ＨＩ／ＬＯレジスタに格納する。例えば、「ＰＰＥＲＭ＄５、＄６」は、ＡＣＸ／ＨＩ／ＬＯレジスタを６ビット左にシフトさせる。それから、レジスタ＄６によって指定されるように、下位６ビットがレジスタ＄５から選定される。ＡＣＸ／ＨＩ／ＬＯレジスタの下位ビットを満たすために、レジスタ＄５のどのビットが使用されるかを選定するために、レジスタ＄６の３２ビットの内容が用いられる。レジスタ＄５には３２ビットがあるので、３２ビットのうちの特定の１つを指定するためには５ビットが必要とされる。例えば、「０１１０１」は、数１３に対する２進数である。従って、これらの５つのビットは、ビット１３を指定する。同様に、「０００００」は０に対する２進数で、「１１１１１」は３１に対する２進数である。従って、３２ビットはすべて、５ビットの指定子（スペシファイア）を用いて指定されることができる。
【００２６】
レジスタ＄６は、以下のようにＡＣＸ／ＨＩ／ＬＯの下位ビットを満たすために使用される＄５のビットを指定する。つまり、ビット０−４はビット０のソースを指定するために使用され、ビット５−９はビット１を指定するために使用され、ビット１０−１４はビット２を指定するために使用され、ビット１５−１９はビット３を指定するために使用され、ビット２０−２４はビット４を指定するために使用され、そしてビット２５−２９はビット５を指定するために使用される。残りのビット３０−３１は未使用である。従って、説明されたようなし指定子を使用して、＄５レジスタからの指定されたビットでＬＯレジスタの最下位の６ビットを満たすためのインストラクションが実行される。
【００２７】
最後に、ＭＵＬＴＰは２進の多項式乗算を実行するために使用され、ＭＡＤＤＰは２進の多項式乗算を実行してその結果をＡＣＸ／ＨＩ／ＬＯレジスタに加算するために使用される。これらの演算はＭＵＬＴ及びＭＡＤＤに類似しているが、２進の多項式オペランド上で作動する。
【００２８】
ＭＵＬＴＰ及びＭＡＤＤＰの多項式のオペランドは、３２ビットのレジスタ内にコード化され、このとき、各ビットは多項式の係数を表す。例えば、多項式「ｘ４＋ｘ＋１」は、ｘ３及びｘ２の係数が「０」で、残りの係数が「１」であるので、「１００１１」としてコード化される。ＭＵＬＴＰインストラクションは、２つのオペランド上で２進の多項式乗算を実行する。例えば、
（ｘ４＋ｘ＋１）（ｘ＋１）＝ｘ５＋ｘ４＋ｘ２＋２ｘ＋１
多項式をモジュロ２で減じると、ｘ５＋Ｘ４＋ｘ２＋１を生じる。多項式が上記の２進の表現でコード化される場合、同じ乗算が、（１００１１）（１１）＝１１０１０１として表わされる。
【００２９】
ＭＡＤＤＰインストラクションは、ＭＵＬＴＰのように乗算を実行して、その結果をＡＣＸ／ＨＩ／ＬＯレジスタに加算する。多項式加算はビットＸＯＲを使用して実行される。例えば、２進の多項式加算（ｘ４＋ｘ＋１）＋（Ｘ＋１）は、ｘ４＋２ｘ＋２となる。係数をモジュロ２で減じると、「１００００」として表わされるｘ４となる。
【００３０】
図２及び３を参照すると、ＭＤＵ２０２０は、２つの３２ビットのオペランドＲＳ及びＲＴを受け取る。これらのオペランドを使用して、ＭＤＵ２０２０は要求された演算を実行し、レジスタＡＣＸ２０２１、ＨＩ２０２２、及びＬＯ２０２３に結果を格納する。これらの演算を実行するために使用される主要なデータ経路は、図３で示される。ＲＳｈｏｌｄ（ＲＳホールド）レジスタ３０１０及びＲＴｈｏｌｄ（ＲＴホールド）レジスタ３０１２は、ＲＳ及びＲＴのオペランドを保持するために使用される。マルチプレクサ３０２０、３０２２及び３０２４は、ＲＳ及びＲＴオペランドをダイレクトに使用するべきか、ＲＳｈｏｌｄレジスタ３０１０及びＲＴｈｏｌｄレジスタ３０１２に格納された値を使用するべきであるかどうかを選定するために使用される。なお、マルチプレクサ３０２２は、ＲＴの下位及び上位ビット、又はＲＴｈｏｌｄレジスタ３０１２に格納された値、の間の選定を行うために使用される。
【００３１】
ＲＴｈｏｌｄレジスタ３０１２は、マルチプレクサ３０２２に接続される。マルチプレクサ３０２２は、ＲＴｈｏｌｄ３０１２の上位ビット、ＲＴｈｏｌｄ３０１２の下位ビット、ＲＴオペランドの上位ビット、又はＲＴオペランドの下位ビットを選定することにより１６ビットの結果を生じる。マルチプレクサ３０２２からの出力は、ブース・レコーダ（ｂｏｏｔｈ  ｒｅｃｏｄｅｒ）３０４０によって処理され、レジスタＲＴＢ３０４２に格納される。ブース・レコーディング（ｂｏｏｔｈ  ｒｅｃｏｄｉｎｇ）は、マルチプライヤアレイが、正負符号付きオペランドと正負符号なしオペランドを同様に処理することを可能にする技術である。レジスタＲＩＢ３０４２の出力は、アレイ・ユニット３０３０への入力ＳＥＬ３０３４になる。
【００３２】
アレイ・ユニット３０３０は、図４に関連して以下に説明されるような算術乗算及び２進の多項式乗算を実行するために使用される。アレイ・ユニット３０３０は、入力として、ＡＣＣ１  ３０３１、ＡＣＣ２  ３０３２、Ｍ３０３３、ＳＥＬ３０３４、及びＲＴｈｏｌｄ３０１２を得る。入力ＡＣＣ１  ３０３１及びＡＣＣ２  ３０３２は、乗算を実行し、その結果の値を、累計された結果に加算又は減算を実行する演算用に使用される累計された結果である。入力ＳＥＬ３０３４（レジスタＲＴＢ３０４２によって決定される）、及びＭ３０３３（レジスタＲＳｈｏｌｄ  ３０１０によって決定される）は、算術演算のためのオペランドを形成する。入力ＲＴｈｏｌｄ３０１２（あるいはＲＴｈｏｌｄ３０１２の上位又は下位ビット）及びＭ３０３３（ＲＳｈｏｌｄ３０１０によって決定される）は、多項式演算及び入替え用のオペランドを形成する。これらの入力の組合せは、詳細に下に説明されるような様々な計算を実行するために使用される。
【００３３】
アレイ・ユニット３０３０はまた、２つの出力であるＲｅｓｕｌｔＣ  ３０３５及びＲｅｓｕｌｔＳ３０３６を含む。算術演算を実行する際に、桁上げ保留（キャリー・セーブ）加算器（ＣＳＡ）が乗算アレイを構築するために使用される。桁上げ保留加算器は、２つの出力を生成するために合計と桁上を別々に計算する。従って、ＲｅｓｕｌｔＣ  ３０３５及びＲｅｓｕｌｔＳ  ３０３６は、それぞれ、ＣＳＡマルチプライヤアレイの桁上出力及び合計出力を表す。１つの実施例では、ＡＣＣ１  ３０３１、ＡＣＣ２  ３０３２、ＲｅｓｕｌｔＣ  ３０３５、及びＲｅｓｕｌｔＳ  ３０３６が、各々７２ビット長で、残りの入力は多くても３２ビット長である。入力ＡＣＣ１  ３０３１及びＡＣＣ２  ３０３２は、マルチプレクサ３０３７及び３０３８を用いて選定される。
【００３４】
マルチプレクサ３０５０及び３０５２は、レジスタＣＰＡＡ  ３０５４及びＣＰＡＢ３０５６への入力としての値を選定するために使用される。例えば、マルチプレクサ３０５０は、ＲｅｓｕｌｔＣ  ３０３５、ＣＰＡ  ３０５８の出力、又はマルチプレクサ３０２０（つまりオペランドＲＳ若しくはＲＳｈｏｌｄ３０１０）の出力、を選定するために使用される。同様に、マルチプレクサ３０５２は、ＲｅｓｕｌｔＳ３０３６、値ゼロ、及びマルチプレクサ３０２４（つまり、オペランドＲＴ、若しくはＣＰＡＡ  ３０５４及びＣＰＡＢ  ３０５６の出力）の出力の間を選定するために使用される。これらのレジスタは、キャリー・プロパゲイト（桁上げ伝搬）加算器（ＣＰＡ）３０５８への入力を格納する。ＣＰＡ３０５８は、乗算演算（乗算）を完了し、また以下に説明されるような反復除算演算（除算）を実行するために使用される。
【００３５】
レジスタＲＤＭ３０６０は、ＣＰＡ３０５８の結果出力を格納する。最後に、マルチプレクサ３０７０及び３０７２は、どの値が、レジスタＡＣＸ、ＨＩ及びＬＯに取り込まれるべき結果を形成するかを選定する。マルチプレクサ３０７０は、ＡＣＸ／ＨＩ／ＬＯレジスタか、ＲＤＭ３０６０か、又は、ＣＰＡ３０５８の結果かを選定するために使用される。マルチプレクサ３０７２は、マルチプレクサ３０７０によって選定された結果の様々な入替えを、代わりに取り込むために使用される。マルチプレクサ３０７２は、（連結されると７２ビット値を形成する）次のような値の選定を可能にすることによって、ＡＣＸ／ＨＩ／ＬＯレジスタの様々なロテーション及び取り込みを実行するために使用される。次のような値とは、（１）マルチプレクサ３０７０の７２ビット出力であるａｈｌ、（２）マルチプレクサ３０７０の上位８ビット、ＲＳｈｏｌｄ３０１０の内容、及びマルチプレクサ３０７０の下位３２ビットであるａｒｌ、（３）マルチプレクサ３０７０の上位４０ビット及びＲＳｈｏｌｄ３０１０の内容であるａｈｒ、（４）マルチプレクサ３０７０の下位４０ビット及びＲＳｈｏｌｄ３０１０の内容であるｈｌｒ、（５）マルチプレクサ３０７０（３２個の先行ゼロを備えた）の上位４０ビットである０ａｈ、である。
【００３６】
ＨＩ／ＬＯレジスタは、乗算の結果を格納し、かつアキュムレータ演算のサポートを提供するために使用される。１つの実施例では、レジスタＡＣＸを拡張アキュムレータとして追加することにより、ＨＩ／ＬＯレジスタの精度が増大する。従って、ＡＣＸ／ＨＩ／ＬＯレジスタは７２ビットの値を格納することができる。図３で示される対応するデータ経路、及びアレイ３０３０のアキュムレータ能力もまた、７２ビットの値をサポートするように増大させられる。いくつかの演算の結果、結果レジスタＡＣＸ、ＨＩ及びＬＯに格納された値が上書きされることになる。この理由のために、別個の結果レジスタ３０８０が、アキュムレータＡＣＸ無しで、上位と下位結果を格納するように提供される。
【００３７】
拡張精度アキュムレータＡＣＸ／ＨＩ／ＬＯは汎用レジスタより高い精度を持つので、汎用レジスタに７２ビットすべてを取り込むことはできない。従って、ＡＣＸ／ＨＩ／ＬＯレジスタの内容を取り込むこと及び操作することをサポートするインストラクション（例えばＭＦＬＨＸＵ及びＭＴＬＨＸ）を提供することが望ましい。
【００３８】
以下に説明されるデータ経路は、６つの主要部分、すなわち（１）入力のレジスタリング及び選定、（２）ブース・レコーディング、（３）マルチプライヤアレイ及び入替えロジック、（４）桁上げ伝搬加算器、（５）結果のレジスタリング及び選定、及び（６）結果を示すための別個の３２ビット出力レジスタ、を含む。
【００３９】
入力のレジスタリング及び選定は、ＲＳ及びＲＴオペランドを保持するためにＲＳｈｏｌｄ及びＲＴｈｏｌｄレジスタを用いて実行される。マルチプレクサは、これらのオペランドをダイレクトに使用するべきか、登録されたバージョンを使用するべきであるかどうかを選定する。ブース・レコーディングは、マルチプライヤアレイ及び入替えロジックに入力を提供するために、一度にＲＴオペランドの半分で実行される。
【００４０】
ブース・レコーディングは、マルチプライヤ・アレイが正負符号付き及び正負符号なしのオペランドを、同じものとして処理することを可能にする技術である。この技術は、次の最も高い２のべき乗からの減算としてオペランドを「レコード（ｒｅｃｏｄｅ）」する。例えば、７は、以下のようにブース・レコードされる。
８−１＝１０００２−０００１２＝１００１
ただし、１は−１を表すものとする。Ｈｅｎｎｅｓｓｙ及びＰａｔｔｅｒｓｏｎは、その全体が参考文献としてここに組み込まれるが、Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ出版社（１９９６年）の「ＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅ：  Ａ  Ｑｕａｎｔｉｔａｔｉｖｅ  Ａｐｐｒｏａｃｈ（コンピュータ・アーキテクチャの定量的アプローチ）」の付録Ａの中で、ブース・レコーディングについて説明している。
【００４１】
アレイ・ユニット３０３０のうちの１つのアレイは、算術乗算を実行し、またアレイ・ユニット３０３０の１つのアレイは、２進の多項式乗算を実行する。１つの実施例では、両方のアレイが３２ビット掛ける１６ビット（３２ｘ１６）で、ＲＴオペランドのサイズに依存して、一回又は二回、使用される（つまり、ＲＴが１６ビット長である場合は、適切なアレイが一回使用され、３２ビット長である場合は二回使用される）。ＣＰＡは乗算を完了するため、そして反復除算を実行するために使用される。他の実施例は、除算の実行用に、より高速のメカニズムを含む。
【００４２】
算術乗算アレイは、ここに組み込まれたＭｏｒｇａｎ  Ｋａｕｆｍａｎｎ出版社（１９９６年）の「ＣｏｍｐｕｔｅｒＡｒｃｈｉｔｅｃｔｕｒｅ：  Ａ  Ｑｕａｎｔｉｔａｔｉｖｅ  Ａｐｐｒｏａｃｈ（コンピュータ・アーキテクチャの定量的アプローチ）」の中で、Ｈｅｎｎｅｓｓｙ及びＰａｔｔｅｒｓｏｎによって記載された技術のうちの任意のものを用いて実現される。例えば、Ｈｅｎｎｅｓｓｙ及びＰａｔｔｅｒｓｏｎによる付録Ａは、演算マルチプライヤを加速するためのいくつかの方法を記載している。記載された技術のうちのいかなるものも、以下に説明される多項式乗算の拡張のための基本原理として使用可能である。
【００４３】
図４を参照すると、アレイ・ユニット３０３０は、並列の２つのマルチプライヤ（Ｍａｒｒａｙ４１００及びＭＰａｒｒａｙ４２００）、及び入替えロジック４３００を含む。第１のアレイであるＭａｒｒａｙ４１００は、図５を参照して下に説明されるような算術乗算を実行する。Ｍａｒｒａｙ４１００は、上に説明されたような入力、つまりＡＣＣ１  ３０３１、ＡＣＣ２  ３０３２、Ｍ３０３３、及びＳＥＬ３０３４を使用する。その出力は、ＲｅｓｕｌｔＣ３０３５及びＲｅｓｕｌｔＳ３０３６を含む。第２のアレイであるＭＰａｒｒａｙ４２００は、図６を参照して以下に説明されるような２進の多項式乗算を実行する。ＭＰａｒｒａｙ４２００は、上に説明されたような入力、つまりＲＴｈｏｌｄ３０１２の下位ビット又はＲＳｈｏｌｄ３０１２の上位ビット、ＲＳｈｏｌｄ３０１０、及びＡＣＣ１  ３０３１を使用する。ＭＰａｒｒａｙ４２００の出力はＲｅｓｕｌｔＣ３０３６である。最後に、入替えロジック４３００は、ＲＴｈｏｌｄ３０１２に格納された値に基づいて、ＲＳｈｏｌｄ３０１０の下位ビット上で、様々な入替えを実行するために使用される。
【００４４】
図５を参照して、Ｍａｒｒａｙ４１００は、２つの７２ビット幅のオペランドＡＣＣ１及びＡＣＣ２の加算をサポートするよう修正された、３２ビット掛ける１６ビットのウォーレス・ツリー（Ｗａｌｌａｃｅ  ｔｒｅｅ）マルチプライヤアレイである。ＡＣＣ１及びＡＣＣ２のオペランドは、７２ビット値の桁上げ保留表示を保持する。乗算を遂行するためにすでに（つまり桁上げ選択加算器（ＣＳＡ）による）加算が実行されているので、乗算の中間結果に加算されるようにするための追加の加算器が、すべてのＡＣＣ１及びＡＣＣ２に含まれる。Ｍａｒｒａｙ４１００は、桁上げ保留表示で７２ビット幅の結果を生成する。３２ｘ１６ビットが１つのサイクル当たり処理されるので、３２ｘ３２ビットの乗算には、アレイを通る２つの経路が必要である。
【００４５】
Ｍａｒｒａｙ４１００は、桁上げ保留加算器のアレイから構築されたウォーレス・ツリーとして実現される。これらのアレイの幅は変化する。この設計は、データ経路のスタイルを使用するのではなく、自動化された桁及び経路を使用して実現される。前のアレイ・パスからの累積加算値がアレイに遅れて入力されるので、累積加算値はレジスタからダイレクトに来る必要はない。ブース・レコーディングは、乗算をより効率的に処理するために、重なり合う三重項の方法を使用することにより実行される。ブース・レコーディングの出力は、−２、−１、０、１、又は２を乗じたオペランドＭを、４の各累乗に対して加算すべきかどうかを伝える。最上レベルのＣＳＡ入力上のマルチプレクサは、対応するＭの倍数を選定するために使用される。
【００４６】
Ｍａｒｒａｙ４１００は、ブース・レコーディングからの８つの積に加えて、特別な１つの部分積を累計する。後者は、マルチプレクサからの「０」及び「ｌｘ」の選択を用いて、３２ビットの正負符号なしの計算に対して使用される。ウォーレス・ツリー内では、２の補数結果を正確に累計するために、オペランドが正負符号拡張される。
【００４７】
図６を参照すると、対応する正負符号なしの算術演算と同様に、２進の多項式に基づいた乗算演算が処理される。１つの実施例では、ＭＰａｒｒａｙ４２００は、例えばＡＣＣ１というオペランド上で、排他的論理和（ＸＯＲ）を用いて加算も実行する３２ｘ１６ビット・アレイである。Ｍａｒｒａｙ４１００と同様に、３２ｘ１６ビットが１つのサイクル当たり処理されるので、３２ｘ３２ビットの乗算には、アレイを通る２つの経路が必要である。第１のサイクルでは、ＡＣＣ１はゼロ（ＭＵＬＴＰ演算に対して）又は前の結果（ＭＡＤＤＰ演算に対して）である。第２のサイクルでは、ＡＣＣ１は、第１のサイクルからの出力の上位ビットである。
【００４８】
ＭＰａｒｒａｙ４２００は、２つのオペランド（例えば、ＯｐＡ及びＯｐＢ）を乗算するが、このとき、ＯｐＡとＯｐＢの１ビットとの論理積（ＡＮＤ）を得ることにより形成される各行毎に１つのアレイを用いる。例えば、第１行は、ＯｐＡとＯｐＢのビット０との論理積である。行２は、ＯｐＡとＯｐＢのビット１との論理積である。各々の連続する行の結果は、左側に１ビットシフトされる。最後の結果は、各列の排他的論理和（ＸＯＲ）を得ることにより形成される。２進の多項式演算で加算を実行するためにビットＸＯＲが使用されるので、アキュムレータ行が、ＭＡＤＤＰのようなインストラクションをサポートするアレイＭＰａｒｒａｙ４２００に加えられる。
【００４９】
図４で示される３つのマルチプレクサは、ＲｅｓｕｌｔＳ３０３６を形成するために、ゼロ、又はＭａｒｒａｙ４１００の合計出力のいずれかを選定するために使用され、そしてまた、ＲｅｓｕｌｔＣ３０３５を形成するために、Ｍａｒｒａｙ４１００、ＭＰａｒｒａｙ４２００、又は入替えロジック４３００の出力のいずれかを選定するために使用される。
【００５０】
再び図１を参照する。ＭＤＵ２０２０は、パイプラインの実行ステージ１００３の第１のサイクルで計算をスタートさせる。インストラクションがパイプライン内のメモリ・ステージ１００４を通過する前に計算が完了する場合、その結果はその点で保持される。インストラクションがパイプライン内のメモリ・ステージ１００４を通過する時に演算が完了すれば、そのインストラクションがコミットされ、その結果はＡＣＸ／ＨＩ／ＬＯレジスタにダイレクトに書き込まれる。
ＭＤＵ２０２０は、環境のパイプラインから切り離されている、つまり、環境によって失速（ｓｔａｌｌ）することがない。それは、ＭＤＵ２０２０がパイプラインの失速中でもその演算を継続するということである。このようにして、多重サイクルＭＤＵ演算は、システムの失速及び（又は）他の非ＭＤＵインストラクションによって、部分的にマスクされることができる。
【００５１】
図７Ａは、３２ｘ１６ビット乗算用のＭＤＵ２０２０を通るパイプラインの流れを示す。ＲＳ及びＲＴは遅れて到着するので、第１のサイクルがブース・レコーディングに対して使用される。第２のサイクルは、アレイが実行されるところであり、第３サイクルは、ＣＰＡ３０５８が演算を完了するところである。結果はＭＦｘｘインストラクションによる読み取りに対して常にアクセス可能なので、３２ｘ１６乗算は失速することなく実行される。汎用レジスタ（ＧＰＲ）にその結果をダイレクトに戻す３２ｘ１６ＭＵＬは、１つのサイクルの間に失速する可能性がある。
【００５２】
図７Ｂを参照する。３２ｘ３２ビット乗算に対しては、アレイが２度使用され、それは３２ｘ１６ビット乗算にさらに１つのクロック・サイクルを追加する。第１のアレイ・パスがオペランドＲＴの第１の部分に対して完了しつつある時、ブース・レコーディングがオペランドの第２の部分上で実行される。従って、ブース・レコードされたＲＴの部分は、第１のパスが完了するとすぐに、アレイを通して第２のパスを始めることができる。その後、乗算結果はＣＰＡ３０５８を用いて計算される。
【００５３】
図７Ｃを参照する。単純な非回復型（ｎｏｎ−ｒｅｓｔｏｒｉｎｇ）除算アルゴリズムが正のオペランドに対して使用される。もし必要ならば、第１のサイクルはＲＳを負にするために使用される。タイミングの理由により、ＲＳが正であっても、このサイクルは実行される。次いで、３２、２５、１８、又は１０のサイクルの繰返しの加算／減算の演算が実行される。その実際の数は、正のＲＳオペランド上の先行ゼロの総数に基づく。剰余が負だったならば、最終の剰余の調整が必要となる。タイミングの理由のために、剰余調整が必要でなくても、このサイクルは実行される。最後に、商及び（又は）剰余の上で必要ならば、正負符号の調整が実行される。両方のオペランドが正の場合、このサイクルはスキップされる。
【００５４】
１つの実施例では、ターゲットのアプリケーションが高速の除算を要求する。除算の性能を増大させるために、多くの技術が使用される。例えばＳｗｅｅｎｅｙ、Ｒｏｂｅｒｔｓｏｎ、及びＴｏｃｈｅｒ（ＳＲＴ）アルゴリズム、又はそのいくつかのバリエーションが使用される。
【００５５】
図８を参照する。乗算演算は有限状態マシーンを用いて実現される。乗算はＩＤＬＥ状態８０１０で始まる。始動信号がアサートされるまで、マルチプライヤは停止状態にとどまる。その後、マルチプライヤは、オペランドＲＴが３２ビットか、又は１６ビットの値を保持しているかどうかに応じて、ＡＲＲ１状態８０２０又はＡＲＲ２Ａ状態８０３０のいずれかに移動する。１６ビットの値がＲＴに格納される場合、システムは、第１のアレイ・パスが実行される状態ＡＲＲ２Ａ  ８０３０に移動する。その後、マルチプライヤは、第２のアレイ・パスが実行される状態ＡＲＲ２Ｂ  ８０４０に移動する。１６ビットの値がオペランドＲＴに格納される場合、乗算は、状態ＡＲＲ１  ８０２０で、アレイ・ユニットを通る。
【００５６】
この実施例では、マルチプライヤがパイプライン化される。１つの乗算は、アレイ・ユニットに流され、別のものはＣＰＡに流される。従って、実行すべき追加の乗算が無い場合、マルチプライヤは、ＡＲＲｌ  ８０２０又はＡＲＲ２Ｂ  ８０４０から、状態ＣＰＡ８０５０へ移動するか、あるいは、第２の乗算を始める。もし追加の乗算が必要でない場合、マルチプライヤはＣＰＡ８０５０を通り、それからＩＤＬＥ８０１０に戻るか、又は上に説明されるような新しい乗算を始める。
【００５７】
第１の乗算がＣＰＡを通る準備ができた時に、第２の乗算が実行される準備ができたならば、マルチプライヤはＣＰＡ１  ８０６０（３２ｘｌ６乗算用の）又はＣＰＡ２Ａ  ８０７０（３２ｘ３２乗算用の）のいずれかに移動する。状態ＣＰＡ１  ８０６０では、第１の乗算がＣＰＡを通り、第２の乗算がアレイ・ユニットを通る。その後、マルチプライヤは第２の乗算を終了させるために状態ＣＰＡ８０５０に移動する。
【００５８】
第２の乗算が３２ビットの乗算である場合、状態ＣＰＡ２Ａ  ５０７０では、第１の乗算がＣＰＡを通り、第２の乗算がアレイ・ユニットを通る。その後、マルチプライヤは、３２ｘ３２の乗算を完了するために状態ＡＲＲ２Ｂ  ８０４０に移動する。このパイプラインのアプローチは、２サイクルの待ち時間で、すべてのクロック・サイクル毎に３２ｘ１６の乗算が行われることを可能にする。また、３２ｘ３２の乗算は、３サイクルの待ち時間で、クロック・サイクルの１つおきに得られる。
【００５９】
図９を参照する。反復除算演算が有限状態マシーンを用いて実現される。１つの実施例では、ＭＤＵがＩＤＬＥ状態９０１０で始まる。除算演算を始めるための信号が受信されると、ＭＤＵは、演算が正負符号付きである場合はＤＩＶ１  ９０２０へ移動するか、又は演算が正負符号なしである場合はＤＩＶ１Ｕ  ９０３０へ移動する。状態ＤＩＶ１  ９０２０及びＥＲＬＹ  ９０４０は、正負符号を必要に応じて調整して、除算用の正負符号付きオペランドを準備するために使用される。状態ＤＩＶ１Ｕ  ９０３０及びＥＲＬＹＵ  ９０５０は、正負符号なしの除算演算を準備するために使用される。状態ＥＲＬＹ  ９０４０及びＥＲＬＹＵ  ９０５０では、必要な除算の反復数を調整するために、オペランドＲＳにおいて先行ゼロが検知される。
【００６０】
反復除算が状態ＤＩＶ９０６０及びＤＩＶＵ９０７０で実行される。除算は、一連の反復する加算／減算及びシフトを用いて実行される。最後に、剰余は、状態ＲＥＭ９０８０及びＲＥＭＵ９０９０で完成される。オペランドのどちらかが負である場合、正負符号の調整が状態ＳＧＮ９１００で実行される。
【００６１】
再び図４を参照する。１つの実施例において、入替えロジック４３００が、上に説明されたＰＰＥＲＭインストラクションをサポートするために使用される。入替えロジック４３００は、ＲＴｈｏｌｄ３０１２の値に基づいて、ＲＳｈｏｌｄ３０１０の３２ビットのうちのいずれをも選定するために、使用される６つのシングル・ビット３２：１セレクタから成る。このロジックは、データ経路モジュールの中でダイレクトに実現される。
【００６２】
例えば、入替えロジック４３００は、インストラクション「ＰＰＥＲＭ＄５、＄６」を実行するために使用される。入替えロジック４３００は、ＲＳｈｏｌｄ３０１０からの出力としてどのビットを含むべきであるかを特定するために、ＲＴｈｏｌｄ３０１２によって決定される６つの５ビットのセレクタを使用する。例えば、レジスタ＄５が下位ビット「０１０１０１」を保持している場合、セレクタ「０００１０」は、「１」を保持しているビット２（つまり右から３番目のビット）を選択することになる。ＲＴｈｏｌｄ３０１２が下位ビット「０００１００００１１」を保持している場合、「１０」をもたらすビット２（「１」を保持している）及びビット３（「０」を保持している）が、選定されることになる。この方法を使用して、入替えロジック４３００が、ＲＴｈｏｌｄ３０１２に基づいて６ビットを生成するために、ＲＳｈｏｌｄ３０１０からビットを選定する。その結果生じる６ビットが、結果を形成するＡＣＣ１の６６下位ビットに連結される。これは事実上、ＡＣＣ１の６６下位ビットを６ビット左側にシフトさせ、６下位ビットを入替えロジック４３００の出力と入れ替える。
【００６３】
ハードウェア（例えば、マイクロプロセッサあるいはマイクロコントローラ内の）を使用するマルチプライヤの実施例に加えて、ソフトウェア（つまりコンピュータ読み取り可能なプログラムコード）を格納するように設定された、例えば、コンピュータが使用可能な（例えば、読み取り可能な）記憶媒体内に配列されたソフトウェアにおいても、マルチプライヤが具現化される。そのプログラム・コードは、ここに開示されたシステム及び技術の機能又は構成を、あるいはその両方を可能にする。例えば、これは、汎用プログラミング言語（例えばＣ、Ｃ＋＋）、Ｖｅｒｉｌｏｇ−ＨＤＬ、ＶＨＤＬ、ＡＨＤＬ（ＡｌｔｅｒａＨＤＬ）などを含むハードウェア記述言語（ＨＤＬ）、又は他の利用可能なプログラミング及び／又は回路（つまり回路図）キャプチャのツールの使用を通して達成されることができる。プログラム・コードは、半導体、磁気ディスク、光ディスク（例えばＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＷ）、及びコンピュータ使用可能な（例えば、読み取り可能な）伝送記憶媒体（例えば、搬送波、あるいはデジタル、オプティカル又はアナログ・ベースの記憶媒体を含む他の記憶媒体）において具現化されるコンピュータ・データ信号のようなものを含む任意のよく知られたコンピュータ使用可能な記憶媒体内に配列されることができる。従って、コードは、インターネット及びイントラネットを含む通信ネットワーク上で伝送されることができる。
【００６４】
上に説明したシステム及び技術によって、達成される機能、及び／又は提供される構造が、プログラム・コードで実現されるコア（例えばマイクロプロセッサ・コア）内で表されることができ、またＩＣの製品の一部としてハードウェアに変換されることが、理解されるべきである。また、そのシステム及び技術は、ハードウェア及びソフトウェアの組合せとして実現されてもよい。従って、他の実施例も、特許請求の範囲内である。
【図面の簡単な説明】
【００６５】
【図１】ＲＩＳＣアーキテクチャで使用される典型的な５ステージのパイプラインのブロック図である。
【図２】実行ユニット及び乗算ユニットを含むプロセッサ・コアのブロック図である。
【図３】２進の多項式算術をサポートする乗算ユニットの１つの実施例内のデータ経路のダイアグラムである。
【図４】１つの実施例中で算術及び２進の多項式の乗算をサポートするマルチプライヤアレイのブロック図である。
【図５】図４で示した実施例の中で使用される算術マルチプライヤアレイのブロック図である。
【図６】図４で示した実施例の中で使用される２進の多項式マルチプライヤアレイのブロック図である。
【図７Ａ】１つの実施例において、１６ビット乗算による３２ビットの演算を示すタイミング図である。
【図７Ｂ】１つの実施例において、３２ビット乗算による３２ビットの演算を示すタイミング図である。
【図７Ｃ】１つの実施例において、除算の演算を示すタイミング図である。
【図８】乗算インストラクションを実行するためのステップを実現する有限状態マシーンの図である。
【図９】除算インストラクションを実行するためのステップを実現する有限状態マシーンの図である。
【図１０】Ａ及びＢは、拡張精度マルチプライヤを操作する典型的なインストラクションに対するインストラクションの符号の図である。
【図１】
2005505023.tif 000002
【図２】
2005505023.tif 000003
【図３】
2005505023.tif 000004
【図７Ａ】
2005505023.tif 000005
【図７Ｂ】
2005505023.tif 000006
【図７Ｃ】
2005505023.tif 000007
【図１０】
2005505023.tif 000008
【国際公開パンフレット】
2005505023.tif 000009
2005505023.tif 000010
2005505023.tif 000011
2005505023.tif 000012
2005505023.tif 000013
2005505023.tif 000014
2005505023.tif 000015
2005505023.tif 000016
2005505023.tif 000017
2005505023.tif 000018
2005505023.tif 000019
2005505023.tif 000020
2005505023.tif 000021
2005505023.tif 000022
2005505023.tif 000023
2005505023.tif 000024
2005505023.tif 000025
2005505023.tif 000026
2005505023.tif 000027
2005505023.tif 000028
2005505023.tif 000029
2005505023.tif 000030
2005505023.tif 000031
2005505023.tif 000032
2005505023.tif 000033
2005505023.tif 000034
2005505023.tif 000035
2005505023.tif 000036
2005505023.tif 000037
2005505023.tif 000038
2005505023.tif 000039
2005505023.tif 000040
2005505023.tif 000041
2005505023.tif 000042
2005505023.tif 000043
2005505023.tif 000044
2005505023.tif 000045
2005505023.tif 000046
【国際公開パンフレット（コレクトバージョン）】
2005505023.tif 000047
【国際調査報告】
2005505023.tif 000048
2005505023.tif 000049
2005505023.tif 000050