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

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


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



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

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

スポンサーサイト

上記の広告は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 ビット整数値、もしくはその逆の変換が可能な点・・・

長くなりましたので今回はこの辺で・・・
スポンサーサイト

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

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

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

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

「除算が遅い」の補足 (4)「除算が遅い」の補足 (5)でお手軽に新しく追加された機能を活かすアプリを作る方法を述べた。全てお任せでは物足りないこともある。そこで、前話にて
高速化したい箇所のみ新機能を活かすようなソースコードに書き換えることにより、さらに高速化が狙えるのでは!?!?!?
を触れた。通常アプリを作成すると、新機能が備わっていない PC ( 1990年代中頃の PC ) でも 動く機械語コードが生成される。



生成されたのは fdiv など FPU ( 浮動小数点演算処理装置 ) を介して演算するようなコード。これを、明示的に 新機能を使うように書き換え、さらなる高速化を狙う。



divpd が2命令続いている。divpd 命令ひとつにつき2組の除算を同時に行うことを意味する。
並列、つまり、同時に複数の作業を進めるようなコードが生成される・・・


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


前話の続きとして、整数の除算の話に移りたいところであるが、後に回したい。

先に述べた、
並列実行されるようなコードが生成された・・・ゆえに、高速化されるハズ・・・と安堵できないケースもある。

実生活の場でも、命令を出す側、受ける側の想いが異なることは多々ある。受けた側がどのような手順で遂行するかを気にするよりも、オーダーされた通りの結果が出たかが大事。

前話で、
2組分の除算を行える~~~待ち時間はほぼ一緒。~~~※ 一部のCPUを除く。
という表現を用いた。「一部のCPU」と記しただけでは曖昧なので、実際を挙げます。
かつて、モバイル向けに開発された CPU の中に同時に2組分の処理を行わないモノがリリースされていました。
筆者はかつて、モバイル向け ( ノートPC 向け ) にリリースされていた Pentium M というCPU をデスクトップ PC として使っていました・・・



ひとくちにモバイル向け CPU と書くと紛らわしいので補足。
デスクトップ用の Pentium iii や Pentium 4 を基にノートパソコン向けにチューニングされた CPU もリリースされていました。それらは、Pentium III-M や Mobile Pentium 4 processor や Pentium 4-M と呼ばれていました。これら Pentium III-M や Pentium 4-M がデスクトップ用 CPU を基にノートパソコンで特化させたモノ。

画像で載せたのは、通称 Dothan と呼ばれる Pentium M。こちらはもともと、開発段階からモバイル用途を意識していた、というよりもモバイル専用としてリリースする予定だった。ところが、リリース後、高性能さが受け、やがてこれをデスクトップ用としても使えるように対応マザーボードが出荷されるに至った。
「なぜ、わざわざモバイル向けの CPU をデスクトップ用に???」と不思議に感じるヒトもいることだろう。理由としては、低発熱のモバイル向け CPU は静音化や小型化の面で有利だったから。
同世代の デスクトップ用として流通していた CPU は Pentium 4。



Pentium 4 は消費電力が高いとされ、ひと世代前の Pentium iii と比べ 2 ~ 3倍強。その分、発熱量も増大する。Pentium 4 で消費電力が増大してしまったというよりも、それと引き換えに高速な CPU を投入せざるをえなかった。Pentium 4 が登場した背景を考えると仕方のないことであるが、ひと世代前のPentium iii が全盛の頃、ライバル ( 互換品メーカー ) との間で高クロック競争となり、やがて追い抜かれてしまった。Pentium iii の動作クロックを向上させることも検討されたようだが、限界があり、ある程度の高さから動作不良を起こす。そこで、巻き返しを狙い、燃費が悪くてもライバル製品に対抗できる CPU をとして Pentium 4 がリリースされるに至った。
PC を 自作する者にとって、よりワット数が高い電源ユニットや、発熱対策としてより強力な冷却ファンを用意する必要があった。つまり、静音化や小型化とはかけ離れていった・・・

Pentium 4 が表舞台を賑わせている頃、その裏で Pentium M の開発が行われていました。ひと世代前の Pentium iii に磨きをかけ、Pentium 4 で見過ごされた消費電力を最小に抑えるための工夫も盛り込まれました。それはその後に登場する Core 2 Duo / Quad や Core i7 の礎となってゆきました・・・



