# Estimating ROM gate count in ASIC

#### Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

•  Subject
• Author
• Posted on
I've searched for this but to no avail.  I'd like a function f(D,W), where
D=depth and W=width, which provides an estimate of the gate count of a
lookup ROM implemented in ASIC gates.

Yes, I know it's dependent on the contents.  However, if half the bits are
ones and the contents are randomly distributed, a formula should be pretty
accurate.

It's easy for me to figure out an upper limit.  A basic ROM is an AND-OR ar
ray.  The D address decoders (comprising ANDs/NOTs) can be shared amongst t
he W columns.  Each of the W columns would require D/2-1 OR gates if half t
he ROM bits in each column are 1.

What I don't know is how many gates can be eliminated by sharing terms.  As
W increases, term sharing should go up.  Again, I'm looking for a *formula
*.

Re: Estimating ROM gate count in ASIC
On Thursday, December 6, 2018 at 4:02:25 PM UTC-7, Kevin Neilson wrote:

e D=depth and W=width, which provides an estimate of the gate count of
a lookup ROM implemented in ASIC gates.

e ones and the contents are randomly distributed, a formula should be prett
y accurate.

array.  The D address decoders (comprising ANDs/NOTs) can be shared amongst
the W columns.  Each of the W columns would require D/2-1 OR gates if half
the ROM bits in each column are 1.

As W increases, term sharing should go up.  Again, I'm looking for a *formu
la*.

I meant each column would require D/4-1 ORs.  Approximately.

Re: Estimating ROM gate count in ASIC
On Thursday, December 6, 2018 at 4:05:29 PM UTC-7, Kevin Neilson wrote:

ere D=depth and W=width, which provides an estimate of the gate count o
f a lookup ROM implemented in ASIC gates.

are ones and the contents are randomly distributed, a formula should be pre
tty accurate.

R array.  The D address decoders (comprising ANDs/NOTs) can be shared among
st the W columns.  Each of the W columns would require D/2-1 OR gates if ha
lf the ROM bits in each column are 1.

As W increases, term sharing should go up.  Again, I'm looking for a *for
mula*.

I was right the first time.  D/2-1

Re: Estimating ROM gate count in ASIC
Am Freitag, 7. Dezember 2018 00:16:38 UTC+1 schrieb Kevin Neilson:

where D=depth and W=width, which provides an estimate of the gate count
of a lookup ROM implemented in ASIC gates.

s are ones and the contents are randomly distributed, a formula should be p
retty accurate.

Not so easy as you think as the content of the ROM has a very strong influe
nce on the result.

Assume a simple ROM content with 50% '0' and 50% '1'

Bit      3210
-------------

This is

Now you can very easy scramble the content slightly to be no longer able to
build that simple terms.

In worst case you end up with a full DNF for each Bit.

Each bit of datawidth would in worst case need a term in DNF with a number
of clauses equal to the number of bit ='1' and each clause in DNF having

For a ROM of 10 bit address with equal distributed '1' and '0' this means 5
12 clauses of 10 variables in DNF is your upper limit per databit.

This would be 512 AND gates with 10 inputs and one OR gate with 512 inputs.

As no ASCI technology has an OR gate with 512 inputs or an AND gate with 10
inputs, you need to build this using a gate tree => 5 AND3 per clause an
d ~300 OR3 for the or-tree. This means something like 2.9k Gates with three

As you see it might still be possible to have a regularity in the formula t
hat can reduce this to a simple gate per data bit, but in general random RO
M data tend to have only low possibilities of term reduction and for larger
depth of RAM you cannot see on first glance if any reduction is possible a
t all.

bye Thomas

Re: Estimating ROM gate count in ASIC

Maybe I should have specified that depth D is large.  A formula will not be accurate for tiny ROMs but should be as D increases.

Re: Estimating ROM gate count in ASIC
On Thursday, December 6, 2018 at 6:02:25 PM UTC-5, Kevin Neilson wrote:

e D=depth and W=width, which provides an estimate of the gate count of
a lookup ROM implemented in ASIC gates.

e ones and the contents are randomly distributed, a formula should be prett
y accurate.

array.  The D address decoders (comprising ANDs/NOTs) can be shared amongst
the W columns.  Each of the W columns would require D/2-1 OR gates if half
the ROM bits in each column are 1.

As W increases, term sharing should go up.  Again, I'm looking for a *formu
la*.

That would be pretty easy.  Consider the costs of a D wide multiplexer with
1 or 0 on each input.  That would be an upper bound in any case.

I believe my text book of many years ago used one of the input variables in
either true or inverted form combined with 1s and 0s as choices for inputs
which simplified the mux by one address input.

Rick C.

Tesla referral code - https://ts.la/richard11209
Get 6 months of free supercharging

Re: Estimating ROM gate count in ASIC
On Saturday, December 22, 2018 at 12:14:43 PM UTC-7, snipped-for-privacy@gmail.co
m wrote:

ere D=depth and W=width, which provides an estimate of the gate count o
f a lookup ROM implemented in ASIC gates.

