部分餘數/除數表拆分實現的製作方法

2023-05-01 11:40:21 2

技術領域

本說明書涉及用於執行數學運算的電路，更具體地，涉及用於執行除法的電路。

背景技術：

除法是一種給定兩個數，計算出它們的商和/或餘數的數學運算。作為術語的餘數，通常被除的較大的數被稱為分子或被除數(N)。被除數所除以的數被稱為分母或除數(D)。整數結果被稱為商(Q)，並且已經被確定為商之後剩下的任意數為餘數(R)。或用更加常見的公式表述：

N/D＝(Q,R),或

N＝(Q×D)+R

如回憶我們在學校時所學，除法趨向於一種迭代過程。對於被除數中的每個數位(decimal place)，人們推測除數將進入被除數多少次(直至當前數位)。然後，從被除數(N)減去推測的成倍的除數(Q×D)，並得到局部或當前餘數(PR)。然後，移動活動的小數點，並針對添加到(prepended to)被除數的下一數位的當前餘數再次執行該過程。這樣持續直到確定最終的商和餘數(如果有)。

也許令人驚訝，計算機在進行除法時執行相同的基本操作集。主要的不同在於，由於計算機不使用基於10的或十進位數的系統，因此「小數點」被稱為其更廣泛的術語「基點」。能使用的基數越大，計算機需要完成的迭代可越少並且整個除法運算越快。

除法技術通常落入兩個主要類別：低速除法和快速除法。低速除法算法 每次迭代產生最終商的一個數位。慢速除法的示例包括恢復除法、不良恢復除法、不恢復除法和SRT除法。快速除法方法以對最終商的近似開始，並在每次迭代時產生兩倍的最終商的數位。牛頓-拉夫遜(Newton–Raphson)法和戈爾德施密特(Goldschmidt)技術落入該類。

SRT除法以其創造者(斯威尼(Sweeney)、羅伯森(Robertson)和託赫爾(Tocher))命名，並且在很多微處理器實現中是用於除法的普遍方法。SRT除法類似於不恢復除法，但它使用基於被除數和除數的查找表來確定每個商位。英特爾奔騰處理器的聲名狼藉的浮點型除法的漏洞就是由不正確編碼的查找表造成的。1066個條目中的五個被錯誤地忽略。

SRT之類的除法的問題之一是查找表(LUT)可能會很大。隨著基數增大(例如，從2到4，或甚至到16、32、64或128等)，查找表的大小大幅增加的事實使該問題加重。一般來講，隨著查找表的大小增加，不止存儲LUT所需的電路的大小增大，而且電路處理LUT所需的時間也增加。

技術實現要素：

根據一個總的方面，設備可包括：關鍵字選擇器，被配置為從輸入值的至少一部分選擇個性關鍵字。所述設備可包括：稀疏查找表，被配置為基於個性關鍵字和先前餘數確定結果的部分。所述設備可包括：加法器，被配置為至少基於輸入值和結果的所述部分計算當前餘數。所述設備可被配置為迭代地計算當前餘數和結果的部分，直到當前餘數為零或者達到預定義水平的精度。

根據另一個總的方面，方法可包括：基於除數的至少一部分選擇個性關鍵字。所述方法可包括：基於個性關鍵字和先前餘數從稀疏查找表確定商的部分。所述方法可包括：基於被除數、除數和商的所述部分計算當前餘數。所述方法可包括：迭代地執行確定商的部分和計算當前餘數的步驟，直到當前餘數為零或者達到預定義水平的精度。

根據另一個總的方面，片上系統(SoC)可包括：指令單元，被配置為將指令發送給算術單元，其中，所述指令與輸入值有關。算術單元可包括：關鍵字選擇器，被配置為從輸入值的至少一部分選擇個性關鍵字。算術單元可包括：稀疏查找表，被配置為基於個性關鍵字和先前餘數確定結果的部分。算術單元可包括：加法器，被配置為基於輸入值和結果的所述部分計算當前 餘數。算術單元可被配置為迭代地計算當前餘數和結果的部分，直到當前餘數為零或者達到預定義水平的精度。SoC可包括：存儲器，被配置為存儲結果。

在下面的附圖和描述中對一個或多個實現的細節進行闡述。其他的特徵通過描述和附圖以及權利要求將是清楚的。

如在權利要求中更全面地闡述的，用於執行數學運算的電路的系統和/或方法，更具體地，用於執行除法的電路的系統和/或方法基本如至少一個附圖所示和/或結合至少一個附圖所描述。

附圖說明

圖1是根據公開的主題的系統的示例實施例的框圖。

圖2是根據公開的主題的系統的示例實施例的框圖。

圖3是根據公開的主題的數據結構的示例實施例的示圖。

圖4是根據公開的主題的系統的示例實施例的框圖。

圖5是根據公開的主題的數據結構的示例實施例的示圖。

圖6a是根據公開的主題的系統的示例實施例的框圖。

圖6b是根據公開的主題的數據結構的示例實施例的示圖。

