Bayle Shanks's website: proj-oot-ootConcurrencyNotes2

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.4173 Four Concurrency Primitives for Haskell (1995) by Enno Scholz

https://www.google.com/search?q=small+set+of+concurrency+primitives

http://research.microsoft.com/en-us/um/people/simonpj/papers/lw-conc/

http://julia.readthedocs.org/en/latest/manual/parallel-computing/

" Parallel programming in Julia is built on two primitives: remote references and remote calls. A remote reference is an object that can be used from any process to refer to an object stored on a particular process. A remote call is a request by one process to call a certain function on certain arguments on another (possibly the same) process. A remote call returns a remote reference to its result. Remote calls return immediately; the process that made the call proceeds to its next operation while the remote call happens somewhere else. You can wait for a remote call to finish by calling wait on its remote reference, and you can obtain the full value of the result using fetch. You can store a value to a remote reference using put. "

http://davidad.github.io/blog/2014/03/23/concurrency-primitives-in-intel-64-assembly/

---

http://berb.github.io/diploma-thesis/community/050_index.html

---

http://blog.ezyang.com/2014/01/so-you-want-to-add-a-new-concurrency-primitive-to-ghc/

---

http://www.cl.cam.ac.uk/~so294/documents/ec209.pdf

Relaxed memory models must be rigorous

---

http://www.cs-lab.org/historical_beam_instruction_set.html

---

http://www.cs-lab.org/historical_beam_instruction_set.html#2.9%20Inter-process%20Communication

---

" Concurrency is concerned with controlling non-determinism, which can arise in all sorts of situations having nothing to do with parallelism. Process calculi, for example, are best viewed as expressing substructural composition of programs, and have very little to do with parallel computing. (See my PFPL and Rob Simmons’ forthcoming Ph.D. dissertation for more on this perspective.) " -- http://existentialtype.wordpress.com/2012/08/26/yet-another-reason-not-to-be-lazy-or-imperative/

---

" ppgallardo says: May 2, 2011 at 6:37 am

Rate This

Dear Prof. Harper,

According to your own comments:

I simply meant that it is not clear whether monadic isolation of effects (esp store effects) is a good idea, because it precludes benign effects.

… for the sake of parallelism: you can’t evaluate a Sequence.map in parallel unless you know that the function being mapped is effect-free.

