Investigations on circuit level Evolutionary partitioning algorithms For vlsi physical design automation

Abstract

Designing the circuit partitioning becomes extensively interconnect dominated and holds unmanageable difficulties; hence it is considered one of the pivotal optimization issues in Computer-aided Design (CAD) automation. The trait and the practicability of automatic placement, routing function and procedures are profoundly estimated on the partitioning quality solutions. Moreover, the present partitioning model techniques analyze and identify the pros and cons and recommend new effective partitioning techniques. This thesis presents the novel partitioning methods widely utilized in large scale designs, and the main goal is to enhance the partitioning solutions quality and feasibility. Primarily, a hmetis based circuit-partitioning presented that is emulated and directed by visual hierarchies. Then, a hypergraph partitioning (netlist) and a design hierarchy are logically utilized to partition the Kernighan-Lin (KL) algorithm. Furthermore, stability is defined as an additional measure in quality for partitioning solutions. And a modification based partitioning methodology is executed. newlineIn addition, the provided previous results on partitioning utilizing an original hypergraph (netlist) and mutated hypergraph (netlist), a novel cost function and a parallel factor are determined to generate partitions on a hyper graph, which is identical to the original partition. Thirdly, a new evolutionary-based partitioning approach is proposed that is aware of the minimum cut size and required interconnection: a novel and efficient evolutionary partitioning algorithm utilized based on Graph Cellular Automata (GCA). In the proposed GCA, the concept of graph theory combined with cellular automata theory is used to get an optimum solution newline