Oceanography 101

We created a marine ecosystem simulation, modeling the behaviors of various sea creatures as they interact with each other and their environment.

The simulation models the creatures as boids and focuses on symbiotic relationships and predator-prey dynamics, providing an interactive and educational tool for observing ecological interactions.

The system is implemented on the DE1-SoC board which houses an FPGA and HPS processor. We use the HPS to implement our boid algorithm and interact with a python GUI, and the FPGA to draw and synthesize audio.

Demo Video

Rationale and Sources for Idea

We chose this project because we were interested in modeling some sort of interaction between particles. We all share an interest in animals and were excited at the prospect of getting to observe animal interactions. We went through a couple ideas of what algorithm to use to model the animals, and landed on the boids algorithm as we learnt about it in ECE 4760 and were interested in exploring it more.

Background Math

The basis for our algorithm was the boids algorithm we learnt in ECE 4760. This algorithm models the flocking behavior of animals. The movement can be summarized by the following rules:

• Separation: boids move away from neighbors that are too close
• Alignment: boids attempt to match the velocities of their neighbors
• Cohesion: boids move toward the center of mass of their neighbors

Each boid has a position (x, y) and velocity (vx, vy). A neighbor is in the visual range of a boid if the neighbor is within a certain distance, and is included in the boid’s alignment and cohesion calculation. A neighbor is in the protected range of a boid if the neighbor is within a certain distance (less than the visual range), and is included in the boid’s separation calculation. Every boid iterates through the list of boids and updates the separation, alignment, and cohesion variables depending on if the neighbor is in its visual or protected range. Here are how the three rules are updated:

• Separation: We accumulate the sum of the opposite directions away from neighbors in a boid’s protected range. Then, we update the boid’s velocity by the sum to steer away from its neighbors in its protected range:
close_dx = close_dy = 0
loop:
    close_dx += boid.x - neighbor.x
    close_dy += boid.y - neighbor.y
boid.vx += close_dx * avoidfactor
boid.vy += close_dy * avoidfactor

• Alignment: We calculate the average velocity of all neighbors in the boid’s visual range and update the boid’s velocity to match:
xvel_avg = yvel_avg = neighboring_boids = 0
loop:
    xvel_avg += neighbor.vx
    yvel_avg += neighbor.vy
    neighboring_boids += 1
if neighboring_boids > 0:
    xvel_avg = xvel_avg/neighboring_boids
    yvel_avg = yvel_avg/neighboring_boids
    boid.vx += (xvel_avg - boid.vx)*matchingfactor
    boid.vy += (yvel_avg - boid.vy)*matchingfactor

• Cohesion: We calculate the average position of all neighbors in the boid’s visual range and gently steer towards the center of mass:
xpos_avg = ypos_avg = neighboring_boids = 0
loop:
    xpos_avg += otherboid.x
    ypos_avg += otherboid.y
    neighboring_boids += 1
if neighboring_boids>0:
    xpos_avg = xpos_avg/neighboring_boids
    ypos_avg = ypos_avg/neighboring_boids
    boid.vx += (xpos_avg - boid.x)*centeringfactor
    boid.vy += (ypos_avg - boid.y)*centeringfactor


Logical Structure

To emulate an ecosystem, symbiotic relationships are represented by attraction and repulsion forces between animals.

• Mutualism: Both animals benefit; they are attracted to each other, e.g., clownfish and sea anemones
• Commensalism: The commensal benefits without affecting the host; the commensal is attracted to the host which is neither attracted nor repelled, e.g., barnacles on whales.
• Parasitism: The parasite benefits at the expense of the host; the parasite is attracted and the host is repelled, e.g., barnacles on sea turtles.
• Predator-Prey: The predator chases prey; the predator is attracted and prey is repelled, e.g., sharks and fish

In the case of parasitism and predator-prey relationships, after being exposed to the parasite/predator for a certain amount of time, the host/prey is killed. Additionally, if two of the same animal are exposed to each other for a certain amount of time, they procreate and a boid of the same species is spawned.

A python GUI communicates with the ARM by sending commands to a FIFO queue to customize what kind and the number of animals spawned. The ARM calculates the positions and velocities of every boid, based on the math described above. After updating every boid, the ARM and FPGA perform a handshake and the FPGA draws the boids on a VGA display and emits audio with the tone corresponding to the population size.

Hardware/Software Tradeoffs

On the FPGA side, our primary objective was to achieve acceleration. Initially, we contemplated performing all calculations on the FPGA, but could not find an effective method to parallelize the system and fully leverage the FPGA's capabilities and would have run out of multipliers. We considered offloading a portion of the calculations to the FPGA, but this would require transferring values (x, y, vx, vy) at least four times per boid, which was impractical for handling 700 boids. The acceleration of drawing boids on the FPGA increased the number of boids from 450 to 700 boids to meet frame rate requirements. Thus, all boid interactions and calculations are done on the ARM.

HPS

We added the attractive and repelling forces between animals by creating a struct that represented an animal and its symbiotic relationships.

typedef struct animal {
    short color;
    fix15 speed;
    int rels[9];
} animal;


The color variable is the color of the animal drawn on the VGA screen. The speed defines the minimum and maximum speed the boid is bound between: [speed, 2*speed]. The rels array is indexed as follows:

#define NAME 0
#define MUTUAL 1
#define HOST1 2
#define HOST2 3
#define PARASITE 4
#define PREY 5
#define PREDATOR 6
#define COMMENSAL 7
#define FLOCK 8


