Tue, 5 Sep 1995 20:02:58 GMT

Related articles |
---|

Multiplication by constants lederman@dstc.qut.edu.au (Jeff Ledermann) (1995-08-28) |

Re: Multiplication by constants preston@tera.com (1995-09-05) |

Re: Multiplication by constants chase@centerline.com (1995-09-12) |

Newsgroups: | comp.compilers |

From: | preston@tera.com (Preston Briggs) |

Keywords: | arithmetic |

Organization: | Tera Computer Company, Seattle, WA |

References: | 95-09-018 |

Date: | Tue, 5 Sep 1995 20:02:58 GMT |

Jeff Ledermann <lederman@dstc.qut.edu.au> writes:

*>I recently picked up Preston Briggs and Tim Harvey's excellent*

*>paper "Multiplication by Integer Constants"*

*>(ftp://cs.rice.edu/public/preston/optimizer/multiply.ps.gz).*

*>I was interested to compare their more formal approach with*

*>the very simple heuristic I've been using in the GPM code*

*>generators with some success.*

Everyone should understand that the little paper doesn't describe a

new approach; instead, it's simply an implementation (with an attempt

at an explanation) of Bernstein's approach

title="Multiplication by Integer Constants",

author="Robert L. Bernstein",

journal=spe,

volume=16,

number=7,

month=jul,

year=1986,

pages="641--652",

*>Their algorithm includes a neat memoizing feature so that once an*

*>optimal factorization is found it never has to be calculated again*

*>(for that run). Extending the persistence leads to the (probably*

*>not terribly novel) approach of precalculating all factors (well up*

*>to some limit anyway), using brute force to find optimal sequences.*

*>*

*>Has anyone experience with this?*

Perhaps David Chase will respond to this too.

First, remember that Bernstein's approach doesn't always find optimal

sequences. Thus, the memoization doesn't keep track of optimal

sequences, merely good sequences. Note also that it all intermediate

steps in the exploration are recorded, even if they don't turn out to

be useful for a particular problem. That way, if another problem can

use them, re-exploration will be avoided.

Given the memoization, it's possible to seed it with optimal

sequences. One way to do this is to write an exhaustive (offline)

algorithm that finds truly optimal sequences, and compares them to the

best sequences discovered by the heuristic approach. If, for some

number N, the heuristic approach turns out to be non-optimal, then

simply record the optimal sequence in the memo table. In this

fashion, you avoid the need to record every optimal sequence.

Preston Briggs

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.