Ershov-Zahl – ウィキペディア

エルショフ・ザレン レジスタを割り当てるときは、コンピューターサイエンスの分野で必要です。彼らは、登録登録手順のアイデアを発表したロシアのコンピューター科学者のアンドレイ・ペトロウィッシュ・ジャルショーにちなんで名付けられました。この手順は、水文学者のロバート・エルマー・ホートンとアーサー・ニューウェルのスポットライトにさかのぼり、川の空間の川の数を計算する手順を開発しました。 Jerschowによると、この手順は、印刷するために必要なレジスタの数を決定することもできます

${displaystyle a}$

評価し、したがって、できるだけ少ないレジスタで大きな式の評価を可能にします。

バイナリツリーのershov数は次のように計算されます。

1. 各シートには値があります
   ${displaystyle ershov（a）= 1}$

   （定数または変数）。

2. 1つの下位ノードのみのすべての結び目は、下位ノード（Unare Operators）と同じ値を持っています。
3. 他の結び目に適用されます

${displaystyle ershov（a_ {1} circ a_ {2}）= {begin {cases} max（ershov（a_ {1}）、ershov（a_ {1}）neq ershov（a_ {2}）\ {1 1}）= ershov（a_ {2}）end {case}}}$

プロセスは、フォームの関数を指定します。

${displaystyle ershov：endruckrightarrow mathbb {n}}$

与えられた算術式

${displaystyle a}$

評価に必要なレジスタの数が示されています。
これには症例の違いが必要です。

変数と定数 [ 編集 | ソーステキストを編集します ]

変数または定数を評価するには、正確に1つのレジスタが必要です。によると：

${displaystyle ershov（v）= 1}$

非警戒リンク [ 編集 | ソーステキストを編集します ]

非武装のオペレーターを評価します

${displaystyle alpha}$

表現について

${displaystyle a}$

レジスタの数のみが必要な場合、それは

${displaystyle a}$

結果の登録が必要です

${displaystyle a}$

単純に上書きすることができます。

${displaystyle ershov（alpha〜a）= ershov（a）}$

バイナリリンク [ 編集 | ソーステキストを編集します ]

フォームの2つの式間のバイナリリンクを評価するとき

${displaystyle a_ {1} circ a_ {2}}$

まだ際立つような3つのケースがあります。

fall I：ershov（a _初め ）2 ）） [ 編集 | ソーステキストを編集します ]

想定された、

${displaystyle a_ {1}}$

最初に評価された場合、結果はレジスタになり、それでも

${displaystyle ershov（a_ {2}）}$

さらに登録する必要があります

${displaystyle a_ {2}}$

評価します。全体的に、そうでしょう

${displaystyle ershov（a_ {2}）+1}$

必要な登録

${displaystyle ershov（a_ {1} circ a_ {2}）}$

評価します。

代わりに

${displaystyle a_ {2}}$

最初に評価されたので、正確にのみです

${displaystyle ershov（a_ {2}）}$

必要な登録

${displaystyle ershov（a_ {1} circ a_ {2}）}$

評価。結果として

${displaystyle a_ {2}}$

追加の登録簿にありますが、他のすべてのレジスタはの評価のために戻ってきました

${displaystyle a_ {1}}$

この1つの結果に加えて、利用可能な理由

${displaystyle ershov（a_ {1}）}$

さらなるレジスタが必要です。そこには

${displaystyle ershov（a_ {1}）}$

より小さい

${displaystyle ershov（a_ {2}）}$

すぎます

${displaystyle ershov（a_ {1}）+1}$

小さいまたは等しい

${displaystyle ershov（a_ {2}）}$

これは明らかにより小さいです

${displaystyle ershov（a_ {2}）+1}$

。

によると：

