Software Design¶
C Simulation¶
Before implementing the simulation in Verilog we wanted to verify that the simulation worked well in the first place. We implemented the simulation in C to achieve a fast computation of the algorithm, and since no individual part of the algorithm was too complex we didn't need a higher order language's bells and whistles (which is why we decided against Python). We also monitored a few features to the algorithm to help with determining if the simulation was interesting:
Avg. Happiness
Avg. sale prices for each good
Quantity produced of each good
Quantity sold of each good
Fraction of goods made by a specialist.
Fraction of people alive.
We implemented the functions from section 2 in a sequential manner in the C code, doing the following set of functions for an actor, then moving on to the next actor for all actors:
Interact with 8 nearest neighbors
Produce
Consume
Adjust values/cooldown.
Each actor was represented by a struct holding the data discussed previously, specialty, hunger, thirst, cash, happiness, and arrays of inventory, value, and cooldown for each good.
We ran the simulation multiple times and observing what set of parameters and how certain simplifications could be made without hugely affecting the result. We printed out the mentioned values of interest, as well as each actor's data for verification. Through the simulation it was determined that the simulation was stable after 10 years (3650 iterations) and that a wide variety of goods was produced. For most goods, production was disproportionately done by specialists (with some exceptions), and that luxury goods were produced in great quantities. There was a decent survival rate of $96.75\%$, compared to a $~55\%$ survival rate if trading was disabled. The result was deemed logical, the quantity of goods produced spread out enough to be interesting, and was interesting enough to implement on the hardware as-is.
Graphics and Visualization¶
The principle of the visualization is to deliver both the microscopic and the macroscopic dynamics of the population that we are simulating. The former is being implemented as a grid-like structure where each cell represents an actor, and the values at each instance are being represented by the color changes. And the macroscopic properties are represented as a 3d time-series curve.
At the early stage of the project, we didn’t have a good grasp of how the simulation would look as the hardware implementation was not done. Thus we first created the visualization on computers with our C implementation of the economy simulation, which uses the Simple DirectMedia Layer(SDL) as the graphics interface library. Then we transfer the relevant part of the C code onto the HPS.
The SDL Library provides a slightly different way to interact with the computer graphics, to reduce the hassle of transferring the code onto HPS to use the VGA library, we created a few functions that abstracts the SDL functions to the ones available in the VGA library such as draw_pixel(), draw_line(). Thus, when we migrate the codebase from the computer to the ARM, we would only have to replace these function calls.
To draw the population grid, we created a draw_island() function, which essentially draws each individual actor as rectangles. And we fill these cells with a several color mapping from values(such as cash, units of goods) to colors.
To plot the macroscopic data, we created a plotting function which draws the axes and plots the aggregated data.
Later we were able to migrate it to the HPS easily.
Hardware design¶
High level design¶
The shift register is the interface for the economy simulation to run on. It was designed to output 9 complete actor data at a time: the current actor for this iteration and their 8 neighbors. Those 9 actors could have their entire data overwritten in one cycle after the compute for fast modification. The actor data at the end of the shift register would be lost on the shift, so it should be written back to memory before shifting. In addition, new actor data would need to be written in at the front.
The logic behind the design is that a correctly sized shift register would hold 2 lines of actor data (the actors being arranged on a grid) plus 3 additional actors, and this would be enough data to avoid re-reading and writing an actor more than once per iteration. I'll show this logic using this scaled diagram.
Imagine the shift register as a ``snake'' slithering around the actor grid. The black dot is the tail of the snake, which should be written back to memory, the white arrow heads a block of memory in the shift register, the gold arrow head the direction the snake will advance in, and the diamonds the relevant actor data needed to perform the algorithm. We write back the tail of the snake, we advance the snake by one square in its path (potentially wrapping to the next column), and feed it the new SE block to create its new head. In this way we can store just enough data in the snake so that only one read and one write is needed per actor per iteration, and the actor's neighbors don't need to be read and written back to immediately.
Implementation¶
The model in the diagrams above works for a grid with minimum dimension 8, but we wanted our actor grid to be as rectangular as possible. We decided to use MLAB blocks since we believed we would have enough to do columns of size 256, however this would involve generating 515 memory blocks and we couldn't get the fitter to fit that many memory blocks in the design. We settled on a column size of 128, which meant instantiating $128 \times 2 + 3 = 259$ memory blocks. There wasn't enough M10K blocks to use after adding in the SRAM VGA driver (more on that in the ``Other Hardware'' section) so we needed to use MLAB blocks for each block in the shift register, except for the currently active actors.
The currently active actors (center and its 8 neighbors) were stored in registers so that the entire 320 bits associated with the actor could be spit out at once for the algorithm. There was enough registers to do this, but not store the whole shift register, as that would need 2 lines + 3 amounts of actor data, or about $82 kb$. There are $128,300$ register bits available on the device, but that would leave a small amount of registers available to perform the algorithm or anything else, so it was decided to use the MLAB blocks configured with 10 32 bit words each.
This meant that advancing the shift register would involve multiple cycles, as the MLAB blocks could only access a word at a time. This was considered fine, since the largest source of latency by far for the project would be SDRAM, as long as the MLAB shift operation was efficient. A pipelined MLAB read was considered, but for ease a program a simple state machine was implemented that read an address, waited one cycle, then wrote the data back, making the shift operation take 30 cycles in total. The piecewise shift was test to make sure no data was lost, feeding the mouse of the snake with random test data and ignoring the tail.
SDRAM State Machine¶
We designed a memory controller to operate the shift register, feeding the shift register new actor data, starting a shift operation, and writing back data at the end of the shift register.
Platform Designer Layout¶
To create the memory block we instantiated an SDRAM memory controller IP on the Avalon bus and sized it large enough to hold our actor data. The SDRAM can be sized up to 64MB, which can easily hold our actor data of about 5.3MB. The SDRAM controller takes care of operating the SDRAM memory for us, which includes occasional refreshes of each memory bank and translating an address to a setting for the row/column/address/bank pins on the SDRAM. Placing it on the Avalon bus may introduce some delay as the bus will abitrate multiple masters are trying to use the bus at a time, which is why we decided to borrow the SRAM VGA driver example from the course website (more on that in the next subsection) to not have the graphics portion interfere.\ To make the memory controller accessible to the FPGA we needed to create a bridge to the Avalon bus using Platform designer.
State Machine¶
A state machine needed to be developed to execute reads and writes to the bridge, setting the read/write address, write data, and storing the read data. The machine would need to wait for an "acknowledge" signal from the bus to know the transaction has gone through. Since the SDRAM memory controller could only be configured to be 16 bits wide (or else the HPS couldn't interface with it) that meant 20 transactions had to occur to read or write 1 actor's worth of data, with a total of 40 transactions per actor per iteration (write back the tail of the shift register, read in the new head).\ To advance to the next actor, you must do this in order:
Write back the tail.
Advance the snake.
Read in the new head.
To write back back the tail you must iterate through each 16-bit word in the northeast neighbor, and the new head must be read into the southeast neighbor 16 bits at a time, waiting for an "acknowledge" after each transaction.
Other Hardware¶
A few notes on ancillary hardware for the project.
SRAM Video Controller¶
To avoid using the SDRAM for video data, which could add traffic to the Avalon bus, we used the SRAM video driver from the course website. Video data would then be written to M10K memory on the lightweight bus instead of SDRAM. The drawback is that only 8 bits were available to define color instead of 16, but this was a fine tradeoff since the video display would be used for a visual display, and it wasn't important to have a wide color field.
PIO¶
A few pio were added to control and monitor the simulation.
Pause: halts the state machine to allow a fresh grid of actors to be loaded in from the HPS.
Finished: high when an iteration has been finished since the last pause.
Timing: Counts how many clock cycle it takes to finish one iteration.
These control signals allow the HPS to pause the simulator when initializing data as well as only refreshing the VGA display after an iteration.
Compute Module¶
Lastly, the actual economy compute module had to be created to simulate our economy. The module needed to take in the array of people and return a new array that have, interacted, adjusted, produced, and consumed. The Verilog followed the structure of the c code very closely. Each function could be contained in a module. Constant arrays like the "Probabilities" array could also be defined as parameter arrays in system Verilog. We used the features of System Verilog extensively, especially exploiting the value of structs and logics. With structs, we could structure our code around the person_t struct thus keeping writing and reading from person_t members easy. Without this, we would have had to split up person_t members into separate inputs and outputs. The struct also has a very direct relationship to the synthesizable code, so there wasn't a chance for confusion from abstraction. One thing we had to be careful of was that since we can't take in person_t structs and write to them and read from them, we had to split the module into an input and output person_t. Writing each member of the input person to the output person combinationally unless the module changes the value of the output. Another consideration we had to make was with regards to large lookup tables like our "f" function from the c code. Instead of using the complex arithmetic, from the function, we made a lookup table of the results of the function. This lookup table is about 2100 lines long, way too large to fit in a combinational lookup and would take away almost all our LABs. Since our bottleneck was our SRAM read and write speed, we sacrificed a couple of our clock cycles by making the lookup sequential.
Module to function conversions that were combinational like the trade module were a very simple conversion. Rather than rewrite variables, we created new wires for each result.
Sequential modules on the other hand were a different story. Some for loops could be eliminated while some could not based on their dependency loop. For example, looping through goods could be formed into a generate statement as producing, consuming, and trading could be done across all goods at once. On the other hand, when interacting, each trade had to be done sequentially, so a state machine had to be created based on the index variable.
To keep the interactions between the modules similar to the c functions, we formed all sequential modules with of course a clock and reset signal, they would also have a done output signal. To reflect the c code, running a "function" involved pulling the reset signal low, and waiting until the done signal went high, then grabbing the output value and resetting the module.
The last thing to implement was to interface with RAM. Since the ram stored each person as a bit reg, we needed to convert the reg to a struct. To do this, we made person_to_bits and bits_to_person modules. Each would take in the former as an input and wire the bits to a struct. Since we had knowledge of the amount of bits each member took up as discussed above, we could make our own offsets, grab sections of bits and stick them into the members of the person struct. This could of course be done combinationally. The module was essentially just a rewiring of bits. Therefore, when people are taken from RAM, they are converted to person structs, inserted into the compute module, and reformed back into bits at the output.
Here is a diagram for the overall structure of the compute module.
Here's how the verilog is structured, there is a trade module which combinationally takes in an input buyer, seller, and good to sell and outputs the buyer and seller post trade.
The Interact module takes in a buyer and an 8 long array of sellers. The module has a trade module contained within it. Using a state machine, the interact module loops through the sellers and goods trading each sequentially. The module outputs the post-interaction buyer and sellers when the done signal goes high.
The utility and desire functions from the c simulation are combined in the utilites_and_desires module which combinationally calculates the utility and desire for each good. Though due to the previously discussed lookup table, the module takes 1 cycle for the result to show.
The expected_value module is another combinational module providing the same inputs and outputs as the c code, but for each good once again.
The actual compute module then provides instances of the interact, adjust, produce, and consume modules. They all share a clock, but the interact module takes in the input persons. The module contains a reg with the person being adjusted and feeds the same reg through all modules, with the output person wired to the reg. The way the sequential nature works is that the reset for the adjust module is tied to (interact_done || reset), produce is (adjust_done || reset). Therefore if the compute module is reset, all modules will be reset, but if the reset is lifted, a module will only start when the previous module has completed.
Testing¶
Software¶
The software testing was quite qualitative since the type restrictions were loose and development and debugging was quick and easy. By looking at the visualization of the economy we could see the behavior we expected based on the initial conditions. For example, no production should result in a starving and dying population. Starting an economy with a high value for a certain good should make people specializing in that good rich.
Hardware¶
Since we didn't use floating point for any of our simulator operations, the verilog that we wrote on the FPGA for the compute module should produce the exact same values as the c code given the same random seeds. Using this we could write many unit tests for each module.
We used SVUnit to test our code. This was able to easily produce a dut and make an easy interface to catch errors. We could then run this with the modelsim command line to get quick unit test results and ensure the verilog worked with the c code. For each module, we would of course make a test file in c. We would create the appropriate initial conditions in our person_t structs and input values which because of our system verilog structs, we could easily reproduce on the verilog side. We then took the C output and compared it to our DUT's own output. The first test was always to put conditions on the module so that no activity would occur. An example is a person interacting with its neighbors, but no-one has enough cash to trade. This should result in the output people being the same as the input people. We would always check that these values weren't don't care values. If any of them were, we had an undriven output. This is where it was important to use the "===" equality operator rather than "==", the former will return false if one of the values is don't care, but the latter returns true. Our next type of test would be a simple comparison to the c code outputs. The last test we would do would be checking boundary conditions to make sure that the bit sizes we allocated to each member, struct, or reg was appropriate and not cutting off values. We made a unit testing structure like this for almost every single module in our files ensuring that the verilog at least behaves just as the c simulation does.
Testing on the FPGA was harder. Due to our speed bottleneck, our time-steps were very small, so we couldn't analyze long-term behaviors of the economy and check it against the c code output. We could at least test the initial behavior of the economy. Such as if there is no production and each person has no inventory, there should be no trading or inventory present. Adding production in should slowly grow inventories.
