Parallel, multi-variate simulations of collective behavior for tiled display walls

To properly evaluate models for complex systems, it is often necessary to run results across a multi-variate parameter space.  Changes in one input parameter might have implications for the system as a whole.  Further, many permutations of input parameters are possible, leading to high complexity in comparing simulation output given differing input parameters.  

Large, high-resolution displays provide researchers with the space to view and compare simulations run in parallel with varying input parameters.  To test this approach, I developed a system that runs multiple, simultaneous simulations of fish collective behavior.  The schooling simulation was implemented in OpenCL and was based upon the behavior model for collective behavior described in the following journal articles from the Couzin lab at Princeton University:

Specifically, I sought to consider the question of the first article, and evaluate whether a small number of informed individuals within a large school of fish could direct movement toward a target, such as a food source.

Source Code
Source code for the program, including a makefile for MacOsX, can be downloaded here
This program requires OpenCL libraries, OpenGL and GLUT.  
At present, it should compile and run on Mac and Windows in '4 simulation' mode.  For Linux it defaults to 18 simulation mode, which is designed for large, high-resolution displays. 

Design Platform:
The program was created for my 2007 MacBook Pro the runs an NVIDIA GeForce 8600M GT as well as for the Electronic Visualization Lab Cybercommons.  In the cybercommons, this program runs on 18-tiled displays with a total resolution of 8196x2304.  "The wall' is powered by 3 NVIDIA GTX 480 GPUs and runs the OpenSuse operating system.  

Program runs at 40 frames per second when showing 4 simulations on my Mac.  It runs at approximately 20fps on the wall when showing 18 simulations simultaneously. 

What does the program show
Depending upon your system, 4-18 simulations will open showing fish clustered initially in the center of the tank.  In 4 simulation mode, the bottom left simulation shows a control school of fish, with no informed individuals. The fish in this tank should display normal schooling movements.  Along the X axis, as you move to the right tanks have increasing numbers of individuals informed about a food source as target 1, the red point in the tank. Along the Y axis, as you move upwards the tanks have increasing numbers of individuals informed about a food source at target 2, the yellow point in the tank.  Information about the number of individuals informed about each food source is displayed atop each tank.  

How to control the program
To change the number of individuals with information about the targets, click 'm'.  A menu will open that allows you to increase or decrease the number of individuals informed about a food source as target 1, the red target, or target 2, the yellow target.  These changes will go into effect when you click on the 'Reset Program with New Values'.  To exit the menu, press the 'm' key a second time. 

To move about the scene:
    + zooms in
    - zooms out
    right arrow moves the camera to the right
    left arrow moves the camera to the left
    up arrow moves the camera up
    down arrow moves the camera down
    click and drag to rotate the tank

Fish schooling behavior:

Separation:  Separation is the inclination of individuals to avoid collisions and keep space between individuals, even in tightly packed groups. 

This is a strong force for the fish in my simulation.   All individuals at the start had a degree of separation of 1.0, which means that this force contributes more strongly to the movement of the population than the other primary schooling forces- cohesion and alignment.  The fish in the simulation will execute a separation maneuver when it is 1.5 body lengths from any fish.  

If the fish were not executing a separation maneuver, then cohesion and alignment could be taken into account.  

Cohesion:  The tendency of an individual fish to move toward the average position of its neighbors.  This exerted a force of '.01' in the simulation, a relatively small contribution. 

Alignment:  Similar to cohesion, alignment refers to the tendency of individuals to move at the same rate and in the same direction as their neighbors.  This contributed .16 degrees of influence on the fish behavior.  

Cohesion and Alignment were computed for fish that were within 3 body lengths, a relatively small area.  

Obstacle Avoidance:  Fish in the simulation stay within the bounds of the tank, with the rare escapee (a bug that would need to be worked out in future versions).   I used the following approach:
1)  Create 3 'scan lines' - one in the direction of the velocity and two at a 30 degree angle from this orientation.  
2) Scan forward at set intervals for some range until a obstacle is detected.  
     If no obstacle detected in any direction, no brake or steering force is applied
