TW201810019A

TW201810019A - 浮點除法器以及浮點除法器操作方法

Info

Publication number: TW201810019A
Application number: TW105138802A
Authority: TW
Inventors: 陳靜; 張稚
Original assignee: 上海兆芯集成電路有限公司
Priority date: 2016-06-22
Filing date: 2016-11-25
Publication date: 2018-03-16
Also published as: TWI606391B; CN106020769A; CN106020769B

Abstract

一種浮點除法器，除了根據一第一部分餘數、一除數以及一第一商值產生一第二部分餘數，更根據該第二部分餘數、該除數以及複數個第二商值待測值產生複數個第三部分餘數候選。一第一商值表格經查詢，除了供應對應該第二部分餘數以及該除數的一第二商值，更供應對應該等第三部分餘數候選以及該除數的複數個第三商值候選。一第一多工器自該等第三商值候選中選擇對應該第二商值者作為一第三商值。該第三商值用作下一輪運算的結合商值的部分位元、或是用作當輪之結合商值的部分位元但更用於預測下一輪運算所需內容。

Description

浮點除法器以及浮點除法器操作方法

本案係關於浮點除法器(floating-point dividers)。

浮點除法器需要反覆疊代進行多輪的商值計算。然而，面對大基數(radix)的設計需求，浮點除法器每輪計算出的商值具有相當多的位元數量，邏輯電路設計相當冗雜。

本案提出一種浮點除法器，將多次查表獲得的短位元量商值在一輪運算中組合在一起，呈長位元量的結合商值輸出，其中各輪運算更包括預測下一輪運算所得的結合商值的部分位元。

根據本案一種實施方式所實現一浮點除法器包括一當輪部分餘數產生器、一部分餘數模擬器、一第一商值表格以及一第一多工器。該當輪部分餘數產生器根據一第一部分餘數、一除數以及一第一商值，產生一第二部分餘數。該部分餘數模擬器，根據該第二部分餘數、該除數以及複數個第二商值待測值，產生複數個第三部分餘數候選。該第一商值表格經查詢，供應對應該第二部分餘數以及該除數的一第二商值。該第一商值表格更經查詢，供應對應該等第三部分餘數候選以及該除數的複數個第三商值候選。該第一多工器自該等第三商值候選中選擇對應該第二商值者輸出，作為一第三商值。該第三商值用作下一輪運算的結合商值的部分位元、或是用作當輪之結合商值的部分位元但更用於預測下一輪運算所需內容。

根據本案一種實施方式所實現的一種浮點除法器操作方法，用以操作包括一第一商值表格的一浮點除法器，包括：根據一第一部分餘數、一除數以及一第一商值，產生一第二部分餘數；根據該第二部分餘數、該除數以及複數個第二商值待測值，產生複數個第三部分餘數候選；查詢該第一商值表格，供應對應該第二部分餘數以及該除數的一第二商值；查詢該第一商值表格，供應對應該等第三部分餘數候選以及該除數的複數個第三商值候選；以及提供一第一多工器，自該等第三商值候選中選擇對應該第二商值者輸出，作為一第三商值。該第三商值用作下一輪運算的結合商值的部分位元、或是用作當輪之結合商值的部分位元但更用於預測下一輪運算所需內容。

本案使得浮點除法器的一輪運算不只進行一次商值表格查詢。多次獲得的商值表格查詢結果可結合，在浮點除法器的一輪運算中作結合商值輸出。基數較大的浮點除法器在每輪運算所應輸出的長位元商值因而可由查表獲得的多個短位元數據結合。此外，本案浮點除法器的各輪運算更包括預測下一輪運算所輸出之結合商值的部分位元，其效率遠優於傳統浮點除法器架構。

下文特舉實施例，並配合所附圖示，詳細說明本發明內容。

200‧‧‧浮點除法器

202‧‧‧當輪部分餘數產生器

204‧‧‧部分餘數模擬器

206‧‧‧第一商值表格

207‧‧‧第一多工器

208‧‧‧第二商值表格以及第二多工器

210‧‧‧商值轉換器

212‧‧‧後續輪部分餘數產生器

400‧‧‧浮點除法器

