Introduction

Hey there, everyone. I am going to be posting my experiences here as I work through my asynchronous logic design projects. I’m a Computer Engineering undergrad student at Iowa State University. I will try to answer any questions as much as I can, but this is my first try at asynchronous designs, so I won’t have all the answers.

Anyways, thank you for taking a look and I hope you learn something. If you have a request for something, let me know and I can try it. Some things I thought of, but don’t know if people want:

  • VHDL Tutorial
  • Modelsim Tutorial
  • Testing details (how to make the scripts)
Advertisements

I Broke MAVRIC

Last week, I was working on cleaning up some wiring, specifically the wiring providing power to the wheel motors controllers. When it was originally done, we weren’t sure if the length would be changing, so we left them long (about an extra foot on each cable). This meant that they were hanging down under the rover and were generally in the way. We now know that we are not changing the suspension before competition, so I decided to fix the length. It looks much nicer now.

MAVRIC good wiring

Jump to Saturday, we go to start a test drive, power on the rover and hear some clicking/popping sounds. We check all the LEDs and one of the motor controllers is not working. A review of the wiring on the left side of the rover (right in above image) showed that I had plugged a pair of wires in backwards. Now, I’m usually a careful guy, and I did actually attempt to check the wires, I just did so incorrectly (clearly).

Further diagnostics on the motor controller showed that the internal microcontroller was fine, but all the power transistors for the H-bridge were fried. Thankfully, we had spares ordered already.

Events like this are why I usually opt for polarized, grouped connectors for my cables (XT60s are amazing) but sometimes there are external constraints in place. We have a very tight window for those cables to fit through, and it is not possible to push a solid multiple-pin power connector through the window. We are using bullet terminals because they are very close to the size of the wire, and allow the wires to be pushed through individually.

This has reinforced my opinion on polarized connectors as a necessity, and served as an excellent reminder to always check your new/modified thoroughly connections before activating a system. It is especially important to identify things that you are doing in a riskier manner, and check them extra carefully. Know your risks, and watch them carefully.

 

Another MAVRIC Test Drive

More MAVRIC! Today we had another test drive, and got some good footage (some of it is below). We haven’t edited it together or anything yet though. We took the rover out to the Frederiksen Court area north of campus to get some open space. We were able to get up to 0.2 miles (measured with some GPS pins on a phone) with some small buildings in the way before the connection dropped below acceptable levels. We were able to recover the rover from that distance using the antennas, the cameras were just too laggy to drive very well or operate the arm (not currently attached).

As mentioned, we did a range test, with the first sign of degradation at ~0.1 mi, and the rover becoming unusable at ~0.2 mi. This is a little concerning, but workable for most events at competition. We also did some testing of the suspension’s ability to handle rough surfaces, large bumps and hills. The rover was able to climb over curbs (with a little practice) and remained stable over washboard-type terrain (the 6 wheels help out there). The rover was also able to maneuver on uneven ground at significant angles, though it could not climb steep hills. When driving, the camera mast shakes back and forth, even without the main camera mount attached and may need reinforcement. See the videos below for examples (links because I can’t host videos here, sorry).

Washboard: https://iastate.box.com/s/u1s6bgy23gspb59n9qvf1u7amnplxku7

Bigger Bumps: https://iastate.box.com/s/9hk372vl0fm39629aco75z09jwiqpm0d

Angled Terrain: https://iastate.box.com/s/jbldn017uwto6jfl4lh8ngg4cs5f3dxi

Parking Lot Driving (curb at the end): https://iastate.box.com/s/5h1jv6h9ey0yxjjingovo30o6t4byfnu

 

MAVRIC Update

Nothing too big, we had the M2I Kickoff on Tuesday, so hopefully we will be getting some new members coming in. We have several returning members (almost all of the electrical team came back, and most of mechanical). Unfortunately, we took a pretty big hit on science – the team responsible for the soil analysis and scientific presentation. We have 1-2 returning members. If anyone has experience/interest or contacts with experience/interest in soil analysis (focusing on factors that indicate the possibility of life) please contact me.

That’s about it for now, I hope to post more photos and videos eventually. We can’t do test dives right now because the key (a little part that forces the motor shaft and the wheel to rotate together) is missing, and an Allen wrench broke off in a screw. We should have that fixed quickly once the machining lab is open next week.

