TWI512669B - 用於可規劃揀選單元之編譯技術 - Google Patents

Description

用於可規劃揀選單元之編譯技術 發明領域

本發明係有關數位表示圖形，更特別係有關產生數位表示圖形之效能的改善。

發明背景

在1980和1990年代中，用於電腦和遊戲操縱台的顯示器配接器以具有圖形加速器的型態問世，而減輕中央處理單元(CPU)的負載。一開始，顯示器配接器係提供2D圖形的加速，但其最後亦包括對經加速3D圖形的支援。現代的顯示器配接器係使用常被稱為圖形處理單元(GPU)的一個處理單元。

由於3D圖形的複雜性，所以CPU使用其大量的處理能力來執行和3D圖形有關的計算。永遠都有新的應用程式和遊戲需要更高的圖框速率(每秒所呈現的螢幕影像)、更高的解析度和更高的影像品質，導致各個螢幕影像應該要以盡可能快的時間來呈現的這樣的需求。易言之，增進效能永遠都是很重要的。

可藉由藉著致能更高的時鐘速度、管線化、或利用平行運算來增進CPU的處理能力，而增進效能。然而，這常會產生更多熱能，而導致在對CPU降溫上的更多的電力消耗及更大的風扇噪音。此外，在各個CPU的時鐘速度上也有限制。

發明概要

依據本發明之一實施例，係特地提出一種方法，其包含下列步驟：在運行時間之前判定用於一個可規劃揀選單元的一個程式碼是否具有可判斷出的數個界限；以及若是如此，則在編譯時間在該程式碼中針對各個變數而追蹤該等界限。

依據本發明之一實施例，亦特地提出一種儲存有指令的電腦可讀媒體，該等指令由一電腦執行時係用於下列步驟：在編譯時判定用於一個可規劃揀選單元的一個程式碼是否具有可計算的數個界限；以及若是如此，則在編譯時在該程式碼中針對各個變數而追蹤該等界限。

依據本發明之一實施例，尚特地提出一種裝置，其包含：一個可規劃揀選單元：以及耦接至該可規劃揀選單元的一個編譯器，該編譯器係用於：判定用於該可規劃揀選單元的程式碼是否具有可計算的數個界限，以及若是如此，則在編譯時在該程式碼中針對各個變數而追蹤該等界限。

圖式簡單說明

第1圖為繪示在本發明的一個實施例中，不同實體如何在一個顯示器配接器中互動的一個方塊圖。

第2圖為示出在第1圖之顯示器配接器中所使用的不同程式間之關係的一個概略方塊圖。

第3圖繪示一個範例，於此範例中，係可使用區間算術來揀選在第1圖之顯示器配接器中的一個瓦片。

第4a和4b圖示出可在第1圖之顯示器配接器中執行的數個揀選處理程序的流程圖。

第5圖示出體現第1圖之顯示器配接器的一個典型一般用途電腦的一個概觀架構。

第6a圖為一個顯示器畫面，其繪示出第1圖之顯示器配接器中之輸入值的一個例外情況。

第6b圖為繪示第6a圖之情況中之輸入值的一個圖。

第7a和7b圖為可用於第1圖之顯示器配接器中之紋理的例示性透視圖。

第8a～d圖為可用於第1圖之顯示器配接器中之紋理的例示性圖。

第9圖為一個實施例的流程圖。

較佳實施例之詳細說明

參見第1圖，一個顯示器配接器100可包括一個多角形設立方塊102，其負責依由示於第5圖中的所連接的一個中央處理單元(CPU) 570之指示來設立多角形。雖然可使用任何多角形，但一般係使用三角形。針對各個多角形，一個瓦片光柵化器104將要被呈現的此多角形劃分成一或多個瓦片，其中各個瓦片都至少有一部份與此多角形重疊。一般而言，一個瓦片是一群碎片。在一個實施例中，一個瓦片是含有多個碎片的一個二維四角形。這些碎片各對應於一個像素，並含有呈現此像素及測試此像素是否應呈現在螢幕上所需的所有資料。一個瓦片的常用的大小為8乘8個碎片，但任何瓦片大小皆係於本發明之範圍中。

一個階層式深度揀選方塊106執行階層式深度揀選，此為基於深度緩衝的揀選。於此，可執行一個保守測試來證明那個瓦片是否被深度緩衝器中的內容覆蓋。易言之，此測試從觀察者之角度判斷是否有另一個經呈現物件完全覆蓋此瓦片中的多角形。如果是這種情況的話，可揀選整個瓦片，也就是單獨挑出以做例如跳過這樣的較少處理。在一些實施例中，這因此可導致效能增益。此階層式深度揀選可係在一個可規劃揀選單元108的揀選之前或之後執行。此單元可為一個固定的功能，在一個實施例中，這就表示其並不執行可替換程式。

