專利授權區國立清華大學國際產學營運總中心 Operations Center for Industry Collaboration

搜尋專利授權區

關鍵字

» 新增關鍵字

選單

專利授權區

專利授權區
專利名稱(中)	用於積體電路佈局之繞線後階段冗餘介層洞插入之方法
專利家族	中華民國：I323416 美國：7,302,662
專利權人	國立清華大學 100%
發明人	王廷基,李光曜
技術領域	電子電機

專利摘要(中)
本發明提供一種用於積體電路佈局之繞線後階段冗餘介層洞插入之方法。該方法首先自一繞線後階段設計建構一互斥關係圖，隨後找出該互斥關係圖之一最大獨立集合(MIS)，且最後對於該最大獨立集合中之每一頂點用一雙介層洞來替代一單介層洞。此外，由於可將冗餘介層洞分類為在軌冗餘介層洞及離軌冗餘介層洞，且在軌冗餘介層洞具有較好的電學特性，故本發明亦呈現兩種方法來增大在軌冗餘介層洞之數量，同時給出一冗餘介層洞插入解決方案。 The present invention provides a method for post-routing redundant via insertion in IC layout. The method is to construct a conflict graph from a post-routing design first, then find a maximal independent set (MIS) of the conflict graph, and finally replace a single via with a double via for each vertex in the maximal independent set. Besides, since redundant vias can be classified into on-track and off-track ones, and on-track ones have better electrical properties, the invention also present two methods to increase the amount of on-track redundant vias while a redundant via insertion solution is given. 【創作特點】本發明之目的為提供一種用於IC佈局之繞線後階段冗餘介層洞插入的方法。該方法首先自一路徑之設計建構一互斥關係圖，隨後找出該互斥關係圖之一最大獨立集合(Maximum Independent Set；MIS)，且最後對於該MIS中之每一頂點(vertex)用一雙介層洞(double via)來替代一單介層洞(single via)。本發明之第一實施例提供一種用於藉由同時建構頂點及連接線(edge)集合來建構一互斥關係圖的方法。首先，建構每一金屬層之R樹，且藉由所有單介層洞之座標之一者以非遞減次序對所有單介層洞進行排序，隨後形成一動態頂點比較集合(VCS)(其初始為空集合)，且隨後根據經排序的介層洞之次序，對於每一單介層洞執行以下四個步驟以獲得互斥關係圖：(1)若VCS之元素的位置距處理中之單介層洞過遠，則刪除該等元素；(2)藉由在鄰近金屬層的所建立之R樹與雙介層洞之間進行設計規則檢查(DRC)來選擇處理中之單介層洞的雙介層洞，其中若不存在DRC違反，則認為雙介層洞為一可行雙介層洞，且將一新的相應頂點添加至互斥關係圖中；(3)在步驟(2)中所產生之新的可行雙介層洞與VCS之元素之間執行DRC，且若在一新的可行雙介層洞與一VCS之元素之間存在任何DRC違反，則將一連接線在其相應頂點之間添加至互斥關係圖中；(4)將新的可行雙介層洞的延伸之邊界框作為新元素而添加至VCS中，且將一連接線在步驟(2)中所產生之每一對頂點之間添加至互斥關係圖中。在完成互斥關係圖之建構之後，本發明之第二實施例呈現一解決一互斥關係圖上之MIS問題的試誤法。MIS解之時間複雜性通常隨著圖形中頂點及連接線之數目增大而很快地增加。因此，MIS試誤法將以一迭代方式解決MIS問題。在每一迭代中，根據一包含至少一個密鑰之優先級隊列而自互斥關係圖擷取一大小k(其規定子圖中頂點之最大數目，且其為一使用者規定之常數)之子圖，搜尋對子圖之一最大獨立集合的解且將其添加至先前的解中，且隨後更新互斥關係圖及優先級隊列。當互斥關係圖不具有剩餘頂點時，MIS試誤法將終止，隨後找出一MIS之解。本發明之一第三實施例呈現一後段處理試誤式(Post Processing Heuristic；PPH)方法。給定一冗餘介層洞插入解，PPH方法將盡可能多地增大在軌雙介層洞之數量而同時不會降低所插入之雙介層洞的總數目。PPH方法運作如下：將一互斥關係圖及一冗餘介層洞插入解MIS作為輸入。將藉由以下三個步驟以一隨機次序來處理MIS之每一頂點：(1)若MIS之一頂點v並非為一在軌雙介層洞，則搜尋該頂點v；(2)檢查互斥關係圖中每一連接線連接v之頂點v’以在互斥關係圖中找出一替代頂點，且若連接線連接的頂點v’為一在軌雙介層洞且v’之每一連接連接線的頂點不處於MIS中，則搜尋一替代頂點v’；(3)若搜尋到至少一個替代頂點v’，則自MIS刪除頂點v，且將頂點v’添加至MIS中。本發明之方法將同時建構頂點及連接線集合，藉此在建構一互斥關係圖中節省大量時間。此外，本發明提供一有效試誤法以找出互斥關係圖之一MIS。而且，本發明提供一有效PPH方法以增大在軌雙介層洞之數量，同時給出一冗餘介層洞插入解。

