Re: A perspective on parallelism

Mayan Moudgill <mayan@xxxxxxxxxxx> writes:
Bernd Paysan wrote:
Well, when the implicit order of GCC patterns hides a bug in the pattern
description, you better have a randomization to uncover that bug early
enough. It will occur sooner or later anyway.

No, its not a bug in the pattern description, its a bug in the user
source code.

Of which user? Do you mean to say that if the code generated by gcc
produces the wrong result for "-(x>y)", then that expression is buggy?

See <http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31152>

The bug in the pattern had been there since 1994; it did not show up
gcc-3.3, but it did show up in gcc-4.1, without parallelization. This
demonstrates that such bugs are uncovered sooner or later anyway.

Some forms of pattern based selection _might_ be order invariant.
However, in general they are not. Worse, finding the best set of
selections is generally NP-complete, probably for very simple cases. I
suspect it is enough to allow pattern matching across branches and
permit a small set of overlapping patterns such as:
{A,B} -> Xab
{B,C,D} -> Ybcd
Given that there is no guarantee that we're going to find the best
answer (NP-complete, remember), the instruction selector will generally
use some hueristic, such as greedy.

Using the greedy heuristic, the sequence
M,N,A,B,C,D
will get converted into
M,N,Xab,C,D.
Now, if we were to split the original sequence down the middle and hand
each half to separate threads doing greedy combining,

I think that Bernd meant something different: there are many patterns
that are checked on each sequence. Bernd does not want to split the
sequence, but wants to run the pattern checks in parallel instead of
one after the other.

the result would
be M,N,A from thread 1 and Xbcd from thread 2, combining to give
M,N,A,Xbcd.
Clearly this is better than the sequence found by the sequential
approach, but that is not the relevant point - the point is that it is
different.

So what? In this case it is totally deterministic. You can program a
sequential version that gives the same result. And if your patterns
are correct, this result will be correct.

The problem with this scheme I see is that dividing sequences at
arbitrary places will probably reduce the code quality on average.

- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@xxxxxxxxxxxxxxxxxxxxxxxxxx Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
.

Relevant Pages

  • Re: A perspective on parallelism
    ... No, its not a bug in the pattern description, its a bug in the user source code. ... Now, if we were to split the original sequence down the middle and hand each half to separate threads doing greedy combining, ... You make a decision that "instruction selection will handle upto 64 threads", pick 64 partitions, and run instruction selection on each partition, in parallel or sequentially or some mixture, depending on the number of available resources. ...
    (comp.arch)
  • Re: A perspective on parallelism
    ... Well, when the implicit order of GCC patterns hides a bug in the pattern description, you better have a randomization to uncover that bug early enough. ... Given that there is no guarantee that we're going to find the best answer, the instruction selector will generally use some hueristic, such as greedy. ... Using the greedy heuristic, the sequence ...
    (comp.arch)
  • Re: A perspective on parallelism
    ... the same sequence of intructions, and some exhibit a bug and other ... when the implicit order of GCC patterns hides a bug in the pattern ... cycles, and another match that takes 4 cycles, and you then choose the 3 ...
    (comp.arch)
  • Re: an true information theory
    ... If a message has meaning then it has structure and will show a pattern. ... if there is a pattern in the sequence of numbers. ... solve the halting problem, which is uncomputable. ...
    (sci.math)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... If the phenomenon in question shows a random-type pattern, ... have access to a code that contains a much longer sequence. ... Your model of single bit compression does not seem to me to be a ... strings with shorter input strings depends on the reference computer. ...
    (talk.origins)
Loading