EP0990981B1 - Multiplieur à grande vitesse - Google Patents

Multiplieur à grande vitesse Download PDF

Info

Publication number
EP0990981B1
EP0990981B1 EP99307627A EP99307627A EP0990981B1 EP 0990981 B1 EP0990981 B1 EP 0990981B1 EP 99307627 A EP99307627 A EP 99307627A EP 99307627 A EP99307627 A EP 99307627A EP 0990981 B1 EP0990981 B1 EP 0990981B1
Authority
EP
European Patent Office
Prior art keywords
multiplicand
multiplier
product
cache
memory
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
EP99307627A
Other languages
German (de)
English (en)
Other versions
EP0990981A2 (fr
EP0990981A3 (fr
Inventor
Thi N. Nguyen
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
STMicroelectronics lnc USA
Original Assignee
STMicroelectronics lnc USA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by STMicroelectronics lnc USA filed Critical STMicroelectronics lnc USA
Publication of EP0990981A2 publication Critical patent/EP0990981A2/fr
Publication of EP0990981A3 publication Critical patent/EP0990981A3/fr
Application granted granted Critical
Publication of EP0990981B1 publication Critical patent/EP0990981B1/fr
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
    • G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
    • G06F7/52—Multiplying; Dividing
    • G06F7/523—Multiplying only
    • G06F7/53—Multiplying only in parallel-parallel fashion, i.e. both operands being entered in parallel

Definitions

  • the present invention relates to a high speed multiplier and specifically to a high speed multiplier that utilizes cache memory searches for previous results.
  • the multiplier would be well suited for various digital signal processing (DSP) applications,
  • DSP digital signal processing
  • the basic design for each multiplier is an add and shift algorithm. This algorithm generates a partial product, using Booth's algorithm for example, and then adding a partial product using a ROM look up table.
  • the multiplier is consisting of a fast adder, multiplexer (mux) and shift register.
  • An example of a 4 X 4 multiplier is following:
  • Two registers 202, 204 are used to hold the value of the multiplier and the multiplicand as shown in Figure 2.
  • the multiplier register 202 is shifted into the control logic. If multiplier bit n is a zero, the multiplexer (mux) 216 will select a zero output. Otherwise the mux will select the multiplicand output.
  • the shift register will shift the mux output to n-1 bit to the left.
  • the adder 212 will add this with the partial register 210 that has the initial value of zero. After N iterations the adder 212 will output the final product 214 From the above example, there are N iterations for an N x N multiple. Thus, for a 30-bit by 30-bit multiplication, there would be 30 iterations. Likewise, for a 60 x 60 multiplication, there would be 60 iterations. A need exists to perform these multiplications with fewer iterations.
  • US 5,343,416 describes an apparatus for reconfiguring a partial product reduction tree.
  • a cache memory is described which comprises storage for a divisor field.
  • the divisor is fed to the cache memory and compared with the existing divisor field.
  • the reciprocal of the divisor is read from the cache memory instead of being calculated, thus saving valuable computer resources in the division operation.
  • GB 2,184,269 describes a VLSI ROM-based multiplier having two ROMs to which the bits of an input number are alternately applied as an address.
  • the ROM sections are identical and operative as "look-up tables" to multiply the bits applied thereto by a multiplying factor.
  • a high speed multiplier for calculating the product of a multiplicand and a constant multiplier in a digital signal processing environment, comprising a memory for storing a first multiplication result equal to a product of a first multiplicand and the constant multiplier, said memory capable of retrieving the first multiplication result if a cache lookup bit (CLB) portion of a second multiplicand matches with a cache lookup bit portion of said first multiplicand; a lookup table circuit containing a plurality of sub-products, wherein a first sub-product is equal to a product of the constant multiplier and a first difference value, the first difference value associated with a difference between a first table lookup bit (TLB) portion of the first multiplicand and a second table lookup bit portion of the second multiplicand; and a summation circuit capable of adding the first sub-product to the retrieved first multiplication result to produce a second multiplication result equal to a product of the constant multiplier and the second multiplicand
  • a method of multiplying a multiplicand and a constant multiplier in a digital signal processing environment comprising the steps of: storing a first multiplication result equal to a product of a first multiplicand and the constant multiplier in a memory, retrieving from the memory the first multiplication result if a cache lookup bit (CLB) portion of a second multiplicand matches with a cache lookup bit portion of said first multiplicand; retrieving from a lookup table circuit a first sub-product equal to a product of the constant multiplier and a first difference value, the first difference value associated with a difference between a first table lookup bit (TLB) portion of the first multiplicand and a second table lookup bit (TLB) portion of the second multiplicand; and adding the first sub-product to the first multiplication result to thereby produce a second multiplication result equal to a product of the constant multiplier and the second multiplicand.
  • CLB cache lookup bit
  • the present invention recognizes that in many circumstances, several multiplication operations are conducted as part of a sequence.
  • the multiplier may be the same for each operation while the multiplicand differs only slightly.
  • the method used to improve the speed of multiplication operations involves dividing the multiplicand into two portions.
  • the first portion is referred to as a cache lookup bit (CLB), while the second portion is referred to as a table lookup bit (TLB).
  • CLB cache lookup bit
  • TLB table lookup bit
  • a 30 bit mulitplicand could be divided into a 24 bit CLB and a 6 bit TLB.
  • the lengths of the CLB and TLB can be varied.
  • the method first compares the CLB of the multiplicand with the previous multiplicand. If the CLB's match, also known as a cache hit, the output data from the cache will add/sub with a value pulled from the TLB RAM lookup for a final product.
  • the RAM lookup table is simply a multiplication table. For example, if the TLB is 4 bits in length then the table will contain the results of values 0 to 16 multiplied with C1.
  • the decision to add or subtract is made from the comparison between the multiplicand TLB and cache TLB address bit. If the multiplicand TLB bit is smaller than the cache TLB address bit, then a subtract operation will be performed. If the TLB bit is equal to the cache TLB bit, then cache output is the final product. If it is bigger, then an add operation will be performed. If no cache hit occurs, also known as a cache miss, then a conventional multiplier will be used to perform the multiplication. The output data from the multiplier can still be used to update the cache and the final product.
  • FIG. 3 illustrates the present invention.
  • the high speed multiplier 300 utilizes a multiplier circuit 306 .
  • This multiplier circuit 306 operates on a multiplicand 302 and a multiplier 304 .
  • the multiplier is designated as a constant.
  • the output is delivered on line 308 .
  • a data valid line 310 is also provided. The data valid line will show a distinct value, such as true, once the necessary number of iterations have occurred. Once this distinct value is detected, then the result on line 308 is the final product.
  • Figure 4 shows an example multiplicand 400 of 30-bit length.
  • the multiplicand is divided into a cache lookup bit (CLB) portion 402 and a table lookup bit (TLB) portion 404 .
  • CLB cache lookup bit
  • TLB table lookup bit
  • Figure 5a illustrates a circuit that could be used to implement the method 500 of the present invention.
  • the CLB of the multiplicand 502 will show less variation than the TLB.
  • the value of the CLB from a previous multiplication can be stored in high speed cache 504 .
  • it could be stored in a content addressable memory (CAM).
  • CAM content addressable memory
  • the cache will be checked to see if the CLB of the multiplicand of the present multiplication is the same as the CLB of the previous operations multiplicand. A cache hit occurs when the CLBs match. If a cache hit occurs, the output data from the cache will add/sub 512 with the TLB RAM lookup 510 for a final product 514 .
  • the decision to add or sub is made from the comparison between the multiplicand TLB and cache TLB. If the multiplicand TLB is smaller than the cache TLB, then a subtract operation will be performed. If the multiplicand TLB is equal to the cache TLB, then cache output is the final product. If it is bigger, then an add operation will be performed. If no cache hit occurs, also known as a cache miss, then a conventional multiplier 506 will be used to perform the multiplication. The output data from the multiplier can still be used to update the cache and the final product.
  • the RAM lookup table 510 is simply a multiplication table. For example, if the TLB is 4 bits in length then the table will contain the results of values 0 to 16 multiplied with C1. For example, address 0 will contain the value of 0*C1, address 1 will contain the result of 1 *C1 and so forth. If the TLB is 4-bit, there is 16 X 33 RAM, a respectively small amount of memory.
  • the following example demonstrates the steps involved with either a cache hit or a cache miss.
  • the desired output is the value of Xn multiplied by C1.
  • the CLB is 0x034 and the TLB is 0x0.
  • the multiplier outputs the final product 0x11100.
  • the cache is updated with address 0x0340, the CLB of the initial multiplicand, and data 0x11100.
  • the CLB is 0x034 and the TLB is 0x2.
  • Cache output is 0x11100, the entry made above.
  • the RAM look up using the TLB is 0xA8.
  • the high speed multiplier is configured to eliminate the decision of either adding or subtracting the value from the RAM lookup table. Instead the system is biased to either always add or always subtract a value from the value retrieved from cache. For example, take the multiplication of 372 by 6 which equals 2232.
  • the CLB can be the first two numbers of the multiplicand, i.e. 37, while the TLB is the last value, i.e. 2. If no cache hit occurs, a standard multiplier is used to produce the result.
  • a new value is formed with the existing CLB 37 and where all additional bits are set at zero, i.e. 370. Then the product of 370 and 6, i.e. 2220, is stored in cache.
  • a cache hit occurs because the CLB 37 is present in both the present and previous multiplication.
  • the product of 2220 is retrieved from cache.
  • the product of the TLB 8 and the constant 6, i.e. 48 is retrieved from the RAM lookup table and added to the retrieved value of 2220 producing a final value of 2268.
  • the values of the non-CLB bits are set to zero, the value from the RAM table is always added to the retrieved value.
  • the value of the non-CLB bits can be set to 9 before the product is stored in cache.
  • the product of 372 times 6 would initially be stored as 379 times 6, i.e. 2274. The difference is then subtracted from 2274.

Landscapes

  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Memory System Of A Hierarchy Structure (AREA)

Claims (12)

  1. Un multiplicateur à grande vitesse (500) pour calculer le produit d'un multiplicande et d'un multiplicateur constant dans un environnement de traitement numérique des signaux, comprenant :
    (a) une mémoire (504) pour enregistrer le résultat d'une première multiplication égal au produit d'un premier multiplicande et du multiplicateur constant (506), ladite mémoire étant capable d'extraire ce premier résultat de multiplication si une portion des bits de recherche en cache (CLB) d'un second multiplicande correspond à une portion des bits de recherche en cache dudit premier multiplicande ;
    (b) un circuit de table de recherche (510) comprenant une pluralité de sous-produits, un premier sous-produit étant égal au produit du multiplicateur constant et d'une première valeur de différence, laquelle valeur de différence est associée à la différence entre une première portion de bits de recherche en table (TLB) du premier multiplicande et une seconde portion de bits de recherche en table du second multiplicande ;
    (c) un circuit de totalisation (512) pouvant ajouter le premier sous-produit au résultat extrait de la première multiplication afin d'obtenir le résultat d'une seconde multiplication égal au produit du multiplicateur constant et du second multiplicande.
  2. Le multiplicateur à grande vitesse de la revendication 1, dans lequel le circuit de totalisation (512) est capable de soustraire le premier sous-produit du résultat de la première multiplication pour obtenir le résultat de la seconde multiplication.
  3. Le multiplicateur à grande vitesse des revendications 1 ou 2, dans lequel la mémoire (504) est une mémoire cache.
  4. Le multiplicateur à grande vitesse des revendications 1 ou 2, dans lequel la mémoire (504) est une mémoire adressable par le contenu (CAM).
  5. Le multiplicateur à grande vitesse de l'une quelconque des revendications précédentes, comprenant en plus un multiplicateur conventionnel (506) à utiliser lorsque la portion des bits de recherche en cache du second multiplicande ne correspond pas à la portion des bits de recherche en cache du premier multiplicande.
  6. Le multiplicateur à grande vitesse de la revendication 1, dans lequel le circuit de recherche en table (510) comprend une mémoire vive (RAM).
  7. Un processeur numérique de signaux comprenant le multiplicateur à grande vitesse (500) de l'une quelconque des revendications précédentes.
  8. Une méthode de multiplication d'un multiplicande et d'un multiplicateur constant dans un environnement de traitement numérique des signaux, comprenant les étapes suivantes :
    enregistrement d'un premier résultat de multiplication égal au produit d'un premier multiplicande et du multiplicateur constant dans une mémoire (504),
    extraction de la mémoire (504) du premier résultat de multiplication si une portion des bits de recherche en cache (CLB) d'un second multiplicande correspond à une portion des bits de recherche en cache dudit premier multiplicande ;
    extraction d'un circuit de recherche en table (510) d'un premier sous-produit égal au produit du multiplicateur constant et d'une première valeur de différence, laquelle valeur de différence est associée à la différence entre une première portion de bits de recherche en table (TLB) du premier multiplicande et une seconde portion de bits de recherche en table du second multiplicande et
    addition (512) du premier sous-produit avec le premier résultat de multiplication pour obtenir un second résultat de multiplication égal à un produit du multiplicateur constant et du second multiplicande.
  9. La méthode de la revendication 7 comprenant en plus une étape de soustraction de la première sous-portion du résultat de la première multiplication pour obtenir le résultat de la seconde multiplication.
  10. La méthode de la revendication 8, dans laquelle la mémoire (504) est une mémoire cache.
  11. La méthode de la revendication 8, dans laquelle la mémoire (504) est une mémoire adressable par le contenu (CAM).
  12. La méthode de la revendication 9, dans laquelle le circuit de recherche en table (510) comprend une mémoire vive (RAM).
EP99307627A 1998-09-30 1999-09-28 Multiplieur à grande vitesse Expired - Lifetime EP0990981B1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US09/164,027 US6298369B1 (en) 1998-09-30 1998-09-30 High speed multiplier
US164027 1998-09-30

Publications (3)

Publication Number Publication Date
EP0990981A2 EP0990981A2 (fr) 2000-04-05
EP0990981A3 EP0990981A3 (fr) 2001-03-07
EP0990981B1 true EP0990981B1 (fr) 2003-03-12

Family

ID=22592660

Family Applications (1)

Application Number Title Priority Date Filing Date
EP99307627A Expired - Lifetime EP0990981B1 (fr) 1998-09-30 1999-09-28 Multiplieur à grande vitesse

Country Status (4)

Country Link
US (1) US6298369B1 (fr)
EP (1) EP0990981B1 (fr)
JP (1) JP2000112714A (fr)
DE (1) DE69905833T2 (fr)

Families Citing this family (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6507629B1 (en) * 1998-04-07 2003-01-14 Sony Corporation Address generator, interleave unit, deinterleave unit, and transmission unit
US6480874B1 (en) * 1999-11-09 2002-11-12 Motorola, Inc. Power saving method for performing additions and subtractions and a device thereof
US6542963B2 (en) * 2001-01-10 2003-04-01 Samsung Electronics Co., Ltd. Partial match partial output cache for computer arithmetic operations
US7296049B2 (en) * 2002-03-22 2007-11-13 Intel Corporation Fast multiplication circuits
US8364670B2 (en) * 2004-12-28 2013-01-29 Dt Labs, Llc System, method and apparatus for electronically searching for an item
US9900314B2 (en) 2013-03-15 2018-02-20 Dt Labs, Llc System, method and apparatus for increasing website relevance while protecting privacy
US10120650B2 (en) 2014-09-30 2018-11-06 Samsung Electronics Co., Ltd. Method and apparatus for calculating data
KR102315278B1 (ko) * 2014-09-30 2021-10-21 삼성전자 주식회사 데이터를 연산하는 방법 및 장치.
US9678749B2 (en) 2014-12-22 2017-06-13 Intel Corporation Instruction and logic for shift-sum multiplier

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2108736B (en) * 1981-10-27 1984-12-12 Standard Telephones Cables Ltd Sum of products multiplier
JPS5932216A (ja) 1982-08-17 1984-02-21 Sony Corp ディジタル信号処理回路及びディジタルフィルタ
GB8529422D0 (en) 1985-11-29 1986-01-08 British Broadcasting Corp Integrated circuits
US4864529A (en) 1986-10-09 1989-09-05 North American Philips Corporation Fast multiplier architecture
US5117385A (en) * 1990-03-16 1992-05-26 International Business Machines Corporation Table lookup multiplier with digital filter
JPH04165530A (ja) 1990-10-30 1992-06-11 Nec Corp 浮動小数点乗算装置
US5255216A (en) * 1991-08-16 1993-10-19 International Business Machines Corporation Reduced hardware look up table multiplier
US5260898A (en) * 1992-03-13 1993-11-09 Sun Microsystems, Inc. Result cache for complex arithmetic units
US5828591A (en) 1992-11-02 1998-10-27 Intel Corporation Method and apparatus for using a cache memory to store and retrieve intermediate and final results
US5343416A (en) 1992-11-02 1994-08-30 Intel Corporation Method and apparatus for re-configuring a partial product reduction tree
US5715187A (en) * 1996-03-04 1998-02-03 Holtek Microelectronics, Inc. Method and apparatus for integer multiplication

Also Published As

Publication number Publication date
JP2000112714A (ja) 2000-04-21
EP0990981A2 (fr) 2000-04-05
DE69905833D1 (de) 2003-04-17
DE69905833T2 (de) 2003-12-04
US6298369B1 (en) 2001-10-02
EP0990981A3 (fr) 2001-03-07

Similar Documents

Publication Publication Date Title
US7043520B2 (en) High-speed/low power finite impulse response filter
US6366936B1 (en) Pipelined fast fourier transform (FFT) processor having convergent block floating point (CBFP) algorithm
US5870323A (en) Three overlapped stages of radix-2 square root/division with speculative execution
KR19990072273A (ko) 초등함수값을고정밀도로어림계산하는시스템및방법
EP0990981B1 (fr) Multiplieur à grande vitesse
Piromsopa et al. An FPGA implementation of a fixed-point square root operation
JPH05216627A (ja) 乗算器および乗算方法
US7143126B2 (en) Method and apparatus for implementing power of two floating point estimation
JP3551113B2 (ja) 除算器
KR100308726B1 (ko) 고속 산술 장치에서 올림수 예견가산기 스테이지의 수를 감소시키는 장치 및 방법
CA2329104C (fr) Methode et appareil pour calculer un reciproque
US6941334B2 (en) Higher precision divide and square root approximations
KR100433131B1 (ko) 작은 사이즈의 룩업 테이블을 갖는 파이프라인 나눗셈연산기 및 연산방법
JPH0731592B2 (ja) 除算回路
US8577952B2 (en) Combined binary/decimal fixed-point multiplier and method
Eisig et al. The design of a 64-bit integer multiplier/divider unit
Pineiro et al. High-radix logarithm with selection by rounding
KR20080050226A (ko) 모듈러 곱셈 장치 및 설계 방법
US5677863A (en) Method of performing operand increment in a booth recoded multiply array
US4190894A (en) High speed parallel multiplication apparatus with single-step summand reduction
Schulte et al. Accurate function approximations by symmetric table lookup and addition
Schulte et al. High-speed reciprocal approximations
US6157939A (en) Methods and apparatus for generating multiplicative inverse product
Lewis An accurate LNS arithmetic unit using interleaved memory function interpolator
Jaiswal et al. Taylor series based architecture for quadruple precision floating point division

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): DE FR GB IT

AX Request for extension of the european patent

Free format text: AL;LT;LV;MK;RO;SI

PUAL Search report despatched

Free format text: ORIGINAL CODE: 0009013

AK Designated contracting states

Kind code of ref document: A3

Designated state(s): AT BE CH CY DE DK ES FI FR GB GR IE IT LI LU MC NL PT SE

AX Request for extension of the european patent

Free format text: AL;LT;LV;MK;RO;SI

17P Request for examination filed

Effective date: 20010809

17Q First examination report despatched

Effective date: 20011002

AKX Designation fees paid

Free format text: DE FR GB IT

GRAH Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOS IGRA

GRAH Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOS IGRA

GRAA (expected) grant

Free format text: ORIGINAL CODE: 0009210

AK Designated contracting states

Designated state(s): DE FR GB IT

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: IT

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT;WARNING: LAPSES OF ITALIAN PATENTS WITH EFFECTIVE DATE BEFORE 2007 MAY HAVE OCCURRED AT ANY TIME BEFORE 2007. THE CORRECT EFFECTIVE DATE MAY BE DIFFERENT FROM THE ONE RECORDED.

Effective date: 20030312

REG Reference to a national code

Ref country code: GB

Ref legal event code: FG4D

REF Corresponds to:

Ref document number: 69905833

Country of ref document: DE

Date of ref document: 20030417

Kind code of ref document: P

ET Fr: translation filed
PLBE No opposition filed within time limit

Free format text: ORIGINAL CODE: 0009261

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: NO OPPOSITION FILED WITHIN TIME LIMIT

26N No opposition filed

Effective date: 20031215

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: FR

Payment date: 20060908

Year of fee payment: 8

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: DE

Payment date: 20060922

Year of fee payment: 8

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: GB

Payment date: 20060927

Year of fee payment: 8

GBPC Gb: european patent ceased through non-payment of renewal fee

Effective date: 20070928

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: DE

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20080401

REG Reference to a national code

Ref country code: FR

Ref legal event code: ST

Effective date: 20080531

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: FR

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20071001

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: GB

Free format text: LAPSE BECAUSE OF NON-PAYMENT OF DUE FEES

Effective date: 20070928