410‧‧‧部分餘數模擬器

420‧‧‧第一商值表格以及第一多工器

430‧‧‧商值轉換器

440‧‧‧後續輪部分餘數產生器

d‧‧‧除數

Q‧‧‧結合商數

q0…q3、q(i+1)、qa、qb、qc、qan‧‧‧商值

qp1…qpN‧‧‧第二/第三商值待測值

S1…S3、S(i+1)、Sa、Sb、San‧‧‧部分餘數

S302…S314、S502…S518‧‧‧步驟

San1…SanN、Sc1…ScN、San11…San1N、…、SanN1…SanNN‧‧‧部分餘數候選

qan1…qanN‧‧‧第三商值候選

w‧‧‧被除數

w0…w2、w(i+1)‧‧‧中間餘數

第1A圖舉例說明除法運算的各運算元；第1B圖以及的1C圖以二維座標顯示商值表格；第2圖根據本案一種實施方式圖解一浮點除法器200；第3圖為流程圖，圖解第2圖浮點除法器200的操作方法，以提供一除法運算(w/d)；第4圖根據本案另一種實施方式圖解一浮點除法器400；以及第5A、5B圖為流程圖，圖解第4圖浮點除法器400的操作方法，以提供一除法運算(w/d)。

以下敘述列舉本發明的多種實施例。以下敘述介紹本發明的基本概念，且並非意圖限制本發明內容。實際發明範圍應依照申請專利範圍界定之。

第1A圖舉例說明一除法運算的各運算元，包括被除數w以及除數d，運算中依序獲得商值q0、q1、q2、q3。值得注意的是，這裡運算得到4個商值q0~q3僅為示例，本發明並不限於此，商值的數量由除數w何時被除數d除盡或者收斂決定，因此除法運算很可能獲得其它數量的商值，並不限於4個。本實施例採基數(radix)4，即每個時鐘週期產生2位元的商值。商值q0、q1、q2、q3運算期間需將中間餘數wi的小數點向右移位2位元(即4×wi)，i為編號。本案將數值wi以及4×wi都稱為部分餘數(partial remainder)，標號S(i+1)。商值q(i+1)可根據部分餘數S(i+1)與除數d以查表方式獲得。

第1B圖以二維座標顯示一商值表格。一種查表方式係利用部分餘數4×wi(即S(i+1))查表，將部分餘數4×wi(即S(i+1))與除數d的各種倍數比較，即可獲得對應的商值q(i+1)線條。在商值q(i+1)線條上，呈現為除數d的一定倍數的部分餘數4×wi，在一定範圍內的商值q(i+1)相同，如第1B圖中，呈現為[-d,d]區間內的部分餘數4×wi對應商值q(i+1)=0。下面結合第1A圖具體說明如何查詢商值表格獲得對應的商值，例如部分餘數4×w0=1.110101B1.75D(其中B代表二進制數，D代表十進制數)，除數d=1.101B1.625D，則部分餘數4×w0呈現為除數d的大約1.08倍，因此查詢第1B圖中的商值表格可知對應商值q1=1。部分餘數4×wi(即S(i+1))軸上更可設計多個臨界值，使得對應多條商值q(i+1)線條的部分餘數4×wi得以正確自該等商值q(i+1)線條選出正確對應者。第1C圖以另一種二維座標顯示一商值表格，其中是採用wi為部分餘數，即S(i+1)軸上的值係wi的值，利用部分餘數wi查表，將部分餘數wi與除數d的各種倍數比較，即可獲得對應的商值q(i+1)線條。第1B圖、或第1C之商值表格是用來根據部分餘數S(i+1)以及除數d查表獲得商值q(i+1)。以上商值表格概念可使用在各種基數的浮點除法器應用中。本實施例採基數(radix)4，即每個時鐘週期產生2位元的商值，如果每時鐘週期只能查詢一次商值表格，則商值的取值範圍為{-2,-1,0,1,2}。在採用其他基數的實施例中，例如採基數16，則每個時鐘週期產生4位元的商值，如果每時鐘週期只能查詢一次商值表格，則商值的取值範圍為{-15,-14,-13,-12,...-1,0,1,...12,13,14,15}，即[-15,15]，但本發明並不限於此，採取不同的商值編碼方式時，商值的取值範圍會有所不同。浮點除法運算中查詢商值表格比較耗時，而且每次查表得到的商值位元數越多，則硬件開銷越大。因此本發明提出了一種一輪運算進行多次商值表格查詢的浮點除法器，即使採用硬件開銷較小的商值表格，舉例而言，即使採用每次查表僅能得到2位元的商值的表格(例如查詢圖1B的商值表格)，一輪運算查詢兩次也可以得到4位元的商值，即實現基16，例如SRT-16，而不必採用硬件開銷較大的商值取值範圍為[-15,15]的商值表格。

