I need a good visual O(n) algorithm



  • For background, my company is working on a shared memory product that is nearly ready for release. It's a custom PCI Express board that can connect to a fiber optic network. All the boards on the network keep their RAM synchronized over the fiber network. It's a very fast, low-latency way for multiple systems to keep a common set of data synchronized.

    Right now my role is mostly testing, and as part of that I'm working on a couple demo suites which are essentially distributed simulations using the shared memory for synchronization. My first demo is a 2-dimensional N-body gravity simulation, simulating Newtonian gravity among a set of particles, and rendering the current state to a window. While it's a cool demo (and has already uncovered a few bugs in our hardware since it's a lot more intensive than our unit test suite 😆), it's an O(n2) algorithm and does not scale well as the particle count goes up. Double the particle count, and I have to quadruple the number of PCs to maintain performance.

    Here's an animated GIF of one of the displays (assuming Discourse doesn't Discourse-up the GIF):

    I want to do another demo which is O(n) so it scales linearly data and with additional PCs. Double the simulation data and frame rate drops to half, then double the number of PCs and it goes back to what it was.

    I was thinking of another particle simulation, but one where the particles only interact with some kind of force field and not with each other, which will bring it down to O(n). It may be too similar to the N-body gravity demo, but I'll probably do it anyway.

    Any suggestions? Whatever it is, it needs to be something I can graphically render in a pretty manner to make our sales guys and customers ooh and aah.



  • Spontaneously I'd think of charged particles in a magnetic field.

    Maybe solar wind against Earth's magnetosphere?



  • Well, I'm off to Wikipedia to refresh myself on how magnetic fields affect moving charged particles.



  • Wow, that sounds like a cool project/product, not that I understand how it can be used, but anyway, AFAIR there are some fractal algorithms that are O(n)



  • @Eldelshell said:

    not that I understand how it can be used

    That makes two of us, actually. My understanding is existing customers want to use it to tie together a large number of avionics testing equipment, since they need a large number of interface boards and most PCs do not have unlimited PCI Express slots. I see this and my inner nerd screams "Scientific supercomputing!!!!" which is what's guiding my testing and demo ideas.



  • @mott555 said:

    Well, I'm off to Wikipedia to refresh myself on how magnetic fields affect moving charged particles.

    Oh bugger, I forgot the interaction was 3-dimensional. I wanted to keep it 2D so I could have a static background image to indicate field strength...

    I suppose I could switch it to charged particles moving through an electric field, and completely ignore the magnetic portion, that ought to make it simple to squash back down to two dimensions. Or make the magnetic field always perpendicular to the screen.


  • area_pol

    Simulate the ideal gas - no iteraction between particles, particles fly around and bounce on walls. The complexity is number_of_particles * number_of_walls.

    • You can then add a constant number of dynamic objects and simulate pressure, make pistons or sails or a steam engine if you are ambitious.
    • Alternatively, put many particles in one place and simulate an explosion like this:

    There are more explosion pictures in this [tutorial][2]

    Or try running the [Powder Toy][3] game.
    [2]: http://www.iforce2d.net/b2dtut/explosions
    [3]: http://powdertoy.co.uk/


  • Winner of the 2016 Presidential Election

    For background, my company is working on a shared memory product that is nearly ready for release. It's a custom PCI Express board that can connect to a fiber optic network.
    For a second, I thought we worked at the same company, but then I read
    avionics testing equipment


  • IIRC Gouraud shading is linear respect the amount of light sources...

    and you cna make a pretty teapot
    http://www.crypticcypher.com/images/school/gwu/cs6554/teapot_iso_gouraud.png



  • An early version of the Lorentz Force demo is nearly done. Only problem, it's too damn easy! 😆 At O(n) complexity, a single PC doesn't even sweat at 10,000 particles, and graphically it's a visual mess. I suppose I could greatly expand the simulation space, and allow pan/zoom functions on the display.



  • Well, that's the problem with such simplified field interactions - you can solve them analytically which kind of does away with the reason why we needed computers for such simulations in the first place. 😄



  • Anything that doesn't look at all other particles, but a bounded subset. If that bound is coordinates, you'll need an O(n) way of determining which particles are nearby. You could assign a (random) subset at the start to each particle, and then you'll get some kind of flocking behavior.



  • Cellular automata!
    They're simple, very visual, and there's a vast quantity of well-documented interesting patterns and algorithms (thanks to obsessive geeks dedicating their lives to finding more). There's computers made inside Conway's Game of Life that simulate another level of Conway's Game of Life, etc.

    https://www.youtube.com/watch?v=C2vgICfQawE
    (excuse the "epic" music, you might want to mute)

    Here's a fun example: https://www.quinapalus.com/wi-index.html
    Just install https://golly.sourceforge.net/ and play with them for a while.

    Alternatively: basic fluid simulations! Which are essentially cellular automata. I'm sure you've seen the "falling sand game"?

    Amusingly, Google keeps suggesting a paper called "Scalable fluid simulation in linear time on shared memory multiprocessors", which on one hand is exactly what you're looking for, but on the other hand is probably overkill for a small demonstration.

    For testing though, maybe you should focus on finding existing simulation code and porting it?


  • Discourse touched me in a no-no place

    @mott555 said:

    I want to do another demo which is O(n) so it scales linearly data and with additional PCs.

    The problem there is that virtually everything that is linear will scale trivially, and O(nlogn) will be almost as trivial (that log term really doesn't grow fast). You'd be better off finding something where you can limit the number of interactions for each particle to only using an easily-selectable subset of the overall particles.

    But particle demos are very cool, as they're great at showing emerging behaviours. Avoid general field demos though; they're awesome, but the mathematics is evil. The suggestion of solar wind demonstrating is such an example; magnetohydrodynamics is viciously nasty. 3D wouldn't be a problem though; projecting onto the plane of the ecliptic is trivial, and would be what a researcher in the field normally does. (I used to work with solar wind researchers, organising their data.)

    You could try doing some simple demonstrations of turbulence in ordinary liquids. Perhaps constraining them to effectively 2D, as if you're looking at something like these. I used to have one, and I could look at it for ages; it's behaviour was both simple and really complicated. Alas, I fear this will make your gravitation demo look trivial. 😃



  • Also: 3D rendering?

    It's embarrassingly parallel, so O(n) in respect to the number of pixels, but still slow enough that you can clearly see the difference between having 1 PC and having 3 (unlike, for example, rendering Mandelbrot fractals). Ray tracing in particular is very slow but looks really cool.

    The downside, of course, it's an order of magnitude more complex than particle simulation. So you'd probably want to port an existing renderer to your architecture, and I don't know how easy that is.



  • I can do 3D rendering with DirectX, just not interested in it since outputting a 2D particle universe to a bitmap myself is rather trivial.

    I think a fluid simulation is the next thing I'll investigate, but that's not something I have any experience with. I started with gravity and magnetism since I studied those heavily in college and even did particle simulations for them back then out of boredom, it's nothing new to me.


  • Discourse touched me in a no-no place

    @mott555 said:

    I think a fluid simulation is the next thing I'll investigate

    Those can be really awesome. I remember when we used to do those back when we ran a supercomputer and visualisation centre; the flow over things like aircraft wings was quite interesting, though generally almost all the staff were cleared out of the area when that was going on. Something about commercial secrets. 😄


  • FoxDev

    @anonymous234 said:

    There's computers made inside Conway's Game of Life that simulate another level of Conway's Game of Life, etc.

    so what you're saying is Conways Game of Life is Turing complete?



  • I think someone proved that CSS is turing-complete because you can implement Conway's Game of Life using only CSS, HTML, and a user pressing tab-space-tab-space-tab-space.


  • FoxDev

    @ben_lubar said:

    and a user pressing tab-space-tab-space-tab-space.

    that's a hell of a slow clock cycle if you're relying on meatwear to provide you clock pulses




  • FoxDev

    @ben_lubar said:

    >-webkit-animation: bugfix

    .... :wtf: css? are you drunk?


  • Winner of the 2016 Presidential Election

    @mott555 said:

    I think a fluid simulation is the next thing I'll investigate

    Mandatory youtube video that everybody in here already knows but I feel like posting:

    https://www.youtube.com/watch?v=QMYfkOtYYlg

    Filed Under: #bored



  • You bet! http://rendell-attic.org/gol/tm.htm

    But it's not really the best cellular automaton to make a turing machine in. With only 4 states and 4 rules (3 or which are trivial, and the other one is really simple) you can make something that behaves like "electric signals" and also makes logic gates easy. From there implementing a full processor is easy.

    @ben_lubar said:

    I think someone proved that CSS is turing-complete because you can implement Conway's Game of Life using only CSS, HTML, and a user pressing tab-space-tab-space-tab-space.

    I'm pretty sure that was with a 1-dimensional cellular automaton. Still turing complete.


  • BINNED

    wow that toy game is amazing, and it is open source, my wife will love that, thank you :)


  • Discourse touched me in a no-no place

    Wireworld is fun (especially since it can be both computation and display) but relatively static since empty cells never change and other cells never become empty.

    If you want to make it go fast, you should pre-compute the neighbourhood of each non-empty cell. Or at least that was the single thing that made the most difference when I had a go back in college. 😉 I also did something with a ring buffer that helped quite a bit, but I can't remember exactly what. It might've been something to do with efficiently converting heads to tails and tails to conductors? I do remember that I never worked out how to size the buffer to my satisfaction.



  • @dkf said:

    Wireworld is fun (especially since it can be both computation and display) but relatively static since empty cells never change and other cells never become empty.

    Hmm, make a similar automaton where the "electrons" travel through empty space? And the "wires" just redirect them to the next processing element.

    I should spend some time doing this.

    And then do a VHDL-to-this compiler. I'd have Linux running on that shit in no time.

    Too bad I can't spend my entire life doing fun but completely useless projects.


  • Discourse touched me in a no-no place

    @anonymous234 said:

    Hmm, make a similar automaton where the "electrons" travel through empty space?

    That would require a more complex automaton. The interesting thing about wireworld is that the automaton itself is very simple (four states, Moore neighbourhood, only one non-trivial evolution rule). Conway's Game of Life is theoretically a bit simpler, but it's more complex to implement efficiently. Wireworld implementations can be very fast indeed.


  • Discourse touched me in a no-no place

    And my actual favourite model of computation is train sets. :-D The linked points are the key to emulating a cell of a Turing machine tape in finite space IIRC.

    Not that this helps @mott555 at all. ;-)



  • That's a fascinating website.

    So much work has gone into writing those explanations and making those interactive simulations.



  • @Adynathos said:

    There are more explosion pictures in this [tutorial][2]

    Or try running the [Powder Toy][3] game.
    [2]: http://www.iforce2d.net/b2dtut/explosions
    [3]: http://powdertoy.co.uk/

    Hell, most of the other advanced tutorials are fun too: http://www.iforce2d.net/b2dtut/

    (EDIT: let's all pretend this post went to the Quick Links Thread like it was supposed to...)



  • Okay, update on the Lorentz Force demo: My system gets appreciably slow at 100k particles (~150ms per physics tick) and graphically it is fine if I reduce each particle to a single pixel instead of the 5-pixel star I was using before. This ought to scale well enough to be useful without looking cluttered now.



  • GIF format kind of murdered the magnetic field display, but you get the idea:

    http://i.imgur.com/asAH8Ns.gif


Log in to reply