多重處理環境中透明動態優化的方法和系統的製作方法

2023-10-08 09:49:39

專利名稱：：多重處理環境中透明動態優化的方法和系統的製作方法
技術領域：
：本發明一般而言涉及軟體系統，具體地涉及用於改進對此種系統的調整(tuning)以提高其性能的方法。
背景技術：
：建造一個典型的軟體系統包括若干步驟，並最終產生一個綁定模塊(或「可執行的二進位程序」，executablebinary)，該模塊已被調整(調優)，從而在一個特定的硬體和軟體配置上執行。這個稱為「靜態優化」的處理過程可能包括以下步驟帶優化地編譯程序，插入插截(instrumentation)，與預先建造的運行時程序庫(runtimelibrary)進行靜態或動態綁定，在某種預期用戶配置的樣本上使用一定範圍的預期用戶輸入進行測試，以及基於測試過程中收集的數據帶優化地再次編譯(這稱為「通過剖面法(profile)指導的反饋進行的優化」)。人們期望，由此產生的程序在預期的用戶配置和輸入數據的範圍內既是健壯的，也是最優化的。然而，在現實中，用戶環境的範圍是如此寬廣，以至於這樣的程序無法在所有情況下都獲得最佳性能。人們很早就認識到，靜態技術(即在操作環境之外搜集關於代碼執行的信息，以便為隨後的執行微調代碼)不適於產生有效的代碼，因為要生成代表所有可能的最終用戶數據和硬體配置的測試數據是很困難的，如果不是不可能的話。此外，隨著指令級別上的並行性增加以及流水線加深，這種不適合就變得逾加令人煩惱了。與靜態優化技術不同的另一種方法是「動態優化」。動態優化與帶有剖面法指導的反饋(profile-directedfeedback)的靜態優化的相似之處在於，它也包括在將被優化的代碼中插入插截、編譯它，並將其與運行時程序庫靜態或動態的綁定起來。然而，動態優化與靜態優化的不同之處在於，被插截的代碼(instrumentedcode)是在使用實際用戶數據、實際執行程序時被觀察的，而執行代碼是被當場再優化的(即如此搜集的關於程序運行的信息被用於在同一運行中對代碼進行再優化，用於隨後的(同一次運行中)的執行)。動態優化所產生的優化代碼常常比靜態優化技術所能取得的效率更高，因為能夠集中關注於例如代碼的那些被頻繁使用的部分，這些部分的效率的提高可以影響到如實際的程序使用所表現的整體性能。此外，使用動態優化時，不需要客戶執行繁重的生成假設數據集的任務。然而，在上述動態優化系統中，動態優化的缺點是必須進行的信息的收集和編譯工作是相繼散布在應用代碼的執行中的，這樣就增加了應用的執行時間。應用的運行時間方面因優化得到的改善必須超過此附加成本，才能從動態優化中獲得任何益處。動態優化的例子包括人們提出的通過對Java字節代碼進行動態編譯和優化來優化Java應用的執行的技術。此項技術的關鍵是，由於典型的字節代碼執行顯著慢於大多數編譯的應用，運行時優化處理的開銷可以由執行過程中的不大的改善而吸收。而這樣的機會在已高度優化的非Java(二進位代碼)應用中是很少存在的。此外，該方法所採用的很多技術，如優化方法調用，並不是普遍適用的。其它項目，如V.Bala等人的「TransparentDynamicOptimizationthedesignandimplementationofDynamo」(HPL1999-1978990621)中所描述的技術，通過重新安排代碼布局來改善指令緩存局部性，來解決動態改善運行時性能的問題，它所基於的假設是，開銷可以由所產生的執行時間方面的改善來補償。然而，Dynamo技術沒有利用插截信息(instrumentationinformation)，而且由於它是為單處理器系統設計的，也沒有考慮多處理器應用。然而，今天的計算機系統通常包含不止一個處理器。即使在低端，單片多處理器也正在變得普遍起來。常見的情況是，在許多這些配置中，至少其中的一個處理器被利用不足。利用多處理器能力以改善程序執行的早期努力集中於諸如應用的自動並行化的技術。這些技術只取得有限的成功，這是由於多種原因，其中最顯著的一點是自動並行化最適用於數值計算密集的應用，特別是哪些使用Fortran編寫的應用；而通常以C語言編寫的商業事務處理應用，事實證明不那麼適於這種方法；而且，即使對於較常規類型的代碼，自動並行化也已證明在實踐中難以實施。因此，顯然需要一種優化處理過程，它可以利用多處理器系統的獨有特性，並面向更廣泛類別的代碼。
發明內容鑑於傳統方法和結構的上述和其它問題、障礙和缺點，本發明的一個目的是，通過抓住時機地利用一個或多個空閒的或利用不足的處理器，而提高多處理器系統中的程序執行效率。本發明的另一個目的是通過了解軟體系統的執行特徵，並應用此種知識，以對系統的用戶透明的方式，來調整和提高在當前主機系統上的執行行為，而改善該軟體系統的性能。具體而言，本發明試圖通過利用對稱或分布式多處理器系統中的可用周期，實現此性能提高，而不妨礙被優化應用的執行，從而對傳統方法和系統進行改進。在本發明的第一個方面中，一種在多重處理環境中進行透明動態優化的方法(和系統)，包括使用運行於系統的另一個處理器上的執行監視器，來監視一個第一處理器上的應用的執行，並使用運行於系統的該另一個處理器上的運行時優化器，來透明地優化原始應用的一個或多個片段。在本發明的第二個方面中，一種用於多處理器計算環境對應用進行相對於其執行環境的同時的、動態的優化的方法，包括在系統的一個第一處理器上執行該應用的被插截的(instrumented，被加入檢測代碼的)複本；使用運行於該系統的另一個處理器上的執行監視器監視該應用的執行，該監視是參照執行特徵而進行的，該執行特徵是通過執行包含於該應用的被插截的複本中的插截代碼而產生的；使用執行於該系統的另一個處理器上的運行時優化器對原始應用的一個或多個片段進行優化，該優化是參照該執行監視器所收集的執行特徵而進行的，並且不會影響並行執行的應用的性能；通過使用新近優化的片段代替一個或多個片段而修改原始執行應用，該修改是以對該應用的用戶透明的方式進行的。在本發明的第三個方面中，一種用於在多處理器系統中對應用進行相對於其執行環境的同時的、動態的優化的方法，包括使用運行於一個單獨的處理器上、或作為單獨的處理過程運行於多個處理器上的執行監視器，監視運行於一個第一處理器上的一個程序或應用的每次執行；由二進位代碼在其執行時，創建二進位代碼的執行特徵的簡表數據(profiledata)，該二進位代碼包含用於監視性能的插截代碼；執行監視器不斷地評估該簡表數據；並當一個給定閾值條件滿足時，調用動態優化器，來優化頻繁執行的代碼片段，優化後的代碼片段被插入執行的指令流中，用於其後續的執行。在本發明的第四個方面中，一種在共享多重處理(sharedmultiprocessing，SMP)系統中進行透明動態優化的方法，包括在一個第一處理器上執行應用二進位程序；在該系統的另一個處理器上監視該執行的行為，並在應用二進位程序執行的同時，對應用二進位程序的執行進行優化。在本發明的第五個方面中，一種在多重處理系統中進行透明動態優化的系統，包括一個執行監視器，用於監視在一個第一處理器上一個應用二進位程序的執行，該執行監視器運行於該系統的另一個處理器上，該執行監視器包括一個動態優化器，用於與監視同時地優化該原始應用二進位程序的一個或多個片段，該優化器執行於該系統的該另一個處理器上。在本發明的第六個方面中，一種信號承載介質，以有形的方式體現了機器可讀的指令的程序，該程序可由數字處理裝置執行，以在多重處理系統中執行透明動態優化的方法，該方法包括使用運行於該系統的另一個處理器上的執行監視器監視一個第一處理器上的應用二進位程序的執行，並使用執行於該系統的該另一個處理器上的運行時優化器透明地優化原始應用二進位程序的一個或多個段。因而，使用本發明時，優選地使用多重處理系統中多餘的處理周期來觀察執行中的應用的執行特徵，並透明地修改此運行的系統，以顯著提高其性能。優選地，程序或應用的每次執行由一個執行監視器「跟蹤」(shadow)，該監視器運行於另一個處理器上，或作為一個單獨的進程運行於多個處理器上。當它執行時，包含被設計用來監視性能的插截代碼的該二進位代碼創建其執行特徵的簡表。執行監視器不斷地評估此簡表數據，並當滿足給定閾值條件時，調用本發明的動態優化器，以優化(或再優化)頻繁執行的代碼片段，然後將其插入該執行指令流中，這裡它們被用於隨後的執行。新插入的代碼片段或者不包含插截，或者被再次插截以便檢測該應用的執行特徵中的進一步變化。本發明把上述技術應用於二進位可執行(文件)，而不是Java的字節代碼，後者由於是被解釋的，因而執行得足夠慢，以至於可逐步補償優化的成本(但是，同樣的技術對於字節代碼應用也是有效的)。就是說，二進位程序(代碼)是以如此方式被插截的，以至於當它運行時，能夠在共享多處理器(SMP)系統的另一個處理器上監視其執行行為，並在其執行過程中，該此另一個處理器上，對它進行優化。從參照附圖對本發明的優選實施例所作的如下詳細說明，可以更好地理解本發明的上述及其它目的、方面和優點，在附圖中圖1示出了用於運行本發明的一個多重處理系統100的系統視圖；圖2所示增強視圖200示出了根據本發明的用於運行被插截的二進位(程序)201a的處理器201，以及用於運行動態優化器207的處理器203。圖3的流程圖示出了根據本發明的動態優化處理過程300；圖4的流程圖是本發明的動態優化器的處理過程400的另一個實施例400，它適用於利用在靜態優化處理過程中收集的信息，具體而言，其中編譯時收集的數據被保存在可執行程序中，以便由執行監視器的動態優化器組件在運行時使用。圖5A-5C示出了在圖4所示方法400中創建的注釋文件，具體而言，圖5A示出了一種稱為控制流圖(ControlFlowGraph)的編譯時數據結構的可視表示，圖5B示出了該流圖的編碼表示，它可以形成該注釋的二進位(程序)的一部分，而圖5C代表可能被包含在圖5B的例子的注釋文件中的實際數據；圖6示出了本發明的一個進一步的實施例，它允許對那些在靜態優化時未被插截的二進位應用進行動態優化；圖7示出了本發明的一個實施例，它用於如前述具有IBM檔案編號(IBMDocketNo.)YOR920010532US1的美國專利申請號10/_,_所描述的仿真器(emulator)；以及圖8示出一種信號承載介質800(如存儲介質)，用於根據本發明的方法的程序的存儲步驟。具體實施例方式現在請參照附圖，更具體地說，參照圖1-8，其中示出了根據本發明的方法和結構的優選實施例。大體上說，本發明以新的方式利用了多重處理能力，以獲得在多處理器系統上執行程序時顯著的性能改善。純粹靜態編譯器一般假設程序中的所有路徑都同等地可能被採用，因而通常對所有可能路徑進行同等程度的優化。然而，由於在實際上可能更經常採用某些路徑，因而如果選擇關鍵的路徑進行優化，甚至付出減慢不常採取的路徑的代價，優化可能會更有利。另一方面，純粹動態編譯器(如Java字節代碼程序的大多數及時(just-in-time，JIT)編譯器)，儘管擁有程序當前執行的詳細信息，卻由於需要在很窄的時間窗(temporalwindow)內使用此信息的苛求而被嚴重阻礙。正如下面將說明的，本發明相對於已知的動態編譯器有兩個優點。首先，由於其多處理器設計，它實際上不需要運行在如此受限制的時間範圍中。其次，在進行優化操作時，它可以利用靜態優化輸出，以便減少執行過程中程序分析的需要。此外，在不太遙遠的未來，預期幾乎所有系統都將用單片多處理器建造，因而使得本發明的方法格外意義重大。在即將在這裡描述的本發明的一個實施例中，我們假定動態運行時優化系統(或「動態優化器」)-該系統包含的那些方法來監視代碼執行，基於收集到的執行信息對代碼進行優化，並將被優化的代碼重新插入程序-可以作為子線程或進程而處於持續運行的執行監視器控制之下，在一個處理器(或一組處理器)中執行，該處理器獨立於執行被監視程序的一個處理器(或一組處理器)。進一步地，將被優化的執行代碼被使用諸如Ball等人的「EfficientPathProfiling」(ProceedingsofMICRO1996，Dec.1996)中所描述的技術編譯以納入插截代碼。因而，本發明假定執行的二進位代碼已經被插截(例如靜態地或動態地)，正如在本領域中廣為人知的。本發明的一個重點是以新的方式利用該插截代碼所產生的信息。應當注意的是，儘管上述描述假定使用SMP環境，但本發明也適用於這樣的計算機系統，它由一個或多個處理器的一個群集所構成，這些處理器通過分布式共享存儲器進行通信。在這樣的配置中，動態優化系統既可以在群集中的一個(或多個)節點上執行，也可以在群集中的一個節點的一個(或多個)處理器上運行，只要它們與執行待優化代碼的節點或處理器不同。下面，我們將參照圖1，詳細描述本發明，該圖示出了運行於多重處理硬體系統100之上的動態優化器。多重處理系統100可以包括大於1的任意數量處理器101a、101b等，在圖1中每個處理器分別被標以1至n+1。每個處理器可以具有自己的局部存儲器(圖1中未示出)，而所有處理器都可以通過一個共享的主存儲器102進行通信。該系統被一個作業系統103控制，該作業系統包含或支持一個線程調度軟體包。對於每一個被插截的、且在本發明的動態優化處理過程中執行的程序(如執行的二進位程序)，在一個執行監視器104中將繁育(spawn)一個同時性的執行監視器線程，下面將詳細描述。執行監視器線程的目的是分析給定執行中的被插截的二進位代碼(程序)的執行行為，並進一步根據此種分析，進行更改(優化)，它將保持該應用的期望輸出，但減少產生這些輸出的時間。此(監視器)線程只當它監視的應用執行時才執行。因此，圖1示出了有1至n個處理器執行真正的應用，其中每個都可能與所有其他的不同，並至少有一個另外的處理器n+1(例如，可能有多個其它處理器，如n+2等，但簡便起見只示出一個)。有一個執行監視器104與運行在處理器1至n上的每一個被插截的二進位(程序)相關聯。它們不需要都只運行在處理器n+1上。根據這樣的執行監視器104耗用多少資源，它們也可以運行在其它一個或多個不同的處理器上。然而，在執行監視器的數量和在處理器1至n上運行的被插截的二進位(程序)的數量之間存在著一對一的關係。應當注意的是在一個SMP的多於一個的處理器上可能有多於一個被插截的二進位(程序)在執行。這裡描述的關係只是在這樣的被插截的二進位(程序)和它自己的「影子」(跟蹤)進程之間(如下面描述並如圖2中的標號201a和205所示的)。正是這種一對一關係，是本發明所關注、並有利地加以利用的，而本發明只要求一個給定的被插截的二進位程序的影子進程執行在一個分離的處理器上。這樣，當處理器1(101a)執行其二進位(程序)時，處理器1的執行特徵由一個專用的執行監視器104觀察。圖2是一個概念性視圖200，它表現了在一個第一處理器201上執行的、將被優化的被插截的二進位應用201a，和監視此被插截的二進位應用201a的執行的執行監視器線程205之間的交互，該執行監視器在與處理器201不同的處理器203上被執行。在圖2中，執行的被插截的二進位(程序)可能由一個相當大的系統構成，並執行很長時間。在這裡，執行的被插截的二進位(程序)在執行過程中被監視和修改的方法稱為一個「影子」進程。該影子進程包括使用一個執行監視器、一個動態優化器和一個片段表(或高速緩存)管理器。在被插截的二進位(程序)的啟動時，該「影子」即被派生(fork)，並在被插截的二進位(程序)或應用的執行過程中繼續執行。影子進程205也包括一個片段高速緩存(fragmentcache)201b。應當注意的是，片段高速緩存201b是影子進程的一種軟體產物，用於在向執行的代碼流重新插入它們之間保存優化後的代碼片段。該數據結構很大，並由「片段高速緩存管理器」管理，以便動態存儲被插截的應用201a的被再優化的片段。這些「片段」是被頻繁執行的指令序列(由執行監視器線程基於它對插截代碼所產生的插截信息的分析而確定)，這些指令序列可能隨後由處理器201作為該應用的一部分而執行，它們是當「影子」進程確定該片段的優化可以導致程序執行得更有效率時，在影子進程的執行或簡表監視步驟(204)中被選擇的。應當注意的是，只有執行的二進位程序的被選擇部分才被存儲在片段高速緩存201b中。這些部分是基於插截(代碼)的輸出而選擇的。基本上，它們包括被頻繁執行的指令的序列，以及優化功能認為必要和可接受的某些添加或刪除。執行或簡表監視器204可能監視各種特徵，包括程序中某一特定路徑被執行的次數。因此，如果一個路徑被執行了很多次(如1000次或更多)，則它將觸發片段管理器202，開始對此路徑進行某種處理，並開始針對此特定代碼片段的優化處理過程(使用下面將討論的動態優化器207)。因而，處理器203也運行動態優化器線程207，作為影子進程線程205的一部分，用於優化來自被插截的二進位應用的所選擇片段，並通過片段管理器202，將優化後的片段傳回片段高速緩存201b。在上例關於監視程序中的路徑被執行了多少次、以及是否此種執行發生的次數已超過一個閾值(臨界)次數(如多於1000次)的情境中，片段管理器202採取行動，從片段高速緩存201b中提取該路徑(例如，執行的二進位程序的一部分或一個「片段」，它是一個較小的代碼塊)或該路徑的一部分，以便由動態優化器207進行優化(或再優化)。因此，這些片段被取出、優化然後再放回到運行的二進位程序中。片段管理器202確定應當優化該路徑的哪個部分。很可能這不是整個路徑。片段管理器202通過製作該指令的複本而「抽取」(提取)該部分路徑，並存儲這些指令，以便優化器207可以察看複本，並對複本進行更改。就是說，片段管理器202「告訴」優化器207執行這種優化，並向它提供片段管理器202認為與該片段有關的簡表信息。然後，優化器將對該片段進行優化(如重排代碼的順序等，以便使其更快和更有效)，並在完成後，通知片段管理器202。然後，片段管理器202，使用存儲在它自己的內部表中的數據，確定在處理器1(201)上的原始執行的二進位程序中重新插入被優化的代碼的正確的邏輯位置。然後，被優化的代碼被放入處理器1(201)的片段高速緩存201b中，而片段管理器202將修改執行的程序，從而下次在執行的二進位程序中同樣的路徑(指令)(或者路徑的一部分，如在可能的情況下)需要執行時，片段高速緩存201b中的代碼片段將被挑選執行，代替原始執行二進位程序中的代碼。應當注意的是，片段管理器202在第一次會直接從被插截的執行的二進位程序201a中提取一段路徑，而在以後的階段(例如，路徑再優化)，片段管理器202將從片段高速緩存201b中提取它，而不是直接從被插截的執行的二進位程序201a中提取。因此，片段可以以兩種形式出現作為原始二進位程序(或後來的動態優化後的二進位程序)中的真實代碼序列，以及作為動態優化器產生的重新插入的被優化的代碼序列。後者出現在片段高速緩存201b中，而前者(除了上述括號中的情況之外)出現在原始應用中。對於每一個執行的被插截的二進位應用，將有一個執行監視器線程(影子進程線程)205的實例，在這裡，一個給定的被插截的二進位應用的執行監視器被稱為它的「監視線程」。執行監視器(或影子進程)線程205的操作是與應用平行進行的，但不為應用所知，應用的執行過程，除了產生表現它自己的執行特徵的簡表流之外，沒有變化。應當注意的是，「執行特徵」代表由被插截的二進位程序作為執行的副作用而產生的簡檔數據。此外，應當注意的是，片段高速緩存201b只是一個數據結構或表，它存在於(駐留在)共享存儲器中，由執行監視器線程205的片段管理器202分配和控制。如上所述，片段是這樣的指令序列，其執行特徵使它成為潛在的(再)優化對象；該指令序列將由執行監視器(影子進程)205從執行的二進位程序中提取，優化後保存在片段高速緩存中，以便隨後重新插入到二進位程序中。還應當注意的是，由於目的是優化這些片段，並重新把它們插入執行的二進位程序，因此它們在片段高速緩存201b中的駐存是暫時的(transient)，並使用標準技術管理和收回其存儲(空間)。本發明的方法圖3的流程圖示出了與本發明的動態優化處理過程有關的圖2所示的系統所進行的方法300的步驟。在方法300中，當把被插截的二進位程序裝入處理器201之時，即執行一次派生，以在圖2所示的處理器203(n+1)中啟動執行監視器線程(步驟300A)。進一步講，當裝入被插截的二進位應用時，即在步驟301繁育(派生)一個執行監視器線程，用於在圖2所示處理器203(n+1)上與處理器201上被插截的二進位應用的執行並行地執行。如上所述，執行監視器線程也稱為「影子線程」，因為它觀察或監視被插截的二進位程序的執行。影子進程(執行監視)線程的繁育是通過執行諸如FORK或其它某種作業系統(OS)原語實現的。再次強調，應當注意此種活動的並行性質。這種並行性很重要，因為它允許使用更主動的技術，並允許定時的誤差(錯誤)，這是由於在處理器201上運行的被插截的二進位應用不知道分析和優化處理過程，因而從來不需要等待(不象上述Dynamo或JavaJIT的情況)。儘管被插截的二進位應用可以是被設計用來進行基準檢測(benchmarking)的程序，當該系統與實際的用戶應用一起使用並執行實際的用戶數據時，該系統的真正益處才得以實現。作為執行被插截的二進位程序的一部分，在步驟302中，產生執行簡表。執行簡表描述執行的二進位程序(或正在運行的程序)的執行特徵。這些特徵是由插入到該二進位應用的特定的插截代碼(instrumentationcode)確定的。插截代碼可能被設計用來監視的特徵的例子包括該應用中一個特定循環執行的次數，或更特別地，一個特定路徑或代碼塊序列被執行的次數。應當注意的是，簡表數據是由被插截的應用在共享存儲器中產生的，而影子進程(執行監視器)線程從同一個共享存儲器位置讀取它。監視器線程並不非常嚴格地依賴於任何一個簡表計數器的絕對值(例如，一個循環的10,000次執行和10,0001次執行甚至11,000次執行並沒有顯著不同)，因而不需要在應用線程和監視器線程之間鎖定或其它同步方法。如下所述，該信息是在產生的過程中連續提供的。因而，這是一個動態處理過程，並且因為此種信息是連續地被提供的，執行代碼可以在執行發生時實際地被修改。因此，在步驟302，圖2所示運行於處理器203之上的執行監視線程205持續地監視所產生的簡表信息(例如，也稱為「執行特徵」)，而監視線程205唯一地與當前接受檢驗的被插截的二進位應用相關聯。為了描述當前實施例，我們假設監視線程運行於一個單獨的處理器之上，此處理器與執行正在接受檢驗的、被插截的二進位應用的處理器不同。然而，本發明的意圖是，監視線程也可以在多個處理器上運行，只要這些處理器與正在執行被插截的二進位應用的處理器不同。在步驟304，影子進程(執行監視器)205檢驗所產生的簡表數據，以確定臨界(閾值)條件是否滿足。就本示例性實施例而言，可以採用一個計數據器或增數/減數器(incrementer/decrementer)。可替代地，在不同的實施例中，可以使用不同的結構。例如，根據正在檢測的閾值是什麼、或者條件或正在檢測的閾值的複雜性，可以使用計數器和某種其它裝置的組合(或者多個計數器的組合，其中各計數器的總和達到某個值時，其依次指示某種條件)。通常，採用的閾值是在插截時設置的，而且在執行時它們被逐步減少，因而達到零值即觸發調用優化器207。進一步地，通常「閾值」是與某種計數或數量相聯繫的(例如，相同的代碼被執行的次數)，這與被檢測的某其它類型的值是不同的。優選地，優化器207是一種通用編譯器優化器。已經意識道，它是在運行時執行的，並且這樣與典型的編譯時優化器相比必須用較少時間執行，但除此之外，它在任何方面都不是專門適應於它正在優化的二進位應用。動態優化器207通常分析包含它被調用來處理的「片段」的特定指令序列，並通過例如對指令序列重新組合以便補償當基礎硬體不是代碼為之編譯的特定型號時可能發生的延遲，來改善其性能。動態優化器270通常與動態編譯系統預封裝在一起。例如，它可能作為計算機的作業系統(OS)的一部分而分發。只要閾值還沒有達到，監視線程205就將繼續檢驗插截(代碼)的輸出。如果達到閾值，則在步驟306，造成閾值到達的二進位應用的那部分就被從被插截的二進位程序中抽取出來(如由片段管理器207複製)，並發送給動態優化器207進行優化，並在優化後存儲在片段高速緩存201b中，以便此後當本來要執行原始的(未進行再優化的)片段時使用。接著，在步驟308中，該片段被優化器207優化。如上所述，所採用的優化處理過程是可用於在運行時優化代碼的許多標準優化技術之一。優選的優化類型是那些利用在靜態編譯時尚不知道的信息(例如，一個給定變量在運行時具有一個恆定值)的類型。此外，可以進行這樣的優化，根據存在大量證據表明一個給定變量確實具有一個恆定值，推測該變量具有該設想的值。當然，在這種情況下，必須為這種猜測不正確的情況作好準備。我們注意到，這樣的考慮在本領域是為人所知的，但是在這裡，本發明將它應用在新的情境中。例如，優化可以包括從頻繁執行的代碼路徑中取消不必要的分支，或者使應用專用於充分利用它正在其上運行的特定網絡節點的體系結構能力。大體上說，如果應用已被編譯以運行於一種機器的早期型號(或更便宜的型號)上，並在當前情況下運行於較晚的機器(或更昂貴和高端的機器)上，則會存在進一優化的機會。例如，可能有新的和更強大的指令，或者與應用原來為之編譯的機器相比，當前機器有更多指令級並行性(如更多的功能單元)。這些可能的情況(在網絡化的世界裡，它們正變得越來越可能了)將導致動態再優化的顯著機會。因而，這呈現了應用這些技術的另一個理由。就是說，在網絡化世界裡，人們有強烈的動機為特定體系結構的「最小公分母」型號進行編譯，因為這樣應用可以運行於網絡中更多比例的計算機上。然而，這也提供了降低優化水平(因而降低性能)的動機，本發明的技術對於改善這樣的應用的運行次數特別有用。可選地，圖3中的方法300允許在被優化的片段中插入插截代碼，以允許隨後的監視。這種在片段中自動插入插截代碼的做法，相信是人所熟知的，因而簡略起見，這裡就不進一步描述了。上述Bala等人的文章(及其它文章)講授了如何插入插截(代碼)。當在步驟308由動態優化器207進行優化之後，在步驟310，優化後的片段被保存於片段高速緩存201b中。然後，在步驟312中，已優化的片段被插入被插截的二進位程序中，代替未優化的版本，這樣在將來，在被插截的二進位的隨後的執行時，它將作為被插截的二進位程序的一部分而被執行。作為示例，這種插入操作可以通過這樣的方法完成，即對原二進位程序進行修補(patch)，使其分支到新優化的片段，而該優化的片段當然也必須分支回原來的(被提取的)的片段之後的指令。也可以使用其它技術，正如當本領域普通技術人員從整體上理解了本發明之後，所能清楚地理解的。可選地，在插入二進位應用之前，該插截代碼也可以被從片段中刪除。在這種情況下，並非插截代碼本身被刪除了，因為它實際上沒有重新插入。插截(代碼)是相當程式化的並且容易被識別，因此應用代碼可以很容易地與插截區分開來，因而避免並不困難。即使情況不是這樣，使插截的位置由插截代理(instrumentingagent)記錄在已知的(或可發現的)位置，也不困難。當在步驟312中優化後的片段插入執行的二進位程序之後，在步驟313中，將確定被插截的二進位程序是否仍在執行。如果被插截的二進位程序仍在執行(如步驟313中的「是」)，則本處理過程循環回到步驟302。如果被插截的二進位程序並非仍在執行(如步驟313中的「否」)，則本處理過程進行到步驟314。在步驟314中，被插截的二進位程序和執行監視器(影子線程)的執行終止。因而，二進位程序和影子線程的執行是同時終止的。確實，本發明的一個關鍵特徵就是所有步驟都是在執行時發生的。應當注意的是，如上所述，圖3所示的兩個垂直流程是並行操作。第二個實施例現在參照圖4討論本發明的另一個實施例，它是對圖3所示處理過程的改進，具體而言可用於圖3中的步驟308。就是說，在圖3的步驟308中，動態優化器207檢驗一個片段，並分析該片段，以確定可以執行何種優化，而優化該片段。這種優化決定只是基於動態優化器此時能夠觀察到的東西。在圖4的方法400中，採取了一些附加步驟以使動態優化器207進行更好的優化。在這方面，在步聚308中為動態優化器207提供了附加信息，以便該優化器可以更快地運行，而不需要優化器自己計算此種信息。此外，還可以為優化器提供它在其它情況下可能很難自己提取的信息。具體而言，圖4示出了一種動態優化方法400，該方法利用了一個應用程式的靜態編譯時所收集的信息。按照本發明的這一實施例，動態優化器207可以利用編譯時所收集的關於該被插截的二進位程序的信息，該編譯在這裡稱為動態優化處理過程的「靜態編譯階段」。應當注意的是，由靜態編譯器所產生的數據/信息一般保存在一個注釋的二進位程序中，其可以是被插截的二進位程序，該程序具有一個擴展(例如附加其上的一個注釋)以包含額外信息。在靜態優化時能夠收集的、並有助於動態優化的信息可以包括流圖信息，特別是那些標籤是一個給定分支的目標，以及靜態的數據依賴性，在運行時，由於消除了這種依賴的模糊性，而可以使得編譯時受到抑制的優化可以進行。本實施例可能特別有利地利用了編譯時更容易檢測的詳細信息，從而排除了代價高昂的運行時的分析。方法400開始於圖4的步驟400A，其中以上面參照圖3所描述的方式將插截代碼插入已編譯的程序。上述注釋是在編譯時通過收集靜態程序信息(不是通過使用一組特定的樣本數據執行程序而收集的簡表數據)而產生的。在步驟402，編譯進行，並且信息在編譯的各種階段，如前端處理(FrontEnd)、優化(Optimizeton)、寄存器分配(RegisterAllocation)和最終彙編(FinalAssembly)階段被收集。步驟404描述在收集到有用信息的各種位置(peint)上編譯器的中間語言(IntermediateLanguage，IL)的注釋。在步驟406中，由靜態編譯階段產生的二進位程序不僅包括自本說明書開始至此一直提及的插截，而且也包括編譯時產生的注釋。這些注釋採取的形式是附加於二進位模塊的編碼的數據串。步驟410-414按圖3所述的方式進行，但不同之處在於包含在已注釋二進位程序中的信息被執行監視器(影子進程)系統的動態優化組件展開(deploy)。應當注意的是，修改只是針對二進位程序的，並與二進位程序的執行並行地進行。如果不需要進一步的靜態優化，則在步驟402收集的信息被用於創建一個注釋文件，該文件將在步驟408中被附加到該被插截的二進位程序上。這種文件的一個例子如圖5A-5C所示。具體而言，圖5A示出了一個稱為控制流圖(ControlFlowGraph)的編譯時數據結構的可視表示500。該圖中的每個節點(即1-12)代表一個基本塊，而有向線代表連接節點的後繼邊(successoredge)。這裡代表的程序包括一個計算的轉移表(branchtable，分支表)。圖5B示出可能構成已注釋的二進位程序的一部分的流圖的編碼表示。圖5C代表此例的可能包含在注釋文件中的實際數據540。動態優化器207有可能會在運行時使用此數據快速重建此圖。然後，已注釋的、被插截的二進位程序就準備好，可以在裝備了根據本發明的動態優化工具207的多處理器系統中運行。在步驟408中，該程序被使用實際的用戶數據在一個第一處理器或第一組處理器上運行，該程序在步驟410中，在與執行該二進位應用本身的處理器不同的一個或一組處理器上，為被插截的二進位應用繁育執行監視器線程。在步驟412，動態優化器使用靜態優化時產生的注釋，以及由包含在執行的二進位程序中的插截(代碼)產生的信息，來生成改進的優化二進位程序；如同上面參照圖3的步驟302-312所描述的，但經過了修改以利用注釋。第三個實施例轉向圖6中處理過程600的流程圖，該圖顯示，根據本發明的動態優化系統的另一個實施例，包括在將被優化的二進位應用的執行過程中，檢測該二進位應用的某些已經被頻繁執行的、未被插截的(non-instrumented)模塊的能力。如果檢測到這樣的模塊(步驟610)，本發明規定了自動插入插截代碼，以用於隨後的監視和優化。應當注意的是，圖6的內容可以被視為優化的一個特例，從邏輯上講，圖6的步驟與圖3中的框306和框312之間一致。為了避免修改有可能會與其它應用「共享」的代碼，在步驟620中，系統製作了原始模塊(未被提取簡表的(unprofiled)二進位程序)的複本，並維護一個如此更改的任意模塊的列表。然後，步驟630調用該方法，以對二進位模塊中進行插截。在將來調用該模塊時，監視器可以立即切換到被插截的版本，並執行它以產生將由執行監視器(步驟640)讀取的簡表。就是說，步驟640修改「熱的」(hot)片段，從而在下次調用時調用被插截的版本。然後，本方法進行到圖3中的步驟310，並繼續進行直到該執行在步驟314終止，此時，在步驟650中，複製的二進位程序列表被刪除。本技術允許在例如由於無法得到原始碼而無法編譯的組件中進行插截。二進位運行時程序庫是可以用這種方式優化的這種組件的一個例子。本發明的這個方面的進一步應用允許遺留(即未被插截的)的二進位程序通過應用所描述的自動重編譯技術，而享受處理器組織的結構化增強或提高的益處。第四個實施例在如圖7所示本發明的另一個實施例中，在動態轉換一個目標應用的指令流用於在如上述Nair等人的、具有IBM檔案編號YOR920010532US1的美國專利申請No.10/_,_所描述的宿主系統上運行的處理過程中，產生被插截的二進位程序。圖7示出了系統700，它包括由用於宿主處理器750的線程調度器740調度的仿真(emulation)線程710、轉換線程720和服務線程730。在如圖7所示的本實施例中，仿真系統700具有執行監視器線程，它是仿真系統700的一個不可少的部分，即轉換線程720之一。一個或多個轉換線程被用來動態地優化由執行監視器選擇的代碼片段。在圖7所示系統700中，頻繁執行的代碼序列被動態優化，以提高性能。這些序列是由解釋器轉換線程插入的插截代碼識別的，其採用計數器來跟蹤被緩存的代碼的執行頻率。監視器線程不斷追蹤這些計數器的值，並在其達到某個閾值時，發信號通知優化器線程對一個給定代碼序列進行(更多)優化是有益的，並且指明引入該將被優化的代碼序列的(被仿真的)賓客(guest)指令的真實地址。除了上述硬體/軟體環境以外，本發明的一個不同方面包括一個用於執行上述各方法的計算機實施的方法。作為例子，該方法可以在上述特定環境中實施。例如，這樣一樣方法可以通過操作由數字數據處理設備所體現的一個計算機，來執行機器可讀指令序列而被實施。這些指令可以駐留在各種信號承載介質中。作為例子，這種信號承載介質可以包括CPU中包含的RAM，如由快速訪問存儲技術所代表的。可替代地，該指令也可以被包含在其它信號存儲介質中，例如可以由CPU直接或間接訪問的磁性數據存儲盤800(圖8)中。不管是包含在磁碟800、計算機/CPU中，還是包含在其它地方，該指令可以被存儲在各種機器可讀的數據存儲介質中，如DASD存儲(如傳統的「硬碟驅動器」或RAID陣列)、磁帶、電子只讀存儲器(如ROM、EPROM或EEPROM)、光存儲設備(如CD-ROM、WORM、DVD、數字光帶等)、紙質「穿孔」卡或其它適當的信號承載介質，包括傳輸介質，如數字和模擬通信鏈路和無線鏈路。在本發明的一個說明性實施例中，該機器可讀的指令可以包括軟體目標代碼，該目標代碼是從諸如C等語言編譯而成的。儘管本發明是按照幾個優選實施例進行說明的，但本領域的技術人員能夠認識到，實施本發明時，可以在附後的權利要求書的精神和範圍內進行修改。例如，如上所述，本發明不僅局限於共享多處理器系統(SMP)，也可以有利地用於分布式多處理器系統。此外，應當注意的是，申請人的意圖是涵蓋所有權利要求元素的等同物，即使在以後的獲得權力的過程中有修改。權利要求1.一種多重處理系統中透明動態優化的方法，包括使用運行於該系統的另一個處理器上的執行監視器，監視在一個第一處理器上的應用二進位程序的執行。使用在該系統的所述另一個處理器上執行的運行時優化器，透明地優化原始的應用二進位程序的一個或多個段。2.如權利要求1所述的方法，進一步包括在該系統的所述第一處理器上執行該應用二進位程序的一個被插截的複本。3.如權利要求1所述的方法，其中所述監視是參照執行特徵進行的，該執行特徵是通過執行在該應用二進位程序的被插截的複本中包含的被插截的代碼而產生的。4.如權利要求1所述的方法，其中所述優化是參照由該執行監視器收集的執行特徵而進行的，並且不影響並行執行的應用二進位程序的性能。5.如權利要求1所述的方法，進一步包括通過用新近優化的段代替一個或多個段，同時地修改原始執行應用二進位程序。6.如權利要求5所述的方法，其中所述修改是以對該應用二進位程序的用戶透明的方式進行的。7.如權利要求1所述的方法，進一步包括在插入執行的應用二進位程序之前，從已優化的部分中刪除插截代碼。8.如權利要求1所述的方法，進一步包括，通過插截，確定已經被頻繁執行的一個或多個段。9.如權利要求1所述的方法，進一步包括向一個被優化的部分插入新的插截，來繼續監視該新近優化的應用二進位程序的執行特徵。10.如權利要求1所述的方法，其中所述優化包括從被頻繁執行的代碼路徑中刪除不必要的分支。11.如權利要求1所述的方法，其中所述優化包括使一個應用二進位程序專門化於充分利用它正運行於其上的一個特定網絡節點的結構能力。12.如權利要求1所述的方法，其中該應用二進位程序包括編譯時收集的並存儲在該二進位程序中以供所述運行時優化器使用的簡表指令和程序數據。13.如權利要求1所述的方法，其中執行的應用二進位程序的至少多個部分沒有被預先插截。14.如權利要求13所述的方法，其中所述至少多個部分包括沒有原始碼的遺留二進位程序和共享的運行時程序庫的至少一個，所述方法進一步包括監視頻繁執行的多個二進位程序；分析所述多個二進位程序，並製作一個複本，其中插入適當的插截代碼；以及在將來調用所述二進位程序時，切換到一個被插截的複本，並繼續其執行。15.如權利要求14所述的方法，其中在沒有被執行時，所述多個二進位程序被分析。16.如權利要求1所述的方法，其中所述系統包括通過分布式共享存儲器進行通信的一簇節點。17.如權利要求1所述的方法，其中所述系統包括一個共享多處理器系統(SMP)。18.如權利要求2所述的方法，其中該被插截的應用二進位程序是在動態轉換一個目標應用的指令流、用於在一個宿主系統上執行的處理過程中產生的。19.一種用於多處理器計算環境對一個應用針對其執行環境進行同時的、動態的優化的方法，包括在該系統中一個第一處理器上執行該應用的一個被插截的複本；使用運行於該系統的另一個處理器上的一個執行監視器，監視該應用的執行，所述監視是參照執行特徵進行的，該執行特徵是通過執行包含在該應用的被插截的複本中的插截代碼產生的；使用該系統的另一個處理器上執行的一個運行時優化器，優化該原始應用的一個或多個段，所述優化是參照由所述執行監視器所收集的執行特徵進行的，並且對該並行執行的應用的性能沒有影響；通過用新近優化的段代替一個或多個段，修改該原始執行應用，所述修改是以對該應用的用戶透明的方式進行的。20.一種用於在多處理器系統中對一個應用針對其執行環境進行同時的、動態優化的方法，包括由運行於一個單獨的處理器或作為單獨的進程運行於多個處理器上的一個執行監視器，監視運行於一個第一處理器上的一個程序或應用的每次執行；由二進位代碼在其執行時，創建所述二進位代碼的執行特徵的簡表數據，所述二進位代碼包含用於監視性能的插截代碼；由所述執行監視器持續地評估該簡表數據；以及當一個給定臨界條件滿足時，調用一個動態優化器來優化頻繁執行的代碼片段；所述被優化的代碼片段被插入執行的指令流，用於隨後其執行。21.如權利要求20所述的方法，其中該多處理器系統中的多餘處理周期被用來觀察該執行的應用的執行特徵，並透明地修改該執行的應用，以改進其性能。22.如權利要求20所述的方法，其中新插入的代碼片段不包含插截。23.如權利要求20所述的方法，其中新插入的代碼片段包含再插截代碼，以檢測該應用的執行特徵中的進一步變化。24.一種共享多重處理(SMP)系統中透明動態優化的方法，包括在一個第一處理器上執行一個應用二進位程序；在該系統的另一個處理器上，監視該執行的行為；以及當該應用二進位程序正在執行時，優化該應用二進位程序的執行。25.如權利要求24所述的方法，其中所述應用二進位程序是被插截的。26.如權利要求24所述的方法，其中該應用二進位程序的至少一些沒有先前被插截。27.一種用於在多重處理系統中進行透明動態優化的系統，包括一個執行監視器，用於監視在一個第一處理器上的一個應用二進位程序的執行，所述執行監視器運行在該系統的另一個處理器上；所述執行監視器包括一個動態優化器，用於與所述監視同時地優化該原始應用二進位程序的一個或多個段，所述優化器在該系統的所述另一個處理器上執行。28.如權利要求27所述的系統，其中所述執行監視器包括一個片段高速緩存，用於動態存儲該被插截的二進位應用的多個再優化的片段。29.如權利要求27所述的系統，其中所述執行監視器參照執行特徵進行該監視，該執行特徵是通過執行包含在該應用二進位程序的一個被插截的複本中的插截代碼而產生的。30.如權利要求27所述的系統，其中所述動態優化器參照執行監視器所收集的執行特徵進行該優化，並且不影響該並行執行的應用二進位程序的性能。31.如權利要求27所述的系統，其中所述執行監視器通過用新近優化的段取代一個或多個段，來同時地修改該原始執行應用二進位程序。32.如權利要求31所述的系統，其中所述修改是以對該應用二進位程序的用戶透明的方式進行的。33.如權利要求27所述的系統，其中所述執行監視器在將一個優化後的部分插入該執行的應用二進位程序之前，從該優化後的部分中刪除插截代碼。34.如權利要求27所述的系統，其中所述執行監視器向一個優化後的部分中插入新的插截，從而繼續監視該新近優化的應用二進位程序的執行特徵。35.如權利要求27所述的系統，其中該動態優化器從一個被頻繁執行的代碼路徑中刪除不必要的分支。36.如權利要求27所述的系統，其中該動態優化器使一個應用二進位程序專門化於利用它正在其上運行的一個特定網絡節點的全部結構能力。37.如權利要求27所述的系統，其中該應用二進位包含在編譯時收集、並存儲在該二進位程序中以便所述動態優化器使用的簡表指令和一些程序數據。38.如權利要求27所述的系統，其中該執行的應用二進位程序的至少多個部分沒有先前被插截。39.如權利要求38所述的系統，其中所述至少一些部分包括沒有原始碼的遺留二進位程序和共享的運行時程序庫的至少一個，所述系統進一步包括用於監視頻繁執行的多個二進位程序的裝置；用於分析所述多個二進位程序、並製作一個複本，在其中插入適當的插截代碼的裝置；以及當將來調用所述二進位程序時，用於切換到一個被插截的複本，並繼續其執行的裝置。40.如權利要求39所述的系統，其中所述多個二進位程序是在沒有執行時被分析的。41.如權利要求27所述的系統，進一步包括通過分布式共享存儲器進行通信的一簇節點。42.如權利要求27所述的系統，其中所述系統包括一個共享多處理器系統(SMP)。43.如權利要求28所述的系統，其中在動態轉換一個目標應用的指令流、用於在一個宿主系統上執行的處理過程中，產生一個被插截的應用二進位程序。44.如權利要求27所述的系統，其中所述執行監視器專用於所述第一處理器。45.如權利要求28所述的系統，其中所述執行監視器進一步包括片段管理器，用於管理所述片段高速緩存中的多個片段；以及簡表監視器，它由該執行的應用二進位程序當預定條件滿足時觸發，來為該片段管理器提供一個輸入；其中，該動態優化器將優化後的片段通過該片段管理器傳回片段高速緩存；其中，該執行監視器決定提取該應用二進位程序的哪個部分進行優化，並通過製作那些指令的一個複本提取該應用二進位程序的所述部分，並存儲該指令，以便該動態優化器可以引用並修改該複本，其中，所述執行監視器向該動態優化器提供與優化一個特定片段有關的簡表信息。46.一種有形地體現了由機器可讀的指令的程序的信號承載介質，該程序由數字處理裝置執行來實現一種在多重處理系統中透明動態優化的方法，包括使用運行於該系統的另一個處理器上的一個執行監視器，監視在一個第一處理器上的一個應用二進位程序的執行；以及使用在該系統的所述另一個處理器上執行的運行時優化器，透明地優化該原始應用二進位程序的一個或多個段。47.一種用於具有多個宿主處理器的多處理器系統的仿真系統，包括執行監視器，用於當動態地轉換一個目標應用的一個指令流、用於在一個宿主系統上執行時，產生被插截的二進位程序；其中所述執行監視器線程包括多個轉換線程中的一個；以及其中該多個轉換線程的至少一個被用於動態優化由該執行監視器選擇的多個代碼片段。48.如權利要求47所述的仿真系統，其中所述多個轉換線程的一個包括一個優化器線程；其中，頻繁執行的多個代碼序列被動態地優化，以提高性能；其中，所述多個序列是由被解釋器轉換線程插入的、監視被緩存的代碼的執行頻率的插截代碼識別的；以及其中多個監視器線程不斷地跟蹤所述頻率，從而當其達到一個預定的閾值時，通知該優化器線程，一個給定代碼序列是優化的候選，並向該優化器線程提供引入該將被優化的代碼序列的一個賓客指令的一個被仿真的真實地址。49.一個用於多處理器系統的仿真系統，包括多個線程，其中該多個轉換線程的一個包括一個執行監視器，並且其中所述多個轉換線程的至少一個包括一個動態優化器。全文摘要一種在多重處理環境中透明動態優化的方法(和系統)，包括使用運行於該系統的另一個處理器上的執行監視器，監視在一個第一處理器上的一個應用的執行；以及使用在該系統的該另一個處理器上執行的運行時優化器，透明地優化該原始應用的一個或多個段。文檔編號G06F9/45GK1490718SQ0315716公開日2004年4月21日申請日期2003年9月16日優先權日2002年9月17日發明者R·奈爾,J·K·奧布賴恩,K·M·奧布賴恩,P·H·奧登,D·A·普萊納,R奈爾,奧布賴恩,奧登,普萊納申請人:國際商業機器公司