跨個別過程增強約束求解器的性能的製作方法

2023-07-26 00:23:16 1

專利名稱：跨個別過程增強約束求解器的性能的製作方法
技術領域：
本發明主要地涉及用於求解針對問題域的約束問題的技術。具體而言，本發明涉 及一種用於跨一個或者多個問題域重用與約束求解運算關聯的信息的系統。
背景技術：
半導體製造技術的發展已經引起每個半導體器件的電晶體數量的顯著增長。晶體 管個數的這一增長使計算機架構師能夠創造出設計複雜性與日俱增的數字電路設計。因 而，隨著數字電路設計變得更複製，驗證所得實施的正確性這一任務變得更加複雜。為此，電路設計團隊依賴於自動化技術以處理與日俱增的設計複雜性。在這樣做 時，這些設計團隊針對與實施和驗證電路設計的功能關聯的諸多應用來執行約束求解運 算。在一種應用中，這些設計團隊執行約束求解運算以生成受約束的隨機輸入刺激以朝著 重要拐角情況驅動給定的電路仿真。在另一應用中，這些設計團隊在電路合成期間執行約 束求解運算。然而，這些應用可能由於大量遞歸的複雜約束滿足問題而負擔過重。另外，多 個獨立問題域(即應用實例)必須時常求解類似的複雜約束滿足問題，其中一個獨立問題 域可以持續從另一問題域的經驗中受益。

發明內容
本發明的一個實施例提供一種用於重用與針對問題域的約束求解運算關聯的信 息的系統。該系統通過從問題域接收約束問題來開始。然後，該系統在問題高速緩存中搜 尋與規範表示對應的條目。如果對應條目在問題高速緩存中不存在，則該系統在問題高速 緩存中產生用於規範表示的條目。否則，如果對應條目已經存在於問題高速緩存中，則該系 統通過重用與問題高速緩存中的對應條目關聯的求解器試探法來生成規範表示的解。在一些實施例中，該系統在問題高速緩存中產生條目。在這樣做時，該系統先在問 題高速緩存中存儲約束問題的規範表示。接著，該系統從多個可用試探法中選擇求解器試 探法並且通過使用所選求解器試探法來生成規範表示的解。只要所選試探法無法在預定 時間段內生成解，則該系統選擇新的求解器試探法並且使用新的試探法以生成規範表示的 解。在選擇求解器試探法之後，該系統將所選求解器試探法與問題高速緩存中的規範表示 條目關聯。在一些實施例中，該系統監視在生成規範表示的解時的計算時間並且在問題高速 緩存中的對應規範表示條目中存儲計算時間。在一些實施例中，該系統使用後臺過程來精化對求解器試探法的選擇。在一些實施例中，該系統能夠執行多個同時線程，其中相應線程與獨立約束問題 關聯。在一些實施例中，該系統將約束問題轉換成規範表示。在一些實施例中，當該系統將約束問題轉換成規範表示時，該系統將約束問題分 割成多個不相交約束問題。
在一些實施例中，該系統通過在問題高速緩存中記錄和保留用來第一次求解指定 的規範表示的求解器試探法、由此允許當在以後時間求解指定的規範表示時使用相同試探 法來提供用於規範表示的持久解。在一些實施例中，該系統通過在問題高速緩存中記錄和保留用來第一次求解指定 的規範表示的隨機種子、由此允許該系統產生與求解個別規範表示的順序無關的恆定解來 為規範表示提供隨機穩定性。在一些實施例中，該系統記錄用於問題域的約束問題解序列並且為後續問題域重 放解序列。在一些實施例中，該系統跨與一個或者多個應用關聯的多個獨立問題域重用問題 高速緩存的信息。