So, it’s been a while…

I haven’t posted in about a year now. I’m still not really back. I’ve been pouring my time into a Mars rover project that I will be a part of for another year. As the project goes on (we go to competition next summer) I may post things here, I will try to tag them with ‘MAVRIC’ to keep them straight.

My apologies for the very long silence and the lack of asynchronous logic content. I’ll be getting back to it eventually (or that’s the plan). Thanks for bearing with me.

Shifter

Theory

A Shifter takes an array of bits, and shifts them right of left. Numerically, this is like multiplying or dividing by 2 (in the case of binary numbers). Some examples:

Direction Input Shift Amount Output
Right 001001  1 000100
Left 001001  1 010010
Right 001001  2 000010
Left 001001  3 001000

This could be applied to non-binary variables as well (like 3-rail signals) but the exact meaning will be different. There are a few ‘extensions’ to this behavior I’d like to add:

  • Rotation
  • Arithmetic shifting

Rotation allows the bits shifted out one end to be shifted back in the other:

Direction Input Output
Right 1001 1100
Left 1001 0011

Arithmetic shifting treats the shift as a mathematical operation and preserves the sign of the number. It is only valid for right shifts.

Direction Input Output
Right 100(-4) 110(-2)
Right 110(-2) 111(-1)

The sign of a number is represented by leading 1’s in the MSB, so an arithmetic right shift adds 1’s into the leftmost bits, if the number was negative. This is accomplished by shifting in the MSB.

Design

Each shift_amount bit corresponds to a shift of 2^n, where n is the index of the bit. Each constant-size shift can be accomplished with only wiring. As my CprE 381 professor always said, if you have two possible values, the easiest way to pick one is a MUX. So, each shift_amount bit will choose between an unshifted, or 2^n shifted value. By connecting these in layers, we get a shift of any size.

BasicShifter

The un-supplied inputs are 0’s. The first column is controlled by shift_amount(0), the second column is controlled by shift_amount(1).

To change the direction, we add a mux at the beginning that selects a reversed version of the input, let the shifter shift that, then un-reverse it at the end.

To add rotations, we add another input to the MUX’s at the bottom that feeds back from the top, so that the ‘lost’ bits are shifted back in.

basicshifter1.png

To add arithmetic operations, the unassigned inputs in the lower MUX’s are changed from 0 to the MSB of the input. This signal is constant across all the MUX’s it is applied to, so it is generated with a single MUX. On a left shift, the shifted-in value must be 0, so the MUX can only output the MSB when a right arithmetic shift is selected.

Implementation

the VHDL source, using generics to make it work for any number of inputs (even non-powers of 2, btw):

library ieee;
use work.ncl.all;
use ieee.std_logic_1164.all;

entity Shifter is
  generic(NumInputs : integer := 2);
  port(inputs       : in ncl_pair_vector(0 to NumInputs - 1);
       shift_amount : in ncl_pair_vector(0 to clog2(NumInputs) - 1);
       direction    : in ncl_pair;
       rotate       : in ncl_pair;
       logical      : in ncl_pair;
       output       : out ncl_pair_vector(0 to NumInputs - 1));
end Shifter;

architecture structural of Shifter is
  constant NumShiftAmountBits : integer := clog2(NumInputs);
  constant NumRows : integer := clog2(NumInputs);
  
  type RowSignals is array (integer range <>) of ncl_pair_vector(0 to NumInputs - 1);
  
  -- The shifted array at each stage of the shifter.
  signal rows : RowSignals(0 to NumRows);
  
  -- A generated value that is always DATA0 or NULL as appropriate
  signal zero_in : ncl_pair;
  
  -- The third input that is used for either logical or arithmetic operations.
  signal non_rotate_in : ncl_pair;

  signal input_reversed : ncl_pair_vector(0 to NumInputs - 1);
  signal output_reversed : ncl_pair_vector(0 to NumInputs - 1);