本案使得浮點除法器的一輪運算不只進行一次商值表格查詢。多次獲得的商值表格查詢結果可結合，在浮點除法器的一輪運算中作結合商值輸出。基數較大的浮點除法器在每輪運算所應輸出的長位元商值因而可由查表獲得的短位元數據結合。此外，本案浮點除法器的各輪運算更包括預測下一輪運算所輸出之結合商值的部分位元，其效率遠優於傳統浮點除法器架構。

第2圖根據本案一種實施方式圖解一浮點除法器200，包括一當輪部分餘數產生器202、一部分餘數模擬器204、一第一商值表格206以及一第一多工器207、一第二商值表格以及一第二多工器(結合以方塊208表示)、一商值轉換器210、以及一後續輪部分餘數產生器212。

該當輪部分餘數產生器202根據一第一部分餘數Sa、一除數d以及一第一商值qa產生一第二部分餘數Sb。該部分餘數模擬器204根據該第二部分餘數Sb、該除數d以及複數個第二商值待測值qp1…qpN產生複數個第三部分餘數候選San1…SanN。該等第二商值待測值qp1…qpN可為第二商值qb的所有可能數值，舉例而言，qp1…qpN取值為圖1B或圖1C的商值表格中所有可能的商值。該第一商值表格206經查詢，供應對應該第二部分餘數Sb以及該除數d的一第二商值qb。該第一商值表格206更用於查詢供應對應該等第三部分餘數候選San1…SanN以及該除數d的複數個第三商值候選qan1…qanN，交由該第一多工器207根據該第二商值qb從該等第三商值候選qan1…qanN中選擇對應該第二商值qb的一個輸出，作為一第三商值qan，即選擇該第二商值qb(作為複數個第二商值待測值qp1…qpN之一)所對應的第三部分餘數候選(San1…SanN之一)所對應的第三商值候選(qan1…qanN之一)作為第三商值qan。特別是，該第二商值表格以及第二多工器(208)是在該浮點除法器200的一第一輪運算中使用，對應一被除數w以及該除數d供應上述第一商值qa以及該第一部分餘數Sa至該當輪部分餘數產生器202。如圖所示，商值轉換器210於各輪運算中，將各提供M位元資訊的該第一商值qa以及該第二商值qb轉換結合成為2M位元的結合商值Q，上述M為數值。至於該第三商值qan，此實施例係將之用作下一輪結合商值Q的部分位元。該第三商值qan將經方塊208內的該第二多工器切換供應作為下一輪運算使用的該第一商值qa。至於下一輪結合商值Q運算所需要的該第一部分餘數Sa，則是由該後續輪部分餘數產生器212提供。該後續輪部分餘數產生器212係根據該第二部分餘數Sb、該除數d以及該第二商值qb產生一第三部分餘數San，經方塊208內的該第二多工器切換供應作為下一輪運算所需要的該第一部分餘數Sa。如前所述，第二商值表格以及第二多工器(208)僅在該浮點除法器200的第一輪運算中供被除數w以及除數d查詢獲得第一部分餘數Sa及第一商值qa使用；而後續輪的運算中，無需使用方塊208中的該第二商值表格，而是由方塊208中的該第二多工器直接選擇前一輪運算所得的第三商值qan作為本輪運算的第一商值qa，並且選擇前一輪運算所得的第三部分餘數San作為本輪運算的第一部分餘數Sa。

