24 ms·

As a GPU programmer and someone who’s experimented with genetic algorithms, I believe you are misunderstanding the concepts involved. Genetic algorithms are in

As a GPU programmer and someone who’s experimented with genetic algorithms, I believe you are misunderstanding the concepts involved. Genetic algorithms are in fact much better suited to SIMD than MISD, as you want to run the same evaluation on a population of individuals with different attributes, and they scale perfectly well with current hardware. Take a toy example, you could fit a small neural network in a single kernel, and there you would obviously run the same inference algorithm with each neural network having different weights and biases. That won’t work for large networks, but in general there you’d want to scale by using multiple GPUs, and there genetic algorithms scale even better as you can run each machine almost entirely independently.

zackmorris 6y ago
Oh hmm, I've always approached it from the other direction, imagining a population of creatures with different genes interacting with the same environment. Like 10,000 very different shader programs (mutations of each other) running simultaneously, but sharing the same texture/environment/data. Analogous to each creature being its own process on its own CPU, ideally. But I never saw how such a setup could be run on a video card. Admittedly, I got really disheartened about this stuff a decade ago when OpenCL and CUDA came out and seemed to be made for running one program on a bunch of different data. And complicated. Do you or does anyone know if things have changed? The closest I've come to this lately is Unity shaders, but I vaguely remember there is a way to run Julia on GPU? Like if each different shader program is run as a layer in a rendering pass. Except rather than 8 or 16 layers, can modern GPUs run more on the order of 100+ layers? What's the limit?
- zackmorris 6y ago
  Stumbled onto a few crash course items that helped get me a bit up to speed on this: https://www.cl.cam.ac.uk/teaching/1819/AdvGraphIP/03_OpenCL.pdf https://www.cl.cam.ac.uk/teaching/1819/AdvGraphIP/03_OpenCL.... https://stackoverflow.com/a/27250785/539149 https://stackoverflow.com/a/27250785/539149 https://community.amd.com/t5/opencl/parallel-execution-of-kernels/td-p/318178 https://community.amd.com/t5/opencl/parallel-execution-of-ke... https://www.intel.com/content/www/us/en/programmable/documentation/mwh1391807516407.html https://www.intel.com/content/www/us/en/programmable/documen... It's kind of looking like it's not really feasible to run more than a handful of OpenCL kernels simultaneously, certainly not 10,000. Maybe I'm looking at it the wrong way? Conceptually, I want to run a C-style "Hello, World" program with a hundred random instructions after it, hardcoded into 10,000 variations. Then compile and run them simultaneously, passing them all the same data. I mean even being able to do this with 16 different kernels to start with would be awesome!
  - joefourier 6y ago
    Ah, I think you’re talking about applying genetic algorithms to self modifying code. In that case you’d want to run the self-modifying code in a VM; if you’re just putting random instructions after another, you’ll most likely just have segfaults, invalid memory addressing, and worse. With a simple VM, you could fit it in a GPU kernel (keep in mind the language limitations) and then you’ll have no issues launching your huge batch in parallel. I don’t know if genetic program generation has any useful applications however. Personally I am more interested in applying genetic algorithms to machine learning, i.e. neuroevolution. A few examples include NEAT and Uber’s reinforcement learning research.
    - zackmorris 6y ago
      Ya the method I want to try is transpiling Lisp to C and then running that on GPU (so no segfaults). As far as I can tell, the problem is that I can only run 10,000 copies of the same shader, not 10,000 different shaders at once on the same data. This is the closest I can come to a "proof" that today's hardware is on the wrong branch of the search space of possible hardwares. I'm hoping to be proven wrong though, and that someone knows a way to run say 16 or more different shaders simultaneously on a GPU. Maybe there is a way to encode the variations in sub-shaders and run those at the same time or something? Edit: a few more links about running concurrent GPU kernels: https://stackoverflow.com/a/53341888/539149 https://stackoverflow.com/a/53341888/539149 https://stackoverflow.com/a/52978372/539149 https://stackoverflow.com/a/52978372/539149 https://community.amd.com/t5/opencl/opencl-concurrent-kernel-execution/td-p/112686 https://community.amd.com/t5/opencl/opencl-concurrent-kernel... https://community.khronos.org/t/concurrents-kernels-in-opencl/7604 https://community.khronos.org/t/concurrents-kernels-in-openc... http://ecosimulation.com/chrisgregg/Publications/Fine-GrainedResourceSharing.pdf http://ecosimulation.com/chrisgregg/Publications/Fine-Graine... http://docs.potionmagic.eu/per.pdf http://docs.potionmagic.eu/per.pdf Unfortunately, concurrent kernels execution is only possible with CUDA on NVIDIA graphics cards. For other cards, OpenCL does not offer this functionality. Looks like it may only be possible on NVIDIA, according to the last link. Since this was the first thing I wanted to do with OpenCL, it doesn't bode well for the standard or AMD. As a software developer, I see this issue a lot. What happened is, their public interface is too thick so doesn't reflect the actual capabilities of the hardware. I hit this with OpenGL too way back before ES2 and shaders were mainstream. I just wanted direct access to some of the matrix hardware math but couldn't get to it. I'd vote to scrap current GPU implementations and move to a pure 2D or 3D grid of compute units (a bit like AWS EC2) running something like Docker. Then write OpenGL, OpenCL, Vulkan, Metal and the rest as niche libraries implementing use cases above the runtime. That would give us bare metal access to get real work done with languages like C, Rust, MATLAB, Julia, Erlang, Go, etc and finally drop the distinction between CPU and GPU.