begin

  produceDATA0: THmn 
    generic map(M => 1, N => 2)
    port map(inputs(0) => inputs(0).DATA0,
             inputs(1) => inputs(0).DATA1,
             output => zero_in.DATA0);
  
  zero_in.DATA1 <= '0';   msb_in_mux: MUX     generic map(NumInputs => 4)
    port map(iOptions(0) => inputs(NumInputs-1),
             iOptions(1) => zero_in,
             iOptions(2) => zero_in,
             iOptions(3) => zero_in,
             iSel(0) => logical,
             iSel(1) => direction,
             output => non_rotate_in);

  in_bit_flipper: for i in 0 to NumInputs-1 generate
    input_reversed(i) <= inputs(NumInputs-1-i);     directionMux: MUX       generic map(NumInputs => 2)
      port map(iOptions(0) => inputs(i),
               iOptions(1) => input_reversed(i),
               iSel(0) => direction,
               output => rows(0)(i));
  end generate;

--  rows(0) <= inputs;

  rowsloop: for r in 0 to NumRows-1 generate
    columns: for c in 0 to NumInputs-1 generate
      ifstd: if (c + (2**r)) < NumInputs generate         multiplexer: MUX           generic map(NumInputs => 2)
          port map(iOptions(0) => rows(r)(c),
                   iOptions(1) => rows(r)(c + (2**r)),
                   iSel(0) => shift_amount(r),
                   output => rows(r+1)(c));

      end generate;

      ifwrp: if (c + (2**r)) >= NumInputs generate
        multiplexer: MUX
          generic map(NumInputs => 4)
          port map(iOptions(0) => rows(r)(c),
                   iOptions(1) => non_rotate_in,
                   iOptions(2) => rows(r)(c),
                   iOptions(3) => rows(r)((c+(2**r)) mod NumInputs),
                   iSel(0) => shift_amount(r),
                   iSel(1) => rotate,
                   output => rows(r+1)(c));

      end generate;
    end generate;
  end generate;

  out_bit_flipper: for i in 0 to NumInputs-1 generate
    output_reversed(i) <= rows(NumRows)(NumInputs - 1 - i);     outMux: MUX       generic map(NumInputs => 2)
      port map(iOptions(0) => rows(NumRows)(i),
               iOptions(1) => output_reversed(i),
               iSel(0) => direction,
               output => output(i));
  end generate;

end structural;

This code generates the necessary multiplexers for shifting the signal, flipping it at the input and output, and selecting how to handle the bits that can’t be shifted normally (because the source is out of range).

Testing

I made a simple test script to run through some cases. Everything seems to check out, here’s a sample:

Capture

Commit: 53d34cf, ef416eb

Null Convention Logic Signals II

Background

My naming conventions have probably been misleading. I have mostly treated NCL bits as three-state logic (NULL, DATA0, and DATA1) this is a valid way to work with the data, but it is limiting. The better way to think of it is as individual 2-state logic lines (NULL and DATA).

Internally to a component, using single-rail signals is very helpful. Not only are single-rail signals the inputs to all NCL gates, but they can be used as links between components as well. Single-rail signals cannot really be passed through registers because they have to be asserted for the DATA wave to read as complete. This would prevent the signal from conveying meaning, as it would always have the same value during computations.

My Theory

This section is unverified theory. Please share your thoughts below.

I will b using _ to refer to a non-asserted rail (null) and ^ to refer to an asserted rail (data).

Another benefit of this view is that you get more flexibility in state encodings. Standard encodings (that I’ve come across) use mutually exclusive data lines. So a 3-rail signal would have 3 possible states and a 4-rail signal would have 4 states. By thinking of the data more in terms of DATA and NULL, you get to design your own state encodings. For example, with a 4-rail encoding, you could use the following 6 states: {__^^, _^_^, _^^_, ^__^, ^_^_, ^^__}.

State Space Restrictions

A state space is the set of valid states. We will use it here a little more specifically to refer to the valid DATA states. Not all state spaces will actually work for NCL, The completion logic has to be able to correctly identify completed states. For example, if we try to use the following for a 3-rail signal, we have a problem: {__^, _^^, ^^^}. If the result is the last state (^^^) and the data on line 0 arrives first, the completion logic will see it as a complete __^ and pass on the wrong result.

For any state, it has to be able to partially arrive, without looking like another state. This is required for delay insensitivity. A simple way to make this happen is to use M-hot states. By that I mean that each state will have the same number of rails asserted as data (^), and all such states can be used. The number of states in such an assignment for a N-rail signal is M Choose N or C(M, N). This has its maximum value when M=N/2. It also has the benefit that any incomplete state has at most M-1 rails set, which will never match another state.

