On Thu, Jul 3, 2008 at 9:09 AM, Devang Patel <dpatel at apple.com> wrote:>> On Wed, Jul 2, 2008 at 7:00 PM, Mike Stump <mrs at apple.com> wrote: >>> If we apply their logic to llvm, we can dominate, if we just target 8 >>> cores. :-) > > Does this mean llvm can not dominate if llvm target 1 core machine > also ?Making an optimizer/code generator parallel is fundamentally a lot easier than making a browser parallel because the problems parallelize a lot more naturally. There are essentially two chunks of code in the llvm pipeline that take up large amounts of time: the optimization passes and the code generator. I think parallelizing both of these is feasible with conventional parallelism techniques, with very little penalty for the single-core case. That said, that wasn't the point I was trying to make by linking to that blog post; I was really trying to point in the direction of building new programming tools with LLVM. Parallelizing a web-browser to many cores involves much more difficult issues. -Eli
On Jul 3, 2008, at 10:28 AM, Eli Friedman wrote:> On Thu, Jul 3, 2008 at 9:09 AM, Devang Patel <dpatel at apple.com> wrote: >>> On Wed, Jul 2, 2008 at 7:00 PM, Mike Stump <mrs at apple.com> wrote: >>>> If we apply their logic to llvm, we can dominate, if we just >>>> target 8 >>>> cores. :-) >> >> Does this mean llvm can not dominate if llvm target 1 core machine >> also ? > > Making an optimizer/code generator parallel is fundamentally a lot > easier than making a browser parallel because the problems parallelize > a lot more naturally.It is hard for me to agree or disagree because I do not know typical web browser architecture.> There are essentially two chunks of code in the > llvm pipeline that take up large amounts of time: the optimization > passes and the code generator. I think parallelizing both of these is > feasible with conventional parallelism techniques, with very little > penalty for the single-core case. > > > That said, that wasn't the point I was trying to make by linking to > that blog post; I was really trying to point in the direction of > building new programming tools with LLVM. Parallelizing a web-browser > to many cores involves much more difficult issues.host vs. target If LLVM itself is parallelized than it can spit out optimized code faster if the host has multiple cores. This is a win for developers who use LLVM based compiler, e.g. web browser developers. If LLVM targets machines with multiple cores then the generated code runs faster on machines with 8 cores. This is a big one for end users whose application is compiled using LLVM based tools., e.g. web browser users. Mike is well versed in compiler host/target terminology so I asked him the question. - Devang
On Thu, 3 Jul 2008, Eli Friedman wrote:>> Does this mean llvm can not dominate if llvm target 1 core machine >> also ? > > Making an optimizer/code generator parallel is fundamentally a lot > easier than making a browser parallel because the problems parallelize > a lot more naturally. There are essentially two chunks of code in the > llvm pipeline that take up large amounts of time: the optimization > passes and the code generator. I think parallelizing both of these is > feasible with conventional parallelism techniques, with very little > penalty for the single-core case.This is also something I'm interested in supporting. The whole design of the FunctionPassManager and CallGraphSCCPassManager (e.g. inliner) is to allow parallelism of optimizations between different parts of the program. There are three main problems with this: 1) There are various places in LLVM that use globals, e.g. to unique types and for a couple things in the code generator. This should be easy to synchronize on or eliminate. 2) Various passes poke at the module to get things like intrinsics, function declarations, etc. I think this is easy to solve with locking and would be easy. 3) The use/def chain machinery in LLVM violates the principle that local manipulation doesn't touch global objects. This is because *everything* has use/def chains, including global variables and even constants (e.g. 'i32 2'). Solving this is much trickier than #2, but seems feasible with some tricky atomic access algorithms. -Chris -- http://nondot.org/sabre/ http://llvm.org/
On Thu, Jul 3, 2008 at 11:00 AM, Devang Patel <dpatel at apple.com> wrote:> > On Jul 3, 2008, at 10:28 AM, Eli Friedman wrote: > >> On Thu, Jul 3, 2008 at 9:09 AM, Devang Patel <dpatel at apple.com> wrote: >>>> On Wed, Jul 2, 2008 at 7:00 PM, Mike Stump <mrs at apple.com> wrote: >>>>> If we apply their logic to llvm, we can dominate, if we just >>>>> target 8 >>>>> cores. :-) >>> >>> Does this mean llvm can not dominate if llvm target 1 core machine >>> also ? >> >> Making an optimizer/code generator parallel is fundamentally a lot >> easier than making a browser parallel because the problems parallelize >> a lot more naturally. > > It is hard for me to agree or disagree because I do not know typical > web browser architecture.Okay... in case you're interested, I can give a quick description of some of the issues: first is the pipeline of actually rendering a page, parsing->DOM construction->style resolution->layout->painting, which is essentially serial; within the parsing, DOM construction, and layout stages, it's very difficult to do parallelization because later pieces of the document depend on earlier pieces. (This is fast enough single-threaded to not be a serious issue on a desktop computer these days, but it's still an issue on lower-power devices, and for heavy DOM manipulation.) Another is that Javascript is fundamentally single-threaded, so it's extremely difficult to parallelize. And multiple pages can interact with each other's state, which complicates things even further.>> There are essentially two chunks of code in the >> llvm pipeline that take up large amounts of time: the optimization >> passes and the code generator. I think parallelizing both of these is >> feasible with conventional parallelism techniques, with very little >> penalty for the single-core case. >> >> >> That said, that wasn't the point I was trying to make by linking to >> that blog post; I was really trying to point in the direction of >> building new programming tools with LLVM. Parallelizing a web-browser >> to many cores involves much more difficult issues. > > host vs. target > > If LLVM itself is parallelized than it can spit out optimized code > faster if the host has multiple cores. This is a win for developers > who use LLVM based compiler, e.g. web browser developers. > > If LLVM targets machines with multiple cores then the generated code > runs faster on machines with 8 cores. This is a big one for end users > whose application is compiled using LLVM based tools., e.g. web > browser users. Mike is well versed in compiler host/target terminology > so I asked him the question.Oh, okay... sorry to drag your question off-topic. -Eli