4 ms·

I am craving one of these for my superoptimizer. The level of task parallelism I have is north of 100M independent jobs; my last run took a single-core machine

I am craving one of these for my superoptimizer. The level of task parallelism I have is north of 100M independent jobs; my last run took a single-core machine 20 days. It's pretty rare to have a workload like this but as more machines ship with >16 cores, I think more developers will look at the order-of-magnitude improvements of parallelizing their tasks where possible.

qubex 7y ago
Of course, not everything can be parallelised.
namibj 7y ago
In what context are you working with Superoptimizers, if you don't mind me asking?
Straw 7y ago
Can you tell us more about this superoptimizer?
- glangdale 7y ago
  It's an SMT-based solver to make fast "single-lane" SIMD calculations for AVX2 (doing different things in multiple lanes, doing AVX512 or SSE or ARM or general purpose registers, etc. are all on my todo list). Branch free code only. Can handle up to 4 or 5 instruction sequences including things like generating constants like 128-bit tables for PSHUFB (considering PSHUFB as a single-lane operation where every lane looks up a table).
  - Straw 7y ago
    Sounds very cool! I recently wondered about the possibility of superoptimizing vectorized code, so glad to hear about it! Would you like to chat about opportunities to do analagous work for GPU instruction sets? I work at a startup making high-performing GPU software and compilers, incidentally including a regex engine! (We can't quite match HyperScan on the CPU, but support capture groups and very high throughput on GPUs.) We also have several other interesting projects, and would like to start a superoptimizer at some point. P.S. After reading your blog, one of our engineers said: "We see you like PSHUFB. So do we."
yvdriess 7y ago
Why are you sticking to desktop processors with that kind of workloads?
- glangdale 7y ago
  Because this is a hobby project and I was doing it at home? eventually I will be doing this in the cloud or with a home-based server or both, but you have to start somewhere. Much of the work is currently centered around "being less stupid" rather than "try to parallelize more" as wasting tons of time doing pointless solves is not a good idea - I've already got about 80-100x speed improvements from optimizations (not looking at sequences I can prove won't work, not looking at sequences that I can prove "do the same thing as some other sequence").
0-_-0 7y ago
Could you run it on the GPU then? Or does it have a lot of branches?
- glangdale 7y ago
  It uses an SMT solver (can use Z3, Yices or Boolector) all of which are very complex and branchy. So no GPGPU - maybe some specialist in SAT solving or SMT could build that one day, but that person would not be me.
voldacar 7y ago
What are you superoptimizing?

qubex 7y ago

Of course, not everything can be parallelised.

namibj 7y ago

In what context are you working with Superoptimizers, if you don't mind me asking?

Straw 7y ago

Can you tell us more about this superoptimizer?

glangdale 7y ago
It's an SMT-based solver to make fast "single-lane" SIMD calculations for AVX2 (doing different things in multiple lanes, doing AVX512 or SSE or ARM or general purpose registers, etc. are all on my todo list). Branch free code only. Can handle up to 4 or 5 instruction sequences including things like generating constants like 128-bit tables for PSHUFB (considering PSHUFB as a single-lane operation where every lane looks up a table).
- Straw 7y ago
  Sounds very cool! I recently wondered about the possibility of superoptimizing vectorized code, so glad to hear about it! Would you like to chat about opportunities to do analagous work for GPU instruction sets? I work at a startup making high-performing GPU software and compilers, incidentally including a regex engine! (We can't quite match HyperScan on the CPU, but support capture groups and very high throughput on GPUs.) We also have several other interesting projects, and would like to start a superoptimizer at some point. P.S. After reading your blog, one of our engineers said: "We see you like PSHUFB. So do we."

yvdriess 7y ago

Why are you sticking to desktop processors with that kind of workloads?

glangdale 7y ago
Because this is a hobby project and I was doing it at home? eventually I will be doing this in the cloud or with a home-based server or both, but you have to start somewhere. Much of the work is currently centered around "being less stupid" rather than "try to parallelize more" as wasting tons of time doing pointless solves is not a good idea - I've already got about 80-100x speed improvements from optimizations (not looking at sequences I can prove won't work, not looking at sequences that I can prove "do the same thing as some other sequence").

0-_-0 7y ago

Could you run it on the GPU then? Or does it have a lot of branches?

glangdale 7y ago
It uses an SMT solver (can use Z3, Yices or Boolector) all of which are very complex and branchy. So no GPGPU - maybe some specialist in SAT solving or SMT could build that one day, but that person would not be me.

voldacar 7y ago

What are you superoptimizing?