Common Lisp言語処理系によるBroadwellの 任意精度整数演算命令の

Bulletin of Aichi Univ. of Education, 65（Natural Sciences），pp. 25 － 28, March, 2016
Common Lisp 言語処理系による Broadwell の
任意精度整数演算命令の評価
安本 太一
情報教育講座
Evaluation of Broadwell Instructions Supporting Large Interger
Arithmetic on a Common Lisp System
Taichi YASUMOTO
Department of Information Sciences, Aichi University of Education, Kariya 448-8542, Japan
ための命令として，mulx，adcx，adox が用意されて
1　はじめに
いる．
インテル社の第 5 世代 Core プロセッサ Broadwell マ
イクロアーキテクチャに実装されている任意精度の整
数演算のための命令
［1, 2］
の評価を，Common Lisp［3］
mulx は，64 ビット（あるいは 32 ビット）の符号な
し整数どうし src1，src2 の掛け算を行う機械語命令
言語処理系である KCL（Kyoto Common Lisp）［4, 5］
mul の拡張版である．アセンブラ表記は次の通りであ
り，64 ビットの場合は rdx を，32 ビットの場合は edx
の bignum（無限長整数）の掛け算を用いて行ったの
を src2 として使う．
で，その結果を報告する．なお，本論文では，任意精
mulx dest_hi, dest_lo, src1
度整数は一般的な用語，bignum は Common Lisp の無
限長整数を示すものとして扱う．
その動作は
任意精度の整数演算をとりあげるとき，基本データ
dest_hi:dest_lo = src1 r/edx
型である整数の配列
（例えば 32 ビットや 64 ビットの整
数の配列）で，基本データ型の整数よりも長い任意精
のように，ソースオペランド src1 と src2 の積を計算
度の整数を表現することが多い［1, 2］
．基本データ型
である整数の演算を何度も適用して，任意精度の整数
し，その結果を，2 つのレジスタを連結したディスティ
ネーションオペランドである dest_hi:dest_lo に格
の演算を行うのである．一方，KCL の bignum は，配
納する．フラグレジスタは変更されない．実質 4 オペ
列でなく，リスト形式で，C 言語の基本データ型の整
ランドの命令なので，ソースオペランドの値を破壊し
数を連結した表現で実現されている．
配列形式の任意精度整数において，インテル社が提
ないことが可能である，
adcx と adox は，adc（キャリー付き加算命令）の拡
案して実装した任意精度の整数演算のための命令が速
張版であり，アセンブラ表記は次の通りである．
度向上に寄与するのは，掛け算に必要な命令数が減っ
adcx dest/src1, src2
ていることがインテル社のドキュメントおいて示され
adox dest/src1, src2
ているので，明らかである［1］
．
そこで，今回は，これらの命令を，実際の Lisp 言
語 処 理 系 に お いて，リスト形式で表現され て い る
これらの2つの命令は，src1と src2のキャリー付き加
算を行い，その結果を dest に格納する．adcx と adox
bignum における掛け算で用いた場合は，どれくらい
の違いは，CF フラグと OF フラグの扱いである．adcx
の速度向上が得られるのか調べてみた．
は，CF フラグを用いてキャリーインしてキャリーア
ウトし，OF フラグを変更しない．adox は，OF フラグ
2　Broadwell における任意精度整数演算のため
の命令
を用いてキャリーインしてキャリーアウトし，CF フ
ラグを変更しない．adcx と adox を使い分けることに
よって，2 つのキャリーフラグのチェーン（流れ）を
2.1　mulx, adcx, adox 命令
作ることができる．
Broadwell には，任意精度整数演算をサポートする
例 え ば，mulx，adcx，adox を 使 う と，64 ビ ッ
― 25 ―
安本 太一
トの整数を 8 個連結して表現した 512 ビットの整数
A7 A6 . . . A1 A0，B7 B6 . . . B1 B0 の積を，効率よく計算でき
3　KCL の bignum
る．筆算のように，A7 A6 . . . A1 A0 × Bi を繰り返して行
KCL の bignum は，図 1 に示す bignum セル（無限
うとき，A7 A6 . . . A1 A0 × Bi–1 の結果と加算していくこ
長整数セル）の連結によって実現されている．この
とになるが，Aj × Bi は 2 語になるので，
“フラグを変
図で示すのは 64 ビット版の KCL における表現であり
更しない掛け算命令”と“キャリーの流れを 2 つ実現
［7, 8］，本論文では 64 ビット版の KCL に 64 ビット版の
mulx と adcx を適用することのみを扱う．
できる加算命令”があると，命令数が少なくて済むか
らである［1］
．
固定長の任意精度整数のように 64 ビットの整数領
なお，今後は，32 ビットについては言及せず，64
域を連続してメモリ領域に配置した表現ではなく，連
ビットにのみに言及する．
続した領域が確保できなくても，メモリの許す限り無
限長の整数を表現できるよう，このような構造になっ
2.2　高級言語からの利用
ている．計算の過程で，変数から参照されなくなった
mulx，adcx，adox 命令は，次に示すように，C 言語
bignum が使用していた bignum セルの領域は，ごみ集
（C++ 言語を含む）から次のような関数呼び出しの形
めで回収され，再利用可能なメモリ領域として利用さ
で利用可能であると，ICC（Intel C++ Compiler）を発
れる．
売しているインテル社のドキュメントに記述されてい
る［1］
．gcc の場合は，_umul128 ではなく _mulx_u64
である．関数呼び出しの形式ではあるが，gcc-4.9 コン
パイラにおいて，call 命令を伴わなずに，アセンブラ
命令（機械語命令）に展開されることを確認している．
mulx に対応．返り値が lo_dest /
unsigned _ _int64
/
umul128(unsigned _ _int64 src1, unsigned _ _int64 src2, unsigned _ _int64
hi_dest);
図 1：64 ビット環境下の bignum セルの構造
adcx と adox に対応，返り値が c_out /
unsigned char
/
bignum を構成する整数を表現するためのフィール
_addcarryx_u64(unsigned char c_in, unsigned _ _int64 src1, unsigned _ _int64 src2, unsigned _ _int64
ドとして 64 ビット確保しているが，実際に整数を表現
しているのは下位 63 ビットである．上位 1 ビットは一
時的な利用場所で，例えば，下位 63 ビットに整数を加
sum_out);
算した直後のキャリー検出に使用し，キャリー検出に
キャリーのための C 言語の変数（c_in, c_out に対
応する変数）
の名前を使い分けて，_addcarryx_u64 を
対応した処理を行った後はすぐ 0 にされる．
使えば，コンパイラの方で，adcx と adox を使い分け
bignum の掛け算を実現するための内部ルーチンと
して，extended_mul(long int d, long int q, long
るコード生成をすると，インテル社のドキュメントに
int r, long int   hp, long int   lp) を使用してい
は記述されている［6］
．ICC の場合は，そうなるのか
る．d × q + r を計算し，その結果を，hp と lp が指す
もしれないが，gcc-4.9 ではそのようにはならず，C 言
場所に格納する．d, q, r は，64 ビットの非負整数であ
語の変数を用いてキャリーフラブを陽に設定するコー
る．lp が指す場所には，結果の下位 63 ビットを格納
ドが生成されていた．
し，最上位ビットは 0 である．hp が指す場所には，結
AVX の SIMD 命令に対応する C 言語の関数が用意
果の残りのビットを格納し，最上位ビットは 0 である．
されるといったことはあったが，上記のように逐次実
extended_mul は，当初は実行効率を重視してイン
行の機械語命令に対応する C 言語の関数が用意される
ラインアセンブラで記述されていたが，KCL の移植
ことは珍しい．高級言語から特定の機械語命令を明示
の容易性を重視して C 言語バージョンが用意されてい
的に指定できるので，キャスト演算子を駆使するなど
る．KCL の配布ソースには，アセンブラバージョンは
プログラムの書き方を工夫して特定の機械語命令が生
成されるようコンパイラに期待するいう，不安定でや
32 ビットプロセッサ向けのみが含まれているので，今
回，64 ビット版の mulx と adcx の使用を試みることは
りにくい方法をとる必要がない．
意義がある．大雑把にいうと 64 ビット版の C 言語の
バージョンは，図 2 に示すように，64 ビットの掛け算
― 26 ―
Common Lisp 言語処理系による Broadwell の任意精度整数演算命令の評価
を，被乗数 d と乗数 q を 32 ビットに分けて計算するよ
うになっていた．オーバーフローを防ぐためである．
本図において，r の加算，積の結果の lp や hp への 63
ビットずつの配置は省略されている．
図 3：任意精度整数演算のための命令を利用した C 言語版
extended_mul
図 2：オリジナルの C 言語版 extended_mul の概要
4　任意精度整数演算をサポートする命令 mulx,
adcx の利用
先述の _mulx_u64と _addcarryx_u64を用いて書き
換えた，C 言語バージョンの extended_mulを図 3 に示
す．gcc-4.9ののヘッダにあわせて，unsigned_int64で
はなく，unsigned long longを使用しているが，64
なものである．再帰的にしなかったのは，fact の引数
が大きい場合，スタックが足りなくなり，実行が途中
で中断してしまうからである．関数 fact は，実行する
前にコンパイルしたので，インタプリタ実行ではない．
extended_mul コンパイル時の最適化オプション
（-O）なしで構築した KCL で（fact 10000）を実行し
た場合の実行時間を，表 1 に示す．10 回計測し平均値
ビット環境下では，unsigned long long は long int
をとったものである（以下同様）．この実行中 565 回の
とともに，64 ビットである．
ごみ集めが行われ，そのための時間も実行時間に含ま
積 d × q は 4 つに分けることなく _mulx_u64 で一
気に行う．和 +r は _addcarryx_u64 を用いて行う．
れている．最適化オプションなしなので，gcc が C 言
語の関数 extended_mul を翻訳して生成したアセンブ
キャリーは，C 言語の変数 carry で明示的に受け渡し
ラコードは，（ロード・ストア命令 movq を主とする不
する．その結果，extended_mul の（ブロックの内側
の）行数は，オリジナルの C 言語版と比べて 40% 程度
必要な命令を大量に含む）冗長なものである．mulx,
adcx 使用のバージョンは，オリジナルと比べて，約
に減少した．
9% の実行時間短縮が得られている．
一方，extended_mul コンパイル時の最適化オプ
ション（-O）ありで構築した KCL で（fact 10000）
5　評価実験
を実行した場合の実行時間を，表 2 に示す．この実行
mulx, adcx の使用の有無によって，階乗のプログラ
ムの実行時間がどのように変化するか調べた．また，
extended_mul を（定義している KCL のソースファイ
ル earith.c を）gcc でコンパイルするときの最適化オプ
ション（-O）の有無によって，階乗のプログラムの実
表 1：(fact 10000) の実行時間（-O 最適化なし）
extended_mul のバージョン
実行時間
比
オリジナル
1.943
1.0
mulx, adcx 使用
1.765
行時間がどのように変わるかも調べた．
実行環境は，アップル社製 MacBook Pro
（Retina, 13inch, Early 2015）で，搭載している CPU は Intel Core
i7-5557U 3.1GHz で あ る．OS は OS X 10.10.5，gcc の
バージョンは4.9である．実験に用いた階乗のプログラ
ムは（fact 10000）を計算するもので，階乗を計算す
る関数 fact の定義は do を用いた繰り返し的な典型的
― 27 ―
0.908
（単位は秒）
表 2：(fact 10000) の実行時間（-O 最適化あり）
extended_mul のバージョン
実行時間
比
オリジナル
1.744
1.0
mulx, adcx 使用
（手修正なし）
1.733
0.994
mulx, adcx 使用
（手修正あり）
1.728
0.991
（単位は秒）
安本 太一
中にも，565 回のごみ集めが行われ，そのための時間
も実行時間に含まれている．最適化オプションありな
ので，gcc が C 言語の関数 extended_mul を翻訳して
7　まとめ
Broadwell の任意精度整数演算命令を，Lisp 言語処
生成したアセンブラコードは，先述のような不必要な
理系の bignum の掛け算の中で用いることで，評価し
命令を含まず，簡潔なものである．
“手修正”という
た．
のは，carry という変数を使って C 言語レベルでキャ
mulx 命令の意義は，64ビットの整数の積を確実に高
リーの受け渡しを行っていたものを，機械語レベルで
行うよう，gcc が生成した extended_mul のアセンブ
速に行うことと，フラグを変更しないことであること
ラコードを，手作業で修正したもので，機械語レベル
で命令数が減る（図 4 参照）
．コンパイラの最適化オプ
分割して 4 つの積を行う方法をとるとき，これらの積
が同時実行できる場合は，mulx 命令に実行効率が近づ
ションありの場合は，オリジナルと比べて，手修正な
くが，生成される機械語命令の列によっては，常に同
しの場合は約 0.5% の実行時間短縮が，手修正ありの場
時実行できるとは限らないからである．
合は約0.9% の実行時間短縮が得られている．コンパイ
adcx が C 言語から使えるようなったことは，C 言
ラの最適化オプションなしの場合に比べて，実行時間
語によるコード記述が簡潔になる利点があるが，C 言
短縮（速度向上）の効果は，ごくわずかである．
語の変数を介するオーバーヘッドがあらわれる．コン
が，明確にわかった．被乗数と乗数を 32 ビットずつに
パイラによる最適化においては，キャリーフラグの
チェーンをみつけ，C 言語の変数へのアクセスを排除
して，adcx（や adox）の特徴を生かしたコード生成
が行われることが望まれる．
参考文献
［1］Intel Corporation: New Instructions Supporting Large Integer Arithmetic on Intel Architecture Processors, Document
number: 327831-001（2012）
.
［2］Intel Corporation: Large Integer Squaring on Intel Architecture Processors, Document number: 328569-001（2013）
.
［3］Steele, G. L. Jr.: Common Lisp the language, Digital Press
（1984）
.
［4］Yuasa, T. and Hagiya, M.: Kyoto Common Lisp Report,
図 4：gcc -O が出力したアセンブラのコードの手修正
­Teikoku Insatsu Publishing（1985）
.
［5］Yuasa, T.: Design and Implementation of Kyoto Common
Lisp, Journal of Information Processing, Vol. 13, No. 3, pp.
284-295（1990）
.
6　考察
［6］Intel Corporation: User and Reference Guide for the Intel
C++ Compiler 15.0（2015）
.
gcc の最適化オプションを指定しない場合，
（fact
10000）の実行時間が約 9% 短くなったことは，mulx や
［7］安本太一：Common Lisp 言語処理系の 64 ビット化，愛知教
adcx の使用の効果によるものだと推測される．実行時
［8］安本太一：Common Lisp 言語処理系による 64 ビット環境の
間には 565 回も行われたごみ集めなど extended_mul
育大学研究報告 自然科学編，五十三輯，pp. 27-32（2004）．
評価，愛知教育大学研究報告 自然科学編，五十五輯，pp.
9-13（2006）．
以外のものが含まれていることを考慮すれば，よく健
闘していると判断される．
gcc の最適化オプションを指定した場合は，実行時
間の短縮がわずかであったのは，図 2 で示したオリジ
ナルの 4 つの掛け算の全て（あるいはいくつかが）が同
時に実行されたことが推測される．Broadwell は ALU
を複数持っているからである．最適化オプションを指
定しないときは，冗長な命令が多かったため，掛け算
の同時実行が行われなかったと推測される．
図 4 に示す手修正により得られたコードは，命令数
が減ったことが，実行時間のわずかな短縮に繋がって
いる．C 言語の変数によるキャリーの伝達のコストを
みることができた．
― 28 ―
（2015 年 9 月 24 日受理）