PORA: A Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design

摘要

The plasmodium of Physarum polycephalum, a large, amoeboid cell, has attracted much attention recently due to its intelligent behaviors in pathfinding, danger avoidance, and network construction. Inspired by the biological behaviors of this primitive organism, in this study, we explore the optimization capability of Physarum polycephalum systematically and present the first Physarum-inspired obstacle-avoiding routing algorithm for the physical design of integrated circuits. We simulate the foraging behaviors of Physarum polycephalum using a novel nutrition absorption/consumption mathematical model, thereby presenting an efficient routing tool called Physarum router. With the proposed routing approach, for a given set of pin vertices and a given set of on-chip functional modules, a rectilinear Steiner minimal tree connecting all the pin vertices while avoiding the blockage of functional modules can be constructed automatically. Furthermore, several heuristics including a divide-and-conquer strategy, a non-pin leaf node pruning strategy, a dynamic parameter strategy, etc., are integrated into the proposed algorithm to fundamentally improve the performance of the Physarum router. Simulation results on multiple benchmarks confirm that the proposed algorithm leads to shorter wirelength compared with several state-of-the-art methods. (C) 2019 Elsevier Inc. All rights reserved.