jarred at webkit.org
Fri Apr 12 13:43:10 PDT 2013
Argh, sending from the right address this time.
On Fri, Apr 12, 2013 at 4:39 PM, Jarred Nicholls
<jarred.nicholls at gmail.com>wrote:
> On Fri, Apr 12, 2013 at 2:54 PM, Filip Pizlo <fpizlo at apple.com> wrote:
>> On Apr 12, 2013, at 8:36 AM, "Hudson, Rick" <rick.hudson at intel.com>
>> hardware's power stingy parallelism.
>> True, but there is also the question of how high of a priority we should
>> give to this relative to other project goals, and also what opportunity
>> costs are introduced from any particular implementation of parallelism that
>> we choose. What you are proposing will only work for code that performs
>> non-effectful operations. This is a limited form of parallelism, and I'm
>> not sure that it's a general enough programming model to warrant adding new
>> things to the platform.
>> > For completeness there seems to be the following approaches.
>> > 1) Add nothing to the language and rely on increasingly
>> sophisticated compilers to detect opportunities to safely parallelize
>> computations within the current semantics.
>> > 2) Add methods to Array that provide parallel semantics.
>> > 3) Add syntax and keywords such as parallelFor to introduce
>> > 4) Add a parallel type (ParallelArray) and associated methods that
>> provide parallel semantics.
>> You forgot the obvious ones:
>> 5) Message passing
>> 6) Shared mutable memory with either threads and locks, or something
>> along those lines.
>> We sort of already have (5) but it is half baked; I think there is
>> opportunity to improve it.
>> We don't have (6). (6) subsumes all of (1), (2), (3), (4), and (5) as it
>> would allow the programmer to roll all of those primitives in JS.
>> We should not reject shared mutable memory out of hand. It is the
>> prevailing technique for implementing concurrency and parallelism in the
>> other languages that people use.
>> > The _nothing_ approach would have to deal with array methods, such as
>> map and reduce, that have sequential semantics. For example reduce is
>> really reduce right (or fold right) and these semantics defeat
>> parallelization. For example the EIC signature for the function/closure
>> passed to reduce assumes E === C[I] but the value E could be the result of
>> previous invocation of the function. This approach seems to be strictly
>> worse than the methods approach. A similar nothing approach is to analyze
>> loops to mechanically discover opportunities for parallelization. While
>> there exists decades of literature that have been full of optimism the
>> reality is that this approach has not achieved wide spread success.
>> Part of that lack of success stems from the fact that most code that does
>> things to arrays has subtle loop-carried side-effects. The closures passed
>> to ParallelArray methods could have those, also; and if they did then you
>> wouldn't be able to soundly parallelize.
>> You haven't convinced me that ParallelArray will be any more successful
>> than the full autoparallelization approach. You also haven't convinced me
>> that it will be any more successful than other eclectic ideas, like OpenMP,
>> for example. I don't think that such annotation-based approaches have been
>> particularly successful in other languages. The languages that have seen
>> the most success in parallel development are precisely those that give
>> *complete* control to the programmer, such as Java, which gives you threads
>> and locks combined with a sensible memory model - and allows you to craft
>> your algorithm in the way that best suits your problem domain. Why is this
>> approach being rejected?
>> > The _methods_ approach side steps the semantics issue raised in the
>> nothing approach but does not compose well with the original methods. For
>> example Array has several inherently sequential methods, such as push and
>> pop, that do not have a reasonable parallel semantics since they force
>> > That said this approach has its proponents. Nico
>> http://smallcultfollowing.com/babysteps/blog/2013/02/26/splitting-the-pjs-api/suggested that we add unorderedMap and unorderedReduce to indicate that the
>> scheduling of the computation be unordered. While the idea is compelling on
>> the surface it is likely to lead to the development of algorithms that are
>> at first sequential and then hacked to make them parallel. This approach
>> will impede the goal of having programmers develop parallel algorithms and
>> the appropriate parallel data structures. The methods approach would miss a
>> real opportunity here to move programmers away from the sequential models
>> and on to parallel models.
>> ParallelArray also misses this opportunity. The only thing that
>> ParallelArray does is adds methods that could have been added to Array, and
>> requires you to say, when you write your code, if you want parallelization
>> or not. The only problem this solves is inferring the "is it profitable to
>> parallelize" question. I'm not sure that inferring the answer to this
>> question is hard enough to warrant a new type.
>> > The _syntax_ approach suggests that we follow the lead of Amp and add
>> not being backwardly compatible and like the methods approach misses an
>> opportunity to move programmers away from their sequential mindset.
>> > The _parallel type_ approach provides a clear separation from the
>> semantics of Array and in doing so does a much better job of encouraging
>> programmers to build parallel algorithms and data structures instead of
>> attempting to parallelize sequential algorithms.
>> The methods approach also provides such a clear separation.
>> Just adding the word "Parallel" to the name of a new type and saying that
>> this is the only type that benefits from parallelism does not constitute
>> positive encouragement of any kind. Quite the opposite, it seems the only
>> thing it encourages is for VM engineers to give up on the inference
>> approach entirely.
>> > The contract between the programmer and the system can be better
>> defined if ParallelArray exists independently of Array and the two
>> prototypes could develop independently. That is not to say that we
>> shouldn't follow the principle of least surprise and leverage the
>> programmer's familiarity with the Array methods signatures. For example the
>> kernel/callback function should follow the same conventions found in the
>> Array.map signature such as the call back (kernel) function formals being
>> element, index, array.
>> But this is a double-edged sword: having a separate array type with
>> separate semantics incurs opportunity costs for optimization. As the two
>> prototypes diverge, there will be optimizations that get implemented less
>> well in one than in the other.
>> Supporting more types in a compiler is never free.
>> > Furthermore the parallel type approach is a clear indication to the SDE
>> and JIT implementers that the programmer wishes to execute this code in
>> parallel. The SDE will be able to assist the programmer when they don't
>> follow the contract, for example by throwing when it encounters a kernel
>> with side effects.
>> But how will developers debug this exception? Likely by using something
>> like the Inspector's exception view which highlights parts of the code that
>> We can do the same thing for autoparallelization in the "methods"
>> approach: we can highlight those array method calls that were parallelized,
>> as well as those that didn't.
>> I don't buy your argument that ParallelArray handles this developer
>> scenario any better than the other approaches. Whether the failure case
>> throws an exception, or not, either way we can highlight the fact that one
>> kernel or another wasn't parallelized.
>> > While the parallel type approach could be implemented on top of the
>> methods or even the syntax approach information about the intent of the
>> programmer would be lost to the JIT and the SDE. In summary the real value
>> in adding ParallelArray as its own type is that it helps move the developer
>> structure his programs and choose his algorithms with parallelism in mind
>> and convey that intent clearly.
>> This argument can be used in favor of any parallel or concurrent
>> programming model. If I run s/ParallelArray as its own type/threads and
>> locks/ on your statement, I get a convincing argument for the traditional
>> approach to shared memory parallelism.
>> I do believe that parallelism, and concurrency, are features that should
>> limited-use restricted programming model for this purpose.
> TL;DR: I'd rather see ParallelArray be a library that is built on top of
> lower-level primitives.
> For as little worth as it is, I agree with you Filip that providing
> low-level primitives would be best in terms of a foundation for many
> parallel programming models. In terms of actually supporting shared
> mutable memory and locks, it would be a challenge for the engines to become
> thread-safe (internally) across contexts that share memory cells. I'd
> envision the sharing of mutable memory being an opt-in semantic, marking a
> piece of memory as being shared/mutable from multiple contexts.
> The fact is, parallelism comes in many different forms and use cases.
> Performing side-effect homogenous tasks over an Array of data is one type
> of problem (and which can be GPU accelerated easily). Performing separate
> heterogenous operations on shared (or unshared) memory can be different
> more general problem altogether. I'd tend to prefer a solution that
> provides the primitives to solve all such cases, and can be further
> abstracted & simplified by user-land code to implement different parallel
> programming models. There are others out there that would vehemently
> disagree with that approach, and their objections are understandable.
>> webkit-dev mailing list
>> webkit-dev at lists.webkit.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the webkit-dev