Design the Look-up Table

EDAboard.com Forum Index -> ASIC Design Methodologies & Tools (Digital) -> Design the Look-up Table

Author

Message

quake

Joined: 23 Nov 2004
Posts: 86

25 Nov 2004 7:32 Design the Look-up Table

hi. The decoder in my design needs several very large Look-up Table, and the speed of my design is so critical, I have corrected these tables for several times but still cannot achive the timing constraint, they waste too much of the time, since a lot of levels of gate are produced, and muxs, the fan_out are also so big with too many wires for connection, big buffers are alse added. Anyone have good idea or experience about it?

nand_gates

Joined: 19 Jul 2004
Posts: 907
Helped: 120

25 Nov 2004 7:58 Re: Design the Look-up Table

One solution is pipe line ur design if you can.
Need the code to see what exactly ur trying to do!
You have't mensioned whether ur targettiong ur design
to FPGA or ASIC. If FPGA then which device? If ASIC then
what technolog and synthesis tools ur using...

quake

Joined: 23 Nov 2004
Posts: 86

25 Nov 2004 9:40 Re: Design the Look-up Table

nand_gates wrote:

hi, thanks. It is for ASIC, 0.18. And I cannot pipeline this module since it belongs to
one stage of the big pipeline of our whole design. It has to process the data and get the result in One Cycle. This module deals with variable length codes. Since those tables must feedback the data and thus the procedure can go on, otherwise the whole system has to wait. Almost all the data are in the tables, do you have any idea of how to look up the data that I want quickly?

nand_gates

Joined: 19 Jul 2004
Posts: 907
Helped: 120

25 Nov 2004 11:48 Re: Design the Look-up Table

I got it you mean to say, unless u decode current code you cant get
next one for decoding. This seems to be complicated. Can I get the code
or example code. I will try out myself.

quake

Joined: 23 Nov 2004
Posts: 86

26 Nov 2004 2:49 Re: Design the Look-up Table

Hey, nand_gates: I can give you my codes, but my codes are changing, I can make it any form, it depends on the architechture directly. The only problem now is that the design has too much data to look up, depending on those already decoded codes, and those data in the tables are also variable-lengthed, it difficult to gather then together and arrange for searching. What I hope to know is what usually engineers do when they have some tables in their design.

niuniu

Joined: 23 Jul 2002
Posts: 87
Helped: 4

26 Nov 2004 2:52 Design the Look-up Table

maybe you have to check if you can use another architecture, see if you can optimize the table.
or use herarchical table.

nand_gates

Joined: 19 Jul 2004
Posts: 907
Helped: 120

26 Nov 2004 7:09 Re: Design the Look-up Table

For lookup tables in design what we do
1. As suggested by niuniu use hirarchical decoding. Here is example

Code:

input [7:0] data_to_be_decoded
...............................
...............................
case(data_to_be_decoded[7:4])
value1 :
case(data_to_be_decoded[3:0])
value1_1 :
decodede = xyz;
value1_2 :
decode = pqr;
...........................
...........................
endcase

value2 :
case(data_to_be_decoded[3:0])
value2_1 :
decodede = abc;
value2_2 :
decode = def;
...........................
...........................
endcase
.......................................
........................................
endcase

This method is used in instuction decoders..

2. Carryout logic analisys and optimization manually and write
gate level code for ur logic. Here optimization means you flatten ur logic
which will increase the gate count.
You try out this with ur synthesis tool first.

quake

Joined: 23 Nov 2004
Posts: 86

26 Nov 2004 7:17 Re: Design the Look-up Table

Hello, niuniu. What kind of architechture do you think is more efficient and more fast? I also hope to find a more efficient way to change my original structrue. I have tried to optimise those tables, but still cost a lot. all kinds of selection paths exist there and they make the delay too long.

quake

Joined: 23 Nov 2004
Posts: 86

26 Nov 2004 7:23 Re: Design the Look-up Table

to nand_gates: originaly I use your first method, but those talbes are big and not like normal instruction sets. your second idea was what I want to do, I realy hope to optimize them at nearly gate level, that realy make me drain my head doing it .
Another important thing is how can I flatten them with DC? I think the synthesis process is highly depends on my RTL codes. So do you havev any idea of how to let DC highly flatten them?