圖6c是根據公開的主題的數據結構的示例實施例的示圖。

圖7是根據公開的主題的系統的示例實施例的框圖。

圖8是可包括根據公開的主題的原理而形成的裝置的信息處理系統的示意性框圖。

在各種附圖中的相同的參考符號指示相同的元件。

具體實施方式

以下，將參照附圖對各種示例實施例進行更加全面地描述，在附圖中示出了一些示例實施例。然而，本公開的主題可以以多種不同的形式來實現，並且不應該被視為限於這裡闡述的示例實施例。相反，提供這些示例實施例使得本公開將是徹底的和完整的，並且將本公開的主題的範圍全面地傳達給本領域技術人員。在附圖中，為了清晰，可能誇大層和區域的大小以及相對大小。

將理解，當元件或層被稱為「在……上」、「連接到」或「結合到」另一 個元件或層時，它能直接在所述另一個元件或層上、連接到或結合到所述另一個元件或層，或者可存在中間元件或層。相反，當元件被稱為「直接在……上」、「直接連接到」或「直接結合到」另一個元件或層時，不存在中間元件和層。相同的標號始終指代相同的元件。如這裡使用的，術語「和/或」包括一個或多個關聯的所列項的任何組合和全部組合。

將理解，儘管可在這裡使用術語「第一」、「第二」、「第三」等描述各種元件、組件、區域、層和/或部分，但是這些元件、組件、區域、層和/或部分不應該由這些術語限制。這些術語只是用於將一個元件、組件、區域、層或部分與另一個區域、層或部分進行區分。因此，在不脫離本公開的主題的教導的情況下，以下討論的第一元件、組件、區域、層或部分可被稱為第二元件、組件、區域、層或部分。

空間相對術語(諸如「在…以下」、「在…下面」、「低於」、「在…之上」、「上面的」等)可在這裡使用以便於說明書描述在附圖中示出的一個元件或特徵與另外的元件或特徵的關係。將理解，空間相對術語意圖包含除了在附圖中描述的方向之外的裝置在使用或操作中的不同方向。例如，如果翻轉在附圖中的裝置，則被描述為在其他元件或特徵「下面」或「以下」的元件可被定向為在其他元件或特徵的「上面」。因此，示例性術語「在…下面」可包含上面和下面的兩個方向。裝置可被另外定向(旋轉90度或朝向其他方向)，並相應地解釋了這裡使用的與空間相關的描述符。

這裡使用的術語僅是用於描述特定的示例實施例的目的，而意圖不在於限制本公開的主題。如這裡所使用的，除非上下文明確地另有指示，否則單數形式也意圖包括複數形式。還將理解，當在本說明書中使用術語「包括」和/或「包括的」時，表明描述的特徵、整體、步驟、操作、元件和/或組件的存在，但不排除一個或多個其他特徵、整體、步驟、操作、元件、組件和/或它們的組的存在或添加。

在這裡參照作為理想化的示例實施例的示意圖的截面圖(和中間結構)對示例實施例進行描述。因此，由於例如製造技術和/或公差導致的示圖形狀的變化是可預期的。因此，示例實施例不應被解釋為限於這裡示出的區域的特定形狀，而是包括由於例如製造引起的形狀上的偏差。例如，以矩形示出的注入區域通常將在其邊緣上具有圓形的或彎曲的特徵和/或注入濃度的梯度，而不是從注入區域到非注入的區域的二元變化。類似地，通過注入形成 的埋入區可導致在埋入區和發生注入的表面之間的區域中的一些注入。因此，在附圖中示出的區域在本質上是示意圖，並且它們的形狀不意圖示出裝置的區域的實際形狀，並且不意圖不限制本公開的主題的範圍。

除非另有定義，否則這裡使用的所有術語(包括技術術語和科學術語)具有和本公開的主題所屬領域的普通技術人員普遍理解的含義相同的含義。還將理解，除非在這裡明確地定義，否則術語(諸如在通用字典中定義的術語)應該被解釋為具有與它們在相關領域的語境中的含義一致的含義，而不將被解釋為理想化或過於正式的意義。

以下，將參照附圖對示例實施例進行詳細地說明。

圖1是根據公開的主題的系統100的示例實施例的框圖。在各種實施例中，系統100可包括處理器或甚至片上系統(SoC)。需理解，上述僅是一些說明性示例，公開的主題不限於此。

在示出的實施例中，系統100可包括：指令單元102，將指令發送給各種執行單元(僅示出一個)。在示出的實施例中，指令單元102可接收用於執行某些形式的除法(例如，整數除法、浮點除法、平方根運算等)的指令。指令單元102可將該指令發送給或轉發給算術執行單元104。

在示出的實施例中，系統100可包括一個或多個算術執行單元104。在一些實施例中，算術單元104可處理整數數學運算。在另一個實施例中，算術單元104可處理浮點數學運算。需理解，上述僅是一些說明性示例，公開的主題不限於此。在示出的實施例中，算術單元104可被配置為執行除法運算(例如，平方根運算、除法運算等)。