${displaystyle ershov（a_ {1}）$

秋II：ershov（a _初め ）= ershov（a ₂ ）） [ 編集 | ソーステキストを編集します ]

どちらの式でも同じ数のレジスタが必要なため、どの式が最初に評価されるかは関係ありません。したがって、式は最初に模範的である可能性があります

${displaystyle a_ {1}}$

のために評価されます

${displaystyle ershov（a_ {1}）}$

登録が必要です。評価後、結果は結果の登録になり、

${displaystyle ershov（a_ {1}）-1}$

今すぐ登録してください

${displaystyle a_ {2}}$

利用可能。式の評価以来

${displaystyle ershov（a_ {1}）}$

また

${displaystyle ershov（a_ {2}）}$

の結果の結果のための登録に加えて、登録ニーズ

${displaystyle a_ {1}}$

、 まだ

${displaystyle ershov（a_ {2}）}$

さらなるレジスタ、つまり全体的に

${displaystyle ershov（a_ {2}）+1}$

の評価に登録します

${displaystyle ershov（a_ {1} circ a_ {2}）}$

必要です。

によると：

${displaystyle ershov（a_ {1}）= ershov（a_ {2}）rightarrow ershov（a_ {1} circ a_ {2}）= ershov（a_ {1}）+1}$

[ ershov（a2） “>編集 | ershov（a2） “>ソーステキストを編集する ]

議論はケースIに類似しています：

${displaystyle ershov（a_ {1}）> ershov（a_ {2}）rightarrow ershov（a_ {1} circ a_ {2}）= ershov（a_ {1}）}$

${displaystyle f（a_ {1}、…、a_ {n}）}$

スタックに記述するには、結果をレジスタに保存する必要はありません。
バイナリ式の場合の場合と同じ引数から次のようになります。

${displaystyle ershov（f（a_ {1}、…、a_ {n}））= max（ershov（a_ {1}）、…、ershov（a_ {n}）}）}}$

ただし、議論が特定のレジスタに引き渡されるコールコンベンションもあり、関数の速度を改善できます。
ここでは、登録簿に2つの引数を持つ機能的呼び出しの特別なケースであるバイナリ演算子に関しては、可能な限り多くのレジスタが利用可能になるように、最も多くのエルショフとの引数が最初に計算されます。すべての引数をレジスタで書く必要があるため、関数呼び出しのershov数は、レジスタの引数の数と同じくらい大きいです。

${displaystyle Minimum = max（ershov（a_ {1}）、…、ershov（a_ {n}）、＃argumenteinregistern）}$

エルショフ数が複数の引数でこの最小値に等しい場合、機能的な呼び出しのエルショフ数がさらに1つのそのような議論によって増加することをバイナリ演算子にも同様に適用します。

${displaystyle inkrement =＃{a_ {k} | ershov（a_ {k}）=最小}}}$

${displaystyle ershov（f（a_ {1}、…、a_ {n}））= {begin {case} inkrement> 1＆minimum+inkrement-1 \ inkrement <2＆minimum \ end {case}}}}$

ただし、最初の5つの引数のみがレジスタに引き渡され、残りはスタックに配置されます。次に、最初に最後の引数を計算してスタックに置いて、すべてのレジスタを最初の引数の計算に使用できるようにすることは理にかなっています。レジスタの引数は任意の順序で計算できますが、スタック上の引数は論理的な順序である必要があります。

Ravi SethiとJeffrey Ullmanにちなんで名付けられたSethi-ullmanアルゴリズムは、抽象的な構文ツリーをマシンコードなどのレジストリマシンのコマンドに変換します。 ^[初め] アルゴリズムは基本的にERSHOV数を計算するのと同じですが、実際のレジスタマシンのコマンドのプロパティを考慮しています。 x86プロセッサのコマンドレートにより、メモリ内の定数と値を引数として直接使用できます。ただし、すべての組み合わせが許可されているわけではありません。許可されています：

 追加  dword  [  a  ]、、  0x1337  ;定数は、RAMの変数に直接追加できます。   追加  EAX 、  0x2342  ;定数はレジスタに直接追加できます。   米  EAX 、  dword  [  a  ]   追加  dword  [  b  ]、、  EAX  ;登録は変数に直接追加できます。   追加  EAX 、  dword  [  c  ]  ;変数はレジスタに直接追加できます。  

