Program optimization
 

I while back I came across [url]http://critticall.com/[/url]
This program optimizes code by making random changes, checking whether they work and their speed.
Would this sort of approach work with optimizing assembler? Currently a compiler outputs a particular version for each type of cpu but there are potentially more optimizations that can be done for a particular system. Experimentation would surely give better results.

[QUOTE=henryzz;311738]I while back I came across [url]http://critticall.com/[/url]
This program optimizes code by making random changes, checking whether they work and their speed.
Would this sort of approach work with optimizing assembler? Currently a compiler outputs a particular version for each type of cpu but there are potentially more optimizations that can be done for a particular system. Experimentation would surely give better results.[/QUOTE]

[url]http://critticall.com/mersenne.html[/url]

It would have been funny, if it wasn't so sad to watch...

Here's how Critticall would solve the following problem.

One of the lights in the bathroom just went out.
Solve it.
<...a few hours later...>
All walls are drilled in random places, the toilet is taken off and broken to pieces, all the fuses are blown by shorts, the water pipes were disconnected (but not shut)... you get the idea. The light is still off. :smile:
_______________

(Genetic algorithms were around for more than a decade. I do agree that there are some problems for them. I've [COLOR=black][FONT=Verdana]exaggerated[/FONT][/COLOR] a little bit with this example.)

The basic problem is that the random genetic evolution algorithm needs 4 billion years to work properly.

[QUOTE=Batalov;311743]Here's how Critticall would solve the following problem.

One of the lights in the bathroom just went out.
Solve it.
<...a few hours later...>
All walls are drilled in random places, the toilet is taken off and broken to pieces, all the fuses are blown by shorts, the water pipes were disconnected (but not shut)... you get the idea. The light is still off. :smile:
_______________

(Genetic algorithms were around for more than a decade. I do agree that there are some problems for them. I've [COLOR=black][FONT=Verdana]exaggerated[/FONT][/COLOR] a little bit with this example.)[/QUOTE]

That's not the real problem here, though. The problem is the fitness function: it's very hard to test if a program correctly tests primality. So instead it pokes a hole in the wall and waits a billion years seeing if that made the lights go on.

[QUOTE=henryzz;311738]I while back I came across [url]http://critticall.com/[/url]
This program optimizes code by making random changes, checking whether they work and their speed.
Would this sort of approach work with optimizing assembler? Currently a compiler outputs a particular version for each type of cpu but there are potentially more optimizations that can be done for a particular system. Experimentation would surely give better results.[/QUOTE]

The x64 assembler code in MPIR is produced using a method that is not random but is based on a related idea (developed by another MPIR contributor).

The code is first designed and it is then analysed and annotated with information that specifies how far each individual instruction can be moved relative to the others around it without changing the final answer (using knowledge of the target micro-architecture). The code is then run in a simulator that tests the different instruction orders to find the order that gives the highest speed.

The problem I foresee here is:[QUOTE=Brian Gladman;312409]The code is then run in a simulator that tests the different instruction orders to find the order that gives the highest speed.[/QUOTE]... under what conditions?

The modern CPUs are very complex things. There are both internal and external states and conditions that occur under real application usage that a simulator cannot hope to duplicate, or even model closely.

Also with the sheer number of movable instruction in any non-trivial program I suspect that finding the optimal order is a rather hard problem. Is there a travelling salesman in the house?

[QUOTE=retina;312411]The problem I foresee here is:... under what conditions?

The modern CPUs are very complex things. There are both internal and external states and conditions that occur under real application usage that a simulator cannot hope to duplicate, or even model closely.

Also with the sheer number of movable instruction in any non-trivial program I suspect that finding the optimal order is a rather hard problem. Is there a travelling salesman in the house?[/QUOTE]

Most of the time a relatively short piece of assembler code is running, it is possible to predict with reasonable accuracy how the micro-architecture will behave. Moreover, the low level code that implements many of the primitives on which multiple precision arithmetic depends is actually quite simple so the complexity is well contained.

[QUOTE=Batalov;311743]Here's how Critticall would solve the following problem.

One of the lights in the bathroom just went out.
Solve it.
<...a few hours later...>
All walls are drilled in random places, the toilet is taken off and broken to pieces, all the fuses are blown by shorts, the water pipes were disconnected (but not shut)... you get the idea. The light is still off.[/QUOTE]The main difference from your example is that computer code can be easily restored to the original condition if it becomes obvious that things are going haywire.[QUOTE=cheesehead;311747]The basic problem is that the random genetic evolution algorithm needs 4 billion years to work properly.[/QUOTE]Are you sure 4Gy is enough, we've yet to see the outcome "work properly". :razz: But we had better hurry up since we've only got about another 800My-1Gy left to get things right.[QUOTE=Brian Gladman;312414]Most of the time a relatively short piece of assembler code is running, it is possible to predict with reasonable accuracy how the micro-architecture will behave. Moreover, the low level code that implements many of the primitives on which multiple precision arithmetic depends is actually quite simple so the complexity is well contained.[/QUOTE]There are many different micro-architectures around; they all respond differently to the input code. Plus not just the micro-architecture is at play here: there is also the various myriad of buffers, caches, cores, SMT, temperature sensors, pipelines, etc. that tend to mess up any predictions depending upon what was executed immediately in the past or might be executed shortly in the future.

[QUOTE=retina;312417]There are many different micro-architectures around; they all respond differently to the input code. Plus not just the micro-architecture is at play here: there is also the various myriad of buffers, caches, cores, SMT, temperature sensors, pipelines, etc. that tend to mess up any predictions depending upon what was executed immediately in the past or might be executed shortly in the future.[/QUOTE]

Much of the MPIR assembler code is optimised on an architecture specific basis with the various quirks taken into account. The impact of cache effects can be reasonably accounted for and we have included techniques to account for the run-in and run-out effects you mention (many of which are weird and not well documented but can be seen in the results and hence built into the simulator).

Nobody pretends that any of this is perfect - it doesn't have to be. The overall speed improvements are both measurable and significant.