用於並行化集成電路計算機輔助設計軟體的設備與方法
2023-06-01 05:23:11
專利名稱：用於並行化集成電路計算機輔助設計軟體的設備與方法
技術領域：
通常，已公開的原理涉及用於並行化軟體及算法的設備和方法。更具體地說，這些原理涉及用於並行化集成電路(IC)，比如可編程邏輯器件(PLD)的計算機輔助設計(CAD)軟體的設備及方法。
背景技術：
傳統上，處理器(比如Intel公司的奔騰系列，AMD公司的Athlon系列等等)通過支持不斷增加的時鐘速度而變得更快。由於處理器照此方式變得更快，在這些處理器上運行一個特定軟體片段的耗時自動成比例增加(因為執行代碼的單個指令的時間大致與處理器時鐘的速度成比例)。
然而當今發布的新一代處理器沒有使用比兩年前顯著加快的時鐘(大約3G赫茲)。而代替的是，現在這些處理器晶片在其內部包括超過一個處理器(例如，奔騰D處理器是「雙核」，意思是一個晶片中有兩個微型處理器)。這個特性使計算機能同時運行幾個執行線程。
在這些晶片中，任何串行的軟體(意思是一次執行一個任務)不能通過可使用附加的處理器來提高速度。為了平衡附加的處理能力，串行軟體需要被並行化，意味著為了使所有處理器保持忙碌，它不得不具有準備執行的多個任務。遺憾的是，幾乎從不能自動進行這個並行化，因為它必需修改軟體代碼。修改本身也相當錯綜複雜，因為在並行軟體中，許多構成串行軟體基礎的假設失效。因此需要將軟體並行化，比如將CAD軟體並行化。
發明內容
公開的新原理涉及並行化軟體，比如CAD軟體和算法的設備和方法。本發明原理的一個方面涉及並行化CAD軟體，比如PLD CAD軟體的方法。在一個實施例中，依據本發明的一種方法包括識別一組具有獨立性的任務，並分配該組任務中要並行執行的的每個任務。該方法進一步包括執行該組任務中的每個任務。
本發明的另一個方面涉及一種用於並行化軟體的系統，其中該系統包括一臺配置用來執行上述並行化方法的計算機。然而，本發明原理的另一個方面關於電腦程式產品，其包括適於通過計算機處理來並行化軟體的計算機應用程式。計算機應用程式使計算機執行上述軟體並行化方法。
附圖只說明本發明的示例性實施例，因此不能認為或解釋為限制其範圍。受益於本發明說明書的本領域的普通技術人員可以理解，所公開的發明的原理適用於其他同樣有效的實施例。在附圖中，在多個附圖中使用的相同的數字標記表示同樣的、類似的或等效的功能性元件或塊。
圖1示出了一種通過使用多線程在示例實施例中使用的並行化技術。
圖2說明通過使用多處理器在示例實施例中使用的另一種並行化技術。
圖3描述PLD的通用框圖，該PLD可通過使用本發明說明性實施例來設計或使用。
圖4示出了PLD的平面圖，其可通過使用本發明的原理設計或實現。
圖5說明了根據本發明的說明性實施例的PLD CAD軟體使用的各種軟體模塊。
圖6顯示並行化技術的簡化框圖。
圖7描述說明裝置平面布置圖的初始配置的實例。
圖8顯示資源移動後的圖7的裝置平面布置圖。
圖9說明裝置平面布置圖中移動資源的建議。
圖10顯示根據示例性實施例的並行化技術。
圖11描述串行分析算法的實例。
圖12顯示分析算法的並行化的實例。
圖13說明使用公開的原理處理信息的系統框圖。
具體實施例方式本發明的原理設想用於並行化軟體的設備和相關方法，例如CAD算法或軟體或用於現場可編程門陣列(FPGA)的CAD軟體。公開的原理尋求並行運行軟體或算法，例如通過使用線程或多處理器，從而提高執行速度。
總的來說，本發明的原理設想以並行方式運行軟體或並行執行算法的各種方法。圖1和2示出了可能使用的技術的兩個實例。如所期望的，受益於本發明說明書的本領域普通技術人員能夠理解可以使用的其它技術和實例。
圖1示出了一種通過使用多線程在示例性實施例中使用的並行化技術。圖1中顯示的配置包括一任務組13，調度程序或調度器10和一線程組16。任務組13組成不同的任務，這些任務由CAD軟體或算法執行或運行。通常，任務組13可包括任何期望數量的任務，比如說，N個任務，而線程組16可包括任何期望或合適數量的線程，比如說，K個線程(注意K和N可相等或不等)。
調度器10從任務組13接受任務，並安排它們在一臺或多臺計算機上執行。更明確地說，調度器10將任務組13中的任務分配到線程組16中的線程上。例如，調度器10可將任務1分配到線程1，任務2到線程2等等。到線程的分配然後將導致執行相應的分配任務。
圖2說明了另一種通過使用多處理器在示例性實施例中使用的並行化技術。圖2中的配置包括一任務組13，調度器10和一組處理器或計算機或類似適當的設備，標記為19。作為一個實例，處理器組19可以組成一臺並行計算機，一臺大規模並行計算機等等，如已經從本發明說明書中受益的本領域普通技術人員理解的。
任務組13表示CAD軟體或算法設法執行或運行的不同任務。通常，任務組13可以包括任何期望數量的任務，比如說N個任務，而處理器組19可包括任何期望或合適數量的處理器，比如說M個線程(注意，K和M可以相等或不等)。
調度器10從任務組13中接受任務，並安排由一臺或更多臺計算機執行它們。更具體地說，調度器10將任務組13中的任務分配到組19中的處理器。例如，調度器10可以分配任務1到處理器1，任務2到處理器2等等。將任務分配給處理器將導致相應分配任務的執行。
根據需要，本發明的原理可以應用到各種CAD軟體，算法和應用程式中。應用程式的一個特定領域構成CAD軟體，用於設計並使用PLD(例如，使用PLD的資源實現用戶的設計)。下面的描述提供這種PLD和軟體並行化技術的詳細資料。
圖3描述PLD的概括框圖，該PLD可通過本發明說明性的實施例設計或使用。人們可以使用所公開的原理在CAD軟體中並行化軟體，該CAD軟體用於設計PLD 103或使用它的資源來實現期望的電路或系統。
PLD 103包括配置電路130、配置存儲器(CRAM)133、控制電路136、可編程邏輯106、可編程互連109和輸入/輸出(I/O)電路112。另外，依照需要，PLD 103可以包括測試/調試電路115、一個或更多個處理器118、一個或更多個通信電路121、一個或更多個存儲器124、一個或更多個控制器127、和初始化電路139。
注意附圖顯示了PLD 103的簡化框圖。因此，如本領域普通技術人員理解的，PLD 103可以包括其它塊和電路。這種電路的實例包括時鐘生成和分發電路、冗餘電路等等。此外，依照需要，PLD 103可以包括模擬電路、其它數字電路、和/或混合模式電路。
可編程邏輯106包括可配置或可編程邏輯電路塊，比如查找表(LUT)、乘積項邏輯、多路復用器(MUX)、邏輯門、寄存器、存儲器等等。可編程互連109與可編程邏輯106耦合，並在可編程邏輯106中的不同塊及PLD103內外的其它電路之間提供可配置的互連(耦合機構)。
控制電路136控制PLD 103內的不同操作。在控制電路136的監督下，PLD配置電路130使用配置數據(其從外部源獲得，比如存儲裝置、主機等等)編制或配置PLD 103的功能。配置數據典型用於在CRAM133中存儲信息。CRAM 133的內容確定PLD 103的不同塊的功能，比如可編程邏輯106和可編程互連109的功能。在PLD 103復位或通電時，初始化電路139可以執行不同的功能。
I/O電路112可以組成眾多種的I/O裝置或電路，如已經從本發明說明書中受益的本領域中普通技術人員理解的。I/O電路112可以與PLD 103的不同的部分耦合或連接，例如，可編程邏輯106和可編程互連109。I/O電路112提供機構和電路用於PLD 103內不同的塊以與外部電路或裝置通信。
測試/調試電路115幫助PLD 103內不同塊和電路的測試和故障診斷，測試/調試電路115可包括各種塊或電路，這些塊或電路是已經受益於本發明說明書的本領域普通技術人員公知的。例如，依照需要，測試/調試電路115可以包括在PLD 103加電或復位後執行測試的電路。依照需要，測試/調試電路115還可包括編碼和奇偶電路。
PLD 103可以包括一個或更多個處理器118。處理器118可以與PLD103內的其它塊和電路相連。處理器118可以從PLD 103內部或外部的電路接收數據和信息，並以多種方式處理該信息，如受益於本發明說明書的本領域技術人員可以理解的。一個或更多個處理器118可以組成數位訊號處理器(DSP)。依照需要，DSP可執行眾多種信號處理任務，比如壓縮、解壓縮、音頻處理、視頻處理、濾波等等。
PLD 103可能還包括一個或更多個通信電路121。(多個)通信電路121可幫助在PLD 103內外的不同電路之間交換數據和信息，如受益於本發明說明書的本領域普通技術人員理解的。
PLD 103可以進一步包括一個或更多個存儲器124和一個或更多個控制器127。存儲器124允許在PLD 103中存儲不同的數據和信息(比如用戶-數據、中間結果、計算結果等等)。依照需要，存儲器124可為粒狀或塊狀的形式。控制器127可連接到PLD外部的電路，並控制PLD外部的電路的操作及各種功能。例如，依照需要，控制器127可以組成存儲控制器，該存儲控制器連接於並控制外部同步動態隨機存取存儲器(SDRAM)。
注意，PLD 103包括多個可編程資源塊。使用這些資源實現設計經常需要在PLD 103的平面布置圖中布局那些塊(在下面描述)。圖4顯示了通過使用本發明原理設計或實現的PLD的平面布置圖。
PLD 103包括布置為二維陣列的可編程邏輯106。布置為水平和垂直互連的可編程互連109，將可編程邏輯106的塊彼此相連。可以以特別的方式布局這些塊，從而實現用戶的設計，如受益於本發明說明書的本領域普通技術人員理解的。
在說明性實施例中，PLD 103具有分層體系結構。換句話說，可編程邏輯106的每個塊也可以依次包括更小的或更多的粒狀可編程邏輯塊或電路。例如，在一個實施例中，可編程邏輯106可以組成稱為邏輯陣列塊(LAB)的可配置的邏輯塊，並且依照需要，每個LAB可以包括邏輯元件(LE)或其它電路。
但是，受益於本發明說明書的本領域普通技術人員理解，具有變化的術語和拓撲結構的各式各樣的其它裝置都是可能的，並且屬於本發明原理的範圍。此外，雖然圖4顯示了可編程邏輯106的塊，但是可以在它們的平面布置圖中使用具有其它或附加塊(例如存儲器、處理器、圖3中的其它塊等等)的PLD，並利用本發明原理的優點，如受益於本發明說明書的本領域普通技術人員理解的。
但是，不管是特別的裝置或設計，可以在CAD軟體或程序中使用本發明原理，以採用PLD的資源，並實現期望的電路或系統。在PLD比如PLD103中實施用戶的設計，需要多個步驟或處理，如下詳述的。
圖5說明了根據本發明的說明性實施例的PLD CAD軟體使用的各種軟體模塊。這些模塊包括設計項目模塊203、合成模塊206、布局和路由模塊209和驗證模塊212。下面的描述提供每個模塊的操作的簡化說明。
CAD技術可以具有各種應用，如受益於本發明說明書的本領域普通技術人員理解的。依照需要，例子包括設計範圍、定時性能、電源需求、和可路由性或可布線性(routability)。
設計項目模塊203允許使用電路或其行為的圖形或文本描述來編輯不同的設計描述，依照需要，比如圖表、硬體描述語言(HDL)或波形。依照需要，用戶可以通過使用設計項目模塊203或通過使用各種電子設計自動化(EDA)或CAD工具(比如工業標準電子設計自動化工具)生成設計文件。依照需要，用戶可以以圖形格式、基于波形的格式、圖表格式、文本或二進位格式、或作為那些格式的組合輸入設計。
合成模塊206接收設計項目模塊203的輸出。根據用戶提供的設計，合成模塊206生成適當的邏輯電路，其實現用戶提供的設計。一個或更多個PLD(未明確顯示)實現該合成的總體設計或系統。合成模塊206還可以生成任何膠合邏輯(glue logic)，其允許在用戶設計中不同模塊的集成和正確操作及相接口。例如，合成模塊206提供適當的硬體，以便一個塊的輸出可以正確地與另一個塊的輸入相接。合成模塊206可以提供適當的硬體，以便滿足總體設計或系統中每個模塊的規範。
此外，合成模塊206可以包括用於最佳化或優化該合成設計的算法和例程。通過最優化，合成模塊206設法更有效地使用一個或更多個PLD的資源，其實現總體設計或系統。合成模塊206將其輸出提供給布局和路由模塊209。
布局和路由模塊209使用設計者的定時規範來執行最佳邏輯映射和布局。該邏輯映射和布局確定(多個)PLD內的路由資源的使用。換句話說，通過(多個)PLD使用特別的可編程互連用於設計的特定部分，布局和路由模塊209幫助優化該總體設計或系統的性能。通過適當使用PLD路由資源，布局和路由模塊209幫助滿足該總體設計或系統的苛刻的定時路徑。
布局和路由模塊209最優化該苛刻的定時路徑，以一種為受益於本發明說明書的本領域普通技術人員已知的方式提供更快的定時關閉。結果，該總體設計或系統可以實現更快速的性能(即，以更高的時鐘頻率運行或具有更高流通量)。
驗證模塊212進行設計的模擬和驗證。模擬和驗證尋求部分驗證該設計符合用戶規定的規範。該模擬和驗證還在給設計作原型之前用於檢測和校正任何設計問題。因此，驗證模塊212幫助用戶減少總體設計或系統進入市場的時間和總成本。
依照需要，驗證模塊212可以支持和執行各種驗證和模擬選項。這些選項可以包括功能驗證、測試工作檯生成、靜態定時分析、定時模擬、硬體/軟體模擬、系統內驗證、板級定時分析、信號完整性分析和電磁兼容性(EMC)、正式連線表驗證等等，如受益於本發明說明書的本領域普通技術人員理解的。
注意，依照需要，可以執行其它或附加驗證技術，如受益於本發明說明書的本領域普通技術人員理解的。視情況和依照需要，設計的驗證還可以在流程的其它階段執行。
大量(大概是大多數)常規的商業CAD算法的本性是串行的。換句話說，它們串行地執行不同的任務，而不是以並行方式。這並不驚奇，第一，因為迄今處理器時鐘速度已經定期加速，第二，因為開發穩固的並行軟體通常困難得多。
由於上面描述的趨勢，現在更重要的是修改現有的算法，以平衡用戶將可用的新的並行處理能力。這是特別正確的，因為CAD算法通常處於現用的最慢類型的軟體之中。整個周末的典型運行時間是十分平常的。除非使用並行化技術，否則串行算法不可能加速到足以滿足將來將它們用於解決更複雜的問題。
通常，當並行化串行的CAD算法時，常使用兩種方法。第一種方法，丟棄串行算法，並替代使用具有更內在並行性的算法。這個選擇有一些缺點。
第一，它強制設計者從頭開始，丟棄現有代碼並開發新的並行代碼。假髮已經投入許多人年的工作到將現有的算法最優化，丟棄它們將使新算法在多年內難以達到相同的質量水平。該方法還限制設計者可用的算法選擇——一些串行算法更適合於某些問題，而被迫使用並行算法可能損害軟體工具的質量。
另外，並行算法相對難以做出確定性。當以相同的輸入運行多次時，確定性算法給出相同的結果。然而，並行程序或算法同時執行多組指令，並根據每個處理器分給這些組的使用權，該算法每次運行的結果可能不同。這個特徵使用戶難以再現他們使用該算法得到的結果，以及使賣方難以調試用戶遇到的問題。
最後，對於仍使用單個處理器運行算法的用戶，強迫改為並行算法具有上述的質量潛在損失，以及上述另一個缺點會造成用戶不滿。另外，對於這些用戶來說，並行算法通常引起使程序明顯變得更慢的開銷。軟體工具賣方將因此至少在短期內保持兩組算法，導致較高的維護費用。
第二個選擇，可以在具有不同設置的每個可用處理器上運行串行算法，並最終獲得最好的結果。這個傳統的方法，儘管比第一個容易實現，但也有一些限制。
首先，它不包含加速該算法——它僅僅運行該算法的更多個副本以改進結果。任何需要獲得算法的最快可能運行時間的用戶都不能從該方法獲取他們所需的結果。其次，它不能隨著更多的處理器可用而良好地伸縮，因為隨著運行越來越多的副本，這種多次運行同樣的算法來獲得更好結果的能力迅速地消失。明顯地，這兩種方法都有重要的限制。然而本發明原理提供克服這些限制的技術。
更具體地說，本發明的方法利用這樣的事實，眾多的串行CAD算法花費大部分它們的執行時間在輸入問題的不同部分執行一個特定的動作或一組動作。這個動作重複多次(經常是幾百萬次)，這導致這些算法相對長的運行時間。使這些算法串行的特性是，在知道每個先前動作的結果的情況下(即，依靠先前的動作)執行每個動作。這個特性又意味著一個動作可以或實際上隨時執行，這限制算法為串行執行。
然而，給定的鄰近動作組經常影響輸入問題的獨立部分，由此去除它們所有被串行執行的需求。這個特性對於相對大的輸入問題尤其有效。例如，在包括許多動作的問題中，包括動作#10到#20，動作#10到動作#20可彼此獨立。換句話說，不需根據執行其它(多個)動作的(多個)結果執行本動作。
在這樣的條件下，該算法可以並行執行所有那些11個動作。在示例性實施例中，本發明的技術使用局部獨立性來產生並行執行。例如，如果動作#21接著依賴於兩個先前的動作(比如說#13和#17)，那麼在算法可以繼續進行#21以前，它必須結束動作#13和#17(否則結果將不是確定性的)。否則，該算法可以並行執行各個動作。這個方法使用這個局部獨立性來產生並行性，從而產生改進的性能。
本發明的技術使用動作隊列，其中，隊列裝載著彼此相互獨立的動作。這個隊列是串行地裝載的，以確保全部動作是獨立的。在本發明的一個變體中，隊列以和串行算法將執行動作的同樣順序被裝載。這個動作確保算法的並行版本的結果與那些串行版本相仿或相同。
圖6顯示該技術的簡化框圖。一組任務13輸入到調度器10中。如上所述，調度器10向隊列250提供任務，以便提供局部獨立性。任務從隊列250輸出，並以並行方式執行(只要存在局部獨立性)。
在本發明的另一個變體中，可以以使隊列保持的獨立動作數目最多的方式選擇動作。一旦裝載這個隊列，則所有可用處理器都可以以它們選擇的任何隨意的或期望的順序處理動作，因為在隊列中動作的獨立性是有保證的。一旦完成隊列中所有動作，就再次裝載該隊列，並重複該過程。
為了更詳細地闡明本技術，提供一個布局的實例，以說明它如何用於並行化布局算法。布局算法採用電路的連線表(netlist)表示和裝置的平面布置圖表示作為輸入。在Qrartus II軟體中(可以從本申請的受讓人Altera公司獲得)，例如，連線表表示用戶的邏輯電路中的塊(例如，邏輯陣列塊或LAB；RAM塊；乘法器塊等等)。平面布置圖表示在PLD或類似器件中的可用塊。
串行布局算法可工作如下儘量快或相對快地創建初始的合法布局，而幾乎不考慮或不考慮質量。結果，在平面布置圖中，連線表的每個塊都已經被分配一個位置。第二，在連線表中隨機地取出一個塊，並試圖將它移動到隨機位置。交換已經在那裡的任何塊與源塊。第三，評估布局的這個改變是否好或合乎需要。如果是，則提交這個改變。否則，丟棄這個改變。經常對幾個度量進行該評估，並且，通常，這些度量通常試圖保持彼此間連接或耦合的塊彼此靠近放置。最後，回到第二步並重複，直到完成給定次數的移動(例如，這個次數可以是連線表中塊數目的1000倍)。
以上布局算法本質上是串行的，因為在第三步提交改變的決定影響算法的所有將來迭代(即移動)。例如，假設採用圖7中所示的平面布置圖。假設在該平面布置圖中塊#6處於X＝3且Y＝4，並且算法的第一移動試圖交換它與塊#20，塊#20處於X＝30且Y＝40。
另外，假設算法的第二移動將要移動塊#21(它正巧與塊#20連接或耦合)從X＝30，Y＝4到X＝1，Y＝1。圖8示出了如果接受第一移動的位置和連接性是什麼樣子。
如果算法的第一移動接受該移動，那麼第二移動(它試圖移動塊#21到(1，1))很可能被接受，因為塊#21的新位置(1，1)將更接近於與它連接或耦合的塊(即，塊#20，其當前位置是(3，4))。然而，如果沒有接受第一移動(保留圖7中的情況)，移動塊#21到(1，1)就似乎不像是一個好的移動，因為其連接或耦合的塊(即，塊#20)在(30，40)，並且塊#21的當前位置(即，30，4)比(1，1)離它近。
這個實例說明了如果如上面串行算法一樣的算法並行運行將會遇到的問題。例如，如果同時移動#1和#2，那麼移動#2是否被接受依賴於移動#1是否在移動#2被評估之前結束。
除非改變該算法，否則並行運行它可以導致產生追趕最後位置的塊，而該位置是其連接或耦合塊所在，可能急劇地降低最後的布局質量。它還將使結果不確定，因為通常不可能預計將用多長時間完成給出的移動，即使是對於同一電路的不同運行。
為應用本發明的技術來解決這些問題，可以設立一個獨立移動的隊列，如上所述。當以上實例中的第一移動被放入隊列中時，第二移動將不再被容許進入該隊列(因為該移動依賴於通過塊#21和塊#20之間的連接或耦合的第一移動)。該隊列裝載可以被停止，並且處理的移動或者隊列可以在處理這些移動之前裝入其它獨立的移動，如上所述。但不論是哪種情況，因具有多個處理器，隊列越大，加速越快。例如一個其中總是只有兩個移動的隊列將受益於使用兩個處理器(但不是四個或更多)。
注意上述技術使用隊列的串行裝載。如果計劃移動的時間花費相對較小，那麼串行裝載不會引起問題。例如，在雙處理器機器上，裝載佔用5％的串行運行時間而評估佔用95％的運行時間的算法理論上可以加速1.9倍。但是如果串行部分更大，這個益處將顯著地減少。例如，如果僅僅一半算法是並行的，那麼在雙處理器系統中的加速將限於1.33倍。
但是，通過使用相對更複雜的隊列，就可能緩和該問題。回到以上的布局實例，我們注意到，在移動之間存在依賴性的兩個來源(1)不可能計劃獨立的移動；和(2)不可能獨立地評估移動。
類似地或同等地處理這兩個實例，但是它們十分不同。例如，考慮單個塊的兩個計劃移動。顯然，直到第一個移動已經被提交或被拒絕，才能計劃第二個移動，因為不知道第一個移動之後該塊將在哪裡。
另一方面，考慮希望移動兩個塊到更接近。可以容易地計劃同時移動兩個塊。不能獨立地評估它們(因為，依賴於首先移動哪一個塊，第二個移動未必是好的或合乎需要或有利的)。注意，儘管甚至能夠在已經評估的兩個塊移動之前進行和計劃其它移動。從並行觀點來看，這樣做是有利的，因為它能夠在比任何種類的依賴導致停頓時的環境多得多的環境中為所有處理器持續生成工作。
以下說明這個改進應用的實例。考慮在圖9中的布局，具有塊303-315的幾個計劃的移動。使用上述原始的發明算法，可以計劃第一個移動，然後在計劃第二個移動之後停止，因為它們與連接或耦合塊相關，由此，接受或丟棄移動#2的決定將依賴於移動#1的結果(換言之，移動#1將移動塊303，而移動#2將移動塊306，其中塊306與塊303耦合)。
無論如何，然後可以評估並行移動#2和#3(移動塊309)，然後移動#4(移動塊312)，#5(移動塊315)和#6(移動塊303)，和最後移動#7(移動塊318)。注意，布置已經停止了三次，並且在第四組移動中，半個組是使單個塊移動。因此，在一半時間內，雙核機器的一個處理器(作為實例)將空閒。
但是，如果相反，當不能再計劃移動時就停止，情況改進了。例如，可以計劃移動#1通過#5而不停止。注意，將在移動#6停止，因為它指向作為另一個移動的結果的已經被移動的塊(即，塊303)。一旦已經接受或者拒絕移動#1，就可以恢復，並進行到計劃移動#7。換句話說，當已經解決在一個或更多個較早的移動上的一個或更多個依賴性後，可以進行恢復。
現在，在任何給定時間，總是存在可以並行評估的至少兩個移動(移動#3與#1並行；移動#4與#3並行；移動#5與移動#4和移動#2並行；移動#6與移動#3並行；移動#4，#5和#7與移動#3，#5和#6並行)。受益於本發明說明書的本領域普通技術人員可以理解如何進行，使用該技術，將還有很大的可能性確保每次可以生成4個或8個乃至更多的移動，由此，依照需要，能夠很好地利用具有兩個以上處理器的機器。
為了實現該算法，本發明原理使用一個更複雜或「聰明」或改進或增強的隊列。更具體地說，代替保持所有移動按次序並允許處理器在下一個有效的移動上工作，這種隊列記錄最後的移動，該移動在每個移動可以被評估之前應該被接受或拒絕。例如，移動#2將列出移動#1，移動#6將列出#2(但不是移動#3，#4或#5)。例如，結束評估移動#2的處理器將能開始在移動#6上工作，即使移動#3，#4和#5還沒有完成。
可以在各種情況中使用本技術。例如，依照需要，可以在圖6中用這種隊列代替隊列250。或者，依照需要，可以使用其它排列，如受益於本發明說明書的本領域普通技術人員理解的。
如果即使增強或改進隊列允許的加速不夠充分，也可能使不同的線程選擇輸入問題的哪些部分是它們希望並行工作的。注意，這樣做將仍保持確定性結果。使用以上的布局實例，本方法意味著我們不僅並行評估這些移動，我們還並行產生它們。該技術的操作如下所述，並如圖10中所示。
如上所述，在350，給每個動作一個數字ID。然而，多個線程可以在355作出關於它們選擇檢查輸入問題的哪個部分(例如，每個線程計劃移動哪個塊)的決定。然而各個線程並不實際執行該動作。
然後該線程在360將該動作添加到提交隊列。該隊列以任何順序接受動作，但是將按照它們的ID號的順序發出它們。例如，如果加入動作#1和#3，則該隊列將看來像是在其中具有一個動作(#1)，直到動作#2也加入。
隨著從該隊列中去除動作，在365，執行如上所述的依賴性分析。如果發現一個動作依賴於一個先前的動作，就按如上所述處理它。然而，該動作自身可能是無效的。例如，可以為一個塊計劃移動，該塊可能不再處於預期的位置。注意，如果伴隨此處所述的本技術版本出現該情況，就簡單地停止生成新的動作。假設用改進的技術，可以使多個線程並行生成動作，那將是相對更嚴格的限制。
一旦發現該相對更嚴重的依賴性類型，在370，僅僅要求一個線程重新生成該動作，優選的是越快越好。例如，「越快越好」可能是指確定目標塊是否已經移動的時候。如果它還沒有移動，就可能僅僅評估該移動；但是，如果它已經移動，就計劃或考慮一個從頭開始的新移動並代替評估該移動。
該技術的好處是因為該算法沒有任何部分是串行的(除了依賴性檢驗器外，其假設相對快)，考慮到其固有的依賴性，預計能夠按理論上的可能加速整個程序。注意，該算法幾乎沒有引入其自己的新的依賴性。
存在除了PLD CAD應用之外的其它方法，其對於特殊算法是特定的，這些算法可利用並行處理的能力，而不顯著影響算法設計的靈活性。一個實例是並行分析。
更具體地說，最優化算法經常依賴分析引擎來確定施加多少工作(及那些工作用在哪裡)，以實現不同的設計目標。這些分析引擎經常給當前狀態拍快照，並返回對該狀態分析的結果。在圖11中顯示的串行算法將等待該分析，並在它完成時進行(例如，最優化階段403B等待分析階段406的結果，而分析階段406依次從最優化階段403A接收其輸入)。因此，它具有以上所述的缺點。
為使這些算法並行，可以使附加處理器持續地進行該狀態的快照，並執行分析。這有一個缺點，因為分析結果將過時，因為當可獲得分析結果時，用於分析的狀態不是當前的，但是，另一方面，並行性提供增加的效率並降低資源需求。圖12顯示這個過程如何工作。
在圖12顯示的技術中，可以並行執行分析和最優化。例如，最優化階段或引擎403A可以與分析階段或引擎406A並行工作或當前工作。同樣地，最優化階段或引擎403B可以與分析階段或引擎406B並行工作或當前工作。在該方案中，分析階段在先前的最優化狀態上執行。在最優化狀態已經潛在地改變之後，分析階段的結果反饋到最優化階段。
注意，到每個分析步驟的輸入來自於一個與使用其輸出的狀態不同的最優化狀態。例如，假設該最優化步驟是布局(其中，假定，塊正在進行數千次的移動)，並且分析步驟是定時分析，其向布局階段提供輸入，該輸入是關於哪些連接對定時是關鍵的。這種技術提供的優點是分析和最優化是並行執行或同時執行的，即使潛在地(但不是必然地)以不太最優的解為代價。
本技術可能應用的分析的例子包括定時分析(確定電路中每個路徑的定時性能)、擁塞分析(根據設計的布局，確定晶片的哪些區域可能會面臨路由擁塞)和設計分析(確定設計的什麼部分更聚焦進行最優化是可取的或有益的(或需要的))。注意，列出的例子是說明性的，並且可以將該技術應用到其它應用或情況，如受益於本發明說明書的本領域普通技術人員理解的。
如上所述，可以在計算機系統或處理器上，運行或執行根據本發明的算法或軟體。圖13顯示根據本發明的用於處理信息的示例性系統的框圖。
系統1000包括計算機裝置1005、輸入裝置1010、視頻/顯示裝置1015和存儲/輸出裝置1020，雖然依照需要，可以包括一個以上的這些裝置。
計算機裝置1005與輸入裝置1010、視頻/顯示裝置1015和存儲/輸出裝置1020相連。系統1000可以包括多於一個的計算機裝置1005，例如，依照需要，一組關聯計算機裝置或系統。
系統1000的運行與來自用戶的輸入相關聯。用戶輸入典型地導致系統1000執行特定的期望的信息處理任務，包括電路模擬。系統1000部分使用計算機裝置1005來執行那些任務。計算機裝置1005包括信息處理電路，諸如中央處理單元(CPU)，儘管可以使用一個以上或信息處理電路，如本領域的技術人員將會理解的。
輸入裝置1010接收來自用戶的輸入，並使那些輸入可以讓計算機裝置1005使用進行處理。依照需要，該用戶輸入可以包括數據、指令或兩個都有。輸入裝置1010可以組成字母數字輸入裝置(例如，鍵盤)、定點設備(例如滑鼠、滾動球、光筆、觸敏設備，例如觸控式顯示器、或寫字板)或兩者。用戶操作字母數字鍵盤來向計算機裝置1005提供文本，例如ASCII字符。同樣地，用戶操作定點設備提供光標位置或控制信息到計算機裝置1005。
視頻/顯示裝置1015向用戶顯示視覺圖像。視覺圖像可以包括關於計算機裝置1005的操作的信息，例如圖表、圖片、圖像和文本。視頻/顯示裝置可以組成計算機監視器或顯示器、投影裝置等等，如本領域普通技術人員可以理解的。如果系統使用觸控式顯示器，那麼該顯示器也可以提供用戶輸入到計算機裝置1005。
存儲/輸出裝置1020允許計算機裝置1005保存信息用於附加處理或以後取回(例如，軟拷貝)，以不同的形式(例如，硬拷貝)表現信息，或兩者。作為實例，存儲/輸出裝置1020可以組成磁、光或磁光碟機動器，它們能夠以期望的格式將信息存儲到期望的介質上。作為另一個實例，存儲/輸出裝置1020可以組成印表機、繪圖儀或其它輸出裝置，以從計算機裝置1005生成信息的列印表示或繪圖表示。
計算機可讀介質1025在結構上和功能上與計算機裝置1005相互關聯。計算機可讀介質1025存儲、編碼、記錄和/或具體化功能描述內容。通過說明，該功能描述內容可以包括電腦程式、計算機代碼、計算機應用程式、和/或信息結構(例如，數據結構或文件系統)。當通過計算機可讀介質1025存儲、編碼、記錄和/或具體化時，該功能描述內容賦予功能性。功能描述內容與計算機可讀介質1025相互關聯。
功能描述內容內的信息結構在信息結構和計算機可讀介質1025和/或系統1000的其它方面之間定義結構和功能相互聯繫。這些相互聯繫允許信息結構的功能的實現。此外，在這種功能描述內容內，電腦程式在電腦程式和計算機可讀介質1025及系統1000的其它方面之間定義結構和功能相互聯繫。這些相互聯繫允許電腦程式功能的實現。
通過說明，計算機裝置1005將功能描述內容讀出、存取或複製到計算機裝置1005的計算機存儲器內(附圖中未明確顯示)。計算機裝置1005執行操作來響應計算機存儲器中存在的內容。計算機裝置1005可以執行處理計算機應用的操作，其中計算機應用導致計算機裝置1005執行附加的操作。因此，功能描述內容展現功能相互聯繫和計算機裝置1005執行處理和操作的方式。
此外，計算機可讀介質1025組成一臺設備，計算機裝置1005可以從這個設備訪問計算機信息、程序、代碼和/或應用。計算機裝置1005可以處理引起計算機裝置1005執行附加操作的信息、程序、代碼和/或應用。
注意，可以以各種方式實現計算機可讀介質1025，如本領域普通技術人員可以理解。例如，依照需要，計算機裝置1005內的存儲器可以組成計算機可讀介質1025。或者，計算機可讀介質1025可以包括一組關聯的、相互關聯的、耦合的(例如，通過導體、光纖等等)、或連網的計算機可讀介質，例如，當計算機裝置1005從計算機裝置或信息處理系統網絡接收該功能描述內容時。注意，依照需要，計算機裝置1005可以從計算機可讀介質1025、網絡或兩者接收功能描述內容。
注意，依照需要，可以有效地將本發明原理應用到不同的集成電路(IC)，包括有可編程或可配置電路的IC，其在該領域中可有其它名字，並且如受益於本發明說明書的本領域技術人員理解的。這種電路包括例如以下裝置，通稱是複雜可編程邏輯器件(CPLD)、可編程門陣列(PGA)、現場可編程門陣列(FPGA)、和結構化應用特定IC或結構化ASIC的裝置。
參考附圖，本領域普通技術人員將注意到，顯示的不同塊可以大體上描述設想的功能和信號流。實際電路實現可能或未必單獨包含用於不同功能塊的可識別硬體，以及可能或未必使用顯示的特定電路。例如，依照需要，可以將不同塊的功能組合到一個電路塊中。此外，依照需要，可以在幾個電路塊中實現單個塊的功能。電路實現的選擇依賴不同的因素，例如對一個給定實現的特定設計和性能規範，如受益於本發明說明書的本領域普通技術人員理解的。除這裡描述的之外，本發明的其它修改和替代實施例對於受益於本發明說明書的本領域普通技術人員是顯而易見的。因此，本說明書向本領域技術人員講授實施本發明的方式，並看作僅僅是說明性的。
應該認為示出和描述的本發明形式是目前優選的或說明性的實施例。本領域技術人員可以在不脫離本文說明的本發明的範圍內，在部件的形狀、尺寸和排列方面進行各種變化。例如，本領域技術人員可以將這裡說明和描述的元素代替為等效的元素。此外，受益於本發明說明書的本領域技術人員可以獨立於其它特徵的使用來使用本發明的某些特徵，而不脫離本發明的範圍。
權利要求
1.一種在計算機輔助設計CAD軟體中提供並行的系統，該系統包括計算機，其配置為識別具有獨立性的一任務組；分配所述任務組中要並行執行的每個任務；和執行所述任務組中的每個任務。
2.如權利要求1所述的系統，其中所述計算機被配置為裝載具有所述任務組的隊列。
3.如權利要求2所述的系統，其中所述隊列以類似於串行CAD算法的順序被裝載，以便並行化的CAD軟體產生類似於該串行算法的結果。
4.如權利要求2所述的系統，其中選擇所述任務組，以便最大化所述隊列中保持的獨立動作的數量。
5.如權利要求4所述的系統，其中以任意順序執行任務。
6.如權利要求2所述的系統，其中所述隊列在所述任務組被執行之前裝載所述任務組中的所有任務。
7.如權利要求2所述的系統，其中所述隊列包括增強隊列，該增強隊列允許當正在執行所述任務組時，計劃附加的任務。
8.如權利要求2所述的系統，其中多個線程確定要被執行的各自任務，並將該任務增加到所述隊列。
9.如權利要求8所述的系統，其中如果依賴另一個任務，則線程重生一個任務。
10.如權利要求1所述的系統，其中所述CAD軟體包括布局算法，其用於在可編程邏輯器件PLD中的資源布局。
11.如權利要求1所述的系統，其中所述CAD軟體包括並行分析算法。
12.一種電腦程式產品，包括計算機應用程式，其適合於通過計算機處理來並行化計算機輔助設計CAD軟體，該計算機應用程式被配置為使所述計算機識別一具有獨立性的任務組；分配所述任務組中要並行執行的每個任務；和執行所述任務組中的每個任務。
13.如權利要求12所述的電腦程式產品，使所述計算機裝載具有所述任務組的隊列。
14.如權利要求13所述的電腦程式產品，使所述計算機以類似於串行CAD算法的順序裝載所述隊列，以便並行化的CAD軟體產生類似於該串行算法的結果。
15.如權利要求13所述的電腦程式產品，使所述計算機選擇所述任務組，以便最大化所述隊列中保持的獨立動作的數量。
16.如權利要求15所述的電腦程式產品，使所述計算機以任意順序執行任務。
17.如權利要求13所述的電腦程式產品，使所述計算機在所述任務組被執行之前給所述隊列裝載所述任務組中的所有任務。
18.如權利要求13所述的電腦程式產品，使所述計算機使用一個增強隊列，該增強隊列允許當所述任務組正在被執行時，計劃附加的任務。
19.如權利要求13所述的電腦程式產品，使所述計算機使用多個線程，所述線程確定要被執行的各自任務，並將該任務增加到所述隊列。
20.如權利要求19所述的電腦程式產品，使所述計算機使用一個線程，如果依賴另一個任務，則該線程重生一個任務。
21.如權利要求12所述的電腦程式產品，使所述計算機在可編程邏輯器件PLD中執行資源的布局。
22.如權利要求12所述的電腦程式產品，使所述計算機執行並行分析算法。
23.一種並行化計算機輔助設計CAD軟體的方法，該方法包括識別一具有獨立性的任務組；分配所述任務組中要並行執行的每個任務；和執行所述任務組中的每個任務。
24.如權利要求23所述的方法，還包括裝載具有所述任務組的隊列。
25.如權利要求24所述的方法，還包括以類似於串行CAD算法的順序裝載所述隊列，以便並行化的CAD軟體產生類似於該串行算法的結果。
26.如權利要求24所述的方法，還包括選擇所述任務組，以便最大化所述隊列中保持的獨立動作的數量。
27.如權利要求26所述的方法，還包括以任意順序執行所述任務。
28.如權利要求24所述的方法，還包括在所述任務組被執行之前給所述隊列裝載所述任務組中的所有任務。
29.如權利要求24所述的方法，其中所述隊列包括增強隊列，該增強隊列允許當所述任務組正在執行時，計劃附加的任務。
30.如權利要求24所述的方法，還包括使用多個線程，這些線程確定要執行的各自任務，並將該任務增加到所述隊列。
31.如權利要求30所述的方法，其中如果依賴另一個任務，則線程重生一個任務。
32.如權利要求23所述的方法，其中所述CAD軟體包括布局算法，該算法用於可編程邏輯器件PLD中資源的布局。
33.如權利要求23所述的方法，其中所述CAD軟體包括並行分析算法。
全文摘要
一種在計算機輔助設計(CAD)軟體中提供並行的系統包括臺計算機該計算機被配置成識別一組具有局部獨立性的任務，並分配該組任務中要並行執行的每個任務。該計算機進一步配置為執行該組任務中的每個任務。
文檔編號G06F17/50GK101021802SQ20071008798
公開日2007年8月22日 申請日期2007年2月12日 優先權日2006年2月13日
發明者K·帕達利, A·路德文, V·比特茲, R·馮 申請人:阿爾特拉公司