Keywords

1 Introduction

Due to the progress of the semiconductor industry, the scale of VLSI circuits dramatically increases, which makes hierarchical representation of circuit crucial for computer-aided design tools and designer himself. The main levels of abstraction of VLSI circuit are: transistor-level circuit describes VLSI as a set of transistors and their interconnections; gate-level consists of gates formed from transistors, each gate has its function; functional or behavioral level is represented by functional blocks, which could be grouped in to the blocks of the next hierarchical level.

  • Verification of a circuit layout (Abadir 1990). Due to the complexity of VLSI producing cycle there could be different fails on any step of the process.

  • Speeding up circuit simulation (Huang 1995). Design-for-testability and built-in-self-test (Jolly 2002), registers can be selected as test resources (test pattern generators, scan registers and test response compactors) which can reduce the complexity of achieving a testable design.

  • Floorplanning and resynthesis (Kundu 1998; Jindal et al. 2010).

Existing subcircuit extraction algorithms appearing in literature can be classified into three categories:

  • Structural recognition (Lester 1998);

  • Pattern matching (Graeb 2001; Pelz and Roettcher (1994); Ohlrich 1993);

  • Combination of structural recognition and pattern matching (Yang 2006).

Structural recognition methods divide the CMOS circuits into channel connected-components (CCCs). In general, structural recognition algorithms cannot handle irregular-structured blocks, it is hard to define them in terms of rules.

Pattern matching is the technology independent algorithms where circuit is represented as a graph, functional groups of elements are subgraphs, subgraph isomorphism is used to find the elements groups which are similar to previously defined functional pattern.

The combination of two previous technics allows speeding up the process by detecting regular logical structures and generating the hybrid graphs of transistors and gates netlist. Then pattern-matching algorithm is applying to extract the high-level structural representation. Using the patterns is not possible if there is no information about structure or function of high-level hierarchy of the VLSI circuit. Another problem is pattern blocks represented by next hierarchical level from the gate-level. In this case much effort has been dedicated to matching large circuit with pattern which consists of ten or more vertices.

In this paper, we propose pattern-free, technology independent method for extracting of functional blocks with irregular structure. The first step is structural analysis of transistor-level VLSI circuit, then TLS are extracting from transistor-gate-level VLSI circuit. The third step is pattern matching with extracted (from gate-TLS-level VLSI circuit) TLS and library or manual TLS analysis. Then it is possible to obtain functional blocks from gate-level tangled logic structures by pattern matching or any other technics. Genetic algorithm for functional block initial vertices search could be used on this step. The advantages of the method are possibility of pattern-free functional analysis of irregular structures. The first step could be performed without structural analysis which is dependent on technology of VLSI design.

The remainder of this paper is organized as follows. An overview of related work is given in Sect. 2. Section 3 describes method and its time complexity analysis. Section 4 presents experimental results on real sample. Concluding remarks are given in Sect. 5.

2 Related Work

In (Yang 2006) FROSTY reads in a transistor-level CMOS netlist (object circuit) and a library file. The library file contains user-specified high-level functional blocks to be recognized from the object circuit and the netlist for each functional block (called subcircuit). The whole FROSTY flow is divided into two steps: in Step 1, the program tries to identify all CMOS gate with regular structure, converting the object circuit to mixed gate-level and transistor-level object graph; in parallel, the program transfers each library-defined subcircuit to a mixed gate-level and transistor-level subgraph too; in Step 2, pattern matching is applied to recognize all subgraphs from the object graph. After the above gate recognition and functional blocks extraction, FROSTY outputs VHDL or Verilog model with user-defined blocks in the library.

In practice, FROSTY pre-defines a library, which contains all kinds of functional blocks like flip-flops, adders, latches and so on. The disadvantages of this method are compilation of the functional block library and pattern matching process in Step 2. FROSTY tries to match all the library-defined subcircuits in the object circuit. Unfortunately, if one subcircuit does not exist in the object circuit, the program still spends CPU time in order to find it. In some cases library is unknown and this step could not be used.

In (Jindal et al. 2010) Jindal et al. proposes a straightforward algorithm (tangled-logic finder) to identify GLTs. This method consists of three phases: Phase I: linear ordering generation; Phase II: initial candidate GTL generation; Phase III: GTL refinement and pruning.

Tangled-logic finder does not need any library to find functional groups. The purpose of this method is to find TLS but not every TLS is a functional block. In this paper, we propose to set additional parameters to the Tangled-logic finder algorithm to specify our search for better functional partition. The combination of structural analysis, pattern matching and TLS extracting make up the deficiency of each method used separately.

3 A Method to Find Functional Groups

