Population counting in computer systems

Claim 2

A multiplying unit provided in a computer system, for performing multiplication of multiplicand data and multiplier data in a multiplication mode and for performing population counting of population counting input data in a population counting mode, said multiplying unit comprising: means for registering and equally dividing the multiplicand data into a plurality of multiplicand elements in the multiplication mode; means for registering and equally dividing the multiplier data into a plurality of multiplier elements in the multiplication mode, and for registering and equally dividing the population counting input data into a plurality of population counting elements, of the same number as said multiplier elements, in the population counting mode; a plurality of multiplying sub-units for executing simultaneously partial multiplications among the multiplicand elements and the multiplier elements, producing partial product data of the partial multiplications in the multiplication mode, and for executing simultaneously partial population countings for the population counting elements, producing partial counted data of the partial population countings in the population counting mode; and means for adding said partial product data from said multiplying sub-units, outputting a multiplication result of the multiplicand data and the multiplier data in the multiplication mode, and for adding said partial counted data of the partial population countings from said multiplying sub-units, outputting a population counting result of the population counting input data in the population counting mode.

Claim 3

A multiplying unit according to claim 1, wherein a plurality of said multiplying sub-units comprise first type multiplying sub-units, of the same number as the population counting elements, each said first type multiplying sub-unit comprising: a first sub-unit register for setting one of the multiplier elements in the multiplication mode, and for setting one of the population counting elements in the population counting mode; a second carry save adder for counting the number of "1" data bits in the population counting element registered in said first sub-unit register, simultaneously inputting every two data signals of the population counting element, said two data signals having been registered respectively in two registering positions adjacent each other, of said first sub-unit register, and outputting elemental sum and carry data of the population counting element; a second sub-unit register for setting and outputting one of the multiplicand elements in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; a decoder for outputting decoded signals required for multiplying the multiplicand element and the multiplier element, inputting the multiplier element from said first sub-unit register in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; a multiple generator for generating and outputting shifted data by combining the multiplicand element data from said second sub-unit register and the decoded signals from said decoder in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; a pair of a first carry save adder and a first carry propagate adder for outputting the partial product data of the partial multiplication of the multiplicand element and the multiplier element, adding the shifted data from said multiple generator in the multiplication mode, and for outputting the partial counted data of the number of "1" data bits in the population counting element, adding the elemental sum and carry data from said second carry save adder in the population counting mode; and selector means for selecting the shifted data from said multiple generator and the elemental sum and carry data from said second carry save adder so as to send either of said data to said pair of a first carry save adder and a first carry propagate adder in accordance with the multiplication mode and the population counting mode respectively.

Claim 4

A multiplying unit according to claim 2, wherein a plurality of said multiplying sub-units further comprise second type multiplying sub-units having a number obtained by subtracting the number of said first type multiplying sub-units from a number required to perform the partial multiplication among the multiplicand elements and the multiplier elements, each said second type multiplying sub-unit comprising: a third sub-unit register for setting and outputting one of the multiplier elements in the multiplication mode; a fourth sub-unit register for setting and outputting one of the multiplicand elements in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; and a decoder for outputting decoded signals required for multiplying the multiplicand element and the multiplier element, inputting the multiplier element from said third sub-unit register in the multiplication mode, and for generating and outputting all "0" data bits in the population mode.

Claim 5

A multiplying unit provided in a computer system, for performing multiplication of multiplicand data and multiplier data in a multiplication mode and for performing population counting of population counting input data in a population counting mode, said multiplying unit comprising: means for registering the multiplicand data in the multiplication mode; means for registering and equally dividing the multiplier data into a plurality of multiplier elements in the multiplication mode, and for registering and equally dividing the population counting input data into a plurality of population counting elements, of the same number as said multiplier elements, in the population counting mode; a plurality of multiplying sub-units for executing simultaneously partial multiplications among the multiplicand and the multiplier elements, producing partial product data of the partial multiplications in the multiplication mode, and for executing simultaneously partial population countings for the population counting elements, producing partial counted data of the partial population countings in the population counting mode; and means for adding said partial product data from said multiplying sub-units, outputting a multiplication result of the multiplicand data and the multiplier data in the multiplication mode, and for adding said partial counted data of the partial population countings from said multiplying sub-units, outputting a population counting result of the population counting input data in the population counting mode.

Claim 6

A multiplying unit provided in a computer system, for performing multiplication of multiplicand data and multiplier data in a multiplication mode and for performing population counting of population counting input data in a population counting mode, said multiplying unit comprising: means for registering the multiplicand data in the multiplication mode; means for registering and equally dividing the multiplier data into a plurality of multiplier elements in the multiplication mode, and for registering and equally dividing the population counting input data into a plurality of population counting elements, of the same number as said multiplier elements, in the population counting mode; a plurality of multiplying sub-units for executing simultaneously partial multiplications among the multiplicand and the multiplier elements, producing partial product data of the partial multiplications in the multiplication mode, and for executing simultaneously partial population countings for the population counting elements, producing partial counted data of the partial population countings in the population counting mode; and means for adding said partial product data from said multiplying sub-units, outputting a multiplication result of the multiplicand data and the multiplier data in the multiplication mode, and for adding said partial counted data of the partial population countings from said multiplying sub-units, outputting a population counting result of the population counting input data in the population counting mode.

Claim 7

A multiplying unit according to claim 4, wherein a plurality of said multiplying sub-units comprise first type multiplying sub-units, of the same number as the population counting elements, each said first type multiplying sub-unit comprising: a first sub-unit register for setting one of the multiplier elements in the multiplication mode, and for setting one of the population counting elements in the population counting mode; a second carry save adder for counting the number of "1" data bits in the population counting element registered in said first sub-unit register, simultaneously inputting every two data signals of the population counting element, and two data signals being what have been registered respectively in two registering positions adjacent each other, of said first sub-unit register, and outputting elemental sum and carry data of the population counting element; a second sub-unit register for setting and outputting the multiplicand data in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; a decoder for outputting decoded signals required for multiplying the multiplicand data and the multiplier element, inputting the multiplier element from said first sub-unit register in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; a multiple generator for generating and outputting shifted data by combining the multiplicand data from said second sub-unit register and the decoded signals from said decoder in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; a pair of a first carry save adder and a first carry propagate adder for outputting the partial product data of the partial multiplication of the multiplicand data and the multiplier element, added the shifted data from said multiple generator in the multiplication mode, and for outputting the partial counted data of the number of "1" data bits in the population counting element, adding the elemental sum and carry data from said second carry save adder in the population counting mode; and selector means for selecting the shifted data from said multiple generator and the elemental sum and carry data from said second carry save adder so as to send either of said data to said pair of a first carry save adder and a first carry propagate adder in accordance with the multiplication mode and the population counting mode respectively.

Claim 8

A multiplying unit according to claim 5, wherein a plurality of said multiplying sub-units further comprise second type multiplying sub-units having a number obtained by subtracting the number of said first type multiplying sub-units from a number required to perform the partial multiplication among the multiplicand and the multiplier elements, each said second type multiplying sub-unit comprising: a third sub-unit register for setting and outputting one of the multiplier elements in the multiplication mode; a fourth sub-unit register for setting and outputting the multiplicand data in the multiplication mode, and for generating and outputting all "0" data bits in the population counting mode; and a decoder for outputting decoded signals required for multiplying the multiplicand data and the multiplier element, inputting the multiplier element from said third sub-unit register in the multiplication mode, and for generating and outputting all "0" data bits in the population mode.