Impossible Equation

[Ndf]

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
……………………………………………
……………………………………………

 

[Jonathan Bromley]

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
(e-mail address removed)
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]

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.

 

[KJ]

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

 

[Jonathan Bromley]

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
(e-mail address removed)
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]

Thanks Kevin!

For the moment I tried with Lattice ispLEVER and ModelSim! The output error
is something like "Memory allocation failure"!

 

[Pascal Peyremorte]

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 !

 

[Paul Floyd]

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)

 

[KJ]

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

 

[backhus]

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

 

[Ndf]

Hi,
The algorithm is simple backtracking.

 

[Brian Drummond]

Hi,
The algorithm is simple backtracking.

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

- Brian

 

[kennheinrich]

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

 

[Ndf]

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]

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

 

[Eli Bendersky]

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

 

[Ndf]

Like I said, I do that only for fun

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]

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!

 

[Dwayne Dilbeck]

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.