在自动配线设计之配线路径探索方法及记录有配线路径探索程式之记录媒体

摘要

本发明旨提供一种于LSI等之自动配线设计时,降低无法配线之配线之发生机率,提高全部配线之配线完成率。为达成前述目的,依本发明系在使用迷宫法进行LSI等之自动配线设计时,对配线区域20之各格子行抽出配置元件21A、21B所划分之部分区域31~39,对于这些部分区域计算表示可配线之程度之裕度。而,在例如网C无法配线之情况,将配置元件21A令在同一行向正上移动一个格子。因而,网C变成可配线。在网A与网B之配线所使用之部分区域31、34,其「裕度」随着该配置元件21A之移动而变成负("-l")，但是将网B之配线和别的路径再配线。因此,系在配线区域有高度限制之情况,也在行方向不增加格子的满足高度限制，完成全部网A~E之配线。

主权项

1.一种在自动配线设计之配线路径探索方法,于进行LSI等之自动配线设计时,使用在分割成沿格子列与格子行方向排列之多个格子之配置区域,每前进到各格子就加上费用而计算配线路径费用的迷宫法,以探索配线路径,其特征在于具备:部分区域抽出处理,对该配线区域之各格子列或各格子行,抽出藉由配置于该配线区域之电晶体等配置元件与配线禁止区域而分割好之各格子列或各格子行之多个部分区域;资料产生处理,对在该部分区域之抽出处理所抽出之各部分区域,产生按照可通过之配线条数和已配线之通过条数之资料;及费用计算处理,依照在该资料产生之处理所产生之资料,每前进到各格子就加上费用。2.一种在自动配线设计之配线路径探索方法,在进行LSI等之自动配线设计时,使用在分割成沿格子列与格子行方向排列之多个格子之配置区域,按照配置于该配线区域之电晶体等配置元件之端子之连接要求,每前进到各格子就加上费用而计算配线路径费用之迷宫法,以探索配线路径,其特征在于具备:移动处理,将该配置元件设为可移动,当变成无法配线时,如可配线之格子集中般移动该配置元件;及再计算处理,在该移动处理后,再计算配线路径费用。3.一种在自动配线设计之配线路径探索方法,在进行LSI等之自动配线设计时,使用在分割成沿格子列与格子行方向排列之多个格子之配置区域,按照配置于该配线区域之电晶体等配置元件之端子之连接要求,每前进到各格子就加上费用而计算配线路径费用之迷宫法,以探索配线路径,其特征在于具备:部分区域抽出处理,对该配线区域之各格子列或各格子行,抽出藉由配置元件与配线禁止区域而分割好之各格子列或各格子行之多个部分区域;资料产生处理,对在该部分区域之抽出处理所抽出之各部分区域,产生按照可通过之配线条数和已配线之通过条数之资料;费用计算处理,依照在该资料产生之处理所产生之资料,每前进到各格子就加上费用;移动处理,将该配置元件设为可移动,当变成无法配线时,如可配线之格子集中般移动该配置元件;及再计算处理,于该移动处理后,再度进行该资料产生之处理与该费用计算处理后,再计算配线路径费用。4.如申请专利范围第1或3项之在自动配线设计之配线路径探索方法,其中,该资料产生之处理系对各部分区域,计算自构成部分区域之格子数减去已配线所使用之格子数后之裕度,将该裕度作为该资料。5.如申请专利范围第2或3项之在自动配线设计之配线路径探索方法,其特征在于该配置元件横跨多个格子行或格子列。6.如申请专利范围第2或3项之在自动配线设计之配线路径探索方法,更包含:判定处理,判定该移动处理之结果,是否有已配线之通过条数超过了可配线之配线条数之部分区域;及再配线处理,若该判定处理之结果,有已配线之通过条数超过了可配线之配线条数之部分区域时,将通过该部分区域之配线再配线。7.一种记录有在自动配线设计之配线路径探索程式之记录媒体,该程式系为于利用电脑进行LSI等之自动配线设计时,使用在分割成沿格子列与格子行方向排列之多个格子之配置区域,每前进到各格子就加上费用而计算配线路径费用之迷宫法以探索配线路径的配线路径探索程式,其特征在于:对该配线区域之各格子列或各格子行,抽出藉由配置于该配线区域之电晶体等配置元件与配线禁止区域所分割好之各格子列或各格子行之多个部分区域;对在该部分区域之抽出处理所抽出之各部分区域,产生按照可通过之配线条数和已配线之通过条数之资料;依照在该资料产生之处理所产生之资料,每前进到各格子就加上费用。8.一种记录有在自动配线设计之配线路径探索程式之记录媒体,该程式系为于利用电脑进行LSI等之自动配线设计时,使用在分割成沿格子列与格子行方向排列之多个格子之配置区域,按照配置于该配线区域之电晶体等配置元件之端子之连接要求,每前进到各格子就加上费用而计算配线路径费用之迷宫法以探索配线路径的配线路径探索程式,其特征在于:当变成无法配线时,移动该配置元件使配线之格子集中;及于该配置元件移动后,再计算配线路径费用。9.一种记录有在自动配线设计之配线路径探索程式之记录媒体,该程式系为于利用电脑进行LSI等之自动配线设计时,使用在分割成沿格子列与格子行方向排列之多个格子之配置区域,按照配置于该配线区域之电晶体等配置元件之端子之连接要求,每前进到各格子就加上费用而计算配线路径费用之迷宫法,以探索配线路径的配线路径探索程式,其特征在于:对该配线区域之各格子列或各格子行,抽出藉由配置元件与配线禁止区域所分割好之各格子列或各格子行之多个部分区域;对该所抽出之各部分区域,产生按照可通过之配线条数和已配线之通过条数之资料;依照该所产生之资料每到各格子就加上费用;当变成无法配线时,移动该配置元件使可配线之格子集中;及于该配置元件移动后,再度产生该资料与计算该费理,而后再计算配线路径费用。10.如申请专利范围第7或9项之记录有在自动配线设计之配线路径探索程式之记录媒体,其中,于产生该资料时,对各部分区域计算自构成部分区域之格子数减去已配线所使用之格子数后之裕度,将该裕度作为该资料。11.如申请专利范围第8或9项之记录有在自动配线设计之配线路径探索程式之记录媒体,其特征在于:判定该配置元件之移动之结果,是否有已配线之通过条数超过了可配线之配线条数之部分区域;该判定之结果,若有已配线之通过条数超过了可配线之配线条数之部分区域时,即将通过该部分区域之配线再配线。图式简单说明:第一图系显示本发明之实施例1之配线路径探索方法之处理步骤之流程图。第二图系显示实施例1之配线路径探索方法之高度限制与连接资料之图。第三图系说明在实施例1之配线路径探索方法之部分区域裕度计算处理之图。第四图系显示在实施例1之配线路径探索方法移动了配置元件之具体实例之图。第五图系显示实施例1之配线路径探索方法之配线结果之图。第六图系显示习知例之配线路径探索方法之处理步骤之流程图。第七图系显示习知例之配线路径探索方法之探索过程之图。第八图(a)系显示习知例之配线路径探索方法之配线结果之图,(b)系显示简化了该结果之结果之图。第九图系显示在习知例之配线路径探索方法使用按照配线间距均匀分割进行标准单元之配线设计之结果之图。第十图系在该习知例之配线路径探索方法说明因格子数不足而未完成配线之情况之图。第十一图系显示在该习知例之配线路径探索方法说明设置比配线间距窄之格子而完成配线之情况之图。第十二图系显示在本发明之实施例2之配线路径探索方法之配线结果之图。第十三图系显示和实施例2之配线路径探索方法之配线结果比较之本发明申请人提议之配线路径探索方法之配线结果之图。