Julia Set Renderer

The pixel solver, a shim around the the VLIW processor, provides an interface for controlling the VLIW processor. Interfacing with the pixel solver entails setting the instruction on each cycle and waiting for the done interrupt to be thrown. On the same cycle that the inputs are ready a start signal is strobed which sets off the computation. When the solver is done (the magnitude of \(Z\) has escaped), it strobes the outut done (effectively sending an interrupt).

The row solver instantiates a single pixel solver, but provides an additional abstraction. The row solver accepts C_B which is the imaginary component of the row to be operated on. Additionally, it accepts C_A_reference which is the real coordinate of the leftmost pixel in the frame (floating point), C_A_step which is the step size between pixels (floating point), and generates the index C_A_column (10-bit unsigned number). Together, those specify the real component of the point's location by the expression \(C\_A\_reference + C\_A\_step * C\_A\_column\). The row solver uses the VLIW CPU to evaluate that expression to determine the pixel's coordinates, then iterates the given program on that pixel coordinate until the magnitude diverges or the maximum number of iterations is reached.

The Row Solver uses the VLIW CPU to calculate the pixel's coordinate is an optimization which allows using the solver's instantiated adder/multiplier instead of instantiating new ones as resources on the board are in high demand.

The row solver supplies the pixel solver with the necessary inputs, starting at column 0. When the pixel solver throws an exception indicating the magnitude of the iterated equation has escaped the threshold or when the Row Solver determines that the maximum number of iterations has been reached the iteration count and location of the pixel is strobed out from the Row Solver. If the end of the row has not been reached, the Row Solver resets the Pixel Solver and repeats the process for the next pixel. Otherwise, if the end of the row has been reached, then the Row Solver sets its request signal and waits for the grant input to be strobed indicating it should start on the next line.

The frame solver accepts the coordinates of the top left corner of the screen and the step sizes for the real and imaginary axes. The frame solver instantiates row solvers and coordinates the inputs and outputs to/from each. At most one row solver is given a grant in a particular cycle (so it takes at least as cycles to get the row solvers all computing as there are row solvers). On any cycle when at least one row solver's request flag is set high the lowest indexed row solver whose request is high receives a grant and gets assigned an imaginary coordinate corresponding to the row it should start computing. The imaginary coordinate is incremented by the imaginary step size using an adder. If no row solvers are have their request flag set then no action is taken. If the row index exceeds the frame size then it is reset to 0 and the running count of the imaginary coordinate is reset to the initial value (that of the top left corner).

The output of each row solver is fed into a corresponding true dual-ported FIFO. Each time the row solver strobes its output signal the coordinates of the most recently generated pixel and the pixel's value are concatenated and inserted into a FIFO.

On a separate clock domain, the outputs of the FIFOs are arbitrated and used as the outputs of the frame solver. On each clock cycle on the output_clk domain a pixel's coordinates and value may be output; if one is available on that cycle then a strobe signal is set high. FIFOs are emptied with those having lowest index having highest priority. While that is not fair, it doesn't impact the draw time of the solver since the high-indexed solvers will simply be blocked when framebuffer bandwidth is the limiting factor and since solvers are not pre-assigned rows a subsequent change in the cause of the bottleneck would not disproportionately leave some solvers "out of work".

The top level module instantiates a single frame solver and interfaces it with the HPS PIO signals and the VGA framebuffer. The VGA framebuffer is a dual-ported SRAM with one port dedicated to the VGA subsystem and the second exported from QSYS into Verilog. The output interface of the Frame Solver conveniently wires combinationally into the input interface of the SRAM; each time the frame solver's strobe indicating an output is available is wired to the SRAM's write enable and the frame solver's pixel coordinates combinationally determine the address to which the frame solver's iteration count output should be written. This is by design to minimize logic which can't be unit tested in ModelSim (the top level module is the only module not tested in ModelSim, as is discussed later). The SRAM's value is an 8-bit color which is determined by the bottom eight bits of the number of iterations that point took to escape.

The top level module also keeps track of the number of cycles it takes to compute each frame which is passed to the HPS to display in milliseconds on the display.

The top level module also contains the instruction broadcast code which reads the VLIW instructions from SRAM on each cycle and broadcasts it to each of the VLIW processors. This is repeated "blindly" and the processors subscribe/unsubscribe as needed.

QSys was used to connect the HPS and FPGA to registers, clocks, RAMs, etc in a graphical layout. The screenshot below shows the layout used for this project.

I used Haskell's recursive descent parser library Parsec to parse the equations (which lend themselves to recursive descent parsing). The parser reads the equation into the following algebraic data type:

data Exp = Num Int     -- base numeric data
         | Cpx Exp Exp -- complex numbers, real & imaginary components must be Num
         | Var String  -- only 'z' is permitted
         | Add Exp Exp
         | Sub Exp Exp
         | Mul Exp Exp
         | Div Exp Exp
         | Pow Exp Exp
         | Pos Exp
         | Neg Exp
           deriving (Show)

In the example formula above, \(z*z+1i2\), the parser returns this result:

Add (Mul (Var "z") (Var "z")) (Cpx (Num 1) (Num 2))

The parsed expression is then converted into an Intermediate Representation where each node in Exp is translated into one or more Instruction objects.

data Instruction =
  --     SRC1     SRC2     DEST
    Add  Register Register Register
  | Mul  Register Register Register
  --     SRC      DEST
  | Neg  Register Register
  --     Val      DEST
  | Load Int      Register
  --     DEST
  | Var  Register
                 deriving (Show)

The translation to instructions has the below signature, where the output is a Complex (defined type Complex = (Register, Register)) indicating where the result of the computation will be stored, and a list of instructions. The instruction output is a nested list where the first sub-list represents the LATEST instructions to be run. If two instructions could be run concurrently (dependency wise, not hardware wise) then they may exist in the same sub-list. The result is how the program could be executed in the fewest possible number of cycles assuming there were infinite copies of each pipe available in the CPU.

preschedule :: JuliaParser.Exp -> State Int ([[Instruction]], Complex)

The next step is to convert the instructions to cycles, which have a notion of the hardware constraints. There are four fields in Cycle which correspond to the four pipes in the CPU. If a pipe should be starting an instruction in a particular cycle then that instruction should appear in the appropriate field. If no instructions start in a pipe in a cycle then the field is set to Nothing (see Haskell's Maybe monad for a description of how that works). The flattenSchedule function takes the nested-list-of-instructions data and schedules it into a list of Cycles. The key to flattening the 2d instructions into the 1d schedule is the intuition that every instruction appears at the lowest index possible (i.e. running as late as possible chronologically) in the input, but it could certainly be executed earlier as long as all of its inputs are ready (I assume a large register space so there are no collisions). A trivial way to ensure there are no Read After Write dependency violations from scheduling instructions earlier I guarantee all instructions that came earlier than instruction \(I\) in the 2d instruction list have already run by the time \(I\) is executed.

data Cycle = Cycle { load :: Maybe Instruction
                   , add  :: Maybe Instruction
                   , mul  :: Maybe Instruction
                   , neg  :: Maybe Instruction
                   } deriving (Show)

flattenSchedule :: [[Instruction]] -> [Cycle]

[
  Cycle {load = Nothing,          add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 4 5 2),       mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Just (Mul 0 0 4),   neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Just (Mul 1 1 5),   neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 4 522 0),     mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 4 523 1),     mul = Nothing,            neg = Nothing},
  Cycle {load = Just (Load 0 4),  add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 525 20 523),  mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 524 19 522),  mul = Nothing,            neg = Nothing},
  Cycle {load = Just (Load 2 20), add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Just (Load 1 19), add = Nothing,                mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 785 784 525), mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Just (Mul 1 0 785), neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Just (Mul 0 1 784), neg = Nothing},
  Cycle {load = Nothing,          add = Just (Add 274 782 524), mul = Nothing,            neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Nothing,            neg = Just (Neg 783 274)},
  Cycle {load = Nothing,          add = Nothing,                mul = Just (Mul 1 1 783), neg = Nothing},
  Cycle {load = Nothing,          add = Nothing,                mul = Just (Mul 0 0 782), neg = Nothing}
]

The last step of compilation is converting each Cycle to its 121-bit VLIW instruction. Each pipe's instruction is encoded separately in a cycle (see the type signature of encodeLoad below for an example the associated type signature where BV is a BitVector). If an instruction is Nothing in a cycle then the code for a NOP is emitted. An instruction word is created by concatenating the bits together from the individual pipes. The assemble function maps each cycle to the concatenated instructions of the pipes. The last step of the assembler is reversing the list of instructions since until now the lowest-indexed instruction ran last.

encodeLoad :: Maybe IR.Instruction -> BV.BV
assemble :: [IR.Cycle] -> [Word128]

Here is a decimal representation of the list of cycles from our running example:

[
  1073742606,
  1074792207,
  8534579836514498005434368,
  2924556919630725120,
  1073743632,
  1074791185,
  4075231024617881600,
  1329228005872192911768272894028677120,
  1329228015785384632608232126619320320,
  3485829014013083648,
  3488083014997508096,
  0,
  1329227995823601499131475193870942208,
  2316000299778572288,
  2315998098607833088,
  0,
  1074791429,
  1073741828,
  2314861207879680000,
  0,
  0
]