are ones and the contents are randomly distributed, a formula should be pre
tty accurate.

R array.  The D address decoders (comprising ANDs/NOTs) can be shared among
st the W columns.  Each of the W columns would require D/2-1 OR gates if ha
lf the ROM bits in each column are 1.

As W increases, term sharing should go up.  Again, I'm looking for a *for
mula*.

th 1 or 0 on each input.  That would be an upper bound in any case.

in either true or inverted form combined with 1s and 0s as choices for inpu
ts which simplified the mux by one address input.

Thanks, but I am looking for an accurate estimate.

Re: Estimating ROM gate count in ASIC
On Friday, December 28, 2018 at 2:49:37 PM UTC-5, Kevin Neilson wrote:

com wrote:

where D=depth and W=width, which provides an estimate of the gate count
of a lookup ROM implemented in ASIC gates.

s are ones and the contents are randomly distributed, a formula should be p
retty accurate.

-OR array.  The D address decoders (comprising ANDs/NOTs) can be shared amo
ngst the W columns.  Each of the W columns would require D/2-1 OR gates if
half the ROM bits in each column are 1.

s.  As W increases, term sharing should go up.  Again, I'm looking for a *f
ormula*.

with 1 or 0 on each input.  That would be an upper bound in any case.

s in either true or inverted form combined with 1s and 0s as choices for in
puts which simplified the mux by one address input.

I'm confused.  Do you want an accurate measurement or an estimate?

Rick C.

- Get 6 months of free supercharging
- Tesla referral code - https://ts.la/richard11209

Re: Estimating ROM gate count in ASIC
On Saturday, December 29, 2018 at 9:53:20 AM UTC-7, snipped-for-privacy@gmail.com
wrote:

l.com wrote:

e:

, where D=depth and W=width, which provides an estimate of the gate cou
nt of a lookup ROM implemented in ASIC gates.

its are ones and the contents are randomly distributed, a formula should be
pretty accurate.

ND-OR array.  The D address decoders (comprising ANDs/NOTs) can be shared a
mongst the W columns.  Each of the W columns would require D/2-1 OR gates i
f half the ROM bits in each column are 1.

rms.  As W increases, term sharing should go up.  Again, I'm looking for a
*formula*.

r with 1 or 0 on each input.  That would be an upper bound in any case.

les in either true or inverted form combined with 1s and 0s as choices for
inputs which simplified the mux by one address input.

Both.  An estimate will be very close for large D,W.  If I roll a die 1e6 t
imes, estimating there will be 5e5 heads is pretty accurate.  Estimating th
ere will be less than or equal to the upper bound of 1e6 heads is correct b

Re: Estimating ROM gate count in ASIC
On Sunday, December 30, 2018 at 2:52:43 PM UTC-5, Kevin Neilson wrote:

om wrote:

ail.com wrote:

ote:

W), where D=depth and W=width, which provides an estimate of the gate c
ount of a lookup ROM implemented in ASIC gates.

bits are ones and the contents are randomly distributed, a formula should
be pretty accurate.

AND-OR array.  The D address decoders (comprising ANDs/NOTs) can be shared
amongst the W columns.  Each of the W columns would require D/2-1 OR gates
if half the ROM bits in each column are 1.

terms.  As W increases, term sharing should go up.  Again, I'm looking for
a *formula*.

xer with 1 or 0 on each input.  That would be an upper bound in any case.

ables in either true or inverted form combined with 1s and 0s as choices fo
r inputs which simplified the mux by one address input.

times, estimating there will be 5e5 heads is pretty accurate.  Estimating
there will be less than or equal to the upper bound of 1e6 heads is correct

Good thing you aren't rolling a die.

How much do you think this upper bound will vary from your estimate?  Have
you tried any tests?  What is the result of your "estimate" under-estimatin
g?

I think if I were doing this I'd try to get a handle on the expected result
s and how much they might vary before I start looking for an equation to "e
stimate" the number.  The one thing you didn't do with the die example is t
o figure out how much you need to adjust your estimate to get a bound that
will include 99.9xxx% of your cases or whatever value you need.  Do you kno
w that equation?

Rick C.

+ Get 6 months of free supercharging
+ Tesla referral code - https://ts.la/richard11209

Re: Estimating ROM gate count in ASIC
On Sunday, December 30, 2018 at 2:37:46 PM UTC-7, snipped-for-privacy@gmail.com w
rote:

.com wrote:

:

gmail.com wrote:

wrote:

D,W), where D=depth and W=width, which provides an estimate of the gate
count of a lookup ROM implemented in ASIC gates.

he bits are ones and the contents are randomly distributed, a formula shoul
d be pretty accurate.

an AND-OR array.  The D address decoders (comprising ANDs/NOTs) can be shar
ed amongst the W columns.  Each of the W columns would require D/2-1 OR gat
es if half the ROM bits in each column are 1.

g terms.  As W increases, term sharing should go up.  Again, I'm looking fo
r a *formula*.

