Impossible Equation

Discussion in 'VHDL' started by Ndf, Jan 24, 2008.

  1. Ndf

    Ndf Guest

    Hello,

    I have a design that should output TRUE or FALSE as the result of a very
    large equation made with 256 inputs combined by 8! There are about 7 000
    000 lines of code like below!!

    Anybody know of a VHDL compiler capable to optimize such a huge equation?

    Thanks!


    Pout <=
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(5) and
    Pinp(112) and Pinp(45)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(10)
    and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(19)
    and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(25)
    and Pinp(77) and Pinp(37)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(25)
    and Pinp(89) and Pinp(44)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(30)
    and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(32)
    and Pinp(229) and Pinp(45)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(39)
    and Pinp(237) and Pinp(44)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(42)
    and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(4) and Pinp(63) and Pinp(48) and Pinp(16) and Pinp(50)
    and Pinp(112) and Pinp(45)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(213) and Pinp(211) and Pinp(37)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(213) and Pinp(219) and Pinp(38)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(216) and Pinp(211) and Pinp(37)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(216) and Pinp(219) and Pinp(38)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(232) and Pinp(237) and Pinp(44)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(238) and Pinp(237) and Pinp(44)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(239) and Pinp(237) and Pinp(44)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(243) and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(21) and Pinp(251) and Pinp(252) and Pinp(198) and
    Pinp(249) and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(24) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(5)
    and Pinp(112) and Pinp(45)) or
    (Pinp(13) and Pinp(24) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(10)
    and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(24) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(19)
    and Pinp(224) and Pinp(38)) or
    (Pinp(13) and Pinp(24) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(25)
    and Pinp(77) and Pinp(37)) or
    (Pinp(13) and Pinp(24) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(25)
    and Pinp(89) and Pinp(44)) or
    (Pinp(13) and Pinp(24) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(30)
    and Pinp(224) and Pinp(38)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(244) and Pinp(179) and Pinp(6)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(247) and Pinp(118) and Pinp(9)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(247) and Pinp(142) and Pinp(6)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(247) and Pinp(210) and Pinp(9)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(247) and Pinp(224) and Pinp(8)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(248) and Pinp(118) and Pinp(9)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(248) and Pinp(142) and Pinp(6)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(250) and Pinp(128) and Pinp(5)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(250) and Pinp(233) and Pinp(9)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(251) and Pinp(118) and Pinp(9)) or
    (Pinp(24) and Pinp(50) and Pinp(129) and Pinp(254) and Pinp(120) and
    Pinp(251) and Pinp(142) and Pinp(6)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(5)
    and Pinp(121) and Pinp(6)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(10)
    and Pinp(210) and Pinp(9)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(10)
    and Pinp(224) and Pinp(8)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(18)
    and Pinp(179) and Pinp(6)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(19)
    and Pinp(210) and Pinp(9)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(19)
    and Pinp(224) and Pinp(8)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(30)
    and Pinp(210) and Pinp(9)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(30)
    and Pinp(224) and Pinp(8)) or
    (Pinp(24) and Pinp(58) and Pinp(125) and Pinp(49) and Pinp(16) and Pinp(39)
    and Pinp(102) and Pinp(5)) or
    ……………………………………………
    ……………………………………………
     
    Ndf, Jan 24, 2008
    #1
    1. Advertising

  2. On Thu, 24 Jan 2008 16:31:33 +0100,
    Ndf <> wrote:

    >I have a design that should output TRUE or FALSE as the result of a very
    >large equation made with 256 inputs combined by 8! There are about 7 000
    >000 lines of code like below!!
    >
    >Anybody know of a VHDL compiler capable to optimize such a huge equation?


    No, I would expect many tools to choke on it - but what are
    you REALLY trying to do? What's the condition you're trying
    to check? There may be an alternative way to compute it.
    --
    Jonathan Bromley, Consultant

    DOULOS - Developing Design Know-how
    VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

    Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK

    http://www.MYCOMPANY.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
     
    Jonathan Bromley, Jan 24, 2008
    #2
    1. Advertising

  3. Ndf

    Ndf Guest

    This if for fun: I try to resolve a puzzle :0)

    In the same time I start some research about logic optimization and I hope
    to reduce this equation enough to fit inside a FPGA.







    "Jonathan Bromley" <> a écrit dans le message
    de news:...
    > On Thu, 24 Jan 2008 16:31:33 +0100,
    > Ndf <> wrote:
    >
    > >I have a design that should output TRUE or FALSE as the result of a very
    > >large equation made with 256 inputs combined by 8! There are about 7 000
    > >000 lines of code like below!!
    > >
    > >Anybody know of a VHDL compiler capable to optimize such a huge equation?

    >
    > No, I would expect many tools to choke on it - but what are
    > you REALLY trying to do? What's the condition you're trying
    > to check? There may be an alternative way to compute it.
    > --
    > Jonathan Bromley, Consultant
    >
    > DOULOS - Developing Design Know-how
    > VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
    >
    > Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
    >
    > http://www.MYCOMPANY.com
    >
    > The contents of this message may contain personal views which
    > are not the views of Doulos Ltd., unless specifically stated.
     
    Ndf, Jan 24, 2008
    #3
  4. Ndf

    KJ Guest

    On Jan 24, 10:31 am, "Ndf" <> wrote:
    > Hello,
    >
    > I have a design that should output TRUE or FALSE as the result of a very
    > large equation made with 256 inputs combined by 8!  There are about 7 000
    > 000 lines of code like below!!
    >
    > Anybody know of a VHDL compiler capable to optimize such a huge equation?
    >


    Have you simply tried your 7 million lines of code either with
    Modelsim (for a simulation result) or Quartus, XST, etc. (for an FPGA
    synthesis result)? Who knows, it might work right out of the shoot.

    Kevin Jennings
     
    KJ, Jan 24, 2008
    #4
  5. On Thu, 24 Jan 2008 17:32:30 +0100, "Ndf" <>
    wrote:

    >This if for fun: I try to resolve a puzzle :0)


    Eight queens?

    Like I said.... there may be other ways.
    --
    Jonathan Bromley, Consultant

    DOULOS - Developing Design Know-how
    VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services

    Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK

    http://www.MYCOMPANY.com

    The contents of this message may contain personal views which
    are not the views of Doulos Ltd., unless specifically stated.
     
    Jonathan Bromley, Jan 24, 2008
    #5
  6. Ndf

    Ndf Guest

    Thanks Kevin!

    For the moment I tried with Lattice ispLEVER and ModelSim! The output error
    is something like "Memory allocation failure"!
     
    Ndf, Jan 24, 2008
    #6
  7. Ndf a écrit :
    > Hello,
    >
    > I have a design that should output TRUE or FALSE as the result of a very
    > large equation made with 256 inputs combined by 8! There are about 7 000
    > 000 lines of code like below!!


    Hi,

    As I'm sure you have not typed in the 7M lines, you may have generated them from
    an algorithm.
    Describe the same algorithm in VHDL and you will have your solution !
     
    Pascal Peyremorte, Jan 24, 2008
    #7
  8. Ndf

    Paul Floyd Guest

    On Thu, 24 Jan 2008 18:00:44 +0100, Ndf <> wrote:
    > Thanks Kevin!
    >
    > For the moment I tried with Lattice ispLEVER and ModelSim! The output error
    > is something like "Memory allocation failure"!


    Hi

    Can you try on a 64bit platform (Solaris x86/SPARC, Linux Itanium/x64)?

    A bientot
    Paul
    (Not speaking for Mentor Graphics)
    --
    Paul Floyd http://paulf.free.fr
     
    Paul Floyd, Jan 24, 2008
    #8
  9. Ndf

    KJ Guest

    On Jan 24, 12:00 pm, "Ndf" <> wrote:
    > Thanks Kevin!
    >
    > For the moment I tried with Lattice ispLEVER and ModelSim! The output error
    > is something like "Memory allocation failure"!


    As an experiment, try chopping off half of the file and try again.
    Keep doing that and you'll be able to zero in on what the rough file
    size/line size/whatever size constraint is being hammered. The
    purpose of the experiment is to get a handle on what the constraint is
    so you can avoid it, not to solve the entire problem.

    Once you've done that go back to your original 7M file and break it
    down into the size file that the tools are happy with. Put a top
    level wrapper around it all to 'or' it all together and then try to
    synthesize/simulate the entire design and see if everything still
    hangs togeter.

    The better solution as others have suggested is to not work directly
    with the 7M file that you've got since obviously some algorithm
    generated that file in the first place but I'm assuming you don't have
    access to that and you have to work with the 7M file whether want to
    or not.

    Good luck

    Kevin Jennings
     
    KJ, Jan 24, 2008
    #9
  10. Ndf

    backhus Guest

    Ndf schrieb:
    > This if for fun: I try to resolve a puzzle :0)
    >
    > In the same time I start some research about logic optimization and I hope
    > to reduce this equation enough to fit inside a FPGA.
    >

    Hi Ndf,

    we want to have some fun too...what is the puzzle? :)

    regards
    Eilert
     
    backhus, Jan 25, 2008
    #10
  11. Ndf

    Ndf Guest

    Hi,
    The algorithm is simple backtracking.


    >
    > As I'm sure you have not typed in the 7M lines, you may have generated

    them from
    > an algorithm.
    > Describe the same algorithm in VHDL and you will have your solution !
     
    Ndf, Jan 25, 2008
    #11
  12. On Fri, 25 Jan 2008 08:18:01 +0100, "Ndf" <> wrote:

    >Hi,
    >The algorithm is simple backtracking.


    Should be easy to re-implement in VHDL directly then.

    - Brian
     
    Brian Drummond, Jan 25, 2008
    #12
  13. Ndf

    Guest

    On Jan 25, 8:39 am, Brian Drummond <>
    wrote:
    > On Fri, 25 Jan 2008 08:18:01 +0100, "Ndf" <> wrote:
    > >Hi,
    > >The algorithm is simple backtracking.

    >
    > Should be easy to re-implement in VHDL directly then.
    >
    > - Brian


    There are two "sizes" here: the textual size and the complexity of the
    equation.

    On the textual aspect, you can achieve perhaps an order of magnitude
    gain by simple compression: overload the "+" and "-" operators for and/
    or, reducing on average 5 chars ("and"+2 spaces) down to one.
    Additionally, you should rename your signal; make 256 different
    signals named "aa", "ab",..."ba","bb",... etc. This will further
    reduce 9 chars per conjunct to two. This will likely help tools,
    especially those which don't cache identifiers in the lexical input
    stage. This presupposes that you don't strictly need all signals to be
    part of the same vector; if you do, try setting up aliases instead.

    The equational complexity will not change, since you're still using
    simple CNF. This will cause tools to build huge AST's internally,
    hence the memory error. Depending on what you're trying to do, you
    could explore the state space completely differently, say using a SAT-
    solver or a BDD-based tool (such as SMV, perhaps, or linking some "C"
    code to an explicit BDD library like cudd or buddy).

    Like others, I'm curious to see what the puzzle is!

    - Kenn
     
    , Jan 25, 2008
    #13
  14. Ndf

    Ndf Guest

    Sorry that I was unable to continue exchange of ideas. I got out today.
    The puzzle is EternityII. My intention is to combine some PC code with FPGA
    parallel processing but, because the search space is huge, I need to
    optimize some equations!
     
    Ndf, Jan 25, 2008
    #14
  15. If we help you get your function synthesizable, how much of the $2 million
    dollar prize money do we get?

    If you are working from pure theory there are 256! combinations. Assuming
    you are using a spartan 3e chip running at 50mhz. and are some how able to
    get a result every cycle. You are looking at 153,555 days just to submit
    the (256!-249!) possibiliteis for evaluations.

    The 256! combinations does not take into acount the orientation on the tile.
    which would change the number of possibilities higher. But you could write
    your checking program to compare against all 4 angles of placement.

    Assuming you have tile rotation in your checkign algorythm. You can
    actually decrease the number of tests you need to run by removing invalid
    combinations based on the rules of the game.

    the new number of possibilities then becomes (4!)(56!)(196!).

    I hope you have alot of Xilinx and Altera stock. Just trying to check all
    the combinations
    of the outer frame are (4!)(56!) combinations or 24 times 7.2e74. Using a
    brute force method on this solution would take a very long time and alot of
    chips/computers running in parrallel.


    Dwayne




    "Ndf" <> wrote in message
    news:479a1ebd$0$26255$...
    > Sorry that I was unable to continue exchange of ideas. I got out today.
    > The puzzle is EternityII. My intention is to combine some PC code with
    > FPGA
    > parallel processing but, because the search space is huge, I need to
    > optimize some equations!
    >
    >
    >
    >
    >
     
    Dwayne Dilbeck, Jan 25, 2008
    #15
  16. On Jan 25, 7:41 pm, "Ndf" <> wrote:
    > Sorry that I was unable to continue exchange of ideas. I got out today.
    > The puzzle is EternityII. My intention is to combine some PC code with FPGA
    > parallel processing but, because the search space is huge, I need to
    > optimize some equations!


    In the eternal question of size vs. speed, you chose speed here.
    Obviously, had there been an FPGA large enough and a Synthesizer
    powerful enough to process your 7e6 equations, you could do it very
    quickly. But such tools don't exist (yet). So, you'll have to pull the
    size-speed string a bit to the side of size. This is usually done by
    breaking the computation into several cycles, by serializing,
    pipelining, and so on.

    As others suggested, you should really explain the algorithm you're
    trying to find the solution for.

    Eli
     
    Eli Bendersky, Jan 25, 2008
    #16
  17. Ndf

    Ndf Guest

    Dwayne Dilbeck wrote:
    >>If we help you get your function synthesizable, how much of the $2 million
    >>dollar prize money do we get?


    Like I said, I do that only for fun :)

    Dwayne Dilbeck wrote:
    > the new number of possibilities then becomes (4!)(56!)(196!).


    I don't want to modelize the entire search space, just to help the main
    backtracking routine (Vc++ code) using some bounding function, which checks
    whether it is possible to obtain a final solution, for the current partial
    solution.

    Thanks.
     
    Ndf, Jan 25, 2008
    #17
  18. Ndf

    Ndf Guest

    Kenn,

    Thanks for all this feedback! This is quite interesting.

    I just need to translate terms like: CNF, AST's, SAT-solver, BDD-based
    tool, SMV,
    BDD library, cudd or buddy.

    Google is my friend!


    >
    > There are two "sizes" here: the textual size and the complexity of the
    > equation.
    >
    > On the textual aspect, you can achieve perhaps an order of magnitude
    > gain by simple compression: overload the "+" and "-" operators for and/
    > or, reducing on average 5 chars ("and"+2 spaces) down to one.
    > Additionally, you should rename your signal; make 256 different
    > signals named "aa", "ab",..."ba","bb",... etc. This will further
    > reduce 9 chars per conjunct to two. This will likely help tools,
    > especially those which don't cache identifiers in the lexical input
    > stage. This presupposes that you don't strictly need all signals to be
    > part of the same vector; if you do, try setting up aliases instead.
    >
    > The equational complexity will not change, since you're still using
    > simple CNF. This will cause tools to build huge AST's internally,
    > hence the memory error. Depending on what you're trying to do, you
    > could explore the state space completely differently, say using a SAT-
    > solver or a BDD-based tool (such as SMV, perhaps, or linking some "C"
    > code to an explicit BDD library like cudd or buddy).
    >
    > Like others, I'm curious to see what the puzzle is!
    >
    > - Kenn
     
    Ndf, Jan 25, 2008
    #18
  19. Your impossible Equation is not impossible just took someone writing it
    rather than using computer generated code. I checked out the puzzle and was
    curious. Here is the number of lines for the basic solution verifier. I will
    share the code if you still want a synthesizable solution.

    comparator.vhd 22 lines
    tile.vhd 106 lines
    memory.v 42 lines
    or
    memory.vhd 44 lines
    mux.vhd 33 lines
    eternity_check.vhd 186 lines
    rom.mem 16 lines
    vectors.mem 16 lines
    eternity_check_tb.v 64 lines
    total 531 lines of code.

    This design will synthesize to 107807 emulation gates on the Cadence
    Palladium Emulator.
    I only recieved my Xilinx starter kit last night. As a result I have not
    checked how the Spartan 3e will handle the design.

    I have written the basic design in VHDL since you asked on the VHDL news
    group. Although the the testbench is in verilog and the memory has been
    implemented in both vhdl and verilog. Basically I can code memory loading
    quicker in verilog,and Cadence IUS 6.1.s003 has a problem with OOMRs that
    point from verilog and end in vhdl. Thus the memory model being in both
    vhdl and verilog.

    I went ahead and verifyied the design against the online sample eternityII
    4x4.
    But it is written with generics to expand to however large you want. The
    design would check the clue puzzles as well as the main puzzle. I have not
    coded in the actually pieces information. That I leave to you if you wish
    to have the code.

    "Ndf" <> wrote in message
    news:479a5c1c$0$4915$...
    > Dwayne Dilbeck wrote:
    >>>If we help you get your function synthesizable, how much of the $2
    >>>million dollar prize money do we get?

    >
    > Like I said, I do that only for fun :)
    >
    > Dwayne Dilbeck wrote:
    >> the new number of possibilities then becomes (4!)(56!)(196!).

    >
    > I don't want to modelize the entire search space, just to help the main
    > backtracking routine (Vc++ code) using some bounding function, which
    > checks whether it is possible to obtain a final solution, for the current
    > partial solution.
    >
    > Thanks.
     
    Dwayne Dilbeck, Jan 31, 2008
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shukla, Sunil Kumar

    parallel CRC equation generator

    Shukla, Sunil Kumar, May 31, 2005, in forum: VHDL
    Replies:
    2
    Views:
    1,171
    Pete Fraser
    May 31, 2005
  2. Weng Tianxiang
    Replies:
    12
    Views:
    1,431
  3. Marty Underwood

    String to equation

    Marty Underwood, Feb 18, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    454
    Marty Underwood
    Feb 18, 2004
  4. David Zimmerman
    Replies:
    0
    Views:
    930
    David Zimmerman
    Jun 27, 2003
  5. Replies:
    5
    Views:
    274
    Michele Dondi
    Jun 30, 2006
Loading...

Share This Page