在各種實施例中，系統100可包括存儲單元106。在各種實施例中，該存儲單元106可包括寄存器、高速緩存或更長期的存儲器。在這樣的實施例中，存儲器106可被配置為存儲諸如指令的輸入和/或指令的輸出或結果的數據。在各種實施例中，指令可與除數和被除數有關。在示出的實施例中，可通過存儲器106將輸入提供給算術單元104。在另一個實施例中，可由指令單元102提供輸入。

在示出的實施例中，算術執行單元104可被配置為通過採用查找表(LUT)的技術來執行數學指令或運算。然而，如下所述，算術單元104可採用使用被除數的個性關鍵字(personality key，個性密鑰)或特徵(signature，籤名)產生的稀疏查找表。

在這樣的實施例中，算術單元104可包括：稀疏LUT產生器電路112，被配置為基於個性關鍵字和完整LUT產生稀疏LUT。由於該稀疏LUT可用於每次除法運算的交互，因此將完整LUT削弱為更有效和更稀疏的形式可獲得顯著效益。在一些實施例中，利用完整LUT的對稱性，稀疏LUT甚至可摺疊或減半，以減小LUT的大小達至少50％。

在示出的實施例中，稀疏LUT產生器電路112可將稀疏LUT提供給除法計算器電路114。然後，除法計算器電路114可迭代地採用稀疏LUT來確定除法運算的結果。在這樣的實施例中，結果可包括商和餘數。之後可在存儲器106中存儲這些結果。

在為了示例的清楚的目的的本文中，將在例如圖2等中對處理除法指令的實施例進行描述。然而，需理解，除法僅是一個說明性示例，公開的主題不限於此。

在各種實施例中，可利用公開的主題來計算平方根值。在除法實施例中，第一輸入值可以是除數，第二輸入值可以是被除數。結果可以是商。在平方根實施例中，第一輸入值可以是被開方數，結果可以是根。在一些實施例中，可存在n次方根實施例，其中，第二輸入值是次數(例如，在平方根實施例中，次數可等於2；在立方根實施例中，次數可等於3，等)。基於公開的主題和已知的平方根計算方法，本領域技術人員將理解平方根實施例可以是如何產生的。需理解，上述僅是一些說明性示例，公開的主題不限於此。

圖2是根據公開的主題的系統200的示例實施例的框圖。在各種實施例中，系統200可包括被配置為執行給定除數292和被除數294作為輸入的除法的數學運算的電路。在各種實施例中，除法運算的結果可包括商296和餘數298。

在示出的實施例中，除法運算被示出為使用基數4。在各種實施例中，可改變基數，並且在一些實施例中，可基於接收的指令動態地修改基數。在各種實施例中，基數為2、4、8、16，甚至32、64或128是預期的。習慣上，在涉及較高基數(例如，16或更大)的電路中，LUT和相關的邏輯電路的大小可變得難以接受。然而，在示出的實施例中，稀疏LUT的使用，特別是與個性關鍵字有關的稀疏LUT的使用可將相關的電路和大小減小至可管理的部分。需理解，上述僅是一些說明性示例，公開的主題不限於此。

在示出的實施例中，系統200可包括：關鍵字表或選擇器202，被配置 為選擇與除數292有關的個性關鍵字282。對於各個基數的大小(例如，4、8、16等)，個性關鍵字282的大小和可能的個性關鍵字的數量可不同。在示出的實施例中，可存在八個均為11位的可能的關鍵字282。在這樣的實施例中，可採用除數292的三個最高有效位(MSB)(或更一般地，除數292的部分)來選擇八個可能的個性關鍵字中的一個。該關鍵字282決定商(或更具體地，q位(qbit)284)在除法過程中的每次迭代的期間是如何被選擇或被推測的。與人們在手動執行十進位長除法時會使用不同次數的表(基於除數)來推測商的方式類似，個性關鍵字282允許系統200基於除數292對查找表進行改變。

在各種實施例中，系統200可包括用於存儲稀疏LUT 290的稀疏存儲器(例如，隨機存取存儲器(RAM)、多路復用器和觸發器等)。在示出的實施例中，稀疏LUT產生器可能已經提供了稀疏LUT 290。下面將參照圖3、圖4、圖5、圖6a、圖6b、圖6c和圖7對稀疏LUT 290的產生進行描述。

在各種實施例中，稀疏LUT 290可包括：一維表，具有若干由先前迭代的餘數298(或其部分)的值來進行索引的條目。在一些實施例中，這些條目中的一些可以是常數(例如，0b10，0b11等)或可以是可變的並且依賴於個性關鍵字282(例如，關鍵字key[5:4]，關鍵字key[1:0]、0b0&關鍵字key[10]等)。在這樣的實施例中，由於關鍵字282一旦被選擇(基於輸入除數)將不會改變，因此稀疏LUT 290對於給定的除法運算的性能可以是不變的。

