A genetic algorithm for over-the-cell and channel area optimization

Presents a new genetic algorithm (GA) based router which concurrently optimizes both areas over-the-cell and the main channel. The GA is guided through the solution space by a set of heuristics/rules which are executed during the evaluation of prospective solutions. The GA commences by identifying multi-terminal net circuit segments (including side nets) for over-the-cell routing, and places these on tracks over-the-cell according to horizontal constraints. The algorithm proceeds to route the remaining net circuits inside the main channel area subject to horizontal and vertical constraints. The over-the-cell routing procedure within the GA ensures that only two terminal nets are left in the main channel after its action. This reduces the amount of congestion in the main channel area. The algorithm is tested on several internationally well-known benchmark examples, and is found to produce significantly better routing solutions than previous approaches to the problem to date