Are there any existing algorithms which examine the operations that
must be conducted and then create an optimized / minimal sequence of mechanical steps to conduct it given a constrained set of features
(such as those present on a given CPU)?
Are there any algorithms which take a known-at-compile-time sequence
of bitwise operations on an 8-bit to 64-bit quantity, and optimize
them down to their minimal set of operations?
Input: 07 06 05 04 03 02 01 00
Output: 05 04 07 02 01 03 00 06
Are there any existing algorithms which examine the operations that
must be conducted and then create an optimized / minimal sequence of mechanical steps to conduct it given a constrained set of features
(such as those present on a given CPU)?
On 05/09/2020 17:05, Rick C. Hodgin wrote:1987 paper "Superoptimizer: A Look at the Smallest Program":
Are there any existing algorithms which examine the operations that
must be conducted and then create an optimized / minimal sequence of
mechanical steps to conduct it given a constrained set of features
(such as those present on a given CPU)?
The process you are describing is called "Superoptimization":
finding the optimal code sequence for one loop-free sequence
of instructions.
https://en.wikipedia.org/wiki/Superoptimization
The term superoptimization was first coined by Alexia Massalin in the
http://www.stanford.edu/class/cs343/resources/superoptimizer.pdf
Back in 1980 there was a discussion in the magazine
"Pratical Electronics" regarding the shortest sequence of
instructions needed to reverse the bits in the accumulator
for a 6800 system (an operation that is needed in some Fast Fourier Transform algorithms).
One solution (given in June 1980, page 70) consisted of just
two instructions and used no additional data.
The instructions were:
STAA PORTA write to output port
LDAB PORTB read from input port
with the output port being wired directly to the input port with
the bits reversed!
One such idea is writing to a port, and reading back from another port,
where the external thing does the processing for you as a co-processor or custom ASIC.
On 05/09/2020 17:05, Rick C. Hodgin wrote:
Are there any existing algorithms which examine the operations that
must be conducted and then create an optimized / minimal sequence of mechanical steps to conduct it given a constrained set of features
(such as those present on a given CPU)?
The process you are describing is called "Superoptimization":
finding the optimal code sequence for one loop-free sequence
of instructions. ...
Are there any algorithms which take a known-at-compile-time sequence
of bitwise operations on an 8-bit to 64-bit quantity, and optimize
them down to their minimal set of operations?
For example, if I have an 8-bit byte and I want to swizzle the bits
thusly:
Input: 07 06 05 04 03 02 01 00
Output: 05 04 07 02 01 03 00 06
On Saturday, September 5, 2020 at 9:45:43 AM UTC-7, Rick C. Hodgin wrote:
Are there any algorithms which take a known-at-compile-time sequence
of bitwise operations on an 8-bit to 64-bit quantity, and optimize
them down to their minimal set of operations? ...
There is a lot of work, and many algorithms, for logic optimization,
or minimization, that, for example, will find the optimal combination
of NAND and NOR gates to evaluate some logical operation. ...
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 292 |
Nodes: | 16 (2 / 14) |
Uptime: | 190:46:50 |
Calls: | 6,616 |
Files: | 12,165 |
Messages: | 5,315,134 |