在一實施例中，該當輪部分餘數產生器202、該部分餘數模擬器204、以及該後續輪部分餘數產生器212都是基於r×wi-q(i+1)×d=w(i+1)運算而設計，其中r為中間餘數wi移位位元量。例如第1A圖的實施例中，r取值為4，w(i+1)=4×wi-q(i+1)×d，而部分餘數S(i+1)=4×wi，具體舉例而言，d=1.101B，並且根據第一部分餘數S1=4×w0=1.110101B查詢商值表格得到q1=1；則w1=4×w0-q1×d=1.110101B-1×1.101B=0.001101B，則第二部分餘數S2=4×w1=0.1101B。視部分餘數S(i+1)的不同定義方式(如，S(i+1)=r×wi或S(i+1)=wi)，該當輪部分餘數產生器202、該部分餘數模擬器204以及該後續輪部分餘數產生器212的邏輯電路設計會相應調整。該當輪部分餘數產生器202、該部分餘數模擬器204以及該後續輪部分餘數產生器212可使用串行加法器、加法器、以及乘法器…等邏輯運算元件實現上述r×wi-q(i+1)×d=w(i+1)運算，使根據部分餘數S(i+1)(即r×wi或wi)、除數d以及商值q(i+1)輸出部分餘數S(i+2)(即r×w(i+1)或w(i+1))。第一商值表格206 也是視部分餘數定義而建立。

以基數256為例，浮點除法器200各輪運算應當輸出的結合商值Q為8位元，其中較高4位元由第一商值qa提供，較低4位元由第二商值qb提供。4位元的商值運算遠較8位元硬件開銷小且簡易，其中對中間餘數wi的位移量僅2⁴位元，遠低於傳統浮點除法器架構所需要的2⁸位元。此外，關於基數256的浮點除法器200架構，第二商值待測值qp1…qpN可設定為{-15,-14,-13,-12,...-1,0,1,...12,13,14,15}如此31個數值，以估算出31個第三部分餘數候選。當然，本發明並不限於關於基數256的商值範圍為[-15,15]，採取不同的商值編碼方式時，商值的取值範圍會有所不同，為[-N,N]一共2N+1个數值，其中N{8,9,10,11,12,13,14,15}。

第3圖為流程圖，圖解第2圖浮點除法器200的操作方法，以提供一除法運算(w/d)。

步驟S302接收被除數w與除數d，據以查詢方塊208內的第二商值表格獲得第一商值qa。步驟S304操作該當輪部分餘數產生器202根據被除數w(作為第一輪結合商值Q運算的第一部分餘數Sa)、除數d以及第一商值qa產生第二部分餘數Sb。步驟S306操作該部分餘數模擬器204根據第二部分餘數Sb、除數d以及第二商值待測值qp1…qpN產生第三部分餘數候選San1…SanN。步驟S308根據第二部分餘數Sb以及除數d，查詢第一商值表格206獲得第二商值qb。步驟S310根據第三部分餘數候選San1…SanN以及除數d，查詢第一商值表格206獲得第三商值候選qan1…qanN，交由第一多工器207根據步驟S308產生的第二商值qb從該等第三商值候選qan1…qanN中選擇對應該第二商值qb的一個輸出，作為第三商值qan。步驟S312操作後續輪部分餘數產生器212根據第二部分餘數Sb、除數d以及第二商值qb產生第三部分餘數San。步驟S314中，上述第三商值qan以及第三部分餘數San經方塊208內的該第二多工器交由該當輪部分餘數產生器202分別作為浮點除法器200新一輪運算所需的第一商值qa以及第一部分餘數Sa，即是說，上一輪運算產生的第三商值qan作為新一輪運算所需的第一商值qa，上一輪運算產生的第三部分餘數San作為新一輪運算所需的第一部分餘數Sa，據以產生該新一輪運算的第二部分餘數Sb，進而流程重回步驟S306。第3圖所示流程可循環運作直至部分餘數位元數不足。所揭露之除法流程將在各輪運算中取得第一商值qa以及第二商值qb，轉換結合為結合商值Q。不同輪運算獲得的所有結合商值Q將再結合成為除法運算w/d的結果。其他實施方式中，步驟S308可以安排在步驟S306之前，或是安排在步驟S310之中，即步驟S306和步驟S308不分先後順序。