專利摘要(中)

本發明提供一種用於積體電路佈局之繞線後階段冗餘介層洞插入之方法。該方法首先自一繞線後階段設計建構一互斥關係圖，隨後找出該互斥關係圖之一最大獨立集合(MIS)，且最後對於該最大獨立集合中之每一頂點用一雙介層洞來替代一單介層洞。此外，由於可將冗餘介層洞分類為在軌冗餘介層洞及離軌冗餘介層洞，且在軌冗餘介層洞具有較好的電學特性，故本發明亦呈現兩種方法來增大在軌冗餘介層洞之數量，同時給出一冗餘介層洞插入解決方案。 The present invention provides a method for post-routing redundant via insertion in IC layout. The method is to construct a conflict graph from a post-routing design first, then find a maximal independent set (MIS) of the conflict graph, and finally replace a single via with a double via for each vertex in the maximal independent set. Besides, since redundant vias can be classified into on-track and off-track ones, and on-track ones have better electrical properties, the invention also present two methods to increase the amount of on-track redundant vias while a redundant via insertion solution is given. 【創作特點】本發明之目的為提供一種用於IC佈局之繞線後階段冗餘介層洞插入的方法。該方法首先自一路徑之設計建構一互斥關係圖，隨後找出該互斥關係圖之一最大獨立集合(Maximum Independent Set；MIS)，且最後對於該MIS中之每一頂點(vertex)用一雙介層洞(double via)來替代一單介層洞(single via)。本發明之第一實施例提供一種用於藉由同時建構頂點及連接線(edge)集合來建構一互斥關係圖的方法。首先，建構每一金屬層之R樹，且藉由所有單介層洞之座標之一者以非遞減次序對所有單介層洞進行排序，隨後形成一動態頂點比較集合(VCS)(其初始為空集合)，且隨後根據經排序的介層洞之次序，對於每一單介層洞執行以下四個步驟以獲得互斥關係圖：(1)若VCS之元素的位置距處理中之單介層洞過遠，則刪除該等元素；(2)藉由在鄰近金屬層的所建立之R樹與雙介層洞之間進行設計規則檢查(DRC)來選擇處理中之單介層洞的雙介層洞，其中若不存在DRC違反，則認為雙介層洞為一可行雙介層洞，且將一新的相應頂點添加至互斥關係圖中；(3)在步驟(2)中所產生之新的可行雙介層洞與VCS之元素之間執行DRC，且若在一新的可行雙介層洞與一VCS之元素之間存在任何DRC違反，則將一連接線在其相應頂點之間添加至互斥關係圖中；(4)將新的可行雙介層洞的延伸之邊界框作為新元素而添加至VCS中，且將一連接線在步驟(2)中所產生之每一對頂點之間添加至互斥關係圖中。在完成互斥關係圖之建構之後，本發明之第二實施例呈現一解決一互斥關係圖上之MIS問題的試誤法。MIS解之時間複雜性通常隨著圖形中頂點及連接線之數目增大而很快地增加。因此，MIS試誤法將以一迭代方式解決MIS問題。在每一迭代中，根據一包含至少一個密鑰之優先級隊列而自互斥關係圖擷取一大小k(其規定子圖中頂點之最大數目，且其為一使用者規定之常數)之子圖，搜尋對子圖之一最大獨立集合的解且將其添加至先前的解中，且隨後更新互斥關係圖及優先級隊列。當互斥關係圖不具有剩餘頂點時，MIS試誤法將終止，隨後找出一MIS之解。本發明之一第三實施例呈現一後段處理試誤式(Post Processing Heuristic；PPH)方法。給定一冗餘介層洞插入解，PPH方法將盡可能多地增大在軌雙介層洞之數量而同時不會降低所插入之雙介層洞的總數目。PPH方法運作如下：將一互斥關係圖及一冗餘介層洞插入解MIS作為輸入。將藉由以下三個步驟以一隨機次序來處理MIS之每一頂點：(1)若MIS之一頂點v並非為一在軌雙介層洞，則搜尋該頂點v；(2)檢查互斥關係圖中每一連接線連接v之頂點v’以在互斥關係圖中找出一替代頂點，且若連接線連接的頂點v’為一在軌雙介層洞且v’之每一連接連接線的頂點不處於MIS中，則搜尋一替代頂點v’；(3)若搜尋到至少一個替代頂點v’，則自MIS刪除頂點v，且將頂點v’添加至MIS中。本發明之方法將同時建構頂點及連接線集合，藉此在建構一互斥關係圖中節省大量時間。此外，本發明提供一有效試誤法以找出互斥關係圖之一MIS。而且，本發明提供一有效PPH方法以增大在軌雙介層洞之數量，同時給出一冗餘介層洞插入解。

聯絡資訊
承辦人姓名	李曉琪
承辦人電話	03-5715131 #31061
承辦人Email	hsiaochi@mx.nthu.edu.tw