リンクフリーを近日中にとりやめる予定です

すでにリンクを貼っていただいている方、ご一報頂きたくお願い申し上げます。


ごく少数ですが、リンクをお断りする場合があります



ブログ内 風景光景カテゴリー

続編記事などをご希望の方は こちらへどうぞ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[未掲載分] 「除算が遅い」の補足 (8)

「除算が遅い」の補足 (6)「除算が遅い」の補足 (7)で、実数 ( 浮動小数点数 ) の除算でさらなる速度向上を目指すについて触れた。



今回は、整数の除算について・・・


お知らせ
活動休止にともない、この記事を事前に予約投稿してあります。
トップ記事の固定を目的としています




A = B ÷ C という式において、C ( 除数、割るほうの数 ) が定まっている場合、「除算が遅い」の補足 (2)で、述べたように
・整数の除算ならば、「乗算とシフト」に置き換えると良い。

除数 が定まっていないとして話を進めよう。「除算が遅い」の補足 (6)で、浮動小数点数の演算を多数繰り返す場合、
・追加された XMM レジスタを活かし同時に複数の演算を行うことや、
・並列に実行できるように練り直すことで、さらなる速度向上を期待できると述べた。昨今のCPUであれば、依存関係が無い命令が続く場合、同時に実行できる。

ということは、整数の除算についても、それと同様の手法が使える???

SSE2 命令に対応した CPU であれば、XMM レジスタで整数の演算も可能である。
複数の倍精度浮動小数点数を扱うには、__m128dといった変数の型を用いた。複数の整数を扱う際に用いる変数の型は__m128i



128ビットの XMMレジスタで32ビット幅の整数値を4組、



もしくは、64ビット幅の整数値を2組同時に扱える。ほかにも、16組の8ビット整数や8つの16ビット整数といった組み合わせも可能である。

実は、加算、減算、乗算の命令は用意されている。しかし、XMM レジスタで整数の除算を行う命令が無い。

C/C++ 言語で XMM レジスタを明示的に使う場合、浮動小数点数の演算では_mm_ ○△□ _pdなどの組み込み関数を用いる。乗算や除算は_mm_mul_pd_mm_div_pd
整数の加算、減算、乗算はそれぞれ、_mm_add_epi32 や _mm_add_epi64、_mm_sub_epi32 や _mm_sub_epi64 、_mm_mul_epu32 の組み込み関数が用意されている。しかし、除算に直結するような _mm_div_epu32 や _mm_div_epu64 が用意されていない・・・
たしか、ここはリザーブ扱いになっていたハズなので SSE2 が登場したての頃将来的に実装する予定だったのかもしれません。その後、SSE3 から SSE4.2に至るまで整数の除算命令は追加されませんでした。XMM レジスタを用いた整数の除算命令が備わることを望む声も少なくなかったハズ・・・

・・・ということで、整数の除算部分を自前で組む???

昨今流通している CPU では当然のようにハードウェアレベルで除算が可能。汎用レジスタで除算する仕組みが備わっている。
これを書いている時点でPC 用として普及している CPU は Core i7 シリーズ。Core i7 は 1980年代後半に普及した Intel 80386 ( i386 ) の流れを汲んでいる。i386 は 32ビット版 の CPU として登場した。遡ると、8086 や 80286 などの16ビット版のプロセッサをもとに32ビット版への拡張が施された。



8086 には登場時から除算機能が備わっている。つまり、汎用レジスタによる整数の除算が可能である。8086 の説明で「~~~ 8080のアーキテクチャを16ビットに拡張し、乗除算などの命令を強化したCPU ~~~」などの記載を見かける。
「アーキテクチャうんぬん」との表記に戸惑うヒトがいるかもしれない。要はIntel 8080 という 8ビット版 CPU の「基本設計概念」を受け継ぎ 16ビット版 CPU として登場したといったところ。
細かく言うと、Intel 8080 の後継、拡張版としては Intel 8085 や Z80 などの 8ビット版 CPU が存在した。Z80 は Intel 8080 の開発に携わった者たちが独立起業して開発されたモノだが、当時は 8080よりもZ80を搭載した PC も多く流通していた・・・