圖1圖示了根據本發明一個實施例的約束求解器系統。圖2圖示了根據本發明一個實施例的跨約束求解器系統的數據流。圖3圖示了根據本發明一個實施例的問題高速緩存。圖4A圖示了根據本發明一個實施例的變換機制。圖4B圖示了根據本發明一個實施例的不相交機制。圖4C圖示了根據本發明一個實施例的歸約機制。圖5呈現了對根據本發明一個實施例的用於重用與約束求解運算關聯的信息的 過程進行圖示的流程圖。圖6呈現了對根據本發明一個實施例的用於生成規範約束表示的解的過程進行 圖示的流程圖。圖7圖示了根據本發明一個實施例的實施求解器伺服器的計算機系統。
具體實施例方式呈現以下描述以使本領域技術人員能夠實現和利用本發明，並且在特定應用及其 要求的背景下提供該描述。本領域技術人員將容易清楚對公開的實施例的各種修改，並且 這裡限定的一般原理可以適用於其它實施例和應用而不脫離本發明的精神和範圍。因此， 本發明不限於所示實施例而是將被賦予以與這裡公開的原理和特徵一致的最廣範圍。在本具體實施方式
中描述的數據結構和代碼通常存儲於計算機可讀存儲介質上， 該介質可以是能夠存儲用於由計算機系統使用的代碼和/或數據的任何設備或者介質。計 算機可讀存儲介質包括但不限於易失性存儲器、非易失性存儲器、磁和光學存儲設備(比 如盤驅動器、磁帶、CD(壓縮盤)、DVD(數字多功能盤或者數字視頻盤)或者現在已知或者 以後開發的能夠存儲計算機可讀介質的其它介質。可以將具體實施方式
這一節中描述的方法和過程實施為能夠存儲於如上所述計 算機可讀存儲介質中的代碼和/或數據。當計算機系統讀取和執行計算機可讀存儲介質上 存儲的代碼和/或數據時，計算機系統實現作為數據結構和代碼來實施的並且存儲於計算 機可讀存儲介質內的方法和過程。另外，可以在硬體模塊中包括下文描述的方法和過程。例如，硬體模塊可以包括但不限於專用集成電路(ASIC)晶片、現場可編程門陣列(FPGA)和現在已知或者將來開發的 其它可編程邏輯器件。當激活硬體模塊時，硬體模塊實現硬體模塊內包括的方法和過程。鍵電路設計團隊依賴於自動化技術以處理複雜性與日俱增的電路設計。在這樣做 時，這些設計團隊針對與實施和驗證電路設計的功能關聯的諸多應用來執行約束求解運 算。在一種應用中，這些設計團隊執行約束求解運算以生成受約束的隨機輸入刺激以朝著 重要拐角情況驅動給定的電路仿真。在另一應用中，這些設計團隊在電路合成期間執行約 束求解運算。然而，這些應用可能由於大量遞歸的複雜約束滿足問題而負擔過重。另外，多個獨 立問題域(即應用實例)必須時常求解類似的複雜約束滿足問題，其中一個獨立問題域可 以持續從另一問題域的經驗中受益。對於本公開內容的其餘部分，問題域指代一個需要大 量約束求解運算的應用實例。例如，來自電路仿真集合的相應電路仿真是用於相應問題域 的來源。本發明的實施例提供一種系統，用於重用來自問題域的與約束求解運算關聯的信 息以在重訪給定的約束問題時改進性能並且提高它們的解的穩定性。在本發明的一些實施例中，系統支持在給定的問題域內重用約束求解信息，而在 其它實施例中，系統支持隨時間跨多個獨立或者有關問題域內重用這一信息。另外，在本發 明的實施例中，系統允許依次重放約束問題的先前解以有助於回歸測試。在一些實施例中， 系統有助於對於給定的約束求解運算而言解隨時間的持久性。在更多實施例中，系統有助 於在以後時間重訪給定的約束求解運算時的隨機穩定性。約束求解器系統圖1圖示了根據本發明一個實施例的約束求解器系統100。約束求解器系統100 包括網絡102、求解器伺服器104、問題高速緩存106和多個求解器客戶機108-112。網絡 102可以包括任一類有線或者無線通信信道。在本發明的一個實施例中，網絡102包括因特 網。求解器客戶機108-112可以包括任何如下節點，該節點具有計算能力和用於通過 網絡102來與求解器伺服器104通信的通信機制。求解器客戶機108-112執行與一個或者 多個約束求解應用關聯的運算。在本發明的一個實施例中，求解器客戶機108-112或者使 用預先生成的輸入刺激或者使用由求解器伺服器104生成的受約束的隨機刺激對一個或 者多個受驗證的電路設計(DUV)進行電路仿真。在仿真期間，電路仿真器可以生成對複雜 約束滿足問題執行限定的約束並且可以將該約束髮送到求解器伺服器104以請求滿足約 束值的輸入刺激。求解器伺服器104可以包括任何如下節點，該節點具有計算能力和用於通過網絡 102來與求解器客戶機108-112通信並且直接地或者通過網絡102來與問題高速緩存106 通信的通信機制。求解器伺服器104從求解器客戶機108-112中的任何求解器客戶機接收 約束並且返回可以滿足約束值的輸入刺激。在這樣做時，求解器伺服器104通過利用可以 求解給定的約束滿足問題的許多可用求解器試探法之一來生成用於約束的輸入刺激。求解 器伺服器104然後存儲和重用問題高速緩存106中與約束求解運算有關的信息以幫助加速 遞歸約束的約束求解運算。問題高速緩存106可以包括用於在非易失性儲存器中存儲數據的任一類系統。這
7包括但不限於基於磁、光或者磁光存儲設備的系統以及基於快閃記憶體和/或電池後援式存儲器 的存儲設備。注意，問題高速緩存106可以耦合到求解器伺服器104或者網絡102。問題高 速緩存106可以包括與多個約束求解運算有關的信息和/或可以存儲用於一個或者多個求 解器客戶機108-112的多個預先生成的輸入序列。注意本發明的不同實施例可以使用不同配置而不限於約束求解器系統100中圖 示的配置。在本發明的一些實施例中，求解器客戶機108-112執行並行運算，而在其它實施 例中，求解器客戶機108-112在不同時間工作。在這些實施例的一些變形中，求解器客戶機 108-112存在於相同計算節點上，而在其它變形中，求解器客戶機108-112存在於分布式計 算節點上。在本發明的一些實施例中，求解器伺服器104在與給定的求解器客戶機相同的 計算節點上執行。在其它實施例中，求解器伺服器104實施為在一個或者多個計算節點上 執行的分布式系統。在本發明的更多其它實施例中，求解器伺服器104實施為在實現求解 器客戶機108-112的相同計算節點上執行的分布式系統。圖2圖示了根據本發明一個實施例的跨約束求解器系統200的數據流。起初，求解 器客戶機202將約束204發送到求解器伺服器206。求解器伺服器206使用接收機制270 以從求解器客戶機202接收約束204並且使用變換機制208以將約束204轉換成規範表示 210。接著，求解器伺服器206在問題高速緩存212中搜尋與規範表示210對應的條目。約 束的規範表示是用於該約束和結構類似的任何其它約束的標準表示，從而將類似約束匯集 轉換成它們的規範表示產生一種一致的形式。將約束轉換成它的規範表示允許任何其它類 似約束訪問和重用問題高速緩存中的約束問題的解。在本發明的一些實施例中，規範表示 作為二元判決圖(BDD)而存在。在本發明的一些實施例中，接收機制207從求解器客戶機202接收的約束204是 用於約束問題的規範表示。如果對應條目在問題高速緩存212中不存在，則求解器伺服器206通過在問題高 速緩存212中存儲規範表示210來產生條目。求解器伺服器206也將規範表示210轉發到 求解器216以對規範表示210執行約束求解運算並且生成解218。在這樣做時，求解器216 從多個可用試探法中選擇求解器試探法並且通過使用所選求解器試探法來生成規範表示 210的解。只要所選試探法無法在預定時間段內生成解，求解器216就選擇新的求解器試探 法並且使用新的求解器試探法以生成規範表示210的解。在生成規範表示210的解之後，求解器216將元數據214轉發到問題高速緩存 212，其中元數據214包括所用求解器試探法和與約束求解運算關聯的其它信息。問題高速 緩存212然後將元數據214與問題高速緩存212中的新條目關聯。因而，當遇到與先前已 經探究的約束問題類似的約束問題時，求解器216將通過使用發現成功的求解器試探法來 求解約束問題。否則，如果對應條目存在於問題高速緩存212中，則求解器216通過重用與先前約 束求解運算關聯的信息來生成規範表示的解218。在這樣做時，求解器216先從問題高速 緩存212中的對應條目取回如下元數據214，該元數據包括先前用來求解約束問題的規範 表示的求解器試探法。然後，求解器216使用元數據214以通過重建先前已經允許求解器 216求解規範表示210的條件來生成解218。在求解器216生成用於規範表示210的解218之後，求解器伺服器206將解218轉發到求解器客戶機202。在這一實施例的一種變形中，求解器伺服器206從問題高速緩存 212取回預先計算的解218並且將解218轉發到求解器客戶機202。在本發明的實施例中，在將解218轉發到求解器客戶機202之前，求解器伺服器 206將為規範表示210生成的解218轉換成與原約束204 —致的形式。在這一實施例的一 種變形中，求解器伺服器206用原約束204的原變量名取代為規範表示210生成的解218 的任何通用變量名。在本發明的一些實施例中，求解器伺服器206使用後臺過程以精化對用於問題高 速緩存212中難以求解的規範表示條目的求解器試探法的選擇。在這些實施例的一種變形 中，求解器伺服器206選擇其解先前已經需要多於預定計算時間的規範表示條目並且嘗試 使用不同求解器試探法來生成更快的解。在本發明的一些實施例中，求解器伺服器206嘗試通過先應用一求解器試探法以 求解來自規範表示的約束變量的子集並且隨後將該求解器試探法應用於規範表示的其餘 部分來優化用於給定的規範表示條目的求解器試探法。問題高諫緩存圖3圖示了根據本發明一個實施例的問題高速緩存300。問題高速緩存300存儲 規範表示302和與針對規範表示302的約束求解運算關聯的元數據。這一元數據包括求解 器試探法304、計算時間306、持久性標誌308、隨機穩定性標誌310和隨機種子312。求解 器試探法304指代如下求解器試探法，該試探法允許求解器伺服器在預定時間段生成用於 規範表示302的解。求解器伺服器206監視在生成規範表示210的解時的計算時間並且在 與問題高速緩存300的規範表示302條目關聯的計算時間306條目之下存儲這一時間。求解器客戶機的許多用戶持續從隨時間的持久解中受益。例如，當用戶希望產生 用於DUV的具體仿真結果時，求解器伺服器206可以繼續產生用於相同問題隨時間一致的 結果。先前提到在本發明的實施例中，求解器伺服器重訪問題高速緩存的規範表示條目以 精化對應用於它們的求解器試探法的選擇。重要的是求解器伺服器沒有重訪其值隨時間保 持持久的規範表示條目。當為問題高速緩存300中的規範表示302設置持久性標誌308時， 不允許求解器伺服器改變用於對應規範表示302的求解器試探法304。當沒有設置持久性 標誌308時，允許求解器伺服器重訪問題高速緩存300中的規範表示302以搜尋可以在更 短計算時間內求解規範表示的最優求解器試探法。為了進一步增強解隨時間的持久性，針對電路仿真的一些用途可能需要在重訪規 範表示302時的隨機穩定性。隨機穩定性指代依賴於隨機數的運算必須針對固定成組輸入 隨時間產生一致結果這一要求。當求解器伺服器針對多個問題域同時對多個約束執行運算 時可能出現隨機穩定性違規。在這一情形中，針對一個問題域的約束求解運算可能影響另 一問題域的後續約束求解運算所用的隨機種子值。 在本發明的一個實施例中，求解器伺服器能夠以任何順序處理用於多個求解器客 戶機的約束而不會讓一個約束求解運算幹擾後續約束求解運算的隨機穩定性。求解器服務 器在相應規範表示320的解必須隨時間維持隨機穩定性時通過允許規範表示320設置隨機 穩定性標誌310來為對某些規範表示的約束求解運算施加隨機穩定性。如果為問題高速緩 存300中的給定規範表示條目設置隨機穩定性標誌310，則求解器伺服器將把用來求解規 範表示302的隨機種子存儲到隨機種子312條目中。如果求解器伺服器接收對求解如下約束的請求，該約束的規範表示302具有在問題高速緩存300中的對應條目，該條目設置有隨 機穩定性標誌310，則求解器伺服器將從對應條目取回隨機種子312並且使用這一隨機種 子值作為約束求解運算的初始種子。重放機制電路設計者通常需要複製用於約束求解器的給定應用的先前解序列。例如，這可 以作為對電路設計的完整回歸測試的部分而發生，或者它可以是先前確定為激活已知設計 錯誤的孤立仿真運行。因此，用戶可能想要保存先前受約束的隨機輸入刺激序列和生成該 序列的種子以重建先前電路仿真運行。在本發明的實施例中，問題高速緩存300存儲多個重放序列314，其中相應重放序 列314伴隨有解ID 316和外部狀態318。在這些實施例中，求解器伺服器存儲它為它從相 應求解器客戶機接收的約束而生成的解。在這樣做時，求解器伺服器在問題高速緩存300 的重放序列314條目中按依次順序存儲這些解。解ID 316是與重放序列314條目對應的 標識符，求解器伺服器用該標識符來將重放序列與給定的求解器客戶機執行匹配。外部狀 態318包括與可以改變值並且對給定的約束問題有影響的多個非隨機變量關聯的信息。在本發明的一些實施例中，求解器客戶機可以請求求解器伺服器提供重放序列 314以重現先前約束求解應用。在其它實施例中，求解器客戶機可以請求在相同約束求解 應用中更早生成的重放序列314。例如，電路仿真可以請求求解器伺服器提供在用於給定 DUV的回歸仿真期間的重放序列314或者甚至可以請求在相同電路仿真中更早生成的重放 序列314。變換機製圖4A圖示了根據本發明一個實施例的變換機制400。變換機制400將約束402變 換成一個或者多個不相交規範表示410。注意變換機制400包括用於將約束402分割成一 個或者多個不相交約束406的不相交機制404。另外，變換機制400也包括將不相交約束 406變換成規範表示410的歸約機制408。圖4B圖示了根據本發明一個實施例的不相交機制404。不相交機制404接收約束 402並且產生一個或者多個不相交約束406。如果約束從其它約束斷開並且與其它約束無 關，則它是不相交約束，並且它代表單個鄰接問題空間。注意為了能夠將約束402分割成多 個不相交約束406，約束402需要是對多個不相交問題空間的描述(例如，如在圖4B的約束 402中所示的約束不相交)。圖4C圖示了根據本發明一個實施例的歸約機制408。在操作期間，歸約機制408 接收不相交約束406並且產生對應規範表示410。歸約機制408通過對不相交約束執行將 形式相似的約束變換成單個規範表示的一致的運算序列來產生對應規範表示。為了產生規 範表示410，歸約機制408先通過將不相交約束406的運算順序轉換成規範形式來將不相交 約束406轉換成中間表示。接著，歸約機制408按預定順序(例如從左到右)遍歷中間表 示並且通過用變量名遞增序列(例如VI、V2…Vn)取代中間表示的變量名序列來產生規範 表示410。圖5呈現了對根據本發明一個實施例的用於重用與約束求解運算關聯的信息的 過程進行圖示的流程圖。系統通過從求解器客戶機接收約束來開始(操作502)。接著，系 統將約束分割成一個或者多個不相交約束(操作504)並且將不相交約束歸約成規範表示(操作506)。在本發明的一些實施例中，系統僅使用一個所得規範表示以求解約束。在本 發明的其它實施例中，系統求解多個規範表示並且在問題高速緩存中存儲元數據和/或它 們的解以供以後使用。為了解決規範表示，系統在問題高速緩存中搜尋與規範表示對應的條目(操作 508)並且確定對應條目是否存在(操作510)。如果是這樣，則系統從問題高速緩存中的對 應條目中選擇求解器試探法(操作51幻。然後，系統通過使用所選求解器試探法來生成規 範表示的解(操作514)並且將解返回給求解器客戶機(操作522)。如果對應條目在問題高速緩存中不存在，則系統在問題高速緩存中的新條目內存 儲規範表示(操作516)。然後，系統通過使用求解器試探法來生成規範表示的解(操作 518)並且將求解器試探法與問題高速緩存中的新條目關聯(操作520)。最後，系統將解返 回給求解器客戶機(操作522)。圖6呈現了對根據本發明一個實施例的擴展圖5的操作518的用於生成規範約束 表示的解的過程進行圖示的流程圖。系統通過從可用求解器試探法匯集中選擇求解器試探 法(操作602)來開始。然後，系統使用所選求解器試探法預定時間段以生成對給定規範表 示的解(操作604)。接著，系統確定是否找到解(操作606)。如果是這樣，則系統返回解 和用來生成該解的求解器試探法(操作608)。如果沒有找到解，則系統確定是否存在任何未用的求解器試探法(操作610)。如 果存在，則系統返回到操作602以選擇另一求解器試探法。如果不存在未用的求解器試探 法，則系統啟動錯誤處理程序(操作612)。在這一實施例的一種變形中，錯誤處理程序報告 錯誤。在另一變形中，錯誤處理程序將規範表示標註為不可解，從而可以忽略對求解類似約 束問題的以後嘗試。圖7圖示了根據本發明實施例的求解器伺服器的計算機系統。計算機系統702包 括處理器704、存儲器706和存儲設備708。計算機系統702也耦合到顯示設備710。存儲 設備708存儲作業系統712和求解器伺服器714。求解器伺服器714包括接收機制716、變 換機制718和求解器720。在操作期間，求解器伺服器714從存儲設備708加載到存儲器 706中並且由處理器704執行。僅出於示例和描述的目的已經呈現對本發明實施例的前文描述。本意並非讓它們 窮舉本發明或者使本發明限於公開的形式。因而，本領域技術人員將清楚許多修改和變形。 此外，本意並非讓上述公開內容限制本發明。本發明的範圍由所附權利要求書限定。
權利要求
1.一種用於重用與針對問題域的約束求解運算關聯的信息的方法，所述方法包括從所述問題域接收用於約束問題的規範表示；在問題高速緩存中搜尋與所述規範表示對應的條目；並且如果對應條目在所述問題高速緩存中不存在，則在所述問題高速緩存中產生用於所述 規範表示的條目；否則，如果對應條目存在於所述問題高速緩存中，則通過重用與所述問題高速緩存中 的所述對應條目關聯的求解器試探法來生成所述規範表示的解。
2.根據權利要求1所述的方法，其中在所述問題高速緩存中產生用於所述規範表示的 條目包括在所述問題高速緩存中存儲所述約束問題的所述規範表示；從多個可用試探法中選擇求解器試探法；通過使用所述選擇的求解器試探法來生成所述規範表示的解，其中只要所述選擇的試 探法無法在預定時間段內生成解，則系統選擇新的求解器試探法並且使用所述新的試探法 以生成所述規範表示的解；並且將所述選擇的求解器試探法與所述問題高速緩存中的所述規範表示條目關聯。
3.根據權利要求1所述的方法，其中所述方法還包括監視在生成規範表示的解時的 計算時間，並且在所述問題高速緩存中的所述對應規範表示條目中存儲所述計算時間。
4.根據權利要求3所述的方法，其中所述方法還包括使用後臺過程來精化對求解器試 探法的選擇。
5.根據權利要求1所述的方法，其中執行所述方法的求解器伺服器能夠執行多個同時 線程，其中相應線程與獨立約束問題關聯。
6.根據權利要求1所述的方法，其中所述方法還包括將約束問題轉換成規範表示。
7.根據權利要求1所述的方法，其中所述方法還包括通過在所述問題高速緩存中記錄 和保留用來第一次求解指定的規範表示的求解器試探法、由此允許當在以後時間求解所述 指定的規範表示時使用相同試探法來提供用於所述規範表示的持久解。
8.根據權利要求7所述的方法，其中所述方法還包括通過在所述問題高速緩存中記錄 和保留用來第一次求解指定的規範表示的隨機種子、由此允許系統產生與求解個別規範表 示的順序無關的恆定解來為所述規範表示提供隨機穩定性。
9.根據權利要求1所述的方法，其中所述方法還包括記錄用於問題域的約束問題解 序列，並且為後續問題域重放所述解序列。
10.根據權利要求1所述的方法，其中所述方法還包括跨與一個或者多個應用關聯的 多個獨立問題域重用所述問題高速緩存的信息。
11.一種存儲指令的計算機可讀存儲介質，所述指令在由計算機執行時使所述計算機 執行一種用於重用與針對問題域的約束求解運算關聯的信息的方法，所述方法包括從所述問題域接收用於約束問題的規範表示；在問題高速緩存中搜尋與所述規範表示對應的條目；並且如果對應條目在所述問題高速緩存中不存在，則在所述問題高速緩存中產生用於所述 規範表示的條目；否則，如果對應條目存在於所述問題高速緩存中，則通過重用與所述問題高速緩存中的所述對應條目關聯的求解器試探法來生成所述規範表示的解。
12.根據權利要求11所述的計算機可讀存儲介質，其中在所述問題高速緩存中產生用 於所述規範表示的條目包括在所述問題高速緩存中存儲所述約束問題的所述規範表示；從多個可用試探法中選擇求解器試探法；通過使用所述選擇的求解器試探法來生成所述規範表示的解，其中只要所述選擇的試 探法無法在預定時間段內生成解，系統選擇新的求解器試探法並且使用所述新的試探法以 生成所述規範表示的解；並且將所述選擇的求解器試探法與所述問題高速緩存中的所述規範表示條目關聯。
13.根據權利要求11所述的計算機可讀存儲介質，其中所述方法還包括使用後臺過程 來精化對求解器試探法的選擇。
14.根據權利要求11所述的計算機可讀存儲介質，其中執行所述方法的求解器伺服器 能夠執行多個同時線程，其中相應線程與獨立約束問題關聯。
15.根據權利要求11所述的計算機可讀存儲介質，其中所述方法還包括將約束問題轉 換成規範表示。
16.根據權利要求11所述的計算機可讀存儲介質，其中所述方法還包括通過在所述問 題高速緩存中記錄和保留用來第一次求解指定的規範表示的求解器試探法、由此允許當在 以後時間求解所述指定的規範表示時使用相同試探法來提供用於所述規範表示的持久解。
17.根據權利要求16所述的計算機可讀存儲介質，其中所述方法還包括通過在所述問 題高速緩存中記錄和保留用來第一次求解指定的規範表示的隨機種子、由此允許系統產生 與求解個別規範表示的順序無關的恆定解來為所述規範表示提供隨機穩定性。
18.根據權利要求11所述的計算機可讀存儲介質，其中所述方法還包括記錄用於問 題域的約束問題解序列，並且為後續問題域重放所述解序列。
19.根據權利要求11所述的計算機可讀存儲介質，其中所述方法還包括跨與一個或者 多個應用關聯的多個獨立問題域重用所述問題高速緩存的信息。
20.一種用於重用與針對問題域的約束求解運算關聯的信息的約束求解器伺服器，包括接收機制，配置成從所述問題域接收用於約束問題的規範表示；問題高速緩存，配置成存儲用於約束問題的規範表示、存儲與針對所述規範表示的所 述約束求解運算關聯的元數據並且取回與所述規範表示對應的條目；以及求解器機制，配置成通過使用選擇的求解器試探法來生成所述規範表示的解；其中如果所述問題高速緩存沒有包含與所述規範表示對應的條目，則所述約束求解器 伺服器在所述問題高速緩存中產生用於所述規範表示的條目；否則，如果所述問題高速緩存包含與所述規範表示對應的條目，則所述求解器機制通 過重用與所述問題高速緩存中的所述對應條目關聯的求解器試探法來生成所述規範表示 的解。
21.根據權利要求20所述的約束求解器伺服器，其中在所述問題高速緩存中產生用於 所述規範表示的條目包括在所述問題高速緩存中存儲所述約束問題的所述規範表示；從多個可用試探法中選擇求解器試探法；通過使用所述選擇的求解器試探法來生成所述規範表示的解，其中只要所述選擇的試 探法無法在預定時間段內生成解，則系統選擇新的求解器試探法並且使用所述新的試探法 以生成所述規範表示的解；並且將所述選擇的求解器試探法與所述問題高速緩存中的所述規範表示條目關聯。
22.根據權利要求20所述的約束求解器伺服器，其中所述約束求解器伺服器能夠使用 後臺過程來精化對求解器試探法的選擇。
23.根據權利要求20所述的約束求解器伺服器，其中所述約束求解器伺服器能夠執行 多個同時線程，其中相應線程與獨立約束問題關聯。
24.根據權利要求20所述的約束求解器伺服器，還包括配置成將約束問題轉換成規範 表示的變換機制。
25.根據權利要求20所述的約束求解器伺服器，其中所述約束求解器伺服器能夠通過 在所述問題高速緩存中記錄和保留用來第一次求解指定的規範表示的求解器試探法、由此 允許當在以後時間求解所述指定的規範表示時使用相同試探法來提供用於所述規範表示 的持久解。
26.根據權利要求25所述的約束求解器伺服器，其中所述約束求解器伺服器能夠通過 在所述問題高速緩存中記錄和保留用來第一次求解指定的規範表示的隨機種子、由此允許 所述約束求解器伺服器產生與求解個別規範表示的順序無關的恆定解來為所述規範表示 提供隨機穩定性。
27.根據權利要求20所述的約束求解器伺服器，其中所述約束求解器伺服器能夠在所 述問題高速緩存中記錄用於問題域的約束問題解序列並且為後續問題域重放所述解序列。
28.根據權利要求20所述的約束求解器伺服器，其中所述約束求解器伺服器能夠跨與 一個或者多個應用關聯的多個獨立問題域重用所述問題高速緩存的信息。
全文摘要
本發明的一個實施例提供一種用於重用與針對問題域的約束求解運算關聯的信息的系統。該系統通過從問題域接收約束問題來開始。然後，該系統在問題高速緩存中搜尋與規範表示對應的條目。如果對應條目在問題高速緩存中不存在，則該系統在問題高速緩存中產生用於規範表示的條目。否則，如果對應條目已經存在於問題高速緩存中，則該系統通過重用與問題高速緩存中的對應條目關聯的求解器試探法來生成規範表示的解。
文檔編號G06N5/02GK102084381SQ200980000255
公開日2011年6月1日 申請日期2009年7月13日 優先權日2008年7月21日
發明者G·R·瑪圖拉納 申請人:新思科技有限公司