TWI334571B - Program instruction rearrangement methods - Google Patents
Program instruction rearrangement methods Download PDFInfo
- Publication number
- TWI334571B TWI334571B TW096106090A TW96106090A TWI334571B TW I334571 B TWI334571 B TW I334571B TW 096106090 A TW096106090 A TW 096106090A TW 96106090 A TW96106090 A TW 96106090A TW I334571 B TWI334571 B TW I334571B
- Authority
- TW
- Taiwan
- Prior art keywords
- instruction
- program
- command
- write
- current
- Prior art date
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/40—Transformation of program code
- G06F8/41—Compilation
- G06F8/43—Checking; Contextual analysis
- G06F8/433—Dependency analysis; Data or control flow analysis
Landscapes
- Engineering & Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Executing Machine-Instructions (AREA)
- Advance Control (AREA)
Description
13-34571 九、發明說明： 【發明所屬之技術領域】 本發明係有關於電腦技術，且特別有關於程式指令調 整方法。 【先前技術】
典型的處理器利用管線技術(pipelining)在同一時間中 可執行複數指令（instruction)。在管線中，當一指令之運算 元（operand)暫存器（register)為前一指令之輸出結果時，此 指令會被暫停執行直到等待前一指令產生上述輸出結果。 以下列指令來說明一實例： #101.add a X y #102. inc a #103. dec b // a = (x+y)+l; b = b-l 參照第1圖，指令#10〗的執行階段可以分為： 取得指令#101 ; 讀取X及y ; add運算；以及 寫入a 〇 指令#102在其第二執行階段時被讀取(fetch)出，隨即 需在第三執行階段進行a的讀取，但因為#令麵係在第 四執行階段才寫人暫存H a，因此指令繼需在第五執行 階段時才可以執行暫存H a的讀取。換言之，指令#1〇2第
Client's Docket No.: VIT06-0030 TT’s Docket No: 0608-A40780twf.doc/J〇seph/2〇〇5_12 2〇 1334571 . 五執行階段的輸入係需依賴指令#101在第四執行階段的 輸出。另’在執行指令#102的第五執行階段的同時開始處 理指令#103。這使得指令總共需要8個時脈的時 間來執行。若指令#102在第五執行階段所讀取的不是暫存 器a，則與指令#101第四執行階段無相依關係，則指令#1〇2 可提前至第三執行階段時執行暫存器a的讀取，指令#1〇3 亦可提前兩個執行階段，因此整體指令#1()1屬的執行只 需要6個時脈即可完成。 由上述實例可知，具有相依關係之二指令在具有管線 架構的處理器中若無適當的安排難，則會降低整體的執 行效率。 【發明内容】 有鑑於此’本發明提供―種程式指令調整方法。首先， 、自一儲存裝置中取得即將由-電腦處理器執行之-程 式。取得該程式檢視中的-指令作為—目前指令，取得該 目^指：所使用的-暫存器及該目前指令對該暫存器所執 灯的-弟-動作。在其他程式指令在上述第—動 =-暫存器執行-第二動作的情況下，根據該目前指令 與其他程式齡存取該暫存^之餐建立_式之指令間 的-相依_"根據該相依_計算程式 依深度。根據該程式中每一指令之相依 :7的1 式中所有指令的執行順序。 又 ^^^ 另外，本發明實施例提供一種程式指令調整方法。首 先自一儲存裝置中取得即將由—電 门么舌^
Client's Docket No.: VIT06*0030 匈爽理器執行之一程 TT's Docket No: 0608-A40780twf.doc/Joseph/20〇5-i2-2〇 6 弋取h·上述程式檢視中的一入 上述目前指令對該暫存器執行1—動：:！指：。當在 指令對同-暫存器執行 ㈣乍以月”亦有其他 令盥目‘#入 第一動作的情況下，建立1他浐 目則指令之間的相依關係， 。他才曰 些其他指令係為目前:上以相依關係中該 ，的每—指令作為上述目前指序地取得程式 係後，開始順序地反向回溯所:上'ϋ應的相依闕 反向回溯的上層指令為一指令群組:若曰:上：:::被 指令另不=令群組時，自上述程式中刪 先，=二2!施例提供—種程式指令調整方法。首 彳 ：子裝置中取侍即將由-電腦處理器執行之一程 式_:取得該程式檢視中的一指令作為-目前指令，取得令 :前π使用的一暫存器以及該目前指令對該暫=二 :=二：動作。在其他程式指令在上述第-動作以前 亦子同-暫存㈢執行存取的情況下，根據該目前指令就 他程式指令存取該暫存k順序建立該程式之指令間的二 相依關係。根據該相依關係以移除上述程式中冗餘的移動 指令。 上述之私式在經由上述各實施例的重新排列及/或冊I】 除後，會交付至該電腦處理器進一步執行。 【實施方式】 以下έ兒明是本發明的較佳實施例，乃舉例說明本發明 般性的原則，不應視為本發明之限制，本發明之範圍當 以申請專利範圍所界定者為準。
Client’s Docket No.: VIT06-0030 TT s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 1334571 在先前技術中所描述的例子中，由於指令#103與其它 指令無相依關係，因此可以安排指令#103提前為第二指令 進行執行，因此上述指令可以下列順序執行： #101. add a X y #103. dec b #102. inc a
第2圖顯示以上述重新安排之順序執行上述指令之執 行階段，以此順序執行的結果與原順序一致，而且僅需7 個時脈的時間即可完成。由此可知在不影響程式正確性的 條件下，只需調整指令的順序就可以改善程式的執行效 率。因此，以下提出一種程式指令調整方法。 參照第3圖，電腦裝置1〇〇中，處理器1耦接顯示卡 2、程式指令調整系統3以及儲存裝置4。程式41可以先 用程式指令調整系統3處理後，再由電腦裴置1〇〇或其它 電腦裝置，例如遊樂器（video game console)、行動電話、 個人數位助理(Personal Digital Assistant，簡稱pj)A)等之處 理器（例如處理器1或顯示卡2中的圖形處理器（Graphics ProcessmgUnit，簡稱GPU))上來執行。程式指令調整系統 3包含分析程式、移除冗餘指令、移除冗餘的移動指令 _V in_ctl0n)以及指令重新排序等步驟，分別由分析 器31、指令移除器33、指令移除器34 ; M广。。 及排序器32來實作。 程式指令調整系統3中的各元件可以萨4 + 式或硬體或此二者 之組合來實作。 包含下列指 舉例來說，程式41為著色程式（shader)，
Client’s Docket No.: VIT06-0030 TT's Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 8 1334571 令： #0: texld r0, tO sO #1: mov r2 rO #2: texld rl, tl si #3: mad r3, rO cO rl #4: rep r4, rl #5: mad oCO, r2 r3 cl #6: mov 0C1, r3 參照第4圖，分析器31分析程式41之指令間的相依 關係之流程圖。首先，分析器31取得程式41，並取得程 式41正檢視中的一指令作為目前指令（步驟S2)。若該目前 指令為一開始指令、輸出指令或移動指令，分析器31會儲 存一對應紀錄以指示該目前指令之指令類別（步驟S4)，其 中，輸出指令為輸出程式41最後結果的指令，另外，有些 暫存器被定義為輸出暫存器，而將運算結果寫入輸出暫存 器的指令亦可以被判別為輸出指令。 分析器31會在步驟S6中進行初始化程序，其中初始 化程序包括取得上述目前指令的初始相依深度 (dependency depth)，並在步驟S8中取得上述目前指令使用 的暫存器，包含寫入暫存器與讀取暫存器。每一指令的相 依深度可以再細分為不同類型。以下之相依深度用以指示 複數指令存取暫存器之順序上的相依關係。 主要是由於指令存取相同暫存器才構成指令間的相依 關係，因此步驟S8記錄指令所使用的暫存器是為了方便相
Client’s Docket No.: VTT06-0030 TT^ Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 c 1334571 依關係的分析。可以一資料結構記錄上述目前指令所使用 的暫存器之寫入指令（writer instruction)及讀取指令（reader instruction)。分析器31判別上述目前指令所使用的寫入暫 存器是否已經被記錄於一資料結構（步驟S10)?如否，分析 器31產生一資料結構以記錄上述目前指令之寫入暫存 器，並記錄上述目前指令為該暫存器之寫入指令（步驟 S18)。其中，上述資料結構可以儲存於電腦裝置100之主 記憶體（未圖示）。
舉例來說，分析器31可以利用下列表格0來記錄指令 #0寫入的暫存器r0 : r0 寫入指令 讀取指令 表格0 以上的暫存器紀錄法是在一單純狀況下的模式，如果 一暫存器rlO具有紅、綠、藍及alpha頻道，則可以表格1 記錄暫存器rlO各頻道的讀取或寫入指令： rlO R 寫入指令 讀取指令 G 寫入指令 讀取指令 B 寫指令 讀取指令 A 寫入指令
Client’s Docket No.: VIT06-0030 TT5s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20
其中R、g、b、a八表袼1 频道。任_ 為暫存器rl〇的 =分析…《類似的二暫存器，之單-頻道I 如指物己錄。目前指令的讀取暫 °歹'如指令#0的r〇)。 ~暫存s(或稱為結果暫存 器已:=τ〇的，中，上述… 饿。己錄，表示至少 目刖指令之寫入暫在 先ί :Μ前已經使用同樣的暫；!:令在目前指令使用寫入 :存器之第二動作以建立:二::作及目前指令對該寫人 、=(包含稍後說明的及目Μ指令之間的相依 述貝料結構（例如上述表格 _w相依關係）。可以從上 為早於目前指令使用同的元錄的指令來判斷何者 表格0無記錄任何指令=的先前指令。舉例來說， 的指令。 θ令#0為首先使用暫存器r0 由於指令#0將運算钟 是暫存tiro的寫入指令:暫存11 Γ〇,因此指令#0 格2所示： ^貝料結構記錄指令#1後如表 ^-—L^______________________ 表格2 當指令#1讀取暫存器Γ〇 ’ 八
Client's Docket No.: VTT06-0030 TT's Docket No: 0608-A40780twf.doc/Joseph/2005-12· 、私π #1疋暫存器r〇的讀
Docket No.: VIT06-0030 "Μλ· ΠΑ〇β_Δ4Π7βΠκι/ί* ΗΛη/ΤΓ»ε#»Γ\ν»/9ΠΠ<_ 1-» 11 -20 取指令。於上述表格2令記 令以前’表格2中無任何讀取;二=^，指 令。指令-與子有取'存器，最後一個指 Write-Read(W-R)#feM#i 間相依關係還有W_W相依 ’ Ύ之 R-W相依關係（即先讀後寫’、P先寫後寫關係）以及 存…動作(為=寫說’指令㈣暫 入資料至暫存W，則指令料與指令曰===旨糾寫 «係；如果有指⑽早於存^2 相 :與ί Γ#1之間具有R，相依關係:。換言：先 第一與第二動作，並且^存j订之處理動作分別稱為 動作盥讀取動作昧甘田 作及第二動作分別為寫入 3第相依關係…相依關係;或 W-W相依關係；或‘第’其間的相依關係為 寫人動作時，其間的相依關係讀=與 關係令，先前指令為目前指令之關係°上述相依 用另-種資料結構，如樹狀 ”7 ’依此’可以利 另外， f狀、，，口構，以記錄上述相依關係。 中，亦會記錄該器所對應的資料結構 指令，如下列表格3所示： 縣令#1為其讀取 ·： VIT06-0030 〇608-A40780twf.d〇c/J〇
Client’s Docket Ν TT5s Docket No： seph/2〇〇5-12-2〇 12 1334571 r0 寫入指令 #0 讀取指令 #1 表格3
在步驟S18甲，於目前指令的寫入暫存器對應的資料 結構中記錄目前指令為寫入指令。若該資料結構中已存在 一寫入指令，則以上述目前指令取代之。若該資料結構中 已存在一個或一個以上的讀取指令，則刪除上述一個或一 個以上的讀取指令。刪除先前的寫入指令以及讀取指令是 為了方便下一次對先前指令之判斷。 以一實例來說明，請參考表格4，其乃紀錄在寫入暫 存器r2對應的資料結構中記錄指令#1為寫入指令以前的 狀態。 r2 寫入指令 #8 讀取指令 #ΙΌ, #12 表格4
表格4中，讀取指令#10及#12未被刪除，表示在指令 #8寫入資料至暫存器r2後，讀取指令#10及#12才讀取暫 存器r2。因此，在指令# 1加入後，分析器31需分別建立 指令#10與指令#1之間以及指令#12與指令#1之間R-W相 依關係，與指令#8與指令#1之間W-W相依關係，並在表 格4中以指令#1取代指令#8,最後删除表格4中的指令#10 及#12，結果如表格5所示： r2 寫入指令 #1 讀取指令
Client’s Docket No·: VIT06-0030 TT's Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 13 1334571 表格5 以另一實例來說明，請參考表格6，其乃紀錄在寫入 暫存器r2對應的資料結構中記錄指令#1為寫入指令以前 的狀態。 r2 寫入指令 #13 讀取指令 表格6
表格6中表示指令#13是在指令#1寫入資料至暫存器 r2以前，寫入資料至暫存器r2的最後一個指令。因此，在 指令#1加入後，分析器31會建立指令#13與指令#1之間 的W-W相依關係，並在表格6中以指令#1取代指令#13， 結果如表格7所示： r2 寫入指令 #1 讀取指令 表格7 因此，如果在步驟S10的判斷中，上述目前指令之寫 入暫存器已被記錄，表示有一個或一個以上的先前指令在 目前指令使用寫入暫存器以前使用同樣的暫存器，則分析 器31根據上述方式以建立每一先前指令及上述目前指令 W-W相依關係（步驟S12)及R-W相依關係（步驟S14)，並 計算目前指令之相依深度，作為相依深度第一值（步驟 S16)。因為在此步驟S10判斷的是目前指令之寫入暫存 器，在步驟S12及步驟S14中只會建立W-W及R-W相依 關係，而W-R相依關係則在步驟S20之後處理。
Client's Docket No.: VIT06-0030 TT's Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 14 1334571
以下舉例說明目前指令相依深度之計算。當目前指令 具有複數上層指令時，分析器31選取其中相依深度最大者 作為計算目前指令相依深度的參考基準，以上述被選取的 先前指令之相依深度值來作運算，取其運算結果作為上述 目前指令之相依深度，使先前指令與目前指令之相依深度 相差一預定差值。舉例來說，當每一指令之相依深度初始 化為整數0時，上述運算可以為加法運算，而上述預定差 值可以是整數1。當然每一指令之相依深度初始化為整數0 以外另一數值(例如程式41之指令總數），上述運算可以其 它運算（例如減法運算）實作。 類似於步驟S10，分析器31判別上述目前指令所使用 的讀取暫存器是否已記錄於一資料結構中（步驟S20)?如 否，分析器31產生一資料結構以記錄目前指令之讀取暫存 器，並記錄目前指令為該暫存器之讀取指令（步驟S28)。如 果在步驟S20的判斷中，上述目前指令之讀取暫存器已被 記錄於一資料結構中，表示有一先前指令在目前指令使用 該讀取暫存器以前使用同樣的暫存器，則分析器31會根據 先前指令與目前指令分別對該讀取暫存器之第一動作與第 二動作，以建立先前指令及目前指令之W-R相依關係（步 驟S22)，並以上述方式利用其上層指令計算上述目前指令 之相依深度（步驟S24)，作為相依深度第二值，並以上述第 一值及上述第二值中較大者作為上述目前指令之相依深度 (步驟S26)。 因為在此步驟S20判斷的是目前指令之讀取暫存器，
Client's Docket No.: VIT06-0030 TT^ Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 ^领S22中只會建立W.R相依關係，而不 相依關係。R_R關係(先讀 1 序不會影響程式執行的正確性，因此不^^曰令之喂 另外，第4时有關寫人暫關係。 雖係以步㈣㈣及S20〜28的:;:= 及S20 % — 士《 — 幻丨負序執仃，但步驟S10〜18 8在處理順序上亦可以對調，或平行處理 在步驟S28 ’分析器31於記錄目前指令讀取暫
貝科結構中記錄目前指令為該暫存器的讀取指令 p 刪除其它讀取指令或寫入指令（步驟S28)。 不而 舉例來說’當有指令#12讀取暫存器 表格8之記錄： 乂月』已存在如
在建立指令#8與指令#12之間的W_R相依關係後，於
中登記指令#12為暫存器〇之讀取指令而不需刪除 /、匕讀取指令或寫入指令，結果則如表格4所示。 分析器3丨判別程式41是否還有其它指令（步驟s3〇)。 如有’分析器31取得下一指令作為目前指令以進行上述各 處理步驟(步驟S2);如無，分析器31輸出分析結 S32、。 在順序地取得上述程式中的每一指令作為目前指令以 上述步驟處理後，分析器31可以產生一樹狀資料結構來表 示权式41中的所有指令之間的相依關係，如第$圖所示。
Client’s Docket No·: V1T06-0030 TT’s Docket No: 0608-A4078〇twf d〇c/J〇seph/聰 i2 2〇 1334571 第5圖的樹狀資料結構中，每一節點可以包含指令的 編號、相依深度（以參數D e p表示）及其它資訊。排序器3 2、 指令移除器33及34可以利用此樹狀資料結構以進行冗餘 指令移除、冗餘移動指令移除以及指令重新排序。 指令移除器33從程式41之輸出指令開始利用反向回 溯器3 5來回溯所有的上層指令，並紀錄所有被反向回溯的 上層指令為一指令群組。若程式41中有一指令不屬於上述 指令群組時，則指令移除器33會自程式41中刪除該指令。
參照第6圖以說明反向回溯器35之運作。反向回溯器 35將程式41之輸出指令#5及#6輸入至一驗證清單中（步驟 S40)，其中上述驗證清單如表格9所示： 驗證清早 回溯次序 已回溯指令 0 #5, #6 表格9 在回溯次序0對應的已回潮指令中，反向回溯器3 5取 指令#5為目前指令（步驟S42)，並將該目前指令之所有未 記錄於上述驗證清單中的上層指令（即指令#1及#3)記錄於 上述驗證清單（步驟S44)，其結果如表格10 : 驗證清單 回溯次序 已回溯指令 0 #5, #6 1 #5, #6, #1, #3 表格10
Client's Docket No.: VIT06-0030 TT's Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 17 1334571 在回溯次序1中，目前指令#5的上層指令#1及#3被 記錄於驗證清單。反向回溯器3 5判別驗證清單中目前指令 之後是否還有指令（例如指令#6)(步驟S46)。如是，則反向 回溯器35取得下一指令作為目前指令以重複上述步驟（步 驟S42);如否，反向回溯器35輸出回溯清單中的已回溯 指令至指令移除器33，作為上述指令群組（步驟S48)。下 列表格11列出反向回溯器35之各回溯次序及最後的結果：
驗證清單 回溯次序 已回溯指令 0 #5, #6 1 #5, #6, #1, #3 2 #5, #6, #1, #3 3 #5, #6, #1, #3, #0 4 #5, #6, #1, #3, #0, #2 5 #5, #6, #1, #3, #0, #2 6 #5, #6, #1, #3, #0, #2 表格11 表格11的各回溯次序中加底線的指令為該次序中的 目前指令。程式41中有一指令#4不屬於上述指令群組， 被視為冗餘指令，因此指令移除器33刪除程式41中的指 令#4，結果如下： #0: texld r0, t0 s0 #1: mov r2 r0 #2: texld rl, tl si
Client’s Docket No·: VIT06-0030 TT5s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 1334571 #3: mad r3, rO cO rl #5: mad oCO, r2 r3 cl #6: mov 0C1, r3 其中指令#4已被刪除。此結果的對應樹狀資料結構如 第7圖所示。
參照第8圖，其係本發明另一實施例之流程圖。指令 移除器34根據記錄指令類別的上述對應紀錄取得上述程 式中的移動指令，例如指令#1(步驟S5(J)，並判別該移動指 令是否可以被移除（步驟S52)。
當移動指令具有上層指令及下層指令（例如指令# 1的 上層指令#0及下層指令#5)，且與其上層指令及下層指令之 相依關係皆屬於W-R關係時，該移動指令可以被移除。該 移動指令即使被移除也不會影響程式執行之正確性。在移 動指令被刪除時，指令移除器3 4修改上述移動指令的下層 指令。明確而言，指令移除器34修改移動指令的下層指令 中與該移動指令共用之運算元暫存器（例如指令#5的原讀 取暫存器r2)為上述移動指令之上層指令的結果暫存器（例 如指令#0的寫入暫存器rO)(步驟S54)。上述被修改的共用 運算元暫存器同時也是被刪除的上述移動指令的寫入暫存 器。在刪除移動指令後，指令移除器34重新建立上述移動 指令的下層指令與上層指令之間的相依關係。 指令移除器34刪除上述移動指令（例如指令#1)(步驟 S56)，並判別程式41是否還有移動指令（步驟S58)。如否， 則結束指令移除器34之作業；如是，則再取得另一移動指
Client's Docket No.: VIT06-0030 TT5s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 19 1334571 令以上述步驟處理。程式41由指令移除器34處理後的結 果如下： #0: texld rO, t0 s0 #2: texld rl, tl si #3: mad r3, rO cO rl #5: mad oCO, rO r3 cl #6: mov 0C1, r3
其中指令#1已被刪除，且指令#5的原讀取暫存器r2 被暫存器rO取代。此結果的對應樹狀資料結構如第9圖所 示。 上述的指令移除器33及34的執行順序可以任意安 排，而本發明除了利用指令移除器33及34刪除不必要的 指令外，排序器32可以處理經過指令移除器33及34之一 或二者調整後的程式指令。排序器32根據上述程式中每一 指令之相依深度以穩定排序法（stable sorting algorithm)，例 如合併排序法(merge sort)重新排列程式41中的所有指令。 為了顯示排序前後的差異，僅將指令移除器33處理後 的程式41輸入排序器32。程式41由排序器32處理後的 結果如下： #0: texld rO, t0 s0 #2: texld rl, tl si #1: mov r2 rO #3: mad r3, rO cO rl #5: mad oCO, r2 r3 cl
Client’s Docket No.: VIT06-0030 TTss Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 20 1334571 #6: mov 0C1, r3 其中指令#2之執行順序已被調整至指令#1之前。由於 指令#1與指令#2之間無資料相依關係，在處理器的管線中 可以順序執行，不需暫停處理指令#2。 排序器32、指令移除器33及34可以單獨對程式41 執行對應功能，並不影響程式之最後輸出結果的正確性。 因此，程式41被排序器32、指令移除器33及34中任何 一者處理過後皆可以由電腦裝置100執行。 總之，上述方法是根據執行特定作業之程式（例如著色 程式）_的複數指令對暫存器之動作來分析指令之間的相 依關係，再根據分析結果以減少該程式中冗餘指令、調整 其中的指令順序，之後再將調整後的程式輸入電腦裝置， 可以改善電腦裝置執行上述特定作業的效率。 雖然本發明已以較佳實施例揭露如上，然其並非用以 限定本發明，任何熟習此技藝者，在不脫離本發明之精神 和範圍内，當可作各種之更動與潤飾，因此本發明之保護 範圍當視後附之申請專利範圍所界定者為準。 【圖式簡單說明】 第1圖顯示複數指令之執行階段示意圖； 第2圖顯示調整執行順序之上述指令之執行階段示意 圖； 第3圖顯示一電腦裝置實施例之結構方塊圖； 第4圖顯示一程式指令相依關係分析方法實施例之流 程圖；
Client's Docket No.: VIT06-0030 TT*s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 21 1334571 第5圖顯示程式指令相依關係分析結果之資料結構示 意圖， 第6圖顯示反向回溯之流程圖； 第7圖顯示刪除冗餘指令之程式的對應資料結構示意 圖； 第8圖顯示刪除冗餘移動指令之方法實施例之流程 圖，以及 第9圖顯示刪除冗餘移動指令之程式的對應資料結構 示意圖。 【主要元件符號說明】 ‘ 1〜處理器；2〜顯示卡；3〜程式指令調整系統；4〜儲存 裝置；31〜分析器；32〜排序器；33〜指令移除器；34〜指令 移除器；35〜反向回溯器；N0-N6〜節點；100〜電腦裝置。
Client’s Docket No.: VIT06-0030 TT5s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 22
Claims (1)
- 丄： 十、申請專利範圍： I一種程式指令調整方法，包含. 式； 电知處理器執行之—程 取知该種式檢視中的—指令 目前指令所使用的—暫存器及該目前·; ^指令，取得該 行的一第一動作； ^曰々對该暫存器所執 在其他程式指令在上述第一動 執行-第二動作的情況下，根據亦對同-暫存器 :存取該暫存器之順序建立_式之程式指 係； 7間的—相依關 根據該相依關係計算程式中 及 的相依深度；以 根據該程式中每一指令之相依深度 所有指令的執行順序。 重新排列該程式中 2. 如申請專鄉㈣丨項所 更包括： 任巧知令凋整方法， 儲存一對應紀錄以指示該目前指令 中該指令類別包括開始指令、輸出 ^=別，其 出指令乃為輸出該程式最後執行結果的指^純令，而輸 3. 如申請專利範圍第！項所述 7 更包括一初妒仆鞀皮^ 7目周整方法， •初始相依 深度。 Η曰7的不 整方法， 4·如申請專利範圍帛1項所述的程式指令調 Client’s Docket No.: VIT06-0030 TT's Docket No： 0608.A40780twf.doc/Joseph/2005-i2-20 23 丄334571 ^中以一穩定排序法(stable sorting algorithm)重新排列上 述程式中的所有指令。 5.如申請專利範圍第1項所述的程式指令調整方法， 其中叶算程式中每一指令的相依深度方式包括： 以執行該第二動作的其他指令作為該目前指令的上層 指令； S 、^取。亥些上層指令中相依深度最大者之相依深度值作 一運算，以該運算的結果重新作為上述目前指令之相依深 度，使上述目前指令與其上述上層指令之相依深度相差一 預定差值；以及 根據上述程 < 中每—指令之相依深度以重新排列上述 程式中的所有指令。 6.如申請專利範圍第5項所述的程式指令調整方法， 其中’更包含：開始順序地反向回朗有上層指令，並崎所有被反 向回溯的上述上層指令為一指令群組；以及 若上述程式中有一指令不屬於上述指令群組時，自上 述程式中刪除該指令。 /.如"專利範圍第！項所述的程式指令調整方法， ^中’當上述第二與第-動作分別為寫人動作與讀取動作 ¥，將上述相依_分類為先寫後讀_ 第一動作皆為寫入動作時 11弟―、 智明也. ♦上过相依關係分類為先寫後 寫關係，當上述第二與第一動作八 ± 乐動作刀別為頊取動作與寫入動 作時，將上述相依關係分類為先讀後寫關係。 Clients Docket No.： VIT06-0030 TT>s Docket No: 〇608-A40780twf.doc/Joseph/2〇〇5-i2-2〇 24 8.如申請專利範圍第7 其中’更包含： 根據一指示指令類別之 移動指令； 項所述的程式指令調整方法， 對應紀錄取得上述程式中的一 當上述移動指令具有—上、下層指令，且 與其上層指令及下層指令之 比 0 ^ 時，則修改上述移動指令的下乂指令先=讀關係 杯動指令的上層指令的結果暫存器；以及 自上述程式令刪除該移動指令。 更勺9人如申請專利範㈣1項所述的程式指令調整方法， 進一 ^執=新排舰之'^程式交付至該電腦處理器作 10. —種程式指令調整方法，包含： 式；自—儲存裝置中取得即將由一電腦處理器執行之-程 =得上述程式檢财的—指令料—目前指令； =在上述目前指令對該暫存器執行—第_動作以前， 2他暫存器執行—第二動作的情況下，建 ㈣他k與該目前指令之間的相依_，其卜 依關係中該些其他指令係為目前指令之上層指令； 建立t:::::私式中的母—指令作為上述目前指令並 :二及錄所有被反向_的上層指令為—指令群 Client's Docket No.： VIT06-0030 s Docket No： 〇608-A40780twf.doc/Joseph/2005-12-2〇 25 !334571 上述===:指令不屬於上述指令群組時，自 法：申:包專含利，^ 電腦處理器作進-步執Ζ除5亥指令後之上述程式交付至該 令；以H结構記錄上述暫存器的讀取指令及寫入指 :上逑第—動作為讀取動作時，於上 錄上述目前指令為上述暫存器的_第一讀=了射吕己 士資:T構中記錄上述目前指令為 ； 令上述相依關係為先寫後讀關: 钎二、、'動作為寫人動作時，於上述資料己 錄亡述目前指令為上述暫存器的—第 =4中5己 ί貢料結構中記錄上述目前指令為上述第；入二士 入指令，且無上述暫存器之讀取為t述暫存器之寫 係為先寫後寫關係，且刪除上述資心吉構中的立已關 令以前，上述資料結構中已經儲 ：:寫， 個以上的讀取指令時，建 这暫存DD之一個或一 個以上的讀取指令之每前指令與上述一個或一 曰的相依關係為先讀後寫關 Client's Docket No.： VIT06-0030 IT's Docket No: 〇6〇8-A40780twf.doc/Joseph/2〇〇5-12-2〇 26 j334571 係’並刪除上述資料結構中的上述一個或一個以 指令；以及 ^ _若於上述資料結構中記錄上述目前指令為第一寫入指 令以别，上述資料結構中已經错存上述暫存器之一個或一 個以上的讀取指令以及一第二寫入指令時，刪除上 寫入指令。 币一 13. —種程式指令調整方法，包含·· .自儲存裝置中取得即將由一電腦處理器執行之 式； 取得該程式的-指令作為一目前指令 令所使用的一暫存器； ·汉々目刚才曰 ，其他％式指令在上述第_動作以前亦對同一暫存器 :子取的情況下，根據該目前指令與其他程 取 该暫存器之順序建立該程式#a '存取 式才"間的一相依關係；以及 根據该相依關係以移除上述程式中冗餘的移動指〜 法，請專利範圍第13項所述的程式指令調整方 财1上式中具有—第二指令在上述目前指令使用-暫存㈣前使㈣-暫存器，則㈣ 7 暫存器之第-動作及上述目前指令對上述玆=上； r建f上述第二指令及上述目前指令之相二 虽上述第一與第二動作分別為宜 ’、八中 ，述,依關係分類為先寫後讀關係，上’將 第二指令為上述目前指令之上層指令； 又卜、上述 Chenfs Docket No.: VIT06-0030 TT*s Docket No： 〇6〇8-A40780twf.d〇c/jOSeph/2〇〇5_12.2〇 27 田延目月IJ指令為一移動 且上述移動指令與其Ί、有一下射曰令， 於先寫後n主 及下層指令之相依關係皆屬 =寫後毫時’則修改上 : 存器為上述移動指令的上層指令的上二; 杰，其中上述相關運算元暫 ？的、，口果暫存 入暫存器；以及 °。 °述移動指令的寫 刪除上述程式中的上述移動指令。 15·如申請專利範圍第u焐 法，更包含： 、a的程式指令調整方 若上述目前指令為移動指令，儲存 該目前指令為移動指令；以及 T應紀錄以指示 根據上述對應紀錄取得上述程 16.如申請專利笳囹筮夕動指令。 T明寻利耗圍# 13項所述 法’更包含： 飞和令調整方 關係 建立上述移動指令的下層指令與上層於八 |。 9 7 <間的相依 Client’s Docket No·: VIT06-0030 TT’s Docket No: 0608-A40780twf.doc/Joseph/2005-12-20 28
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| TW096106090A TWI334571B (en) | 2007-02-16 | 2007-02-16 | Program instruction rearrangement methods |
| US11/849,485 US8082421B2 (en) | 2007-02-16 | 2007-09-04 | Program instruction rearrangement methods in computer |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| TW096106090A TWI334571B (en) | 2007-02-16 | 2007-02-16 | Program instruction rearrangement methods |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| TW200836099A TW200836099A (en) | 2008-09-01 |
| TWI334571B true TWI334571B (en) | 2010-12-11 |
Family
ID=39707657
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| TW096106090A TWI334571B (en) | 2007-02-16 | 2007-02-16 | Program instruction rearrangement methods |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US8082421B2 (zh) |
| TW (1) | TWI334571B (zh) |
Families Citing this family (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8335912B2 (en) * | 2009-04-22 | 2012-12-18 | Oracle America, Inc. | Logical map table for detecting dependency conditions between instructions having varying width operand values |
| US8504805B2 (en) * | 2009-04-22 | 2013-08-06 | Oracle America, Inc. | Processor operating mode for mitigating dependency conditions between instructions having different operand sizes |
| US20100274961A1 (en) * | 2009-04-22 | 2010-10-28 | Golla Robert T | Physically-indexed logical map table |
| US8458444B2 (en) | 2009-04-22 | 2013-06-04 | Oracle America, Inc. | Apparatus and method for handling dependency conditions between floating-point instructions |
| US9052890B2 (en) * | 2010-09-25 | 2015-06-09 | Intel Corporation | Execute at commit state update instructions, apparatus, methods, and systems |
| HK1165184A2 (zh) * | 2011-08-10 | 2012-09-28 | Easy Printing Network Limited | 一种使用图像恢复相关信息的方法 |
| LU101480B1 (en) * | 2019-11-18 | 2021-05-18 | Luxembourg Inst Science & Tech List | Data preprocessing for a supervised machine learning process |
| US11593251B2 (en) * | 2021-03-03 | 2023-02-28 | Oracle International Corporation | Techniques for large-scale functional testing in cloud-computing environments |
Family Cites Families (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6138230A (en) | 1993-10-18 | 2000-10-24 | Via-Cyrix, Inc. | Processor with multiple execution pipelines using pipe stage state information to control independent movement of instructions between pipe stages of an execution pipeline |
| US5812810A (en) * | 1994-07-01 | 1998-09-22 | Digital Equipment Corporation | Instruction coding to support parallel execution of programs |
| JP3113792B2 (ja) * | 1995-04-27 | 2000-12-04 | 松下電器産業株式会社 | 最適化装置 |
| US5867644A (en) * | 1996-09-10 | 1999-02-02 | Hewlett Packard Company | System and method for on-chip debug support and performance monitoring in a microprocessor |
| US6260190B1 (en) * | 1998-08-11 | 2001-07-10 | Hewlett-Packard Company | Unified compiler framework for control and data speculation with recovery code |
| SE0102564D0 (sv) * | 2001-07-19 | 2001-07-19 | Ericsson Telefon Ab L M | Arrangement and method in computor system |
| JP3896087B2 (ja) * | 2003-01-28 | 2007-03-22 | 松下電器産業株式会社 | コンパイラ装置およびコンパイル方法 |
| US7571302B1 (en) * | 2004-02-04 | 2009-08-04 | Lei Chen | Dynamic data dependence tracking and its application to branch prediction |
| US20060206732A1 (en) | 2005-03-14 | 2006-09-14 | Sony Computer Entertainment Inc. | Methods and apparatus for improving processing performance using instruction dependency check depth |
-
2007
- 2007-02-16 TW TW096106090A patent/TWI334571B/zh active
- 2007-09-04 US US11/849,485 patent/US8082421B2/en active Active
Also Published As
| Publication number | Publication date |
|---|---|
| US8082421B2 (en) | 2011-12-20 |
| TW200836099A (en) | 2008-09-01 |
| US20080201556A1 (en) | 2008-08-21 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| TWI334571B (en) | Program instruction rearrangement methods | |
| JP4886918B1 (ja) | フラッシュコピー・プロセスを処理する方法、ならびにそのためのシステム、およびコンピュータ・プログラム | |
| JP6629678B2 (ja) | 機械学習装置 | |
| RU2544751C2 (ru) | Компьютерная система с визуальным буфером обмена | |
| CN106020778A (zh) | 还原寄存器重命名映射 | |
| CN107403141A (zh) | 人脸检测方法及装置、计算机可读存储介质、设备 | |
| US20120172098A1 (en) | Suggesting game roles for different players based on a player's gaming statistics from other games | |
| TW200813820A (en) | Method and apparatus for back to back issue of dependent instructions in an out of order issue queue | |
| Spinellis et al. | Beautiful architecture: leading thinkers reveal the hidden beauty in software design | |
| CN109376152A (zh) | 大数据系统文件数据准备方法和系统 | |
| CN104583999B (zh) | 数据迁移管理 | |
| Zakhary et al. | Db-risk: The game of global database placement | |
| WO2018078735A1 (ja) | 情報処理装置、情報処理方法および情報処理プログラム | |
| CN100451953C (zh) | 程序指令调整方法 | |
| CN110019201A (zh) | 一种生成结构化数据的方法、装置及系统 | |
| CN111522586A (zh) | 信息处理装置、非暂态计算机可读介质和信息处理方法 | |
| Guan et al. | Ground-state shape evolution in Er and Yb isotopes | |
| CN116361486B (zh) | 镜像蛋白质相互作用图谱的构建方法及相关设备 | |
| Liu et al. | Zigzagattention: Efficient long-context inference with exclusive retrieval and streaming heads | |
| Vandevoort | Optimizing Concurrency Control: Robustness Against Read Committed Revisited | |
| CN115758366B (zh) | 病毒扫描进度的计算方法、装置、电子设备及存储介质 | |
| Pan et al. | DNA sequence splicing algorithm based on Spark | |
| CN105302495B (zh) | 数据存储方法及装置 | |
| CN118784937B (zh) | 快速分片续传超大图片的方法、系统、装置及存储介质 | |
| US20220269681A1 (en) | Computer-readable recording medium storing data specifying program, device, and method |