Hi, When I read a tutorial on FIR implementation on FPGA, I am not clear about "partial results can be used for many multiplications (regardless of symmetry)" That slide may be based on multiplier with logic cell in FPGA, not a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results can be used for many multiplications (regardless of symmetry)'? I only think that to save 50% multiplier taking advantage of FIR coef symmetric characteristic. Could you tell me how to understand about the partial results? Thank,
Question about partial multiplication result in transposed FIR filter
Started by ●September 25, 2015
Reply by ●September 25, 20152015-09-25
>Hi, > >When I read a tutorial on FIR implementation on FPGA, I am not clearabout> "partial results can be used for many multiplications (regardless of > symmetry)" That slide may be based on multiplier with logic cell inFPGA,>not > a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results canbe> used for many multiplications (regardless of symmetry)'? I only thinkthat>to > save 50% multiplier taking advantage of FIR coef symmetriccharacteristic.> > >Could you tell me how to understand about the partial results? > >Thank,can we read that tutorial? Kaz --------------------------------------- Posted through http://www.FPGARelated.com
Reply by ●September 25, 20152015-09-25
On Friday, September 25, 2015 at 4:40:18 PM UTC-4, kaz wrote:> >Hi, > > > >When I read a tutorial on FIR implementation on FPGA, I am not clear > about > > "partial results can be used for many multiplications (regardless of > > symmetry)" That slide may be based on multiplier with logic cell in > FPGA, > >not > > a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results can > be > > used for many multiplications (regardless of symmetry)'? I only think > that > >to > > save 50% multiplier taking advantage of FIR coef symmetric > characteristic. > > > > > >Could you tell me how to understand about the partial results? > > > >Thank, >=20 > can we read that tutorial? >=20 > Kaz > --------------------------------------- > Posted through http://www.FPGARelated.comHere is the link:https://www.google.ca/url?sa=3Dt&rct=3Dj&q=3D&esrc=3Ds&sou= rce=3Dweb&cd=3D1&cad=3Drja&uact=3D8&ved=3D0CB0QFjAAahUKEwi_vKXaoZPIAhVRB5IK= HZbHBTk&url=3Dhttp%3A%2F%2Fcct.cnes.fr%2Fsystem%2Ffiles%2Fcnes_cct%2F459-mc= e%2Fpublic%2F06_MVD_%2520FIR_Design.pdf&usg=3DAFQjCNHDrIXK_J6WMErALOhKYrGsx= LFg6w Thanks,
Reply by ●September 26, 20152015-09-26
On 9/25/2015 4:10 PM, fl wrote:> Hi, > > When I read a tutorial on FIR implementation on FPGA, I am not clear about > "partial results can be used for many multiplications (regardless of > symmetry)" That slide may be based on multiplier with logic cell in FPGA, not > a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results can be > used for many multiplications (regardless of symmetry)'? I only think that to > save 50% multiplier taking advantage of FIR coef symmetric characteristic. > > Could you tell me how to understand about the partial results?They are talking about an extreme level of optimization by sharing partial products between multiplies. Trouble is, each multiply is by a different coefficient *and* a different data value. But in each successive clock cycle the data moves to the next coefficient, so if any of the bits of the coefficients match, the result of the previous partial product can just be shifted into the appropriate location in the adjacent product calculation. It would be a bit tortuous to code and would nullify the utility of the hard multipliers available in many FPGAs. It might be worth while to do if you are designing an ASIC though. -- Rick
Reply by ●September 26, 20152015-09-26
On 9/26/2015 12:06 AM, rickman wrote:> On 9/25/2015 4:10 PM, fl wrote: >> Hi, >> >> When I read a tutorial on FIR implementation on FPGA, I am not clear >> about >> "partial results can be used for many multiplications (regardless of >> symmetry)" That slide may be based on multiplier with logic cell in >> FPGA, not >> a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results >> can be >> used for many multiplications (regardless of symmetry)'? I only >> think that to >> save 50% multiplier taking advantage of FIR coef symmetric >> characteristic. >> >> Could you tell me how to understand about the partial results? > > They are talking about an extreme level of optimization by sharing > partial products between multiplies. Trouble is, each multiply is by a > different coefficient *and* a different data value. But in each > successive clock cycle the data moves to the next coefficient, so if any > of the bits of the coefficients match, the result of the previous > partial product can just be shifted into the appropriate location in the > adjacent product calculation. It would be a bit tortuous to code and > would nullify the utility of the hard multipliers available in many > FPGAs. It might be worth while to do if you are designing an ASIC though.I posed this before I read your link. I assumed right, but I didn't see the block diagram which shows all the multiplies happening on the same data at the same time. I've written FIR filters before, I should have remembered this. So the individual partial products can be shared across all the multiplies and added appropriately. I expect this assumes fixed coefficients which naturally make multipliers simpler. -- Rick
Reply by ●September 26, 20152015-09-26
On 9/26/15 12:06 AM, rickman wrote:> On 9/25/2015 4:10 PM, fl wrote: >> Hi, >> >> When I read a tutorial on FIR implementation on FPGA, I am not clear >> about >> "partial results can be used for many multiplications (regardless of >> symmetry)" That slide may be based on multiplier with logic cell in >> FPGA, not >> a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results >> can be >> used for many multiplications (regardless of symmetry)'? I only >> think that to >> save 50% multiplier taking advantage of FIR coef symmetric >> characteristic. >> >> Could you tell me how to understand about the partial results? > > They are talking about an extreme level of optimization by sharing > partial products between multiplies. Trouble is, each multiply is by a > different coefficient *and* a different data value. But in each > successive clock cycle the data moves to the next coefficient, so if any > of the bits of the coefficients match, the result of the previous > partial product can just be shifted into the appropriate location in the > adjacent product calculation. It would be a bit tortuous to code and > would nullify the utility of the hard multipliers available in many > FPGAs. It might be worth while to do if you are designing an ASIC though. >A simple, and useful, transformation for a FIR or IIR filter for FPGAs is to switch from using one big summing node, with a series of delays before/after with tap offs and multiplies to having a single node feed forward/back to a series of nodes with simple adders. Since with the FPGA the registers at the outputs are free, this is the most efficient format. It also says that if the coefficients are constants, you have a possibility of optimizing some of the partial produces if building explicit multipliers.
Reply by ●September 27, 20152015-09-27
On Fri, 25 Sep 2015 15:47:29 -0700, fl wrote:> On Friday, September 25, 2015 at 4:40:18 PM UTC-4, kaz wrote: >> >Hi, >> > >> >When I read a tutorial on FIR implementation on FPGA, I am not clear >> about >> > "partial results can be used for many multiplications (regardless of >> > symmetry)" That slide may be based on multiplier with logic cell in >> FPGA, >> >not >> > a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results >> > can >> be >> > used for many multiplications (regardless of symmetry)'? I only think >> that >> >to >> > save 50% multiplier taking advantage of FIR coef symmetric >> characteristic. >> > >> > >> >Could you tell me how to understand about the partial results? >> > >> >Thank, >> >> can we read that tutorial? >> >> Kaz --------------------------------------- Posted through >> http://www.FPGARelated.com > > Here is the > link:https://www.google.ca/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CB0QFjAAahUKEwi_vKXaoZPIAhVRB5IKHZbHBTk&url=http %3A%2F%2Fcct.cnes.fr%2Fsystem%2Ffiles%2Fcnes_cct%2F459-mce%2Fpublic% 2F06_MVD_%2520FIR_Design.pdf&usg=AFQjCNHDrIXK_J6WMErALOhKYrGsxLFg6w> > Thanks,Well, the guy throws out one unfounded statement and then never supports it. In a live presentation you could raise your hand and ask about it. Can you send him an email? I can see ways that, given a predetermined set of coefficients, you may be able to get the gate count down, but that's not really within the scope of the talk. I suspect it's an editing turd -- he had something brilliant in a prior version of the presentation which he either found out was unfounded, or which he didn't have time to present for this particular talk, so he set out to edit all of it out but he left this one little bit. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●September 27, 20152015-09-27
On Sun, 27 Sep 2015 15:08:02 -0500, Tim Wescott wrote:> On Fri, 25 Sep 2015 15:47:29 -0700, fl wrote: > >> On Friday, September 25, 2015 at 4:40:18 PM UTC-4, kaz wrote: >>> >Hi, >>> > >>> >When I read a tutorial on FIR implementation on FPGA, I am not clear >>> about >>> > "partial results can be used for many multiplications (regardless of >>> > symmetry)" That slide may be based on multiplier with logic cell in >>> FPGA, >>> >not >>> > a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results >>> > can >>> be >>> > used for many multiplications (regardless of symmetry)'? I only >>> > think >>> that >>> >to >>> > save 50% multiplier taking advantage of FIR coef symmetric >>> characteristic. >>> > >>> > >>> >Could you tell me how to understand about the partial results? >>> > >>> >Thank, >>> >>> can we read that tutorial? >>> >>> Kaz --------------------------------------- Posted through >>> http://www.FPGARelated.com >> >> Here is the link:https://www.google.ca/url? >sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CB0QFjAAahUKEwi_vKXaoZPIAhVRB5IKHZbHBTk&url=http> %3A%2F%2Fcct.cnes.fr%2Fsystem%2Ffiles%2Fcnes_cct%2F459-mce%2Fpublic% > 2F06_MVD_%2520FIR_Design.pdf&usg=AFQjCNHDrIXK_J6WMErALOhKYrGsxLFg6w >> >> Thanks, > > Well, the guy throws out one unfounded statement and then never supports > it. In a live presentation you could raise your hand and ask about it. > Can you send him an email? > > I can see ways that, given a predetermined set of coefficients, you may > be able to get the gate count down, but that's not really within the > scope of the talk. > > I suspect it's an editing turd -- he had something brilliant in a prior > version of the presentation which he either found out was unfounded, or > which he didn't have time to present for this particular talk, so he set > out to edit all of it out but he left this one little bit.Just a note: since nearly all FIR filters are symmetrical around some point, it would be interesting to see how much the area would increase or decrease if you insisted on that, then reduced the multipliers by a factor of two at the cost of having one more adder per multiplier. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●September 27, 20152015-09-27
On 9/27/2015 4:08 PM, Tim Wescott wrote:> On Fri, 25 Sep 2015 15:47:29 -0700, fl wrote: > >> On Friday, September 25, 2015 at 4:40:18 PM UTC-4, kaz wrote: >>>> Hi, >>>> >>>> When I read a tutorial on FIR implementation on FPGA, I am not clear >>> about >>>> "partial results can be used for many multiplications (regardless of >>>> symmetry)" That slide may be based on multiplier with logic cell in >>> FPGA, >>>> not >>>> a dedicated MAC in FPGA. Anyhow, I don't know why 'partial results >>>> can >>> be >>>> used for many multiplications (regardless of symmetry)'? I only think >>> that >>>> to >>>> save 50% multiplier taking advantage of FIR coef symmetric >>> characteristic. >>>> >>>> >>>> Could you tell me how to understand about the partial results? >>>> >>>> Thank, >>> >>> can we read that tutorial? >>> >>> Kaz --------------------------------------- Posted through >>> http://www.FPGARelated.com >> >> Here is the >> link:https://www.google.ca/url? > sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CB0QFjAAahUKEwi_vKXaoZPIAhVRB5IKHZbHBTk&url=http > %3A%2F%2Fcct.cnes.fr%2Fsystem%2Ffiles%2Fcnes_cct%2F459-mce%2Fpublic% > 2F06_MVD_%2520FIR_Design.pdf&usg=AFQjCNHDrIXK_J6WMErALOhKYrGsxLFg6w >> >> Thanks, > > Well, the guy throws out one unfounded statement and then never supports > it. In a live presentation you could raise your hand and ask about it. > Can you send him an email? > > I can see ways that, given a predetermined set of coefficients, you may > be able to get the gate count down, but that's not really within the > scope of the talk.I think it is clear that he is talking about a hard coded set of coefficients. If the coefficients are variables in registers, there is no efficient way to optimize the multipliers. With fixed coefficients and multipliers in the fabric, this would be an important optimization. He discusses using fabric for multipliers in later slides. It is not unreasonable to expect the tools to do this optimization automatically. -- Rick
Reply by ●September 27, 20152015-09-27
On Sun, 27 Sep 2015 18:28:12 -0400, rickman wrote:> On 9/27/2015 4:08 PM, Tim Wescott wrote: >> On Fri, 25 Sep 2015 15:47:29 -0700, fl wrote: >> >>> On Friday, September 25, 2015 at 4:40:18 PM UTC-4, kaz wrote: >>>>> Hi, >>>>> >>>>> When I read a tutorial on FIR implementation on FPGA, I am not clear >>>> about >>>>> "partial results can be used for many multiplications (regardless of >>>>> symmetry)" That slide may be based on multiplier with logic cell in >>>> FPGA, >>>>> not a dedicated MAC in FPGA. Anyhow, I don't know why 'partial >>>>> results can >>>> be >>>>> used for many multiplications (regardless of symmetry)'? I only >>>>> think >>>> that >>>>> to save 50% multiplier taking advantage of FIR coef symmetric >>>> characteristic. >>>>> >>>>> >>>>> Could you tell me how to understand about the partial results? >>>>> >>>>> Thank, >>>> >>>> can we read that tutorial? >>>> >>>> Kaz --------------------------------------- Posted through >>>> http://www.FPGARelated.com >>> >>> Here is the link:https://www.google.ca/url? >>sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CB0QFjAAahUKEwi_vKXaoZPIAhVRB5IKHZbHBTk&url=http>> %3A%2F%2Fcct.cnes.fr%2Fsystem%2Ffiles%2Fcnes_cct%2F459-mce%2Fpublic% >> 2F06_MVD_%2520FIR_Design.pdf&usg=AFQjCNHDrIXK_J6WMErALOhKYrGsxLFg6w >>> >>> Thanks, >> >> Well, the guy throws out one unfounded statement and then never >> supports it. In a live presentation you could raise your hand and ask >> about it. >> Can you send him an email? >> >> I can see ways that, given a predetermined set of coefficients, you may >> be able to get the gate count down, but that's not really within the >> scope of the talk. > > I think it is clear that he is talking about a hard coded set of > coefficients. If the coefficients are variables in registers, there is > no efficient way to optimize the multipliers. With fixed coefficients > and multipliers in the fabric, this would be an important optimization. > He discusses using fabric for multipliers in later slides. It is not > unreasonable to expect the tools to do this optimization automatically.I totally missed that -- yes, one would hope that in 2015 the tools would be able to figure out how to optimize fixed multipliers. This is a tangent, but it makes me wonder -- I saw a paper ages ago that was basically saying that if addition and subtraction are equally costly, then you can optimize a multiplication by using both -- i.e., if you're multiplying (x) by 11110001111b, then you can either do eight adds, or you can do (x << 11) - (x << 6) + (x << 4) - x, for a 4x savings. So -- do modern optimizers do this when multiplying by fixed coefficients, or not? -- www.wescottdesign.com
