CAJ | 학술논문

该文提出了一种新的划分算法,算法中引入可变线网权重.由于超图(hypergraph)中的线网连接节点数一般多于两个,为了充分将线网增加的权重作用到与该线网相连的所有节点上去,线网增益采用了概率增益模型.该算法与原有算法相比较,可以有效地让电路的划分跳出局部最小,结果有较大的改进,特别是当电路规模比较大的时候,改进更明显.由于采用概率增益模型,出现浮点数,节点增益的存储采用了平衡二叉树(balanced binary tree),因此算法的速度相对于FM算法有所下降,但是时间复杂度仍然接近为线性复杂度,时间复杂度为O(Plog2(n))(P为电路所有逻辑单元的引脚数之和,n为电路的逻辑单元数).
해문제출료일충신적화분산법,산법중인입가변선망권중.유우초도(hypergraph)중적선망련접절점수일반다우량개,위료충분장선망증가적권중작용도여해선망상련적소유절점상거,선망증익채용료개솔증익모형.해산법여원유산법상비교,가이유효지양전로적화분도출국부최소,결과유교대적개진,특별시당전로규모비교대적시후,개진경명현.유우채용개솔증익모형,출현부점수,절점증익적존저채용료평형이차수(balanced binary tree),인차산법적속도상대우FM산법유소하강,단시시간복잡도잉연접근위선성복잡도,시간복잡도위O(Plog2(n))(P위전로소유라집단원적인각수지화,n위전로적라집단원수).