程序轉換裝置及程序轉換方法

2023-06-20 17:31:11 2

專利名稱：程序轉換裝置及程序轉換方法
技術領域：
本發明涉及程序轉換裝置，尤其是涉及具備指令系統(instruction set)的面向處理器的程序轉換裝置，其中該指令系統包含在運行時等待來自外部的指定應答的指令。
背景技術：
近幾年來，處理器的處理速度急劇提高，然而與其相比，主存儲器的存取速度的提高幅度很小，兩者的速度差逐年增大。為此，在信息處理裝置的高速處理中，存儲器存取成為瓶頸的問題早已被指出。
為了解決這個問題，根據存儲分層的考慮方法，使用了高速緩存機構。在高速緩存機構中，把處理器中必須的數據從主存儲器事先傳輸(預取)到高速的高速緩存中。由此，可以高速應對來自處理器的存儲器存取。
然而，處理器存取高速緩存上並不存在的數據時，就會產生高速緩存失誤。由此，產生了從主存儲器向高速緩存傳輸數據耗費時間的問題。
用戶意識不到高速緩存進行編程，如果運行這個程序，可以設想到會頻繁產生這種高速緩存失誤。結果，高速緩存失誤引起的損失很大程度地惡化了處理器的性能。為此，編譯器有必要進行考慮了高速緩存的最佳化。
作為高速緩存最佳化技術之一，可以例舉預取指令的插入被提出來。預取指令指的是，在參照某存儲器地址之前，把這個地址的數據，提前從主存儲器傳輸到高速緩存上。在預取指令的插入的最佳化中，在開始參照該存儲器地址的稍微提前一點的周期裡，插入預取指令。
例如，對於如圖1(a)所示的循環處理，如圖1(b)所示，考慮數據被參照之前的等待(latency)時間，把預取指令(dpref)插入循環內，以便預取在多個迭代前被參照的數據。另外，在這裡設int型的數組a的要素是4位元組，高速緩存的行大小(line size)為128位元組。
但是，圖1(b)所示的代碼中，對於1個迭代分別進行了數組a的參照和預取，參照只能以每4位元組進行，與此相對，預取則以1行(128位元組)單位進行。
因此，1次的預取可以對應32次的參照，剩餘31次成了進行無用的預取的狀態。也就是說，連續發出了相同行的預取指令。
而且，通過處理器，在dpref指令的數據傳輸中，如果要運行下一個dpref指令，儘管按照前面的dpref指令的主存儲器向高速緩存的數據傳輸沒有結束，也會發出下一個dpref指令，儘管本來是為了消除互鎖插入了dpref指令，還是會引起互鎖。
因此，如上所述，如果循環的1個迭代短，2個dpref指令的間隔短，則按照dpref指令的主存儲器到高速緩存的數據傳輸所消耗的時間(等待時間)變得顯著，反而惡化了性能。
而且，即使是在dpref指令的運行狀態以外，如存儲器存取指令等，即使是指令發出後發生任何的應答等待的指令的情況，也可能引起互鎖。

發明內容
本發明，正是為了解決上述課題而做出的，其目的在於，提供一種不再無用地發出有可能引起互鎖的指令，可以提高程序運行時處理速度的程序轉換裝置及程序轉換方法。
而且，本發明的目的在於，提供一種程序轉換裝置及程序轉換方法，，不再無用得發出在指令發出後發生某種應答等待的指令，可以提高程序運行時處理速度。
而且，本發明的目的是提供一種程序運行時不會引起互鎖的程序轉換裝置及程序轉換方法。
為了達到上述目的，本發明涉及的程序轉換裝置，是一種面向處理器的程序轉換裝置，該處理器具備包含運行時等待來自外部的指定應答的指令的指令系統，其特徵在於，具備進行雙重循環的循環結構轉換裝置，其中雙重循環轉換是把包含於輸入程序中的反覆次數是x次的循環轉換為反覆次數是y次的循環作為內循環，反覆次數是x/y次的循環作為外循環的嵌套結構；指令配置裝置，在上述內循環的外部位置配置上述指令，由此轉換為包含該指令的輸出程序。
由此，例如如圖2所示，把圖1(a)所示的循環處理雙重循環化，並且可以在最內循環的外側插入預取指令。由此，消除了沒用的預取運行。由此提高了處理速度。而且，從一個dpref指令運行後到下一個dpref指令運行之前的期間，可以隱蔽從主存儲器到高速緩存傳輸數據耗費的等待時間，難以發生互鎖。
也就是說，依據本發明，由於循環的雙重化，如果在內循環的外側運行有可能引起互鎖的指令，可以不用多餘發出相應指令就可以提高程序運行時的處理速度。
而且，由於循環的雙重化，可以保證發出有可能引起互鎖的指令之後到下一個有可能引起互鎖的指令為止的期間的周期數。為此，程序運行時很難引起互鎖。
另外，程序轉換裝置，可以作為編譯器、OS(Operating System)或者CPU等的集成電路來實現。
應答等待指令包括如上述的dpref指令那樣可能引起互鎖的指令和指令運行時等待來自外部的指定應答的指令，另外還有等待應答的情況和不等待應答情況的指令。
而且，本發明，不僅能作為具備這種特徵裝置的程序轉換裝置來實現，還可以由把程序轉換裝置所具備的特徵裝置作為步驟的程序轉換方法來實現，作為程序轉換裝置也可以由賦予計算機功能的程序來實現。而且，這種程序，可以通過CD-ROM(Compact Disc-Read OnlyMemory光碟只讀存儲器)等記錄媒介和網際網路等傳輸媒介流通是不言而喻的。
發明效果依據本發明，可以提高程序運行時的處理速度。
而且，程序運行時不易引起互鎖問題。


