MANA: A Shortest Path Maze Algorithm Under Separation and Minimum Length NAnometer Rules

作者：Chang Fong Yuan^*; Tsay Ren Song; Mak Wai Kei; Chen Sheng Hsiung

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(10): 1557-1568.

DOI：10.1109/TCAD.2013.2265878

• End-end separation
• minimum length
• nanometer rules
• shortest path

Due to process limitations, wiring rules are imposed on chip layout by foundries. Under nanometer wiring rules, the required separation between two wire ends is dependent on their surrounding wires, and there is a limit on the minimum length of each wire segment. However, traditional shortest path algorithms are not properly designed for these rules. In the paper, we propose a maze routing algorithm, called MANA, capable of finding legal shortest paths under these rules. Experiments with seven industrial cases show that by handling these rules during maze routing, 94% of the violations are prevented on average, and the overall runtime of a commercial router is reduced by 71%. In addition, the total wire length is also reduced by 3% on average.

• 出版日期2013-10
• 单位清华大学