在這樣的實施例中，稀疏LUT 290可包括一列和若干行。每一行的索引可以是先前迭代的餘數298的一部分。在一個實施例中，如下所述，可針對每列將除法所採用的更大更通用的LUT分為更小的子LUT。還發現，由於更大的LUT的列是在除法運算的開始被設置，因此在運算的迭代的期間只需要使用一個子LUT。雖然之前已知在運算的開始對列進行設置的事實，但是如何利用這個事實還沒有被成功地解決到由公開的主題所示出的程度。

在這樣的實施例中，開發了關鍵字來表示每個子LUT。該關鍵字被示出為個性關鍵字282。每個個性關鍵字282允許按列然後按行減少，以獲得最小的可能的關鍵字。可將關鍵字282傳遞給子LUT 290，並使稀疏LUT 290起到如同完整LUT那樣的作用。拆分LUT具有減小LUT 290的大小的優點，並且稀疏LUT 290可從704個2位條目(16乘以44個)減少到22個條目。每個條目可包括用於Q位(Qbit)的2位。

此外，由於一些相鄰行可包括相同的條目值，所以稀疏LUT 290可包括收縮的行，以便針對多輸入或餘數298的值選擇相同的條目或行。

在傳統的基數4的實施方式中，完整的部分餘數LUT可包括704個2位條目。在示出的實施例中，針對基數4的實施方式的摺疊的稀疏LUT 290可包括10個2位條目。需理解，上述僅是一個說明性示例，公開的主題不限於此。

在另一個實施例中，稀疏LUT 290不僅大小可被減小(例如，通過去除列和去除行等)，還可被摺疊。在這樣的實施例中，稀疏LUT 290可包括摺疊LUT。即，LUT 290可針對正行和負行兩者而大致對稱。在各種實施例中，可不針對正行和負行存在對稱，而是針對非負(正和零兩者)行和負行存在對稱。將在以下對這種情況進行更詳細地討論。在這樣的實施例中，如果餘數298是負的，那麼餘數298(或作為索引而採用的部分)可在使用該值作為索引之前被反轉(inverted)。在這樣的實施例中，摺疊稀疏LUT 290可不僅佔據更少的空間，還隨著反向器的使用而需要更少的邏輯(與處理正值和負值兩者的多路復用器相比)。

在拆分LUT實施例的實施期間，表變得小得多和容易分析得多。正是這種大小的減小使人看到了第二種想法：表摺疊。這種摺疊的想法已經討論和嘗試了多年，但從來沒有正確得到過。先前針對摺疊表的嘗試需要額外的邏輯來填補正的一半和負的一半不能彼此整齊地摺疊的事實。然而，一旦LUT減小到更易於分析的地步，便看不到摺疊表所需的調整。在摺疊LUT(如下所述)之後，現在摺疊LUT的最終大小只是11行2位的值。與完整LUT的704個條目相比，這是非常小的。在這樣的實施例中，能夠看到時序、邏輯和功耗的優點。

稀疏LUT 282的輸出可以是商296的一部分(被稱為q位(q)284)。在各種實施例中，隨著基數的大小被改變，q位284的大小或數量可被改變。在一些實施例中，q位284可以是關於除數292將進入被除數294的當前部分的次數的推測。在示出的實施例中，可從稀疏LUT 290中選擇五個可能的q位284的值：-2，-1，0，1和2。需理解，以上僅是一個說明性示例，公開的主題不限於此。

然後，除數292可之後被乘以q位284(在點250處示出)。在示出的實施例中，採用一種不恢復除法技術。在這樣的實施例中，可採用先前餘數298 的符號來調整相乘的除數286(Q×D)的符號。

在各種實施例中，系統200可包括加法器204。加法器204可將相乘的除數286和先前餘數298相加。在一些實施例中，加法器204可包括全加器204(而不是進位存儲加法器(CSA))。在這樣的實施例中，可不需要針對部分餘數行選擇的超前進位加法器。此外，全加器可產生允許系統使用更少(例如，6位等)的餘數298進行行查找的更精確的值。全加器的另一個優點是，CSA的選擇需要兩組寄存器，以保持每次迭代的進位以及和的信息，而全加器不需要兩組寄存器。對於雙精度而言，這是具有兩倍數量的觸發器的大面積的成本，並且可通過全加器的使用來避免。在示出的實施例中，可採用符號位作為輸入到加法器204的進位輸入。需理解，以上僅是一個說明性示例，公開的主題不限於此。

在示出的實施例中，加法器的輸出288可與被除數294結合，以產生新的或當前的餘數298。該新的或當前餘數298可在下一次迭代中成為先前餘數298。在各種實施例中，結合的步驟可包括：對加法器的輸出288進行由基數大小確定的一定數量的移位(例如，對於基數4的實施方式，2位)。需理解，通過增大基數大小，並由此增加由每次迭代來移位或處理的位的數量，可減少迭代的次數，並且減少了執行全部的除法運算所花費的時間。

系統200可處理多次迭代，直到餘數298為零或者已經達到預定的或預定義的精度水平。在示出的實施例中，系統200可包括被配置為從每次迭代接收q位284並產生完整的商296的商累加器206。在最後一次迭代之後，可由系統200將商296和最終的餘數298(如果有的話)輸出(例如，到存儲器等)。