The logic proof-y version: ∀x,y∈S:(x&y!=x) and (x&y!=y) must hold (& is the bitwise AND operator) where S is the state space.

Using this N/2-hot encoding, the states/rail is

Rails States State Increase Factor
1 1
2 2 2
3 3 1.5
4 6 2
5 10 1.6667
6 20 2

Using this encoding, you get nearly twice as many states for each rail you add. Using mutually-exclusive rails (1-hot) you get 1 extra state per rail. Even if you break it up into 2-rail pairs and use combinations of those values, you only double your state space for every 2 rails you add. In the table above, s you increase the number of rails, the factor approaches 2 for the odd numbers of rails as well.

In special cases, you might want a more complex encoding, some examples of valid state spaces:

  • {___^, ^_^_, _^__}
  • {__^^, ^___, _^__}
  • {^^^_, ^^_^, ^_^^, _^^^}
  • {^^^_, ___^}
  • {__^^, _^_^, _^^_, ^__^, ^_^_, ^^__}

Takeaway

While you can increase the compatibility of your modules by using a standard state space, sometimes you can reduce the number of rails by using more dense encodings. Additionally, signals that exist only between registers (are not passed on) can actually be 1-rail signals, which is something I have a hard time remembering when integrating components. These 1-rail signals can act as enable signals: They can be used to prevent data from propagating, or to allow it to propagate (remember steering).

Steering

Problem

In Null Convention Logic, all computation is done with oscillating DATA/NULL cycles. The NULL cycles clear the whole circuit, the DATA cycles perform the computation. This requires 2 transition sets per computation (Previous DATA => NULL => Next DATA). Sometimes the DATA output from a component will not be used (think the unselected inputs of a MUX).

Solution

When using steering, the DATA wavefront is only passed to the necessary components. In the case of a MUX, the outputs of these components are then combined as needed with TH1n gates:

Steering

The TH22 gates in this example do not allow the DATA wavefront to apss into the components unless they are selected by the DMUX1. During any particular DATA wavefront, only one of these components will be active at a time; the other component will remain NULL. This saves transitions, and thus power. This method also works if only some, or no inputs are shared.

Details

The DMUX1 component is a decoder, that only outputs the DATA1 lines. Technically, I think it matches the NCL network criteria, if you consider the outputs to be single rail outputs, which have only one DATA value. The DMUX1 is used to enable only the selected component.

We will use steering when our ALU has more than just the Adder with glue logic. At some point we’ll have a multiplier, and a shifter, only one of these will operate at a time.

For more on steering, see Karl Fant’s site. His blog posts have lots of good theory too.

NCL Arithmetic Logic Unit – ADD/SUB

Theory

An arithmetic logic unit (ALU) is a component that performs operations on (usually) two or more sets of inputs, and outputs results. The operation performed is designated by an Operation signal.

Design

Our ALU will start simple, and we’ll add more operations over time. First, let’s build an add/sub unit. I already have an adder, which can be used to subtract by swapping some signals: In single-rail (standard) logic, to subtract instead of add, the second input to the adder is inverted and the carry bit is set – in NCL, we invert the input by swapping DATA0 and DATA1.

The swapper operates as the following equations

output.0 = input.0*swap.0 + input.1*swap.1
output.1 = input.1*swap.0 + input.0*swap.1

These can be implemented with THxor0 gates:

output.0 = THxor0(input.0, swap.0, input.1, swap.1)
output.1 = THxor0(input.1, swap.0, input.0, swap.1)

Our add/sub module will have these on every bit on input to the adder, with iC having the swap signal fed directly into it. Swap will be exposed in the component’s port as the add/subtract selector:

Add_Sub

Green is iA, blue is iB, and red is iC on the Adder. If Control is asserted (DATA1) iB will be inverted and the carry in will be asserted as well, resulting in subtraction.

This module actually fulfills the interface of an ALU by itself, it has data inputs, and a opcode. When we add more operations, we’ll wrap it all up in a ALU block and add a MUX.

Implementation

To implement this in VHDL, we need 1 Adder module and 2*N THxor0 gates:

