Re: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
Excerpts from t.r.willingham's message of Sun Nov 02 17:28:08 -0600 2008: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? Thanks, TW Hi, The main issue has to do with the decisions the compiler needs to make in order to generate adequate code for a general case. The problem is the compiler has to make decisions about the *granularity* of the threading in particular - the generated code for example may waste a lot of time sparking off threads using 'par' or something, for computations that take less time than the thread-creation itself, meaning the overall cost of that thread being spawned was negative. So your code would need the threading to be more coarse-grained. On the other hand, if you have some computation, the compiler may not adequately sprinkle enough par's throughout the program, and therefore we miss opportunities where the parallelism could give us a speed up - in this case, we need more fine-grained threading. So the problem is (in the general case): given an arbitrary input program, how do you adequately decide what should and should not be parallelized in that program? Even then, how do you decide the granularity at which the threads should operate? It's a pretty tough problem, and I don't think we're even close to full-blown automagically-parallelizing compilers (although with things like parallel strategies and DPH we can get close.) But there is work in this area using profiling information to guide these optimizations, see Feedback directed implicit parallelism here: http://research.microsoft.com/~tharris/papers/2007-fdip.pdf Austin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
I was surprised when I read the multi-core section of Real World Haskell which explains the use of par, seq, and force to achieve parallelism. While it's obvious a programmer could provide useful parallelism hints to the compiler, given the nature of the language I would have thought Haskell could do a significant amount of parallelism itself without any hints or code changes at all. I am thinking of our troglodytic friend 'make', which will run (for example) 4 parallel jobs when given the option make -j4. Even 'rake', the ruby version of make, now has a branch (called drake) which does the parallel -j option. Since much of Haskell code is free of side effects, it would seem that it can be analyzed in similar manner to Makefile dependencies in order to find sections which can be run in parallel. What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? Thanks, TW ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
Hello T, Monday, November 3, 2008, 2:28:08 AM, you wrote: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC this part of job is large enough -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC this part of job is large enough Right, but couldn't the Haskell complier+runtime discover rather large pieces of work? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
t.r.willingham: On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC this part of job is large enough Right, but couldn't the Haskell complier+runtime discover rather large pieces of work? Requires runtime profiling to work out the costs. See this paper which implements this this idea, PDF http://research.microsoft.com/~tharris/papers/2007-fdip.pdf HTML http://209.85.173.104/search?q=cache:7cC4fQjCEH4J:research.microsoft.com/~tharris/papers/2007-fdip.pdf Note that for subsets of Haskell, where we have more information statically about the costs involves, we can do the parallelism automatically. Data Parallel Haskell is the prime example. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
On Sun, Nov 2, 2008 at 12:42 PM, T Willingham [EMAIL PROTECTED] wrote: On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC this part of job is large enough Right, but couldn't the Haskell complier+runtime discover rather large pieces of work? Perhaps, but not easily. Especially if it can be done statically, there is plenty of research to be done in this area. Haskell is rather different from make. The graph of a lambda calculus program is not nearly as transparent as the graph of a makefile -- *especially* considering lazy evaluation. For example, you might think: map (+1) [1..1000] Is a rather large piece of work, but if it is then applied to take 4, that is no longer true. We don't want to be futilely spinning our processor computing this. So my guess is that there are some cases, in the same way as strictness analysis, where you can identify these, but there are many cases which are much more subtle and hard to identify automatically. But I am no expert in the area. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
Bulat Ziganshin [EMAIL PROTECTED] writes: Hello T, Monday, November 3, 2008, 2:28:08 AM, you wrote: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC this part of job is large enough ..and also that this piece of work will actually need to be evaluated. With lazyness, a program can have subexpressions that are bottom as long as they are not evaluated, any kind of speculative execution must take care to handle this properly. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Automatic parallelism in Haskell, similar to make -j4?
Hello T, Monday, November 3, 2008, 3:42:49 AM, you wrote: On Sun, Nov 2, 2008 at 6:44 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: What would it take to implement a -j equivalent for, say, GHC? Or if this is not possible, what is wrong with my reasoning? problem is that make have rather large pices of work which it can run parallel. if ghc will try to parallel every machine operation, it will pend more time maintaining these jobs. 'par' is just the way to tell GHC this part of job is large enough Right, but couldn't the Haskell complier+runtime discover rather large pieces of work? are you ever herd about halting problem? it's imposible in general case and i doubt how far it may be done on practice. in general, it looks close to really compute the function (and you still need to know its actual input params!) anyway it's not done and i don't heard about researches in this direction -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
