Giorgio Zoia wrote:
> >Think of the following code block:
> >
> > asig w,x,y,z;
> >
> > w = sum(y, z); // 1
> > x = sum(x, y); // 2
> > x = sum(x, z); // 3
> >
...
> 2) I could merge the two sum calls and create a sum(x,y,z), and
> in this
> case I could parallelize the execution, i.e.
>
> for (i=0;i<ksmps;i++) {
> x[i] = x[i-1] + y[i];
> x[i] = x[i] + z[i];
> }
> In my opinion it is theoretically possible to go through the flow-graph and
> merge all the lines that involves a certain feedback, so that I can
> parallelize
> the execution.
...
> I fear that finding out the block-based
> code for all circumstances will be a heavy optimization task for the
> compiler or interpreter.
> Comments ? Is my analysis correct ? Can I consider this as a starting point
> for this issue ?
I think that the problem might be restated as finding a topological sort
of a graph which becomes direct and acyclic as soon as the unit delays
implicit in variable sample-carried dependencies have been cut.
In x=sum(x,y); x=sum(x,z); there is one such delay between the second
left-side x and the first right-side x.
Once a thread of execution has been found in topological sorting, this
can be enclosed within a for loop such as that indicated above. This
loop might be unrolled but I am not quite sure it can be parallelized
because of loop-carried dependencies.
Another, even harder, issue is the possibility of solving loops which
are non-computable by specification. They occur frequently in physical
modeling where subsystems are discretized independently and then
connected. Up to now, the most used approach is to insert a fictituous
unit delay (but this introduces inaccuracy). However, there are methods
for solving these loops exactly by changing the underlying graph, which
one might consider to automate.
As an example, consider the following pseudo-code, representing a
nonlinear map coupled with a dynamic linear system:
y = f(x);
x = dyn(y);
In the saol semantics, there is always a unit delay between the two x's.
Am I right? This might be source of instabilities and inaccuracy.
I should be thinking about these issues in the near future, so I will be
happy to discuss with you if there's interest.
davide
+----------------------------------------------+
Davide Rocchesso
Ist. Policattedra - Fac. di Scienze
Strada Le Grazie - 37134 Verona (IT)
Tel. (+39)(0)45-8098979
Fax. (+39)(0)45-8098928
e-mail: rocchesso@sci.univr.it
http://www.dei.unipd.it/ricerca/csc/people/roc
+ ---------------------------------------------+
This archive was generated by hypermail 2b29 : Wed May 10 2000 - 12:14:10 EDT