在可規劃揀選單元108中，揀選係依據一個可替換揀選程式118，也稱作可替換揀選模組，來執行。下文中配合第4a圖，對此可替換揀選程式118的細節和效力有更詳細的說明。

在一個碎片光柵化器110中，由可規劃揀選單元108所處理的瓦片被分解成數個碎片，與多角形重疊。這些碎片各對應於一個像素，並含有呈現此像素及測試此像素是否應呈現在螢幕上所需的資料。碎片資料可包括光柵位置、深度、顏色、紋理座標、模板、alpha(用於混和)等等。就每一個像素而言，可係存在有多個碎片樣本。

在碎片程式單元112中，從碎片光柵化器所輸出的碎片利用一個碎片程式120而被處理。這個單元的目的是要執行任務，例如將先前所算出的顏色與紋理組合，以及加上例如起霧的效果，以及在可能的時候界定並不需要被呈現的碎片，也就是碎片揀選。

一個紋理單元114係用於紋理查詢，例如使用一維、二維、三維、四維及立方圖紋理，並將這些提供給可規劃揀選單元108及碎片程式單元112。

混和/深度/alpha單元116使用從碎片程式單元112所提供的碎片而在這些碎片被寫入目標緩衝器之前執行深度測試、alpha測試及混和。

可使用示於第2圖中的一個經組合程式或編譯器程式222來自動產生一個可替換揀選程式118，以供在可規劃揀選單元108和一個碎片程式120中使用，以供在碎片程式單元112中使用。選擇性地，一個程式設計師可寫出個別的揀選及碎片程式118、120。

舉個例子，考慮一個經組合程式222的一個偽碼片段(1)，最初是寫來用作一個碎片程式：

此程式藉由將光線(I)和法線(n)的點積藉由DP3指令運算成一個結果(d)來執行基本漫射照明。n和I向量依每個碎片而變。在表面法線並不面向光線，這由d小於0指出，時，KIL指令終止所有碎片。TEX2D指令執行一個二維紋理至c的查詢。最後，結果(d)乘上一個漫射材料係數(c)。

KIL指令是揀選整個瓦片的碎片的一個機會。但是為了這麼作，應該要保守地證明KIL指令的條件對這整個瓦片而言是被滿足的。在這個範例中，也必須要有可能保守地評估DP3指令，因為KIL指令係取決於那個指令的結果。此外，必須要有可能針對一整個瓦片找出輸入(於此實例中，為法線n和光線I)的保守邊界，因為DP3指令又是取決於這些值。

為了實施這個保守評估鍊，可規劃揀選單元係以和碎片程式單元相同的指令組為基礎。然而，取代於典型上在處理碎片時係用浮點變數作為一個指令的來源和目的暫存器，於此係使用區間，且係使用區間算術的原理來實施指令。舉個簡單的例子，考慮一個標準的ADD指令：

就對應的可規劃揀選單元區間指令而言，運算元被區間取代，其中，一個區間，例如，係定義為：

則可規劃揀選單元ADD指令為：

其中區間加法操作係如此實施：

可以看出，這個區間加法的結果含有所有可能「正常」加法的結果，或更正式地說，其在a且b的情況下保有。這因此是保守上的正確。以類似方式，在碎片程式指令組中的每一個指令的行為都被重新定義。

除了使用區間指令以外，可亦將輸入定義為區間。因此，必須要可能針對在整個瓦片之碎片上所內插的量來計算保守邊界。當知，雖然於此係使用區間算術，但亦可使用任何適合的代表整個瓦片的算術。例如，仿射算術或泰勒(Taylor)算術可同樣合用於本發明之範圍內。就上文中之推論，可自動地從經組合程式(1)導出可替換揀選程式118。所導出之揀選程式為：

此外，在這裡，碎片程式120係從經組合程式(1)所導出的，和經組合程式220完全相同。此碎片程式為：

對於一整個瓦片的碎片，假設判斷出其法線330的區間334為，且其光線向量332的區間336為，如於第3圖中所繪示的。z座標係假設為零，以簡化此範例。這些區間表示型態之點積的結果是。因此，可斷定可最多為=-1/。因為這個值絕對小於零，所以於上文中參考第2圖所說明的揀選程式中，可揀選這整個瓦片，而無須針對每一個碎片執行碎片程式，如將於下文中參考第4a圖而以更進一步細節說明的。在本發明的一些實施例中，這是效能增益的一個來源。