ここで肝心なのは CPU の進化うんぬんよりも、「乗除算などの命令を強化した」の部分。かつては除算命令が備わっていなかったことを指している。その頃の機器は、データの読み書き、加算、減算とシフトが出来る程度だった。誤解が無いように加えておけば「除算命令が備わっていない」「除算できない」ではない。
自前で組むか、既存のライブラリに頼るかプログラマの力量次第だが、除算命令が備わっていなくてもソフトウェアレベルで何とかすることができた。

そもそも、昨今の CPU で除算命令をどのように処理しているのだろうか。
大雑把に言えば、ひたすら引き算を繰り返す。乗算 ( 掛け算 ) はたくさんの足し算に置き換えられることが判ればこの辺は易く理解できるハズ。

古くからの手法として、引き放し法や引き戻し法が有名である。また、0 と 1 で表される2進数の除算に最適なFast recursive divisionが発表されている。この元を書いたのは西暦2012年。Fast recursive division が発表されたのは西暦1998年頃であり、それから10年以上経つが、ハードウェアレベルで備るにはまだ時間が掛かるかも。

ひとことに引き算を繰り返すと書いただけでは想像しずらいかもしれません。
例えば1234÷5を計算するとしよう。予め答えを書いておくと246。
ひたすら引き算を繰り返すといっても、1234から5を引いて1229、まだ5より大きいから5を引いて1224~~~といった手順は非効率。
私たちが子供の頃習うのは、最上位の1は5より小さいので引けない。上から2桁の12から5を2回引いて、余りが234。次に2から5は引けないので23から・・・といった具合である。
被除数 ( 割られるほうの数 ) に対して除数 ( 割るほうの数 ) をそれぞれの位に合わせながら解いてゆくハズ。

2進数を理解すればシフト、減算、比較命令で除算処理を実現できそう。その前に、2進数とは何ぞやという状態でここを訪れたヒトは遅くない除算をご参照あれ・・・
1234を 2進数 ( 0 と 1 の組み合わせ ) で表すと0100 1101 0010 。同様に5を2進数で表すと 0101。

最初に被除数と除数を比べます。小さければ 0、等しいなら1の答えをもって終了。そうでない場合は位をそろえながら引き算を繰り返します。

まず、位を合わせます。


最上位の何ビット目が1であるかを探し、除数をシフトして位を合わせます。使うのはビットスキャンとシフト命令。



引けるか否かを比べ、可能なら減算。ここでは 0100 から 0101 を引けないので位を下げるため1ビット右シフト。使うのは比較と分岐、シフト命令。



さてさて、今度は引けそうです。減算命令の出番。引いた結果が大きければ、さらに1ビット右シフトして~~~といった感じで引けなくなるまで繰り返します。

答えは2進数で 1111 0110。 不慣れなヒトにとって 0 と1 の組み合わせで0110 等の表記は見辛いことでしょう。理解するには、一番右を1として、2番目のビットが1なら2,3番目のビットが1なら4,4番目のビットが1なら8 を足してゆくことで変換し易くなります。例えば、2進数の 0110を10進数に変換する場合 4+2。
一度4ビット分ずつの16進数に直すと判り易いかもしれません。1111 は 8*1 + 4*1 + 2*1 + 1*1 となり 16進数で F , 10進数で15、同様に 0110 は 8*0 + 4*1 + 2*1 + 1*0 となり
16進数で 6、つまり 2進数で1111 0110 は16進数で F6となります。これは 15*16 + 6 となり、答えは10進数で246。

