Estimating ROM gate count in ASIC

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 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.

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*. 

On Thursday, December 6, 2018 at 4:02:25 PM UTC-7, Kevin Neilson wrote:
> 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 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.
> 
> 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*.

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

On Thursday, December 6, 2018 at 4:05:29 PM UTC-7, Kevin Neilson wrote:
> On Thursday, December 6, 2018 at 4:02:25 PM UTC-7, Kevin Neilson wrote:
> > 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 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.
> > 
> > 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*.
> 
> I meant each column would require D/4-1 ORs.  Approximately.

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

Am Freitag, 7. Dezember 2018 00:16:38 UTC+1 schrieb Kevin Neilson:
> On Thursday, December 6, 2018 at 4:05:29 PM UTC-7, Kevin Neilson wrote:
> > On Thursday, December 6, 2018 at 4:02:25 PM UTC-7, Kevin Neilson wrote:
> > > 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.

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

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

Bit      3210
-------------
Adr 000: 0000  
Adr 001: 1010    
Adr 010: 1100    
Adr 011: 1110    
Adr 100: 1000    
Adr 101: 1010  
Adr 110: 1100  
Adr 111: 1111  
 
This is
RomData(0)= Adr(0) AND Adr(1) AND Adr(3)
RomData(1)= Adr(0)
RomData(2)= Adr(1)
RomData(3)= Adr(0) OR Adr(1) OR ADR(3)

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 addresswidth number of variables.

For a ROM of 10 bit address with equal distributed '1' and '0' this means 512 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 and ~300 OR3 for the or-tree. This means something like 2.9k Gates with three inputs per bit instead of your assumed Depth/2-1 gates.
 
As you see it might still be possible to have a regularity in the formula that can reduce this to a simple gate per data bit, but in general random ROM 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 at all.

bye Thomas

> Not so easy as you think as the content of the ROM has a very strong influence on the result.
> 
> Assume a simple ROM content with 50% '0' and 50% '1'
> 
> Bit      3210
> -------------
> Adr 000: 0000  
> Adr 001: 1010    
> Adr 010: 1100    
> Adr 011: 1110    
> Adr 100: 1000    
> Adr 101: 1010  
> Adr 110: 1100  
> Adr 111: 1111  

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.

On Thursday, December 6, 2018 at 6:02:25 PM UTC-5, Kevin Neilson wrote:
> 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 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.
> 
> 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*.

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

On Saturday, December 22, 2018 at 12:14:43 PM UTC-7, gnuarm.del...@gmail.co=
m wrote:
> On Thursday, December 6, 2018 at 6:02:25 PM UTC-5, Kevin Neilson wrote:
> > I've searched for this but to no avail.  I'd like a function f(D,W), wh=
ere D=3Ddepth and W=3Dwidth, which provides an estimate of the gate count o=
f a lookup ROM implemented in ASIC gates.
> >=20
> > 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 pre=
tty accurate.
> >=20
> > It's easy for me to figure out an upper limit.  A basic ROM is an AND-O=
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.
> >=20
> > 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 *for=
mula*.
>=20
> That would be pretty easy.  Consider the costs of a D wide multiplexer wi=
th 1 or 0 on each input.  That would be an upper bound in any case. =20
>=20
> 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 inpu=
ts which simplified the mux by one address input. =20
>=20
>   Rick C.=20
>=20
>   Tesla referral code - https://ts.la/richard11209
>   Get 6 months of free supercharging

Thanks, but I am looking for an accurate estimate. 

On Friday, December 28, 2018 at 2:49:37 PM UTC-5, Kevin Neilson wrote:
> On Saturday, December 22, 2018 at 12:14:43 PM UTC-7, gnuarm.del...@gmail.com wrote:
> > On Thursday, December 6, 2018 at 6:02:25 PM UTC-5, Kevin Neilson wrote:
> > > 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 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.
> > > 
> > > 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*.
> > 
> > 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
> 
> Thanks, but I am looking for an accurate estimate.

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

On Saturday, December 29, 2018 at 9:53:20 AM UTC-7, gnuarm.del...@gmail.com wrote:
> On Friday, December 28, 2018 at 2:49:37 PM UTC-5, Kevin Neilson wrote:
> > On Saturday, December 22, 2018 at 12:14:43 PM UTC-7, gnuarm.del...@gmail.com wrote:
> > > On Thursday, December 6, 2018 at 6:02:25 PM UTC-5, Kevin Neilson wrote:
> > > > 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 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.
> > > > 
> > > > 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*.
> > > 
> > > 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
> > 
> > Thanks, but I am looking for an accurate estimate.
> 
> 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

Both.  An estimate will be very close for large D,W.  If I roll a die 1e6 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 but not helpful.

On Sunday, December 30, 2018 at 2:52:43 PM UTC-5, Kevin Neilson wrote:
> On Saturday, December 29, 2018 at 9:53:20 AM UTC-7, gnuarm.del...@gmail.com wrote:
> > On Friday, December 28, 2018 at 2:49:37 PM UTC-5, Kevin Neilson wrote:
> > > On Saturday, December 22, 2018 at 12:14:43 PM UTC-7, gnuarm.del...@gmail.com wrote:
> > > > On Thursday, December 6, 2018 at 6:02:25 PM UTC-5, Kevin Neilson wrote:
> > > > > 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 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.
> > > > > 
> > > > > 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*.
> > > > 
> > > > 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
> > > 
> > > Thanks, but I am looking for an accurate estimate.
> > 
> > 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
> 
> Both.  An estimate will be very close for large D,W.  If I roll a die 1e6 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 but not helpful.

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-estimating? 

I think if I were doing this I'd try to get a handle on the expected results 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 that will include 99.9xxx% of your cases or whatever value you need.  Do you know that equation? 


  Rick C.

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