Basing on methods and algorithms described in Sect. 2, we propose an algorithm to find functional group from transistor-level VLSI circuit. This method consists of five steps:

  • Step 1: Structural analysis of transistor-level VLSI circuit.

  • Step 2: TLS extracting from transistor-gate-level VLSI circuit.

  • Step 3: Pattern matching with extracted gate-TLS-level TLS and library or manual TLS analysis.

  • Step 4: Pattern matching with extracted gate-level TLS and library or manual TLS analysis. Genetic algorithm is used for functional block initial vertices search.

  • Step 5: Repeat Step 4 until the necessary functional level of hierarchy will be obtained.

Step 1 is described in (Yang 2006). In step 2 TLS extracting method (that is described in Sect. 2) could be more efficient when the best candidate is chosen due to best GTL value.

Step 3 is the conversion of the gate-TLS-level VLSI circuit into the gate-level VLSI circuit. Obtaining library functional block from TLS is less complicated process then from transistor-gate-level VLSI circuit. If library of functional patterns is available, we do not need to match all patterns with all circuit. Each extracted TLS will have a set of structural parameters for example number of TLS elements, elements interconnections. Comparing TLS structural parameters with same parameters of pattern functional blocks simplifies this step. After the third step we will obtain the gate-level VLSI circuit.

Using common chains data on step 4 the higher-hierarchical functional levels of VLSI circuit could be extracted. In the next section we will show modified steps of functional extraction on real VLSI circuit sample. At this step, genetic algorithm performs the search of those initial vertices that will allow us to obtain functional blocks. The correct choice of the initial vertex determines the result of the functional block extraction. In (Moharam 2017) genetic algorithm uses on graph tasks. In (Zhang 2017), a genetic algorithm is used to extract a subset of vertices in a graph.

The main steps of search with genetic algorithm are:

  1. 1.

    Analyses of scheme graph connectivity. Each of the connectivity components considers separately.

  2. 2.

    Random selected vertices are the individuals of the population. Blocks begin to be built from each vertex using the nGTLS metric.

  3. 3.

    The fitness function is the minimum value of the nGTLS function, which was calculated for a block constructed on the basis of the current individual after several steps.

  4. 4.

    The individuals of the population are ranked according to the fitness function.

  5. 5.

    The lower quarter of the population is excluded from consideration.

  6. 6.

    Among the better half, pairs are randomly formed. Those pairs complement the population after the crossing.

  7. 7.

    The crossing procedure: finding the shortest way between two vertices; the new individual to be added to the population is the vertex situated in the middle of the shortest way.

  8. 8.

    The supplemented population passes through a mutation. If an individual mutates, it is excluded from the population. New individual adds to its place corresponding to one of the neighboring vertices of the one that underwent a mutation.

  9. 9.

    The new generation goes from steps 3 to 8. The algorithm completes its work after the predetermined number of generations.

4 Experimental Results

For nGTLS metrics obtained by old and new methods are shown on Fig. 1 new method curve has precise and more accurate minima than initial method curve. Curves on Fig. 2 describe the group of tangled logic (GTL) extracted from gate-level VLSI circuit. Both metrics curves have minima when group size is 22 elements. New nGTLS metric curve is more plane than old metric at the beginning.

Fig. 1.
figure 1

Transistor-level VLSI circuit TLS groups

Full size image
Fig. 2.
figure 2

GTL from gate-level VLSI circuit

Full size image

5 Conclusions

This paper introduces a new method of automatic transistor-level VLSI circuit analysis, which combines structural analysis, pattern matching and improved TLS extraction. The hierarchical representation of VLSI circuit can help with verification of a circuit layout, speeding up circuit simulation, design-for-testability and built-in-self-test, floorplanning and resynthesis of VLSI. Our method extracts higher hierarchical functional blocks from transistor-level VLSI circuit with regular and irregular structure. TLS blocks speed-up the pattern matching and allow to obtain functional block without a pattern. Due to GTL-based linear ordering and genetic algorithm TLS extracting routing has higher degree of accuracy.

On the first step, transistors are grouped by their structure. Groups with irregular structure are highly interconnected to each other. Detecting Tangled Logic Structures (TLS) with a GTL-depended linear ordering and genetic algorithm divides the circuit due to its functional structure and forms the gate-level VLSI circuit. High-level functional blocks in circuit description consist of gate-level cells groups, which are also highly interconnected. After TLS-blocks extracting, it is possible to describe their function. TLS-blocks are smaller, represent a cell of high-level circuit, and are thus more suitable for further functional circuit analysis than a gate-level VLSI circuit.

Future works seek to expand the technics of technology- and library- independent VLSI circuit analysis, and to figure out the new ways of pattern matching for TLS groups.