Fri, 4 Mar 1994 11:24:57 GMT

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

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.