圖3是根據公開的主題的數據結構300的示例實施例的示圖。在各種實施例中，數據結構300可包括針對基數4的實現的完整的部分餘數/除數查找表。在示出的實施例中，LUT可包括16列和44行，共計704個條目。需理解，以上僅是一個說明性示例，公開的主題不限於此。

在示出的實施例中，列由除數的四個MSB確定或進行索引。因此，由於每次除法運算的除數保持恆定，因此選擇的列將在整個除法運算的期間保持相同。相反地，行由部分或先前餘數的六個MSB確定。由於部分或先前餘數每當除法運算的迭代時將改變，所以除法運算的每次迭代時預期選擇的行改變。

在示出的實施例中，示出了三種一般類型的條目或單元值。具有「超出範圍」的值的條目被認為是「不在意」值，這意味著他們的值是不重要的。一般情況下，這些表示對於給定的除數的不可能的餘數值(例如，除數3不能具有餘數7)。具有固定值(例如，±2或10，±1或01，±0或00等)的條目是常數，並且不管除數如何都不變化。用一個或兩個星號(「*」)標記的條目基於除數變化，並可由給定除數的個性關鍵字表示。每個條目表示二進位值，或(當被轉換為十進位符號時)在商集{0,1,2}中的條目。在各種實施例中，可包括部分或先前餘數的符號位，以形成冗餘的商集{-2,-1,0,+1,+2}。需理解，以上僅是一個說明性示例，公開的主題不限於此。

此外，在示出的實施例中，存在六個加框的或突出顯示的條目。應注意到，這些條目(關於行0000.00和行1111.11之間的中心線)是不對稱的，因此提出表摺疊操作的問題。

圖4是根據公開的主題的系統400的示例實施例的框圖。在各種實施例中，系統400可包括稀疏LUT產生器的實施例，如圖1所示。在各種實施例中，稀疏LUT產生器400可被配置為基於輸入的除數，產生每次除法運算或指令的稀疏LUT。

在示出的實施例中，稀疏LUT產生器400可包括完整的部分餘數/除數(PD)表402，諸如在圖3中示出的。在這樣的實施例中，PD表402可包括針對每個除數的一系列的列以及針對每個部分餘數(正和負兩者)的一系列的行。

在示出的實施例中，稀疏LUT產生器400可包括：列選擇器電路404，被配置為基於給定除數，選擇當前除法運算將訪問的列。在這樣的實施例中，這可將LUT從很多列(例如，對於基數4，16列)減少到單個列。這已經發生了16:1或更大的縮減。

在示出的實施例中，稀疏LUT產生器400可包括行壓縮器電路406。在這樣的實施例中，具有帶有類似條目值的相鄰行的多個行可被減少為共同的或摺疊(collapsed，坍塌)的行。例如，返回參照圖3，針對行1100.00、1100.01、1100.10和1100.11的所有條目具有值0b01或X(不在意)。由於X可以是任何方便的值，所以在這種情況下，X可具有值0b01。因此，可認為所有從1100開始的行(1100.XX)具有0b01的值。可將這四個行摺疊成具有1100.XX的索引和0b01的條目的單個行。在這四個行的情況下，可獲得4:1的壓縮率。 這同樣適用於其他行。

儘管示出的實施例顯示列選擇(404)和行壓縮(406)同時發生，但是在各種實施例中，它們可順序發生。在這樣的實施例中，行壓縮(406)可在列選擇(404)之後發生。這樣，任何非相似的行的條目可由允許更大行壓縮的列選擇進行移除。需理解，以上僅是一個說明性示例，公開的主題不限於此。

在一些實施例中，可組合列選擇器電路404的輸出和行壓縮器電路406的輸出以形成稀疏LUT 490。如以上參照圖2所述，在每次迭代的期間，可採用稀疏LUT 490來產生或輸出一個或多個q位484。

在一個實施例中，如圖2所示，稀疏LUT 490可包括直接引用個性關鍵字482(例如，關鍵字[5:4]，關鍵字[1:0]等)的各部分的條目，並且當訪問稀疏LUT 490時，在每次迭代的期間可「填入」這些值。在這樣的實施例中，存儲關鍵字482的寄存器可以是向稀疏LUT 490邏輯的輸入。相反地，在圖4的示出的實施例中，由於個性關鍵字482在整個除法運算和指令期間是不變(靜態)的，因此可將引用關鍵字482的稀疏LUT 490的值靜態地嵌入到稀疏LUT 490。例如，如果條目指的是key[5:4]並且key[5:4]具有0b11的值，那麼可將條目的值改變為0b11。因此，稀疏LUT 490可變為常數的陣列(針對該特定的除法運算)。在這樣的實施例中，可對在圖2中示出的系統進行適當地改變。需理解，以上僅是一個說明性示例，公開的主題不限於此。

