Keywords
|
FM based hybrid algorithm, area reduction, digital VLSI circuit partitioning algorithm |
INTRODUCTION
|
Partitioning is the first design step towards the production and fabrication of a circuit design. The CAD plays a vital role in modeling the algorithms with minimal effort and efficient logic design optimization [1].The application logic is mapped as a graph and the connectivity of all the elements of the design are translated to non directed graph. Then the soft and hard blocks are decided. The choice of the design style as full custom or semi-custom ASICs depends on the intended functionality of the chip, time to market and the total number of chips to be manufactured. |
The Design styles can be seen as to cater to the differing needs of the application development purpose. The full custom provides compact layouts for high performance designs and FPGA is completely prefabricated and requires no user specific fabrication steps [2]. This necessitates the need for unification of these consecutive and distinctly irreversible stages of the physical design. VLSI physical design involves the division of a circuit into smaller parts for ease of design and layout [2,3]. The main objectives of circuit partitioning include minimization of number of interconnections between the partitions, minimization of delay due to interconnections between partitions, and ratio-cut minimization [4, 12]. The circuit under consideration is considered as a graph. |
A sample graph is shown in the Fig [1].The graph is the representation of the test circuit of ACM /SIGDA [15] and has 7 gates. Its a small size test circuit. The graph has all the circuit components expressed as nodes and the connections as edges of the graph. The circuit under consideration has 5 inputs and 2 outputs. The inputs and the outputs are connected to the gates. Partition is also referred to as a cut [13, 14]. The cost of partitioning is called the cut size [6,7] which is the number of hyper edges crossing the cut. The FM algorithm has no basic requirement that the two Partitions be of same size. So when there is swapping done between the partition 1 and 2.The gain of each swap is calculated in terms of number of nets crossing the partitions. |
RELATED WORK
|
In the past decade there are many works emphasizing the need of miniaturization. The partitioning stage forms the base of the physical design process. In the earliest work on graph theory, nodes have been modeled and partitioned using algorithms to minimize the distance and form a cluster .These algorithms are move based and the earliest algorithm focused on mutual swapping of nodes between the partitions [2,8]. This approach did not work for the partitions with odd number of nodes and the partitions of different sizes were accommodated in the further work done by Fidduccia and Mathysses [3, 9].The consolidated survey on the importance of area parameter minimization of VLSI applications [4,5] suggests that, there is ample scope of algorithmic choices for reducing the design area than the default optimized design made available by the CAD tool. |
PROPOSED ALGORITHM
|
A. Design Considerations: |
• Initial circuit chosen is to be converted to directed graph. |
• Difference in the number of inward connections to outward connections is calculated as gain. |
• Keeping track of previous area. |
• Considered all possible partitioning and making gain nearing 1. |
B. Description of the Proposed Algorithm: |
Aim of the proposed algorithm is to reduce the area of the VLSI circuit through hybrid genetic algorithm approach during CAD design of the circuit. The proposed algorithm is consists of four main steps. |
Step 1: Calculating the area of the VLSI circuit before applying the algorithms |
Step 2: Convert the circuit to nodes and applying the algorithms. |
Step 3: Calculate the area for the optimized circuit for the partitioning value. |
Step 4: Change the partitioning value and obtain the area reductions for the optimized circuit. |
PSEUDO CODE
|
Step 1: Convert the circuit to nodes and map the adjacency matrix. |
Step 2: Implement the VLSI circuit and calculate the area parameter. |
Step 3: Feed it as input to the FM +mincut +GA algorithm in C language. |
Step 4: Check the below condition for convergence. |
If ( mindis1 = mindis) |
the area is optimal so no swapping of the nodes between the partitions |
else |
swap the nodes and calculate distance |
Step 5: Implement the new optimized VLSI circuit and calculate the area parameter. |
Step 6: Go to step 3 with different partitioning value for same circuit. |
Step 8: End. |
SIMULATION RESULTS
|
In this paper, to circuit C17 netlist, the move based algorithm of Fidducia Matthyses [FM] is applied in C Language, then the mincut algorithm merged GA [10,11] is applied to the partitioning result. This step uses the partition stage output to perform the optimization. The effect of the hybridization on the physical parameter of area of the circuit is calculated from the synthesis report of the EDA tools. The methodology consists of obtaining the netlist from the graph, then applying the algorithms and optimizing the partitioning result. Using Cadence EDA tool area report is generated before and after application of this algorithm, to assess the efficiency of the algorithm. |
The effect of FM and mincut algorithms on C17 and C1908 test circuits is shown in Fig [2].The effect on the area of the application is seen as about 30% on an average. For various partitions the area optimization also varies. The criteria for the genetic algorithm to converge, is defined by the mincut algorithm. It is also observed that the size of the circuit does not affect the performance of the algorithm, but the number of partitions vary the optimization outputs. |
CONCLUSION AND FUTURE WORK
|
The implementation of hybrid genetic algorithm based FM-Mincut algorithm on a series of digital circuits and benchmarks, suggest that there is a lot of advantages in unifying the partitioning and placement stages. The area optimization can be more accurate before further physical design stages. The optimization of the area can be obtained by employing greedy Heuristic algorithms to the same level of physical design in continuation with hybrid algorithm discussed in the paper. This approach may provide further area optimization to the circuit. The applications of such approach, has greater impact on designs of biomedical circuits and wearable sensors where the size of the application is a major design constraint. |
|
Figures at a glance
|
|
|
Figure 1 |
Figure 2 |
|
|
References
|
- Christopher J. Augeri Hesham H. Ali, “New Graph-Based Algorithms for Partitioning VLSI Circuits”, In proceedings of International symposium on Circuits and systems ,ISCAS, 2004,vol-4, pp:521-524,2004.
- B.W. Kerhinghan, S. Lin, “An efficient heuristic procedure for partitioning graphs”, Bell System Tech. Journal, Vol. 49, pp. 291 – 307,1970.
- Andrew E. Caldwell, Andrew B. Kahng, and Igor L. Markov, “Design and Implementation of Move-Based Heuristics for VLSI Hypergraph Partitioning”, ACM, 2000.
- Rajine Swetha R, B. Shekar Babu, Sumithra Devi K.A, “A Survey of Various Algorithms for Vlsi Physical Design”, World Academy of Science, Engineering and Technology,Vol:5 2011-03-21, International Science Index Vol:5, No:3, 390-395,2011.
- Rajine Swetha R, et al, “Comparison of Hierarchical Mixed-Size Placement Algorithms for VLSI Physical Synthesis”, CSNT '11 Proceedings of the 2011 International Conference on Communication Systems and Network Technologies, IEEE Computer Society Washington, DC, USA,pp 430-435.
- David A. Papa and Igor L. Markov, “Hypergraph partitioning and clustering”, In Approximation Algorithms and Metaheuristics,CRC press, ISBN:61-1-61-19,2007.
- Shanavas, I.H., Gnanamurthy, R.K.; Thangaraj, T.S, “A Novel approach to find the best fit for VLSI Partitioning – Physical Design”; International Conference on Advances in Recent Technologies in Communication and Computing (ARTCom), 2010.
- Naveed Sherwani, “Algorithms for VLSI Physical Design and Automation”, third edition, Springer (India) Private Limited, New Delhi, ISBN: 0792383931, 2005.
- M. Burstein and M.N. Youssef.,” Timing influenced layout design.”, In Proceedings of the Design Automation Conference, Albuquerque, NM, pp. 124–130, 1984.
- A.E. Dunlop, V.D. Agrawal, D.N. Deutsch, M.F. Jukl, P. Kozak, and M. Wiesel. “Chip layout optimization using critical path weighting “, In Proceedings of the Design Automation Conference, Las Vegas, NV, pp. 133–136, 1985.
- H.Yu, X.Hing, and Y. Cai,MMP: “A novel placement algorithm for combined macro block and standard cell layout design”, Proceedings of IEEE Asia and South Pacific Design Automation Conference , pp. 271–276, 2000.
- Mehmet Can Yildiz , Patrick H. Madden “Improved Cut Sequences for Partitioning Based Placement” , Proceedings of Design Automation Conference (DAC’01),.ISBN:1-58113-297-2, 2001.
- Charles J Alpret, Dinesh Metha and Sachin S Sapatnekar, “Handbook of Algorithms for physical design automation” ,CRC Press Publishing, 2008
- Sabih H. Gerez, “Algorithms for VLSI Design Automation”, Wiley INDIA, ISBN: 10: 0471984892, 2007.
- www.cbl.net
|