7 ms·

How does one keep serial semantics while making parallelism explicit? Those two goals seem to be in conflict, one with the other.

scott_s 15y ago
Out of order processors do it all the time: http://en.wikipedia.org/wiki/Out-of-order_execution http://en.wikipedia.org/wiki/Out-of-order_execution Most modern processors execute instructions out of order. They have hardware logic specifically designed to keep track of dependencies among the instructions, ensuring that even though instructions are executed out of order, instructions are committed in order, and if instruction A depends on the result of B, A does not execute until B finishes. And therein lies your answer: many operations "don't care" what order they are executed in. Consider the algebraic expression A + B + C + D + E. You can "execute" that expression in any way, even doing some in "parallel" and still end up with the same answer that you would if you did it the intuitive way, from left to right. That's trivial. If you have A + B * C + D * E, then it's a little more complicated because you have to ensure that B * C happens before the additions that involve B and C, and same with D * E. But surely it's not hard to imagine a static analysis that recognizes such dependencies, and a runtime that enforces their order. So no matter what order the expressions were actually executed in, you can pretend they happend in the serial one you expected.
- numeromancer 15y ago
  Thank you. What you say is correct, but not to the point. The expression you gave is not explicitly parallel. And more to the point, if I can expect expressions to be executed in a serial order, than I don't see how I can make them explicitly parallel.
  - scott_s 15y ago
    Think of it as an explicit request for parallelism. So I may say something like: parallel_sum(array); And it would do a data-parallel summation of my array. In fact, OpenMP (http://openmp.org/wp/ http://openmp.org/wp/) is a great example of what you're asking about. #pragma omp for for (int i = 0; i < N; ++i) { dest[i] = a[i] + b[i] * c[i]; } That is explicitly requested parallelism with serial semantics. The serial semantics are what you would expect without the omp pragma. But at runtime, it will execute in parallel. The compiler ensures that I did not do anything which will violate serial semantics, and the runtime system does the work of farming the work off to threads, and then synchronizing them.
    - numeromancer 15y ago
      This may be pedantic, but the #pragma seems more to be overriding the serial semantics, rather than complementing it. BTW: what do you think of OpenMP? What are its conveniences and frustrations? I may be looking into ways of doing embedded parallel development soon, and OpenMP looks convenient, since it's implemented in gcc.
      - scott_s 15y ago
        No, semantics are what something means. The results of executing the code - it's semantics - are the same with and without the pragma. If that distinction bothers you, consider that compilers perform all sort of dirty tricks when optimizations are turned on, sorts of things that you didn't ask it to do, but it is allowed to do because it preserves semantics. If you have data parallel code and you're working in C, C++ or Fortran, OpenMP is an excellent solution to gain performance from shared memory parallel machines. While I say above that it's a hack, it's a hack in terms of language design, it works. It's a very well defined standard, and any problem that you have will have been encountered by thousands of people before you, so you should be able to find solutions online easily. It's super convenient for data parallel code like the above. It's frustrating when you want to do task parallelism. I'm unfamiliar with OpenMP in the embedded world, though. OpenMP in gcc relies on Pthreads, and I don't know if that will be supported on your platform.
snorkel 15y ago
For example a for loop is typical serial semantics: for (i=0;i<10;i++) { a[i] = i*10; } ... but it's obvious that this loop can execute all passes in parallel so we want to pass a concurrency suggestion to the compiler without losing the readability of the code, so perhaps something like this block syntax: parallel { for (i=0;i<10;i++) { a[i] = i*10; } }

scott_s 15y ago

Out of order processors do it all the time: http://en.wikipedia.org/wiki/Out-of-order_execution http://en.wikipedia.org/wiki/Out-of-order_execution Most modern processors execute instructions out of order. They have hardware logic specifically designed to keep track of dependencies among the instructions, ensuring that even though instructions are executed out of order, instructions are committed in order, and if instruction A depends on the result of B, A does not execute until B finishes. And therein lies your answer: many operations "don't care" what order they are executed in. Consider the algebraic expression A + B + C + D + E. You can "execute" that expression in any way, even doing some in "parallel" and still end up with the same answer that you would if you did it the intuitive way, from left to right. That's trivial. If you have A + B * C + D * E, then it's a little more complicated because you have to ensure that B * C happens before the additions that involve B and C, and same with D * E. But surely it's not hard to imagine a static analysis that recognizes such dependencies, and a runtime that enforces their order. So no matter what order the expressions were actually executed in, you can pretend they happend in the serial one you expected.

numeromancer 15y ago
Thank you. What you say is correct, but not to the point. The expression you gave is not explicitly parallel. And more to the point, if I can expect expressions to be executed in a serial order, than I don't see how I can make them explicitly parallel.
- scott_s 15y ago
  Think of it as an explicit request for parallelism. So I may say something like: parallel_sum(array); And it would do a data-parallel summation of my array. In fact, OpenMP (http://openmp.org/wp/ http://openmp.org/wp/) is a great example of what you're asking about. #pragma omp for for (int i = 0; i < N; ++i) { dest[i] = a[i] + b[i] * c[i]; } That is explicitly requested parallelism with serial semantics. The serial semantics are what you would expect without the omp pragma. But at runtime, it will execute in parallel. The compiler ensures that I did not do anything which will violate serial semantics, and the runtime system does the work of farming the work off to threads, and then synchronizing them.
  - numeromancer 15y ago
    This may be pedantic, but the #pragma seems more to be overriding the serial semantics, rather than complementing it. BTW: what do you think of OpenMP? What are its conveniences and frustrations? I may be looking into ways of doing embedded parallel development soon, and OpenMP looks convenient, since it's implemented in gcc.
    - scott_s 15y ago
      No, semantics are what something means. The results of executing the code - it's semantics - are the same with and without the pragma. If that distinction bothers you, consider that compilers perform all sort of dirty tricks when optimizations are turned on, sorts of things that you didn't ask it to do, but it is allowed to do because it preserves semantics. If you have data parallel code and you're working in C, C++ or Fortran, OpenMP is an excellent solution to gain performance from shared memory parallel machines. While I say above that it's a hack, it's a hack in terms of language design, it works. It's a very well defined standard, and any problem that you have will have been encountered by thousands of people before you, so you should be able to find solutions online easily. It's super convenient for data parallel code like the above. It's frustrating when you want to do task parallelism. I'm unfamiliar with OpenMP in the embedded world, though. OpenMP in gcc relies on Pthreads, and I don't know if that will be supported on your platform.

snorkel 15y ago

For example a for loop is typical serial semantics: for (i=0;i<10;i++) { a[i] = i*10; } ... but it's obvious that this loop can execute all passes in parallel so we want to pass a concurrency suggestion to the compiler without losing the readability of the code, so perhaps something like this block syntax: parallel { for (i=0;i<10;i++) { a[i] = i*10; } }