第4圖根據本案另一種實施方式圖解一浮點除法器400，相較於浮點除法器200對應修正提供部分餘數模擬器410、第一商值表格以及第一多工器(結合以方塊420表示)、商值轉換器430、以及後續輪部分餘數產生器440，使每輪運算所獲得的結合商值Q是由三個商值qa、qb以及qc結合轉換成。

部分餘數模擬器410除了根據該第二部分餘數Sb、該除數d以及複數個第二商值待測值qp1…qpN產生複數個第三部分餘數候選Sc1…ScN，更根據該等第三部分餘數候選 Sc1…ScN、該除數d以及複數個第三商值待測值(此例同樣為qp1…qpN)產生複數個第四部分餘數候選San11…San1N、…、SanN1…SanNN。方塊420內的該第一商值表格經查詢，供應對應該第二部分餘數Sb以及該除數d的一第二商值qb；方塊420內的該第一商值表格更被查詢，對應該等第三部分餘數候選Sc1…ScN以及該除數d供應複數個第三商值候選qc1…qcN(圖未示出)交由方塊420內的第一多工器根據第二商值qb從該等第三商值候選qc1…qcN中選擇對應該第二商值qb的一個輸出為一第三商值qc，即先選擇該第二商值qb(作為複數個第二商值待測值qp1…qpN之一)所對應的第三部分餘數候選(Sc1…ScN之一)所對應的第三商值候選(qc1…qcN之一)作為第三商值qc。此外，方塊420內的第一商值表格更被查詢，根據該等(N×N個)第四部分餘數候選San11…San1N、…、SanN1…SanNN以及該除數d，供應複數個第四商值候選qan11…qan1N、…、qanN1…qanNN(圖未示出)，交由方塊420內的第一多工器對應該第二商值qb以及該第三商值qc擇一作為一第四商值qan輸出。具體舉例而言，方塊420內的第一多工器根據查表所得的第二商值qb選擇該第二商值qb(作為複數個第二商值待測值qp1…qpN之一)所對應的第三部分餘數候選(Sc1…ScN之一)所對應那N個第四部分餘數候選(San11…San1N、…、SanN1…SanNN中的一組，例如為Sani1…SaniN)；再根據查表所得的第三商值qc從前述所選擇的那N個第四部分餘數候選(如前為Sani1…SaniN)中選擇該第三商值qc(作為複數個第三商值待測值，同樣為qp1…qpN之一)所對應的第四部分餘數候選(為Sani1…SaniN之一)所對應的那個第四商值候選(為qani1…qaniN之一)作為第四商值qan輸出。在其他實施方式中，第二商值qb可更輸入該部分餘數模擬器410，使該部分餘數模擬器410不再冗餘提供該等第三部分餘數候選Sc1…ScN中以及該等第四部分餘數候選San11…San1N、…、SanN1…SanNN中不對應該第二商值qb者。

至於該商值轉換器430，係設計於各輪運算中，將各提供M位元資訊的該第一商值qa、該第二商值qb以及該第三商值qc轉換結合成為3M位元的結合商值Q，上述M為數值。以基數2⁹為例，浮點除法器400可在各輪運算中產生9位元的結合商值Q，是由3位元的第一商值qa、3位元的第二商值qb以及3位元的第三商值qc結合轉換而得。