kctang

Joined: 04 Nov 2004
Posts: 39
Helped: 2

26 Nov 2004 9:43 Re: Design the Look-up Table

Hi,

Here is my little suggestions:

1. if you're going to use hier. LUT approach, you should better use hier. boundary to isolate them first or else the result is more similar to a flatten design. For example, you should use a total number of 16 modules for 4-bit LUTs, and a final top level module to MUX to select 16 LUTs' outputs.

2. Do not tried to flatten this design. The number of input is large (a total number of 256 entries). You'll experience non-uniform delay in this design if you've chosen to flatten it.

3. Try to use a ROM to decode. Area of 256 word ROM may be comparable to pure combinational logic with much better worse case delay. This is a design trade-off ;^)

Hope this can help!!

nand_gates

Joined: 19 Jul 2004
Posts: 907
Helped: 120

26 Nov 2004 9:48 Re: Design the Look-up Table

with DC you can use "set_flatten" command.
See help set_flatten

quake

Joined: 23 Nov 2004
Posts: 86

26 Nov 2004 10:45 Re: Design the Look-up Table

hi. If i use a ROM, about how many nano-second do you estimate the latency is?
since my tables cost around 1-2ns with 0.18 tech, and with the large fan_in, the combinational gates are more than ten levels together with big buffers after synthesis.

kctang

Joined: 04 Nov 2004
Posts: 39
Helped: 2

26 Nov 2004 16:07 Re: Design the Look-up Table

In fact the ROM delay varies with target technology and foundary. The best way to find out is get a ROM compiler to do the evaluation. In my own experience, a 256 entries .18um sync. diffusion ROM should be very fast (@100~150MHz range) with small fanin.

One precaution is that if your team didn't use that ROM compiler before, care should be take to make sure the ROM content is correct by running switch level simulation and pass LVS.

uz111

Joined: 25 Oct 2004
Posts: 15

27 Nov 2004 1:52 Re: Design the Look-up Table

How many entries has your table got (all 8 bits are used? 256?)?

Can you give your whole table in Disjunctive Normal Form or in another Form?

I am not very good in Verilog but I can try to help with that algorithm. What is your Max-Fanout???

quake

Joined: 23 Nov 2004
Posts: 86

29 Nov 2004 8:03 Re: Design the Look-up Table

uz111 wrote:

hi. some of the entries have more than 10 bits, but not fully used, like a hundred of items to be stored, and all these data have different lengths. What is Disjunctive Normal Form? Anyother form? Our fanouts are usually very large, some of them have more than 10, or even more. Then do you have any idea?

Google
AdSense
Google Adsense

29 Nov 2004 8:03 Ads

funzero

Joined: 19 Nov 2004
Posts: 204
Helped: 8

06 Dec 2004 3:39 Re: Design the Look-up Table

if your table width exceed 8 bit, you can try decoder shift and encoder tacle to solve this problem ,
for ex: a 8x8 table your can decode input8 to tmp256 after this encoder it to 8 again.
input : 0f; output ff
for (i=0;i<=256;i=i+1)
begin
tmp1[ 0f ] = tmp2[ ff ];
end

quake

Joined: 23 Nov 2004
Posts: 86

06 Dec 2004 4:22 Re: Design the Look-up Table

funzero wrote:

hi, funzero, what do you mean by "decoder shift and encoder tacle"? Is this way faster? why. I still can not make clear what you suggestion is. more details please.
thanks

funzero

Joined: 19 Nov 2004
Posts: 204
Helped: 8

08 Dec 2004 3:37 Re: Design the Look-up Table

I0_____|---------|___ X0 ___|----------|___ Y0 ____|----------|______O0
| | | | |2nXN |
|NX2n | | switch | | |
In_____|decoder|____ Xn___|________|__ Yn ____ |_______|______On
the decoder ouptuts 2n distincct minterns for n-bit s-box input the switch is wiring area composed fo 2n wires , each wire connects an input port Xi to an output Yk .output of the swith is encoded through 2nXN encoder ,which porduces the n-bit output of the sbox.
search google for "block cipher components pdf "