use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.ncl.all;

entity AddSub is
  generic(NumBits : integer := 4);
  port(iA        : in ncl_pair_vector(0 to NumBits-1);
       iB        : in ncl_pair_vector(0 to NumBits-1);
       Operation : in ncl_pair;

       oS       : out ncl_pair_vector(0 to NumBits-1);
       oC       : out ncl_pair);
end AddSub;

architecture structural of AddSub is

  -- iB into adder, potentially inverted from entity input
  signal adder_iB : ncl_pair_vector(0 to NumBits-1);

begin

  plainAdder: Adder
    generic map(NumAdderBits => NumBits)
    port map(iC => Operation,
             iA => iA,
             iB => adder_iB,
             oS => oS,
             oC => oC);

  bits: for iBit in 0 to NumBits-1 generate

    inverter0: THxor0 -- DATA0, Potentially inverted
      port map(A => iB(iBit).DATA0,
               B => Operation.DATA0,
               C => iB(iBit).DATA1,
               D => Operation.DATA1,
               output => adder_iB(iBit).DATA0);

    inverter1: THxor0 -- DATA1, Potentially inverted
      port map(A => iB(iBit).DATA0,
               B => Operation.DATA1,
               C => iB(iBit).DATA1,
               D => Operation.DATA0,
               output => adder_iB(iBit).DATA1);

  end generate;

end structural;

Testing

AddSub-2bit

The 2-bit case above is a little small, but it runs quickly. I have tested the module up to 6 bits. To change the number of bits, change the number at the top of the test script. The first several cases (interpreted to decimal):

  1. 0+0=0
  2. 0-0=0
  3. 0+1=1
  4. 0-1=-1
  5. 0+2=2
  6. 0-2=-2

This test script does check the sum output, but it does not verify the carry out.

Commit: 55d8c9f

Register Ring with Multiple Wavefronts

In this post, we built a ring of registers and set a data wavefront loose in it. We added many stages, and watched the single wavefront run through them. In this post, I’ll show what happens with multiple wavefronts.

Theory

First, we should establish how many registers we need for some number of wavefronts. From the Register Ring post, we know that in order for a state (DATA or NULL) to pass on, the next two stages must both be in the opposite state. This prevents the passage from overwriting the next stage’s state completely, as it has already passed on to the next stage.

Slide7

Here, the DATA state (red) can move on to the next stage because the NULL state has been passed up to the 3rd stage. By overwriting the 2nd stage, no state is lost, because stage 2 has already finished with the NULL state.

Slide2

Here, stage 2 cannot pass DATA on to stage 3 because that would remove the NULL state entirely. If there were 4 stages, and the 4th was NULL, then the 3rd stage could accept data, since the NULL state would be preserved.

As you can see, the number of stages in a state is not important, but rather the sequence must be preserved. Let’s assume a really long line of registers for a moment, with stage states: (DATA, NULL, NULL, DATA, ...) All of these NULLs can be assumed to be the same logical state, which we’ll refer to as NULL1, we’ll also call the first DATA state DATA1: ​(DATA1, NULL1, NULL1, DATA0, ...). Take the case where the last DATA wave can’t move because of some really slow stage after it. If we ‘run’ the system for a register delay, the DATA1 state progresses, and overwrites one of the NULL1 states, but there are still some left, so nothing is really lost. When DATA1 moves forward, a NULL state fills its stage; this is a new state, so let’s call it NULL2(NULL2, DATA1, NULL1, DATA0, ...). If we run again, one might expect the DATA1 state to advance again, but taht would overwrite the NULL1 state completely, putting two distinct DATA states right next to each other. Having two adjacent DATA states prevents the components from resetting between them, which only produces correct results if the DATA states are identical. Since there is no guarantee that DATA1 and DATA0 are identical, we have to preserve the NULL between them.

There are states which would be deadlocked, however, as long as the initial conditions are valid (not deadlocked), the handshaking ensures that these states never occur as a propagation of the circuit.

