next up previous
Next: Rmap Up: CIS4930 Final Report: Survey Previous: Mis-pga

Chortle-crf

  
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



next up previous
Next: Rmap Up: CIS4930 Final Report: Survey Previous: Mis-pga



Hitoshi Oi
All Rights Reserved