An implementation of the B-Tree algorithm in synthesized, placed and routed Verilog targeted at a Advanced Micro Devices XC7Z020 Field Programmable Gate Array .
For reasons why you might want to get involved in this implementation of the B-Tree algorithm in Silicon rather than software see:
https://prb.appaapps.com/zesal/presentation/index.html
A more detailed presentation:
http://prb.appaapps.com/zesal/pitchdeck/pitchDeck.html
See this action.
The B-Tree algorithm has been implemented in normal Java, then successively
reduced until it looked just like assembler code, at which point it was easy to
generate a custom CPU in Verilog to execute the assembler code. The resulting
design was compacted by reusing identical instructions and pipelined to reduce
congestion. 
This produced a custom CPU with an instruction set specifically designed to facilitate the put, find and delete operations on a B-Tree .
The same B-Tree algorithm has now been implemented on a generic reduced instruction set computer CPU so that the performance of the generic CPU versus the performance of the custom CPU can be compared.
Performance as measured by Open Road for the custom CPU versus the generic CPU on a 2/3 keys per leaf/branch B-Tree . The performance gap widens as we increase the number of keys in each branch and leaf in the B-Tree.
| Area μm² | Fmax MHz | Statements | |||
|---|---|---|---|---|---|
| Custom | Generic | Custom | Generic | Custom | Generic |
| 2467 | 12927 | 902 | 399 | 23 | 122 |
| 5.24 x Smaller | 2.26 x Faster | 5.30 * Compact Code | |||
| 62.76 x better | |||||
In the above area in micro meters squared equates to power consumption while frequency in mega hertz equates to execution speed. And even better a find operation takes far fewer statements to execute on the custom CPU than it does on the generic CPU because the custom operation codes are so much better adapted to manipulating a B-Tree .
The logs of the successful synthesis, placement and routing of the individual components of the custom CPU for Database on a Chip using Vivado targeting an Advanced Micro Devices XC7A50T Field Programmable Gate Array can be seen here:
find ,
put .
Open Road successfully compiles the find, delete and put operations
implemented by the custom CPU onto freepdk-45nm Silicon . The following images
show the layout on Silicon for each operation:
,
,
.
The find operation of the custom CPU is small enough to be run on a Gowin Tang Nano 9K Field Programmable Gate Array, see:
In the image, the power light is the LED at the bottom, then reading up the first 4 leds from the power LED having values 8, 4, 2, 1 are signalling that the data associated with database key 5 is 4 or in binary P 0100F0 where F is powered on showing that the database key was successfully found in the B-Tree .
Example: finding the data associated with a database key
For a small tree:
BtreeSF t = new BtreeSF()
{int maxSize () {return 8;}
int maxKeysPerLeaf () {return 2;}
int maxKeysPerBranch() {return 3;}
int bitsPerKey () {return 4;}
int bitsPerData () {return 4;}
};
The tree being searched looks like this:
ok(t, """
4 |
0 |
5 |
6 |
2 6 7 |
5 6 6.1 |
1 4 7 |
3 2 |
1,2=1 3,4=3 5,6=4 7=7 8,9=2 |
""");
Running the generated Verilog code to find the data associated with database key 2 produces:
Stopped after: 117 steps key 2 data 7
The evolution of a B-Tree as the lowest element is deleted successively until the tree is empty.
At start with 32 elements
+----------------------------------------------------------------------------------------------------------------------------+
| 16 24 |
| 0 0.1 |
| 7 18 |
| 8 |
| 4 8 12 20 28 |
| 7 7.1 7.2 18 8 |
| 1 4 6 12 17 |
| 10 15 2 |
| 1,2,3,4=1 5,6,7,8=4 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+----------------------------------------------------------------------------------------------------------------------------+
After deleting: 1
+-----------------------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 4 8 12 20 24 28 |
| 7 7.1 7.2 18 18.1 18.2 |
| 1 4 6 12 15 17 |
| 10 2 |
| 2,3,4=1 5,6,7,8=4 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+-----------------------------------------------------------------------------------------------------------------------------+
After deleting: 2
+---------------------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 4 8 12 20 24 28 |
| 7 7.1 7.2 18 18.1 18.2 |
| 1 4 6 12 15 17 |
| 10 2 |
| 3,4=1 5,6,7,8=4 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+---------------------------------------------------------------------------------------------------------------------------+
After deleting: 3
+-------------------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 4 8 12 20 24 28 |
| 7 7.1 7.2 18 18.1 18.2 |
| 1 4 6 12 15 17 |
| 10 2 |
| 4=1 5,6,7,8=4 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+-------------------------------------------------------------------------------------------------------------------------+
After deleting: 4
+------------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 8 12 20 24 28 |
| 7 7.1 18 18.1 18.2 |
| 1 6 12 15 17 |
| 10 2 |
| 5,6,7,8=1 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+------------------------------------------------------------------------------------------------------------------+
After deleting: 5
+----------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 8 12 20 24 28 |
| 7 7.1 18 18.1 18.2 |
| 1 6 12 15 17 |
| 10 2 |
| 6,7,8=1 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+----------------------------------------------------------------------------------------------------------------+
After deleting: 6
+--------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 8 12 20 24 28 |
| 7 7.1 18 18.1 18.2 |
| 1 6 12 15 17 |
| 10 2 |
| 7,8=1 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+--------------------------------------------------------------------------------------------------------------+
After deleting: 7
+------------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 8 12 20 24 28 |
| 7 7.1 18 18.1 18.2 |
| 1 6 12 15 17 |
| 10 2 |
| 8=1 9,10,11,12=6 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+------------------------------------------------------------------------------------------------------------+
After deleting: 8
+------------------------------------------------------------------------------------------------------+
| 16 |
| 0 |
| 7 |
| 18 |
| 12 20 24 28 |
| 7 18 18.1 18.2 |
| 1 12 15 17 |
| 10 2 |
| 9,10,11,12=1 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+------------------------------------------------------------------------------------------------------+
After deleting: 9
+---------------------------------------------------------------------------------------------------+
| 20 |
| 0 |
| 7 |
| 18 |
| 12 16 24 28 |
| 7 7.1 18 18.1 |
| 1 10 15 17 |
| 12 2 |
| 10,11,12=1 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+---------------------------------------------------------------------------------------------------+
After deleting: 10
+------------------------------------------------------------------------------------------------+
| 20 |
| 0 |
| 7 |
| 18 |
| 12 16 24 28 |
| 7 7.1 18 18.1 |
| 1 10 15 17 |
| 12 2 |
| 11,12=1 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+------------------------------------------------------------------------------------------------+
After deleting: 11
+---------------------------------------------------------------------------------------------+
| 20 |
| 0 |
| 7 |
| 18 |
| 12 16 24 28 |
| 7 7.1 18 18.1 |
| 1 10 15 17 |
| 12 2 |
| 12=1 13,14,15,16=10 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+---------------------------------------------------------------------------------------------+
After deleting: 12
+------------------------------------------------------------------------------------+
| 20 |
| 0 |
| 7 |
| 18 |
| 16 24 28 |
| 7 18 18.1 |
| 1 15 17 |
| 12 2 |
| 13,14,15,16=1 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+------------------------------------------------------------------------------------+
After deleting: 13
+--------------------------------------------------------------------------------+
| 24 |
| 0 |
| 7 |
| 18 |
| 16 20 28 |
| 7 7.1 18 |
| 1 12 17 |
| 15 2 |
| 14,15,16=1 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+--------------------------------------------------------------------------------+
After deleting: 14
+-----------------------------------------------------------------------------+
| 24 |
| 0 |
| 7 |
| 18 |
| 16 20 28 |
| 7 7.1 18 |
| 1 12 17 |
| 15 2 |
| 15,16=1 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+-----------------------------------------------------------------------------+
After deleting: 15
+--------------------------------------------------------------------------+
| 24 |
| 0 |
| 7 |
| 18 |
| 16 20 28 |
| 7 7.1 18 |
| 1 12 17 |
| 15 2 |
| 16=1 17,18,19,20=12 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+--------------------------------------------------------------------------+
After deleting: 16
+-----------------------------------------------------------------+
| 24 |
| 0 |
| 7 |
| 18 |
| 20 28 |
| 7 18 |
| 1 17 |
| 15 2 |
| 17,18,19,20=1 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+-----------------------------------------------------------------+
After deleting: 17
+----------------------------------------------------------------+
| 20 24 28 |
| 0 0.1 0.2 |
| 1 15 17 |
| 2 |
| 18,19,20=1 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+----------------------------------------------------------------+
After deleting: 18
+-------------------------------------------------------------+
| 20 24 28 |
| 0 0.1 0.2 |
| 1 15 17 |
| 2 |
| 19,20=1 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+-------------------------------------------------------------+
After deleting: 19
+----------------------------------------------------------+
| 20 24 28 |
| 0 0.1 0.2 |
| 1 15 17 |
| 2 |
| 20=1 21,22,23,24=15 25,26,27,28=17 29,30,31,32=2 |
+----------------------------------------------------------+
After deleting: 20
+-------------------------------------------------+
| 24 28 |
| 0 0.1 |
| 1 17 |
| 2 |
| 21,22,23,24=1 25,26,27,28=17 29,30,31,32=2 |
+-------------------------------------------------+
After deleting: 21
+----------------------------------------------+
| 24 28 |
| 0 0.1 |
| 1 17 |
| 2 |
| 22,23,24=1 25,26,27,28=17 29,30,31,32=2 |
+----------------------------------------------+
After deleting: 22
+-------------------------------------------+
| 24 28 |
| 0 0.1 |
| 1 17 |
| 2 |
| 23,24=1 25,26,27,28=17 29,30,31,32=2 |
+-------------------------------------------+
After deleting: 23
+----------------------------------------+
| 24 28 |
| 0 0.1 |
| 1 17 |
| 2 |
| 24=1 25,26,27,28=17 29,30,31,32=2 |
+----------------------------------------+
After deleting: 24
+-------------------------------+
| 28 |
| 0 |
| 1 |
| 2 |
| 25,26,27,28=1 29,30,31,32=2 |
+-------------------------------+
After deleting: 25
+----------------------------+
| 28 |
| 0 |
| 1 |
| 2 |
| 26,27,28=1 29,30,31,32=2 |
+----------------------------+
After deleting: 26
+-------------------------+
| 28 |
| 0 |
| 1 |
| 2 |
| 27,28=1 29,30,31,32=2 |
+-------------------------+
After deleting: 27
+----------------------+
| 28 |
| 0 |
| 1 |
| 2 |
| 28=1 29,30,31,32=2 |
+----------------------+
After deleting: 28
+--------------+
| 29,30,31,32=0 |
+--------------+
After deleting: 29
+-----------+
| 30,31,32=0 |
+-----------+
After deleting: 30
+--------+
| 31,32=0 |
+--------+
After deleting: 31
+-----+
| 32=0 |
+-----+
After deleting: 32
+---+
| =0 |
+---+
The Sieve of Eratosthenes is an ancient and efficient algorithm used to find all prime numbers up to a given number N. It works by iteratively removing the the multiples of each prime number from an initial set of integers.
In this example, with N set to 64, the initial set of integers was successfully reduced to a set of primes by deleting the multiples of each prime. A B-Tree was used to hold the initial set of integers 1..64. Deleting the multiples of each prime produces leaves behind the primes as the leaves upon the tree:
6 17 40 |
0 0.1 0.2 |
5 11 23 |
6 |
2 8 16 19 29 43 53 |
5 11 11.1 23 23.1 6 6.1 |
1 7 8 14 18 29 35 |
3 13 26 21 |
1,2=1 3,5=3 7=7 11,13=8 17=13 19=14 23,29=18 31,37=26 41,43=29 47,53=35 59,61=21 |
Find next Further optimization of generic and custom CPUs. Automate reporting of crucial results from mass of files produced by Vivado and Open Road Much larger pages controlled by embedded btrees Widen BtreeSF from one bit to multiples of bits Use BinarySearch to locate a database key in a node. Use OpenRam for memory