3 ms·

For thread-level parallelism to be added you need to perform something akin to Fourier-Motzkin resolution algorithm or Omega test to find out what dependencies

by thesz 9y ago

For thread-level parallelism to be added you need to perform something akin to Fourier-Motzkin resolution algorithm or Omega test to find out what dependencies program has and has not. FM is NP-hard. Omega test is imprecise. And in general you need more complicated checks like aliasing checks. Which are equal to stopping problem, most of the time. Usually you can't spend that amount of time on EACH INVOCATION of a program.

chrisseaton 9y ago
The techniques you are talking about are for proving that there is parallelism. The beauty of a JIT is that you can speculate that there is parallelism, go ahead, and then sort out the mess later and recompile to sequential if there wasn't. https://en.wikipedia.org/wiki/Speculative_multithreading https://en.wikipedia.org/wiki/Speculative_multithreading You can use hardware functionality such as TSX to support this.
- thesz 9y ago
  You can't speculate about parallelism when dealing with shared resource. It is unbelievable you even suggested it. TSX won't save you.
  - chrisseaton 9y ago
    > You can't speculate about parallelism when dealing with shared resource Why do you think that? What do you think the optimistic software transactional memory algorithms are doing if not speculating on parallel access to shared memory?
    - thesz 9y ago
      Because you have O(n) for size of transaction and this O will quickly rise to overflow any buffers you have in hardware, for one. Because Microsoft tried to add STM to the .Net and get 4x slower code after extensive effort: http://www.mail-archive.com/haskell-cafe@haskell.org/msg79739.html http://www.mail-archive.com/haskell-cafe@haskell.org/msg7973... Should I continue from these two arguments?
      - chrisseaton 9y ago
        You've just said that you 'can't speculate about parallelism when dealing with shared resource', and then gave me an example of a system that did exactly that. Clearly, it is possible to do speculative parallelism of shared resources. We may not yet know how to make it efficient, but it is possible.
        thesz 9y ago
        From what I gather, STM in .Net heavily relies on the static program analysis. You may see it as a proof of your point, but I see it as a counterexample - a team of smart people was not able make speculative parallelism efficient even with static analysis. JIT will be even less efficient as it has to keep and account for tracing information and for speculation logs. These two interact in interesting way, I guess.

by thesz 9y ago

chrisseaton 9y ago

The techniques you are talking about are for proving that there is parallelism. The beauty of a JIT is that you can speculate that there is parallelism, go ahead, and then sort out the mess later and recompile to sequential if there wasn't. https://en.wikipedia.org/wiki/Speculative_multithreading https://en.wikipedia.org/wiki/Speculative_multithreading You can use hardware functionality such as TSX to support this.

thesz 9y ago
You can't speculate about parallelism when dealing with shared resource. It is unbelievable you even suggested it. TSX won't save you.
- chrisseaton 9y ago
  > You can't speculate about parallelism when dealing with shared resource Why do you think that? What do you think the optimistic software transactional memory algorithms are doing if not speculating on parallel access to shared memory?
  - thesz 9y ago
    Because you have O(n) for size of transaction and this O will quickly rise to overflow any buffers you have in hardware, for one. Because Microsoft tried to add STM to the .Net and get 4x slower code after extensive effort: http://www.mail-archive.com/haskell-cafe@haskell.org/msg79739.html http://www.mail-archive.com/haskell-cafe@haskell.org/msg7973... Should I continue from these two arguments?
    - chrisseaton 9y ago
      You've just said that you 'can't speculate about parallelism when dealing with shared resource', and then gave me an example of a system that did exactly that. Clearly, it is possible to do speculative parallelism of shared resources. We may not yet know how to make it efficient, but it is possible.
      - thesz 9y ago
        From what I gather, STM in .Net heavily relies on the static program analysis. You may see it as a proof of your point, but I see it as a counterexample - a team of smart people was not able make speculative parallelism efficient even with static analysis. JIT will be even less efficient as it has to keep and account for tracing information and for speculation logs. These two interact in interesting way, I guess.