It seems that there is a conflict here. You can either have effects isolated by default (Haskell), which is good for parallelism, but requires some mechanism like unsafePerformIO to use begin effects, or you can have unsafe free access to effects by default (ML), which is good for begin(safe) effects, but you would need your own effect system to use parallelism. I don’t see clearly that this second approach is a better one. Reply

    ppgallardo says:	
    May 2, 2011 at 10:04 am	
     
    0
     
    0
     
    Rate This

    Sorry, I meant benign effects
    Abstract Type says:	
    May 2, 2011 at 11:30 am	
     
    5
     
    0
     
    Rate This

    Exceptions are perfectly compatible with parallelism; it is only storage effects (which includes I/O that creates a problem. If we isolate storage effects using a re-organized library in the manner I described, we get what we need for parallelism. I consider this significant, but you may not. The concept of purity is not entirely clear, it seems to me.
    neelk says:	
    May 3, 2011 at 4:00 am	
     
    0
     
    0
     
    Rate This

    When you say exceptions are compatible with parallelism, do you mean exceptions with or without handlers?

    In the absence of handlers you’re obviously correct (and it synergizes beautifully with strictness), but if there’s a catch-form then it seems to me that the naive parallel semantics becomes nondeterministic.

    Using par(e,e') to indicate a parallel tuple, consider the expression:

      par(raise (Error 1), raise (Error 2))
      handle 
        Error n => n

    This seems like it may give different answers depending on the scheduling of the left and right components of the pair.
    Abstract Type says:	
    May 3, 2011 at 3:48 pm	
     
    3
     
    0
     
    Rate This

    With handlers, of course, otherwise they wouldn’t be called exceptions! Your example shows only that the join-point logic is more subtle than you are imagining it to be. The crucial point is to ensure that parallelism does not change the semantics of the program. So, in this case, we must ensure that the leftmost exception is the one that is propagated, if any, because that is what would happen in the sequential case. The join point logic ensures that this is the case; I won’t bother to describe here how that is done, it’s not hard to imagine.

    Interestingly, we can also admit other effects, such as printing, by the same means: suspend the output until the join-point is reached, then print in left-to-right order. Input doesn’t seem susceptible to this kind of treatment, but random seeds easily are, because they can be split. We rely on this to implement treaps in parallel (though there are other means based on fingerprinting that avoid the need for random numbers).

    Crucially, the forms of parallelism we consider always have a well-defined join point. Without that, I cannot envision a way to admit effects, even exceptions, in parallel without affecting the sequential meaning. So, for example, parallel futures are out of the question because there is no well-defined join point. Indeed, this is precisely the same reason why it is so awkward to manage exceptions in a lazy language, among other things.

    It seems that I ought to have explained my motivations for this post more thoroughly up front. It seemed that I could just break out the one point, re-defining the interfaces of some of the basis libraries, to get the isolation of effects that I want to ensure absence of race conditions in parallel. My mistake."

---

http://lambda-the-ultimate.org/node/1615 Event-Based Programming without Inversion of Control. Philipp Haller and Martin Odersky.

http://lambda-the-ultimate.org/node/1617#comment-19873

Still has limitations

The Scala paper acknowledges some limitations:

    To conclude, managing information about statements following a call to receive would require changes either to the compiler or the VM. Following our rationale for a library-based approach, we want to avoid those changes.

If you want statements to follow a receive, you have to manually-CPS them yourself, possibly duplicating code between different branches of the receive. Moreover, any function that calls a function that uses receive also cannot contains statements after the receive, and so on, recursively. Scala's type system will enforce that for you, but that doesn't stop it from being annoying.

For me, that's a dealbreaker. I could just as easily use Java and the Proactor pattern. I use threads so that I can write my control flow in direct-style; if I wanted to CPS things I can do so in other languages.

Now, it's certainly possible to get around this: just write a VM with first-class continuations. But then you start running into other problems, like first-class continuations not playing nicely with a C# or Java FFI (which is why Scala doesn't support them). Beware the Turing Tarpit. Once you've generalized your VM to fit every conceivable language, its functionality is probably so general that it becomes faster for a language designer to write his own VM than to target yours. By Jonathan Tang at Wed, 2006-07-19 00:50

---

[–]dons [F] 13 points 7 years ago

Right! Here's what's happening:

    Data Parallel Haskell on the GPU
    SSE for GHC

So that gives us 4 kinds of parallelism to play with:

    explicit threads (forkIO)
    implicit threads (par)
    transparent parallelism on multicore (DPH-based nested parallel arrays)
    GPU-based (nested) parallel arrays (Sean's DPH + GPU) ongoing

The GPU is really the "FP chip that never was", with its hardware supported folds, scans and maps.

Btw, Microsoft is helping fund the Data Parallel Haskell work. I guess they really need a solution for massively multicore programming :-)

    permalink
    save
    parent

'join' functions with arguments from multiple threads is natural if you allow 'shared memory' partially applied functions and closures

kyrra 1 day ago

link

Single-threaded Go programs also run faster for some (many?) cases. The runtime is able to bypass a number of locks when running in a single-threaded mode. And depending on the profile of your code, turning on multiple threads for a Go program can slow it down even if you use channels (as moving data from one CPU core to another can be much slower than just doing a context switch in a single core).

---

BKuhn likes http://vertx.io/manual.html

http://lwn.net/Articles/615834/

---

On the Connection Between Memory Management and Data-race Freedom

As I alluded in the previous post, I have noticed an interesting connection between memory management and data-race freedom. I want to take a moment to elaborate on this, becaause the connection was not obvious to me at first, but it ultimately drives a lot of the Rust design decisions.

First, I believe that if you want to guarantee data-race freedom, and you want to support the cheap transfer of mutable state between tasks, then you must have a garbage-collector-free subset of your language. To see what I mean by “cheap transfer of mutable state”, consider something like double-buffering: you have one drawing and one display task exchanging buffers (so there are only two buffers in total). While the drawing task is preparing the next frame, the display task is busy displaying the current one. At the end, they exchange buffers. In order to prevent data races in a scenario like this, it is vital that we be able to guarantee that when the buffers are exchanged, neither task has any remaining references. Otherwise, the display task would be able to read or write from the buffer that the drawing task is currently writing on.

Interestingly, if we wanted to free one of those buffers, rather than send it to another task, the necessary safety guaranty would be precisely the same: we must be able to guarantee that there are no existing aliases. Therefore, if you plan to support a scenario like double buffering and guarantee data-race freedom, then you have exactly the same set of problems to solve that you would have if you wanted to make GC optional. Of course, you could still use a GC to actually free the memory, but there is no reason to, you’re just giving up performance. Most languages opt to give up on data-race freedom at this point. Rust does not.

But there is a deeper connection than this. I’ve often thought that while data-races in a technical sense can only occur in a parallel system, problems that feel a lot like data races crop up all the time in sequential systems. One example would be what C++ folk call iterator invalidation—basically, if you are iterating over a hashtable and you try to modify the hashtable during that iteration, you get undefined behavior. Sometimes your iteration skips keys or values, sometimes it shows you the new key, sometimes it doesn’t, etc. In C++, this leads to crashes. In Java, this (hopefully) leads to an exception.

But whatever the outcome, iterator invalidation feels very similar to a data race. The problem often arises because you have one piece of code iterating over a hashtable and then calling a subroutine defined over in some other module. This other module then writes to the same hashtable. Both modules look fine on their own, it’s only the combination of the two that causes the issue. And because of the undefined nature of the result, it often happens that the code works fine for a long time—until it doesn’t.

Rust’s type system prevents iterator invalidation. Often this can be done statically. But if you use @mut types, that is, mutable managed data, we do the detection dynamically. Even in the dynamic case, the guarantee that you get is much stronger than what Java gives with fail-fast iteration: Rust guarantees failure, and in fact it even points at the two pieces of code that are conflicting (though if you build optimized, we can only provide you with one of those locations, since tracking the other causes runtime overhead right now).

One reason that we are so intolerant towards iterator invalidation is because we wish to guarantee memory safety, and we wish to do so without the use of universal garbage collection (since, as I just argued before, it is basically unnecessary if you also guarantee data-race freedom). Without a garbage collector, iterator invalidation can lead to dangling pointers or other similar problems. But even with a garbage collector, iterator invalidation leads to undefined behavior, which can in turn imply that your browser can be compromised by code that can exploit that behavior. So it’s an all-around bad thing.

Therefore, I think it is no accident that the same type-system tools that combat iterator invalidation wind up being useful to fight data-races. Essentially I believe these are two manifestations of the same problem—unexpected aliasing—in one case, expressed in a parallel setting, and in the other, in a sequential setting. The sequential case is mildly simpler, in that in a sequential setting you at least have a happens-before relationship between any two pairs of accesses, which does not hold in a parallel setting. This is why we tolerate &const and &mut aliases in sequential code, but forbid them with closure bounds in parallel code.

In some way this observation is sort of banal. Of course mutating without knowledge of possible aliases gets you into trouble. But I think it’s also profound, in a way, because it suggests that these two seemingly unrelated issues, memory management and data races, cannot be truly separated (except by sacrificing mutability).

Most languages make no effort to control aliasing; if anything, they use universal garbage collection to prevent the end user from having to reason about when aliasing might exist to a given piece of data. This works well for guaranteeing memory is not freed, but as I’ve suggested, it can lead to a variety of incorrect behaviors if mutation is permitted.

This observation has motivated a lot of the research into ownership types and linear types, research which Rust draws on. Of other recent non-research languages, the only other that I know which takes the approach of controlling aliasing is Parasail. Not coincidentally, I would argue, both Rust and Parasail guarantee data-race freedom, while most langauges do not.

Posted by Nicholas D. Matsakis rust " -- http://smallcultfollowing.com/babysteps/blog/2013/06/11/on-the-connection-between-memory-management-and-data-race-freedom/

---

https://github.com/mozilla/rust/blob/master/AUTHORS.txt

---

the correct soln is, not to have blocking versions of every call, but to make eveery call nonblocking, and to prlovidee a construct like await to turn a nonblocking call with a callback (or a stream) into a blocking call

---

a notation of 'adjacency' for threads (a graph topology); and maybe also a geometry

---

my friend PR was saying how he just does REST for most IPC instead of using a message bus, which is more complex (and can be harder to debug, if 'debuggability' was not priority for the implementation of the bus). but what about 'simple' IPC like i have in one of atr's drivers (a separate process periodically polls an external webpage, and then puts any new information it finds into update messages, which are read by the primary process and used to update in-memory data structures representing the current state of the world)? he said that's fine. We didn't talk about this but i bet the key to its simplicity is probably that (a) it is spreading information, not commands or state changes, (b) it is 'addressless', ie the semantics of the state-of-the-world update messages don't rely on them being 'sent to' any particular process. tuple spaces?

---

doesn't look too informative, but there are some lists of features:

http://stackoverflow.com/questions/134867/which-programming-language-makes-concurrent-programming-as-easy-as-possible

---

here's how i bet dataflow/the 100-step rule in the brain works:

every time a value is assigned to a register, all later instructions that depend on that value immediately start executing (or re-executing, see below)
- in this way, the number of serial 'steps' in the hundred step rule really are only the serial dependencies, the longest number of hops between the input value and the output value
a different node (neuron, CPU) is assigned to each instruction (source code location)
branches: for non-side-effectful fns, both sides of a branch are 'speculatively' executed before the branch choice is known; the branch choice then chooses which of these results is used (like a gate on a river)
- this can't be done too deeply, however, b/c the number of paths increases geometrically with the number of branch points speculatively crossed
when some but not all dependencies (register or memory locations used as inputs) of an instruction are known, the instruction executes anyways, using the 'old' values of the dependencies -- this is a 'dataflow' system after all. In this fashion, the system is continually 'guessing' even in the face of a lack of complete information (eg it's robust to partial information and to temporary cutoffs from upstream inputs)
in place of moving data values into registers and memory addresses, they are here moved into 'nodes' (neurons, CPUs); an individual node holds one data value
just as move and control instructions are the most used in machine CPUs [1]