使用n位乘加操作實現不變量除數的整數除法的方法和系統的製作方法
2023-05-30 10:15:41
專利名稱：使用n位乘加操作實現不變量除數的整數除法的方法和系統的製作方法
技術領域：
本發明的實施例涉及軟體程序的編譯和執行。更具體地，本發明的實施例涉及使用在除數的倒數近似值中具有最小捨入誤差的N位乘加(multiply-add)操作來實現不變量除數(invariant divisor)(例如，編譯時常量或運行時不變量)的整數除法的方法和系統。
背景技術：
處理器上的整數除法通常比乘法代價更高。通常，整數除法與其它運算操作相比相對較少。因為該原因且因為直接在處理器內部以硬體實現除法的複雜性，所以在現代處理器體系結構隨之而來的趨勢是略去對整數除法的直接硬體支持，而代之以依賴於軟體實現。
以軟體實現整數除法需要特別引起注意的情況發生在除數是編譯時常量、或運行時循環不變量時。現有的研究和發展顯示在這種情況下，無符號整數除法x/d可以以(ax+b)/2s來計算，其中a是除數的換算的(scaled)倒數近似值，b是對於捨入誤差的補償，而s是右移計數。通過使用倒數近似值，整數除法可以作為乘加操作、以及隨後的右移操作來實現。
在這種情況下，必須謹慎選擇或確定除數的倒數。如果沒有謹慎選擇倒數近似值，所得到的商經常遭受差一錯誤(off-by-one error)。為了確定倒數的值，近似值a可以從精確的換算的倒數向上捨入或向下捨入。但是，為了執行N位除法，基於公式(ax+b)/2s的所有現有實現都要求在最壞的情況下，近似值a被捨入為N+1個有效位。超出N位的額外位使得該乘加操作成為N+1位乘加操作。
現有的實現受到對於N+1位乘法的要求。這是因為處理器天生就只實現N位運算。因此，N+1位乘法必須通過N位乘法和附加的運算操作來合成，這為整數除法增加了額外的處理操作。對於一些除數(例如，倒數近似值以「0」結束)，因為額外位是0，所以可以將其優化去除；或者對偶數除數，被除數可以預先移一位，以將該問題降低為N-1位除數的除法操作。但是，這並不總是可行的，尤其對於循環不變量除數，其中循環體內的代碼必須處理最壞的情況，即除數是奇數且倒數近似值以「1」結束的情況。
因此，需要一種使用在除數的倒數近似值中具有最小捨入誤差的N位乘加操作來實現不變量除數(例如，編譯時常量或運行時不變量)的整數除法的方法和系統。
通過實例說明了本發明實施例的特性和優點，且本發明實施例的範圍並不限於所示的特定實施例。
圖1示出實現本發明的一個實施例的整數除法系統的結構，其中該整數除法系統包括預計算模塊和指令生成模塊。
圖2示出根據本發明的一個實施例的圖1的整數除法系統的編譯器實現。
圖3示出根據本發明的另一個實施例的包括即時(just-in-time)編譯器的運行時環境，其中該即時編譯器包括圖1的整數除法系統。
圖4是一個流程圖，示出圖1的預計算模塊所執行的一般預計算處理，用於計算除數的倒數近似值和捨入誤差補償值。
圖5是一個流程圖，示出圖1的預計算模塊的一個特定預計算處理，其中該處理是針對N位無符號除法並使用整數運算。
圖6是一個流程圖，示出圖1的預計算模塊的另一個特定預計算處理，其中該處理是針對無符號除數的N位有符號除法並使用整數運算。
圖7是一個流程圖，示出圖1的預計算模塊的另一個特定預計算處理，其中該處理是針對N位無符號除法並使用浮點數運算。
圖8是一個流程圖，示出圖1的預計算模塊的另一個特定預計算處理，其中該處理是針對無符號除數的N位有符號除法並使用浮點數運算。
具體實施例方式
圖1示出使用在除數的倒數近似值中具有最小捨入誤差的N位乘加操作，實現常量或不變量除數(例如，編譯時常量或運行時不變量)d的整數除法的整數除法系統10。根據本發明的一個實施例，整數除法系統10檢查除數d以確定將其倒數向上捨入還是向下捨入到N位。這使得整數除法系統10能夠避免合成N+1位運算的額外操作，因此將除法減少到N位(較高的或較低的)乘加操作、以及隨後的右移操作。
從圖1可以看出，整數除法系統10包括預計算模塊11和指令生成模塊12。預計算模塊11用於選擇除數d的倒數近似值a和對於倒數近似值a的捨入誤差補償值b。指令生成模塊12用於生成乘加指令和右移指令，所述指令用於使用倒數近似值a、捨入誤差補償值b和移位計數m來計算除法的商。
如下面更詳細描述的、並根據本發明的一個實施例，預計算模塊11確定應當使用向上捨入還是向下捨入來選擇倒數近似值a和鹹捨入誤差補償值b。預計算模塊11還計算移位計數m。預計算模塊11使用整數運算或者浮點數運算來計算該確定。這裡，術語「向上捨入」和「向下捨入」指的是向上或向下將倒數近似值a從N+1位捨入到N位，並確定捨入誤差補償值b。例如，向上捨入可以指倒數近似值a被設為1/d的前N位加上1，而向下捨入可以指倒數近似值a被設為1/d的前N位。對於無符號除數的有符號除法，向上捨入和向下捨入可以分別指朝著正無窮方向捨入和朝著負無窮方向捨入。這裡，前N位指從最左邊的1開始的N個最高有效位。
進行捨入確定所用的測試依賴於整數除法是有符號還是無符號的、以及確定向上捨入或向下捨入時所使用的是整數運算還是浮點數運算。對無符號整數除法使用整數運算，預計算模塊11使用下面的測試來確定將倒數近似值a向上捨入還是向下捨入(td+d)mod2N≤2m其中t＝floor((2m+N)/d)且m＝floor(log2(d))。值m指示非隱式的(non-implicit)右移計數的量。符號floor(x)表示不超過x的最大整數。這裡，除非除數d等於2m(即，除數是2的冪)，否則適用該測試。如果測試結果是真，則預計算模塊11將倒數近似值a向上捨入(即，a＝t+1)，並且捨入誤差補償值b被設為0。如果測試結果是假，則預計算模塊11將倒數近似值a向下捨入(即，a＝t)，並且捨入誤差補償值b可以被選為a。
使用整數運算並對於無符號除數的有符號整數除法，預計算模塊11使用下面的測試來確定將倒數近似值a向上捨入(即，朝著正無窮方向)還是向下捨入(即，朝著負無窮方向)(td+d)mod 2N≤XMA.HU(d，t，0)其中t＝floor((2m+N)/d)且m＝floor(log2(d))，而XMA.HU(d，t，0)表示提供dt+0的高N位的合併(fused)乘加操作。這裡，除非除數d等於2m，否則適用該測試。如果測試結果是真，則預計算模塊11將倒數近似值a向上捨入(即，a＝t+1)。如果測試結果非真，則預計算模塊11將倒數近似值a向下捨入(即，a＝t)。捨入誤差補償值b在向上捨入和向下捨入兩種情況下都可以被選為t/2。
使用浮點數運算，預計算模塊11使用下面的公式來計算倒數近似值aa＝SIGNIFICAND(t)其中t＝RNDN(1/d)。這裡RNDN指將1/d的值捨入到最近的N個有效位(除非d＝2N-1)。如果d＝2N-1，則捨入到最近的N個有效位或向下捨入到2-N都是可以接受的。SIGNIFICAND(x)指x的浮點數表示的N個最高有效位。
對於捨入誤差補償值b，預計算模塊11需要確定應當使用向上捨入還是向下捨入來計算該值。對於使用浮點數運算的無符號整數除法，預計算模塊11採用下面的測試來作出確定RNDN(-dt+1)≤0其中m＝(BIAS-1)-EXPONENT(t)。RNDN暗示應當作為只有最後捨入而沒有中間捨入的合併負數乘加來進行該計算。BIAS表示浮點數表示中的典型偏倚(bias)，而EXPONENT表示有偏的浮點數指數(即，值x值在浮點數中被表示為SIGNIFICAND(x)*2(EXPONENT(x)-BIAS-N+1)。如果測試結果是真，則預計算模塊11選擇捨入誤差補償值b等於0(因為該測試指示發生了向上捨入)。否則，值b可以被設為a(因為該測試指示發生了向下捨入)。對於無符號除數的有符號除法，捨入誤差補償值b在向上捨入和向下捨入的情況下都可以被簡單地設為t/2(即，不需要進行該確定)。結合圖1-8，將在下面詳細描述整數除法系統10。
再次參考圖1，整數除法系統10可以通過軟體或固件實現。對於使用整數運算的計算，整數除法系統10的硬體體系結構支持包括支持表示為XMA.HU的N位整數合併乘加指令的處理器。這一指令的執行提供或返回計算(ax+b)的較高的(或高的)N位。可選地，表示為XMA.LU的整數合併乘加指令可以用於提供或返回計算(ax+b)的較低的N位。
這裡，術語「合併」指乘法和加法運算操作被作為單一操作來完成，該單一操作內部以2N位精度來計算，但是只提供較高的(或較低的)N位。對於N位無符號整數a、x和b，上述指令可以被更正規地定義為XMA.HU(a，x，b)＝(ax+b)/2NXMA.LU(a，x，b)＝(ax+b)mod 2N在一個實施例中，N位處理器是64位處理器。可選地，該處理器可以具有不同長度。例如，N位處理器可以是32位處理器或128位處理器。
在沒有乘加指令的處理器上，XMA.LU指令可以用N位乘法和N位加法來模擬，而XMA.HU可以通過使用例如2N位來精確計算ax+b並只取較高的N位來模擬。乘加指令還可以在具有有符號乘累加(multiply-accumulate)指令的處理器上模擬。例如，XMA.HU(a，x，b)可以被模擬為「x+(XMA.HS(a，x，b))」，其中XMA.HS表示將a和x(但沒有b)作為有符號整數的乘加指令。
除了整數合併乘加指令，整數除法系統10的硬體體系結構支持還包括表示為SHR.U(x，m)＝(x/2m)的右移指令。
當使用浮點數運算時，整數除法系統10的硬體體系結構支持包括(1)支持浮點數合併乘加指令的N位處理器，以及(2)從浮點數值中提取二進位指數和有效位的操作。例如，對於浮點數值u、v和w，這一操作被表示為(uv+w)m，其利用單個最後捨入將(uv+w)計算為N個有效位，其中N包括最高的1位。指數偏倚被表示為BIAS，而提取指數和有效位的操作被分別表示為EXPONENT和SIGNIFICAND。非零值f具有值SIGNIFICAND(f)*2EXPONENT(f)-BIAS-N+1。
處理器或微處理器(圖1中未示出，但可以包括在圖3的執行系統33中)的整數運算單元和浮點數運算單元可以提供上述硬體支持。處理器可以是計算機系統內的處理器，其中計算機系統可以是個人計算機系統、筆記本計算機系統、工作站計算機系統、大型機計算機系統、伺服器計算機系統或超級計算機。可選地，可以在處理器的高速緩存中預先建立對於所有倒數近似值及其對應的捨入誤差補償值的查找表。在操作過程中，處理器可以訪問查找表，檢索特定除數的倒數近似值和捨入誤差補償值。
整數除法系統10可以在多種不同系統中實現。例如，整數除法系統10可以在編譯器(例如，圖2)中實現。在另一個實例中，整數除法系統10可以在如圖3所示的運行時環境的即時編譯器中實現。在另一個實例中，整數除法系統10可以作為處理器中的固件來實現，以執行動態(on-the-fly)整數除法，包括倒數近似值a和捨入誤差補償值b的計算。在另一個實施例中，整數除法系統10可以在軟體程序(例如，編譯後代碼)內部實現。編譯器實現和即時編譯器實現將結合圖2-3在下面詳細描述。
根據本發明的一個實施例，圖2示出圖1的整數除法系統10的編譯器實現。從圖2可以看出，編譯器21用於將原始碼程序20編譯為編譯後代碼22。編譯器21包括圖1的整數除法系統10。原始碼20是用一種已知的高級程式語言(例如，C++)編寫的軟體程序。編譯後代碼22可以是能直接在特定平臺數據處理系統或計算機系統上執行的本機代碼(native code)。可選地，編譯後代碼22還可以是中間語言代碼(例如，Java字節碼)，其可以然後被解釋為、或隨後由運行時系統(或虛擬機)內的即時(JIT)編譯器編譯為能由特定平臺目標計算機系統執行的本機代碼或機器碼。編譯器21是由計算機系統所主控(或運行在其上)的軟體系統。在編譯過程中，當編譯器21編譯具有已知或常量除數的整數除法指令時，編譯器21調用整數除法系統10。
圖3示出圖1的整數除法系統10的運行時環境實現。從圖3可以看出，運行時環境31將編譯後代碼30編譯為由執行系統33執行的本機代碼(或機器碼)。運行時環境31是運行在執行系統33上並由執行系統33主控的軟體系統(或Java虛擬機)。執行系統33使用運行時環境31以協助將編譯後代碼30進一步編譯為執行系統33的特定平臺(或特定體系結構)的本機代碼。運行時環境31還可以被稱為虛擬機或運行時系統。
執行系統33可以是，例如，個人計算機、個人數字助理、網絡計算機、伺服器計算機、筆記本計算機、工作站、大型機計算機、或超級計算機。在本發明的一個實施例中，執行系統33包括一個處理器(未示出)，該處理器包括高速緩存(也未示出)，該高速緩存包括對於所有倒數近似值及其對應的捨入誤差補償值的查找表。編譯後代碼30可以通過諸如區域網、網際網路或無線通信網絡這樣的通信連結傳遞到執行系統33。
運行時環境31包括使用圖1的整數除法系統10的即時編譯器32。即時編譯器32在運行時對編譯後代碼30進行編譯以生成本機代碼或機器碼。術語「即時」指在編譯後代碼30內的每個方法或類真正用於執行時，即時編譯器32將其編譯或翻譯為本機代碼。當即時編譯器32遇到整數除法指令時，它調用整數除法系統10。
可選地，整數除法系統10可以在編譯後代碼(例如，編譯後代碼30)內部實現。在這種情況下，整數除法系統10可以作為程序內的代碼序列來實現，並在進入具有循環不變除數的循環之前執行。在這一實現中的整數除法系統10還可以作為程序內的代碼序列來實現，並為具有相同除數的多個除法執行。在這種情況下，編譯後代碼可以被直接執行或由不包含整數除法系統10的JIT編譯器進一步編譯。
回來參考圖1及如上所述，整數除法系統10用於使用乘加操作加上右移操作來實現整數除法。當整數除法系統10接收到具有已知或常量除數的整數除法指令時，整數除法系統10在知道被除數後返回可以執行整數除法的乘加指令和右移指令。例如，對於被除數為x而除數為d的整數除法，整數除法系統10將該除法轉換為(ax+b)/2s，其中a是除數的倒數近似值，b是捨入誤差補償值，而s是右移計數。然後整數除法系統10生成乘加和右移指令。
整數除法系統10使用指令生成模塊12來生成乘加和右移指令。例如，在上述硬體支持下，對於無符號整數除法x/d，指令生成模塊12所生成的乘加和右移指令是SHR.U(XMA.HU(a，x，b)，m)。如果整數除法是無符號整數除數的有符號整數除法，那麼指令生成模塊12所生成的乘加和右移指令是SHR.U(x+XMA.HS(a，x，b)，m)。
在生成乘加和右移指令之前，整數除法系統10使用預計算模塊11來選擇、確定或計算倒數近似值a和捨入誤差補償值b。根據本發明的一個實施例，預計算模塊11確定應當使用向上捨入還是向下捨入來選擇倒數近似值a和/或捨入誤差補償值b。預計算模塊11使用整數運算或浮點數運算來作出該確定。圖4示出根據本發明的一個實施例，預計算模塊11選擇或計算倒數近似值a和/或捨入誤差補償值b的整個預計算處理，這將在下面詳細描述。
從圖4可以看出，預計算處理在方框40開始。在41，確定除數d是否是特殊情況。這裡，術語「特殊情況」是指除數d是特殊值，其向上捨入或向下捨入不起作用的情況。例如，當除數d等於1時是特殊情況。此外，對倒數近似值向上捨入或向下捨入的確定非常複雜(例如，也許需要超精度運算)的情況也可以設為特殊情況。例如，當除數d是2的冪時可以設為特殊情況。根據本發明的一個實施例，圖1的預計算模塊11作出這種特殊情況的確定。
如果，在41，確定除數d是特殊情況，這意味著將確定倒數近似值a和捨入誤差補償值b而不需要向上捨入或向下捨入的確定。在這種情況下，處理移動到方框42。但是，如果確定除數d不是特殊情況，則處理移動到方框43。
在42，因為除數d已經被確定為特殊，所以使用「被1除(divide-by-one)」技術來計算倒數近似值a和捨入誤差補償值b(在圖4中稱為RRECV)而不經過向上捨入或向下捨入的確定。這裡，「被1除」技術是指倒數近似值a和捨入誤差補償值b中的每一個都被賦予值2N-1。根據本發明的一個實施例，圖1的預計算模塊11進行這一計算。然後該處理在方框46結束。
在43，確定應當使用向上捨入或還是向下捨入來計算倒數近似值a和捨入誤差補償值b。根據本發明的一個實施例，圖1的預計算模塊11作出這一確定。取決於該整數除法是有符號還是無符號的，以及取決於使用整數運算還是浮點數運算來計算倒數近似值a和捨入誤差補償值b，圖1的預計算模塊11使用不同的測試公式來作出這一確定。
例如，如果該整數除法是無符號整數除法並且使用整數運算來計算倒數近似值a和捨入誤差補償值b，則圖1的預計算模塊11使用「(t*d+d)mod 2N≤2m」測試來作出確定，其中t是臨時量，被計算為(2m+N)/d。作為進一步的實例，如果該整數除法是無符號除數的有符號整數除法並且使用整數運算來計算倒數近似值a和捨入誤差補償值b，則圖1的預計算模塊11使用「(td+d)mod 2N≤XMA.HU(d，t，0)」測試來作出確定。進一步，如果該整數除法是無符號整數除法並且使用浮點數運算來計算倒數近似值a和捨入誤差補償值b，則圖1的預計算模塊11使用「RNDN(-dt+1)≤0」測試來作出確定，其中t＝RNDn(1/d)。如果該整數除法是有符號整數除法並且使用浮點數運算來計算倒數近似值a和捨入誤差補償值b，則圖1的預計算模塊11不使用任何測試來作出確定。取而代之，預計算模塊11跳過這一確定，並簡單地令m＝(BIAS-1)-EXPONENT(t)、a＝SIGNIFICAND(t)、且b＝a/2。這些將在下面結合圖5-8詳細描述。
如果，在43，確定應當使用向上捨入，則處理移動到方框44。如果，在43，確定應當使用向下捨入，則處理移動到方框45。
在44，根據本發明的一個實施例，圖1的預計算模塊11基於向上捨入的確定來計算倒數近似值a和捨入誤差補償值b(RRECV)。此外，取決於該整數除法是有符號還是無符號的，以及使用整數運算還是浮點數運算來計算a和捨入誤差補償值b，圖1的預計算模塊11不同地選擇或計算的倒數近似值a和捨入誤差補償值b。這將在下面結合圖5-8詳細描述。然後該處理在方框46結束。
在45，根據本發明的一個實施例，圖1的預計算模塊11基於向下捨入的確定來計算倒數近似值a和捨入誤差補償值b。此外，取決於該整數除法是有符號還是無符號的，以及使用整數運算還是浮點數運算來計算a和捨入誤差補償值b，圖1的預計算模塊11不同地選擇或計算倒數近似值a和捨入誤差補償值b。這將在下面結合圖5-8詳細描述。然後該處理在方框46結束。
圖5示出圖1的預計算模塊11使用整數運算對於無符號整數除法的預計算處理。圖6示出圖1的預計算模塊11使用整數運算對於無符號除數的有符號整數除法的預計算處理。這意味著在圖5-6中，圖1的預計算模塊11使用處理器的整數運算單元進行確定和計算。圖7示出圖1的預計算模塊11使用浮點數運算對於無符號整數除法的預計算處理。圖8示出圖1的預計算模塊11使用浮點數運算對於無符號除數的有符號整數除法預計算處理。
參考圖5，該處理在方框50開始。在51，輸入除數d和N的值。根據本發明的一個實施例，預計算模塊11(圖1)執行這一功能。N的值指示在N位處理器中表示的除數d的長度。
在52，確定N是否大於0且除數d是否大於或等於1但小於2N。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。如果確定是否定的(即，否)，那麼該處理在方框59結束。如果確定為肯定結果(即，是)，則該處理移動到方框53。
在53，m的值被計算為floor(log2(d))。根據本發明的一個實施例，圖1的預計算模塊11執行這一計算。
在54，確定除數d是否是特殊情況(即，d＝2m)。根據本發明的一個實施例，圖1的預計算模塊11執行這一確定。如果在54除數d被確定為是特殊情況(即，是)，那麼該處理移動到方框55，在這一步預計算模塊11令倒數近似值a和捨入誤差補償值b中的每一個具有2N-1的值。然後該處理在方框59結束。
如果在54確定除數d不是特殊情況(即，否)，那麼該處理移動到方框56，在這一步，根據本發明的一個實施例，預計算模塊11作出另一確定。這一確定用於決定將倒數近似值a從N+1位向上捨入還是向下捨入到最近的N位(並因此選擇捨入誤差補償值b的值)。這裡為進行確定所使用的測試是(td+d)mod 2N≤2m，其中t是臨時量，被計算為(2m+N)/d。雖然結果通常是單個字，但是該計算必須在雙精度(2N位)下進行。這意味著該計算需要用雙字除以單字以計算t。然後執行該測試「(td+d)mod 2N≤2m」。圖1的預計算模塊11隻使用如「mod 2N」所指示的N位無符號運算來計算「(td+d)mod 2N」。在(由加利福尼亞聖塔克拉拉的英特爾公司銷售的)64位英特爾安騰處理器上，「(td+d)mod 2N」簡單地為XMA.LU(t，d，d)。
如果在56確定將倒數近似值a向下捨入(即，否)，那麼該處理移動到方框57。否則，該處理移動到方框58。
在57，令倒數近似值a和捨入誤差補償值b都為t(即，(2m+N)/d)。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後該處理在方框59結束。
在58，令倒數近似值a為(t+1)，而捨入誤差補償值b被設為0(即，沒有誤差補償)。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後該處理在方框59結束。下面列出執行圖5的處理的代碼序列。
Inputs:uword d and N,with N≥1 and 1≤d≤2Nint m:=floor(log2(d));
uword a,b;
if d=2mthena:=2N-1;
b:=2N-1;
elseuword t=floor((2N+m)/d);
uword r=(td+d)mod 2N;
ifr≤2ma:=t+1;
b:=0;
elsea:=t;
b:=t;
endifendifEmit SHR.U(XMA.HU(a,x,b),m)這裡，假設類型「uword」的變量保存任意N位無符號值，並且假設類型「iht」的變量保存整數。此外，圖1的指令生成模塊12執行上述代碼序列中的最後一條指令。
參考圖6，圖1的整數除法系統11使用整數運算對於無符號除數的有符號整數除法的預計算處理在方框60開始。在61，輸入除數d和N的值。根據本發明的一個實施例，預計算模塊11(圖1)執行這一功能。N的值指示在N位處理器中表示的除數d的長度。
在62，確定是否N大於0且除數d大於或等於1但小於2N。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。如果確定是否定的(即，否)，那麼該處理在方框70結束。如果確定為肯定結果(即，是)，則該處理移動到方框63。
在63，m的值被計算為log2(d)，向下捨入。根據本發明的一個實施例，圖1的預計算模塊11執行這一計算。
在64，確定除數d是否是特殊情況(即，d＝2m)。根據本發明的一個實施例，圖1的預計算模塊11執行這一確定。如果在64除數d被確定為特殊情況(即，是)，那麼該處理移動到方框65，在這一步，預計算模塊11令倒數近似值a和捨入誤差補償值b中的每一個具有2N-1的值。然後該處理在方框70結束。
如果在64確定除數d不是特殊情況(即，否)，那麼該處理移動到方框66，在這一步，根據本發明的一個實施例，預計算模塊11令t(臨時量)被計算為(2m+N)/d。此外，預計算模塊11令捨入誤差補償值b等於t/2(即，總是進行誤差補償)。
在67，確定將倒數近似值a從N+1位向上捨入(即，朝著正無窮方向)還是向下捨入(即，朝著負無窮方向)到最近的N位。這裡為進行確定所使用的測試是(td+d)mod2N≤XMA.HU(d，t，0)。如果確定將倒數近似值a向上捨入(即，是)，那麼該處理移動到方框69。否則，該處理移動到方框68。
在69，倒數近似值a被設為(t+1)。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後該處理在方框70結束。
在68，倒數近似值a被設為t。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後該處理在方框70結束。下面列出實現圖6的處理的代碼序列。
Inputs:uword d and N,with N≥1 and 1≤d≤2Nint m:=floor(log2(d));
uword a,b;
if d=2mthena:=2N-1;
b:=2N-1;
elseuword t=floor((2N+m)/d);
b:=t/2;
if(td+d)mod 2N≤XMA.HU(d,t,0)thena:=t+1;
elsea:=t;
endifendifEmit SHR.U(x+XMA.HS(a,x,b),m)這裡，圖1的指令生成模塊12執行上述代碼序列中最後一條指令。
圖7示出圖1的預計算模塊11使用浮點數運算對於無符號整數除法的預計算處理。這意味著使用處理器的浮點數運算單元進行計算和確定。從圖7可以看出，該處理在方框80開始。在81，輸入除數d和N的值。根據本發明的一個實施例，預計算模塊11(圖1)執行這一功能。
在82，確定是否N大於0並且除數d大於或等於1但小於2N。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。如果確定是否定的(即，否)，那麼該處理在方框90結束。如果確定為肯定結果(即，是)，則該處理移動到方框83。
在83，確定除數d是否是特殊情況。這裡，特殊情況被定義為d＝1。根據本發明的一個實施例，圖1的預計算模塊11執行這一確定。如果在83確定除數d不是特殊情況(即，否)，那麼該處理移動到方框84。如果在83確定除數d是特殊情況(即，是)，那麼該處理移動到方框85。
在84，臨時浮點數值t被設為RNDN(1/d)，其中RNDN(1/d)使用例如Newton-Raphson迭代序列來完成。這意味著使用Newton-Raphson迭代求1/d的近似值，其中所需迭代的數目依賴於N的值。
Newton-Raphson迭代序列應當求1/d的近似值，捨入到最近的N位(除非d＝2N-1)。如果d＝2N-1，則該序列允許提供1/d的最近的N位近似值，或者1/d向下捨入到2-N。這樣的序列，是數值計算領域從業者非常熟悉的，使用倒數近似值指令來初始化一個初始估計，並使用合併乘加操作來優化這一估計。
在85，t被設為1-2-N，這是向下接近了一最小精度單位的除數d的倒數。這具有將t的有效位設為「全1」且其無偏指數為-1的效果。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。
在86，m被設為(BIAS-1)-EXPONENT(t)。這意味著m被設為(-1)減去無偏指數。此外，倒數近似值a被設為SIGNIFICAND(t)。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。此後，只剩下判斷b應該為0還是a。這在方框87完成。
在87，確定b應當為0或a。根據本發明的一個實施例，圖1的預計算模塊11使用測試「RNDN(-td+1)≤0」來判斷。這一測試實際上確定了通過將倒數近似值a的N位有效位捨入到最近的值所引入的捨入誤差是正還是負。該誤差最大是2-N。該測試可以由合併乘加操作來執行。如果該測試是真(即，向上捨入)，那麼該處理移動到方框89。否則，該處理前進到方框88。
在88，捨入誤差補償值b被設為a。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後該處理在方框90結束。
在89，捨入誤差補償值b被設為0(即，沒有誤差補償)。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後該處理在方框90結束。下面列出實現圖7的處理的代碼序列。
Inputs:uword d and N,with N≥1 and 1≤d≤2Nuword a,b;
real tif d=1thent:=1-2-N;
elset=RNDN(1/d);
endifa:=SIGNIFICAND(t)m:=(BIAS-1)-EXPONENT(t)if RNDN(-td+1)≤0thenb:=0;
elseb:=a;
endifEmit SHR.U(XMA.HU(a,x,b),m)
這裡，圖1的指令生成模塊12執行上述代碼序列中的最後一條指令。
圖8示出圖1的預計算模塊11使用浮點數運算對於無符號除數的有符號整數除法進行的預計算處理。這意味著使用處理器的浮點數單元進行計算和確定。另外從圖7-8可以看出，圖8中方框100-105執行與圖7中方框80-85相同的功能。因此，圖8中這些功能方框100-105將不在下面詳細描述。
在圖8中，在106，m被設為(BIAS-1)-EXPONENT(t)，a被設為SIGNIFICAND(t)，且b被設為a/2。根據本發明的一個實施例，圖1的預計算模塊11執行這一功能。然後處理在方框107結束。下面列出實現圖8的處理的代碼序列。
Inputs:uword d and n,with N≥1 and 1≤d≤2Nuword a,b;
real tif d=1thent:=1-2-N;
elset=RNDN(1/d);
endifa:=SIGNIFICAND(t)m:=(BIAS-1)-EXPONENT(t)b:=a/2Emit SHR.U(x+XMA.HS(a,x,b),m)這裡，圖1的指令生成模塊12執行上述代碼序列中的最後一條指令。
圖4-8是說明根據本發明的多個實施例，圖1的預計算模塊11計算倒數近似值a和捨入誤差補償值b的預計算處理的流程圖。圖中所說明的一些過程可以順序執行、並行執行或以所描述的順序之外其它順序執行。應當理解，並不是需要所描述的所有過程，可以增加其它過程，並且所說明的一些過程可以被其它過程代替。
在前面的說明書中，通過參考本發明的特定的示例性實施例，描述了本發明的多個實施例。但是很明顯，在不背離本發明的實施例的較廣精神和範圍的情況下，可以對本發明的實施例作出各種變化和修改。因此，本說明書和附圖是作為示例性的而不是限制性的。
權利要求
1.一種被除數和除數的整數除法系統，包括預計算模塊，用於選擇所述除數的倒數近似值和捨入誤差補償值，其中，所述倒數近似值具有與所述除數相同的預定二進位位數，並且所述預計算模塊確定在選擇所述倒數近似值和所述捨入誤差補償值時使用向上捨入和向下捨入中的哪一個；指令生成模塊，用於生成指令，該指令用於使用所述倒數近似值和所述捨入誤差補償值來計算所述被除數的商。
2.如權利要求1所述的系統，其中，所述預計算模塊通過使用處理器的整數運算單元計算所述倒數和所述捨入誤差補償值，來選擇所述倒數和捨入誤差補償值。
3.如權利要求1所述的系統，其中，所述預計算模塊通過使用處理器的浮點數運算單元計算所述倒數和所述捨入誤差補償值，來選擇所述倒數和捨入誤差補償值。
4.如權利要求3所述的系統，其中，對於無符號除數的有符號除法，所述向上捨入和向下捨入分別指將所述倒數近似值朝著正無窮方向捨入和朝著負無窮方向捨入。
5.如權利要求1所述的系統，其中，所述指令生成模塊所生成的所述指令包括合併乘加指令和右移指令。
6.如權利要求1所述的系統，其中，所述預計算模塊通過從處理器的高速緩存中的查找表中檢索所述倒數和捨入誤差補償值，來選擇所述倒數和捨入誤差補償值。
7.如權利要求1所述的系統，其中，所述預計算模塊和所述指令生成模塊位於編譯器內。
8.如權利要求1所述的系統，其中，所述預計算模塊和所述指令生成模塊位於運行時環境的即時編譯器內。
9.如權利要求1所述的系統，其中，所述預計算模塊和所述指令生成模塊作為代碼序列位於編譯後的代碼程序內。
10.一種選擇整數除法中除數的倒數近似值和捨入誤差補償值的計算機實現的方法，包括確定使用向上捨入和向下捨入中的哪一個來選擇所述倒數近似值和捨入誤差補償值；基於所述確定來選擇所述倒數近似值和所述捨入誤差補償值，其中，所述倒數近似值具有與所述除數相同的預定二進位位數。
11.如權利要求10所述的方法，其中，使用處理器的整數運算單元來執行所述確定和選擇。
12.如權利要求10所述的方法，其中，使用處理器的浮點數運算單元來執行所述確定和選擇，其中，對於無符號除數的有符號除法，所述向上捨入和向下捨入分別指將所述倒數近似值朝著正無窮方向捨入和朝著負無窮方向捨入。
13.如權利要求10所述的方法，其中，通過從處理器的高速緩存中的查找表中檢索所述倒數近似值和所述捨入誤差補償值來執行所述選擇。
14.一種執行整數除法的方法，包括檢查除數，以確定應當使用向上捨入和向下捨入中的哪一個來選擇所述除數的倒數近似值和捨入誤差補償值；基於所述檢查來選擇所述倒數近似值和所述捨入誤差補償值，其中，所述倒數近似值具有與所述除數相同的預定二進位位數；生成至少一條指令，該指令用於使用所述倒數近似值和所述捨入誤差補償值來計算被除數的商。
15.如權利要求14所述的方法，其中，使用處理器的整數運算單元來執行所述確定和選擇。
16.如權利要求14所述的方法，其中，使用處理器的浮點數運算單元來執行所述確定和選擇。
17.如權利要求16所述的方法，其中，對於無符號除數的有符號除法，所述向上捨入和向下捨入分別指將所述倒數近似值朝著正無窮方向捨入和朝著負無窮方向捨入。
18.如權利要求14所述的方法，其中，所生成的所述指令包括合併乘加指令和右移指令。
19.如權利要求14所述的方法，其中，通過從處理器的高速緩存中的查找表中檢索所述倒數近似值和所述捨入誤差補償值來執行所述選擇。
20.一種包含機器可訪問介質的製品，其中所述機器可訪問介質包括指令序列，所述指令序列包括指令，所述指令當被執行時使所述機器執行檢查除數，以確定應當使用向上捨入和向下捨入中的哪一個來選擇所述除數的倒數近似值和捨入誤差補償值；基於所述檢查來選擇所述倒數近似值和所述捨入誤差補償值，其中，所述倒數近似值具有與所述除數相同的預定二進位位數；生成至少一條指令，該指令用於使用所述倒數近似值和所述捨入誤差補償值來計算被除數的商。
21.如權利要求20所述的製品，其中，使用處理器的整數運算單元來執行所述確定和選擇。
22.如權利要求20所述的製品，其中，使用處理器的浮點數運算單元來執行所述確定和選擇。
23.如權利要求22所述的製品，其中，對於無符號除數的有符號除法，所述向上捨入和向下捨入分別指將所述倒數近似值朝著正無窮方向捨入和朝著負無窮方向捨入。
24.如權利要求20所述的製品，其中，所生成的所述指令包括合併乘加指令和右移指令。
25.如權利要求20所述的製品，其中，通過從處理器的高速緩存中的查找表中檢索所述倒數近似值和所述捨入誤差補償值來執行所述選擇。
全文摘要
一種被除數和除數的整數除法系統，包括預計算模塊，用於選擇除數的倒數近似值和捨入誤差補償值；以及指令生成模塊，用於生成至少一條指令，該指令用於使用倒數和捨入誤差補償值來計算被除數的商。倒數近似值具有與除數相同的預定二進位位數，並且預計算模塊確定在選擇倒數近似值和捨入誤差補償值時使用向上捨入和向下捨入中的那一個。
文檔編號G06F7/535GK1961284SQ200580017331
公開日2007年5月9日 申請日期2005年6月17日 優先權日2004年6月29日
發明者阿奇·羅比森 申請人:英特爾公司