2002年 12月 17日
SPLICE数値演算講演会@ 宇宙開発事業団

Numerical Computing in Javaー 演算結果の再現性と性能

首藤 一幸
産業技術総合研究所
グリッド研究センター

自己紹介
分散処理, 高性能計算, Javan

分散・並列化コンパイラ（1995〜1997）
w ネットワーク接続されたWS/PCを対象に、逐次プログラムを分散。

nJava仮想マシン間のスレッド移送（1997）
w ネットワーク越しに、マシン間で実行状態を移送。

Java Just-In-Timeコンパイラ（1998〜）
n ネッ
トワーク透過な分散オブジェクトシステム（1998）
nw 遠隔、ローカルの区別なく、オブジェクトを扱える。

浮動小数点演算セマンティクスの効率的な実装（1998〜）
n 組織内、インターネット上の分散計算ミドルウェア（2002〜）n

暗号, 情報セキュリティ
共通鍵暗号方式の、Javaによる高性能実装（1998）
n 共通鍵暗号方式の強度解析（1995）nJavaプログラムの実行
ソース
コード

実行前

(.java)

実行前
Java コンパイラ(javac, Jikes, KJC)

バイトコード
命令列(.class)

他言語のソースコードAhead-of-Time
コンパイラ(GCJ, TowerJ, JET, …)

Just-in-Time
コンパイラ 実行中
バイトコードインタプリタネイティブコードJavaによる高性能計算の問題
実装 （JITコンパイラ, インタプリタ）の性能が低かった。
n

ピーク性能はC, Fortranに近づいてきた。

ハードウェアの性能、機能を搾り尽くす手段がない。
nPowerPC の fused multiply-add （FMA）を使えない。
w もし使うと、Java 言語仕様が定める演算のセマンティクスを守れない。

n

丸めの方向を制御できない。
w Javaでは、浮動小数点数の表現形式は IEEE 754。
w IEEE 754は、最近値への丸めだけでなく、+∞, -∞, 0 方向という3通りの丸め方向の提供を義務付けている。

n

浮動小数点演算の例外でトラップを発生させる方法がない。
w 例外：invalid operation ((+∞)+(-∞), 0×∞など), divide by zero, overflow,underflow, inexact
w とはいえ、発生するように設定する方法は、C でも環境依存。場合によっては要アセンブリコード。

Javaによる高性能計算の問題
言語仕様
n

配列アクセス時に境界を越えていないかのチェックが必要。
w (new int[10])[15] …例外発生

n２次元配列が、１次元配列の配列である。
w C言語などとは違い、アドレス計算→アクセス、では済まない。
w Jose Moreira (IBM) らが改善案を提案中。
n ライブラリ （例: doubleArray2Dクラス）+ syntax sugar （a[i,j] という表記をライブラリ呼び出しに変換する）

w C#言語 (Microsoft) には、Javaと同じjagged arrayに加えて、rectangular arrayがある。
n jagged array: a[i][j], rectangular array: a[i, j]n

例外をthrowし得る処理を越えて、命令の実行順を入れ替えられない。
w コンパイラによる最適化が制限される。

n演算子オーバーロードができない。
w 複素数の演算も、a.multiply(b) と書かざるを得ない。

Javaによる高性能計算の問題
言語仕様 （cont’d）
n浮動小数点演算のセマンティクスを厳密に定めている。
w Java 2 より前の規定：「演算の中間結果も、厳密に指数部 11ビット、仮数部 52ビット。」
w Intel社 x86プロセッサ上で律儀に実装すると、数値計算が数倍以上遅くなってしまう。

キーワードstrictfp が Java 2 から導入された。
nプログラム中で strictfp 指定がない箇所でのセマンティクスが緩められた。
w Java 2より前は、常に strictfp の厳しいセマンティクスで演算する必要があった。
w x86でもオーバーヘッドがなくなった。
注）ただし単精度数の演算は依然、要注意。きちんと実装すると、SSE, SSE2命令群を使わない限り、オーバーヘッドを避けられない。

strictfp とは
文法
nクラス、メソッド、インタフェースの修飾子。
w 例) strictfp void aMethod(…)