Some examples:

  • Ring: (NULL, DATA, NULL, DATA) (4 states) – Nothing can pass, the system is deadlocked (we can’t actually get here naturally)
  • Ring: (NULL, DATA, NULL, NULL) (2 states) – Only the DATA state can pass, the NULLs are contiguous, so they can be considered to be identical states
  • Ring: (NULL, DATA, DATA, NULL) (2 states) – Both states can pass, the DATA can overwrite the NULL in position 4, and the NULL can overwrite the DATA in position 2
  • Ring: (NULL, DATA, DATA, DATA) (2 states) – Only NULL can pass, if DATA was able to pass, the NULL could be deleted from the system
  • Ring: (NULL, NULL, DATA, NULL) (2 states) – Only DATA can pass, if NULL was able to pass, the DATA could be deleted from the system
  • Rotations of these work out to the same thing since it’s a ring

Note that DATA and NULL are symmetric and the values in the DATA wave don’t matter. You can swap instances of ‘NULL’ and ‘DATA’ and get a valid result.

In short, with an even number of stages, you can only have N/2 states. What about odd numbers?

  • Ring: (NULL, DATA, NULL, NULL, DATA) (4 states) – Only the first DATA can move, as it is the only stage followed by 2 of the opposite state
  • Ring: (NULL, DATA, DATA, NULL, DATA) (4 states) – Only the first NULL can move, as it is the only stage followed by 2 of the opposite state

Remember that rotations still match

  • Ring: (NULL, DATA, NULL, NULL, NULL) (2 states) – Only the first DATA can move, as it is the only stage followed by 2 of the opposite state
  • Ring: (NULL, DATA, DATA, NULL, NULL) (2 states) – Either state can move
    • Ring: (NULL, DATA, DATA, DATA, NULL) (2 states) – Either state can still move
    • Ring: (NULL, NULL, DATA, NULL, NULL) (2 states) – Only DATA can move

In the odd case, we can get up to (N+1)/2 states to fit. One thing to note is that when the pipeline is full (max number of states) only one state can move at a time in the odd case. In the even case, there’s that extra space that doesn’t get us another state, but it does give the states some wiggle room: more than one state can be advancing at a time.

From the above, we get: NumStages=NumStates+Advancement where Advancement is the maximum number of states that can advance at a time. Advancement must be greater than 0, if it equals 0, the pipeline will be locked. If Advancement>=NumStates then there’s no real advantage to adding more stages, unless the stages are not delay-matched.

Note: NumStates is always even in a ring.

Experiment

We’ll start with a full pipeline (Advancement=1) and then try a throughput-optimized design (Advancement=NumStates) where every state can advance simultaneously. By using the same number of states, we can benchmark the throughput and latency of the two.

Lest use NumStates:=4, which corresponds to 2 NULL and 2 DATA states.

Minimized Pipeline

By our formula above, we need 4+1=5 stages. The initial state:

5-stage-pipeline.png

By putting the value of 0 in the first DATA state, and 1 in the second state, we can track when the ring completes a cycle. Throughput is 2/t_complete (two DATA states per trip around the ring) and latency is t_complete.

5-stage-4-state
5-stage ring with 2 DATA states and 2 NULL states
  • Throughput: 1/(400 ns) = 2.5 MHz
  • Latency: 800 ns

This experiment used the static_loop VHDL file, and a specific test script.

Throughput-Optimized Pipeline

This version has 4+4=8 stages to go through, but all the states can move at the same time. Throughput should increase, but latency may increase as well. I’m not going to show the diagram because of size problems, but it’s a lot like the above, just with more stages.

Throughput and latency are calculated from the simulation, just as before. For optimal throughput and startup latency, arrange the states in pairs – 2 DATA, then 2 NULL, then 2 DATA, … – this increases the number of Advancement options at the start to the maximum: NumStates.

8-stage-4-state
An 8-stage ring with 2 DATA states and 2 NULL states
  • Throughput: 1/(160 ns) = 6.25 MHz
  • Latency: 320 ns

This experiment used the static_loop VHDL file, and a specific test script.

Results

It looks like the throughput-optimized pipeline indeed has a higher throughput: By adding 3 states, we were able to more than double the efficiency of the ring, if you look at the simulation waveforms, in the first one only one stage is transitioning at a time. In the second, 4 stages are transitioning at a time. The second (faster) version uses 8/5 the resources though, so the decision on how many stages to use depends on available die space as well. In simulation, we don’t have to worry about this.

Commits: 997b4bb, be37b7f, 20ddd65