小規模ながら非常に興味深い戦術演習を行う機会を得ました
Cortex-M4アーキテクチャに基づいた有名企業の新しいMKを調査する過程で（これについては後ほど確実に説明します）、ハードウェア実装での整数除算操作がどれほど速く機能するかという疑問が生じました。 実物大の実験では、やや予想外の結果が得られました。32ビットの数値を32ビットの数値に分割すると、プロセッサ周波数の3クロックサイクルにわたって実行されます。 これは特定のオペランドでのみ行われることが判明しましたが、さらなる研究により、除算時間が7サイクルを超えないことが示されています。 得られた結果は、わずかな急ぎを引き起こしました（「これは、それが何を意味するのかわからない特定のスピーチの数字ではなく、非常に特定の動詞です」-いつものように、Divovは比較できません）。
さて、あなたはそのような長い数字を取り、すぐに分割することはできません、それはそのような奇妙なことですが、事実は頑固なものです。 私はロシア連邦大統領が明日私に彼を呼んでいて、MKをARMのそれより悪くならないようにする仕事を設定しているという写真を想像しました（写真は妄想ですが、世界では起こりません）が、私は彼を混乱させて理解しています私はそのような数でこのような数の分割をすることができず、私に課せられた期待に応えることができません（実際、ARMからライセンスをいつでも静かに購入し、自分ですべてを発明したふりをすることができますが、 GDPは私とはまったく異なるものを期待しています。そして、私はそれを欺くことができますが、そうは思わないでしょう。
そして、ARMの人たちが私よりもはるかに頭がいいことを悲しくなりました。そして、私は彼らがそれをどのように行うかをインターネットで待ち望んで見ました。 ARMのWebサイトで実行時間に関する情報を見つけることができませんでした。STM32の資料の1つでは、分割に2〜7クロックサイクルかかることが示されましたが、これは観測に対応しますが、これがどのように行われるかに関する情報はありません。
一般に、全能のインターネットはあまり役に立たず、一定の除算のコツがあります、私はそれらの記事の1つでそれらについて書きましたが、私たちは異なる状況を持っています、ニュートンのアルゴリズムとその加速版がありますが、これは明らかにそうではありません、に基づいたアルゴリズムがありますフーリエ変換。ただし、これは非常に大きな数値用であり、ARMアーキテクチャでも7サイクルで完了することはほとんどありません。 私は自分でそれを考え出さなければならず、解決策が見つかったので、タスクが定式化された直後にこれが行われなかったという事実からやや恥ずかしくなるほど簡単で明白です。
私の解決策を見る前に、自分の解決策を見つけて、自分の解決策と比較することをお勧めします。異なる場合は、コメントでお待ちしています。
したがって、32ビットの結果を得るために、2つの32ビット数値を（7サイクル以内で）すばやく分割するにはどうすればよいでしょうか。
まず、バイナリ算術の除算が一般的にどのように実行されるかを思い出してください。
古典的な形。 アルゴリズムは非常にシンプルで簡単です-被除数から除数を引きます。 結果が負でない場合（符号なしの数値を除算する場合）、結果の次の数字を1に等しくし、結果を次の被除数と見なします。それ以外の場合、結果の次のビットは0です。次のメジャーの前に、除数を半分にします（右にシフトするか、配当を左にシフトします）、ビットウェイトを2倍減らします（同様のシフトにより）。 したがって、1クロックサイクルで1ビットの結果が得られ、全体の操作は32クロックサイクル続きます。 このプロセスにはまだ初期のシフトがありますが、状況全体の評価には影響しません。 加速しますが、どうやって？
結果として生じるアルゴリズムは、逐次近似によるADCの動作に非常に似ていることに注意し、他の変換方法、はるかに高速な並列変換があることを思い出してください。 もしも...
除数だけでなく、配当* 2と配当* 3（同時に、3つの加算器）を除数から減算し、情報の3ビット（結果の符号）を取得します。これは、4つの異なる値を取ります。結果。 次に、結果の3.4.5ビットに対して同様のアプローチを外挿します。
1サイクルで5ビットの情報を取得するには、31の加算器が必要です。各加算器でDividend-Divisor * n演算（1-31）が実行され、結果の符号がエンコーダーを通過し、すぐに5ビットの結果を受け取ります。 次に、配当を5桁左にシフトし、準備が整うまで繰り返します。 次に、操作を完了するために32/5 = 6.4 => 7メジャーが必要です。
仕事のために、31 + xの加算器が必要です、それはたくさんあるように見えますが、サイクルごとに32 * 32の乗算演算があるため、すでにあります。それを実装するには、32の加算器なしではできません（そうですね... ）、すでに必要な機器を持っているので、唯一の問題は、高速シフトを実現するための制御回路とマルチプレクサのヒープを構築することですが、これは完全に解決可能です。
したがって、7つのステップに分割するタスクは解決されましたが、疑問が残ります-研究されたMCでは7未満であるため、この時間をどのように減らすことができますか？商の上位ビットの数がゼロに等しいことがすぐに明らかになるため、アルゴリズムの最初のフェーズまたはいくつかのフェーズをスキップできます。 たとえば、C <3の場合、結果はすぐにゼロになり、操作を完了します。確かに、メジャーの数の式を導出できますが、私はすでに退屈していました。
興味深いことに、残りの部分は明らかに内部のどこかに残っていますが、udiv操作は商のみを提供します。 原則として、疑似コードDivisible-Private * Dividerを実行することにより、マシンコードの調査済みのフラグメントで行われた2つのステップで簡単に取得できますが、これは任意の2つのステップのため、レジスタペアですぐにそれを与えないでください-これに対する答えがわからない質問。
一般的には、GDPを満たし、それが彼にとってまだ興味深い場合は、MKでの分割を間違いなく行うことを伝えます。
PS：ところで、私がKDPVを探していたとき（気づいたように、私はそれを見つけませんでした）、「0で割ってはいけません」というはっきりと間違った碑文を持つものに気付きました。 ゼロで除算することは可能であり、除算することは不可能であると断言しなければなりません。 しかし、真剣に、異なるアーキテクチャではゼロで異なる除算が行われ、x86では例外が発生します（これは忘れられない間違い200です）、いくつかでは配当やゼロが得られますが、最大の整数を見たことはありません。 ARM n / 0 = 0/0では、0になります。