第4a圖示出可在第1圖中之顯示器配接器100內執行的一個揀選處理程序的流程圖。在此處理程序開始的時候，已經選出要被呈現的一個多角形。在一個選擇一個瓦片作處理步驟440中，一個瓦片被選擇，所選擇的瓦片至少有一部份和此多角形重複。接著在執行揀選程式步驟452中，揀選程式被執行。

於此實施例中，當揀選程式請求輸入值的時候，此處理程序繼續來到提供輸入值給揀選程式步驟454a。這些輸入值為和以某種方式代表此瓦片中之所有碎片的一個特徵有關的值。例如，輸入值可為法線、位置座標、光線向量、顏色、紋理座標等等。於此實施例中，所請求的輸入值係利用區間算術來計算。易言之，這些輸入值僅在他們被需要的時候才依據一個『拉動』機制而被計算，相對於參考第4b圖所說明的『推動』機制。此揀選程式的結果為目前所處理的瓦片是否應被揀選。這可被嚴格地判定，而使在此瓦片的區域中，此瓦片僅在目前的多角形對最末所呈現的影像沒有任何貢獻時被揀選。或者是可執行損耗性揀選，而使在此瓦片的區域中，此瓦片在目前的多角形對於最終所呈現之影像的貢獻落於某個臨界值之下時被揀選。

當揀選程式已結束處理時，此處理程序繼續來到一個條件性揀選條件為真步驟456。於此步驟中，係依據揀選程式之輸出而判斷是否應針對目前所處理的瓦片來執行揀選。若要執行揀選，則處理程序繼續來到一個執行指令組A步驟458。否則的話，處理程序便繼續來到一個執行指令組B步驟460。在一個實施例中，若揀選條件為假，則此瓦片被分解成數個較小的瓦片，並且處理程序回到選擇瓦片作處理步驟440。此可針對越來越小的瓦片而連續地重複，實施一個階層性的、多級的揀選處理程序。

揀選程式可亦輸出除了揀選條件以外的結果。這些結果可在用於更進一步之處理的圖形管線下被傳送。這樣的一個實施例的一個例子包含將階層式深度揀選單元106(第1圖)和可規劃揀選單元108(第1圖)的順序反轉。可規劃揀選單元運算一個瓦片中之深度值的一個邊界或區間，並且此區間被傳送至階層式深度揀選單元。此階層式深度揀選單元接著基於由一個程式所運算出的深度值而執行揀選。

在執行指令組A步驟458中，係針對此瓦片的一個子集，其典型上是數個碎片，而執行一個指令組A。這些碎片典型上集體覆蓋此瓦片的所有像素，其與所處理的三角形重疊。

在執行指令組B步驟460中，係針對此瓦片的一個子集，其典型上是數個碎片，而執行一個指令組B。這典型上係在瓦片階段之後的對於碎片呈現的一個傳統處理。

指令組A典型上係比指令組B較不嚴苛，導致在揀選條件被判定為真時針對瓦片所處理之指令的數量的減少，而導致效能增進。在一個實施例中，指令組A是空的，致使在處理上的可觀縮減，也就是效能增進。此流程繼續跌代，直到於步驟462再也沒有更多的瓦片。

第4b圖示出本質上等同於參考第4a圖所述之處理程序的一個處理程序。選擇一個瓦片作處理步驟440、執行揀選程式步驟452、條件性揀選條件為真步驟456、執行指令組A步驟458、執行指令組B步驟460及條件性更多瓦片步驟462皆等同於第4a圖中的對應步驟。

然而，於此，提供輸入值給揀選程式步驟454b係在執行揀選程式之前被處理。於此步驟中，所有有關的輸入值都被計算，於此實施例中係使用區間算術，並被提供，以使揀選程式能夠取得這些值。這是對輸入值計算實施一個『拉動』機制。

第5圖示出一個體現第1圖之顯示器配接器100的一個典型一般用途電腦583的一個概觀架構。此電腦具有能夠執行軟體程式的一個控制器570，例如一個CPU。控制器570連接至一個依電性記憶體571，例如一個動態隨機存取記憶體(RAM)以及一個顯示器配接器500，在一些實施例中，其可為與第1圖中之顯示器配接器100相同者。顯示器配接器500轉而連接至一個顯示器576，例如一個監視器。控制器570亦連接至恆久儲存體573，例如一個硬碟或快閃記憶體以及光學儲存體574，例如光學媒體，例如CD、DVD、HD-DVD或藍光，的讀取器及/或寫入器。一個網路介面581亦連接至控制器570，以提供對一個網路582，例如一個區域網路、一個廣域網路(例如網際網路)、一個無線區域網路或無線都會區域網路，的取用。透過一個週邊介面577，CPU570可與一個滑鼠578、一個鍵盤579或任何其他週邊設備580，包括一個搖桿、一個印表機、一個掃描器等等，通訊。

