* M.map* was developed by Shen et al of Tsing Hua University,
Taiwan, and appeared on IEEE Transactions on Computer-Aided Design
of Integrated Circuit and Systems [11]. Unlike classical
algorithms * mis-pga* or * Chortle-crf*, (but like recent ones
like * Rmap* or [10]) * m.map* performs three tasks in
the process of
FPGA CAD system, that is, * decomposition*, * leveling*,
and * mapping/placement*. In the * decomposition* phase,
the design is converted into the network of two-input primitive
components. The * leveling* phase labels each primitive component
with the length of the path. The third phase, combined process of
* mapping/placement* works iteratively. During this phase,
* m.map* takes the position of CLB on which a portion of Boolean
network is mapped, and the interconnection with CLB's already
placed into consideration. To solve this problem, * m.map*
uses * bipartite-matching algorithm* [12]. The main
advantage of * m.map* algorithm is its delay minimization.
* M.map* was
applied on 14 MCNC networks to compare its performance with
* mis-pga* and * chortle-crf* (* half-perimeter* model was
used for delay measurement). In average, * m.map* was 8.8%
and 30.2% faster than * mis-pga* and * chortle-crf*. In
terms of CLB count, * m.map* showed very inferior results
(more than twice number of CLB's) in 4 out of 14 circuits. However
generally it was competitive with two classical algorithms.

Hitoshi Oi

All Rights Reserved