Skip to content

philiprbrenan/com.AppaApps.Silicon

Repository files navigation

Silicon chip

Design, simulate and layout a B-Tree on a Silicon chip. Reasons why you might want to join this project:

http://prb.appaapps.com/zesal/pitchdeck/pitchDeck.html

Or you might want to design your own RiscV machine and operating system to run on it.

Files

Ban   - RiscV 32I Cpu on a silicon chip.
Chip  - Toolkit to design, simulate and layout the register transfer level code needed to create a binary tree on a silicon chip.
Mjaf  - Java implementation of the Btree algorithm with data stored only in the leaves to simplify deletion.
RiscV - Assemble and execute Risc V machine code using the little endian RV32I subset of RiscV.
Stuck - A fixed size stack of ordered keys used for implementing nodes of the Btree.
Unary - Unary arithmetic using boolean arrays used to control a fixed size Stack for each node of the Btree.

Examples

And

Create a chip that ands two input pins together and places the result on the output pin.

    Chip c = new Chip("And");
    Gate i = c.Input ("i");
    Gate I = c.Input ("I");
    Gate a = c.And   ("a", i, I);
    Gate o = c.Output("o", a);

    Inputs inputs = c.new Inputs().set(i, true).set(I, false);

    c.simulate(inputs);

    c.draw();

    i.ok(true);
    I.ok(false);
    a.ok(false);
    o.ok(false);
    ok(c.steps, 3);

draw() draws a layout mask for the chip using Graphics Design System 2:

And

Compare Greater Than

Compare two unsigned 4 bit integers to check whether the first is greater than the second.

Compare Greater Than

Choose Word Under Mask

Use a mask to choose one word from an array of words:

Choose Word Under Mask

Btree Node Compare

Locate the data associated with a database key in the node of a B-Tree: Btree Leaf Compare

Btree

A complete B-Tree: Btree

Gates

A chip is built at the Register Transfer Level out of standard Boolean logic gates. Each gate produces a bit value that can be used to drive one input pin of another gate or one output pin. Each input pin of each gate can only be driven by one output pin of a gate. To allow one gate output pin to drive several input pins, each gate produces two copies of its output bit enabling the construction of equal depth fan out trees. Some gate types such as or and and can have as many input pins as requested. The remaining gate types have no more than two input pins.

Signal fan in and out

The underlying chip is built up out of Register Transfer Level Boolean gates that have two inputs and one output and a copy of the output giving two input pins and two output pins per gate. One output pin can drive just one input pin via a connecting wire.

There has to be a limit on how many input pins an output pin can drive otherwise we could have situations in which one output pin was driving millions of input pins which would require so much current that the output pin would fuse.

When we request an and gate (for example), we might code:

A = And("A", b, c, d, e)

i.e. we might provide more than two inputs b .. e. Internally, such gates are broken down into a tree of AND gates, see: fanIn in Chip.java.

Also, we might appear to allow one output pin to drive more than one input pin, but internally this is replaced by a tree of fan outs, see: fanOut in Chip.java.

The fan in and fan out trees are carefully arranged to ensure that the number of steps from the root to each leaf is the same along every path so that the fanned signal converges or diverges at the same rate leading to the same signal delay along each line of propagation. The alternative would have been to allow the signals to diverge as they propagate, but this makes debugging very difficult.

So, logically, you can have as many inputs and outputs as you need for each Register Transfer Level Boolean gate, but at the cost of a log(N) delay where N is the number of bits to be fanned in or out.

Buses

The single bits transferred by connections between gates can be aggregated into a bit bus allowing the bits to be manipulated en mass.

A bit bus behaves like a variable or like an array of variables .

Bit buses

A bit bus corresponds to a variable .

25 Bit buses
Bits  Bus_____________________________  Value
   3                            data_1  1
   3                            data_2  3
   3                            data_3  5
   3                            enable  7
   3                              find  4
   3                            keys_1  2
   3                            keys_2  4
   3                            keys_3  6
   3                            next_1  1
   3                            next_2  3
   3                            next_3  5
   3                     out_dataFound  3
   3                    out_dataFound1  3
   3                    out_dataFound2  3
   3                            out_id  7
   3                     out_maskEqual  2
   3                      out_maskMore  4
   3                     out_moreFound  5
   3                      out_nextLink  0
   3                     out_nextLink1  0
   3                     out_nextLink2  0
   3                     out_nextLink3  5
   3                     out_nextLink4  5
   3                     out_pointMore  4
   3                               top  7

