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
Keywords: Extraction and MEMS
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.
being satisfied with the schematic, the designer proceeds to physical
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
element model is simulated using finite or boundary element simulation
different domains. This is computationally intensive and interpretation
the results requires significant expertise.
VLSI designers often use extraction tools to compare the desired
with the extracted schematic from the spatial layout of designs. Use of
tools in VLSI industry has significantly reduced the number of design
This reduces the time to market of a new VLSI product.
As a part of this project, we have developed a new design methodology
introduces the concept of extraction during the design loop and
the task of design checking. In the new and improved design
by reconstructing the design schematic from the layout, the designer is
to perform faster simulations on the reconstructed schematic and also
it with the design schematic, thus reducing the need for numerical
and fabrication iteration loop. We expect that the new design
will significantly streamline the product development process and
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
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
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
The method of creating the state in which each rectangle can be
classified as a structural element should try to avoid unnecessary
of rectangles. The atomic representation developed as a part of this
is one such representation where it is possible to uniquely identify
rectangle. Therefore, we use atomic representation as the basis for
structural elements. The main idea behind the algorithm to create an
set of atomic rectangles is as following. It first identifies locations
rectangle partitioning might be needed to convert non-atomic rectangles
atomic rectangles. After identifying such partitioning locations based
various rectangles' neighborhood information, partitioning is carried
to produce atomic rectangles. After initial partitioning, a
step is carried out to combine those atomic rectangles that can be
together to form larger atomic rectangles and hence resulting in an
set of atomic rectangles.
We proved that a set of primary rectangles (i.e., a collection of
rectangles, where union of any two rectangles cannot be represented as
single rectangle) of size N can be described by an atomic set
of size equal to or less than 9N. We have developed an O(N
log N) algorithm for generating the atomic representation to be
during extraction of structural elements for MEMS devices. Atomic
can be exploited in the following two ways:
Development of Extraction Rules and Algorithm: As part of this
we have developed a novel extraction algorithm. Based on a set of
our extraction algorithm classifies the atomized rectangles as beams,
fingers, anchors depending on the geometrical attributes, neighbor
and inter-level connectivity.
- In the same amount of time they can be used to solve bigger
This would allow the extraction and emulation of more complex and
MEMS designs using the same amount of computing resources. This is
important as complexity of the design problems increase, which requires
complex MEMS designs to be used.
- Since extraction can be carried out faster, the result is faster
extraction and device simulation. So if the design team is looking to
many options and since each option can be evaluated more quickly as a
of this work, more options can be evaluated in the same amount of time.
would allow MEMS designers to explore and evaluate various design
for a given problem using the same amount of resources.
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
of the rectangles in the structural layer. Fingers are defined as
that are bound on one of their shorter edges and its other three edges
not bound. All rectangles in the atomic layout that match the above
are marked as fingers. Next all unmarked structural rectangles are
to look for beams. Beams are defined as rectangles with two of its
edges bound and its longer edges unbound. Rectangles matching these
are marked as beams.
Joints are described as rectangles that are connected to two or more
or beams. This is followed by recognition of rest of the mass and
rectangles. Already marked anchor and mass elements are recursively
into unmarked rectangles in all directions. Thus if an unmarked
is connected to a mass/anchor rectangle through unmarked rectangle, is
accordingly. All structural elements are recognized using the above
Structural elements are grouped to define various MEMS components such
comb drives and springs. Comb drives consist of integrated comb fingers
on electrically disconnected rotor and stator forming a capacitive
used for sensing or actuating mechanical motion. Comb drive extraction
with a connectivity analysis of the set of recognized fingers. Fingers
the same electrical connectivity are given the same connectivity
are then sorted into buckets based on their orientation. Each such
is then checked for uniformity of the fingers with respect to its
parameters. The buckets are partitioned whenever any non-uniformity is
in any of these parameters. A set of overlapping pairs with different
connectivity numbers will result in a comb drive.
Springs are composed of beams and joints, and connect the suspended
to the anchors. The spring detection routine uses an input from a
library, which stores the springs in the form of a graph. Any new
can be recognized if the corresponding graph is present in the library.
spring library is a collection of finite state machine (FSM) for each
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.
The following papers provide more details on the above-described
Some of these papers are available at the publications
section of the website.
- 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.
Computing and Information Science in Engineering, 3(2):155--165,
For additional information and to obtain copies of the above papers
Dr. Satyandra K. Gupta
Department of Mechanical Engineering and Institute for Systems Research
2135 Martin Hall
University of Maryland
College Park, Md-20742