- amkkma 6y ago
  Yea, Julia compiles natively to GPUs. See here: https://juliagpu.org/ https://juliagpu.org/
GregarianChild 6y ago
An interesting question is: why are we not seeing fast and scalable GPU implementations of GAs? (I'm not trying to trick you, genuinely curious). I think one problem, making GAs as they are understood today (maybe there is a better way), is the freewheeling, unconstrained nature of GA fitness functions. If the ambient fitness function has a lot of data-dependent branching, SIMD will be slow. Moreover GAs have two phases: measuring fitness and mutation/crossing over to produce the next generation. Is the mutation/crossover phase SIMD friendly? Typically, it involves randomness ... In contrast, neural net training is essentially GeMM (General Matrix Multiply) which is an incredibly predictable workload -- almost no data dependent branching. So none of the things that make processors slow and complicated (caches, prefetching, branch prediction, reservation station, scheduler ...) is needed: instead you can just stream the data from main memory directly into the matrix multiplier (tensor core). This means you can use the available transistors (and energy) much more efficiently. As far as I am aware, GAs have not, so far, been reduced to as simple uniform and predictable a workload as GeMM, which I believe is why GAs don't usually get run on a GPU (not to mention more specialised hardware like TPUs). run each machine almost entirely independently. I am not sure how this works with mutation/crossover. Learning happens by 'throwing away' unpromising search avenues (genes). So if different machines do not synchronise their populations, they don't learn from each other. Synchronisation OTOH is very slow.
- joefourier 6y ago
  Evolution strategies (essentially the same as genetic algorithms) have been successfully applied to GPU-training of neural networks and parallelise very well. Look at various papers on neuro-evolution (e.g. the ones from the now defunct Uber AI Labs). A simple, very inefficient implementation would be: do inference on n randomly initialised neural networks, calculate loss, select the m best performing and copy them to fill all n spots, add gaussian noise to each weight and bias of every individual, repeat. More efficient mutation and selection strategies exist, but the principle is similar and parallelisation on GPUs is trivial and actually easier than current approaches (atomic operations e.g. compare-and-swap can be used to avoid going back to the CPU for selection). I believe the real reason for neuro-evolution's unpopularity is that for most problems, gradient descent is just faster and more efficient. What would be interesting might be to combine both approaches, using evolution strategies on hyperparameter search, although I haven't read the literature on that front.

zackmorris 6y ago

Oh hmm, I've always approached it from the other direction, imagining a population of creatures with different genes interacting with the same environment. Like 10,000 very different shader programs (mutations of each other) running simultaneously, but sharing the same texture/environment/data. Analogous to each creature being its own process on its own CPU, ideally. But I never saw how such a setup could be run on a video card. Admittedly, I got really disheartened about this stuff a decade ago when OpenCL and CUDA came out and seemed to be made for running one program on a bunch of different data. And complicated. Do you or does anyone know if things have changed? The closest I've come to this lately is Unity shaders, but I vaguely remember there is a way to run Julia on GPU? Like if each different shader program is run as a layer in a rendering pass. Except rather than 8 or 16 layers, can modern GPUs run more on the order of 100+ layers? What's the limit?

zackmorris 6y ago
Stumbled onto a few crash course items that helped get me a bit up to speed on this: https://www.cl.cam.ac.uk/teaching/1819/AdvGraphIP/03_OpenCL.pdf https://www.cl.cam.ac.uk/teaching/1819/AdvGraphIP/03_OpenCL.... https://stackoverflow.com/a/27250785/539149 https://stackoverflow.com/a/27250785/539149 https://community.amd.com/t5/opencl/parallel-execution-of-kernels/td-p/318178 https://community.amd.com/t5/opencl/parallel-execution-of-ke... https://www.intel.com/content/www/us/en/programmable/documentation/mwh1391807516407.html https://www.intel.com/content/www/us/en/programmable/documen... It's kind of looking like it's not really feasible to run more than a handful of OpenCL kernels simultaneously, certainly not 10,000. Maybe I'm looking at it the wrong way? Conceptually, I want to run a C-style "Hello, World" program with a hundred random instructions after it, hardcoded into 10,000 variations. Then compile and run them simultaneously, passing them all the same data. I mean even being able to do this with 16 different kernels to start with would be awesome!
- joefourier 6y ago
  Ah, I think you’re talking about applying genetic algorithms to self modifying code. In that case you’d want to run the self-modifying code in a VM; if you’re just putting random instructions after another, you’ll most likely just have segfaults, invalid memory addressing, and worse. With a simple VM, you could fit it in a GPU kernel (keep in mind the language limitations) and then you’ll have no issues launching your huge batch in parallel. I don’t know if genetic program generation has any useful applications however. Personally I am more interested in applying genetic algorithms to machine learning, i.e. neuroevolution. A few examples include NEAT and Uber’s reinforcement learning research.
  - zackmorris 6y ago
    Ya the method I want to try is transpiling Lisp to C and then running that on GPU (so no segfaults). As far as I can tell, the problem is that I can only run 10,000 copies of the same shader, not 10,000 different shaders at once on the same data. This is the closest I can come to a "proof" that today's hardware is on the wrong branch of the search space of possible hardwares. I'm hoping to be proven wrong though, and that someone knows a way to run say 16 or more different shaders simultaneously on a GPU. Maybe there is a way to encode the variations in sub-shaders and run those at the same time or something? Edit: a few more links about running concurrent GPU kernels: https://stackoverflow.com/a/53341888/539149 https://stackoverflow.com/a/53341888/539149 https://stackoverflow.com/a/52978372/539149 https://stackoverflow.com/a/52978372/539149 https://community.amd.com/t5/opencl/opencl-concurrent-kernel-execution/td-p/112686 https://community.amd.com/t5/opencl/opencl-concurrent-kernel... https://community.khronos.org/t/concurrents-kernels-in-opencl/7604 https://community.khronos.org/t/concurrents-kernels-in-openc... http://ecosimulation.com/chrisgregg/Publications/Fine-GrainedResourceSharing.pdf http://ecosimulation.com/chrisgregg/Publications/Fine-Graine... http://docs.potionmagic.eu/per.pdf http://docs.potionmagic.eu/per.pdf Unfortunately, concurrent kernels execution is only possible with CUDA on NVIDIA graphics cards. For other cards, OpenCL does not offer this functionality. Looks like it may only be possible on NVIDIA, according to the last link. Since this was the first thing I wanted to do with OpenCL, it doesn't bode well for the standard or AMD. As a software developer, I see this issue a lot. What happened is, their public interface is too thick so doesn't reflect the actual capabilities of the hardware. I hit this with OpenGL too way back before ES2 and shaders were mainstream. I just wanted direct access to some of the matrix hardware math but couldn't get to it. I'd vote to scrap current GPU implementations and move to a pure 2D or 3D grid of compute units (a bit like AWS EC2) running something like Docker. Then write OpenGL, OpenCL, Vulkan, Metal and the rest as niche libraries implementing use cases above the runtime. That would give us bare metal access to get real work done with languages like C, Rust, MATLAB, Julia, Erlang, Go, etc and finally drop the distinction between CPU and GPU.
amkkma 6y ago
Yea, Julia compiles natively to GPUs. See here: https://juliagpu.org/ https://juliagpu.org/

GregarianChild 6y ago

An interesting question is: why are we not seeing fast and scalable GPU implementations of GAs? (I'm not trying to trick you, genuinely curious). I think one problem, making GAs as they are understood today (maybe there is a better way), is the freewheeling, unconstrained nature of GA fitness functions. If the ambient fitness function has a lot of data-dependent branching, SIMD will be slow. Moreover GAs have two phases: measuring fitness and mutation/crossing over to produce the next generation. Is the mutation/crossover phase SIMD friendly? Typically, it involves randomness ... In contrast, neural net training is essentially GeMM (General Matrix Multiply) which is an incredibly predictable workload -- almost no data dependent branching. So none of the things that make processors slow and complicated (caches, prefetching, branch prediction, reservation station, scheduler ...) is needed: instead you can just stream the data from main memory directly into the matrix multiplier (tensor core). This means you can use the available transistors (and energy) much more efficiently. As far as I am aware, GAs have not, so far, been reduced to as simple uniform and predictable a workload as GeMM, which I believe is why GAs don't usually get run on a GPU (not to mention more specialised hardware like TPUs). run each machine almost entirely independently. I am not sure how this works with mutation/crossover. Learning happens by 'throwing away' unpromising search avenues (genes). So if different machines do not synchronise their populations, they don't learn from each other. Synchronisation OTOH is very slow.

joefourier 6y ago
Evolution strategies (essentially the same as genetic algorithms) have been successfully applied to GPU-training of neural networks and parallelise very well. Look at various papers on neuro-evolution (e.g. the ones from the now defunct Uber AI Labs). A simple, very inefficient implementation would be: do inference on n randomly initialised neural networks, calculate loss, select the m best performing and copy them to fill all n spots, add gaussian noise to each weight and bias of every individual, repeat. More efficient mutation and selection strategies exist, but the principle is similar and parallelisation on GPUs is trivial and actually easier than current approaches (atomic operations e.g. compare-and-swap can be used to avoid going back to the CPU for selection). I believe the real reason for neuro-evolution's unpopularity is that for most problems, gradient descent is just faster and more efficient. What would be interesting might be to combine both approaches, using evolution strategies on hyperparameter search, although I haven't read the literature on that front.