當知，雖然上文中係以一個一般用途電腦作說明來體現本發明，但本發明亦可同等優適地體現於利用數位圖形，特別是3D圖形，的任何環境中，例如遊戲操縱台、行動電話、行動網際網路裝置(MID)、MP3播放器等等。任何電腦架構皆可被使用。

在一個如上文中所述的指令組的實作中，可係使用區間算術來計算輸入值。可接著針對一整個瓦片的碎片而執行一個揀選程式。然而，為了這麼作，也需要運算針對變動(或內插的)輸入的有界限區間。

一開始，變動屬性的值係在瓦片的所有的四個角落使用內插法來運算。接著，運算這四個值的有界限區間，其被稱為。在三角形頂點之變動屬性的有界限區間也被運算，並稱為。在整個瓦片上的變動屬性之最終有界限區間可被運算為。也有其他方法可運算這些區間，例如，藉由考量重疊一個瓦片的所有碎片。

最後，可處理一個例外情況，其繪示於第6a圖中。於此，係以一個棋盤紋理686的形式來繪示在一個三角形685上的透視校正內插法。可以看出，此紋理沿著一條投影線687鏡射，其為當三角形685無限大時，其水平面所突現之處的線。此鏡射效果為由在透視校正內插法中所用之劃分所致的一種後投影的形式。現在，假設想要在與投影線重疊的一個瓦片688上運算一些變動屬性的有界限區間。

第6b圖示出透視校正內插法函數690，以及當瓦片688的四個角落被內插時所需的值691a～d。這些角落的有界限區間692很明確地被校正，因為當此函數趨近在投影線的無限時，這並不含有函數690在此區間中的所有的值。

這個例外情況可藉由在瓦片的有界限區間與投影線重疊時，將設定為來處理。於此實施例中，只有實際上重疊此三角形的瓦片被遍歷，並且係使用透視型校正重心座標來做這項內插。

當針對一個瓦片的數個角落而運算透視型校正重心座標時，可簡便地刪除這些有問題的瓦片。透視型校正重心座標係以一個比例函數來表示，並且若就這些瓦片角落中之任何一者而言分母小於零，則此瓦片越過投影線。

N維的紋理查詢係如下執行。一般想法係要提供運算在一個給定區域上的紋理資料之有界限區間的一個快速且有效的構件。此範例的剩餘部份將只考量二維紋理，但推廣是很簡單的。

我們一開始先對屬於區間式紋理查詢的各個紋理運算兩個MIP映射(mipmap)金字塔。如於第7a和7b圖中所示，各個基元，例如在一個MIP映射中的基元793被運算為在此金字塔中直接在它下面的這四個對應紋理元素，例如基元794a～d，中的在成份上的最小值，如於第7a圖中所示的，或最大值，如於第7b圖中所示的。最終的結果可被視為有界限區間的一個MIP映射金字塔。這種類型的預先運算可輕易地由驅動器處理，類似於標準MIP映射如何被自動產生那樣。

當執行一個紋理查詢時，我們希望運算在一個座標軸平行邊界盒(axis-aligned bounding box)上之紋理資料的有界限區間，其為為紋理座標區間。首先，我們運算一個適當的MIP映射等級為：

其中是未經標準化整數紋理座標的一個二維區間(即，其包括紋理之維度)。他們被適當地取為整數，使得針對i{x,y}， t _i 係取小於它的最大整數而係取大於它的最小整數。

當轉換至此MIP映射等級時，t在任何維度中將永遠不會多於一個紋理元素寬，且在最寬的維度中會是至少1/2個紋理元素寬。因此，我們得到紋理維度區間的四個可能的情況，如於第8a～d圖中所繪示的。我們總是從紋理元素796中取樣2×2個紋理元素的一個方格，在用於標準線性內插法的取用方案中，其具有在( t _x , t _y )的紋理元素的左下角。此紋理查詢的結果接著被運算為實際上與紋理座標區間重疊的此等紋理之顏色的界限。也就是說，我們屏棄由參考號碼795第8a～c圖所指出的遮蔽的紋理元素。因為這個經MIP映射轉換的t會被取整數成為最接近的整數座標，所以可藉由只對最末位元作比較來非常有效率地實施此重疊測試。此紋理查詢處理程序本質上和一個正常的經「三線性」過濾紋理查詢一樣高成本。最大的差異係對於從在兩個不同MIP映射金字塔中之相同等級，而非兩個相鄰等級，中取樣的需求，以及我們係將最終結果運算為界限，而非使用線性內插法。此策略自然地支援不同類型的包裝模式，例如夾鉗、重複及鏡射重複。可在MIP映射等級運算之後簡便地將適當的包裝模式應用至此等區間座標，以得到預期結果。