この辺の仕組みが判ってくれば、256ビット幅や512ビット幅の数値といった汎用レジスタのビット幅を超えるような数値の演算コードが書けるようになるかもしれません。
とはいえ、ソフトウェアレベルでの代替処理はハードウェアレベルで備わっているのに比べ高速さを求めるような場面では不利。かつて、「除算が遅い」の補足 (1)でソフトウェアレベルでの除算を代行するので遅くなる件を取り上げました。
32ビット版の OS において、途中結果が汎用レジスタの幅に収まらない ( 64ビット幅の整数など ) 場合は、割り算命令に相当する関数を呼出す ( ソフトウェアレベルでの代替 ) ので遅くなる。
同じ計算式のまま64ビット版の OS 上で64ビット版向けアプリとしてビルドすれば、整数の除算部は汎用レジスタを用いた命令に翻訳される、つまり、ハードウェアレベルでの処理が選択される。実行速度を低下させる原因を取り除ける。
32ビット整数値はおおよそプラスマイナス21億、64ビット幅の整数はさらにその42億倍。実際のところ、一般的な PC で必要とされる整数の範囲として不足はない。それでも足りないような高度な演算が必要なのであれば、ソフトウェアレベルでの高速化についてあれこれ調べ巡るよりも、高度な演算に特化した機材を調達することを考えた方が良いだろう・・・

さてさて、SSE4.2に至るまで整数の除算命令が追加されなかった、というよりも見送られてしまった謎が解けそうだ。
Pentium 4 でも 西暦2004年頃リリースされた、通称 Prescott と呼ばれる第三世代より SSE3 の命令が実行可能になった。それと同時に、64ビット環境への対応が施され、つまり、64ビット版のOS やアプリを実行できる仕組みが追加された。
64ビット環境が普及すればハードウェアレベルでの演算に切り替わることにより遅い部分が解消できる。64ビット版で汎用レジスタで扱える。そのほかにもXMM レジスタで 整数の除算命令を行えるような改良・追加も可能だったと推測できる。しかし、その分回路は複雑になり、さらに多くの電力を消費するような構造になる。



当時、Pentium 4 シリーズで消費電力の高さ、言い換えれば、燃費の悪さが問題視されていた。発表されたモデルのうち燃費の悪さ等が重り、出荷されなかったモデルもある。この辺を振り返ってみれば、追加できそうな機能のうちいくつかが省かれてしまったのもいたしかたない。

ではでは、32ビット環境において整数の除算を高速化しようと考えないほうが良い!?!?!?
いえいえ。少し発想を転換すれば道が見つかるかも。ヒントを挙げるとすれば、XMM レジスタで倍精度度浮動小数点値と 32 ビット整数値、もしくはその逆の変換が可能な点・・・

長くなりましたので今回はこの辺で・・・

本日も最後までご覧いただきありがとうございます。

「つまらなかった」「判り辛った」という方もご遠慮なくコメント欄へどうぞ

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

検索サイトからお越しの方へ
検索サイトからお越しの方は、ブラウザのアドレス欄vitalaboloveおよび、fc2.comが含まれているかご確認ください。
含まれていない場合、偽サイトを閲覧なされている可能性があります。

偽サイトは、当ブログの文字部分や画像部分が有害サイトへのバナーと置き換わっているようです。
プロフィール

Author:Vitalabolove
ご訪問ありがとうございます。
店長を任されておりますVitalaboloveです。

コメントはお気軽に。
今のところリンクフリーですが、あと数日でとりやめます。

画像データ、文言の引用は事前連絡くださるようお願い申し上げます。事前連絡の際は、左下、メールフォームを経由をご利用ください。

最新記事
カレンダー
09 | 2017/10 | 11
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -
カテゴリ
ランキング
いつも応援いただきありがとうございました。ただいま休養中につきランキングへ参加していません・・・

フリーエリア
内緒話などはおきてがみをご利用ください。
月別アーカイブ
メールフォーム
掲載された記事について、ご不明な点はここからお問い合わせください

名前:
メール:
件名:
本文:

最新コメント
最新トラックバック
スパムと思われるトラックバックは削除しました
QRコード
QR
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。