I am looking for open source software for logic minimization (a la espresso) targeted to a lookup table based architecture that can take advantage of six inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 implementation). Is there such a beast? thanks much -Arrigo
Logic minimization software with LUT6 support?
Started by ●September 25, 2007
Reply by ●September 26, 20072007-09-26
On Sep 25, 4:30 pm, dudesinmex...@gmail.com wrote:> I am looking for open source software for logic minimization (a la > espresso) targeted to a lookup table based architecture that can take advantage > of six inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 > implementation). Is there such a beast?Howdy, You peaked my curiosity. Could you explain why you need this? Synthesis tools do this for you, and with probably much greater speed, accuracy, and intelligent trade-off's than you'd be able to do manually - especially when you start considering registers rather than just pure combinational logic. Thanks, Marc
Reply by ●September 26, 20072007-09-26
AFAIK there are not good multi level optimization algorithms that take mapping effects into account. Instead logic optimization is done independently of mapping. Usually, first a technology independent multi level logic optimization is performed. (Based on transformations, ATPG or implications). There should be academic implementations for that around. Most of them quite old. Afterwards technology mapping is performed. Mapping for LUTs can be done delay optimal in polynomial time. (Flow map). For 6-LUT FPGAs it might make sense to combine mapping with retiming to balance the amount of logic between stages. There is a paper by Sunil Khatri on optimization for networks of PLAs. A 6-LUT might be large enough to benefit from that approach. (I doubt it) Kolja Sulimma On 25 Sep., 23:30, dudesinmex...@gmail.com wrote:> I am looking for open source software for logic minimization (a la > espresso) > targeted to a lookup table based architecture that can take advantage > of six > inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 > implementation). > Is there such a beast? > > thanks much > > -Arrigo
Reply by ●September 26, 20072007-09-26
On Sep 25, 8:48 pm, Marc Randolph <mr...@my-deja.com> wrote:> On Sep 25, 4:30 pm, dudesinmex...@gmail.com wrote: > > > I am looking for open source software for logic minimization (a la > > espresso) targeted to a lookup table based architecture that can take advantage > > of six inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 > > implementation). Is there such a beast? > > Howdy, > > You peaked my curiosity. Could you explain why you need this?Sure. I am working at a Virtex 5 design with *lots* of squarer circuits (Z=A*B with A=B) where the input is a signed 9 bit value in the [-255,255] range. I am wondering if the LUT6 would give any advantage compared to other implementations. Then, looking at Ray Andraka's page on multipliers I realized that a "Partial product LUT multiplier" looks like a good architecture for the squarer (since A=B the number of LUTs is cut in half), and that the LUT6 probably does not buy you more than a LUT4 since the carry chain limits the number of bits to four per slice. -Arrigo
Reply by ●September 26, 20072007-09-26
>Sure. I am working at a Virtex 5 design with *lots* of squarer >circuits (Z=A*B with A=B) where the input >is a signed 9 bit value in the [-255,255] range.9 bits is a small number. Have you considered table lookup? -- These are my opinions, not necessarily my employer's. I hate spam.
Reply by ●September 26, 20072007-09-26
dudesinmexico@gmail.com wrote:> On Sep 25, 8:48 pm, Marc Randolph <mr...@my-deja.com> wrote: > >>On Sep 25, 4:30 pm, dudesinmex...@gmail.com wrote: >> >> >>>I am looking for open source software for logic minimization (a la >>>espresso) targeted to a lookup table based architecture that can take advantage >>>of six inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 >>>implementation). Is there such a beast? >> >>Howdy, >> >>You peaked my curiosity. Could you explain why you need this? > > > Sure. I am working at a Virtex 5 design with *lots* of squarer > circuits (Z=A*B with A=B) where the input > is a signed 9 bit value in the [-255,255] range. I am wondering if > the LUT6 would give any advantage > compared to other implementations. Then, looking at Ray Andraka's page > on multipliers I realized that > a "Partial product LUT multiplier" looks like a good architecture for > the squarer (since A=B the number of LUTs is cut in half), and that > the LUT6 probably does not buy you more than a LUT4 since the carry > chain limits the number of bits to four per slice. > > -Arrigo > > >The LUT size isn't related directly to the carry chain pitch. The 6 input LUTs (12 per partial product for a 6bit in, 12 bit out LUT) make your partial products, and then you add those together with the appropriate shifting for the weighting of the partials to arrive at the complete square. For 9 input bits though, you really only need 4 and 5 input LUTs. A 6 LUT implementation is still going to have 4 partial products, so there is no savings over 4/5 input LUTs. That said, you could use dual port BRAMs as direct look-ups instead and get two 9 bit squarers per BRAM (one on each port).
Reply by ●September 26, 20072007-09-26
On Sep 26, 3:57 pm, Ray Andraka <r...@andraka.com> wrote:> dudesinmex...@gmail.com wrote: > > On Sep 25, 8:48 pm, Marc Randolph <mr...@my-deja.com> wrote: > > >>On Sep 25, 4:30 pm, dudesinmex...@gmail.com wrote: > > >>>I am looking for open source software for logic minimization (a la > >>>espresso) targeted to a lookup table based architecture that can take advantage > >>>of six inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 > >>>implementation). Is there such a beast? > > >>Howdy, > > >>You peaked my curiosity. Could you explain why you need this? > > > Sure. I am working at a Virtex 5 design with *lots* of squarer > > circuits (Z=A*B with A=B) where the input > > is a signed 9 bit value in the [-255,255] range. I am wondering if > > the LUT6 would give any advantage > > compared to other implementations. Then, looking at Ray Andraka's page > > on multipliers I realized that > > a "Partial product LUT multiplier" looks like a good architecture for > > the squarer (since A=B the number of LUTs is cut in half), and that > > the LUT6 probably does not buy you more than a LUT4 since the carry > > chain limits the number of bits to four per slice. > > > -Arrigo > > The LUT size isn't related directly to the carry chain pitch. The 6 > input LUTs (12 per partial product for a 6bit in, 12 bit out LUT) make > your partial products, and then you add those together with the > appropriate shifting for the weighting of the partials to arrive at the > complete square. For 9 input bits though, you really only need 4 and 5 > input LUTs. A 6 LUT implementation is still going to have 4 partial > products, so there is no savings over 4/5 input LUTs. > > That said, you could use dual port BRAMs as direct look-ups instead and > get two 9 bit squarers per BRAM (one on each port).Ray, nice to hear from you. Yes, I have considered BRAMs as lookup tables. In fact, we noticed that Synplify does something pretty cool: it packs two multipliers in a single BRAM18, using one port for each multiplier. Of course this is possible since they share the same table. According to the documentation, one can use a BRAM36 as two BRAM18s, however PlanAhead refuses to place a pblock with two BRAM18s on any area with just one BRAM36. This could be either a PlanAhead bug or simply that the BRAM36 still has just two ports...
Reply by ●September 26, 20072007-09-26
dudesinmexico@gmail.com wrote:> On Sep 26, 3:57 pm, Ray Andraka <r...@andraka.com> wrote: > >>dudesinmex...@gmail.com wrote: >> >>>On Sep 25, 8:48 pm, Marc Randolph <mr...@my-deja.com> wrote: >> >>>>On Sep 25, 4:30 pm, dudesinmex...@gmail.com wrote: >> >>>>>I am looking for open source software for logic minimization (a la >>>>>espresso) targeted to a lookup table based architecture that can take advantage >>>>>of six inputs LUTs (as you can imagine I have in mind a LUT6/Virtex 5 >>>>>implementation). Is there such a beast? >> >>>>Howdy, >> >>>>You peaked my curiosity. Could you explain why you need this? >> >>>Sure. I am working at a Virtex 5 design with *lots* of squarer >>>circuits (Z=A*B with A=B) where the input >>>is a signed 9 bit value in the [-255,255] range. I am wondering if >>>the LUT6 would give any advantage >>>compared to other implementations. Then, looking at Ray Andraka's page >>>on multipliers I realized that >>>a "Partial product LUT multiplier" looks like a good architecture for >>>the squarer (since A=B the number of LUTs is cut in half), and that >>>the LUT6 probably does not buy you more than a LUT4 since the carry >>>chain limits the number of bits to four per slice. >> >>>-Arrigo >> >>The LUT size isn't related directly to the carry chain pitch. The 6 >>input LUTs (12 per partial product for a 6bit in, 12 bit out LUT) make >>your partial products, and then you add those together with the >>appropriate shifting for the weighting of the partials to arrive at the >>complete square. For 9 input bits though, you really only need 4 and 5 >>input LUTs. A 6 LUT implementation is still going to have 4 partial >>products, so there is no savings over 4/5 input LUTs. >> >>That said, you could use dual port BRAMs as direct look-ups instead and >>get two 9 bit squarers per BRAM (one on each port). > > > Ray, nice to hear from you. Yes, I have considered BRAMs as lookup > tables. > In fact, we noticed that Synplify does something pretty cool: it packs > two multipliers > in a single BRAM18, using one port for each multiplier. Of course this > is possible since > they share the same table. > According to the documentation, one can use a BRAM36 as two BRAM18s, > however > PlanAhead refuses to place a pblock with two BRAM18s on any area with > just one BRAM36. > This could be either a PlanAhead bug or simply that the BRAM36 still > has just two ports... > >It is a limitation of the BRAM36.
Reply by ●September 26, 20072007-09-26
<dudesinmexico@gmail.com> wrote in message news:1190849356.286625.69510@d55g2000hsg.googlegroups.com...> > Ray, nice to hear from you. Yes, I have considered BRAMs as lookup > tables. > In fact, we noticed that Synplify does something pretty cool: it packs > two multipliers > in a single BRAM18, using one port for each multiplier. Of course this > is possible since > they share the same table. > According to the documentation, one can use a BRAM36 as two BRAM18s, > however > PlanAhead refuses to place a pblock with two BRAM18s on any area with > just one BRAM36. > This could be either a PlanAhead bug or simply that the BRAM36 still > has just two ports...From p 125 of ug190.pdf (v3.1 Virtex-5 User Guide, 9/11/2007) Two RAMB18s can be placed in the same RAMB36 location by using the BEL UPPER/LOWER constraint: inst "my_ramb18" LOC = RAMB36_X0Y0 | BEL = UPPER inst "my_ramb18" LOC = RAMB36_X0Y0 | BEL = LOWER which is echoed in Ansew Record 25115 http://www.xilinx.com/xlnx/xil_ans_display.jsp?iLanguageID=1&iCountryID=1&getPagePath=25115 though I think the note's author forgot to write UPPER for the last line. Darned cut & paste! Whether PlanAhead supports these constraints natively isn't obvious. Ask the hotline or your FAE! - John_H
Reply by ●September 26, 20072007-09-26
John_H wrote:> <dudesinmexico@gmail.com> wrote in message > news:1190849356.286625.69510@d55g2000hsg.googlegroups.com... > >>Ray, nice to hear from you. Yes, I have considered BRAMs as lookup >>tables. >>In fact, we noticed that Synplify does something pretty cool: it packs >>two multipliers >>in a single BRAM18, using one port for each multiplier. Of course this >>is possible since >>they share the same table. >>According to the documentation, one can use a BRAM36 as two BRAM18s, >>however >>PlanAhead refuses to place a pblock with two BRAM18s on any area with >>just one BRAM36. >>This could be either a PlanAhead bug or simply that the BRAM36 still >>has just two ports... > > > From p 125 of ug190.pdf (v3.1 Virtex-5 User Guide, 9/11/2007) > > Two RAMB18s can be placed in the same RAMB36 location by using the BEL > UPPER/LOWER constraint: > inst "my_ramb18" LOC = RAMB36_X0Y0 | BEL = UPPER > inst "my_ramb18" LOC = RAMB36_X0Y0 | BEL = LOWER > > which is echoed in Ansew Record 25115 > > http://www.xilinx.com/xlnx/xil_ans_display.jsp?iLanguageID=1&iCountryID=1&getPagePath=25115 > > though I think the note's author forgot to write UPPER for the last line. > Darned cut & paste! > > Whether PlanAhead supports these constraints natively isn't obvious. Ask > the hotline or your FAE! > > - John_H > >Oops, I misread what you were saying here, I thought you were trying to use the BRAM36 dual ported. I don't often use plan ahead. Putting the bel constraints on instantiated BRAM18's works fine for placing them together.
