3 ms·

The GMP (GNU Multi Precision library) guys found that the hand written assembly sequences (which were already 2-6x faster than that produced by a decent C compi

by wbhart 12y ago

The GMP (GNU Multi Precision library) guys found that the hand written assembly sequences (which were already 2-6x faster than that produced by a decent C compiler) could be sped up another factor of 2x by superoptimisation, at least of out-of-order CPUs. Superoptimisation isn't only feasibly, it is actually quite practical. A factor of 2x across an already highly optimised library can cut your supercomputing budget in a grant by half. Whether you need 1 or 2 million CPU hours can make or break entire projects These days, however, one can often do better with SIMD instructions. These often don't superoptimise well because the individual atomic operations they perform aren't able to be rearranged by the programmer. However, lots of existing supercomputers available for research still don't have chipset revisions with decent SIMD support.

gopalv 12y ago
The SIMD auto-vectorization is an off-shoot of this research. But what excites me about super-optimization is to make functional optimization repeatable. Let me give you an example of why I'd use it for more than HPC libs. Assume you have a firewall system, which needs to determine whether a tuple of (srcip, dstip, dstport) is a safe one or not. All 3 variables fit inside registers (assume xmm). A rules engine as written traditionally would be a hashtable of some sort, always regenerated with a gperf hash (already we're in super-optimal territory partially). But what if going to RAM is 300x more expensive than a SIMD sequence over 3 registers run a few hundred times? Then writing a functional chunk of code which produces the same outputs for the same inputs, but without any storage system would be a killer feature. That is sort of the problem where a super-optimizer can take a huge amount of data and turn it into bit-twiddling checks which find hidden invariants in each data-set. Being able to take a bunch of rules which say subnet to subnet or port access patterns and compile it into a storage -less ACL mechanism (like bit 11 on port is 1, then DENY). I'm almost certain these problems were solved in the past using a super-optimized FPGA as well (well, I would if I had the budget). For me, being able to churn a dumb SWITCH loop through these systems is more interesting than chucking well written code into this.
- DanWaterworth 12y ago
  I don't think this will be as successful as you might hope. Consider how many possible sets of rules there are. Call that n. The instruction sequence will need to encode log2 n bits of data, but you have no ability to tune the representation to say which inputs are likely. Instructions aren't free, they still need to be loaded from RAM like data.
darkmighty 12y ago
I wonder if it would be efficient to use part of those millions of CPU hours to optimize the programs themselves before running them?

by wbhart 12y ago

gopalv 12y ago

The SIMD auto-vectorization is an off-shoot of this research. But what excites me about super-optimization is to make functional optimization repeatable. Let me give you an example of why I'd use it for more than HPC libs. Assume you have a firewall system, which needs to determine whether a tuple of (srcip, dstip, dstport) is a safe one or not. All 3 variables fit inside registers (assume xmm). A rules engine as written traditionally would be a hashtable of some sort, always regenerated with a gperf hash (already we're in super-optimal territory partially). But what if going to RAM is 300x more expensive than a SIMD sequence over 3 registers run a few hundred times? Then writing a functional chunk of code which produces the same outputs for the same inputs, but without any storage system would be a killer feature. That is sort of the problem where a super-optimizer can take a huge amount of data and turn it into bit-twiddling checks which find hidden invariants in each data-set. Being able to take a bunch of rules which say subnet to subnet or port access patterns and compile it into a storage -less ACL mechanism (like bit 11 on port is 1, then DENY). I'm almost certain these problems were solved in the past using a super-optimized FPGA as well (well, I would if I had the budget). For me, being able to churn a dumb SWITCH loop through these systems is more interesting than chucking well written code into this.

DanWaterworth 12y ago
I don't think this will be as successful as you might hope. Consider how many possible sets of rules there are. Call that n. The instruction sequence will need to encode log2 n bits of data, but you have no ability to tune the representation to say which inputs are likely. Instructions aren't free, they still need to be loaded from RAM like data.

darkmighty 12y ago

I wonder if it would be efficient to use part of those millions of CPU hours to optimize the programs themselves before running them?