Weekly report 07/01/05
Yan Lin

1. TVLSI final version
I've finished the TVLSI final version and proof read the paper. The 
paper has been submitted to TVLSI.

2. Literature research on Nano programmable logic fabric
i) Design of PLA using nano-technology

---------------------
"Nanowire-Based Sublithographic Programmable Logic Arrays",
Andre DeHon and Michael J. Wilson, ISFPGA'04

"Design of Programmable Interconnect for Sublithographic 
Programmable Logic Arrays", Andre DeHon, ISFPGA'05

These two papers mainly designed nano PLA architecture 
with nano-wires and molecular switches. Area and delay models
have been presented. A simple design flow has been presented
in the second paper. PLAMAP by deming is used for technology mapping.
VPR is used for placement. A nanoPLA router(npr) is developed for global
routing. This router is a global, directional wire router based
on the pathfinder router. The evaluated parameters are I, P and O,
which are number of inputs, product terms and outputs, respectively.
The minimum area mapping solution for each benchmark is used to compare
to the 22nm LUT-based FPGAs.

--------------
"A Greedy Algorithm for Tolerating Defective Crosspoints in
NanoPLA Design", H. Naeimi and A. DeHon, International Conference
on Field-Programmable Technology (FPT)'04

This paper presented two algorithms that map the logic functions to
nano PLA. The defect rate is assumed as of 20% as observed by HP
crossbar, where 15% molecular switches are defective in a 8x8 
arrays. The logic functions are assumed as of being mapped in terms
of sum of products. For a function with m terms, it can be mapped
to a row with n non-defective switches as long as n is no smaller than
m. The problem is to find a fast algorithm to map a set of functions
to an array considering random defective molecular switches.

The first algorithm is exact. It first detect all the switches and
then solve this problem optimally by solving the maximum bipartite matching
problem. It has been shown that this algorithm has O(n^2) test operations
and O(n^3) computing operations.

The second greedy heuristic algorithm map the function set to nano PLA array
in a greedy fashion. The complexity is o(n^2) test operations and o(n log(n))
computing operations in the worst case. The average complexity can be lowered
to o(n) by bounding the maximum number of variables in logic function.

It has also been shown that 20% defect rate can be tolerated by introduced
13% extra molecular switches.

-----------
The above three papers have been deposited under directory 
/nano-fpga/Nano_Paper/PLA/NanoPLA

ii) Technology mapping for PLAs
---------------
"Performance-Driven Mapping for CPLD Architectures", D. Chen et al,
TCAD'03
This paper presented an performance driven algorithm to map logic functions
to multi-output PLA-style programmable logic fabric. The algorithm includes
three steps, labeling, mapping and packing where packing tries to collapse
the mapped netlist without increasing logic depth. An average of 50% depth
reduction has been achieved when compared to the existing work.

----------------
"Technology Mapping for k/m-macrocell Based FPGAs", J. Cong et al,
ISFPGA'00


"Technology Mapping and Architecture Evaluation for k/m-macrocell Based FPGAs",
J. Cong et al, IODAES'05

These two papers presented the mapping algorithms for single-output PLA-style
FPGAs. The second paper also presented the schematic diagram of a k/m-macrocell
with area and delay model. When compared to LUT-based FPGAs. the k/m-macrocell
based FPGAs can reduce delay by 14%-33%. The larger k/m will lead to smaller
delay and larger area.

-----------
The above papers have been deposited under directory
/nano-fpga/Nano_Paper/PLA/Mapping


3. I've read "An Efficient for Statistical Minimization of Total Power 
under Timing Yield Constraints", M. Mani et al, DAC'05

We may study the statistical Vdd-level assignment to minimize power under
delay constraint compared to deterministic approach. The challenge is that
our case is highly discrete (only two states). And also the delay in CLB
is much complicated compared to logic gates.