267 ms·

"the most parallel programs" are those that run on supercomputers / huge clusters, and they don't have these bottlenecks... But for the average parallel progra

"the most parallel programs" are those that run on supercomputers / huge clusters, and they don't have these bottlenecks... But for the average parallel programs, you are (currently) right, I guess.

jbooth 14y ago
You've still got a driver program that coordinates the massively parallel stages, most likely, and a less-scalable dispatch process where not all nodes are yet doing work.
- CookWithMe 14y ago
  Yes, there definitely are programs where this holds true (as I have said), but there are others where it does not. A simple, but perfectly reasonable example is brute-force search for cracking a password (if you got the hash of the password). Your dispatch is simple: send every node 1) the hash, 2) the number of nodes, 3) it's own number. With 2) and 3), each node can easily figure out where it starts. You need no more communication until one of the nodes finds the password. See https://en.wikipedia.org/wiki/Embarrassingly_parallel https://en.wikipedia.org/wiki/Embarrassingly_parallel Again, you said "most parallel", and not "average parallel", and this is what I have commented on.
marshray 14y ago
Keep in mind, https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law was posed at the very beginning of parallel computing. Seymour Cray later became famous both for his fast uniprocessor supercomputer and his quip "If you were plowing a field, which would you rather use: Two strong oxen or 1024 chickens?" For most embarrassingly parallel problems, a Hadoop or BOINC-like cluster made from commodity hardware may always be cheapest. But "real" supercomputers and clusters will spend the most money to reduce bottlenecks precisely because they want to run those programs that are the most limited by them.
- CookWithMe 14y ago
  I know, I actually read the paper like a year ago. Actually, what was turned later into Amdahl's law is more or less a side-note in the paper :) The parent said "most parallel programs", which I translated to embarrassingly parallel problems. > But "real" supercomputers and clusters will spend the most money to reduce bottlenecks precisely because they want to run those programs that are the most limited by them. I agree, but from the talks I have heard most time (= money) is spent trying to work around these bottlenecks as good as possible in software (i.e. incremental algorithms, pipelining, ...) to keep the machines busy. Then again, I hear a lot more talks about software than hardware, so you may be very right. If you have any particular example in mind, I would love to read about it!
  - marshray 14y ago
    My impression (formed from growing up as the annoying kid in the datacenter back when they let annoying kids hang out in the datacenter) is that buying new supercomputer hardware takes takes a lot of money and a really long time. Showing a return for the big investment might take much longer than the life of a typical PC. Once the a computer is actually in place (especially in a University setting), the interesting work begins, trying to write the best code for it and even improve the existing algorithms. It seems like there are computer purchases motivated by "this machine will run our existing code faster" and those motivated by "this machine will allow us to write code for it that will prove something faster". A supercomputer seems, almost by definition, the latter.

"the most parallel programs" are those that run on supercomputers / huge clusters, and they don't have these bottlenecks... But for the average parallel programs, you are (currently) right, I guess.

jbooth 14y ago

You've still got a driver program that coordinates the massively parallel stages, most likely, and a less-scalable dispatch process where not all nodes are yet doing work.

CookWithMe 14y ago
Yes, there definitely are programs where this holds true (as I have said), but there are others where it does not. A simple, but perfectly reasonable example is brute-force search for cracking a password (if you got the hash of the password). Your dispatch is simple: send every node 1) the hash, 2) the number of nodes, 3) it's own number. With 2) and 3), each node can easily figure out where it starts. You need no more communication until one of the nodes finds the password. See https://en.wikipedia.org/wiki/Embarrassingly_parallel https://en.wikipedia.org/wiki/Embarrassingly_parallel Again, you said "most parallel", and not "average parallel", and this is what I have commented on.

marshray 14y ago

Keep in mind, https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law was posed at the very beginning of parallel computing. Seymour Cray later became famous both for his fast uniprocessor supercomputer and his quip "If you were plowing a field, which would you rather use: Two strong oxen or 1024 chickens?" For most embarrassingly parallel problems, a Hadoop or BOINC-like cluster made from commodity hardware may always be cheapest. But "real" supercomputers and clusters will spend the most money to reduce bottlenecks precisely because they want to run those programs that are the most limited by them.

CookWithMe 14y ago
I know, I actually read the paper like a year ago. Actually, what was turned later into Amdahl's law is more or less a side-note in the paper :) The parent said "most parallel programs", which I translated to embarrassingly parallel problems. > But "real" supercomputers and clusters will spend the most money to reduce bottlenecks precisely because they want to run those programs that are the most limited by them. I agree, but from the talks I have heard most time (= money) is spent trying to work around these bottlenecks as good as possible in software (i.e. incremental algorithms, pipelining, ...) to keep the machines busy. Then again, I hear a lot more talks about software than hardware, so you may be very right. If you have any particular example in mind, I would love to read about it!
- marshray 14y ago
  My impression (formed from growing up as the annoying kid in the datacenter back when they let annoying kids hang out in the datacenter) is that buying new supercomputer hardware takes takes a lot of money and a really long time. Showing a return for the big investment might take much longer than the life of a typical PC. Once the a computer is actually in place (especially in a University setting), the interesting work begins, trying to write the best code for it and even improve the existing algorithms. It seems like there are computer purchases motivated by "this machine will run our existing code faster" and those motivated by "this machine will allow us to write code for it that will prove something faster". A supercomputer seems, almost by definition, the latter.