9 ms·

A Library of Parallel Algorithms

212 points by federicoponzi 9y ago

alexggordon 9y ago
Animations link appears to be broken. After doing some way back machine snooping, looks like it hasn't been up since about 2000[0]. You can access the legacy java applet animations here[1] [0] https://web.archive.org/web/20000611153404/http://web.scandal.cs.cmu.edu/cgi-bin/demo https://web.archive.org/web/20000611153404/http://web.scanda... [1] http://www.cs.cmu.edu/~scandal/applets/ http://www.cs.cmu.edu/~scandal/applets/
- visox 9y ago
  Thx, the images seem to be broken/nomore
hackermailman 9y ago
There is also the CMU free draft book on Parallel algorithms design http://www.parallel-algorithms-book.com/ http://www.parallel-algorithms-book.com/
- Athas 9y ago
  This is great! I'm really inspired by the work CMU does on parallelism. They have a parallel programming course[0] that results in some really impressive final projects [1]. I also hear that CMU takes a "parallel-first" approach to teaching algorithms and data structures, but I have not been able to find out exactly how they do that. [0]: http://15418.courses.cs.cmu.edu/fall2017/ http://15418.courses.cs.cmu.edu/fall2017/ [1]: http://15418.courses.cs.cmu.edu/fall2016/article/13 http://15418.courses.cs.cmu.edu/fall2016/article/13
  - gshrikant 9y ago
    There's also 15-210 Parallel and Sequential Data Structures and Algorithms [1] which is what book GP referred to is developed for. [1] https://www.cs.cmu.edu/~15210/ https://www.cs.cmu.edu/~15210/
Athas 9y ago
These algorithms are written in NESL, which is perhaps the cleanest example of the oft-mentioned theory that parallel programming becomes simple in a functional setting. It really is remarkable how flexible it is. Unfortunately, I'm not sure NESL ever managed to run particularly fast in practice.
slaymaker1907 9y ago
As someone who has done a lot of parallel programming, I really can't recommend Java 8 streams enough. They have a bit of overhead, however, they are incredibly easy to use and are extremely expressive.
- RodgerTheGreat 9y ago
  I've done some tinkering with streams, and I was initially very excited. They do come with some frustrating limitations. Foremost in my mind: Concatenation of streams is fairly straightforward, but how do I perform a parallel join (zip?) of multiple streams? In other words, given [1,2,3] and ["A","B","C"], how do I map over [[1,"A"],[2,"B"],[3,"C"]]?
  - dahauns 9y ago
    AFAIK this isn't possible yet in a straightforward way, and it boils down to limitations of the type system (lack of tuples resp. value types in general), and the (understandable) refusal of many to do it in way that's hacky and potentially slow. The discussion about this is actually quite old, for example: http://mail.openjdk.java.net/pipermail/lambda-libs-spec-observers/2013-June/002046.html http://mail.openjdk.java.net/pipermail/lambda-libs-spec-obse... IIRC that's a problem on bytecode level, that's why a (clean) solution still hasn't come up yet.
- nmg 9y ago
  In the talk "Clojure Concurrency" [1], Rich Hickey demands that everyone in the room read "Java Concurrency in Practice" [2]. "It will scare the crap out of you." [1] https://youtu.be/dGVqrGmwOAw?t=23m57s https://youtu.be/dGVqrGmwOAw?t=23m57s [2] https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601/ https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz...
  - muxator 9y ago
    What do that comment mean?
  - peheje 9y ago
Twirrim 9y ago
Now if only I used NESL for anything.
glangdale 9y ago
Back in around 2006 I was doing GPGPU regex and string matching and decided to google around for parallel string matching algorithms. I spent a good chunk of time scrolling around in the Vishkin's algorithm implementation and wondering why it all felt so familiar; it was only when I scrolled back to the top of the file that I realized it was familiar because I wrote it. A fine example of why you should comment your code, as the person who reads it in 10 years from now will be a stranger, even if that person is you.
- microcolonel 9y ago
  > A fine example of why you should comment your code, as the person who reads it in 10 years from now will be a stranger, even if that person is you. For what it's worth, there is at least a comment with your name in it. Maybe I'm a narcissist, but those tend to jump out at me. ;- )

