Upgrade to Pro — share decks privately, control downloads, hide ads and more …

PLDI '21論文読み会: High Performance Correctly Round...

Idein
June 08, 2022

PLDI '21論文読み会: High Performance Correctly Rounded Math Libraries for 32-bit Floating Point Representations

Idein

June 08, 2022
Tweet

More Decks by Idein

Other Decks in Research

Transcript

  1. High Performance Correctly Rounded Math Libraries for 32-bit Floating Point

    Representations PLDI2021読み会@Idein 2021/09/24 藤井裕也
  2. 概要 • 正しく丸められた32bitの数学ライブラリを実装する ◦ 正しく丸められた、とは ▪ 正しい実数から32bitに丸めた値のこと ◦ よく使われているライブラリには誤った出力がある ◦

    正確なライブラリもあるが性能が低い • 著者らの16bit版のライブラリが存在する ◦ 32bitにそのまま適用するにはいくつか課題がある • この論文では16bit版の手法を改良して32bit版を実装する ◦ floatとposit32の両方 ▪ posit32: 0付近の精度が高いような浮動小数点の規格
  3. 先行研究の問題点 • mini-max approach ◦ すべての入力に対する誤差のうち、最大の誤差を最小化する ◦ 誤差発生ポイントがいくつかある ▪ range

    reduction ▪ output compensation ▪ 多項式の評価 • RLIBM ◦ 16bit版の著者らの実装 ◦ 上記の誤差発生ポイントを抑えて、結果的に誤差がないようにしている ◦ 線形計画問題にしてLP solverで解いている ▪ 32bitだと制約の数が多すぎる
  4. sin(𝛑x)の例 range reduction (1/2) • sinの三角関数や周期関数の特性を使って考慮すべき入力を 減らす • ◦ ◦

    J = K + L (Kは整数部分、Lは小数部分) • [0.5, 1)は[0, 0.5)の鏡像なので、入力は[0,0.5)だけ考えれば 良い • これでもまだ1億8400万通りくらい入力がある
  5. sin(𝛑x)の例 range reduction (2/2) • ◦ L’ = N/512 +

    R • sinpi(N/512)とcospi(N/512)は事前に計算しておく • • 入力は0から1/512の範囲まで減らせたが、cosも必要になっ た
  6. sin(𝛑x)の例 多項式の生成 (2/5) • 正しいライブラリを使って、各入力に対する正解値の範囲を 求める ◦ rounding intervalと呼んでいる •

    まず32bitでの正解値を求める • doubleの精度で、丸めると正解値になる上限と下限を求める
  7. sin(𝛑x)の例 多項式の生成 (3/5) • range reductionの結果の入力Rに対する正解値を求める • 範囲は狭まったが、sinpi(R)とcospi(R) (R ∈[0,1/512))

    が必 要になった • 32bitで正しい結果になるsinpi(R)とcospi(R)を求める ◦ sinpi(R)とcospi(R)の結果が32bitで正しいことは不十分 ◦ sinpi(R)とcospi(R)を使った結果の式が32bitで正しい必要がある
  8. sin(𝛑x)の例 多項式の生成 (4/5) • 入力をsub-domainに分割する ◦ 入力を減らしたとはいえ、まだ1億1千万通りもある ◦ ビットパターンで入力を分割する •

    sub-domainのインデックスのbitはMSBから始めない ◦ 事前に範囲を絞ったので、R=0以外の入力は左から6bit分共通している