圖5是根據公開的主題的數據結構500的示例實施例的示圖。在各種實施例中，數據結構500可包括針對基數4的實施方式的未摺疊的稀疏部分餘數/除數查找表。在示出的實施例中，可能已經將LUT減少到1列和25行，共計25個條目，或接近28:1的縮減。需理解，以上僅是一個說明性示例，公開的主題不限於此。

在示出的實施例中，只保留列0000。這提供了LUT大小的16:1的縮減。然後，已摺疊各種相似的行。例如，已經將行1111.11和1111.10摺疊成共同的行1111.1？(其中，「？」意味著不在意的1位)。這已經造成了LUT大小的進一步的縮減。

在示出的實施例中，各種行(例如，0010.11、1111.00等)包括常數或靜態的條目值(例如，分別為0b01和0b10)。其他條目值可以是動態的或者依賴於個性關鍵字。例如，行0001.10的條目包括個性關鍵字的第24位和第 23位。行1111.01的條目包括與常數值0b0相連的關鍵字的第27位。因為已經摺疊了相似的行，所以稀疏LUT 500不再包括任何「X」或「不在意」條目。例如，行0010.11的先前的「不在意」條目已經被轉換為常數0b01。需理解，以上僅是一些說明性示例，公開的主題不限於此。

當在圖5中示出了未摺疊稀疏LUT 500時，可見表沿著中心線(在0000.0？和1111.1？之間)是對稱的。因此，在各種實施例中，可對摺稀疏LUT 500，將行減少至13行。為了做到這一點，可不在嚴格的正值和負值之間摺疊LUT500。相反，按照固定量(例如，-0.25或0b0.01)對中心線進行移位或偏移。當移位時，負的行和非負(正或者零)行可變得對稱並可被摺疊。

此外，可注意，在負值和非負值之間的部分餘數的行索引或MSB僅是彼此的逆。因此，在一個實施例中，可在負的餘數值被輸入到摺疊稀疏LUT500之前，將簡單的反向器應用於負的餘數值。在這樣的實施例中，摺疊稀疏LUT 500可作為多路復用器實現，並且摺疊和反向可顯著地減少實現摺疊稀疏LUT查找功能所需的邏輯的量。

圖6a是根據公開的主題的系統600的示例實施例的框圖。在各種實施例中，系統600可包括如圖1所示的稀疏LUT產生器的實施例。在各種實施例中，稀疏LUT產生器600可被配置為針對基於輸入的除數的指令或每個除法運算產生稀疏LUT。

在示出的實施例中，稀疏LUT產生器600可包括完整的部分餘數/除數(PD)表402和列選擇器電路404。在這樣的實施例中，稀疏LUT產生器600可包括行壓縮器電路406。在一些實施例中，如上所述，可組合列選擇器電路404的輸出與行壓縮器電路406的輸出，以形成稀疏LUT 490。

在示出的實施例中，可摺疊稀疏LUT 490以形成摺疊稀疏LUT 690。在這樣的實施例中，可按係數50％再次減小LUT的大小。在各種實施例中，可沿著劃分負值和非負值(即，正值和零值)的中心線來摺疊未摺疊的稀疏LUT490。現在，摺疊LUT 690的最終大小可以僅為11行的2位值。在這樣的實施例中，與完整PD表402的704個條目相比，摺疊LUT 690可很小。

圖6b是根據公開的主題的表651的數據結構的示例實施例的框圖。在各種實施例中，表651可包括如圖5所示的稀疏LUT的實施例。在各種實施例中，可針對每次除法或平方根運算或指令產生稀疏LUT 651。

在示出的實施例中，稀疏LUT 651可包括正的和負的行或值。如可見的， 正行和負行不是對稱的，並且妨礙簡單的摺疊。換言之，行值的絕對值不是相等的。在行646(+1.50)和648(-1.75)之間可輕易看出不重合(不一致)。對於行646，正行+1.50具有個性關鍵字(p關鍵字[9:8])的第九位和第八位的值，而負行-1.50具有0b10的值。類似的，對於行648，正行+1.75具有個性關鍵字(p關鍵字[7:6])的第七位和第六位的值，而負行-1.75具有個性關鍵字(p關鍵字[9:8])的第九位和第八位的值。此外，在示出的實施例中，+0.00行642和-5.50行644不具有等同的配對物。不存在-0.00行和+5.50行。在這樣的實施例中，必須採用額外的邏輯以處理這些邊角情況。該額外邏輯增加了執行單元的大小和複雜度。

圖6c是根據公開的主題的表652的數據結構的示例實施例的框圖。在各種實施例中，表652可包括圖6a所示的摺疊的稀疏LUT的實施例。在各種實施例中，可針對每次除法或平方根運算或指令產生稀疏LUT 652。

在示出的實施例中，摺疊的稀疏LUT 652可包括非負(即，正值和零值)行和負行。在這樣的實施例中，可應用偏移(例如，0.25等)以對行(例如，負行等)進行移位，使得他們對齊並且對稱。

