Skip to content

Latest commit

 

History

History
134 lines (103 loc) · 9.02 KB

README.md

File metadata and controls

134 lines (103 loc) · 9.02 KB

Execution cost estimator for LBF circuits

Estimate execution cost of a LBF files using concrete estimation tools

Initialize pathed concrete library

bash init.sh

Estimation examples

Estimate sequential execution time:

python3 estimator.py sample.lbf

Change functional bootstrapping precision:

python3 estimator.py sample.lbf --fbs_size 6

LBF format

The LBF (Lincomb Bootstrap Format) files encode circuits composed of linear combinations and bootstrapping gates. LBF files are used to express Boolean circuits in the TFHE functional bootstrapping model of computation. The LBF format is inspired from BLIF format for logic circuits.

LBF files has the following structure:

.inputs <input list>
.outputs <output list>
<gate list>
.end

Circuit inputs and outputs are defined as a list of string identifiers and contain at least one element each. Two types of nodes are defined: linear combination and bootstrapping nodes.

Linear combination node

A linear combination node is defined as:

.lincomb <input list> <output>
<coefficient list> [<constant coefficient>]

The size of input and coefficient list are equal. Optionally a constant coefficient can be declared, in case it is not given zero value is used. If the input list is empty then the output is a constant, given by the constant coefficient.

Examples

A linear combination c = 2 * a + b

.lincomb a b c
2 1

A linear combination c = a - b + 1

.lincomb a b c
1 -1 1

A constant c = 2

.lincomb c
2

Bootstrapping node

A bootstrapping node is defined as:

.bootstrap <input> <output list>
<tables>

This node maps the input value k to the k-th entry of the corresponding table. One table per output in the output list is given. A table is a string of 0 and 1 whose length is equal to the maximum span on input.

Examples

A bootstrapping b = 1 if a == 2 and b = 0 otherwise:

.bootstrap a b
001

3 bootstrapping:

  • b = 1 if a == 2 and b = 0 otherwise
  • c = 1 if a == 0 and c = 0 otherwise
  • d = 0 for a == 0, d = 1 for a == 1 and don't cares otherwise.
.bootstrap a b c d
001
100
01

Estimated results

EPFL benchmarks AutoHoG Area-oriented technology mapping Multi-value-FBS-aware technology mapping
FBS size LinComb sqared norm FBS cost Overall cost FBS size LinComb sqared norm FBS cost Overall cost FBS size LinComb sqared norm FBS cost Overall cost
Adder 4 80 40 20280 3 45 38 7258 3 45 38 4864
Barrel shifter 4 80 40 99840 4 80 40 99840 4 80 40 99840
Divisor 4 80 40 1150920 4 80 40 524640 4 80 40 523040
Hypotenus 4 80 40 4853000 4 80 40 3327760 4 80 40 3123040
Log2 4 80 40 806400 4 80 40 562320 4 80 40 542920
Max 4 80 40 86160 4 80 40 82720 4 80 40 82640
Multiplier 4 80 40 581200 4 80 40 417680 4 80 40 398280
Sine 4 336 44 157432 4 336 44 110088 4 336 44 105512
Square-root 4 80 40 418080 4 80 40 331040 4 80 40 328720
Sqaure 4 80 40 478720 4 80 40 346440 4 80 40 301880
Round-robin arbiter 4 5 40 457360 4 5 40 464200 4 5 40 464200
Coding-cavlc 4 80 40 22160 4 80 40 21800 4 80 40 21680
ALU control unit 4 80 40 3880 4 80 40 3760 4 80 40 3760
Decoder 4 80 40 11640 4 80 40 11680 4 80 40 11680
I2C controller 4 80 40 44360 4 80 40 41280 4 80 40 41160
INT to FLOAT converter 4 80 40 7000 4 80 40 6840 4 80 40 6800
Memory Controller 4 336 44 1603624 4 336 44 1562440 4 336 44 1540704
Priority encoder 4 80 40 33320 4 80 40 32720 4 80 40 32720
Lookahead XY router 4 80 40 6960 4 80 40 5360 4 80 40 5040
Voter 4 336 44 227480 4 336 44 145464 4 80 40 117440
Average 553490.80 405266.50 387796.00