n{ …

static, lexical スコープ。

意味n

言語仕様が定めるセマンティクス (FP-strict) に厳密に沿わねばならない。
w SPARC, Alpha, PowerPC, MIPS と同じセマンティクス。

n

逆に、strictfp ではない文脈では、もう少し、緩くてよい。

x86 プロセッサ(x87命令)は沿っていない。
x86 用の Java 仮想マシンは 実装を工夫する必要がある。
n Sun社, IBM社は Java 2 SE 1.4 でようやく実装した。
n演算結果が異なる 実例
FP-strict か否かによって、結果が異なる。
SPARC等では常に `strictfp’ と同じ結果。
n

特に、実装上の工夫は要らない。

異なる% java StrictfpTest
shuJIT for Sun Classic VM/x86 by Kazuyuki Shudo
1.112808544714844E-308 (0x0008008000000000)* 1.0000000000000002 (0x3ff0000000000001)
default : 1.112808544714844E-308 (0x8008000000000000)
strictfp: 1.1128085447148447E-308 (0x8008000000000001)

異なる

2.225073858507201E-308 (0x000fffffffffffff)/ 0.9999999999999999 (0x3fefffffffffffff)
default : 2.2250738585072014E-308 (0x1000000000000000)
strictfp: 2.225073858507201E-308 (0xffffffffffffffff)

x86 の仕様
浮動小数点数のレジスタは 80 bit 長。
n

64 bit でも 32 bit でもない。

精度に応じた演算命令を持たない。
cf. fmuls とfmuld (SPARC), mul.s とmul.d (MIPS)n 仮数部は丸め精度の設定に応じて丸められる。
nstrictfp が要求する形式単精度
倍精度

x86 拡張精度
80 bit1823(bit)

符号

指数部

仮数部

11152

符号

指数部

115符号

指数部

仮数部

64
仮数部

x86 の仕様
指数部は常に 15 bit (拡張精度) !!
ncf. 単精度 8 bit、倍精度 11 bit。

x86 にて、丸め精度を倍精度に設定した場合
1
符号15 (not 11 !!)
指数部

52 (倍精度)

丸め

仮数部

IEEE 754 規格はこれを許容している。
nx86 は IEEE 754準拠。

問題となる場合
指数部が常に 15 bit なので起こるべき溢れが起きない。
(-1) s ･ 2 E ･ 1. …… としてE のビット数E の範囲

単精度

8-126 〜 +127

倍精度

11-1022 〜 +1023

x86拡張精度

15-16382 〜 +16383

次の倍精度演算の結果が …
レジスタ = 2 +1023
レジスタ+= 2 +1023
レジスタ+= 2 +1023•SPARC では +∞+1023•x86 では2
アンダーフローでは、二度丸めの問題も…

「strictfp を実装する」とはどういうことか？
JavaコンパイラnJava言語で書かれたソースコードをJavaバイトコード（クラスファイル）に変換する。
w javacコマンド, Jikes, KJC など

nキーワード“strictfp” を認識して、クラスファイルにその旨を反映させる。
w 容易。

n

コンパイル時定数は、FP-strict に演算する必要がある。

実行系n

Javaバイトコードを解釈、実行するか、ネイティブコードにコンパイルする。
w インタプリタ, Just-In-Timeコンパイラ, Ahead-of-Timeコンパイラnstrictfp だという印のついたメソッドについて、FP-strict のセマンティクスで演算を行う。
w x86 では工夫が要る。性能上のオーバーヘッドがある。
n もし整数演算でエミュレートしたら、非常に遅くなるだろう。
w Golliver（Intel）は、効率良い方法を提案し、２〜４倍の演算時間、と予想した。
w 首藤らは、x86での効率良い実装方法を調べた。

strictfp の実装状況
Sun社, IBM社は、Java 2 SE 1.4 でようやく実装した。
strictfp の仕様自体は1.2 （Java 2）で導入されたもの。
n Javaコンパイラ（javac）はstrictfp対応していたが、Java仮想マシン（JITコンパイラ, インタプリタ）が未対応だった。
n

ごく一部の実行系、コンパイラは、以前より実装していた。
nshuJIT
w 首藤らによるJITコンパイラn

BulletTrainw NaturalBridge社によるAhead-of-Timeコンパイラ

性能評価
目的
nn

strictfp のオーバーヘッドを知る。
w FP-strictな演算では、そもそも、JavaはCやFortranとどのくらい性能が違うのか？

評価方法
nLinpack ベンチマーク
w 連立一次元方程式を解く。密行列。
w naive なコード。
n ベンチマークプログラムには変更を加えない。
変更するのは問題サイズだけ。
n ブロッキングなど、通常は必須である最適化も行わない。
w C# 版は、Java 版を移植したもの。

環境n

1.7 GHz Pentium 4 / Linuxw C# は、Windows 2000 SP3n800 MHz Pentium III / Linuxw C# は、Windows .NET Server 2003 RC1

Linpackベンチマーク•キャッシュ: L2 256 KB, L1 8KB•IBMのJITコンパイラ、インタプリタは、SSE2命令 （後述）を使っている？

1.7 GHz Pentium 4
050

100

150

200
MFlopsIBM SDKSun HotSpot Server VM

43 %Sun HotSpot Client VM

27 %

GCJ

65 %

Sun インタプリタ

10.95

IBM インタプリタ

8.28

183.6

157.8

strictfp

Linpack Benchmark
n = 1000

n=100, Intelコンパイラ

on 1.7 GHz Pentium 4Intel Fortran Compiler

214.6

g77

211.6Intel C++ Compiler

220.0

gcc

210.3

C#

参考
FORTRAN (SSE2命令)
813.8 MFlops
FORTRAN (x87命令)
425.9 MFlops
C (SSE2命令)
757.1 MFlops
C (x87命令)
426.2 MFlops

通常42.842.4

shuJIT (SSE2)
shuJIT (x87)

203.2
197.8

134.6

FORTRAN 77

CC#Linpackベンチマーク•キャッシュ: L2 256 KB, L1 16 KB

800 MHz Pentium III
01020

Sun HotSpot Server VM

3040

43.4

54 %

IBM SDK

67 %

GCJ

27.0

Sun HotSpot Client VM

5060
MFlops40.4
38.9

通常strictfp

89 %shuJIT

67 %IBM インタプリタ

6.15

Sun インタプリタ

5.43

22.4

参考n=100, Intelコンパイラ

Linpack Benchmark

FORTRAN 344.4 MFlops
C333.7 MFlops

n = 1000
on 800 MHz Pentium III

Intel Fortran Compiler

54.8

g77

55.2

Intel C++ Compiler

54.9

gcc

54.9

C#

26.9

FORTRAN 77

CC#SSE2 命令
実は… SSE2命令は FP-strict に演算を行う。
x87命令のような変態 (80 bit の拡張形式) ではない。
n 精度ごとの演算命令を持つ。
n

SSE2 : Streaming SIMD Extensions 2
Pentium 4 （2000年末出荷）で追加された命令群。
n SIMD演算用の命令セットでありながら、実は浮動小数点演算全般をサポート。
nw IEEE 754準拠 (丸め制御, 例外, 平方根, …)。
w x87 とは異なり、超越関数の命令は持たない。

何ら工夫は要らない。

まとめ
Java言語仕様は、C, Fortran などと比べて確かに厳しい。
結果の再現性を重視。
n 性能の追求や、コンパイラによる最適化を妨げる規定もある。
n しかし、最近の実行系のピーク性能は、C, Fortran に迫っている。
nw Just-in-Timeコンパイラが、実行時に、頻繁に実行されるメソッドに限って、最適化する。
nJavaを使うメリット:
w クラスファイルが機種非依存。
w 実行結果の再現性が高い。異機種間であっても。
w 標準クラスライブラリが充実している。
w 開発、デバッグの労力が比較的低い。
nポインタを数値として扱えない、配列の境界チェックがある、…

参考文献
Validgh Java numerics pagenn

http://www.validlab.com/java/“How Java’s Floating-Point Hurts Everyone Everywhere” by W. Kahan

Java Numericsnn

http://math.nist.gov/javanumerics/
Javaを用いた数値計算についての情報源。Java Grande ForumのNumerical WGの打ち合わせ記録など。

Java Grande Forumnn

http://www.javagrande.org/“Javaと高性能計算” に取り組んでいる集まり。

Performance comparison of JITsnn

http://www.shudo.net/jit/perf/
各種Java仮想マシン、JITコンパイラの性能評価。

The Java Performance Reportnnn

http://www.javalobby.org/members/jpr/
要ユーザ登録 & ログイン。
PART III （Sep 2000）ではCとの比較も行っている。

Languages for the Java VMn

http://grunge.cs.tu-berlin.de/~tolk/vmlanguages.html