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
Viterbi School of Engineering
University of Southern California
Los Angeles, California 90089-1453
Phone: 213-740-0491
Email: guptask [AT] usc [DOT] edu