圖1是說明過去最佳化技術的問題點的圖；圖2是說明依據本發明的循環處理的結構轉換的圖；圖3是表示有關本實施例的編譯器系統組成的圖；圖4是表示編譯器組成的圖；圖5是編譯器所運行的處理的流程圖；圖6是說明循環結構轉換處理的具體內容的圖；圖7是表示複製型內循環分割處理的具體內容的流程圖；圖8是表示條件型內循環分割處理的具體內容的流程圖；圖9是表示預取指令配置處理的具體內容的流程圖；圖10是表示預取指令插入處理的具體內容的流程圖；圖11是說明不需要剝離時的單循環分割處理的圖；圖12是表示不需要剝離時的源程序的一個例圖；圖13是表示對應圖12所示的源程序的中間語言程序的圖；圖14表示的是把圖13所示的中間語言的程序結構轉換為雙重循環之後的中間語言程序的圖；圖15表示的是對圖14所示的中間語言程序插入預取指令之後的中間語言程序的圖；圖16是用來說明需要剝離時的單循環分割處理的圖；圖17是用來說明循環內存在多個數組存取時的循環分割處理的圖；圖18是用來說明循環內存在多個數組存取時的循環分割處理的圖；圖19是用來說明循環內存在多個數組存取，且數組要素的大小全部不同時的循環分割處理的圖；圖20是用來說明循環內存在多個數組存取，且數組要素的大小全部不同時的循環分割處理的圖；圖21是說明循環內存在跨距不同的多個數組存取時的循環分割處理的圖；圖22是說明循環次數不確定的循環處理的循環分割處理的圖；圖23是說明循環次數不確定的循環處理的循環分割處理的圖；圖24是說明不需要循環分割的最佳化處理的圖；圖25是說明在循環內存取的要素在主存儲器上沒有適當排序(align)時的循環分割處理的圖；圖26是說明在循環內存取的要素在主存儲器上沒有適當排序時的循環分割處理的圖；圖27是說明動態確定沒有排序的數組要素，且對循環處理進行最佳化處理的圖；圖28是說明沒有排序的數組要素的圖；圖29是說明使用剖面信息確定沒有排序的數組要素，且對循環處理進行最佳化處理的圖；圖30是說明對最內循環以外的循環進行結構轉換的圖；
圖31是說明由編譯指示(pragma)#pragma_loop_tiling_dpref變量名[，變量名]確定變量情況下的最佳化處理的圖；圖32是說明插入PreTouch指令時不需要剝離情況下的單循環分割處理的圖；圖33是說明插入PreTouch指令時需要剝離情況下的單循環分割處理的圖；圖34是說明動態確定沒有排序的數組要素，且對循環處理進行最佳化處理的圖。
標號說明141源程序142高速緩存參數143彙編文件144目標文件145運行程序146運行登錄數據147剖面(profile)數據148編譯系統149編譯器150彙編程序151連接程序
152模擬器153剖析工具181最佳化輔助信息182語法解析部183最佳化信息解析部184普通最佳化部185指令編排部186循環結構轉換部187指令最佳配置部188代碼輸出部實施發明的最佳實施例系統組成圖3是表示有關本實施例的編譯系統組成的圖。編譯系統148是把以C語言等高級語言記述的源程序141轉換為機器語言的運行程序145的軟體系統，包括編譯器149、彙編程序150和連接程序151。
編譯器149，把具備高速緩存的計算機的CPU(CentralProcessing Unit)作為目標處理器，是把源程序141轉換為以彙編語言記述的彙編程序143的程序。編譯器149，在把源程序141轉換為彙編程序文件143之際，根據與高速緩存的行大小和等待周期等信息有關的高速緩存參數142和下述的剖面數據147，進行最佳化處理，並輸出彙編程序文件143。
彙編程序150是把以彙編語言記述的彙編程序文件143轉換為以機器語言記述的目標文件144的程序。連接程序151是結合多個目標文件144，並生成運行程序145的程序。
作為運行程序145的開發工具，準備了模擬器152及剖析工具153。模擬器152是模擬運行程序145，輸出運行時的各種運行登錄數據146的程序。剖析工具153，是解析運行登錄數據146，輸出解析了程序的運行順序等的剖面數據147的程序。
編譯器組成圖4是表示編譯器組成的圖。編譯器149包括語法解析部182、最佳化信息解析部183、普通最佳化部184、指令編排部185、循環結構轉換部186、指令最佳配置部187、代碼輸出部188。各組成處理部作為程序來實現。
語法解析部182是把源程序141作為輸入接收，並在進行語法解析處理之後輸出中間語言程序的處理部。
最佳化信息解析部183是讀入高速緩存參數142、剖面數據147、編譯程序選項及編譯指示(pragma)等中間語言的最佳化處理必須的信息，並進行解析的處理部。普通最佳化部184，是對中間代碼實施普通的最佳化處理的處理部。指令編排部185是使指令排列最佳化、進行指令編排的處理部。編譯程序選項及編譯指示(pragma)都是針對編譯器的指示。
循環結構轉換部186，是把單層循環轉換為雙重循環的處理部。指令最佳配置部187，是在轉換的雙重循環內配置預取指令的處理部。代碼輸出部188，是把最佳化後的中間語言規格的程序轉換為以彙編語言記述的程序並輸出彙編程序文件143的處理部。
處理流程下面，說明編譯器149所運行的處理的流程。圖5是編譯器149所運行的處理的流程圖。
語法解析部182，進行源程序141的語法解析，生成中間代碼(S1)。最佳化信息解析部183，解析高速緩存參數142、剖面數據147、編譯程序選項及編譯指示等(S2)。普通最佳化部184，根據最佳化解析部183中的解析結果，進行普通的中間代碼的最佳化(S3)。指令編排部185，進行指令的編排(S4)。循環結構轉換部186，著眼於包含在中間代碼的循環結構，如果需要就把單層循環轉換為雙重循環結構(S5)。指令最佳配置部187，把預取循環結構內被參照的數據的指令插入中間代碼(S6)。代碼輸出部188，把中間代碼轉換為彙編代碼，作為彙編程序文件143進行輸出(S7)。
語法解析處理(S1)、最佳化信息解析處理(S2)、普通的最佳化處理(S3)、指令編排處理(S4)及彙編代碼輸出處理(S7)和普通的處理一樣，因此其詳細說明在這裡不再重複。
下面，對循環結構轉換處理(S5)及預取指令配置處理(S6)進行詳細說明。
圖6是用來說明循環結構轉換處理(圖5的S6)的具體內容的圖。循環結構轉換部186，判斷循環次數是被立即給予而可以算出，或者是以其它變量給予且不能算出(S11)。也就是說判斷循環次數是固定的還是不確定的。
如果是循環次數不確定的情況(在S11中是NO)，依據編譯指示或者編譯程序選項判斷有無最低循環次數的指定，或者程序運行時動態判定循環次數，來判斷有無分割循環的指定(S12)。
如果有任何一種指定(S12中是YES)，或者循環次數是固定值的情況(S11中是YES)，調查循環內所參照的數組的下標是否可以解析(S13)。也就是說，如果循環計數是具有某種規律而在變化的情況，就判斷為可以解析。例如，如果循環計數的值在迭代內可以置換，則判斷為不可以解析。
下標如果是可以解析的情況(S13中是YES)，對在循環處理內被參照的各數組求出在1個迭代中參照的要素字節數，導出其中最小的值LB(S14)。
然後，判斷高速緩存的行大小CS除以值LB的值是否大於1(S15)。如果CS/LB的值比1大時(S15中是YES)，調查循環處理的數組是否被排序(align)(S16)。數組是否被排序的判斷，根據是否有依據編譯指示或編譯程序選項等被排序這樣的指示來進行判斷。
數組沒有被排序時(S17中是NO)，進行LB*LC/IC是否比CS大的判斷(S16)。這裡，LC表示等待時間的周期數，IC表示每1個迭代的周期數。LC/IC，表示循環分割為多個最內循環情況下的各循環的循環次數，LB*LC/IC表示各循環中的存取容量。
如果LB*LC/IC大於行大小CS時(S16中是YES)，在分割後的各循環處理中參照1個行大小以上的要素。為此，以分割因子為周期，根據式(1)導出把各循環處理進行雙重循環時的最內循環的循環次數DT(S18)。
DT＝(LC-1)/IC+1…(1)如果LB*LC/IC是行大小CS之下的情況(S16中是NO)或者數組被排序的情況(S17中是YES)，以分割因子為大小，根據式(2)導出把各循環處理進行雙重循環時的最內循環的循環次數DT(S19)。
DT＝(CS-1)/LB+1…(2)在導出最內循環的循環次數DT的處理之後(S18或者S19)，判斷最內循環的循環次數DT是否比1大(S20)。DT如果是1(S20中是NO)的情況，由於最內循環的循環次數DT是1次，因此沒有必要把循環轉換為雙重循環。為此，結束循環結構轉換處理(S5)。
如果最內循環的循環次數DT是2以上的情況(S20中是YES)，就做成循環結構轉換為雙重循環時的外循環結構(S21)。生成外循環結構時，判斷是否需要剝離處理(S22)。下面敘述剝離處理及是否需要剝離處理的判斷方法。
如果是需要剝離處理的情況(S22中是NO)，就進行剝離處理，生成剝離代碼(S24)。之後，調查是否有依據編譯程序選項-O或者-Os的指定(S25)。這裡，編譯程序選項-O，是為把程序大小及運行處理速度同平均的彙編代碼輸出給編譯器的指示。編譯程序選項-Os，是為把重視抑制程序大小的彙編代碼輸出給編譯器的指示。
不需要剝離處理(S22中是YES)或者沒有編譯程序選項-O或者-Os的指定的情況(S25中是NO)，生成內循環(最內循環)的循環次數的條件式(S23)。
有編譯程序選項-O或者-Os的指定的情況(S25中是YES)，把剝離的循環處理疊入雙重循環，生成最內循環的循環次數的條件式(S26)。
在最內循環的循環次數條件生成處理(S23、S26)之後，調查最內循環中所參照的對象數組是否是1個(S27)。如果最內循環中所參照的對象數組是1個的情況(S27中是YES)，結束循環結構轉換處理(S5)。
如果最內循環中所參照的對象數組具有2個以上時(S27是NO)，導出最內循環的分割個數，決定分割後的各最內循環的循環次數的比率(S28)。之後，判斷分割後的最內循環次數DT除以分割個數的值是否比1大(S29)。也就是說，該值在1以下時(S29中是NO)，由於分割後的各循環次數是1次以下，因此沒有分割的意義。為此，結束循環結構轉換處理(S5)。
如果該值比1大(S29中是YES)，分割後的各循環次數是2次以上。這種情況下，調查是否有依據編譯程序選項-O或者-Ot的指定(S30)。編譯程序選項-Ot是把重視提高運行處理速度的彙編代碼輸出給編譯器的指示。
如果有依據編譯程序選項-O或者-Os的指定(S30中是YES)，運行下述的重視運行處理速度的複製型內循環分割處理(S31)，結束循環結構轉換處理(S5)。
如果沒有依據編譯程序選項-O或者-Os的指定(S30中是NO)，運行下述的重視抑制程序大小的條件型內循環分割處理(S32)，結束循環結構轉換處理(S5)。
圖7是表示複製型內循環分割處理(圖6的S31)的具體內容的流程圖。
把最內循環的循環次數DT除以分割個數的值作為細化分割後的內循環次數(S41)。然後，只複製分割個數份的內循環，並生成內循環(S42)。之後，把細化分割後的各內循環次數修正為細化分割後的內循環次數(S43)。而且，把DT除以分割個數的剩餘加在細化分割後的開頭循環的循環次數上(S44)，結束複製型內循環分割處理。
圖8是表示條件型內循環分割處理(圖6的S32)的具體內容的流程圖。
把最內循環的循環次數DT除以分割個數的值設為細化分割後的內循環次數(S51)。然後，生成內循環次數條件的切換switch表(S52)。也就是說，生成用C語言表述的switch語句，以便依次交替內循環次數。另外，也可以是if語句。
表生成之後，把細化分割後的各內循環次數條件修正為細化分割後的內循環次數(S53)。之後，把DT除以分割個數的剩餘加在細化分割後的開頭循環的次數條件上(S54)，結束條件型內循環分割處理。
圖9是表示預取指令配置處理(圖5的S6)的具體內容的流程圖。
預取指令配置處理中，對於所有的循環反覆以下處理(循環A)。首先，調查所關注的循環是否是指令插入對象的循環(S61)。有關是否是指令插入對象的循環的信息，根據循環結構轉換部186的解析結果取得。
如果是指令插入對象的循環(S61中是YES)，對這個循環調查是否進行了條件型循環分割(S62)。如果進行了條件型循環分割，解析各條件語句中的指令插入位置(S63)，插入預取指令(S64)。如果對指令插入對象的循環沒有進行條件型循環分割(S62中是NO)，對這個循環調查是否進行了複製型循環分割(S65)。如果進行了複製型循環分割(S65中是YES)，解析這個循環的前一個指令插入位置(S66)。之後，插入預取指令(S67)。如果是被剝離的循環的情況(S68中是YES)，解析指令插入位置以便在該循環前面插入指令(S69)，在這個位置插入預取指令(S70)。
圖10是表示預取指令插入處理(圖9的S64、S67及S70)的具體內容的流程圖。
指令插入處理中，直到插入指令、插入位置、插入地址等組成的信息清單全為空為止反覆以下處理(循環B)。
判斷要插入預取指令的數組要素是否排序完畢(S72)。如果沒有排序(S72中是NO)，調查是根據周期因子分割的循環還是根據大小因子分割的循環(S73)。
如果排序完畢(S72中是YES)或者是以周期因子分割的循環(S73中是YES)，對1行前的數據插入預取指令(S74)。沒有排序，且是以大小因子分割的循環(S73中是NO)，對2行前的數據插入預取指令(S75)。最後，從信息清單刪除解析完畢的信息(S76)。
編譯程序選項編譯系統148中，作為針對編譯器的編譯程序選項，準備了選項-fno-loop-tiling-dpref。如果指定了這個選項，和編譯指示的指定無關，不進行針對循環的結構轉換。如果沒有指定本選項，結構轉換的實施遵從有無編譯指示的指定。
編譯指示指定本指定針對隨後的循環。
由編譯指示#pragma_loop_tiling_dpref變量名[，變量名]指定了變量時，僅著眼於編譯指示指定的變量進行循環分割。指定的變量可以是數組也可以是指針。
由編譯指示#pragma_loop_tiling_dpref_all指定了循環時，著眼於循環內參照的所有數組進行結構轉換。
下面，說明幾個具體曲面中的循環分割處理。另外，在後面的處理中，為了簡化說明，進行依據C語言的程序記述，但實際上依據中間語言進行最佳化處理。
單循環分割圖11是用於說明不需要剝離情況下的單循環分割處理的圖。
考慮輸入了如圖11(a)所示的源程序282的情況。這個源程序282中，依次參照數組A的要素，加在變量sum上。這裡，數組A的各要素大小設為4位元組，高速緩存的1個行大小設為128位元組(在以後的說明中，高速緩存的行大小也設為128位元組)。也就是說，高速緩存的1行上存儲32個數組A的要素。又，包含於源程序282的循環的迭代次數128次，是32的整數倍。由此，源程序282，如圖11(b)的程序284所示，可以結構轉換為雙重循環。也就是說，在最內循環中，進行32次的反覆處理，在其外的循環中，進行反覆4次最內循環的循環處理。在最內循環處理中，參照高速緩存1行的數據。之後，如圖11(c)的程序286所示，在運行最內循環之前，插入預取指令(dpref(A[i+32])。通過插入預取指令，運行最內循環時，形成了該循環中所參照的數組A的要素搭乘高速緩存的狀態。
圖12～圖15，是說明有關不需要剝離的單循環分割處理中的中間語言推移的圖。
圖12，和圖11(a)一樣，是表示不需要剝離時的一個源程序的例圖。圖13是對應圖12所示的源程序240的中間語言的程序。BGNBBLK和ENDBBLK之間的指令列對應1個基本程序段，始於BGNBBLKB1的基本程序段表示for循環之前的處理，始於BGNBBLKB2的基本程序段表示for循環，始於BGNBBLKB3的基本程序段表示for循環後的處理。
圖14表示的是把圖13所示的中間語言的程序結構轉換為雙重循環之後的中間語言的程序。始於BGNBBLKB2的基本程序段對應最內循環，始於BGNBBLKB4及BGNBBLKB5的循環對應外循環。
圖15表示的是對圖14所示的中間語言程序插入預取指令之後的中間語言的程序。程序270中，在始於BGNBBLKB4的基本程序段的內部重新插入了預取指令(dpref)。
圖16是用來說明需要剝離時的單循環分割處理的圖。
考慮輸入了圖16(a)所示的源程序292的情況。在這個源程序292中，依次參照數組A的要素，加在變量sum上。這裡，數組A的各要素大小設為4位元組。也就是說，高速緩存的1行上存儲了32個數組A的要素。而且，包含於源程序292的循環迭代次數設為140次。也就是說，是除以1行存儲的數組A的要素數32時所得到的餘數。
這種情況下，如圖16(b)所示的程序294，剝離140除以32的餘數的循環次數，其它部分和圖11(b)一樣結構轉換為雙重循環結構。之後，進行為了把被剝離的部分包含於雙重循環結構的剝離疊入處理，可以得到圖16(c)所示的程序296。也就是說，通常狀態下，在最內循環進行32次的反覆處理，最後運行最內循環時，進行殘餘的12(＝140-128)次反覆處理。之後，如圖16(d)的程序298所示，在運行最內循環之前，插入預取指令(dpref(A[i+32]))。
存在多個數組存取的情況(不需要剝離)圖17是用於說明循環內存在多個數組存取的情況下的循環分割處理的圖。
考慮輸入了如圖17(a)所示的源程序301的情況。這個源程序301中，依次參照數組A及數組B的要素，相應要素之間的乘積加在變量sum上。這裡，數組A及數組B的各要素分別設為4位元組。也就是說，高速緩存的1行上存儲32個數組A的要素。或者，存儲32個數組B的要素。也就是說，1行所存儲的要素數，在數組A和數組B是一樣的。而且，源程序301所包含的循環的迭代次數128次是32的整數倍。由此，源程序301，如圖17(b)的程序302所示，不需要剝離就可以結構轉換為雙重循環。
存在多個數組存取情況下的雙重循環結構有兩種，一種是稱作複製型的提高運行處理速度的最佳化結構，另一種是稱作條件型的減小程序大小的最佳化結構。
首先，說明複製型的最佳化結構。用數組A和數組B之間的要素大小比分割程序302中包含的最內循環的循環次數。這裡，數組A和數組B要素的大小相同。因此，如圖17(c)所示的程序303，把最內循環分為2等分，分割為2個循環次數是16次的最內循環。其次，如圖17(d)的程序304所示，在各最內循環的前面插入預取指令。在開頭的最內循環前面，插入預取指令(dpref(A[i+32]))用來預取1行的數組A的要素，在第2個最內循環的前面，插入預取指令(dpref(B[i+32]))用來預取1行的數組B的要素。
這樣，在預取指令之間插入循環處理，由此對不同數組的預取指令不會連續，可以隱蔽運行預取指令引起的等待時間。由此，可以提高運行處理速度。
下面，說明條件型的最佳化結構。條件型的情況也與複製型的情況一樣，以數組A和數組B之間的要素大小比來分割最內循環的循環次數。只是，不是如程序303那樣排列2個最內循環，而是如圖17(e)所示的程序305，最內循環的個數是1個，把這個循環次數作為條件分支。也就是說，以變量K＝1的情況和K＝0的情況改變最內循環的循環次數N。只是，這個例子中，和變量K的值無關，最內循環的次數是16次。然後，如圖17(f)所示的程序306，插入條件分支式及預取指令以便在K＝1的情況下預取1行的數組A的要素，K＝0的情況下則預取1行的數組B的要素。另外，這裡由於最佳化，循環次數N立即置換為16。
這樣，最內循環的個數為1個，由條件分支式改變最內循環的循環次數及預取指令，由此可以減小最終生成的機器語言指令的程序大小。只是，由於有條件分支處理，和複製型比起來處理速度多少會遲緩一些。
存在多個數組存取的情況(需要剝離)圖18是用於說明循環內存在多個數組存取的情況下的循環分割處理的圖。
考慮輸入了圖18(a)所示的源程序311的情況。這個源程序311中，依次參照數組A及數組B，相應要素之間的乘積加在變量sum上。這裡，設數組A及數組B的各要素分別為4位元組。也就是說，高速緩存的1行上存儲32個數組A的要素。或者存儲32個數組B的要素。也就是說，1行所存儲的要素數，在數組A和數組B是一樣的。而且，設源程序311中包含的循環的迭代次數是140次。
因此，把源程序311結構轉換為雙重循環時，和圖16(b)所示的程序294一樣，生成圖18(b)所示的剝離處理了的程序312。
進行複製型的最佳化時，以數組A和數組B之間的要素大小比分割最內循環。這樣，生成圖18(c)所示的程序313。然後，如圖18(d)的程序314所示，在開頭的最內循環前面，插入預取指令(dpref(A[i+32]))用來預取1行的數組A的要素，在第2個最內循環的前面，插入預取指令(dpref(B[i+32]))用來預取1行的數組B的要素。另外，在剝離處理了的最終循環前面不插入預取指令。這是因為，由於運行其前面的雙重循環處理中的預取指令，所希望的數據被高速緩存預取。
在進行條件型的最佳化時，對程序312進行剝離疊入處理，得到圖18(e)所示的程序315。剝離疊入處理和參照圖16進行說明的一樣。然後，以數組A和數組B之間的要素大小比分割最內循環的循環次數，製作圖18(f)所示的程序316以便可以條件分支該循環次數。在程序316中，交替變更變量K的值，改變循環計數N的值以便對應變量K的值。然後如圖18(g)的程序317所示，隨著K值的變化，在條件分支式中插入預取指令以便交互預取每1行的數組A及數組B的要素。
這樣，即使是需要剝離的情況，在複製型的情況，把剝離部分設為區分於雙重循環的循環，條件型的情況，由條件分支式改變剝離情況下的循環計數次數，由此即使在循環內有多個數組存取，且需要剝離的情況，也可以進行考慮了預取引起的等待時間的最佳化。
存在大小不同的多個數組存取的情況(不需要剝離)圖19是說明當循環內存在多個數組存取且數組要素大小完全不同情況下的循環分割處理的圖。
考慮輸入圖19(a)所示的源程序321的情況。這裡，設數組A的要素是4位元組，數組B的要素是2位元組。也就是說，高速緩存的1行上存儲了32個數組A的要素，存儲了64個數組B的要素。
這種情況下，關注要素大小小的數組B，進行對應數組B的要素的循環結構轉換。也就是說，如圖19(b)的程序322所示，把最內循環的循環次數設為1行收納的數組B的要素數64，結構轉換為雙重循環。在最內循環中，對於數組B消耗了1行的要素，對於數組A消耗了2行的要素。由此，為了運行最內循環處理就需要3行的數據。
為此，進行複製型的最佳化之際，如圖19(c)的程序323所示，把最內循環分割為3個，如圖19(d)的程序324所示，在各最內循環前面插入預取指令。這裡，在第1個最內循環前面，插入預取2行前的數組A的要素的預取指令(dpref(A[i+64]))，在第2個最內循環前面插入預取3行前的數組A的要素的預取指令(dpref(A[i+96]))，在第3個最內循環的前面插入預取1行前的數組B的要素的預取指令(dpref(B[i+64]))。而且，3個最內循環的循環次數按照處理順序分別設為22、21及21。這是因為，最外循環的條件分支判斷在運行第3個最內循環後進行，所以由減少第3個最內循環的循環次數，來提高整體的處理速度。
而且，進行條件型的最佳化時，如圖19(e)的程序325所示，1次最內循環處理中，在0到2之間的範圍內更新變量K的值，根據依據變量K值的條件分支處理，把最內循環的循環次數N設為22、21及21中的任一值。之後，運行循環次數N的最內循環。然後，如圖19(f)的程序326所示，進行最佳化，當變量K的值是0時運行預取指令(dpref(A[i+64]))，當變量K的值是1時運行預取指令(dpref(A[i+96]))，當變量K的值是2時運行預取指令(dpref(B[i+64]))的。
存在大小不同的多個數組存取的情況(需要剝離)圖20是說明當循環內存在多個數組存取且數組要素大小完全不同的情況下的循環分割處理的圖。
如圖20(a)所示的源程序331，和圖19(a)所示的源程序321相比僅僅是循環次數不同。因此，和源程序321一樣，數組A的要素是4位元組，數組B的要素是2位元組。如圖20(b)所示，把源程序321的循環結構轉換為雙重循環，對循環次數140除以數組B的1行的要素數64的剩餘進行剝離處理，就可以得到程序322。進行複製型的最佳化處理時，如參照圖19(c)及圖19(d)所說明的那樣，把雙重循環的最內循環分割為3個，並插入預取指令，由此得到圖20(c)所示的程序333。進行條件型的最佳化處理時，如參照圖19(e)及圖19(f)所說明的那樣，由條件分支式控制循環次數及預取指令，最終得到如圖20(e)所示的程序335。
存在跨距不同的多個數組存取的情況圖21是說明循環內存在跨距不同的多個數組存取的情況下的循環分割處理的圖。
跨距指的是循環處理中的數組要素的增量值(存取幅度)。考慮輸入了圖21(a)所示的源程序341的情況。這裡，設數組A的要素及數組B的要素都是4位元組。在源程序341中，循環的每次迭代中，數組A的要素增加1個，而數組B的要素增加2個。也就是說，數組B的存取幅度是數組A的存取幅度的2倍。如果著眼於最小存取幅度的數組A，1行收納32個數組A的要素。由此，如果向最內循環的循環次數設為32次的雙重循環進行結構轉換，就可以得到圖21(b)所示的程序342。在最內循環中，數組A消耗1行的要素，數組B就消耗2行程度的要素。由此，為了運行最內循環處理，就需要合計3行的數據。
因此，進行複製型的最佳化時，如圖21(c)的程序343所示，把最內循環分割為3個，如圖21(d)的程序344所示，在各最內循環前面插入預取指令。這裡，在第1個最內循環前面，插入預取1行前的數組A的要素的預取指令(dpref(A[i+32]))，在第2個最內循環前面插入預取2行前的數組B的要素的預取指令(dpref(B[i*2+64]))，在第3個最內循環的前面插入預取3行前的數組B的要素的預取指令(dpref(B[i*2+96]))。
又，進行條件型的最佳化時，如圖21(e)的程序345所示，1次的最內循環處理中，在0到2之間的範圍內更新變量K的值，根據依據變量K值的條件分支處理，把最內循環的循環次數N設為11、11及10中的任一值。之後，運行循環次數N的最內循環。然後，如圖21(f)的程序346所示，進行最佳化，當變量K的值是0時運行預取指令(dpref(A[i+32]))，當變量K的值是1時運行預取指令(dpref(B[i*2+64]))，當變量K的值是2時運行預取指令(dpref(B[i*2+96]))。
循環次數不定的情況圖22是說明循環次數不定的循環處理的循環分割處理的圖。
考慮輸入了圖22(a)所示的源程序351的情況。包含於源程序351的循環次數，由變量Val確定，編譯時不確定。但是，進行最低128次反覆處理通過編譯指示指定#pragma_min_iteration＝128來保證。這裡，設數組A為4位元組。也就是說，高速緩存的1行上存儲32個數組A的要素。
根據編譯指示指定，把循環分割為開始的128次的循環處理和其後的由變量Val確定的循環次數的循環處理，和單循環的情況一樣把他們分別進行雙重循環化，就可以得到圖22(b)所示的程序352。
進行複製型的最佳化處理時，在程序352的最內循環的前面插入預取指令(dpref(A[i+32]))用來預取1行前的數組A的要素，由此得到圖22(c)所示的程序353。
進行條件型的最佳化處理時，對後半部分的循環處理疊入剝離，最外循環次數達到128次之前，最內循環的次數設為32次，其後插入最內循環的次數設定為(Val-128)次的分支指令。這樣，可以得到圖22(d)所示的程序354。
最後，在運行最內循環之前，插入預取指令(dpref(A[i+32]))，由此得到圖22(e)所示的程序355。
圖23是說明循環次數不定的循環處理的循環分割處理的圖。
考慮輸入了圖23(a)所示的源程序361的情況。包含於源程序361的循環次數由變量N確定，在編譯時不定。而且，源程序361和源程序351不同，沒有表示最低循環次數的編譯指示指定。
對循環次數小的循環處理進行循環的結構轉換，即使進行了最佳化也難以顯現最佳化的效果。由此，這種情況下，為了提高最佳化的效果，如果循環次數大於某臨界值運行被最佳化了的循環處理，其它的情況運行通常的循環處理。例如，某臨界值設定為1024的情況，如圖23(b)的程序362所示，循環次數N如果超過了1024時，對開始的1024次的循環處理運行雙重循環，對於剩餘次數的循環處理進行剝離了的循環處理。又，循環次數N在1024以下時，不運行雙重循環，運行被剝離的循環處理。之後，在雙重循環的最內循環前面插入預取指令(dpref(A[i+32]))，由此生成如圖23(c)所示的最佳化的程序363。
不需要循環分割的情況圖24是說明不需要循環分割情況下的最佳化處理的圖。如果輸入了圖24(a)所示的源程序371時，在循環中完全用完1行的數據(A[i]～A[i+31])。這種情況下，沒有必要進行雙重循環化。為此，如圖24(b)所示的程序372，在循環的開頭插入預取指令(dpref(A[i+32]))用來預取循環內使用的數據的1行前的數據，由此進行最佳化。
而且，循環內的處理周期數比預取指令中需要的處理周期數還要大時，沒有必要對循環進行雙重化，即使在循環的開頭插入預取指令也可以隱蔽預取指令的等待時間。
循環內存取的要素不排序的情況圖25及圖26是說明循環內存取的要素在主存儲器上沒有適當排序情況下的循環分割處理的圖。到此為止的說明中，都是在假設循環內存取的要素在主存儲器上適當排序的情況下進行的。排序的情況事先被編譯指示和編譯程序選項的指定所明確時，進行如上述例子中說明的最佳化。
但是，一般的編譯器，這些要素是否排序在運行之前是不明確的。為此，編譯器要以循環內存取要素在主存儲器上沒有適當排序為前提進行最佳化。
也就是說，出現了圖25(a)所示的源程序381時，如果設數組A的要素大小為4位元組，則和參照圖11進行說明的單循環分割一樣，進行最佳化。只是，由於以要素沒有排序為前提，所以插入最內循環前面的預取指令(dpref(A[i+64]))預取指定2行前的數組A的要素。而且，在循環處理之前，為了確保在循環內存取的數組要素A
～A[63]，預取指令(dpref(A
)及dpref(A[32]))被插入到預取的等待時間可以十分隱蔽的位置，生成圖25(b)所示的程序382。
而且，出現圖26(a)所示的源程序391時，和圖16一樣，疊入循環被剝離處理的部分之後，插入預取2行前的數組A的要素的預取指令(dpref(A[i+64]))。而且，和程序382一樣插入預取指令(dpref(A
)及dpref(A[32]))，生成如圖26(b)所示的最佳化程序392。
插入動態排序解析代碼的結構轉換分割圖27是說明動態確定沒有排序的數組要素，進行循環處理的最佳化的圖。考慮輸入了圖27(a)所示的源程序401的情況。這裡設數組A的要素為4位元組。
數組A的開頭地址(要素A
的地址)指定的比特表示高速緩存的行，存在於這個比特內的比特，表示行開頭開始的偏移量。因此，由進行稱作AMask比特之間的邏輯運算，可以取出行開頭開始的偏移量。這裡，屏蔽值Mask是事先給定的值。從數組A的開頭地址取出的偏移值向右只移位事先給定的補正值Cor，由此可以知道數組A的開頭要素A
位於1行內從頭開始的第幾個。因此，根據式(3)，可以求出行上沒有排序的要素數n。
n＝32-(AMask)＞＞Cor…(3)也就是說，如圖28所示，預取高速緩存431時，可以區分沒有排序的數組A的要素(A
～A[n-1])和排序的數組A的要素。
因此，如圖27(b)的程序402所示，根據式(3)求出沒有排序的數組A的要素數n。然後，根據要素數n，進行與沒有排序的數組A的要素(A
～A[n-1])有關的循環處理。之後，對於排序的數組A的要素(A[n]以後的要素)，和圖11所示的單循環分割情況同樣進行雙重循環化。
之後，對於正在剝離的循環405，如果進行疊入處理，就可以生成圖27(c)所示的程序403。又，如圖27(d)所示，插入預取指令(dpref(A[i+32]))，由此可以得到最佳化的程序404。
使用剖面信息的結構轉換分割圖29是關於使用剖面信息確定沒有排序的數組要素，而後進行循環處理的最佳化的處理進行說明的圖。對於沒有排序的數組要素數，不是如圖27那樣從計算中求得，而是從剖面信息中求出。根據取得的沒有排序的數組要素數N，進行如圖27所示的同樣的處理，把圖29(a)所示的源程序411轉換為圖29(b)所示的程序412。之後，疊入剝離的循環部分，得到圖29(c)所示的程序413。最後，插入圖29(d)所示的預取指令，由此得到最佳化的程序414。
對最內循環以外的循環的結構轉換圖30是說明對最內循環以外的循環結構轉換的圖。
考慮給予了圖30(a)所示的源程序421的情況。源程序421中進行雙重循環處理，設最內循環處理424中所參照的數組A的要素為1位元組。由於最內循環處理424的循環次數是4次，因此在最內循環處理424中數組A的要素被參照了4位元組。所以，由於最內循環處理424中參照的要素字節數小，因此這種情況下，把最內循環處理424作為1個整體考慮，最外循環如圖30(b)所示的程序422那樣，結構轉換為雙重循環。之後，運行第2個循環處理之前，插入預取高速緩存的1行份的數組A的要素的指令(dpref(A[j+128]))，得到圖30(c)所示的最佳化程序423。
依據編譯指示＃pragma_loop_tiling_dpref變量名[，變量名]的變量指定圖31是說明由編譯指示#pragma_loop_tiling_dpref變量名[，變量名]指定了變量情況下的最佳化處理的圖。如圖31(a)所示，編譯指示的指定＃pragma_loop_tiling_dpref b包含於源程序中時，只是著眼於循環內的數組b進行結構轉換，忽略數組a。因此，運行圖31(b)所示的雙重循環化，只插入預取數組b的指令。
如上說明，依據本實施例的編譯系統，雙重化循環處理，並在最內循環的外側運行預取指令。由此，可以防止發出無用的預取指令，並且可以提高程序運行時的處理速度。而且，由於雙重化循環處理，可以保證從運行預取指令之後到運行下一個預取指令之前的周期數。由此，可以隱蔽等待時間，防止互鎖。
以上，對有關本發明實施例的編譯系統，基於實施例進行了說明，但本發明不限於這個實施例。
例如，由指令最佳配置部187配置的指令，不限於預取指令，也可以是以下指令通常的存儲器存取指令、啟動外部處理並等待其處理結果的指令等等待應答指令、運行的結果有可能引起互鎖的指令、運行後在可以參照指定的資源之前需要多個周期的指令等。應答等待指令，除了經常等待應答的指令外，還包含具有等待應答情況和不等待應答情況的指令。
另外，也可以是把不具備高速緩存的計算機的CPU作為目標處理器，隱蔽各種處理的等待時間，輸出防止互鎖的代碼的編譯系統。
還有，可以在逐條解釋由CPU運行的機器語言指令串的同時，實現作為運行本實施例中說明的循環結構轉換等處理的OS(OperatingSystem)。
又，如以下所示的PreTouch指令，對於沒有可能引起互鎖的指令，本發明也可以適用。PreTouch指令指的是，進行在高速緩存上只事先保證用來存儲自變量指定的變量的區域的處理的指令。以下，對進行循環的結構轉換、插入PreTouch指令的處理進行說明。
單循環分割圖32是，在插入PreTouch指令時，對象區域與高速緩存大小排序，對不需要剝離的情況下的單循環分割處理進行說明的圖。
考慮輸入了圖32(a)所示的源程序502的情況。在這個源程序502中，定義了把循環次數i和變量val之間的運算結果(乘積結果)依次代入到數組A的要素的處理。這裡，設數組A的各要素大小為4位元組，設高速緩存的1行大小是128位元組(在以後的說明中，高速緩存的行大小也設為128位元組)。也就是說，高速緩存的1行上存儲32個數組A的要素。又，包含於源程序502的循環迭代次數128次是32的整數倍。
為此，源程序502，如圖32(b)的程序504所示，可以結構轉換為雙重循環。也就是說，在最內循環中進行32次反覆處理，在其外的循環中，進行反覆4次最內循環的循環處理。在最內循環處理中，高速緩存的1行的數據被代入數組A。之後，如圖32(c)的程序506所示，在運行最內循環之前，插入高速緩存區域保證指令(PreTouch(A[i]))。由於插入PreTouch指令，在運行最內循環時，在高速緩存區域中保證了該循環中定義的數組A的要素。由此，不會引起來自主存儲器的不需要的數據傳輸，可以減輕總線佔有率。
圖33是說明插入PreTouch指令時的不需要剝離情況下的單循環分割處理的圖。
考慮輸入了圖33(a)所示的源程序512的情況。在這個源程序512中，定義了把循環次數i和變量val之間的運算結果(乘積結果)依次代入數組A的要素的處理。這裡，設數組A的各要素大小為4位元組，且排序於高速緩存大小。也就是說，高速緩存的1行上存儲32個數組A的要素。又，設包含於源程序512的循環迭代次數是140次。也就是說是，除以1行上所存儲的數組A的要素數32時剩餘的數。
這種情況下，如圖33(b)所示的程序514，剝離140除以32時的剩餘數的循環次數，其外部分和圖32b同樣，結構轉換為雙重循環。之後，進行為了把剝離的部分包含於雙重循環結構中的剝離疊入處理，得到如圖33(c)所示的程序516。也就是說，通常狀態下，在最內循環進行32次的反覆處理，在最後運行最內循環時，進行剩餘的12(＝140-128)次的反覆處理。之後，如圖33(d)的程序518所示，在運行最內循環之前，插入高速緩存保證指令(PreTouch(A[i]))。只是，區域保證處理，以1行單位進行。由此，在運行可以保證目標對象A以外的區域的最後的最內循環時，使其不發出PreTouch指令，使其不保證目標對象A以外的區域。
插入動態排序解析代碼的結構轉換分割圖34是說明動態確定沒有排序的數組要素，進行循環處理的最佳化處理的圖。考慮輸入了圖34(a)所示的源程序522的情況。這裡，設數組A的要素為4位元組。
數組A的開頭地址(要素A
)指定的比特表示高速緩存的行，存在於這個比特內的比特，表示行開頭開始的偏移量。因此，通過進行稱為AMask的比特之間的邏輯演算，可以取出從行開頭開始的偏移量。這裡，屏蔽值Mask是事先給定的值。這裡，設[Mask＝0x7F]。把從循環初次存取的數組A的要素地址中取出的偏移值，從屏蔽值Mask中減掉，僅向右挪動事先給定的補正值Cor，由此可以知道數組A的要素A[X]位於1行從頭開始的第幾個。因此，根據式(4)，可以求出在行上沒有排序的要素數PRLG。
PRLG＝(Mask-(A[X])Mask)＞＞Cor…(4)而且，根據式(5)可以求出在循環最後參照的數組A的要素(A[Y-1])的下一個要素A[Y])位於1行內從開頭開始的第幾個，由此，可以求出沒有完全滿足1行的要素數EPLG。
EPLG＝(A[Y])Mask)＞＞Cor…(5)而且，可以根據式(6)求出進行沒有剩餘的1行的處理的循環次數KRNL。
KNRL＝(Y-X)-(PRLG+EPLG) …(6)也就是說，如圖34(b)的程序524所示，當高速緩存的區域分配有數組A時，也就區分了沒有排序的數組A的要素(A[X])～A[X+PRLG-1])、排序且是1行的倍數大小的數組A的要素(A[X+PRLG]～A[X+PRLG+KRNL-1])、排序但不滿足1行大小的數組A的要素(A[X+PRLG+KRNL]～A[X+PRLG+KRNL+ERLG-1])。
因此，如圖34(b)的程序524所示，進行依據式(4)求出沒有排序的數組A的要素數PRLG的處理等。然後，根據要素數PRLG，對沒有排序的數組A的要素(A[X])～A[X+PRLG-1])進行循環處理。之後，對排序的數組A的要素(A[X+PRLG]～A[X+PRLG+KRNL-1]的要素)，與圖32b所示的單循環分割情況同樣，進行雙重循環化。而且，如果EPLG＞0，由於需要剝離處理，因此與圖33b所示的需要剝離時的情況一樣，進行剝離處理。
之後，對剝離的循環，如果進行疊入處理，就生成了圖34(c)所示的程序526。而且，如圖34(d)所示，插入高速緩存區域保證指令(PreTouch(A[i]))，由此，可以得到程序528。
只是，插入區域保證指令，僅僅針對排序的區域且使用高速緩存的整個1行的最內循環。
產業上利用的可能性本發明適用於控制發出有可能引起互鎖的指令的編譯器、OS、處理器中運行的處理等。
權利要求
1.一種面向處理器的程序轉換裝置，該處理器具備包含運行時等待來自外部的指定應答的指令的指令系統，其特徵在於，具備進行雙重循環轉換的循環結構轉換裝置，其中雙重循環轉換是把包含於輸入程序中的反覆次數是x次的循環轉換為將反覆次數是y次的循環作為內循環且將反覆次數是x/y次的循環作為外循環的嵌套結構；指令配置裝置，在上述內循環的外部位置配置上述指令，由此轉換為包含該指令的輸出程序。
2.根據權利要求1所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置具備檢測包含於上述輸入程序中的循環的循環檢測部；檢測上述循環的反覆次數的反覆次數檢測部；檢測應答等待周期數的應答等待周期數檢測部，其中應答等待周期數是等待上述指令運行時的上述指定的應答的周期數；檢測上述循環的1次反覆處理所需要的1個序列周期數的1序列周期數檢測部；把上述循環分割為反覆次數是「上述應答等待周期數/上述1序列周期數」次的循環的循環分割部；進行雙重循環轉換的雙重循環轉換部，該雙重循環轉換是將反覆次數是「上述應答等待周期數/上述1序列周期數」次的循環作為內循環且將反覆次數是(上述循環反覆次數/上述內循環的反覆次數)次的循環作為外循環的嵌套結構的轉換。
3.根據權利要求1所述的程序轉換裝置，其特徵在於，還具備接收與最佳化有關的最佳化指示信息的最佳化指定信息接收裝置。
4.根據權利要求3所述的程序轉換裝置，其特徵在於，上述最佳化指定信息接收裝置接收包含於上述輸入程序的循環的最低反覆次數，上述循環結構轉換裝置，當循環的運行次數不定時，根據上述最低反覆次數，由上述循環取出上述最低反覆次數的反覆處理，對取出的循環的反覆處理進行雙重循環轉換。
5.根據權利要求1所述的程序轉換裝置，其特徵在於，上述指令是有可能發生互鎖的指令。
6.根據權利要求5所述的程序轉換裝置，其特徵在於，上述有可能發生互鎖的指令是從主存儲器向高速緩存預取數據的指令。
7.根據權利要求6所述的程序轉換裝置，其特徵在於，還具備進行指令編排的編排裝置，上述循環結構轉換裝置根據上述編排裝置得到的結果，把上述反覆次數是x次的循環分割為反覆次數是y次的循環，使得該運行的周期數是運行上述預取所需要的周期數，並進行將反覆次數是y次的循環作為內循環且將反覆次數是x/y次的循環作為外循環的嵌套結構的轉換即雙重循環轉換。
8.根據權利要求1所述的程序轉換裝置，其特徵在於，上述指令是在運行後到指定資源成為可以參照的狀態為止需要多個周期的指令。
9.根據權利要求8所述的程序轉換裝置，其特徵在於，上述需要多個的指令，是訪問主存儲器或者高速緩存的指令。
10.根據權利要求1所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置把上述反覆次數是x次的循環分割為反覆次數是y次的循環，使得該循環中所參照的數組的地址僅運行高速緩存的行大小前進量，並進行將反覆次數是y次的循環作為內循環，將反覆次數是x/y次的循環作為外循環的雙重循環轉換。
11.根據權利要求10所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置進行比例分配轉換，即當上述數組存在多個時，對進行了雙重循環轉換的上述反覆次數是y次的循環，根據上述數組數進一步進行比例分配。
12.根據權利要求11所述的程序轉換裝置，其特徵在於，上述比例分配轉換，對於多個上述數組，當這些數組要素的大小不同時，對應上述大小的比，比例分配上述反覆次數是y次的循環。
13.根據權利要求11所述的程序轉換裝置，其特徵在於，上述比例分配轉換，對於多個上述數組，當循環的反覆處理進行1次所前進的地址跨距不同時，對應上述跨距的比，比例分配上述反覆次數是y次的循環。
14.根據權利要求11所述的程序轉換裝置，其特徵在於，上述比例分配轉換，進行比例分配轉換，以便在轉換內循環之際，生成對應分配的各循環的條件語句，使分配的各循環在同一個內循環中運行。
15.根據權利要求10所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置，在把上述反覆次數是x次的循環分割為上述反覆次數是y次的循環時，如果運算x/y時的餘數z不是0，就對z次的反覆處理進行剝離處理，並進行雙重循環轉換。
16.根據權利要求15所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置，如果上述餘數z不是0，生成判斷內循環的循環次數是y次還是z次的判斷條件語句，並進行雙重循環轉換。
17.根據權利要求10所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置，當循環的運行次數不定時，運行時判斷上述循環的運行次數，根據判斷結果進行動態改變反覆次數的雙重循環轉換，。
18.根據權利要求10所述的程序轉換裝置，其特徵在於，還具備接收數組排序為高速緩存的行大小的信息的接收裝置，上述指令配置裝置，對上述反覆次數是x次的循環配置預取指令，預取該循環中x次的反覆處理所參照的數據的前一個高速緩存的行上所存儲的數據。
19.根據權利要求10所述的程序轉換裝置，其特徵在於，上述最佳化指定信息接收裝置，接收數組從高速緩存的行的哪個相對位置開始存取的信息，上述循環結構轉換裝置，根據該信息進行上述的雙重循環轉換。
20.根據權利要求10所述的程序轉換裝置，其特徵在於，上述指令配置裝置，當上述數組沒有按高速緩存的行大小排序時，對上述反覆次數是x次的循環配置預取指令，預取該循環中的x次的反覆處理所參照的數據的二個前的高速緩存的行上所存儲的數據。
21.根據權利要求10所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置，當上述數組沒有排序為高速緩存的行大小時，判斷數組從高速緩存的行的哪個相對位置開始存取，並根據判別結果進行雙重循環結構轉換。
22.根據權利要求10所述的程序轉換裝置，其特徵在於，還具備接收有關關注的數組的信息的接收裝置，上述循環結構轉換裝置，只對該數組進行關注，進行雙重循環轉換。
23.根據權利要求1所述的程序轉換裝置，其特徵在於，上述循環結構轉換裝置，把最內循環作為1個塊，對外循環進一步進行雙重循環轉換。
24.一種面向處理器的程序轉換方法，該處理器具備包含運行時等待來自外部的指定應答的指令的指令系統，其特徵在於，具備進行雙重循環轉換的步驟，把包含於輸入程序中的反覆次數是x次的循環轉換為將反覆次數是y次的循環作為內循環且將反覆次數是x/y次的循環作為外循環的嵌套結構；在上述內循環的外部位置配置上述指令，並轉換為包含該指令的輸出程序的步驟。
25.一種面向處理器的程序轉換方法的程序，該處理器具備包含運行時等待來自外部的指定應答的指令的指令系統，其特徵在於，使計算機運行如下步驟進行雙重循環轉換的步驟，把包含於輸入程序中的反覆次數是x次的循環轉換為反覆次數是y次的循環作為內循環，反覆次數是x/y次的循環作為外循環的嵌套結構；在上述內循環的外部位置配置上述指令，並轉換為包含該指令的輸出程序的步驟。
全文摘要
一種不再無端發出有可能引起互鎖的指令，可以提高程序運行時的處理速度的編譯器，其面向處理器並具備運行時有可能引起互鎖的指令，其特徵在於，賦予計算機功能，具備循環結構轉換部(186)，對輸入程序進行雙重循環轉換，把循環次數是x次的循環分割為循環次數是y次的循環，把上述循環次數是y次的循環作為內循環，把循環次數是x/y次的循環作為外循環；指令最佳配置部(187)，對上述雙重循環轉換之後的程序進行有可能引起互鎖的指令的配置。
文檔編號G06F9/45GK1918546SQ20058000468
公開日2007年2月21日 申請日期2005年2月4日 優先權日2004年2月12日
發明者川端輝雄, 小川一, 瓶子嶽人, 山本康博, 道本昌平 申請人:松下電器產業株式會社