lexer with 1 or 0 on each input.  That would be an upper bound in any case.

riables in either true or inverted form combined with 1s and 0s as choices
for inputs which simplified the mux by one address input.

e6 times, estimating there will be 5e5 heads is pretty accurate.  Estimatin
g there will be less than or equal to the upper bound of 1e6 heads is corre

e you tried any tests?  What is the result of your "estimate" under-estimat
ing?

lts and how much they might vary before I start looking for an equation to
"estimate" the number.  The one thing you didn't do with the die example is
to figure out how much you need to adjust your estimate to get a bound tha
t will include 99.9xxx% of your cases or whatever value you need.  Do you k
now that equation?

Sorry, my response could've been more nicely expressed.  I originally thoug
h that ASIC guys must have some formula for this but perhaps not--maybe the
y just run it through the synthesizer and check.  I'm writing ASIC code but
don't have direct access to the synthesizer.  If I did I could maybe plot
a few points and fit a curve to it.  I only have access to FPGA synthesizer
s and of course they just implement ROMs in LUTs and the LUT count is propo
rtional to the number of bits in the ROM and there is no logic sharing as t
he ROM size increases.

I did think about the die/coin example and how to find how good the estimat
e is.  For example, say you flip a coin 1000 times.  My expected number of
heads is is 500.  Say you want to know how many runs will have between 450
and 550 heads.  You can use the Poisson CDF.  In Matlab/Octave:

octave:32> n_flips10%00; exp_heads = n_flips*0.5; poisscdf(550,exp_he
ans =  0.97469

So I'll be in that range 97.5% of the time.

Re: Estimating ROM gate count in ASIC
On Tuesday, January 1, 2019 at 6:55:57 PM UTC-5, Kevin Neilson wrote:

wrote:

il.com wrote:

te:

.@gmail.com wrote:

n wrote:

f(D,W), where D=depth and W=width, which provides an estimate of the ga
te count of a lookup ROM implemented in ASIC gates.

the bits are ones and the contents are randomly distributed, a formula sho
uld be pretty accurate.

s an AND-OR array.  The D address decoders (comprising ANDs/NOTs) can be sh
ared amongst the W columns.  Each of the W columns would require D/2-1 OR g
ates if half the ROM bits in each column are 1.

ing terms.  As W increases, term sharing should go up.  Again, I'm looking
for a *formula*.

iplexer with 1 or 0 on each input.  That would be an upper bound in any cas
e.

variables in either true or inverted form combined with 1s and 0s as choice
s for inputs which simplified the mux by one address input.

1e6 times, estimating there will be 5e5 heads is pretty accurate.  Estimat
ing there will be less than or equal to the upper bound of 1e6 heads is cor

ave you tried any tests?  What is the result of your "estimate" under-estim
ating?

sults and how much they might vary before I start looking for an equation t
o "estimate" the number.  The one thing you didn't do with the die example
is to figure out how much you need to adjust your estimate to get a bound t
hat will include 99.9xxx% of your cases or whatever value you need.  Do you
know that equation?

ugh that ASIC guys must have some formula for this but perhaps not--maybe t
hey just run it through the synthesizer and check.  I'm writing ASIC code b
ut don't have direct access to the synthesizer.  If I did I could maybe plo
t a few points and fit a curve to it.  I only have access to FPGA synthesiz
ers and of course they just implement ROMs in LUTs and the LUT count is pro
portional to the number of bits in the ROM and there is no logic sharing as
the ROM size increases.

ate is.  For example, say you flip a coin 1000 times.  My expected number o
f heads is is 500.  Say you want to know how many runs will have between 45
0 and 550 heads.  You can use the Poisson CDF.  In Matlab/Octave:

My point is that unless you can come up with a number like this for your es
timate, how much good will it do you?  Even if you are right 99% of the tim
e, when designing a chip is that of much value?

I would think knowing the upper bound is a very useful thing indeed when pl
anning an ASIC.  But I don't have any more info on calculating the estimate

Rick C.

-- Get 6 months of free supercharging
-- Tesla referral code - https://ts.la/richard11209

Re: Estimating ROM gate count in ASIC
Am Mittwoch, 2. Januar 2019 00:55:57 UTC+1 schrieb Kevin Neilson:

I think you did not understand my posting. There is no way of estimating th
e synthesis result of a ROM right by simple formula.
Unless you build a model of the synthesis tool itself with this formula.

A change of 1 dataword in a ROM with 1024 words could significant change th
e synthesis result by more than 1%.

There is a simple upper bound and a simple lower bound but real ROMs are al
ways in between.
Simple upper bound is calculated by building DNF for ROM in given technolog
y and lower bound is 1 gate per bit (tie0 or tie1) for stand alone synthesi
s.

Take for example DES encryption algorithm S-Box. These are lookup tables (R
OM) designed to be not easy reduced by synthesis tools. You could synthesis
one of this S-Box 10 times with different seeds and would not get 2 identi
cal results for the same S-Box.