Truth table evaluation, summary and thanks

Philip Riebold <philip@livenet.ac.uk>
Fri, 4 Mar 1994 11:24:57 GMT

          From comp.compilers

Related articles
Truth table evaluation philip@livenet.ac.uk (Philip Riebold) (1994-02-25)
Truth table evaluation, summary and thanks philip@livenet.ac.uk (Philip Riebold) (1994-03-04)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Philip Riebold <philip@livenet.ac.uk>
Keywords: optimize, theory, summary
Organization: Compilers Central
References: 94-02-189
Date: Fri, 4 Mar 1994 11:24:57 GMT

I would like to thank everybody who replied to my post last week about
speeding up the evaluation of truth tables for arbitrary boolean
expressions.


Whilst some replies were more helpful than others they all suggested
something worthwhile.


Here is a list of the suggestions I received.


Word level parallelism
Instead of evaluating one bit at a time use the first five variables as
bit vectors and evaluate 32 bits in parallel.
+~32 times faster irrespective of the expression, only took 5 minutes to
incorporate into the original code.
-It's so obvious I could have kicked myself for not thinking of it !


Lazy evaluation
Use two bit vectors, one for the values and the other to indicate if a
value has been evaluated.
+Potentially fast if only a few positions of the table are referenced.
-Unfortunately my program references the table in essentially random
order. The test data I use references _all_ the elements. So there would
be no gain.


Run time code generation
Instead of interpreting the expression generate code at run time that
directly executes it.
+Fast, claimed factor of 10.
-Non-portable, requires knowledge of the specific machine architecture (is
a PD description of the SPARC architecture available anywhere out there
:-) )


Various logic methods
Included ideas such as common sub expression evaluation, partial
evaluation and conversion to sum of products notation.
+Large gain in certain special cases
-Unlike previous methods any gain is not guaranteed and the time taken may
well outweigh the time saved.


In summary I implemented word level parallelism and the TT generation time
fell to 1/10'th of that for the rest of the program.


Thanks,


Philip
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.