後續輪部分餘數產生器440動作如下。根據該第二部分餘數Sb、該除數d以及該第二商值qb，該後續輪部分餘數產生器440產生一第三部分餘數Sc(於方塊440內部，圖未示出)，且更根據該第三部分餘數Sc(圖未示出)、該除數d以及該第三商值qc，產生一第四部分餘數San。浮點除法器400產生的第四商值qan以及第四部分餘數San是由方塊208內的該第二多工器於該浮點除法器400的第一輪運算後，切換輸出作下一輪運算所需的上述第一商值qa以及第一部分餘數Sa。相較於浮點除法器200，浮點除法器400產生的第三商值qc是用作當輪之結合商值Q的部分位元，但更用於預測下一輪運算所需內容(例如，qan與San係基於qc獲得)。相較於浮點除法器200，浮點除法器400在同一輪運算中，並行進行了3次商值表格查詢的動作，其中部分餘數模擬器410進行運算產生N個第三部分餘數候選Sc1…ScN，又接著根據所產生的N個第三部分餘數候選Sc1…ScN進行嵌套運算產生N×N個第四部分餘數候選San11…San1N、…、SanN1…SanNN，由確定的qb和qc作為方塊420中第一多工器中的多工器邏輯的選擇信號，從N×N個第四部分餘數候選San11…San1N、…、SanN1…SanNN對應的N×N個q值中選擇的一個作為qan輸出。第4圖的實施例將比較耗時的輸出qb、qc和qan的三次商值表格查詢操作並列進行，使其得以在同一輪運算中完成，較先前技術之必須等待第一輪查表得第二商值qb之後，再由第二商值qb計算第三部分餘數Sc以進行第二輪查表得由第三商值qc，之後再由第三商值qc計算第四部分餘數San以進行第三輪查表得qan，耗時大大降低。

第5A、5B圖為流程圖，圖解第4圖浮點除法器400的操作方法，以提供一除法運算(w/d)。

步驟S502接收被除數w與除數d，據以查詢方塊208內的第二商值表格獲得第一商值qa。步驟S504操作該當輪部分餘數產生器202根據被除數w(作為第一輪結合商值Q運算的第一部分餘數Sa)、除數d以及第一商值qa產生第二部分餘數Sb。步驟S506操作該部分餘數模擬器410根據第二部分餘數Sb、除數d以及第二商值待測值qp1…qpN產生第三部分餘數候選Sc1…ScN。步驟S508再次操作該部分餘數模擬器410根據第三部分餘數候選Sc1…ScN、除數d以及第三商值待測值(此例同為qp1…qpN)產生第四部分餘數候選San11…San1N、…、SanN1…SanNN。步驟S510根據第二部分餘數Sb以及除數d，查詢方塊 420內的第一商值表格獲得第二商值qb。步驟S512根據第三部分餘數候選Sc1…ScN以及除數d，查詢方塊420內的第一商值表格獲得第三商值候選qc1…qcN，交由方塊420內的第一多工器根據步驟S510產生的第二商值qb從該等第三商值候選qc1…qcN中選擇對應該第二商值qb的一個輸出，作為第三商值qc。步驟S514根據第四部分餘數候選San11…San1N、…、SanN1…SanNN(N×N個)以及除數d，查詢方塊420內的第一商值表格獲得第四商值候選qan11…qan1N、…、qanN1…qanNN(N×N個)，交由方塊420內的第一多工器選擇對應第二以及第三商值qb與qc者輸出，作為第四商值qan。步驟S516操作後續輪部分餘數產生器440根據第二部分餘數Sb、除數d以及第二商值qb產生第三部分餘數Sc(於方塊440內部)，且更根據該第三部分餘數Sc、該除數d以及該第三商值qc，產生第四部分餘數San。步驟S518中，上述第四商值qan以及第四部分餘數San經方塊208內的該第二多工器交由該當輪部分餘數產生器202分別作為浮點除法器400新一輪運算所需的第一商值qa以及第一部分餘數Sa，據以產生該新一輪運算的第二部分餘數Sb，進而流程重回步驟S506。第5A、5B圖所示流程可循環運作直至部分餘數位元數不足。所揭露之除法流程將在各輪運算中取得第一商值qa、第二商值qb以及第三商值qc，操作商值轉換器430轉換結合為結合商值Q。不同輪運算獲得的所有結合商值Q將再結合成為除法運算w/d的結果。其他實施方式中，步驟S510與S512可微調至前或後步驟。

在其他實施方式中，部分餘數模擬器所可以模擬的商值數量，可不只於第2圖所示之一個(qan)或第4圖所示之兩個(qc與qan)。依照上述同樣概念，部分餘數模擬器甚至可模擬多於兩個的商值。

雖然本發明已以較佳實施例揭露如上，然其並非用以限定本發明，任何熟悉此項技藝者，在不脫離本發明之精神和範圍內，當可做些許更動與潤飾，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。