Browse Prior Art Database

Applications of SAT to FPGAs

IP.com Disclosure Number: IPCOM000131697D
Publication Date: 2005-Dec-07
Document File: 9 page(s) / 110K

Publishing Venue

The IP.com Prior Art Database

Abstract

Applications of SAT to FPGAs

This text was extracted from a Microsoft PowerPoint presentation.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Slide 1 of 9

Applications of SAT to FPGAs


Slide 2 of 9

Resynthesis

Given a LUT network, with ‘Y’ LUTs, can you reduce the number of LUTs.

The more LUTs we can remove, the farther we are from the optimal mapping


Slide 3 of 9

Resynthesis

Attempt to map a Maximum Fanout Free Cone (MFFC) with X LUTs to another MFFC with less than X LUTs


Slide 4 of 9

Resynthesis Structures

Given a MFFC with 10 or less inputs and containing more than 3 LUTs, map it to:

Given a MFFC with 7 or less inputs and containing more than 2 LUTs, map it to:

[This slide contains 2 pictures or other non-text objects]


Slide 5 of 9

Circuit

ZMap LUT count

Resynth LUT count

Ratio

b20

5996

5530

0.92

clma

5014

4792

0.96

b15_1

4291

4112

0.96

b15_1_opt_C

3879

3772

0.97

s38584.1

3771

3454

0.92

s38417

3586

3444

0.96

b14

3072

2902

0.94

frisc

2624

2571

0.98

pdc

1928

1875

0.97

misex3

1184

1156

0.98

seq

1182

1162

0.98

alu4

1129

1103

0.98

ex5p

993

968

0.97

i10

789

764

0.97

Total

33442

32075

0.96

Sub-total Small circuits (<3000 LUTs)

9829

9599

0.98

Sub-total Large circuits (>3000 LUTs)

29609

28006

0.95


Slide 6 of 9

Digital Logic Blocks with Tricks

Are current Tech Mappers able to Intelligently map some common Logic Blocks


Slide 7 of 9

ZMap Technology Map 4-MUX

       
       
         
   

00

01

10

11


Slide 8 of 9

After Resynthesis 4-MUX

       
       
         
   

00

01

10

11


Slide 9 of 9

Block

ZMap LUT Count

Resynth LUT Count

Ratio

4:1 MUX

3

2

0.67

4-bit Barrel Shifter

12

8

0.67

16-bit Barrel Shifter

48

32

0.67

6-bit Prioirity Function

6

3

0.50

6-bit Set Reset Check

3

2

0.67

Add Compare

6

2

0.33

8-bit Add Compare

45

41

0.91

2-bit Add Compare

3

2

0.67

Encoder

74

59

0.80

16:1 MUX

29

21

0.72

8-bit Bus MUX

24

16

0.67

Total

253

188

0.74