Re: A perspective on parallelism

Anton Ertl wrote:

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.

In which case, I would offer lots of objections on the subject of fine-grain synchronization overhead, dominance of worst case patterns, impact of cache misses.


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.



I absolutely agree. 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.

This brings us back to my original point:
This means that you've got to embed a particular order in the search space,
>>>> which will impact the parallelism available to be exploited and the order
>>>> in which it can be exploited.

In our example, if you're now running on a 128 processor machine, you're out of luck - you've embedded the decision to support upto 64 processors into your logic.

You could rework it so that you divided the chunks based on the amount of work, so that you could say "I will partition up the work into chunks of 100 instructions each", but then that leads to your other point:

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

If you pick the chunk-size too small, it defeats the purpose of instruction selection, if you make it too big, there is no gain from parallelization.
.

Relevant Pages

  • Re: A perspective on parallelism
    ... you better have a randomization to uncover that bug early ... No, its not a bug in the pattern description, its a bug in the user ... The bug in the pattern had been there since 1994; ... if we were to split the original sequence down the middle and hand ...
    (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