math expressions optimalization
Trix
I`m going to implement simple alghoritm to
optimalize math expressions in terms of
use of memory cells.
E.g.
I have given out=a*b+c*(a+c+d)
then i divide this expression into parts:
x1=a*b
x2=c+d
c3=a+x2
x4=c*x3
x5=x1+x4
To do this step i just convert my expression
to Polish Notation.
Now I run alghoritm which optimalize expression.
Output is:
x1=a*b
x2=c+d
x2=a+x2
x2=c*x2
x1=x1+x2 <- out
So we`ve used only 2 memory cells - not 5 like above.
I`ve written program which do this but I`m not sure
my program works well - I`d like to compare to another
solution.
I don`t know the name of such alghoritm in English
and can find it on the net.
If somebody would provide me with links to web pages
about my problem...
Thanks.
Sid Ahmed Ali TOUATI
This seems to be close to a register allocation process.
SAAT
ps : be aware that optimizing floating point expressions is different
from optimizing mathematical expressions (rounding errors).
Walter Misar
> I`m going to implement simple alghoritm to optimalize math
> expressions in terms of use of memory cells.
> To do this step i just convert my expression to Polish Notation.
> So we`ve used only 2 memory cells - not 5 like above. I`ve written
> program which do this but I`m not sure my program works well - I`d
> like to compare to another solution.
> I don`t know the name of such alghoritm in English and can find it
> on the net.
That sounds like "Sethi Ullman numbering" [1]. It basically works
by evaluating the subexpression which is going to need the most cells
(registers) first.
[1] "The Generation of Optimal Code for Arithmetic Expressions"
by R. Sethi and J.Ullmann in "Journal of the ACM 17(4), 1970"
http://www.acm.org/pubs/citations/journals/jacm/1970-17-4/p715-sethi/
--
Walter Misar mi...@rbg.informatik.tu-darmstadt.de
Allyn Dimock
> I`m going to implement simple alghoritm to
> optimalize math expressions in terms of
> use of memory cells.
...
> I don`t know the name of such alghoritm in English
> and can find it on the net.
Normally the temporaries generated in evaluating expressions are
allocated in registers rather than in memory cells. I don't know a
particular name for your algorithm. However, see "the dragon book"
page 535 in the 1986 edition "Storage for Temporary Names" in Section
9.5: "Next-Use information". Or see Appel's books "Modern Compiler
Implementation in ..." under "Register Allocation for Trees".
In the case of register allocation, it is sometimes the case that
reusing a register name too soon limits the ability of the machine to
find instruction-level parallelism.
The same algorithm (reusing locations that are no longer live) is also
used to minimize the size of stack frames.
-- Allyn Dimock
Tomasz Kowaltowski
> I`m going to implement simple alghoritm to optimalize math
> expressions in terms of use of memory cells.
As far as I know, this problem has been solved independently by many
people and has several variants like minimizing the stack positions
used to evaluate an expression or minimizing the number of temporary
variables as in this case.
Just build a tree representing the expression. For the example given in
your message you get:
+
/ \
* *
/ \ / \
a b c +
/ \
+ d
/ \
a c
Now label nodes of the tree using the following recursive rules:
(1) A leaf receives the label 0.
(2) If the the two children of an inner node have equal labels, say
'n', then the node receives the label 'n+1'; otherwise it receives
the maximum of the two labels.
In your case:
+2
/ \
*1 *1
/ \ / \
a b c +1
0 0 0 / \
+1 d
/ \ 0
a c
0 0
Now generate your code by choosing first the subtree whose root has a
higher
label and reusing temporaries when they are free:
x1 = a*b
x2 = a+c
x2 = x2+d
x2 = c+x2
x1 = x1+x2
Again you get two temporaries (I assumed '+' is left assiociative, but
it does not change the result in this case). It is easy to prove that
this algorithm produces an optimal result.
This kind of numbering of the tree nodes is related to what is known
as Strahler numbers -- they are used also in geography to describe
complexity of confluent streams!
The problem bocomes much harder (NP-complete?) when you try to reuse
common subexpressions. I recall there is an old paper by Sethi & Bruno
about this subject.
-- Tomasz Kowaltowski
Tomasz Kowaltowski
registers (or stack positions) necessary to evaluate an expression
tree, based on a recursive bottom up numbering of its nodes. This kind
of numbering was introduced in 1952 by A. N. Strahler, a geoscience
professor at Columbia University, in order to classify river streams
with regard to their tributaries.
On the other hand, several texts attribute this numbering to the Russian
computer scientist A. Ershov. For instance, the "Dragon Book" uses the
term "Ershov numbers" and does not mention Strahler at all. Anybody
there knows why?
-- Tomasz
PS: Some years ago I posted a message about these numbers:
http://compilers.iecc.com/comparch/article/02-06-053
[I suspect it's because most people never heard of Strahler. I hadn't
until you wrote about him in 2002, then forgot until now. The first
edition of the Dragon Book called it Sethi-Ullman numbers, after two
guys at Bell Labs (including one of the authors) who reinvented
it. -John]