212 points by federicoponzi 9y ago

Animations link appears to be broken. After doing some way back machine snooping, looks like it hasn't been up since about 2000[0]. You can access the legacy java applet animations here[1] [0] https://web.archive.org/web/20000611153404/http://web.scandal.cs.cmu.edu/cgi-bin/demo https://web.archive.org/web/20000611153404/http://web.scanda... [1] http://www.cs.cmu.edu/~scandal/applets/ http://www.cs.cmu.edu/~scandal/applets/

visox 9y ago
Thx, the images seem to be broken/nomore

hackermailman 9y ago

There is also the CMU free draft book on Parallel algorithms design http://www.parallel-algorithms-book.com/ http://www.parallel-algorithms-book.com/

Athas 9y ago
This is great! I'm really inspired by the work CMU does on parallelism. They have a parallel programming course[0] that results in some really impressive final projects [1]. I also hear that CMU takes a "parallel-first" approach to teaching algorithms and data structures, but I have not been able to find out exactly how they do that. [0]: http://15418.courses.cs.cmu.edu/fall2017/ http://15418.courses.cs.cmu.edu/fall2017/ [1]: http://15418.courses.cs.cmu.edu/fall2016/article/13 http://15418.courses.cs.cmu.edu/fall2016/article/13
- gshrikant 9y ago
  There's also 15-210 Parallel and Sequential Data Structures and Algorithms [1] which is what book GP referred to is developed for. [1] https://www.cs.cmu.edu/~15210/ https://www.cs.cmu.edu/~15210/

Athas 9y ago

These algorithms are written in NESL, which is perhaps the cleanest example of the oft-mentioned theory that parallel programming becomes simple in a functional setting. It really is remarkable how flexible it is. Unfortunately, I'm not sure NESL ever managed to run particularly fast in practice.

slaymaker1907 9y ago

As someone who has done a lot of parallel programming, I really can't recommend Java 8 streams enough. They have a bit of overhead, however, they are incredibly easy to use and are extremely expressive.

RodgerTheGreat 9y ago
I've done some tinkering with streams, and I was initially very excited. They do come with some frustrating limitations. Foremost in my mind: Concatenation of streams is fairly straightforward, but how do I perform a parallel join (zip?) of multiple streams? In other words, given [1,2,3] and ["A","B","C"], how do I map over [[1,"A"],[2,"B"],[3,"C"]]?
- dahauns 9y ago
  AFAIK this isn't possible yet in a straightforward way, and it boils down to limitations of the type system (lack of tuples resp. value types in general), and the (understandable) refusal of many to do it in way that's hacky and potentially slow. The discussion about this is actually quite old, for example: http://mail.openjdk.java.net/pipermail/lambda-libs-spec-observers/2013-June/002046.html http://mail.openjdk.java.net/pipermail/lambda-libs-spec-obse... IIRC that's a problem on bytecode level, that's why a (clean) solution still hasn't come up yet.
nmg 9y ago
In the talk "Clojure Concurrency" [1], Rich Hickey demands that everyone in the room read "Java Concurrency in Practice" [2]. "It will scare the crap out of you." [1] https://youtu.be/dGVqrGmwOAw?t=23m57s https://youtu.be/dGVqrGmwOAw?t=23m57s [2] https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz/dp/0321349601/ https://www.amazon.com/Java-Concurrency-Practice-Brian-Goetz...
- muxator 9y ago
  What do that comment mean?
- peheje 9y ago

Twirrim 9y ago

Now if only I used NESL for anything.

glangdale 9y ago

Back in around 2006 I was doing GPGPU regex and string matching and decided to google around for parallel string matching algorithms. I spent a good chunk of time scrolling around in the Vishkin's algorithm implementation and wondering why it all felt so familiar; it was only when I scrolled back to the top of the file that I realized it was familiar because I wrote it. A fine example of why you should comment your code, as the person who reads it in 10 years from now will be a stranger, even if that person is you.

microcolonel 9y ago
> A fine example of why you should comment your code, as the person who reads it in 10 years from now will be a stranger, even if that person is you. For what it's worth, there is at least a comment with your name in it. Maybe I'm a narcissist, but those tend to jump out at me. ;- )