在一個實施例中，只有實際上用於揀選程式的MIP映射等級可被創造。這樣的最佳化對於發生在螢幕空間，例如，比如說，無關順序透明度(order independent transparency)，的演算法而言特別重要。在這種情況中，我們事先知道我們只需要基礎等級的紋理，以及對應於螢幕上的一個瓦片的MIP映射等級。最小及最大深度值可例如在階層式深度揀選單元中被找到。也有可能(但可能性較低)是，最小和最大顏色已經為了壓縮目的而被運算，否則的話，我們便需要對其做運算。

最小/最大MIP映射金字塔係使用和二維紋理相同的途徑，針對立方圖而運算。針對邊緣來講，MIP顏色被運算為在邊緣兩側的四個紋理元素之最小或最大者，而針對角落來講，MIP顏色被耦合成在從那個角落所發出的所有的三側上的四個紋理元素之最小或最大者。在邊緣之相對側上的紋理元素會因此在較高MIP映射等級中共享相同的顏色。同樣地，於一個角落的三個紋理元素也會共享一個共同顏色。

可使用此MIP映射金字塔，以對立方體之僅一側之取用來作保守立方圖查詢。首先，運算主軸的以區間為基礎的等量。給定一個紋理座標區間，定義主軸i為 t _i 和具有相同正負號，並且min(| t _i |,||)最大化的那個軸。若 t _i 和在所有軸上都具有相異的正負號，那麼就找不出主軸。然而，這只有在當原點落於紋理座標區間內時才會發生。在這種情況中，紋理座標區間會投影到整個立方圖上。這可藉由選擇最高MIP映射等級，並取樣一個任意立方圖面來處理。

一旦找到一個主軸，則可將紋理座標區間投影到立方圖的對應側。此項投影係藉由分別投影剩下兩個軸的各個界限來完成。讓我們來考慮一個範例，於此範例中，x為主軸，而y為我們想要投影界限的那個軸。因此，紋理座標區間有六個可能的情況(請注意，沒有任何的區間可越過y軸，因為這樣的話x軸就不會是主軸)，以及我們必須要投影以運算界限的極值點。查看紋理座標區間的正負號，及透過查表而得到這些極值點便足夠。

這些極值點針對剩下的兩個軸而被投影，以形成一個二維的經投影座標區間。此區間被用來運算一個MIP映射等級及執行一個二維紋理查詢，和上文中針對二維情況所說明的方法一模一樣。

為了改善效能，減少在揀選著色器中所做的工作量並增加所運算之界限的緊密度是很可嚮往的。一般而言，係使用關於區間指令的元資料來產生經最佳化純量指令。這些元資料可為區間界限或甚至是關於所需者係界限哪側的資訊，或是關於要執行什麼操作的較高等級的資訊。例如，關於一個方格是否要被完成，而非乘法，的資訊可為可被用來產生經最佳化純量指令的元資料之類型的一個範例。接著，這些界限可在編譯時間在程式碼中被追蹤，以針對各個變數及針對各個指令來運算界限。這些界限使得讓程式碼更有效率成為可能的事。

因此，可替換揀選程式118被含納並屬於在第9圖中之方塊910的靜態輸入界限分析。在一個實施例中，這些界限可係以數個應用程式規劃介面標準為基礎。

此等標準的一個範例包括對於某些類型之輸入的期望值。這些界限可亦係以常數、變數類型、及資料類型為基礎。例如，變數類型可係為正數的一個無正負號的整數。一個資料類型可為一個值，其必須係在零和一之間的範圍內。這些界限被認為是正確的。假如此等界限並不存在，則界限可為正和負無限。

這些界限可用作用以在編譯時以區間方式來評估揀選程式的輸入，以判斷各個變數的可能界限。可應用習知的數學結果來限縮編譯時間界限。數個範例包括這些事實，即，絕對值永遠都是正的，正弦和餘弦係在介於-1和1的範圍內，夾鉗操作限制可能值的範圍。因此，程式碼可在編譯時間在區間範圍內被執行。此結果為針對在揀選程式中之各個指令之有效值的一個範圍。

