用於壓縮程序指令的壓縮條目最優選擇的製作方法

2023-04-24 10:42:41

專利名稱：用於壓縮程序指令的壓縮條目最優選擇的製作方法
技術領域：
本要求保護的發明的實現總體上涉及數據壓縮，特別涉及在執行程序 之前壓縮在程序(或代碼)中的指令。
背景技術：
許多處理系統執行指令。因此，生成、存儲和/或訪問構成程序的指令 的能力是令人期望的。特別地，為了節省存儲容量和/或帶寬，通常期望減 小程序/代碼的大小。已經提出一些技術，用於壓縮在運行時間存儲在高速
緩存(例如，L2)中的數據。但是，在運行時間的壓縮會使硬體複雜化，並且 帶來額外的延遲，該延遲是由對數據是否需要壓縮來做決策所引起的。
已經提出的另一個技術是ECHO指令，這種方案可通過使用ECHO指 令替代公共的湘似的指令序列，來減小程序/代碼的大小。但是，這個技術 關注於搜索在公共的/相似的指令序列中的指令級信息，因此，該技朮忽略 了在指令內任何有用的信息。
然而，這種用於減小程序/代碼的大小的方案會是計算密集型的，和/ 或會使得對於特定程序不是最優壓縮的。


附圖併入並構成該說明書的一部分，圖示了一個或多個與本發明的原 理一致的實現，並與說明部分一起解釋了這些實現。附圖並非必然是按照 比例繪製的，相反地，其重點在於圖示出本發明的原理。在該附圖中
圖1示出了具有第一和第二處理系統的一個系統的方框圖2示出了圖1的第一處理系統的方框圖3示出了一種用於最優地壓縮程序中的比特模式(pattern)的方法； 圖4示出了一種示例性指令設置以便說明比特模式到變量的映射。
具體實施例方式
參照附圖進行了以下詳細地描述。在不同的附圖中可以使用相同的標 號來標識相同或相似的要素。在以下描述中，為了解釋的目的而不是用於 限定，闡明了多個具體細節，例如，特定的結構、架構、接口和技術等， 以便透徹地理解要求保護的發明的各種方面。但是，對於獲得本公開的利 益的本領域普通技術人員顯而易見的是，可以以脫離這些具體細節的其它 示例，來實施要求保護的發明的各個方面。在某些示例中，省略了對公知 的器件、電路和方法的描述，以免不必要的細節影響本發明的描述。
在一些實現中，第一處理系統可以用來生成由第二處理系統執行的至 少部分地壓縮的指令(或由這種指令構成的程序)。
圖1是根據一些實現的系統100的方框圖。參照圖1，系統100包括第 一處理系統110和第二處理系統120。第一處理系統110和第二處理系統 120可以彼此耦合，例如，經由第一通信鏈路130進行耦合。系統100還可 以包括一個或多個被索引的高速緩存190，用於存儲在指令和/或程序壓縮 期間由第一處理系統IIO生成的比特模式，將在下文詳細地解釋以上內容。
根據一些實現，使用第一處理系統110來生成用於第二處理系統120 的指令。在這點上，在一些實現中，系統100可以接收在140處指明的輸 入或第一數據結構。第一數據結構140可以通過第二通信鏈路150來接收， 並且可以包括但並不限於包含有第一數量的指令的程序，所述第一數量的 指令可以包括採用第一語言的指令，例如，高級語言或彙編語言。在一些 實現中，採用第一語言的這些指令可以是128比特指令，儘管本發明並不 限於此。
向第一處理系統110的輸入提供第一數據結構140，第一處理系統110 可以包括編譯器(compiler)和/或彙編器(assembler),它們可以根據一個 或多個與第二處理系統120相關的需求，來編譯和/或彙編第一數據結構140 的一個或多個部分。第一處理系統110的輸出可以提供在160處指明的第 二數據結構。第二數據結構160可以包括但並不限於包含有第二數量的指 令的程序，所述第二數量的指令可以包括採用第二語言的指令，例如，機 器或二進位語言。在一些實現中，第二語言可以與第一語言相同，除了它 可以包含64比特指令之外。在一些實現中，採用第二語言的一些或所有指令可以是64比特指令，儘管採用第二語言的指令也可以包括一些128比特 指令。當然，本發明並不限於任意特定長度的指令，但是採用第二語言的 指令中的至少一些可以比採用第一語言的指令短，或者是從採用第一語言 的指令壓縮得到的。
圖2是第一處理系統110的一個實現的方框圖。參照圖2，在一些實現 中，第一處理系統110包括編譯器和/或彙編器210和壓縮器220，其中在 一些實現中可能不存在編譯器和/或彙編器210。編譯器和/或彙編器210和 壓縮器220可以彼此耦合，例如，經由通信鏈路230進行耦合。儘管為了 便於描述而作為兩個分開的元件來顯示，但是在一些實現中，壓縮器220 可以是編譯器和/或彙編器110的一個功能部分。
在一些實現中，第一處理系統110可以通過通信鏈路150來接收第一 數據結構140。如上所述，第一數據結構140可包括但並不限於第一多個指 令，所述第一多個指令可以包括採用第一語言的指令，例如，高級語言或 彙編語言。
第一數據結構140可以被提供到編譯器和/或彙編器210的輸入。編譯 器和/或彙編器210包括編譯器、彙編器和/或其組合，它們根據與第二處理 系統120相關的一個或多個需求，來編譯和/或彙編第一數據結構140的一 個或多個部分。
編譯器和/或彙編器210可以生成在240處指明的數據結構。該數據結 構240可以包括但並不限於多個指令，所述多個指令可以包括採用第二 語言的指令，例如，二進位語言或機器語言。在一些實現中，第二語言可 以與第一語言相同，除了它可以包含64比特指令之外。在一些實現中，所 述多個指令可以是要由第二處理系統120的執行引擎執行的多個機器碼指 令。在一些實現中，所述多個指令可以包括多於一種類型的指令。
可以向壓縮器220的輸入提供數據結構240，該壓縮器220可以處理在 數據結構240中的每個指令，以便確定該指令是否能由用於第二處理系統 120的壓縮指令來替換。如果能替換該指令，則壓縮器220就可以生成壓縮 指令來替換該指令。在一些實現中，壓縮器220至少部分地基於要替換的 指令，來生成壓縮指令。在一些實現中，壓縮指令包括表明該壓縮指令是 一壓縮指令的欄位。根據一些實現，壓縮器220可以用壓縮指令來替換所述指令。在這點 上，所述多個指令可以代表一個指令序列。可以將指令從其在該序列中的 位置處移除，並將壓縮指令插入在該序列中的該位置處，從而使得壓縮指 令在序列中的位置與由此被替代的指令在從序列中移除該指令之前的位置 相同。
如將在下文詳細地解釋的，壓縮器220可以通過在高速緩存190中存 儲常用的比特模式，來壓縮在數據結構240中的一些指令。壓縮器220可 以通過在第二數據結構160中的指令中使用對於在高速緩存190中的比特 模式的位置的索引來替代比特模式本身，而對指令進行壓縮。
返回圖l，可以通過第一通信鏈路130，向第二處理系統120的輸入提 供第二數據結構160。第二處理系統可以執行第二多個指令中的一個或多 個，並且可以生成在170處指明的數據。在一些實現中，第二處理系統120 可以在執行之前，通過使用壓縮指令中的索引值訪問高速緩存190中的適 當的比特模式，來對在第二數據結構160中的任意壓縮指令(例如，64比特 指令)進行解壓。在第二數據結構160中沒有壓縮的(例如，128比特指令) 指令可以由第二處理系統120在不使用高速緩存190的情況下進行處理。
第二處理系統120可以通過一個或多個通信鏈路，例如第三通信鏈路 180，而耦合到一個或多個外部設備(沒有示出)，並且可以通過一個或多個 這種通信鏈路來向一個或多個這種外部設備提供數據170的一些或全部。
如上所說明，用於第二處理系統120的指令的一個或多個部分(例如， 比特模式)可以存儲到一個或多個存儲單元中(例如，高速緩存190)。在這點 上，高速緩存190可以包括單個存儲單元或多個存儲單元。在特定的情況 下(例如，對於相對較小的程序)，高速緩存190會具有足夠的空間來存儲對 於完全壓縮在第一數據結構140(或數據結構240)中的指令所必需的全部比 特模式。在其它情況下(例如，對於相對較大的程序)，高速緩存190可能不 具有足夠的空間來存儲對於完全壓縮在第一數據結構140(或數據結構240) 中的指令所必需的全部比特模式。在這種實現中，期望優化在數據結構140 或240中的指令的壓縮率，以便在給定了高速緩存190的大小約束的情況 下獲得最大壓縮量。現在將轉為描述這種代碼優化方案。
如上所提到的並且如在相關應用中所說明的，在程序中的指令可以通過從例如128比特指令中提取出常用的比特模式來進行壓縮。被索引的高 速緩存190可以保存這些常用的比特模式和對於新的壓縮指令(例如，64比 特指令)而言所需要的任意其它信息。編譯器和/或彙編器210可以識別要將 何種比特模式存儲到被索引的高速緩存190中，並且還可以確定哪些指令 能夠用新的壓縮指令來替代。根據包含指令的程序的大小和/或高速緩存 190的大小，由於在高速緩存190中有限的空間，可能不能壓縮特定的指令。 在這種情況，會期望壓縮器220(或者在壓縮功能是編譯器模塊的一部分的 情況下則是編譯器210)能最優地壓縮(例如，儘可能地壓縮)程序。
更詳細地說，例如在圖4中概念性地示出，可以將程序中的每個指令 分割為幾個欄位。但是，請注意，在一些實現中， 一個指令的一些部分可 能並不是任何欄位的部分。基於已經執行的經驗，大多數程序會包含用於 這些欄位中某些欄位的多個常用的反覆出現的比特模式(M個，其中M是大 於或等於一的整數)。還應注意，這M個欄位中的各個欄位不必是相同的大 小(即，每個欄位可以包含的比特數量與所有其它欄位都完全不同)。如果一 個指令的所有M個比特模式都由用於對存儲了原始比特模式的高速緩存 190進行索引的索引值所替代，那麼就能夠使用更為壓縮的指令來替代該指 令，從而得到了更為壓縮的程序。由於高速緩存190具有有限數量的條目 (entry),所以不是所有在程序的指令中找到的比特模式都能夠存儲到表中並 由索引值所替代。
圖3中的方法300描述了用於選擇要存儲在高速緩存190中的比特模 式的一種方案，該方案能獲得最佳代碼壓縮率(例如，由壓縮器220輸出的 壓縮數據結構160的大小與輸入到壓縮器220的數據結構240(或數據結構 140)的大小的最低比率)。儘管參照圖l、 2和4來說明方法300，但這個方 案並不限於在這些圖中所示的特定的示例。方法300可以從已經被轉換為 機器格式或二進位格式的指令開始(例如，通過編譯器210編譯它們)，從這 些指令中識別出比特模式。
方法300可以用以下行動開始壓縮器220從目標程序的指令中的可 壓縮欄位中提取出唯一性的比特模式[行動310]。可以使用多種己知的比特 識別方案中的任意方案來在行動310中確定在指令中的唯一性的比特模式 的數量。如參考行動320所說明，這些唯一性的比特模式可以映射到在整數或線性規劃公式(programmingformulation)中的變量上。
在識別了這組比特模式之後，壓縮器220可以構造目標程序的最優壓 縮的整數規劃或線性整數規劃表示[行動320]。這種整數規劃或線性整數規 劃表示可以由壓縮器220根據以下原則、示例和歸納，根據在行動310中 提取的唯一性的比特模式來自動地構造。
在高速緩存190中可能存在用於存儲壓縮比特模式的N個表(N〉-1)， 並且可能存在有M個欄位(M〉-1，M〉-N)，可以從這些欄位中選擇要插入表 中的比特模式。如圖4所示，例如，每個指令都可以包括多個欄位。例如， 兩個可能的情景是所有M個欄位共享單個(N4)表，或每個欄位具有自己 的表(M-N)。在每個情景中，每個欄位具有專用的表，如果指令被壓縮，則 我們就能從該表中取回壓縮的比特模式。在行動320中的方案可以使用從 可壓縮欄位到表的多對一的映射。
第i個表可以由Mi個欄位所共享。對於第i個表，可以存在一組變量。 每個變量與出現在Mj個欄位中的唯一性的比特模式相對應。因此，變量的 數量與Mi個欄位中找到的唯一性的比特模式的總數量相對應。
行動320可以使用用於構造最優代碼壓縮公式的兩個(或更多個)方案 中的一個(a)作為整數規劃問題，以及(b)作為線性整數規劃。然後，用於 解決任一類問題的任意算法都能夠在行動330中應用，以計算最優代碼壓 縮。儘管將說明這兩個方案，但是請注意，在行動320中，可以使用任意 多變量優化方案來建立為了獲得最優程序壓縮而要求解的公式。 (A)整數規劃
對於每個方案，將給出兩個具體的示例(即，M-N和N-1)，來提供用 於實現行動320的直觀的想法。然後，將給出對這兩個示例的歸納。圖4 示出了具有四條指令的示例程序410(該程序是輸入數據結構240或140的 一個具體實例)，每個指令具有三個欄位以及它們的比特模式，以下示例將 公式化這些欄位以便進行壓縮。為了便於描述而沒有示出並非壓縮候選的 其它欄位，儘管這些欄位也可以在程序中出現。為了便於描述，在該示例 中，假定所有欄位都是大小相同的，但之後提供的歸納並不需要這種假定。
M-N的示例
如果每個欄位都具有其自己的表，那麼X、 Y和Z可以被定義為多組變量，每組變量對應一個表。欄位X、 Y和Z分別具有3個、2個和3個唯
—性的比特模式。因此，有3個變量用於表X(X,，X2，X3)，有2個變量用於表
Y(yi，y2)，有3個變量用於表Z (Zl，z2，z3)。 一個可替換的觀點是，分別有3 個、2個和3個候選比特模式要存儲到表X、 Y和Z中。請注意，在這種情 景中，即使是指令1的欄位都具有相同的比特模式，但是仍然存在3個變 量，每個變量對應一個表。表X、 Y和Z分別地被進一步定義為具有Tx、 Ty和Tz個條目。
若且唯若壓縮了比特模式時，才為每個變量賦值l(即，其獲得了在相 應的表中的條目)；否則其被賦值為0。若且唯若壓縮了(即，實際上是用對 表的索引來進行替換)一個指令的所有可壓縮欄位時，該指令才是被壓縮了。 如果一個指令被壓縮了，那麼將該指令賦值為1，否則就將該指令賦值為o。
為了構造這個公式，每個指令都由所有與其欄位的比特模式相對應的 變量的乘積來表示。在這個示例中，表示指令l到4的乘積分別是x⑦zp x2y2z2 、 x!y2z3和x3yz3 。
期望將代碼壓縮(即，壓縮指令的數量)最大化。對於M-N的情況，整 數規劃公式則要尋找使得以下乘積之和最大化的Xi、力和Zi的值
最大化 + X2y2Z2 + Xi》Z3 + x3y,z3
滿足以下約束
*1..3) = 0或1 yi(i-l，2)-0或1 咖1"3) = 0或1
L=..3Xi^rx
L=1..2yi^Ty
I^oz^Tz (即，被壓縮的比特模式的數量必須適合每個相應的表。)
N=l的示例
如果所有欄位共享單個表，那麼對於整數規劃公式僅需要一組變量(例
如，變量組X)。在圖4中的欄位X、 Y和Z中，只存在4個唯一性的比特
模式。因此，有4個變量用於表X(^，X2，X3，X4)或4個候選比特模式。在這個
情景中，在指令1中的所有欄位都由同一變量A表示，因為它們都具有相 同的比特模式。表X可以具有T個條目。於此，對於N-1的情況的整數規劃公式要尋找使得以下乘積之和最大
化的Xj的值
最大化 XX!X+ X2X2X2 + XjX詢+ X4X1X3 要滿足以下約束-
Xi(i:l…4)-0或1
歸納
一般而言，在高速緩存190中有N&1)個表。第i個表具有在所有指令 (例如，所有Q條指令)的Mi個欄位中找到的Pi個候選比特模式。M， + M2 + ...+MN = M=可壓縮欄位的總數量。然後，這組Mi個欄位(和對應的第 i個表)具有一組Pi個變量，每個變量對應一個候選比特模式。
每個指令可以由M個變量的乘積來表示，每個變量都來自一個可壓縮 欄位。如果M-N(如上述示例)，則每個變量來自於不同的組。通用整數規 劃公式要最大化以下所有乘積之和
最大化 》=l..Qnk=l,...MX(j,k)
其中，x(j,k)是用於位於第j個指令的第k個欄位中的比特模式的變量。如 果第k個欄位的比特模式是要存儲到第i個表中的候選，那麼x(j,k)變量是
來自於與第i個表相關聯的Pi個變量之中。
由以下給出對於上述的約束
X-O,l，對於來自所有N個表的所有變量X而言；並且
Zk^Pi Xk^Ti ，其中Ti是第i個表中的條目的數量。也就是說，可插入
到任意表中的候選比特模式的最大數量受到該表的大小的限制。
ns)線性整數規劃
行動320的第二方法是以線性整數規劃問題的形式，來公式化該代碼 壓縮目的。在描述其歸納之前，再次使用以上示例的參數，以兩個不同的 情景(即，MHN並且N-1)給出行動320的直觀的想法。此外，圖4以4條 指令來進行討論，每個指令具有3個可壓縮欄位。
M-N的示例
如之前的方案中所示，若且唯若每個比特模式被壓縮時，與該比特模 式相關的變量才接收值1;否則該變量值為0。此外，還有4個變量(Wl,W2,W3,W4)，每個變量對應一個指令。若且唯若一個指令被壓縮時，與該 指令相關的變量才接收數值O;否則，其被賦值為l。若且唯若壓縮指令的 數量最大化時，和^《4Wj才是最小的。
也可以在與指令相關的變量(Wi's)和與比特模式相關的變量(Xi's， y卩s，
Zi'S)之間建立約束關係。對於每個指令，如果其欄位的比特模式中的任何一
個都沒有被壓縮(即，與比特模式相關的變量=0)，則該指令未被壓縮(即，
與指令相關的變量=1)。例如，對於第一個指令
v^ + xgl, Wi + y^;l， Wi+z!^;l
線性整數規劃公式是要尋找使得以下和最小化的Wi值-最小化Wi + W2 + W3 + W4
約束是
Xi(i-l,.3)-0或1 力(—1,2) = 0或1 咖1..3) = 0或1 Wi(i-l,.4)-0或1
以及
Wi + x^;l ， w2+ x^l ， w3 + x^l， W4+ ，
W2+y21， W2+Z麼l
w3 + y2^1， w3+z3^l
w4+ygl， W4+z化l (即，僅當一個指令的所有
欄位都被壓縮時，該指令才是被壓縮的) 以及
L=i..2y^Ty
Zi^3Z^Tz (即，被壓縮的比特模式的數量必須適合每個相應的表。) N=l的示例
如果所有欄位共享單個表(例如，在高速緩存190中)，那麼僅存在4個
唯一性的比特模式。除了用於4個候選比特模式的4個變量(X,,X2，X3，X4)之外， 還有4個與指令相關的變量(WhW2，W3,W4)。此外，表X可以具有T個條目。 整數規劃公式是要尋找使得以下和最小化的Wi值最小化W! + W2+W3+W4 要滿足的約束是
Xi(i-l.,4)-0或1 Wj(i-l.,4)-0或1
i:k.4x^t，用於將所選擇的候選的數量限制到表的大小
Wi + x>l， Wi + x]^:l， v^ + Xi^;l
w2 + xgl ， W2 + ， w2 + x^;l
W3 + X,>1， W3+X^l， W3+X3^;l
W4+X4>1， W4 + Xi^l， W4+X3>1
為了清楚起見，列出了所有上述這些約束，即使他們中的一些是冗餘的。
歸納
一般而言，在高速緩存190中有N(^1)個表。第i個表必須從所有指令 的Mi個欄位中找到的Pi個候選比特模式中(例如，所有Q條指令)選擇，以 適合它的大小。M1 + M2 + ...+MN = M=可壓縮欄位的總數量。然後，每 個第i個表具有一組Pi個變量，每個變量對應於一個候選比特模式。還有Q 個變量(Wj,j-l...Q)，每個變量對應於一個指令。每個指令生成一組M個約 束，每個約束對應於一個可壓縮欄位。
通用線性整數規劃公式是要尋找使得以下和最小化的Wi值
最小化S=l..QWj 給出如下約束
x = 0,1 ，對於所有與唯一性的比特模式相對應的變量x， w廣O,l，對於所有與指令相關的變量，
Zk^Pi Xk^Ti其中Ti是第i個表中條目的數量。(即，我們能插入到 任意表中的候選比特模式的最大數量是由表的大小所限制的)。
此外，對於每個第j個指令，有M個約束
Wj + x(j，歐l (k=l，...M)
其中x，k)是用於位於第j個指令的第k個欄位中的比特模式的變量。 總之，在行動320中，以上的整數規劃公式或線性整數規劃公式可以由編 譯器220，根據在行動310中提取的唯一性的比特模式來自動地構造。方法300繼續，使用編譯器220求解線性或整數規劃公式[行動330]。 因此，可將公式或表達式提供到任意的整數規劃或線性整數規劃解算器 (solver)。這種解算器是已知的，並且可以生成使得線性或整數規劃問題最 小化的最優解。在行動330中對變量解算出的解會識別出那些要被壓縮從 而使得代碼壓縮率最大化的比特模式。
壓縮器220可以基於在行動330中獲得的解，來壓縮在程序中的適當 的比特模式[行動340]。在相關的應用中描述了用於壓縮指令的幾個技術。 當在編譯時間(或在此之後很短時間內)，在行動340中壓縮程序時，在給定 了高速緩存190的大小約束的情況下來最優地壓縮程序。如上所說明，在 行動340中，在行動330被識別為要進行壓縮的這些唯一性的比特模式可 以存儲到高速緩存190中，並且可以將它們的索引插入到壓縮指令中。
在執行程序時，方法300在執行時間繼續進行，當第二處理系統120 執行該程序時，其對任意的壓縮指令進行解壓縮[行動350]。如上所述，不 是所有指令都需要被壓縮，儘管如果高速緩存190具有足夠的存儲空間則 就可以壓縮所有的指令。對於那些沒有被壓縮的指令，則不使用行動350。 對於被壓縮的指令(例如，從128比特壓縮到64比特的指令)，在行動350 中，第二處理系統120可以基於在壓縮指令中的索引，從高速緩存190中 取回所存儲的比特模式，來重新組合原始的、更大的指令。例如，在行動 350中，可以將解壓縮後的指令插入到由第二處理系統120執行的流水線中。
上述方案和系統可方便地並最優地壓縮程序(例如，內核或其它程序)， 並且其獨立於具體的整數規劃或線性整數規划算法或實現。在編譯時間的 這種最優的程序壓縮可以通過壓縮顯著地減小指令佔用區域，從而允許大 的、複雜的內核適於指令高速緩存。指令代碼大小的減少與指令高速緩存 大小的增加具有等同的效果。指令壓縮還可以減少指令讀取的功率和/或帶 寬需求(流水線、高速緩存等)。
前面的一個或多個實現的描述提供了圖示和描述，但並不旨在窮舉或 限制本發明的範圍到公開的精確的形式。多種變形例和變化例可以根據上 述指導實現或從本發明的各種實現的實施中獲得。
例如，儘管已經描述了線性和整數規劃方案，但可以使用任意的多變 量優化方案來確定要壓縮編譯的指令中的哪些比特模式來獲得最優程序壓縮。
除非明確地進行了描述，否則本發明的說明書中使用的要素、行動或 指令不應理解為對於本發明是關鍵的或是重要的。此外，在此使用的冠詞 "一"旨在包括一個或多個項。根據要求保護的發明的上述的實現，不實 質地背離本發明的精神和原則的情況下可以做出多個變化例和變形例。所 有這些變形例和變化例都旨在包括在本公開的範圍內，並且由以下權利要 求來保護。
權利要求
1、一種用於壓縮程序中的指令的方法，包括以下步驟從所述程序中的指令中，提取唯一性的比特模式；根據所述唯一性的比特模式和所述指令，構造線性規劃公式或整數規劃公式；求解所述線性規劃公式或所述整數規劃公式，以產生解；並且基於所述解，通過以下步驟來壓縮至少一些所述指令在存儲器中存儲至少一些所述唯一性的比特模式並將對所述存儲器的相應索引放置在新壓縮的指令中。
2、 根據權利要求1所述的方法，還包括在所述提取步驟之前，編譯在所述程序中的所述指令，以便將所述指 令從第一表示轉換為二進位語言表示或機器語言表示。
3、 根據權利要求1所述的方法，其中，所述構造步驟包括 構造線性規劃公式，所述線性規劃公式包括一組不等式約束以及方程，當使得所述方程最小化時，將最優地壓縮所述程序。
4、 根據權利要求1所述的方法，其中，所述構造步驟包括 構造整數規劃公式，所述整數規劃公式包括一組不等式限制以及方程，當使得所述方程最小化時，將最優地壓縮所述程序。
5、 根據權利要求1所述的方法，其中，所述構造步驟包括 至少部分地基於用來存儲所述比特模式的存儲器的大小，來構造所述線性規劃公式或所述整數規劃公式。
6、 根據權利要求1所述的方法，其中，所述構造步驟包括 將所述唯一性的比特模式表示為在所述線性規劃公式或所述整數規劃公式中的變量，並且將所述指令表示為在所述線性規劃公式或所述整數規劃公式中的變
7、 根據權利要求1所述的方法，還包括在執行之前通過以下步驟將所述新壓縮的指令進行解壓縮基於在所 述新壓縮的指令中的相應索引，從所述存儲器中取回所述至少一些唯一性 的比特模式。
8、 一種用於壓縮程序中的指令的方法，包括以下步驟 編譯所述程序，以產生二進位數據； 從所述二進位數據中提取唯一性的比特模式；基於所述唯一性的比特模式和用於所述唯一性的比特模式的存儲容 量，來構造線性規劃公式或整數規劃問題，當所述線性規劃公式或整數規 劃問題被解出時，將針對所述存儲容量而產生所述程序的最優壓縮； 求解所述線性規劃公式或所述整數規劃問題，以產生解；並且 基於所述解，來壓縮在所述程序中的至少一些所述指令。
9、 根據權利要求8所述的方法，其中，所述構造步驟包括 將所述唯一性的比特模式映射到在所述線性規劃公式或所述整數規劃問題中的變量上。
10、 根據權利要求8所述的方法，其中，所述整數規劃問題包括線性 整數規劃問題。
11、 根據權利要求8所述的方法，其中，所述解指定了在所述壓縮步 驟中要使用的被指派的唯一性的模式，以及其中，所述壓縮步驟包括在存儲器中的所述存儲容量內存儲所述被 指派的唯一性的模式。
12、 根據權利要求8所述的方法，還包括以下步驟-在執行壓縮的指令之前，將所述壓縮的指令進行解壓縮。
13、 根據權利要求12所述的方法，其中，由第一處理系統來執行所述 編譯步驟、提取步驟、構造步驟、求解步驟和壓縮步驟，並且其中，由第二處理系統來執行所述解壓縮步驟。
14、 一種用於壓縮程序的系統，包括 編譯器，用於將所述程序翻譯為二進位格式；存儲器，用於存儲二進位數據，所述存儲器具有一容量；以及 壓縮器，連接到所述編譯器和所述存儲器，用於從所述程序的所述二 進位格式中提取唯一性的比特模式，並且基於所述存儲器的容量和所述唯 一性的比特模式，通過在所述存儲器中存儲至少一些所述唯一性的比特模 式並將相應的索引插入到所述程序中，來最優地壓縮所述程序。
15、 根據權利要求14所述的系統，還包括處理系統，連接到所述存儲器和所述壓縮器，用於執行所述最優地壓 縮的程序。
16、 根據權利要求15所述的系統，其中，所述處理系統用於通過使用 所述相應的索引從所述存儲器中取回所述至少一些唯一性的比特模式，來 對所述最優地壓縮的程序進行解壓縮。
17、 根據權利要求14所述的系統，其中，所述壓縮器用於公式化並求 解整數規劃問題，以最優地壓縮所述程序。
18、 根據權利要求17所述的系統，其中，所述壓縮器還用於在公式化 所述整數規劃問題時，將所述唯一性的比特模式映射到變量上。
19、 根據權利要求17所述的系統，其中，所述整數規劃問題是線性整 數規劃問題。
全文摘要
一種用於壓縮程序中的指令的方法，可以包括以下步驟從所述程序中的指令中提取唯一性的比特模式；並且根據所述唯一性的比特模式、所述指令、和/或存儲器存儲容量的大小，構造線性規劃公式或整數規劃公式。可以求解所述線性規劃公式或所述整數規劃公式，以產生解。該方法還可以包括基於所述解，通過在存儲器中存儲至少一些所述唯一性的比特模式並將對所述存儲器的相應索引放置在新壓縮的指令中，來壓縮至少一些所述指令。
文檔編號H03M7/30GK101622790SQ200880006440
公開日2010年1月6日 申請日期2008年3月21日 優先權日2007年3月27日
發明者B·鄭, C-C·林, G-Y·魯, 洪 江 申請人:英特爾公司