Words buses

A word bit bus correspond to an array of variables .


3 Word buses
Words Bits  Bus_____________________________
   3     3                              data  1, 3, 5
   3     3                              keys  2, 4, 6
   3     3                              next  1, 3, 5

Structured programming

If/Then/Else statements

In parallel processing both the then and else clauses will be executed in parallel, simultaneously, regardless of the value of the if condition. But we can then and the condition with the results of each clause and or these results together to consolidate the results and make subsequent processing dependent on just one branch. In effect we are converting conventional code:

if (c)
  result = 1
else
  result = 2

to parallel code where & means run in parallel:

(a = 1 & b = 2 & C = not c)

result = (a and c) or (b and C);

This is essentially the technique used in chooseThenElseIfEQ in Chip.java.

Switch/Case statements

Use a ladder of if statements, which is the method used to implement: chooseEq in Chip.java.

For loops

Often a for loop can be unrolled because we know how many iterations there will be in advance.

For example to sum the square roots of the 10 elements of array a we might write:

count = 0;
for(i = 1; i <= 10; ++i)
  count += sqrt(a[i]);

But we could just as well unroll the loop and write:

0+sqrt(a[1])+sqrt(sqrt(a[2])+sqrt(a[3])+ ... sqrt(a[10])

We can generate this code by writing:

String s  = "0"
for(i = 1; i <= 10; ++i)
  s  += "+sqrt(a["+i+"])"
print(s)

// 0+sqrt(a[1])+sqrt(sqrt(a[2])+ ... sqrt(a[10])

If you need to generate names of variables inside the loop body, use a name plus an index, as in:

n(i, "a")

which will generate names like: a_1, a_2, a_3 ... which can be used in expressions as needed.

The gcc compiler uses the same technique when you specify -O3 requesting code optimized for speed because it eliminates the overhead of maintaining and checking the index variable i which can be significant on tight loops.

If the number of iterations is unknown in advance, or the generated code would be too large, you either have to use a pulse and a register to save results and coordinate reuse of the Silicon - difficult - see test_fibonacci in Chip.java - or go up to the RiscV layer, see RiscV.java and write it in conventional, but much slower, assembler code. I.e. one can do addition in software or hardware. Our goal is to do as much as possible in hardware with the goal of producing a database system on a chip that is much faster and more power efficient than any-one else's because they are all written in software.

Subroutines

There are no subroutines at the Register Transfer Level . All notional subroutines have to be inlined. This precludes the use of recursion. However, there is nothing stopping you from using subroutines, with or without recursion, at the Java level to generate the Register Transfer Level code needed to implement an algorithm.

And you can also use for loops to reuse code to obtain a similar effect to calling a subroutine.

Diagnostics

Trace

Execution traces show how the state of the chip evolves over time.

   {final int N = 16;
    Chip      c = chip ();
    Bits      p = c.bits("p", N);
    for (int i  = 1; i <= N; i++)
      c.pulse(p.b(i).name).period(N).delay(i-1).b();

    c.executionTrace = c.new Trace("p")
     {String trace() {return String.format("%s", p);}
     };

    c.simulationSteps(20);
    c.simulate();
    //c.printExecutionTrace(); stop();

    c.ok("""
Step  p
   1  0x1
   2  0x2
   3  0x4
   4  0x8
   5  0x10
   6  0x20
   7  0x40
   8  0x80
   9  0x100
  10  0x200
  11  0x400
  12  0x800
  13  0x1000
  14  0x2000
  15  0x4000
  16  0x8000
  17  0x1
  18  0x2
  19  0x4
  20  0x8
""");

State

Use the say(Chip s) method to print the current state of the chip:

Chip: binary_add  Step: 5 # Gates: 70  Maximum distance: 7  MostCountedDistance: 4  CountAtMostCountedDistance: 16
Seq   Name____________________________ S  Operator  #  11111111111111111111111111111111=#  22222222222222222222222222222222=# Chng Fell Frst Last  Dist                           Nearest  Px__,Py__  Drives these gates
  48                                co      Output  1                        ij_carry_2=1                                  =.    5    0     0    0     0                                co     0,   0
   1                               i_1        Zero  0                                  =.                                  =.    1    0     0    0     3               ij_not_in1_1_anneal     0,   0  i_1_f_1, i_1_f_2
  49                           i_1_f_1      FanOut  0                               i_1=0                                  =.    1    0     0    0     2                               o_2     0,   0  ij_1, ij_carry_1
  50                           i_1_f_2      FanOut  0                               i_1=0                                  =.    1    0     0    0     2               ij_not_in1_1_anneal     0,   0  ij_not_in1_1
   2                               i_2         One  1                                  =.                                  =.    1    0     0    0     6                                co     0,   0  i_2_f_1, i_2_f_2
  51                           i_2_f_1      FanOut  1                               i_2=1                                  =.    1    0     0    0     6                                co     0,   0  i_2_f_1_f_1, i_2_f_1_f_2
  53                       i_2_f_1_f_1      FanOut  1                           i_2_f_1=1                                  =.    1    0     0    0     5                                co     0,   0  ij_carry_2_4_F_1, ij_carry_2_7_F_1
  54                       i_2_f_1_f_2      FanOut  1                           i_2_f_1=1                                  =.    1    0     0    0     5                               o_2     0,   0  ij_carry_2_8_F_1, ij_not_in1_2
  52                           i_2_f_2      FanOut  1                               i_2=1                                  =.    1    0     0    0     5                               o_2     0,   0  ij_result_2_3_F_1, ij_result_2_8_F_1
  11                              ij_1         Xor  1                           i_1_f_1=0                           j_1_f_1=1    2    0     0    0     1                               o_1     0,   0  o_1
  30                              ij_2          Or  0                          ij_2_F_1=0                          ij_2_F_2=0    5    0     0    0     1                               o_2     0,   0  o_2
  28                          ij_2_F_1          Or  0                     ij_result_2_2=0                     ij_result_2_3=0    4    0     0    0     2                               o_2     0,   0  ij_2
  29                          ij_2_F_2          Or  0                     ij_result_2_5=0                     ij_result_2_8=0    3    0     0    0     2                               o_2     0,   0  ij_2
  12                        ij_carry_1         And  0                           i_1_f_1=0                           j_1_f_1=1    1    0     0    0     6                                co     0,   0  ij_carry_1_f_1, ij_carry_1_f_2
  55                    ij_carry_1_f_1      FanOut  0                        ij_carry_1=0                                  =.    1    0     0    0     6                                co     0,   0  ij_carry_1_f_1_f_1, ij_carry_1_f_1_f_2
  57                ij_carry_1_f_1_f_1      FanOut  0                    ij_carry_1_f_1=0                                  =.    1    0     0    0     5                                co     0,   0  ij_carry_2_6_F_1, ij_carry_2_7_F_1
  58                ij_carry_1_f_1_f_2      FanOut  0                    ij_carry_1_f_1=0                                  =.    1    0     0    0     5                               o_2     0,   0  ij_carry_2_8_F_1, ij_not_carry_1
  56                    ij_carry_1_f_2      FanOut  0                        ij_carry_1=0                                  =.    1    0     0    0     5                               o_2     0,   0  ij_result_2_5_F_1, ij_result_2_8_F_1
  45                        ij_carry_2          Or  1                    ij_carry_2_F_1=1                    ij_carry_2_F_2=0    4    0     0    0     1             ij_not_carry_2_anneal     0,   0  co, ij_not_carry_2
  33                      ij_carry_2_4         And  1                  ij_carry_2_4_F_1=1                  ij_carry_2_4_F_2=1    3    0     0    0     3                                co     0,   0  ij_carry_2_F_1
  31                  ij_carry_2_4_F_1         And  1                       i_2_f_1_f_1=1                ij_not_carry_1_f_1=1    2    0     0    0     4                                co     0,   0  ij_carry_2_4
  32                  ij_carry_2_4_F_2    Continue  1                       j_2_f_1_f_1=1                                  =.    2    0     0    0     4                                co     0,   0  ij_carry_2_4
  36                      ij_carry_2_6         And  0                  ij_carry_2_6_F_1=0                  ij_carry_2_6_F_2=1    2    0     0    0     3                                co     0,   0  ij_carry_2_F_1
  34                  ij_carry_2_6_F_1         And  0                ij_carry_1_f_1_f_1=0                  ij_not_in1_2_f_1=0    1    0     0    0     4                                co     0,   0  ij_carry_2_6
  35                  ij_carry_2_6_F_2    Continue  1                       j_2_f_1_f_1=1                                  =.    2    0     0    0     4                                co     0,   0  ij_carry_2_6
  39                      ij_carry_2_7         And  0                  ij_carry_2_7_F_1=0                  ij_carry_2_7_F_2=0    2    0     0    0     3                                co     0,   0  ij_carry_2_F_2
  37                  ij_carry_2_7_F_1         And  0                       i_2_f_1_f_1=1                ij_carry_1_f_1_f_1=0    1    0     0    0     4                                co     0,   0  ij_carry_2_7
  38                  ij_carry_2_7_F_2    Continue  0                  ij_not_in2_2_f_1=0                                  =.    3    0     0    0     4                                co     0,   0  ij_carry_2_7
  42                      ij_carry_2_8         And  0                  ij_carry_2_8_F_1=0                  ij_carry_2_8_F_2=1    2    0     0    0     3                                co     0,   0  ij_carry_2_F_2
  40                  ij_carry_2_8_F_1         And  0                       i_2_f_1_f_2=1                ij_carry_1_f_1_f_2=0    1    0     0    0     4                                co     0,   0  ij_carry_2_8
  41                  ij_carry_2_8_F_2    Continue  1                       j_2_f_1_f_2=1                                  =.    2    0     0    0     4                                co     0,   0  ij_carry_2_8
  43                    ij_carry_2_F_1          Or  1                      ij_carry_2_4=1                      ij_carry_2_6=0    3    0     0    0     2                                co     0,   0  ij_carry_2
  44                    ij_carry_2_F_2          Or  0                      ij_carry_2_7=0                      ij_carry_2_8=0    2    0     0    0     2                                co     0,   0  ij_carry_2
   5                    ij_not_carry_1         Not  1                ij_carry_1_f_1_f_2=0                                  =.    1    0     0    0     6                               o_2     0,   0  ij_not_carry_1_f_1, ij_not_carry_1_f_2
  59                ij_not_carry_1_f_1      FanOut  1                    ij_not_carry_1=1                                  =.    1    0     0    0     5                               o_2     0,   0  ij_carry_2_4_F_1, ij_result_2_2_F_1
  60                ij_not_carry_1_f_2      FanOut  1                    ij_not_carry_1=1                                  =.    1    0     0    0     5                               o_2     0,   0  ij_result_2_3_F_1
   6                    ij_not_carry_2         Not  0                        ij_carry_2=1                                  =.    4    0     0    0     1             ij_not_carry_2_anneal     0,   0  ij_not_carry_2_anneal
  15             ij_not_carry_2_anneal      Output  0                    ij_not_carry_2=0                                  =.    4    0     0    0     0             ij_not_carry_2_anneal     0,   0
   7                      ij_not_in1_1         Not  1                           i_1_f_2=0                                  =.    1    0     0    0     1               ij_not_in1_1_anneal     0,   0  ij_not_in1_1_anneal
  13               ij_not_in1_1_anneal      Output  1                      ij_not_in1_1=1                                  =.    1    0     0    0     0               ij_not_in1_1_anneal     0,   0
   8                      ij_not_in1_2         Not  0                       i_2_f_1_f_2=1                                  =.    1    0     0    0     6                               o_2     0,   0  ij_not_in1_2_f_1, ij_not_in1_2_f_2
  61                  ij_not_in1_2_f_1      FanOut  0                      ij_not_in1_2=0                                  =.    1    0     0    0     5                               o_2     0,   0  ij_carry_2_6_F_1, ij_result_2_2_F_1
  62                  ij_not_in1_2_f_2      FanOut  0                      ij_not_in1_2=0                                  =.    1    0     0    0     5                               o_2     0,   0  ij_result_2_5_F_1
   9                      ij_not_in2_1         Not  0                           j_1_f_2=1                                  =.    2    0     0    0     1               ij_not_in2_1_anneal     0,   0  ij_not_in2_1_anneal
  14               ij_not_in2_1_anneal      Output  0                      ij_not_in2_1=0                                  =.    2    0     0    0     0               ij_not_in2_1_anneal     0,   0
  10                      ij_not_in2_2         Not  0                       j_2_f_1_f_2=1                                  =.    2    0     0    0     6                               o_2     0,   0  ij_not_in2_2_f_1, ij_not_in2_2_f_2
  63                  ij_not_in2_2_f_1      FanOut  0                      ij_not_in2_2=0                                  =.    2    0     0    0     5                               o_2     0,   0  ij_carry_2_7_F_2, ij_result_2_3_F_2
  64                  ij_not_in2_2_f_2      FanOut  0                      ij_not_in2_2=0                                  =.    2    0     0    0     5                               o_2     0,   0  ij_result_2_5_F_2
  18                     ij_result_2_2         And  0                 ij_result_2_2_F_1=0                 ij_result_2_2_F_2=1    2    0     0    0     3                               o_2     0,   0  ij_2_F_1
  16                 ij_result_2_2_F_1         And  0                ij_not_carry_1_f_1=1                  ij_not_in1_2_f_1=0    1    0     0    0     4                               o_2     0,   0  ij_result_2_2
  17                 ij_result_2_2_F_2    Continue  1                           j_2_f_2=1                                  =.    2    0     0    0     4                               o_2     0,   0  ij_result_2_2
  21                     ij_result_2_3         And  0                 ij_result_2_3_F_1=1                 ij_result_2_3_F_2=0    3    0     0    0     3                               o_2     0,   0  ij_2_F_1
  19                 ij_result_2_3_F_1         And  1                           i_2_f_2=1                ij_not_carry_1_f_2=1    1    0     0    0     4                               o_2     0,   0  ij_result_2_3
  20                 ij_result_2_3_F_2    Continue  0                  ij_not_in2_2_f_1=0                                  =.    2    0     0    0     4                               o_2     0,   0  ij_result_2_3
  24                     ij_result_2_5         And  0                 ij_result_2_5_F_1=0                 ij_result_2_5_F_2=0    2    0     0    0     3                               o_2     0,   0  ij_2_F_2
  22                 ij_result_2_5_F_1         And  0                    ij_carry_1_f_2=0                  ij_not_in1_2_f_2=0    1    0     0    0     4                               o_2     0,   0  ij_result_2_5
  23                 ij_result_2_5_F_2    Continue  0                  ij_not_in2_2_f_2=0                                  =.    2    0     0    0     4                               o_2     0,   0  ij_result_2_5
  27                     ij_result_2_8         And  0                 ij_result_2_8_F_1=0                 ij_result_2_8_F_2=1    2    0     0    0     3                               o_2     0,   0  ij_2_F_2
  25                 ij_result_2_8_F_1         And  0                           i_2_f_2=1                    ij_carry_1_f_2=0    1    0     0    0     4                               o_2     0,   0  ij_result_2_8
  26                 ij_result_2_8_F_2    Continue  1                           j_2_f_2=1                                  =.    2    0     0    0     4                               o_2     0,   0  ij_result_2_8
   3                               j_1         One  1                                  =.                                  =.    1    0     0    0     3               ij_not_in2_1_anneal     0,   0  j_1_f_1, j_1_f_2
  65                           j_1_f_1      FanOut  1                               j_1=1                                  =.    1    0     0    0     2                               o_2     0,   0  ij_1, ij_carry_1
  66                           j_1_f_2      FanOut  1                               j_1=1                                  =.    1    0     0    0     2               ij_not_in2_1_anneal     0,   0  ij_not_in2_1
   4                               j_2         One  1                                  =.                                  =.    1    0     0    0     6                                co     0,   0  j_2_f_1, j_2_f_2
  67                           j_2_f_1      FanOut  1                               j_2=1                                  =.    1    0     0    0     6                                co     0,   0  j_2_f_1_f_1, j_2_f_1_f_2
  69                       j_2_f_1_f_1      FanOut  1                           j_2_f_1=1                                  =.    1    0     0    0     5                                co     0,   0  ij_carry_2_4_F_2, ij_carry_2_6_F_2
  70                       j_2_f_1_f_2      FanOut  1                           j_2_f_1=1                                  =.    1    0     0    0     5                               o_2     0,   0  ij_carry_2_8_F_2, ij_not_in2_2
  68                           j_2_f_2      FanOut  1                               j_2=1                                  =.    1    0     0    0     5                               o_2     0,   0  ij_result_2_2_F_2, ij_result_2_8_F_2
  46                               o_1      Output  1                              ij_1=1                                  =.    2    0     0    0     0                               o_1     0,   0
  47                               o_2      Output  0                              ij_2=0                                  =.    5    0     0    0     0                               o_2     0,   0
8 Bit buses
Bits  Bus_____________________________  Value
   2                                 i  2
   2                                ij  1
   2                          ij_carry  2
   2                      ij_not_carry  1
   2                        ij_not_in1  1
   2                        ij_not_in2  0
   2                                 j  3
   2                                 o  1

Modified: 2024-07-30 at 04:47:42

Modified: 2024-08-01 at 19:53:14