所收集的區間可接著在一個低等級被使用，以產生更有效的區間算術評估碼，其在一些實施例中可改善運行時間效能。例如，已知在一個區間乘法中的兩個運算元係非負的可減少運行時間區間評估之成本，從十個指令減少到只有兩個指令。因此，此編譯時間分析可減少揀選程式的長度，並改善效能。靜態輸入界限分析提供一個區間中間表示型態，還有輸入界限。

即使無法判斷出非無限界限，且使用正和負無限的預設界限，在追蹤「無限」界限上可仍有益處。在實務上，一個揀選程式具有一或多個輸出。對於這些輸出中的所有或一些而言，在一些情況中，可係判斷較嚴格的界限。例如，考慮y=sin(x)，其中x為對此揀選程式的一個輸出。若沒有使用任何除了介於正和負無限之間的x界限，則在程式碼中追蹤此界限可仍是很有用的。例如，sin(x)的輸出永遠都會受限於[-1,1]這樣的範圍。此範圍可接著被追蹤，以簡化此程式中的其他操作。

在一些實施例中，可使用在方塊912中的動態輸入界限假設。他們牽涉到對於基於特定領域知識(domain specific knowledge)之假設的使用，以增進效能。例如，一個特定領域知識可包括這樣的事實，即，一個紋理通常是在零到一的範圍之內。可使動態假設進一步地改進靜態界限。

舉個例子，在編譯時間，一個紋理讀取的結果一般而言可能會是完全未知的。然而，做出此值會是在零和一的範圍之內這樣的假設是很合理的，因為大部分的紋理係以無正負號的經標準化值而儲存。在一些實施例中，著色器編譯器可基於輸入格式而自動做出那樣的合理假設，並使用此資訊來產生較快速的揀選程式。只要輸入實際上落於所假設的範圍內，這個較快的程式碼路徑就會是有效的。

然而，若，例如，一個浮點表面係受限於著色器，則此零到一的範圍假設可能會被違反。於運行時，著色器執行機制會知道此錯誤假設，並可請求一個經校正揀選著色器。若有需要，這可藉由在可獲得經校正版本之前跳過針對那個特定著色器的揀選而同步完成。可在數個步驟內完成降格(degradation)。在紋理的情況中，大部分的影像都只含有非負的值，即便其表示型態，例如浮點數，可表示負數亦然。違反這個零到一的範圍可係指此資料至少係由零和無限來限制，這仍然給予在整個未知資料上的效能增進。

在一些實施例中，來自於動態輸入界限假設的輸出再次藉由此動態輸入界限假設而成為區間中間表示型態加上輸入界限作為補充。

在方塊914中，此等界限係在編譯時在程式碼中被追蹤，以運算各個變數的界限。這些界限使得產生更有效率的程式碼成為可能。此程式碼係在編譯時間被執行，並且各個指令被分析，以判斷其可能輸入和輸出的範圍。此處理程序係從靜態動態輸入界限的開端開始，並向前推進。

方塊914之輸出為區間中間表示型態及各個指令的界限。在一些實施例中，於方塊916中，可針對單側界限而完成最佳化。在一些情況中，只需要一個結果的上限或下限。可對指令加上標籤，來以單側產生輸出。此單側標籤可將資訊向後推進到可能的程度。

方塊916之輸出為區間中間表示型態、界限、及邊側資訊，下、上中之一者或下上二者。

接著，在方塊918中，此區間中間表示型態被轉化成經最佳化純量中間表示型態。此界限資訊及邊側資訊可被用來以一個經最佳化序列的純量指令而取代各個區間指令。因此，取代於率直地以一個一般序列的純量指令取代各個內部指令，係可使用界限來侷限由這些純量指令所支援的程度。例如，若已知一個區間乘法的輸入範圍絕對是非負的，則可藉由已被最佳化成只在非負數字上作業的一個較短序列的純量指令來取代此指令。

最後，在方塊920中，此純量中間表示型態被用於標準編譯器最佳化，例如死亡碼消除、向量化、及程式碼產生。此可執行碼在方塊920之後被輸出，此流程從編譯時間轉變成運行時間。

於運行時間，可對動態假設重新評價，如於方塊926所指出的。若此等假設有效，如於928中所判斷的，則可運行揀選程式，如於方塊930中所指出的。

否則，可考慮多種替代形式。例如，可決定不做任何揀選。或者是，可以更多的一般假設來請求一個新的揀選程式。再舉另一種替代形式，可運行具有更多一般假設的一個預先編譯揀選程式，全如方塊932中所指出的。若存在有數個預先編譯程式，則可選擇具有最多滿足目前假設的限制性輸入假設的那一個。

