Magical platinum bullet #3

I'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)

More on FP

This post is not technical, though it looks like one first. So might be interesting for non-programmers too.

Few years ago I've realized that FP is TNBT in programming. Since that time I am observing how it is slowly progressing from "weird things they are playing with in Academia/what's FP??/We don't need it" to "Low paid developers in our sweatshop are proficient in OO/FP / Looking for junior F#/Scala developer". Yes, I suspect it will take about 3 more years until mainstream recruiters will have to learn few more buzzwords.

If I've had more practical mind set I could have ridden on this wave. Please don't mind this whining :)

Where do engineers understanding FP come from? FP had been around for ages, and was always just one of the tools of better s/w engineers. So I would suspect that it usually comes with experience. However, I've recently realized that I know more younger FP experts then there are in my generation or older ones. That was a surprise for me! I've read Kuhn back in Uni, but I did not realize it is applicable :)

Any way, as Thomas Kuhn had suggested, new way of thinking just waits till old paradigm's proponents die out until becoming a mainstream. It is not quite true with programming, old blokes do not die instantly as new paradigm arrives (which is not bad at all). They start sustaining what they've developed or work in the niches where factors other then technical sophistication are important. There are exceptions, I know few old engineers who had successfully picked up OO and now FP. I hope I'll too grasp what will be invented in 20 years from now or be a manager by then and won't care :)

Using social networks, I've found a cluster of bright and young professionals using FP working for Sun, JetBrains,and few other companies in St.Petersburg. They are using Livejournal, rsdn, JUG and SPB HUG to communicate. Lately I've added few mates as "friends" in lj account zabivator, antilamer, just to read what's up in the field.

P.S. And as a amateur Lisper, I can't help but remind Greenspun's tens rule :)
P.P.S. It appears that some of my new "friends" are ENTP (MBTI) like myself, I wonder if there an lj community for us? Kidding...