Automated Extraction for MEMS Devices
Main Participants: Satyandra K. Gupta,
Bikram Baidya, Sashidhar Bellam, and Tamal Mukherjee
Sponsors: This project was sponsored by DARPA and National
Science Foundation.
Keywords: Extraction and MEMS
Motivation
Traditionally, a typical MEMS design project would proceed in the
following way. It starts off with the designer making a sketch of the
schematic of the
design and very basic equations to ensure feasibility of the design.
After
being satisfied with the schematic, the designer proceeds to physical
layout.
The device is then fabricated using the designed layout and the
predetermined process. The device is then tested for functionality.
Errors detected in the
device are used to re-design the layout. Such a design methodology
reduces to a design-fabricate-test loop. Such a methodology is very
expensive and also time consuming as both fabrication and testing are
long and tedious processes.
Use of numerical simulation for detecting complex errors is
computationally expensive but useful as it takes lesser time and is not
as expensive as a trial and error design method. Numerical simulation
involves developing the 3D model from the layout and process
description. The 3D model is assigned material properties depending
upon the process description. The model is then
meshed either manually or by using an automatic mesh generator. The
finite/boundary
element model is simulated using finite or boundary element simulation
over
different domains. This is computationally intensive and interpretation
of
the results requires significant expertise.
VLSI designers often use extraction tools to compare the desired
schematic
with the extracted schematic from the spatial layout of designs. Use of
such
tools in VLSI industry has significantly reduced the number of design
iterations.
This reduces the time to market of a new VLSI product.
As a part of this project, we have developed a new design methodology
that
introduces the concept of extraction during the design loop and
simplifies
the task of design checking. In the new and improved design
methodology,
by reconstructing the design schematic from the layout, the designer is
able
to perform faster simulations on the reconstructed schematic and also
compare
it with the design schematic, thus reducing the need for numerical
simulation
and fabrication iteration loop. We expect that the new design
methodology
will significantly streamline the product development process and
reduce
the time-to-market and the cost of developing MEMS based products.
Main Results Their Anticipated Impact
Atomic Representations: To develop extraction tools for MEMS
designs,
we need geometric algorithms to analyze the spatial layout of the
mechanical portion of the MEMS device and extract a net-list of
mechanical components. Such extracted net-list of mechanical components
can be combined with the electronic component net-list to provide the
complete device schematic. A key step in the extraction of mechanical
elements is classification of various portions of the layout into
structural elements. Because MEMS designs consist of a large number of
elements, computational efficiency of the underlying extraction
algorithm is very important for it to work on complex devices.
Extraction in the MEMS requires geometric reasoning to detect the
mechanical components namely beams, plates, joints, anchors and
fingers. In many MEMS designs, the designer uses rectangles to
represent various components in a
layout. For an element to be recognized, it is necessary that each
rectangle in the layout uniquely represents a structural element. Hence
we need an algorithm
to identify a representation in which each rectangle in the layout
uniquely
represents a structural element. Partitioning the layout and
subdividing the rectangles into many finer pieces so that each
rectangle represents a unique structural element can achieve such
representation. It is important that the algorithm produces an optimal
number of partitions, avoiding over-partitioning which would reduce the
efficiency of the algorithm. To analyze complex MEMS devices, an
extraction algorithm that has a low order polynomial time complexity is
needed.
The method of creating the state in which each rectangle can be
uniquely
classified as a structural element should try to avoid unnecessary
partitioning
of rectangles. The atomic representation developed as a part of this
research
is one such representation where it is possible to uniquely identify
each
rectangle. Therefore, we use atomic representation as the basis for
recognizing
structural elements. The main idea behind the algorithm to create an
irreducible
set of atomic rectangles is as following. It first identifies locations
where
rectangle partitioning might be needed to convert non-atomic rectangles
into
atomic rectangles. After identifying such partitioning locations based
on
various rectangles' neighborhood information, partitioning is carried
out
to produce atomic rectangles. After initial partitioning, a
post-processing
step is carried out to combine those atomic rectangles that can be
combined
together to form larger atomic rectangles and hence resulting in an
irreducible
set of atomic rectangles.
We proved that a set of primary rectangles (i.e., a collection of
non-intersecting
rectangles, where union of any two rectangles cannot be represented as
a
single rectangle) of size N can be described by an atomic set
of rectangles
of size equal to or less than 9N. We have developed an O(N
log N) algorithm for generating the atomic representation to be
used
during extraction of structural elements for MEMS devices. Atomic
representations
can be exploited in the following two ways:
- In the same amount of time they can be used to solve bigger
problems.
This would allow the extraction and emulation of more complex and
larger
MEMS designs using the same amount of computing resources. This is
particularly
important as complexity of the design problems increase, which requires
more
complex MEMS designs to be used.
- Since extraction can be carried out faster, the result is faster
schematic
extraction and device simulation. So if the design team is looking to
evaluate
many options and since each option can be evaluated more quickly as a
result
of this work, more options can be evaluated in the same amount of time.
This
would allow MEMS designers to explore and evaluate various design
options
for a given problem using the same amount of resources.
Development of Extraction Rules and Algorithm: As part of this
project,
we have developed a novel extraction algorithm. Based on a set of
heuristics,
our extraction algorithm classifies the atomized rectangles as beams,
plates,
fingers, anchors depending on the geometrical attributes, neighbor
information
and inter-level connectivity.
The first step in detection of structural elements is to detect
potential anchor elements. These are detected using information from a
non-structural layer, ANCHOR1. The elements of the atomic layout that
overlap the rectangles from the ANCHOR1 layer are marked as potential
anchor elements. Potential mass/plate elements are detected using
information from the DIMPLE and HOLE1 layers. Atomic layout rectangles
that overlap with DIMPLE or HOLE1 layer rectangles
are marked as potential mass/plate elements.
Fingers are detected using neighborhood information and geometrical
information
of the rectangles in the structural layer. Fingers are defined as
rectangles
that are bound on one of their shorter edges and its other three edges
are
not bound. All rectangles in the atomic layout that match the above
conditions
are marked as fingers. Next all unmarked structural rectangles are
analyzed
to look for beams. Beams are defined as rectangles with two of its
shorter
edges bound and its longer edges unbound. Rectangles matching these
criteria
are marked as beams.
Joints are described as rectangles that are connected to two or more
joints
or beams. This is followed by recognition of rest of the mass and
anchor
rectangles. Already marked anchor and mass elements are recursively
expanded
into unmarked rectangles in all directions. Thus if an unmarked
rectangle
is connected to a mass/anchor rectangle through unmarked rectangle, is
marked
accordingly. All structural elements are recognized using the above
methods.
Structural elements are grouped to define various MEMS components such
as
comb drives and springs. Comb drives consist of integrated comb fingers
places
on electrically disconnected rotor and stator forming a capacitive
arrangement
used for sensing or actuating mechanical motion. Comb drive extraction
starts
with a connectivity analysis of the set of recognized fingers. Fingers
having
the same electrical connectivity are given the same connectivity
number. Fingers
are then sorted into buckets based on their orientation. Each such
bucket
is then checked for uniformity of the fingers with respect to its
geometric
parameters. The buckets are partitioned whenever any non-uniformity is
found
in any of these parameters. A set of overlapping pairs with different
electrical
connectivity numbers will result in a comb drive.
Springs are composed of beams and joints, and connect the suspended
plate
to the anchors. The spring detection routine uses an input from a
spring
library, which stores the springs in the form of a graph. Any new
spring
can be recognized if the corresponding graph is present in the library.
The
spring library is a collection of finite state machine (FSM) for each
of
the springs defined in the library.
We have successfully tested our extraction algorithm with numerous
examples of varying degree of complexity. Using our algorithm we have
successfully identified known errors in the layouts as well as
discovered errors in layout that were not noticed by the designers.
Related Publications
The following papers provide more details on the above-described
results.
- B. Baidya, S. K. Gupta, and T. Mukherjee. An extraction based
verification methodology for MEMS. Journal of Microelecromechanical
Systems, 11(1):2--11, 2002.
- S. Bellam and S.K. Gupta. An efficient geometric algorithm for
extracting structural elements to facilitate automated MEMS extraction.
Journal of
Computing and Information Science in Engineering, 3(2):155--165,
June
2003.
Some of these papers are available at the publications
section of the website.
Contact
For additional information and to obtain copies of the above papers
please contact:
Dr. Satyandra K. Gupta
Department of Mechanical Engineering and Institute for Systems Research
2135 Martin Hall
University of Maryland
College Park, Md-20742
Phone: 301-405-5306
FAX: 301-314-9477
WWW: http://www.glue.umd.edu/~skgupta/