### Abstract

We consider technology mapping of combinational circuits onto complex configurable logic blocks (CLBs) with two levels of LUTs. We show that if the CLB has b bases, a tree network with n nodes call be mapped in O(C·n^{2b-1}) time, where C is a function dependent on b. b is fixed for a given CLB architecture. In particular, this algorithm runs in O(n^{5}) time when mapping a circuit of n nodes onto the Xilinx XC4000. To the best of our knowledge, this is the first optimal polynomial time algorithm for mapping any non-trivial network onto such a complex CLB architecture. By simplifying the computation, we obtained an O(n^{3}) algorithm. The mapping results are comparable to the best NP-hard MILP approach, but our algorithm runs in polynomial time and is much faster in practice. The larger MCNC benchmark circuits were mapped in a few minutes. Our algorithm also maps to CLBs with independent, heterogeneous LUTs as a special case.

Original language | English (US) |
---|---|

Pages | 216-221 |

Number of pages | 6 |

State | Published - Dec 1 1999 |

Externally published | Yes |

Event | International Conference on Computer Design (ICCD'99) - Austin, TX, USA Duration: Oct 10 1999 → Oct 13 1999 |

### Other

Other | International Conference on Computer Design (ICCD'99) |
---|---|

City | Austin, TX, USA |

Period | 10/10/99 → 10/13/99 |

### ASJC Scopus subject areas

- Hardware and Architecture
- Electrical and Electronic Engineering

## Fingerprint Dive into the research topics of 'Exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs'. Together they form a unique fingerprint.

## Cite this

*Exact tree-based structural technology mapping algorithm for configurable logic blocks in FPGAs*. 216-221. Paper presented at International Conference on Computer Design (ICCD'99), Austin, TX, USA, .