**Figure:** Decomposition in Chortle-crf

* Chortle-crf* was developed by Francis et al at University of
Toronto, and was presented at 28th Design Automation
Conference [4] in 1991. They are also the authors
of [1]. * Chortle-crf* consists of the following three
steps:

- Bin-Packing Decomposition
- This step utilizes unused pins of
LUT's to minimize their total number. Figure 0.1 shows
the operations in this step. In (a), a logic function is represented
by a AND-OR network. Without optimization, six LUT's are needed
(from
**u**to**z**). The LUT**u**has two unused input pins, and**w**does two. By putting a part of OR function into**u**and**w**, the number of LUT's reduces from 6 to 4 (Figure 0.1 (b)). Note that still has one unused pin and also**y**uses only two input pins. These unused pins are used to implement the rest of OR function in**z**(Figure 0.1 (c)). - Reconvergent Paths Exploitation
- Figure 0.2 shows
how exploitation of reconvergent paths can reduce the number of
LUT's. In Figure (a), LUT
**v**and**w**share an input, and their output converge at**z**. In Figure (b)**v**and**w**are merged, and part of OR function of**z**is implemented in . The number of LUT's reduces from 6 to 5. - Fanout Nodes Replication
- By replicating the function of a
fanout node, it may be embedded into the LUT's of of the following
stage. In Figure 0.3 (a), the shaded AND implements
a fanout node to
**y**and**z**. It is replicated and embedded into**y**and**z**. The total number of LUT's is reduced by one.

**Figure:** Reconvergent Paths Exploitation in Chortle-crf

In [1], performance comparison of * mis-pga* and
* chortle-crf* is found. When these two algorithms are applied
to map 27 MCNC networks into circuits of 5-input LUT's, * mi-pga*
requires 14% fewer LUT's than Chortle-crf, but 47 times slower.

**Figure:** Replication of Logic at a Fanout Node in Chortle-crf

Hitoshi Oi

All Rights Reserved