在一些實施例中，可係使用其他有界限算術，例如仿射算術或泰勒算術。在這些情況中，可由適於所選算術的較高維度之表示型態來取代輸入/輸出界限。

在一些實施例中，於第9圖中所描繪的序列可係在軟體中實施。在這樣的情況中，此序列可係體現於儲存在一個電腦可讀媒體上的指令。那個媒體可為，例如，一個半導體、光學、或磁性儲存體。這些指令可由包括有一個控制器或處理器的一個電腦執行。例如，此控制器與處理器可為第5圖中的CPU 570或顯示器配接器500的一部分。儲存指令的儲存體可為，例如，記憶體571或儲存體573或574。

於本文中所述的圖形處理技術可實施在多種硬體架構中。例如，可將圖形機能整合在一個晶片組內。或者是，可使用一個分立圖形處理器。再舉另一個實施例，可由一個一般用途處理器，包括一個多核心處理器，來實施圖形功能。本說明書通篇中對「一個實施例」或「一實施例」之參照係指關聯於此實施例而說明的一個特定的特徵、結構或特性係包括在本發明所涵蓋的至少一個實作中。因此，「一個實施例」或「在一實施例中」等語的出現並不必然係指相同實施例。此外，特定特徵、結構或特性可係以所例示之特定實施例以外的其他適合的形式來實行，且所有此等形式皆可被涵納在本案所請求之申請專利範圍內。

雖然已針對有限數量的實施例來說明本發明，但熟於此技者會可識出由中而生的多種修改體與變異體。後附申請專利範圍意欲將所有此等修改體與變異體作為落於本發明之真實精神與範疇內者而涵蓋在內。

100、500．．．顯示器配接器

102．．．多角形設置方塊

104．．．瓦片光柵化器

106．．．階層式深度揀選方塊/階層式深度揀選單元

108．．．可規劃揀選單元

110．．．碎片光柵化器

112．．．碎片程式單元

114．．．紋理單元

116．．．混和/深度/alpha單元

118．．．可替換揀選程式

120．．．碎片程式

222．．．經組合程式或編譯器程式

330．．．法線

332．．．光線向量

334、336．．．區間

440．．．選擇一個瓦片作處理步驟

452．．．執行揀選程式步驟

454a．．．揀選程式步驟

454b．．．提供輸入值給揀選程式步驟

456．．．條件性揀選條件為真步驟

458．．．執行指令組A步驟

460．．．執行指令組B步驟

462．．．條件性更多瓦片步驟

570．．．中央處理單元(CPU)/控制器

571．．．記憶體

573、574．．．儲存體

576．．．顯示器

577．．．週邊介面

578．．．滑鼠

579．．．鍵盤

580．．．週邊設備

581．．．網路介面

582．．．網路

685．．．三角形

686．．．棋盤紋理

687．．．投影線

688．．．瓦片

690．．．函數

691a～691d．．．值

793、794a～794d．．．基元

795～796．．．紋理元素

910～932．．．方塊

第1圖為繪示在本發明的一個實施例中，不同實體如何在一個顯示器配接器中互動的一個方塊圖。

第2圖為示出在第1圖之顯示器配接器中所使用的不同程式間之關係的一個概略方塊圖。

第3圖繪示一個範例，於此範例中，係可使用區間算術來揀選在第1圖之顯示器配接器中的一個瓦片。

第4a和4b圖示出可在第1圖之顯示器配接器中執行的數個揀選處理程序的流程圖。

第5圖示出體現第1圖之顯示器配接器的一個典型一般用途電腦的一個概觀架構。

第6a圖為一個顯示器畫面，其繪示出第1圖之顯示器配接器中之輸入值的一個例外情況。

第6b圖為繪示第6a圖之情況中之輸入值的一個圖。

第7a和7b圖為可用於第1圖之顯示器配接器中之紋理的例示性透視圖。

第8a～d圖為可用於第1圖之顯示器配接器中之紋理的例示性圖。

第9圖為一個實施例的流程圖。

100．．．顯示器配接器

102．．．多角形設置方塊

104．．．瓦片光柵化器

106．．．階層式深度揀選方塊/階層式深度揀選單元

108．．．可規劃揀選單元

110．．．碎片光柵化器

112．．．碎片程式單元

114．．．紋理單元

116．．．混和/深度/alpha單元

118．．．可替換揀選程式

120．．．碎片程式

Claims (26)