Pentium M は Pentium 4 と比べ省電力であるほか、クロックあたりの性能が高く、同じ動作クロックであれば 1.5倍ほど高速といわれていました。しばしば、Pentium M の2GHz、Pentium 4 の2.8 GHz がほぼ互角との記載を見かけます。実際に両者を使っていた上で書くと、Pentium M を搭載したデスクトップ PC の方が静かで迅速と感じたものです・・・

そろそろ、除算のお話に移りましょう。
Pentium M は2組分の演算を同時に行えず、2回に分けて処理していたような感がありました。
「除算を2回行う」と「ひとつの命令で同時に2組の除算」の待ち時間がほぼいっしょ。
※ この記事をアップする際にあたり、手元に残っていた過去に計測した数値も確認しました。

それではかえって遅くなるのでは!?!?!?と誤解が生じるかもしれないので補足。
Pentium M は Pentium 4 と比べ除算の待ち時間が大幅に短縮されています。概ね半分か30%くらい。このことから、本来一度に行う作業を2度に分けて作業しても、既存の CPU と大差無い ( 遅くはならない ) と判断したのでしょう。
たしかに、実行ユニットを多く搭載すれば、同時に複数こなせます。反面、消費電力が増えてしまいます。モバイル専用に省電力な製品として開発を進める以上、実行ユニットを増やさなかったと想像できます・・・
※ Pentium M の後発にあたるCore 2 Duo / Quad や Core i7 では並列に実行されるように改良されています。

新機能を使うようなコードでもそうでないコードで書いても、結果がほぼ同じ。
新機能の命令を受け入れる・理解することはできるが、内部での実行手順が今までと異なる。期待したほど高速化されない環境もあるということだ・・・

ほかにも、似た例として、Core 2 Duo / Quad と 64ビット命令を実行した際の状況が挙げられる。中には32ビット時より落ちてしまうといった記述も見掛けるが、64ビット環境下では本来の実力を発揮できないと表現したほうが近い。
その理由としては、Core 2 Duo / Quad は 32ビット版 CPU としての動作に向けて高度な最適化が加えられていたのに比べ、64ビット版命令対応を急いで加えた感がある。とりあえず動くことが優先されたのだろう。もっとも、Core 2 Duo / Quad が登場したての頃、64ビット版アプリはほとんど無かった。

これを書いていた時点でPC に搭載されている CPU は Core i7 ( Ivy bridge )。Ivy bridge の ひと世代前の CPU ( Sandy bridge ) から Intel AVX 命令が実行できるように拡張された。AVX 命令は256ビット幅の YMM レジスタを扱うことがでる。が、Sandy bridge や Ivy bridge では128ビット分ずつ2回に分けて処理している。これも新機能の命令を受け入れることはできるが実行手順は最適化されていない例。そのため、性能をフルに発揮できない。ちなみに、次世代の Haswell ではこの辺が改良され1回で処理できるとアナウンスされています。

ということで、高速化したい部分を新機能を活かすコードへの書き換えるのはひとつの策です。しかし、将来、ハードウェアレベルで改善されるかもしれません。こまめにハードウェアの先行情報、ロードマップをチェックすることで、その書き換え作業が無駄にならないかの判断材料になることでしょう・・・

C/C++ 言語等を用いたアプリを作るとして、全てのヒトが実行環境の特徴を意識する必要はありません。手の込んだコードや特定の機材や環境に絞ったコードに書き換えてしまうと、汎用性が損われます。
Windows 以外の OS や、違うCPU を搭載したマシンといった異なる環境への移植を考えた場合、足かせとなります。かつての作品のこの部分や考え方を他で活用したくなることは多々あります。その際、機種依存で書いた部分は壁となります。
移植する先にその機能が備わっていない場合、ソフトウェアレベルで補うようなルーティン ( 関数 ) を新たに設けるなど面倒が増えます。
逆に、特定の機材と環境に絞れる状況かつ移植も考えないのであれば、C/C++ 言語等ではなく機械語で書いてしまうのが良いでしょう・・・

そろそろ、整数の除算の話に入りたいところですが、
長くなりましたので今回はこの辺で・・・

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

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

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

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

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

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

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

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

最新記事
カレンダー
10 | 2015/11 | 12
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 - - - - -
カテゴリ
ランキング
いつも応援いただきありがとうございました。ただいま休養中につきランキングへ参加していません・・・

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

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

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