Each element of the array contains the unique int identifier of the other animal in the symbiotic relationship, with rels[NAME] containing the id of the animal itself. The relationship is “my [rel] is [id]”, for example, “my PREY is FISH”. The rels[FLOCK] element is 1 if the animal flocks together.

The boid struct contains a pointer to its animal as well as “time” attributes that incremented every time the boid is eaten by a predator, exposed to a parasite, or near another boid of the same species for procreation. Once the “time” attributes reach a certain threshold, the boid dies or a baby boid is spawned, respectively. Additionally, there is an attribute called is_alive that indicates if the boid is alive or not due to parasitic or predator-prey behavior.

typedef struct boid {
    fix15 x;
    fix15 y;
    fix15 vx;
    fix15 vy;
    animal *a;
    int eat_time;
    int is_alive;
    int parasite_time;
    int baby_time;
} boid;


Adding to the boids algorithm, the separation, alignment, and cohesion rules are updated depending on the animal relationships. If the animals are attracted to each other (mutual, flocking, host, or prey relationship), the boid’s cohesion and alignment rules are updated. If the animals are repelled from each other (parasite or predator relationship), the boid’s separation rule is amplified by accumulating another variable called avoid_dx and avoid_dy. The normal separation rule is applied except for mutual, host, prey, and commensal relationships, since we want those relationships to be able to overlap the same space, for example, predators catch up to prey).

We maintain a list of boids, the boids being initialized by numbers specified from the GUI. Animals are initialized with their relationships and boids are initialized with a pointer to its animal. We iterate through the list and update every boid depending on its relationships defined by its animal.

The HPS has two threads: one that updates the boids and one that reads from a FIFO. The thread that reads from a FIFO is described in more depth in the GUI section (below).

The animate thread must meet timing constraints. It gets the time at both the beginning and end of the while loop, then calculates the elapsed time. If the elapsed time is less than the frame rate (the number of microseconds per frame), the thread will wait until the elapsed time is equal to the frame rate. It will also draw a green disc in the upper left hand corner to indicate that we’re meeting our desired timing. If the elapsed time is greater than the frame rate, a red disc is drawn.

FPGA

On the FPGA side, our main goal was acceleration. We first considered doing all of the calculations on the FPGA but we did not have a good way to parallelise the system and take advantage of the FPGA. We also realized that we would likely run out of multipliers.

Our next thought was to shift just part of the calculations over, but that would require sending back and forth at least 4 times as many values as boids we have (x, y, vx,vy), and that did not make sense to do for 700 boids.

We decided to draw using the FPGA. The GPU with FAST display from SRAM from the Quartus 18.1 examples page was used as the basis to accelerate our drawing. We modified the disc drawing function on the HPS to use SRAM pointers.

We also implemented audio. We wanted the frequency of the audio to be a function of the population size. We created a PIO port named “nomnom” that is an input into the FPGA from the HPS. Its value is the number of boids that are alive, and it is updated whenever boids are spawned or killed. We implemented DDS using the Audio output bus master example from the same webpage and use the nomnom PIO port as the accumulator. We implemented the audio subsystem and bus master audio in QSYS as well.

QSYS Connections

GUI

We created a GUI to give the user control over the simulation. The user can pause, play, speed up, and slow down the simulation. The user can also change simulation factors such as the number of each animal and the boundary mode. We have a couple of predefined presets that we think show interesting behaviors, and the user may select these presets and enter the total number of animals they would like to see.

GUI

Establishing communication between the GUI and the ARM took some effort. Our initial thought was to use serial communication, but we were unable to get that working. Our next thought was to run the GUI directly on the ARM (thus requiring no communication between devices), but we were unable to install the necessary python modules. Eventually, we came up with the idea of using FIFOs.

Our python GUI (running on our personal laptops) begins by ssh-ing into the DE1-SoC using the paramiko module. Upon a button press, it sends a command to the command line on the ARM. The command “echo instruction > /home/root/Final/FIFO_Testing/test_fifo” writes the instruction into the FIFO. Our HPS then reads from this FIFO, processes the instruction, and updates the simulation accordingly.

The read_fifo thread on the HPS opens the file for read only, then continuously tries to read from the FIFO. If the FIFO has something in it, it will first strip any \n or \r characters from it. Next, it will check for an instruction, described in the table below.

The boids in our simulation look smooth, with no flicker, hesitation, or jerky movements. We felt that the simulation looked quite nice at a frame rate of 30 frames per second, so we decided to use that as our initial value.

When using the HPS for drawing, we were only able to draw around 450 boids while meeting the frame rate. When drawing with the FPGA, we could draw around 700 boids. This is a significant increase.

Project Features

We are quite happy with our results and think we have a well integrated, fun, and educational system. It was very interesting to observe emergent behaviors and population oscillations as we played with the different ecosystems.

This project could go on forever as there are infinite interactions and animals we could introduce. We think natural death and animal size are the best features to include next.

One of our goals when starting out was using parallelisation and leveraging the FPGA more meaningfully for acceleration, but we were not able to come up with any elegant solutions for this. Even without this, we were able to see a significant speedup through the use of the FPGA.

We leveraged examples from the Quartus 18.1 web page when writing our Verilog code, but we did not use anybody else's code outside of that.

Appendix A : Approvals

The group approves this report for inclusion on the course website.

The group approves the video for inclusion on the course youtube channel.

Appendix B: Work Distribution

We all went to the lab and worked together. We also wrote the lab report together.

Ashley created the GUI and established communication between the python script and the HPS.

Bhadra moved drawing over to the FPGA and did the audio synthesis.

Elise implemented the interactions between the different boids on the HPS.

Appendix C: HPS Code

Appendix D: Verilog

Appendix E: GUI Code