3)  If an intersection is detected, apply a braking force, inversely proportional to the distance of the boid from the object, and proportional to the magnitude of the velocity. In principle, the braking force increases as the object gets closer, and its direction is in the reverse of the forward velocity. 
4)  After applying a braking force, apply a steering force that is lateral to the forward velocity, and is most strongly weighted toward the closest intersection point.  (Eg. if the scan line on the right is closer to the object, then the change in lateral velocity will be weighted away from the right side. 

This force is applied to the velocity after the schooling behavior above is calculated.  

Constraining 'thrashing'
To prevent the fish from appearing to 'thrash', I limited the degree of change in angle between the old velocity and the new velocity to 45 degrees.  This was accomplished using 

Displaying multiple simulations
The approach that was adopted for this project may not be the fastest approach.  The design was originally geared toward the potential for large data sets in each simulation, and with the goal displaying the output vertex buffers in separate OpenGL contexts.  

In the main program, I generated a data set with random fish positions in the center of the tank, random velocities between the max and min velocity.  I also generated the cl program, obtained the cl device list and cl context for the chosen GPU.  (While multiple GPU's could have been directly employed in the computation of the fish movements, this proved difficult with openGL coordination.)   

Each simulation was in an object that I called 'subwindow', though technically no subwindows in the strictest sense were used.  Each subwindow class had its own data- copied from a standard global data set to ensure uniform initial conditions between simulations- cl command queue and cl kernel.  

The GLUT call to display the main window triggered calls to display each fish tank, in which the kernel was run and the results shown within a separate viewport.  These calls were performed sequentially for all the fish tanks. 

Attempting to use multiple GL contexts
Initially, I hoped to run each simulation in a subwindow, expecting faster rendering time on the tiled-display wall.  However, when run in separate contexts, I could not call 'void* ptr = glMapBufferARB(GL_ARRAY_BUFFER, GL_WRITE_ONLY_ARB) b.  This call only returned a null pointer and no solution could be found within the project timeframe.  So, I switched to displaying the simulations in one GL context, but multiple viewports. 

For each thread, the data for fish positions, velocities, targeting and schooling parameters was stored in 'float4's and read one time from the global memory and stored in local memory.  

What can be observed with the program

Even a small number of informed individuals led large portions of the school to the resource.  2-4 individuals alone can pull a subset of the school toward the resource.   Below, observe a series of screen shots of 10 informed individuals out of 1024 leading two subgroups of the school to the respective targets.

Fragmentation is a regular result of the simulation with subgroups splitting off to form smaller schools.  This behavior is observed much less often in groups with no informed individuals.  These groups tend to stay together.


I found that, in general, high numbers of informed individuals tend to fragment school into a group following the lead of the informed subpopulation, and smaller subgroups not moving with the informed subpopulations.   This occurs even when there is only informed individuals for one target.  The act of pulling toward a target tends to fragment the group.  

Results appear to vary depending on the placement of informed individuals.  As a result, repeated runs of the same parameters yield different results.  It would be necessary to systematically record results to detect patterns.  

Challenges and Surprising Results
During the course of completing this project, some surprising differences were found to exist between platforms.  Attempting to understand and address these problems consumed a large portion of the development time.  Some of the problems could not be fixed and I don't entirely understand the underlying causes of these strange results. 

1) On the wall, when given identical initial conditions, all simulations run identically- the fish in each simulation moves in exactly the same way.  This is the expected result, since all simulations have fish in the same initial random positions with the same initial random velocities. Since the computation of changes in velocity is entirely deterministic.
However, on the MacOsX machine, running an NVIDIA GeForce 8600 in OpenCL version 1.0, the simulations with identical starting conditions run differently. I cannot account for this behavior from my OpenCL kernel alone and I find it difficult to conceive of a reason for this variability.  I do not know where randomness enters into the execution of the program on this platform.  

2) Schooling behavior varies from platform to platform, not just in apparent motion of the fish, which might be expected with variable frame rates and computation rates.  What was observed was variability in computed velocities between simulations run on the MacOSX platform and the tiled-display wall.  This finding stemmed from an early observation that the fish 'schooled better' on my Mac than they did on the wall, when run in one simulation.  The frame rates between simulations varied considerably, which led to differences on rate of movement, however, though the frame rate on the wall was approximated 8x's faster, the fish appeared to move more slowly and mostly moved in a straight line with no significant changes in velocity.  When I colored the fish by whether they reached the 'maximal velocity' or the 'minimal velocity', a step I completed to ensure the fish did not move too slowly or too quickly, I found that on the Mac, the fish were mostly hitting the maximal velocity, while on the wall the fish were mostly hitting the minimal velocity.  
Since the computed velocities do not take the time between computations or the frame rate into account, I would expect identical velocities to be computed for the fish, with only apparent differences in speed arising from different frame rates. I cannot account for why one platform would more regularly compute slow fish velocities and another more regularly compute fast fish velocities.  
I spent a significant amount of time checking the kernel for floating point errors- perhaps I divided by an integer in one place that was only picked up by OpenCL 1.0, the sort of error that could account for the different computed velocities.  But nothing adequately resolved the problem.