Missed most of first talk. Q: Relatively poor selection of benchmarks? esp. little overlap with dthreads benchmarks A: We need to run more benchmarks. ------------------------------------- Tasks with effects,m a model for disciplined concurrent programs Steve Human Uses of concurrency: performance, mixing latency-sensitive and long running tasks, or just nicer programming model. Lots can go wrong: races, deadlocks, unintentional nondeterminism, etc. Mainstream languages don't really help. Most schemes for fixing this restrict expressiveness: deterministic, fork-join, etc. Can also be slow. Tasks with effects avoids this tradeoff. Idea: -- Task-based control flow -- Task isolation -- Data race freedom -- Deadlock avoidance -- Optionally nondeterministic ``Effect'' here means the usual type-system style effect system. Task has usual meaning. Use the effect system to control scheduling. That + static checking of effect signature can ensure data race freedom. Q: Can tasks spawn new tasks? A: Yes. Q: What is the isolation guarantee for tasks? A: The obvious one: interfering tasks can't run concurrently. Q: Relate this to Jade? A: Similar idea, but Jade is always deterministic, and has less in the way of static checking. Q: Barcelona has a department working on related stuff. How does this compare? A: They don't do effect-based checking or static checking. Q: What if the system is unschedulable due to e.g. cycles? A: We use an ``effect transfer system'' to break the cycles. Q: Is that still data-race free? A: Yes. Q: How do you implement locks? A: We don't use them; use tasks and effects instead. Every method and task has an effect specification. Compiler checks that specification accurately summarises thing specified. Effect specifications reified to runtime. Q: You're using static effects and then doing runtime scheduling based on that. Have you tried narrowing the effects at runtime? A: Yes, we actually do a limited special case of that: use dynamic information to check whether effects conflict. Q: How much of a pain is it to add these effects? A: Not error prone, because it's statically checked. Could be inferred in future. Not usually a big deal. Scheduler guarantees that interfering tasks will not run in parallel. Doing this efficiently is future work . Example: increasing image contrast when the image is split in half. Side effect might be increaseContrast(im1): write(im1.top), write(im1.bottom), so you get a conflict if you increase the same image's contrast twice, but not if you increase contrast of two different images. If two items don't conflict then ordering is non-deterministic (but of course it doesn't really matter). Effect transfer. Aims: Reduce overhead, statically guarantee determinism for certain fragments, deadlock avoidance, atomicity. Idea: transfer effects between tasks. When a parent spawns a task, some of the parent's effects are transferred to the child task. In that case, the child can always start immediately (because if there were anythign which conflicted then that''d stop the parent from running), and the parent can continue (because we transfer the effects to the child rather than copying them, so it doesn't conflict with child). Join takes transferred effects back. Need extra static analysis to show that this is safe. Q: Can you do sibling to sibling transfers? A: No, only parent<->child. e.g. increaseContrast(im1) writes(top, bottom) could spawn increaseContrast(im1.bottom) writes(bottom) immediately and turn into increaseContrast(im1.top) writes(top) Nice way of handling fork/join determinism. Any job which only uses spawn/join will be deterministic. Adding @Deterministic enforces that you only use spawn/join. Can then support everything which DPJ can support. Open questions: correct representation of effects, both statically and at run time? How to extend to heterogeneous and non-shared-memory systems . Q: Previous DPJ work has looked at adding non-determinism, mostly using STM. You're doing it here by dynamically reasoning about conflicts and then scheduling to avoid them. Compare and contrast. A: This approach doesn't need STM, which helps with performance. This is better for less structured (i.e. non fork-join) stuff. Q: If you had a server, could you run each session in a task, and then have a shared cache in a task? Do you end up serialising everything? A: Serialise tasks which access the task. Effectively implement a rwlock on it. Q: If you do it statically you serialise everything. At runtime you can do it fine-grained. A: That's why we do it at runtime. Q: Jade allows you to drop effects at run-time, and acquire new ones later. Do you? A: Could, but currently don't. Risk of deadlocks when acquiring effects dynamically. ------------------------- Vijay Saraswat Determinate in X10 Distinguish rooted vs. lateral communication. i.e parent/child vs sibling-sibling. Mostly interested in clocked (i.e. phased) computations. Allow mutable variables for rooted communication, but heavily constrain lateral communication using effects. X10: divide program into places? Operations: async -> run somethng async, at (P) S -> synchronously run S at P finish S -> run S, wait for it and all of its spawned tasks to finish. when (c) S -> wait for c, then run S as an atomic transaction Performance is apparently pretty good. Clocked, collecting finish: done using the finish message for finding the termination of a graph of tasks. Idea is to incorporate a reduce operator into the finish statement. Q: Compare to Cilk++ reducers? A: Sorry, I've not dealt with Cilk++. Introduce phasing via clocked version of finish. Then introduce a clock.next() which does obvious pthread_barrier() type synchronisation. There's effectively an implicit finish result in each phase, and you can run a reduce operation in each one. Also have immutable values which are protected from races/nondeterminism using an effect system. Effect language is pretty complicated; looks dependent to me. Heap is partitioned into zones. Each type has one zone, specified statically. Zones are broadly types, but in a very fancy type system (looks like a dependent one, to me). Q: How do the types work? A: It's a SMOP for the programmer, in essence. Q: Can you introduce these types incrementally? A: Not really thought about it. Q: Have you used this? A: Not really. Have used clocked finish, but not the contraints language. Q: What kinds of bugs will there still be? A: Good question. Q: Is there a bound on how long your constraint checker can take? A: No, it's not even guaranteed decidable.