快速拆除閉合環(huán)路和冗余節(jié)點(diǎn)的全局布線(xiàn)方法

基本信息

申請(qǐng)?zhí)?/td> CN202110596295.3 申請(qǐng)日 -
公開(kāi)（公告）號(hào) CN113255283A 公開(kāi)（公告）日 2021-08-13
申請(qǐng)公布號(hào) CN113255283A 申請(qǐng)公布日 2021-08-13
分類(lèi)號(hào) G06F30/3947;G06F30/398 分類(lèi) 計(jì)算；推算；計(jì)數(shù);
發(fā)明人 黃海山;黃志鵬;李旭;汪佳祥;陳偉杰;朱自然;陳建利 申請(qǐng)（專(zhuān)利權(quán)）人 上海立芯軟件科技有限公司
代理機(jī)構(gòu) 福州元?jiǎng)?chuàng)專(zhuān)利商標(biāo)代理有限公司 代理人 張燈燦;蔡學(xué)俊
地址 200120 上海市浦東新區(qū)中國(guó)(上海)自由貿(mào)易試驗(yàn)區(qū)臨港新片區(qū)云漢路979號(hào)2樓
法律狀態(tài) -

摘要

摘要 本發(fā)明涉及一種快速拆除閉合環(huán)路和冗余節(jié)點(diǎn)的全局布線(xiàn)方法，包括如下步驟：S1：輸入一個(gè)有閉合環(huán)路或冗余節(jié)點(diǎn)的線(xiàn)網(wǎng)初始解；S2：計(jì)算線(xiàn)網(wǎng)外邊框、偏移量和線(xiàn)網(wǎng)所有連續(xù)節(jié)點(diǎn)的坐標(biāo)，線(xiàn)網(wǎng)平移至坐標(biāo)系原點(diǎn)；S3：根據(jù)外邊框大小創(chuàng)建boxMap數(shù)組；S4：計(jì)算線(xiàn)網(wǎng)經(jīng)過(guò)的所有邊，存入edgeMap數(shù)組；S5：任意選取一個(gè)pin節(jié)點(diǎn)對(duì)線(xiàn)網(wǎng)進(jìn)行深度優(yōu)先搜索；S6：對(duì)線(xiàn)網(wǎng)進(jìn)行后序遍歷，當(dāng)一個(gè)葉子節(jié)點(diǎn)不是pin節(jié)點(diǎn)時(shí)，刪除該節(jié)點(diǎn)，遞歸回溯刪除所有冗余節(jié)點(diǎn)；S7：對(duì)線(xiàn)網(wǎng)進(jìn)行遍歷，將線(xiàn)網(wǎng)中所有節(jié)點(diǎn)加上偏移量，得到拆除所有閉合環(huán)路和冗余節(jié)點(diǎn)的布線(xiàn)樹(shù)。該方法有利于合理、快速地優(yōu)化布線(xiàn)結(jié)果，降低布線(xiàn)難度。