Magical platinum bullet #3
Aug. 6th, 2008 10:21 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
izardI've recently had 2 posts about a crazy idea about parallelizing single core x86 emulator to manycores, thinking if it can make any speed it up at all.
It's an excellent problem with many limiting factors, each at different level of abstraction, leading to different conclusions.
In the end we had decided that the overhead from finding instruction level parallelism and communicating it to the cores will overweight the parallelization benefits, given the sequential order of the program flow.
Yesterday I've suddenly found a paper by Czechoslovak researchers, published in 1984, that quantifies this effect! This paper hardly has any external references, so it's a miracle I've found it and a shame it's results were never used.
Authors had developed an algorithm that generates a Parallel Turing Machine that is equivalent to a given Turing Machine, provides polynomial speedup and runs in the same tape footprint. The speedup depends on the input Turing Machine. Algorithm is a smart one, similar to one I've been thinking about when considering en emulator, but it works :). In a nutshell, the idea is that there is a unlimited pool of the processors, each has the same r/o program(states description), working in parallel on the same tape, eagerly seeking for parallelism :) I wonder if this algorithm scales to limited pool of processors, simple RISC or JVM to begin with, and eventually to x86.
I'll probably try to implement it in Clojure just to have something cool to play with. Unfortunately, I'll have to fully understand the math behind, and dig old textbooks to refresh few concepts first.
Update: After reading the paper 2 more times I've found out that the researchers had only proved that the universal parallel Turing machine exists and is able to run universal serial Turing machine with polynomial speed up. The proof looks like a cheat, but it is probably correct: The author proves that The Universal Parallel Machine could be ran on Universal Serial machine with polynomial slow down, and concludes that the opposite is true.
No algorithm to create one was proposed (One I've described was not an algorithm but rather a vaguely described approach how to generate a simple (non-universal) parallel machine given simple serial machine)
It's an excellent problem with many limiting factors, each at different level of abstraction, leading to different conclusions.
In the end we had decided that the overhead from finding instruction level parallelism and communicating it to the cores will overweight the parallelization benefits, given the sequential order of the program flow.
Yesterday I've suddenly found a paper by Czechoslovak researchers, published in 1984, that quantifies this effect! This paper hardly has any external references, so it's a miracle I've found it and a shame it's results were never used.
Authors had developed an algorithm that generates a Parallel Turing Machine that is equivalent to a given Turing Machine, provides polynomial speedup and runs in the same tape footprint. The speedup depends on the input Turing Machine. Algorithm is a smart one, similar to one I've been thinking about when considering en emulator, but it works :). In a nutshell, the idea is that there is a unlimited pool of the processors, each has the same r/o program(states description), working in parallel on the same tape, eagerly seeking for parallelism :) I wonder if this algorithm scales to limited pool of processors, simple RISC or JVM to begin with, and eventually to x86.
I'll probably try to implement it in Clojure just to have something cool to play with. Unfortunately, I'll have to fully understand the math behind, and dig old textbooks to refresh few concepts first.
Update: After reading the paper 2 more times I've found out that the researchers had only proved that the universal parallel Turing machine exists and is able to run universal serial Turing machine with polynomial speed up. The proof looks like a cheat, but it is probably correct: The author proves that The Universal Parallel Machine could be ran on Universal Serial machine with polynomial slow down, and concludes that the opposite is true.
No algorithm to create one was proposed (One I've described was not an algorithm but rather a vaguely described approach how to generate a simple (non-universal) parallel machine given simple serial machine)