エルショフ数の計算 [ 編集 | ソーステキストを編集します ]

エルショフ数の計算は、コマンドによって異なります。最も単純な場合、コマンドレートはレジスタを使用した操作のみを許可します。これは、レジスタと定数にのみロードする必要があります。この場合、すべての葉はエルショフの数です

${displaystyle ershov（a）= 1}$

割り当て。コマンドが変数と定数を使用して操作を許可する場合、コマンドレートが2操作された形式または3操作された形式のコマンドのみを許可するかどうかについて区別する必要があります。

2オペレーター形式では、結果は最初のオペランドのレジスタに保存されます。例としては、X86プロセッサに追加されています。

 米  EAX 、  a   追加  EAX 、  b  ; EAX + B→EAX。 EAXは、結果の登録と同様にオペランドでもあります。  

この場合、抽象的構文ツリーの右シートは値になります

${displaystyle ershov（r）= 0}$

割り当てられ、左シートが値になります

${displaystyle ershov（l）= 1}$

。例ではです b 適切なオペランド、レジスタに招待する必要はありません。 a 左オペランド。これは最初に登録簿に含まれている必要があります EAX そのようにロードされます

${displaystyle a+b}$

計算およびin EAX 保存できます。

3オペレーターフォームでは、最初のオペランドは結果レジスタです。

 追加  R1 、  a 、  b  ; A + B→R1。  

この場合、抽象的構文ツリーの各シートは値です

${displaystyle ershov（a）= 0}$

割り当て。

ただし、計算のこのプレゼンテーションは理想化されています。たとえば、実際のプロセッサが許可されています。

• 直接演算子としての定数のみですが、変数はありません。
• たとえば、それらが限られた価値領域にある場合にのみオペランドとして一定
  ${displaystyle [-128,127]}$

  、 横たわっている。それ以外の場合は、定数をレジスタに招待する必要があります。これにより、必要なレジスタの数、したがってershov数が増加します。

• 一部のコマンドの場合、3階級のフォームがあり、他の人の場合は2オペレーター形式のみです。
• 3操作されたフォームですが、2番目のオペランドは一定ではなく、変数ではありません。この場合、3オペレーターのフォームは2オペレーター形式のように動作します。

コードの作成 [ 編集 | ソーステキストを編集します ]

その後、ツリーは副次的な順序で横断され、エルショフの数が最も多いものとなります。アンダーコートが代わりに最も少ない数のエルショフで評価された場合、結果はレジスタに保存する必要があります。これは、他のアンダーコートを計算するために使用できなくなりました。限られた数のレジスタの場合、ツリーの計算に十分なレジスタが利用できないという状況が必然的に発生します。ツリーを計算するために必要なレジスタの数は、両方のサブツリーが同じエルショフ数を持っている場合、または両方の地下木が同じ数を必要とする場合、サブツリーの必要なレジスタの数よりも大きいです。次に、使用可能なタブの限界を超え、サブツリーの中間結果は、たとえばスタックまたは レッドゾーン 、によって保存されます

1. 最初に適切な地下を評価しました、
2. 中間結果を保存するためにコマンドを挿入し、
3. 次に、左ベースツリーを評価しました。
4. 中間結果を充電するためにコマンドを挿入しました
5. 最後に、2つのサブツリーをリンクするコマンドが挿入されます。

順序は実際には無関係ですが、操作が右の演算子としてメモリ内の値を許可する場合、右を評価し、次に左ベースツリーを評価することは利点になる可能性があります。その後、最後の2つのステップを要約できます。

1. ↑ セティ・ラビ、ジェフリー・D・ウルマン： 算術式の最適なコードの生成 。の： Journal of the Association for Computing Machinery 。 バンド 17 、 いいえ。 4 、1970年、 S. 715–728 、doi： 10.1145/321607.321620 。