1. 一種方法，其包含下列步驟：在運行時間之前判定用於一個可規劃揀選單元的一個程式碼是否具有至少一個揀選輸入變數具有可被判斷出的數個非無限大之界限；若是如此，則針對各個變數而其界限係可被判斷出的，在編譯時間經由該程式碼追蹤該等界限；其中該等界限若在編譯時間無法被判斷出，則做出該等界限在編譯時間之一個假設，以及其中追蹤該等界限包括使用有界限之算術來評估指令。
2. 如申請專利範圍第1項之方法，其包括下列步驟：使用關於區間指令的資訊來產生純量指令，該區間指令具有由區間所定範圍之運算元。
3. 如申請專利範圍第2項之方法，其中使用資訊之步驟包括：使用數個經追蹤區間界限。
4. 如申請專利範圍第1項之方法，其包括下列步驟：在運行時間重新評價該假設。
5. 如申請專利範圍第4項之方法，其中若該假設被判定為有效，則運行該程式碼。
6. 如申請專利範圍第4項之方法，其包括下列步驟：若該假設被判定為不為有效，則做一個新假設並以該新假設編譯該程式碼。
7. 如申請專利範圍第6項之方法，其中若該新假設並不生 效，則以不使用界限的方式編譯該程式碼。
8. 如申請專利範圍第1項之方法，其包括下列步驟：將一或多個界限簡化成單側界限。
9. 如申請專利範圍第1項之方法，其中使用有界限算術來評估指令之步驟包括使用下列項目中之一者：區間算術、仿射算術、或泰勒(Taylor)算術。
10. 一種儲存有指令的非暫時性電腦可讀媒體，該等指令由一電腦執行時係用以進行下列步驟：在編譯時判定用於一個可規劃揀選單元的程式碼是否具有至少一個揀選輸入變數具有可被計算的數個非無限大之界限；若是如此，則針對各個變數而其界限係可被判斷出的，在編譯時經由該程式碼追蹤該等界限，該等界限若在編譯時間無法被計算出，則做出該等界限在編譯時間之一個假設，以及追蹤該等界限包括使用有界限之算術來評估指令。
11. 如申請專利範圍第10項之媒體，其更儲存有下列指令：用以使用關於區間指令的資訊來產生純量指令的指令，該區間指令具有由區間所定範圍之運算元。
12. 如申請專利範圍第11項之媒體，其更儲存有下列指令：用以將數個經追蹤區間界限用作該等資訊的指令。
13. 如申請專利範圍第10項之媒體，其更儲存有下列指令：用以在運行時間重新評價該假設的指令。
14. 如申請專利範圍第13項之媒體，其更儲存有下列指令： 用以在該假設被判定為有效時運行該程式碼的指令。
15. 如申請專利範圍第13項之媒體，其更儲存有下列指令：用以在該假設被判定為不為有效時做一個新假設並以該新假設編譯該程式碼的指令。
16. 如申請專利範圍第15項之媒體，其更儲存有下列指令：用以在該新假設不為有效時以不使用界限的方式編譯該程式碼的指令。
17. 如申請專利範圍第10項之媒體，其更儲存有下列指令：用以將一或多個雙側區間界限簡化成單側區間界限的指令。
18. 一種裝置，其包含：一個可規劃揀選單元：以及耦接至該可規劃揀選單元的一個編譯器，該編譯器係用於：判定用於該可規劃揀選單元的程式碼是否具有至少一個揀選輸入變數具有可被計算的數個非無限大之界限，若是如此，則針對各個變數而其界限係可被判斷出的，在編譯時經由該程式碼追蹤該等界限，該等界限若無法被計算出，則做出該等界限在編譯時間之一個假設，以及追蹤該等界限包括使用有界限之算術來評估指令。
19. 如申請專利範圍第18項之裝置，其中該裝置為一個顯示 器配接器。
20. 如申請專利範圍第18項之裝置，其包括一個控制器。
21. 如申請專利範圍第20項之裝置，其中該控制器係用於：在運行時間重新評價該假設。
22. 如申請專利範圍第21項之裝置，其中該控制器係用於：在該假設被判定為有效時運行該程式碼。
23. 如申請專利範圍第21項之裝置，其中該編譯器係用於：在該假設被判定為不為有效時做一個新假設並以該新假設編譯一個程式碼。
24. 如申請專利範圍第23項之裝置，其中該編譯器係用於：在該新假設不為有效時以不使用界限的方式編譯該程式碼。
25. 如申請專利範圍第18項之裝置，其中該編譯器係用於：使用關於區間指令的資訊來產生純量指令，該區間指令具有由區間所定範圍之運算元。
26. 如申請專利範圍第25項之裝置，其中該編譯器係用於：使用區間界限來產生純量指令。