在行666和668中可見這種對稱的對齊。對於行666，正行+1.50具有個性關鍵字(p關鍵字[9:8])的第九位和第八位的值，同樣，移位的或偏移的負行-1.750具有個性關鍵字(p關鍵字[9:8])的第九位和第八位的值。同樣，對於行668，正行+1.75具有個性關鍵字(p關鍵字[7：6])的第七位和第六位的值，並且移位的或偏移的負行-2.00具有個性關鍵字(p關鍵字[7:6])的第七位和第六位的值。此外，在該實施例中，+0.00行和-5.50行現在分別在-0.25行和+5.25行具有等同的配對物。需理解，以上僅是一些說明性示例，公開的主題不限於此。

圖7是根據公開的主題的系統的示例實施例的框圖。在各種實施例中，系統700可以是圖2的系統的局部實施例的特定示例。在示出的實施例中，示出了摺疊稀疏LUT 790的示例。

在示出的實施例中，示出了10行摺疊稀疏LUT 790。此外，行索引已經從6位減少到5位。行索引的MSB包括符號位，並且通過只將負行摺疊到非負行，(在行索引中)不需要符號位。可仍然使用符號位來指示應被反向的行(或部分餘數的MSB)，但是，一旦行被反向(為非負值)，行索引的MSB可被忽略。該反向(由緊挨著行觸發器299的反向器799示出)可從摺疊稀 疏LUT 790處理邏輯的關鍵路徑中去除多路復用電平。因此，可進一步降低處理摺疊稀疏LUT 790的邏輯的複雜度。

在示出的實施例中，對於示出的列0000，摺疊稀疏LUT 790可包括下面的行和條目：

000.0？＝0b00

000.10＝key[10]，與0b0連接

000.11＝0b01

001.0？＝0b01

001.10＝key[9:8]

001.11＝key[7:6]

010.00＝key[5:4]

010.01＝key[3:2]

010.10＝key[1:0]

011.1？＝0b01

因此，摺疊稀疏LUT 790可包括均為2位的10個條目，或者共計20位。與全部704個條目的PD LUT相比，這可以是根本的節省。需理解，以上僅是一個說明性示例，公開的主題不限於此。

在各種實施例中，可使用其他列或除數。此外，雖然示出的示例展現基數4的實施例的使用，但是需理解，可將個性關鍵字和摺疊稀疏LUT的原理應用於其他基數實施方式。例如，可以看到對於更高的基數(諸如，基數8、16或32)的除法運算的益處。潛在地，可採用可能非常高的基數的運算(例如，64和128等)。

圖8是可包括根據公開的主題的原理而形成的半導體裝置的信息處理系統800的示意性框圖。

參照圖8，信息處理系統800可包括根據公開的主題的原理而構造的一個或多個裝置。在另一個實施例中，信息處理系統800可採用或執行根據公開的主題的原理的一個或多個技術。

在各種實施例中，信息處理系統800可包括計算裝置(例如，諸如筆記本電腦、桌上型電腦、工作站、伺服器、刀片式伺服器、個人數字助手、智慧型電話、平板電腦以及其他合適的計算機等)或者虛擬機或其虛擬計算裝置。在各種實施例中，信息處理系統800可由用戶(未示出)使用。

根據公開的主題的信息處理系統800還可包括中央處理器(CPU)、邏輯或處理器810。在一些實施例中，處理器810可包括一個或多個功能單元塊(FUB)或組合邏輯塊(CLB)815。在這樣的實施例中，組合邏輯塊可包括各種布爾邏輯運算(例如，NAND(與非)、NOR(或非)、NOT(非)、XOR(異或)等)、穩定邏輯裝置(例如，觸發器、鎖存器等)、其他邏輯裝置或它們的組合。這些組合邏輯運算可被配置為以簡單或複雜的方式處理輸入信號來獲得期望的結果。需理解，儘管描述了一些同步組合邏輯運算的說明性示例，但是公開的主題不受此限制並且可包括異步運算或它們的混合。在一個實施例中，組合邏輯運算可包括多個互補金屬氧化物半導體(COMS)電晶體。在各種實施例中，可將這些COMS電晶體布置到執行邏輯運算的門中；但是需理解，其他技術可被使用並且在公開的主題的範圍內。

根據公開的主題的信息處理系統800還可包括易失性存儲器820(例如，隨機存取存儲器(RAM)等)。根據公開的主題的信息處理系統800還可包括非易失性存儲器830(例如，硬碟驅動器、光學存儲器、NAND或閃速存儲器等)。在一些實施例中，易失性存儲器820、非易失性存儲器830或它們的組合或部分可被稱為「存儲介質」。在各種實施例中，易失性存儲器820和/或非易失性存儲器830可被配置為以半永久或基本上永久的形式存儲數據。

