I've seen part of that one before. Never made it to the end. This time I did and I very strongly agree with his conclusion and analysis. Breaking things down to a few or singular guiding principle is extremely helpful. Honestly, I think the generalized approach inherent in that talk is widely applicable in many contexts. Recommended.
So, yep, parallel processing is only "smarter" because we have more memory and more processing power.
Actually, no. At least I don't think so. If we choose "minimum necessary and sufficient", like when we try to mimic nature, etc, we can make the system as a whole "appear" smarter, because it does more with fewer resources and overhead. Just a few very simple processes, chosen correctly, are often much more powerful. And doing them in parallel magnifies the effect.
In some applications the increased network bandwidth that comes along with parallel helps, Google search for example. But parallel is not in any purely logically way different than having a single CPU.
You can think of it that way, and in that case its true. But they say there is a "nack" to parallel, where "if you get it" the results are very different indeed. Most folks simply are not experienced and/or not trained to think this "other" way.
Rather than "this, then that", (internal sequential); we have to think "these internal events are controlled by external triggers, and must NOT be influenced by internal sequence".
What I was trying to say is, that from a purely logical point of view, ignoring execution time, size, power consumption and other physical constraints, there is no parallel algorithm that cannot be executed by a single processor sequentially.
The proof that pudding is that massively parallel hardware described in verilog of VHDL can be simulated on a single CPU machine.
In that way parallel is not "smarter" than sequential.
Still, I look forward to being proved wrong. Somewhere there might be a parallel algorithm that cannot be expressed sequentially.
Now, you might have noticed that recently mainstream processors, as used in your PC, have been sprouting cores. What is that about?
For a long time the trend was to shrink the transistors (Thanks to Moore's Law), which allows you to wind up the clock frequency (Thanks to reduced size). And as we have so many transistors available we can add internal parallelism to the single CPU. Pipeline the instructions, issue multiple integer and floating ops at the same time and so on.
That meant the programmers could happily continue to write sequential code. In fact parallel processors and the overheads of parallelizing programs could not keep up with advances in single CPU speed. Hence the failure of the Transputer, the Connection Machine and a host of other parallel efforts over the years.
Turns out that recently winding up the clock frequency pushes your power consumption into impossible realms. And they seem to have run out of CPU design tricks to add more parallelism internally.
There is a simple formula expressing chip power consumption, that I cannot exactly recall just now but it indicates power consumption is proportional to V**2 * f. Where V is the supply voltage and f is the operating frequency. Turns out that you have to increase V to get more f and as a result power consumption in proportional to f ** 3. It is now becoming impossible to wind up the frequency, the cooling requirements are impossible. The chip would immediately melt when you turned it on!
Solution is to keep clock frequency the same and use you extra transistors to build more cores. That is to say if you want more performance now you need to add cores you cannot wind up f or increase the internal parallelism of a CPU anymore.
So yes, today if you want smarter (as in faster) you need parallel.
As for the idea that programmers cannot handle parallel programming. That is a tough one. Prof. David May is fond of saying that Electrical Engineering graduates make better programmers when it comes to parallel systems than the Computer Science graduates. The EE guys are used to thinking of circuits where many things are happening at the same time.
On the other hand there are algorithms that really don't parallelize well, if the result of every iteration depends on the one before having a parallel machine does not help. Or if the cost of communicating between parts is too high you are not winning by going parallel. That's why the world record for calculating the digits of PI has not been held by a parallel super computer since 2009.
Which leads to the depressing conclusion that for a whole class of problems we are at/near the limit. We cannot wind up the clock frequencies anymore and parallelizing only slows you down.
...As for the idea that programmers cannot handle parallel programming. That is a tough one. Prof. David May is fond of saying that Electrical Engineering graduates make better programmers when it comes to parallel systems than the Computer Science graduates. The EE guys are used to thinking of circuits where many things are happening at the same time.
Yes, it was something like that. Makes me wish I had studied electronics instead of software.
.. there are algorithms that really don't parallelize well, if the result of every iteration depends on the one before...
But that's not the general case, and even these can be paralleized in some way...
Which leads to the depressing conclusion that for a whole class of problems we are at/near the limit. We cannot wind up the clock frequencies anymore and parallelizing only slows you down.
I still have to disagree with this. For example, running a robot on a prop versus a PC. I saw a guy with an expensive laptop built right into his bot for its brain. It was clunky. If the wheels were turning, it interfered with communication and sensors, and if the communication and sensor were working, the wheels weren't turning right. Using a prop, even I with my rudimentary skills can have a bot were the wheels can turn smoothingly with ramping, and the bot can run pretty much perfectly straight, etc, and the communications can run full speed, and it can sample the distance 10,000 times in under two seconds, and no subsystem interfers with another. AND I have resources to spare, from which I intend to hang additional parallel subsystems for vision, navigation, etc.
By becoming parallel, each subsystem can be MUCH simpler, and the overall effect is that it appears much smarter, for significantly lower cost with better preformance. BUT we have to know how to set it up such that we don't step on our own feet. This last part is the small difference, and (seems to me to be) the only new learning required.
But that's not the general case, and even these can be paralleized in some way...
I would instead argue that it is indeed the general case, and that's exactly why it's so hard to get increased performance out of massively parallel systems. For our 8-cog propellers it's different because we don't usually use them to execute 'algorithms' as such, we simply let the cogs do different things (serial here, vga there, and so on). Recently at work I had to argue that we should buy a 3.3 GHz system instead of a 2.4 GHz system with lots of CPUs - the problem we were solving couldn't efficiently be solved by just throwing cores at it. Incidentally one step of the processing was to implement a feedback loop originally designed to be done in hardware.
@Braino, you were not disagreeing. Your example of putting sensor drivers and other functions into separate COGs of a Prop is a classic case of a very easily parallelizable application.
I have also had a chuckle occationally at those robots with stonking great laptops on board. I've never actually seen one in the flesh, as it were, so I don't know how well they worked but they allways looked ubsurd to me.
For anyone interested in the current situation with microprocessors, the clock frequency brick wall we have hit, the ever increasing core count and the need for (and problems with) parallel applications to make use of the performance gains we can only get with multi-core, here is a nice lecture about it all from Berkeley in 2008.
All of which is available on the $99 Parallela board http://www.parallella.org/ You perhaps don't even need the Adapteva multi-core floating point chip that is on there.
Comments
Actually, no. At least I don't think so. If we choose "minimum necessary and sufficient", like when we try to mimic nature, etc, we can make the system as a whole "appear" smarter, because it does more with fewer resources and overhead. Just a few very simple processes, chosen correctly, are often much more powerful. And doing them in parallel magnifies the effect.
You can think of it that way, and in that case its true. But they say there is a "nack" to parallel, where "if you get it" the results are very different indeed. Most folks simply are not experienced and/or not trained to think this "other" way.
Rather than "this, then that", (internal sequential); we have to think "these internal events are controlled by external triggers, and must NOT be influenced by internal sequence".
I don't disagree with you except:
What I was trying to say is, that from a purely logical point of view, ignoring execution time, size, power consumption and other physical constraints, there is no parallel algorithm that cannot be executed by a single processor sequentially.
The proof that pudding is that massively parallel hardware described in verilog of VHDL can be simulated on a single CPU machine.
In that way parallel is not "smarter" than sequential.
Still, I look forward to being proved wrong. Somewhere there might be a parallel algorithm that cannot be expressed sequentially.
Now, you might have noticed that recently mainstream processors, as used in your PC, have been sprouting cores. What is that about?
For a long time the trend was to shrink the transistors (Thanks to Moore's Law), which allows you to wind up the clock frequency (Thanks to reduced size). And as we have so many transistors available we can add internal parallelism to the single CPU. Pipeline the instructions, issue multiple integer and floating ops at the same time and so on.
That meant the programmers could happily continue to write sequential code. In fact parallel processors and the overheads of parallelizing programs could not keep up with advances in single CPU speed. Hence the failure of the Transputer, the Connection Machine and a host of other parallel efforts over the years.
Turns out that recently winding up the clock frequency pushes your power consumption into impossible realms. And they seem to have run out of CPU design tricks to add more parallelism internally.
There is a simple formula expressing chip power consumption, that I cannot exactly recall just now but it indicates power consumption is proportional to V**2 * f. Where V is the supply voltage and f is the operating frequency. Turns out that you have to increase V to get more f and as a result power consumption in proportional to f ** 3. It is now becoming impossible to wind up the frequency, the cooling requirements are impossible. The chip would immediately melt when you turned it on!
Solution is to keep clock frequency the same and use you extra transistors to build more cores. That is to say if you want more performance now you need to add cores you cannot wind up f or increase the internal parallelism of a CPU anymore.
So yes, today if you want smarter (as in faster) you need parallel.
As for the idea that programmers cannot handle parallel programming. That is a tough one. Prof. David May is fond of saying that Electrical Engineering graduates make better programmers when it comes to parallel systems than the Computer Science graduates. The EE guys are used to thinking of circuits where many things are happening at the same time.
On the other hand there are algorithms that really don't parallelize well, if the result of every iteration depends on the one before having a parallel machine does not help. Or if the cost of communicating between parts is too high you are not winning by going parallel. That's why the world record for calculating the digits of PI has not been held by a parallel super computer since 2009.
Which leads to the depressing conclusion that for a whole class of problems we are at/near the limit. We cannot wind up the clock frequencies anymore and parallelizing only slows you down.
Man, that was longer than I intended.
Yes, it was something like that. Makes me wish I had studied electronics instead of software.
But that's not the general case, and even these can be paralleized in some way...
I still have to disagree with this. For example, running a robot on a prop versus a PC. I saw a guy with an expensive laptop built right into his bot for its brain. It was clunky. If the wheels were turning, it interfered with communication and sensors, and if the communication and sensor were working, the wheels weren't turning right. Using a prop, even I with my rudimentary skills can have a bot were the wheels can turn smoothingly with ramping, and the bot can run pretty much perfectly straight, etc, and the communications can run full speed, and it can sample the distance 10,000 times in under two seconds, and no subsystem interfers with another. AND I have resources to spare, from which I intend to hang additional parallel subsystems for vision, navigation, etc.
By becoming parallel, each subsystem can be MUCH simpler, and the overall effect is that it appears much smarter, for significantly lower cost with better preformance. BUT we have to know how to set it up such that we don't step on our own feet. This last part is the small difference, and (seems to me to be) the only new learning required.
I have also had a chuckle occationally at those robots with stonking great laptops on board. I've never actually seen one in the flesh, as it were, so I don't know how well they worked but they allways looked ubsurd to me.
For anyone interested in the current situation with microprocessors, the clock frequency brick wall we have hit, the ever increasing core count and the need for (and problems with) parallel applications to make use of the performance gains we can only get with multi-core, here is a nice lecture about it all from Berkeley in 2008.
http://www.youtube.com/watch?v=n-WX9DNq65E
@Tor, sounds like you application could make use of an FPGA tightly coupled to your processors. I wonder how well it would perform on a Xilinx Zync http://eda360insider.wordpress.com/2011/03/01/xilinx-zynq-epps-create-a-new-category-that-fits-in-among-socs-fpgas-and-microcontrollers/
All of which is available on the $99 Parallela board http://www.parallella.org/ You perhaps don't even need the Adapteva multi-core floating point chip that is on there.