在各種實施例中，信息處理系統800可包括：一個或多個網絡接口840，被配置為允許信息處理系統800通過通信網絡而成為通信網絡的一部分並進行通信。Wi-Fi協議的示例可包括(但不限於)電氣和電子工程師協會(IEEE)802.11g，IEEE 802.11n等。蜂窩協議的示例可包括(但不限於)IEEE 802.16m(亦稱，先進無線MAN(城域網))、先進長期演進(LTE)、增強型數據速率的GMS(全球移動通信系統)演進(EDGE)、演化高速分組接入(HSPA+)等。有線協議的示例可包括(但不限於)IEEE 802.3(亦稱，乙太網)、光纖通道和電力線通信(例如，電力貓(HomePlug)，IEEE 1901等)等。需理解，以上僅是一些說明性示例，公開的主題不限於此。

根據公開的主題的信息處理系統800還可包括用戶接口單元850(例如，顯示適配器、觸覺接口、人機接口裝置等)。在各種實施例中，該用戶接口單元850可被配置為從用戶接收輸入和/或為用戶提供輸出。也可使用其他種類的裝置來提供與用戶的交互；例如，向用戶提供的反饋可以是任何形式的感知反饋(例如，視覺反饋、聽覺反饋或觸覺反饋)；並且可以以任何方式接收 來自用戶的輸入(包括聲音、語音或觸覺輸入)。

在各種實施例中，信息處理系統800可包括一個或多個其他裝置或硬體組件860(例如，顯示器或監視器，鍵盤，滑鼠，相機，指紋讀取器，視頻處理器等)。需理解，以上僅是一些說明性示例，公開的主題不限於此。

根據公開的主題的信息處理系統800還可包括一條或多條系統總線805。在這樣的實施例中，系統總線805可被配置為通信地連接處理器810、易失性存儲器820、非易失性存儲器830、網絡接口840、用戶接口單元850和一個或多個硬體組件860。可將由處理器810處理的數據或從非易失性存儲器830的外部輸入的數據存儲在非易失性存儲器830或易失性存儲器820中。

在各種實施例中，信息處理系統800可包括或執行一個或多個軟體組件870。在一些實施例中，軟體組件870可包括作業系統(OS)和/或應用。在一些實施例中，OS可被配置為向應用提供一個或多個服務，並管理信息處理系統800的應用和各種硬體組件(例如，處理器810、網絡接口840等)或充當信息處理系統800的應用和各種硬體組件之間的中介。在這樣的實施例中，信息處理系統800可包括一個或多個本地應用，本地應用可被安裝在本地(例如，在非易失性存儲器內等)，並被配置為由處理器810直接執行並與OS直接交互。在這樣的實施例中，本地應用可包括預編譯的機器可執行代碼。在一些實施例中，本地應用可包括被配置為將原始碼或目標代碼轉換為隨後由處理器810執行的可執行代碼的腳本解釋器(例如，C shell(csh)、AppleScript、AutoHotkey等)或虛擬執行機(VM)(例如，Java虛擬機、微軟公共語言運行庫等)。

上述半導體裝置可使用各種封裝技術進行封裝。例如，根據公開的主題的原理構造的半導體裝置可通過使用以下任何一種技術或本領域普通技術人員所公知的其他技術進行封裝：層疊封裝(POP)技術、球柵陣列(BGA)技術、晶片級封裝(CSP)技術、塑料引線晶片載體(PLCC)技術、塑料雙列直插式封裝(PDIP)技術、裸片格柵技術、裸片級晶片形式技術、板上晶片(COB)技術、陶瓷雙列直插式封裝(CERDIP)技術、塑料方形扁平封裝(公制)(PMQFP)技術、塑料方形扁平封裝(PQFP)技術、小外形封裝(SOIC)技術、緊縮型小外形封裝(SSOP)技術、薄型小外形封裝(TSOP)技術、薄型方形扁平封裝(TQFP)技術、系統級封裝(SIP)技術、多晶片封裝(MCP)技術、晶圓級封裝(WFP)技術、晶圓級處理堆棧封裝(WSP)技術。

方法步驟可由執行電腦程式以通過操作輸入數據並產生輸出來執行功能的一個或多個可編程處理器執行。方法步驟還可由專用邏輯電路(例如，FPGA(現場可編程門陣列)或ASIC(應用專用集成電路))執行，並且設備可被實現為專用邏輯電路。

在各種實施例中，計算機可讀介質可包括指令，當所述指令被執行時，使裝置執行所述方法步驟的至少一部分。在一些實施例中，計算機可讀介質可被包括在磁介質、光學介質、其他介質或它們的組合(例如，CD-ROM、硬碟驅動器、只讀存儲器、快閃記憶體驅動器等)中。在這樣的實施例中，計算機可讀介質可以是有形和非暫時性地實現的製造品。

雖然已經參照示例實施例對公開的主題的原理進行了描述，但是本領域技術人員將清楚，在不脫離這些公開的構思的精神和範圍的情況下，可對示例實施例進行各種改變和修改。因此，應理解，上述實施例不是限制性的，而僅是說明性的。因此，公開的構思的範圍將由權利要求及其等同物的最寬泛的可允許的解釋來確定，而不應該被前述的描述所局限或限制。因此，將理解，權利要求旨在覆蓋落入實施例的範圍之內的所有修改和改變。