多粒度並行化編譯方法

2023-05-26 09:20:11

專利名稱：多粒度並行化編譯方法
技術領域：
本發明涉及一種在由多個處理器單元構成的多處理器系統中，可以使該 多個處理器單元高效動作的多處理器系統的硬體結構以及生成程序的編譯方 法。
背景技術：
由於隨著半導體製造技術的進步而導致的的元件的微細化，而可以集成 數量巨大的集體管。與此同時，處理器的高頻率化也在發展，但由於動作時 功率的增加，此外還由於洩漏電流引起的待機時功率的增加，現有的處理器 通過一步步地提高動作頻率以及改善邏輯方式實現的性能提高開始出現局 限。
因此，目前作為實現性能改善和低功率化的方法，頗具前景的的是在單 片上搭載多個現有的被稱為CPU、 DSP的處理器單元(以下稱為PU)，來並 行地進行處理，由此，即使不提高動作頻率也可以得到較高的運算性能的多 處理器系統(單片.多處理器系統)。將來，通過微細化的進一步發展，可以 預測還可以在單片上集成100個~ 1000個PU。
在這樣的多處理器系統中，為了得到與PU的數量成比例的運算性能， 需要使搭載的PU同時動作來處理程序。但是，因為按時間序列逐一地記述 通常的輸入程序，所以即使搭載多個PU也無法得到與該多個PU成比例期待
的運算性能。
作為解決該問題的一個方法，程序開發者考慮自身程序的並行性，根據
執行該程序的多處理器系統的結構，需要附加用於通過多個PU執行該程序的並行化代碼。但是，本方法雖然在具有數個PU的系統中有效，但在將來 搭載了數十~數千個PU的系統中，此外特別是在具有不同種類的PU的結構
中，在開發時間、實效性能方面是不實用的。
因此，已經進行了自動並行化編i爭程序的研究，該自動並行化編譯程序 在由結構以及運算性能相同的多個PU構成的多處理器系統中，可以對輸入
程序進行分析，從該程序中提取可以並行動作的部分，將該部分分配給多個
PU來同時執行。例如，在特開2004 -252728號公報中公開了一種編譯方式， 該編譯方式，其對輸入源程序進行分析，將該程序分割為子程序或循環等各 種粒度的塊(任務)，對該多個任務間的並行性進行分析，並且將任務和這些 任務存取的數據分割為適合超高速緩沖存儲器或本地存儲器的大小，將其對 各個PU最佳地分配這些任務，由此，來生成使多處理器系統高效地動作的 目的程序。此外，作為支持多粒度並行處理的功能的晶片多處理器的體系結 構，在特開2001 - 175619號公報中進行了公開。
此外，為了降低功率消耗以及降低發熱，在多處理器系統中需要各PU 的低功率化，但是，關於單個處理器的低功率化方法，已經進行了各種各樣 的提案。例如，在專利第3138737號公報、特開2004-234126號公報中公開 了在實時處理制約內降低處理器的動作時鐘，通過動態控制與該時鐘頻率對 應的電壓提供給處理器的、頻率.電壓來實現低功率化的方法。
此外，在特開2004 - 252900號公報中公開了在判明了圖像處理等預處理 的順序的應用程式中，按照各處理的特性來組合CPU、 DSP等不同種類的多 個處理器，並預先測定給出在該處理器上的處理時間和消耗功率信息，由此， 根據該信息動態地將一連串的處理分配給該各個處理器的方法。

發明內容
目前，在汽車的導航系統、行動電話、數位電視等，產生同時處理圖像、 聲音、資料庫信息等多種數據的新應用程式的裝置中，為了使用對各個該數 據最佳的方法來同時處理多個種類的輸入數據，可以考慮處理器搭載多個種 類的PU。在現有的多處理器系統中，如上述特開2004-252728號公報所公 開的那樣，為搭載了多個相同結構的PU的同構的處理器系統。
但是，如此，在多個種類的PU上同時處理多種應用程式的面向未來的
5非同構多處理器系統中，存在以下的問題為了與搭載的PU的種類和數量 成比例地得到處理性能，需要考慮PU的種類來進行程序的並行化和配置。 此外，目前，為了在多個PU上高效地執行程序，在小規模的程序或可
以始終固定地執處理順序的情況下，為了得到用於進行調度的執行時間等調 度信息，需要在該系統上執行一次程序來測定處理時間等，開發者需要根據 該測定值預先手動生成該調度信息，需要較大的勞力和時間。
此時，在事先處理的內容或順序不明的一般程序的情況下，特別是在規
模較大的程序的情況下，難以通過手動事先生成該信息。此外，在PU的種
類或數量增加的情況下也同樣難以通過手動生成該信息。
此外，在搭載了多個PU的系統中，因為擔心全部處理器消耗功率增大，
所以特別是在考慮到用於行動電話等行動裝置、或家庭使用的數位電視等設
備時，不僅需要基於現有的OS的FV (動作頻率和驅動電壓)控制，還需要
根據基於各應用程式內的軟體的各個PU的處理狀況，進行極細緻的電源管 理和動作頻率控制。
特別是需要不降低處理性能地降低消耗功率。此外，即使在執行要求實 時處理的程序時，也必須既要遵守時間制約又要降低功率。
因此，本發明的目的在於提供一種在搭載多個種類的PU的多處理器 系統中，從成為處理對象的輸入程序中自動地提取具有並行化的任務，按照 各PU的特性來配置該任務，由此使該PU高效地動作，而且，通過推測該 PU的處理量來生成使動作頻率和電源電壓最佳化的代碼，並將該代碼附加給 目的程序的解碼器以及可以使其最佳化的多處理器系統。
因此，根據本發明，在集成了多個處理器單元的多處理器系統中，通過 ^_該處理器單元高效動作的程序分割裝置以及生成控制代碼(執行代碼)的 編譯程序，可以最大限度地發揮該處理器系統的性能，同時使處理時間最短，
而且可以以低功率高效地進行處理。此外，軟體開發者無需意識處理單元的 結構，就可以在短時間內高效地生成程序。
此外，在對輸入程序進行編譯時，根據處理器單元的結構編譯程序預先 估計事先的處理時間，對於在編譯時可以靜態地決定處理順序的部分事先決 定處理順序，此外，對於在不到執行時無法決定處理順序的部分，編譯程序
6生成動態地進行基於包含了執行時間的處理信息的調度的程序，由此，可以 在由多個種類的處理器單元構成的多處理器系統中高效地處理一般的程序。
此外，編譯程序對輸入程序進行分析，在事先決定了處理順序後估計處 理時間，查看對於時間制約的該處理時間的裕度來對每個處理器單元極細緻 地進行電壓管理、頻率控制，由此可以大幅降低功率。
此外，在由不同種類的處理器單元構成的多處理器中，在為了使執行時 間最小對輸入程序進行並行化並且進行了調度之後，為了使各處理器單元之 間處理時間最小，對每個處理器單元極細緻地進行動作頻率控制以及電源管 理，由此，可以無損性能地使功率最佳化。


圖1是表示本發明一實施方式的電源.頻率生成型多處理器系統的框圖。 圖2是電源電壓生成電路的框圖。 圖3是降壓電路的框圖。
圖4是供給電壓選擇電路的框圖。 圖5是時鐘生成電路的框圖。 圖6是時鐘脈沖選擇器的框圖。
圖7是表示多處理器系統其他例子的、匯集了電源電壓生成電路和時鐘 生成電路的電源 頻率選擇型多處理器系統的框圖。
圖8是表示多處理器系統其他例子的、匯集了各處理器單元的FV控制 寄存器的、具有FV控制表的多處理器系統的框圖。
圖9是表示基於FV控制的處理器單元的動作模式的說明圖。
圖10a表示本地存儲器的FV控制，是表示由多個存儲體構成本地存儲 器LM對每個存儲體進行FV控制的例子的說明圖。
圖10b表示本地存儲器的FV控制，是表示在本地存儲器LM中對每個 地址空間進行FV控制的例子的說明圖。
圖10c表示本地存儲器的FV控制，是表示對每個在多個存儲體中設定 的地址空間進行FV控制的例子的說明圖。
圖11是由縱橫開關構成本地總線時的電源控制的說明圖。
圖12是圖11所示的本地總線LBUS的結構圖。
7圖13是表示基於FV控制的本地存儲器LM的動作模式的說明圖。
圖14a表示FV控制寄存器格式，是表示由四個存儲體構成本地存儲器
LM時的寄存器格式的說明圖。
圖14b表示FV控制寄存器格式，是與圖14a相同地表示寄存器的設定
例的說明圖。
圖14c表示FV控制寄存器格式，是表示其他寄存器格式的說明圖，是 將LM設為4存儲體結構，對每個控制對象分配地址的FV控制寄存器格式 的例子。
圖15是表示圖8所示的FV設定表的格式的例子的說明圖。 圖16是表示FV控制寄存器的映射的整個多處理器系統的存儲器映射表 的說明圖。
圖17a表示FV控制寄存器訪問的例子，是表示CPU0對DSP0的FV控 制寄存器進行訪問的例子的說明圖。
圖17b表示FV控制寄存器訪問的例子，是表示CPU0對DSP0的FV控 制寄存器進行訪問時目標代碼的例子的說明圖。
圖17c表示FV控制寄存器訪問的例子，是表示用OS的API操作FV控 制寄存器時的目標代碼的例子的說明圖。
圖18a表示並行處理任務時的FV控制的概念，是表示宏任務並行執行 依存性的宏任務圖。
圖18b表示並行處理任務時的FV控制的概念，表示不進行FV控制時 (FULL模式)的甘特圖。
圖18c表示並行處理任務時的FV控制的概念，是表示使CPU持續動作 時的FV控制的例子的甘特圖。
圖18d表示並行處理任務時的FV控制的概念，是表示暫時使CPU停止 時的FV控制的例子的甘特圖。
圖19a表示實時制約時的FV控制，是通常處理的實時處理的甘特圖。
圖19b表示實時制約時的FV控制，是表示使CPU持續動作時的FV控 制的例子的甘特圖。
圖19c表示實時制約時的FV控制，是表示暫時使CPU停止時的FV控
8制的例子的甘特圖。
圖20是表示編譯程序的處理的流程圖。 圖21是表示輸入程序的 一例的原始碼。
圖22是編譯程序生成的任務之間的依存關係圖。 圖23是表示任務 FV控制調度結果的時序圖。
圖24表示編譯程序生成的代碼的一個例子，是表示面向CPUO、 DSP0、 DRP0 、 BRP1的代碼的說明圖。
圖25同樣表示編譯程序生成的代碼的一個例子，是表示面向CPU1、 DSP1、 BMP0、 BMP1的^^碼的i^明圖。
具體實施例方式
以下，根據附圖對本發明的一實施方式進行說明。
(實施方式的全體結構)
圖1表示本發明一實施方式的多處理器系統的結構。在圖1中，多處理 器系統以多個不同種類的處理器單元(以下稱為PU) 10~ 17、和這些共享存 儲器(以下成為SM) 18為主體構成。該各個PU10 17經由各自的總線接 口 (BIF ) 27與本地總線(稱為LBUS ) 19連接。SM18與LBUS19連接，可 以從各PU10- 17進行訪問。該各PU10 17連接了對該PU供給電源電壓以
21。此外，本多處理器系統表示由不同種類的處理器單元構成的非同構多處 理器系統的例子。
在本實施方式中，表示由PU的種類以及數量為兩個通用處理處理器(以 下為CPU) 10、 11，兩個信號處理處理器(以下為DSP) 14、 15,兩個動態 可重構處理器(以下為DRP) 16、 17，以及兩個位運算處理處理器(以下為 BMP) 12、 13構成的例子。此外，上述PU的種類以及數量並不限於本實施 方式表示的例子，可以採用各種各樣的結構。此外，可以是僅由現有相同種 類的PU的結構(例如僅由四個CPU構成)。此外，在本實施方式中，將DSP (0、 1)14、 15, DRP(O、 1)16、 17以及BMP(0、 l)作為特定用途處理 器單元，將CPU(O、 1) 10、 ll作為通用處理器單元。
此外，動態可重構處理器16、 17是指可以動態地重新構成處理電路的處理器，可以在限定的內核內虛擬地變更電^^。
上述各PU10 17,具備暫時保存各PU處理的程序、數據的本地存儲器
(或者超高速緩沖存儲器)(LM) 24、以及用於進行頻率 電源電壓(FV) 控制和PU間同步控制的系統控制寄存器(R) 25,頻率 電源電壓(FV) 控制決定對該PU的供給電壓(VL )、動作頻率(FL )。此外，本地存儲器(LM) 24被劃分為對其他PU以及具有該LM的自身PU可以訪問的全局地址進行 了映射的區域，和對只有該自身PU可以訪問的專用地址進行了映射的區域。 此外，與LBUS19連接的共享存儲器(SM) 18對全局地址進行了映射，可 以從多個PU進行訪問。此外，以上只是本發明應用構成的一個例子，作為 實施方式並不限於此。例如，雖然在圖1中沒有表現，但根據需要在LBUS19 上可連接輸入輸出處理、中斷處理、計時器、除錯電路等周邊電路。此外， 還可以經由總線橋分級連接相同種類或不同種類的總線。
此外，在各個PU10 17共享的SM18中具備系統控制寄存器(R) 181， 其用於設定對SM18供給的供給電壓(VL)、動作頻率(FL)，進行頻率.電 源電壓(FV)控制。此外，在相互連接所述PU以及所述SM的本地總線19 中具備系統控制寄存器R191,其用於設定對LBUS供給的VL、 FL,進行FV 控制。此外，還可以取代該系統控制寄存器(R) 181,對各個PU10 17的 系統控制寄存器(R)25設置SM18以及LBUS19的FV控制用寄存器。此外， 系統控制寄存器(R) 181由PU10- 17中的某一個進行設定。
此外，雖然表示了在一個晶片(LSI)上構成上述PU10 17的情況，但 還可以將構成PU10 17的多個LSI進行結合，來作為一個晶片或模塊。
此外，SM18可以由每個種類的處理器(每個CPU、 DSP、 DRP、 BMP) 共享，例如，如後述的圖10a~圖10c所示，將SM18的區域分割為存儲體， 也可以由每個種類的處理器共享各存儲體。或者可以由多個PU共享SM18 的一部分。
(電壓.頻率可變電路)
然後，對與各個PU連接的電源電壓生成電路(DCGEN) 20以及時鐘生 成電路(CLKGEN) 21的結構進行說明。
圖2表示DCGEN20的結構。DCGEN20由把外部供給的通常'的電源電壓(VD)降壓(或者升壓)為預先指定的多個供給電壓(VL) 205的電路 (DCCNV) 206、從所生成的多個該供給電壓選擇向PU供給的電壓的供給 電壓選擇電5各(VDSEL) 203、以及切斷電源電壓的電路(後述)構成。
此外，降壓(或者升壓)電路(DCCNV) 206,包含多個電壓降低部， 例如如圖2所示，由原樣供給電源電壓VD的電路22'、將電源電壓VD降低 至3/4的降壓電路(LVCNV) 201、將電源電壓VD降低至1/2的降壓電路 (LVCNV) 202構成。
各PU10 17,根據在該PU具有的系統控制寄存器(R) 25內的FV控 制寄存器中設定的FV (驅動頻率以及驅動電壓)模式經由控制線路(DCCL ) 204控制供給電壓選擇電3各(VDSEL) 203，由此，從降壓電i 各(DCCNV) 206生成的多個電壓中選擇某一個電壓，並將該選擇出的供給電壓VL供給給 對應的PU10 17。此外，FV控制寄存器被設定在系統控制寄存器25內的規 定區域中。
圖3表示降低電源電壓的電路(LVCNV)的結構的一例。上述圖2的降 壓電路LVCN201 、 202 ，由決定供給電壓(3/4VD )的參照電壓生成電路(VREF ) 207以及降壓至參照電壓指定的電壓對PU供給電流的電源生成電路(VGEN) 208構成，將電源生成電路208的輸出輸入給圖2的供給電壓選擇電路203。
降壓電路LVCNV輸出電壓(VCNV)由決定參照電壓的參照電壓生成 電路(VREF ) 207內的nMOSFET的級數決定，決定LVCNV的結構，以使 供給由FV控制寄存器指定的電壓。從通過以上電路降壓的多個電壓中選擇 由來自PU的由控制線204指定的電壓，向各PU10 17進行輸出(205 )。
圖4表示供給電壓選擇電路(VDSEL) 203的結構的一例。供給電壓選 擇線路(VDSEL) 203由控制信號解碼部2031和電壓選擇開關2032構成。 此外，通過在PU的源電壓供給部中插入閾值高的nMOSFET209，可以降低 切斷該PU的電源時流動的洩漏電流。此外，圖3、圖4的結構不只是用於實 現降壓電路LVCNV功能的一個結構，還可以應用其他各種各樣的電源電壓 生成電路方式。
然後，在圖5中對時鐘生成電路(CLKGEN)21的結構的一例進行說明。 CLKGEN21，由時鐘脈衝選擇器(CLKSEL) 214構成，該時鐘脈沖選擇器，從把內部時鐘FC (23)降低為該內部時鐘的1/2、 1/4等將內部時鐘FC降低 為整數分之一的分頻電路212、 213,以及分頻生成的多個時鐘中，選擇向該 PU進行供給的時鐘(FL) 216。此外，在PLL ( Phase Locked Loop)電路211 中，通過對從外部輸入的系統時鐘按指定的倍增率進行倍增生成內部時鐘FC (23 )。
圖6表示時鐘脈衝選擇器(CLKSEL )214的結構的 一個例子。CLKSEL214 由輸入控制信號CKCL的解碼部2171和時鐘信號選擇部2172構成。各個PU 通過該PU具有的FV控制寄存器的模式經由控制線路(CKCL) 215控制 DCSEL214，由此從生成的多個時鐘中選擇指定的FL，接受該時鐘FL216的 供給。
此外，除了上述圖l所示的結構之外，如圖7所示，可以是以下的結構 對多個PU (或者全部PU)各附加一個變更電源電壓、時鐘脈沖的電路 (DCCNV206、 CLKCNV217)，並且還在各個PU—側附加對生成的多個種 類的電源電壓以及時鐘脈沖進行選擇的電路(203、 214)。在圖7的例子中， 表示兩組電源電壓生成電路206和時鐘生成電路217分別對四個PU供給電 力和時鐘的情況。
結構並不限於上述表示的結構。例如，可以為以下的結構對多個PU(或者 全部PU)附加一個對電源電壓進行轉換的電路DCCNV206,並在PU —側對 每個PU附加生成時鐘脈衝的電路CLKCNV217。此外，例如可以為以下的結 構對多個PU (或者全部PU)附加一個生成時鐘脈衝的電路CLKCNV217， 並在PU —側對每個PU附加對電源電壓進行轉換的電路DCCNV206。此外， 例如可以為以下的結構不在晶片內搭載DCCNV206,輸入在晶片外部生成 的多個種類的電源電壓，由VDSEL選擇供給希望的供給電壓VL205。
此外，作為設定FV控制模式的單元，除了圖1和圖7所示的各PU具有 進行該PU的FV控制的FV控制寄存器(系統控制寄存器(R) 25)的結構 之外，如圖8所示，還可以採用將總括保存各PU10~ 17的FV控制模式的 FV控制表(FVTBL) 26與LBUS19連接的結構。在圖8中，把圖1中在系 統寄存器25中包含的FV控制寄存器，集合為與本地總線LBUS19連接的FV
12控制表26。
FV控制表(FVTBL ) 26可以由各個PU10 ~ 17訪問，且可以設定在共 享存儲器SM的一部分中，也可以由與共享存儲器SM獨立的存儲器(或者 寄存器)構成。 (總線IF)
如上，因為各個PU10 17可以單獨地設定電源電壓，所以在與該PU連 接的LBUS19之間，信號的電壓等級不同。因此，在PU10~ 17與LBUS19 之間連接的總新接口 (BIF) 27具備信號信號電平轉換電路(省略圖示)，進 行總線LBUS19和PU10 ~ 17之間的信號電平轉換。 (針對PU的電壓.頻率模式的給予方法)
然後，對決定由電源電壓生成電3各(DCGEN) 20以及時4中生成電3各 (CLKGEN) 21生成的電源電壓(VL) 205以及動作時鐘(FL ) 216的硬體 結構進行說明。
在設計時預先決定電源電壓生成電路(DCGEN) 20以及時鐘生成電路 (CLKGEN) 21的動作模式(供給的VL、 FL值)，各個PU針對所述電路根 據該PU具備的FV控制寄存器的值，經由控制線路DCCL、 CKCL進行指定。 關於VL、 FL的設定方法在後面進行詳細地敘述，編譯程序生成設置FV控 制寄存器的控制代碼，執行該代碼的通用處理器CPUO或CPUl,對存儲器映 射的FV控制寄存器進行訪問來改寫值。
本實施方式的PU10 ~ 17的FV模式，將VL、 FL的組合設定為4個階段 (FV控制寄存器內的2位)。圖9表示PU10 ]7動作模式一覽表。即，在 FV控制寄存器的2位的值在"00"中設定為VL-O, FI^O的成為電壓.頻 率切斷的OFF模式，在上述寄存器值為"11"中，設定VI^VD與系統的電 源電壓等價、FL = FC與系統的動作頻率等價的FULL模式。
此外，在寄存器值為"01"中，設定為VL= (1/2)VD， FL= (1/4) FC的LOW模式，在寄存器值為"10"中，設定為VL= (3/4) VD, FL = (1/2 ) FC的MIDDLE模式。此外，VL . FL模式的數量、VD FL值，才艮 據所構築的系統的形式、應用程式、使用的處理技術等決定。 (PU內的部分的FV控制)以上，假定將FV控制對象的範圍設為全部PU,總括設定FV控制模式 來進行了說明，但還可以對PU10 17搭載的本地存儲器(LM)、 FV控制寄 存器、其他的處理器周邊電路進行各種各樣的FV控制模式設定。這可以通 過擴展FV控制寄存器的位域，使其具有設定與被FV控制部對應的FV控制 模式的域來實現。例如，對於本地存儲器LM或系統控制寄存器(R) 25數 據保存所需要的電路，可以考慮採用獨立設定FV、 VL的機構。即，通過對 本地存儲器LM、 FV控制寄存器獨立地進行FV控制，即使所述PU的FV為 切斷狀態，也可以保存該LM以及R的數據，此外，在對象PU為切斷狀態 時，也可以從其他的PU對該PU的LM進行訪問。
此外，還可以根據本地存儲器LM的結構，設定多個FV控制對象。圖 10a ~ 10c表示針對本地存儲器LM的FV控制方式。
例如，如圖10a所示，使本地存儲器LM成為存儲體結構，對每個存儲 體(Bankl Bank3 )分別執行FV控制。因此，對各個Bankl Bank3分別 連接供給電壓選擇電路(VDSEL) 203。
即，只對保存數據所需要的存儲體供給通常電壓，或者供給保存數據所 需要的最低限度的電壓，該存儲體以外的存儲體切斷電源，由此可以削減功 率，並且因為無需進行數據的退避處理，所以可以高速地進行從電源切斷時 向通常動作時的恢復。
此外，還如圖10b所示，按照一定的連續的地址空間(Areal ~ Area4 ) 分割本地存儲器LM的地址空間，以該空間為單位進行FV控制，由此通過 切斷不需要的地址空間(存儲區域)的電源可以削減功率。
因此，對每個本地存儲器LM的各個地址空間(Areal ~ Area4 )連接供 給電壓選擇電路(VDSEL) 203。
此外，如圖10c所示，在本地存儲器LM為存儲體結構時，以按照跨越 各個存儲體(Bank0 3)的一定的連續的地址空間(Areal ~ Area4 )進行分 割的單位進行FV控制。
因此，對跨越本地存儲器LM的各個BankO ~ 3的每個地址空間(Areal ~ Area4)連接供給電壓選擇電路(VDSEL) 203。根據該結構，可以實現活用 存儲體結構使存儲器訪問高速化的存儲器交叉存取，並且可以實現低功率化。
14僅可以僅由功能性地搭載該LM的 PU進行訪問的部分(非共享存儲器)、和不僅由該PU由其他的PU也可以訪 問的部分(分散共享存儲器)來進行安裝，還可考慮按照以上兩個存儲器功 能單位進行FV控制。因此，雖然沒有圖示，但對每個上述非共享存儲器和 分散共享存儲器的區域分別連接供給電壓選擇電路(VDSEL )。
此外，圖10a 圖10c表示的存儲器分割方法，對於所述存儲器功能單位、 還有共享存儲器等系統搭載的各種各樣的存儲器、功能部位單位，也可以同 樣地適用。例如，對於在PU外配置的共享存儲器SM,也可以使其成為多個 存儲體結構，對應針對各個存儲體的訪問頻度、系統狀態(準備、睡眠)進 行其他的FV控制。
例如，通過代替本地存儲器LM將圖10a的結構用於共享存儲器SM18, 並將共享存儲器SM18分割為存儲體(Bank0 ~ 3 )，對每個存儲體連接供給電 壓選擇電路(VDSEL) 203,由此可以以存儲體為單位進行功率控制。此外， 通過代替本地存儲器LM將圖10b的結構用於共享存儲器SM18，按照一定的 連續的地址空間(Areal ~ Area4 )分割共享存儲器SM18的地址空間，以該 空間為單位進行FV控制，由此，可以通過切斷不需要的地址空間(存儲區 域)的電源來削減功率。此外，還可以代替本地存儲器LM將圖10c的結構 用於共享存儲器SM18，以按照跨越各個存儲體(Bank0 3)的一定的連續 的地址空間(Areal ~ Area4 )進行分割的單位進行FV控制(功率控制)。此 外，在將圖10a 圖10c用於共享存儲器SM18的情況下，將圖中的[LM]改 讀作[SM]。
(針對本地存儲器LM的FV控制模式)
作為將FV控制對象設為PU內的多個部分(功能部分)的例子，在下面 對對於本地存儲器LM與PU獨立地進行FV控制的方法進行說明。在本例中， 如圖10a所示，本地存儲器LM由4個存儲體(BankO ~ 3 )構成，FV控制對 象是PU以及每個LM存^諸體。
PU的FV控制模式與上述圖9所示的相同。圖13表示本地存儲器LM 的FV控制模式的一覽表。關於LM的動作模式，因為對象是存儲器，所以 在本實施方式中為可以進行通常存儲器訪問以及數據保存的通常動作模式
15(VL = VD， FL = FC,寄存器值"11")、無法進行存儲器訪問但可以進行數 據保存的數據保存模式(VL= 1/2VD, FL = 0,寄存器值"01")、以及不進 行數據保存完全切斷電源的電源切斷模式(VL = 0， FL-0,寄存器值"00") 的三個模式。
然後，如圖10a或者圖10c所示，由多個存儲體構成本地存儲器LM,在 圖14a中表示與每個存儲體的FV控制對應的FV控制寄存器的格式。在本例 中，對於每個PU10 17將FV控制寄存器1250映射為一個存儲器地址，在 該區域(映射的地址)對每個控制對象決定FV控制模式。如圖所示，在一 個區域為32位時，即，將位l、 O作為PU的FV控制模式(PUFV);將位3、 2作為LM存儲體0 ( BankO )的FV控制才莫式(LMOFV);將位5、 4作為LM 存儲體1 (Bankl )的FV控制模式(LMIFV );將位7、 6作為LM2 ( Bank2 ) 的FV控制模式(LM2FV);將位9、 8作為LM存儲體3 (Bank3)的FV控 制模式(LM3FV),來訪問希望的區域，根據圖13的表決定本地存儲器LM 的動作模式，來進行FV控制。此外，PU的動作模式根據圖9的表來決定。
圖14b表示FV控制寄存器1250的設定例。在本例中，PU的模式在圖 14a的PUFV中設定MIDDLE ( "1 、 0");為了僅激活本地存儲器LM的存儲 體O使其進行通常動作，在LMOFV中設定"1、 1",為了LM的存儲體1成 為數據保存才莫式在LM1FV中設定"1 、 0";存儲體2以及存儲體3在LM2FV、 LM3FV中設定"0、 0"作為電源切斷。
此外，除了上述之外，還可以採用對於FV控制寄存器，對每個控制對 象分配地址的結構。例如，如圖14c所示，表示對每個FV控制對象，將寄 存器映射為存儲器地址的FV控制寄存器的格式。在圖14c中，按照地址的 順序存儲表示PU的FV控制模式和LM的FV控制模式的PUFV、 LMOFV ~ LM3FV。
如上述圖14a所示，當在FV控制寄存器的位域切斷控制對象的FV控制 模式時，需要用於設定該域的值的比特運算，但在圖14c的結構中，直接訪 問直接映射了該控制對象寄存器的地址即可，所以可以削減與FV控制寄存 器的設定有關的命令數。但是相反，與圖14a相比需要較多的地址資源。
16控制模式的例子進行了說明，但如圖8所示，在作為與本地總線LBUS19連 接的FV控制表(FVTBL ) 26,具有表示各PU10 ~ 17的FV控制模式的FV 控制寄存器的情況下，如圖15所示，構成該FVTBL。
圖15表示圖8所示的FV控制表FVTBL的4各式。該FVTBL的1行與 PU號碼(PUN250 )、該PU的FV控制模式(PUFV251 )、 LM的FV控制模 式(LM0FV252、 LM1FV253、 LM2FV254、 LM3FV255 )、以及後述的本地總 線LBUS的FV控制才莫式(BUSFV )相對應，可以決定對於任意PU的該PU、 LM、 LBUS的FV控制模式。
而且，CPUO等讀入該FV控制表FVTBL後，對每個PU10 ~ 17決定PU 和本地存儲器LM (每個存儲體)以及本地總線的FV控制模式，控制電壓生 成電路(DCGEN) 20以及時鐘生成電路(CLKGEN) 21。 (針對總線的電源控制)
此外，對連接各個PU10 17的本地總線(LBUS) 19,作為多處理器系 統的以功能部位單位的FV控制，還可以部分地進行電源控制(電源切斷)。
例如，在PU10 17中的某個PU在非動作時電源-故切斷的情況下，因為 該PU的總線接口 (BIF)不^^皮訪問，所以可以進行該BIF的電源切斷，結果 可以削減洩漏電流。此外，在將總線的結構設為縱一黃交叉開關(crossbar)的 情況下，還可以對決定與該PU連接的總線的切換部的電源進行控制，切斷。
在圖11中表示對於交叉結構總線的電源控制的概念。例如，在將DSPO (14 )設為電源切斷狀態假設沒有對於DSPO的通信量時，還切斷針對DSPO 附帶的BIF( 27)的電源，以及切斷針對開關群(192 )的電源，該開關群(192 ) 對DSPO連接來自其他PU以及共享存儲器SM的總線網絡。
由此，可以削減成為非動作狀態的DSPO的開關群192的功率消耗。在 圖12中表示用於實現針對交叉網絡的電源控制的電路結構。此外，在本圖中 表示將CPUO、 DSPO、 DSP1以及共享存儲器SM與由交叉網絡構成的本地總 線LBUS19連接的結構。本電路由對各個PU10~ 17發送出的數據包數據進 行分析，進行圖11所示的開關群192的控制的網絡控制部NWCRL、和將該 數據包數據的發送源與發送目的地的網絡進行連接的網絡開關部(NWSW) 構成。網絡控制部NWCRL，由對PU10 17發送出的數據包進行分析，決定數 據包的優先度的SHCTL195;對由SHCTL195決定了優先度的該數據包進行 選擇的選擇器(SELC) 196;暫時保存該數據包的隊列197;以及對分析該數 據包連接發送目的地以及發送源的網絡的選擇開關191-194進行控制的 SWCTL198構成。
此外，網絡開關NWSW,由連接各個PU之間的網絡的選擇開關(SEL) 191 ~ 194構成。
在各個PU10~ 17和網絡控制部NWCRL中，分別設置與電源生成電路 DCGEN選擇性連接的開關(DCSEL) 199。而且，從開關(DCSEL) 199對 各個PU10 17以及BIF27和連接該PU的選擇開關191 ~ 194進行電源供給。
例如，在假設將DSPO設為電源切斷狀態、沒有對於DSPO的通信量時， DSPO附加的開關DCSEL199,不僅切斷該DSPO的電源，還切斷針對與該 DSPO連接的BIF27的電源、以及切斷針對選擇開關SEL1 ( 192)的電源，該 選擇開關SEL1 (192)選擇向該DSPO的網絡。由此，不僅是成為電源切斷 狀態的DSPO,還可以通過切斷向周邊電路的功率供給來進一步削減功率消 耗。此外，在使整個網絡為待機狀態，即為電源切斷狀態時，還對NWCRL 通過向該NWCRL供給功率的開關DCSEL199進行電源切斷。 (FV控制寄存器的設定方法)
然後，對設定FV控制寄存器1250的具體的方法進行說明。以下，將寄 存器格式作為圖14a的結構進行說明。
分別對各個PU的FV控制寄存器25分配全部PU可以唯一訪問的全局 地址，編譯程序預先決定的任務管理用PU (即，執行調度程序或OS的PU) 訪問該地址，並變更該寄存器值，由此來設定FV控制模式。
圖16表示整個多處理器系統的全局地址空間映射表。在本實施方式中， 定義從首地址到規定的地址可以看到PU自身的本地資源(包含LM、 FV控 制寄存器1250的系統設定寄存器)的區域、以及廣播(BC)區域。關於BC 區域在後面進行敘述。而且，在BC區域的後面，分配每個PU的地址空間， 而且在各個PU內的地址空間分配本地存儲器LM地址、以及系統設定寄存 器地址。FV控制寄存器，具有所述系統設定寄存器地址內的1個地址，通過訪問該地址可設定FV控制模式。另夕卜，在圖8中，在按CPU0、 CPU1、 DSP0、 DSP1的順序，由首端空間映射地址，例如設定DSP0的FV控制寄存器時， 就訪問地址"DSPO—FVREG—ADRS"。另夕卜，在該空間的各PU區域之後，分 配共享存儲器SM的地址。
FV控制寄存器的設定，通過編譯程序決定的任務管理用PU執行寄存器 訪問用目標代碼，經由本地總線LBUS19訪問控制目的地PU的FV控制寄存 器來進行。關於編譯程序生成該目標代碼的具體的方法將在後面進行敘述， 下面進行簡單的說明，在編譯程序將任務分配給多個PU時，對該多個PU進 行分組，決定進行分組內的任務的啟動、同步處理的任務管理PU。編譯程序 生成在該管理PU上進行FV控制的代碼，通過該管理PU執行該代碼來進行 分組內的PU的FV控制。此外，上述編譯程序在未圖示的計算機上執行。
圖17a表示設定FV控制寄存器的例子。假設編譯程序對CPUO、 DSPO、 DSPl進行分組，CPUO進行任務管理，該CPUO對DSPO進行FV控制。CPUO 通過執行由編譯程序生成的進行FV設定的目標代碼，來設定DSpO的FV控 制模式。
圖17b表示設定DSPO的FV控制模式的目標代碼的例子。在本例中，預 先定義DSPO內的FV控制寄存器的地址，對CPUO內的通用寄存器傳送該 FV控制寄存器的地址以及FV設定值，然後在該地址指定的寄存器中讀入該 設定值，由此來完成設定。
此外，作為進行FV設定的方法，設為任務管理PU執行直接訪問寄存器 的目標代碼，例如如圖17c所示，在設為OS管理各個PU的FV動作模式的 情況下，通過調用OS的FV控制用API,可以在OS的管理下進行PU的FV 控制模式設定。
此外，當設置整個系統的FV控制用寄存器，並在該寄存器內設置對全 部PU10~ 17的FV控制模式進行設定的寄存器，來在各個寄存器中設定模式 時，可以具有自動設定全部PU10~ 17的FV模式的才幾構。例如，如圖8的 FV控制表26所示，通過設置由全部PU10 17共享的寄存器，對該寄存器 進行更新，由此可以變更全部PU10~ 17的FV控制模式。
此外，可以在該整個系統的控制用寄存器中對應通用處理PU組(CPU )、
19專用處理PU組(DSP、 DRP、 BMP)等處理器的種類，設置對該每個種類的 PU同步設定FV模式的多個FV控制寄存器。此時，通過在圖8的FV控制 表26中對處理器的每個種類設置FV控制寄存器，並對各個CPU、DSP、DRP、 BMP共享FV控制寄存器，由此可以通過變更一個寄存器來對每個處理器的 種類變更FV控制模式。 (BC區域)
然後，下面對在上述圖16中表示的在存儲器映射的前端區域中設置的廣 播(BC)區域進行說明。該BC區域是寫入專用的區域，當一 PU對該BC 區域的一地址進行數據的寫入時，經由本地總線LBUS19在預先與該地址對 應的全部PU的各個LM入口 ( entry )中同時寫入該數據。由此，各個PU的 本地存儲器LM同時具有全部PU共享的數據，各個PU10 ~ 17即使不訪問共 享存儲器SM也可以高速地訪問LM上的該數據。
此外，在進行FV控制等系統控制時，也可以通過進行該廣^"對全部PU 一起發送控制信息。此外，通過與指定PU範圍的任務信息一起進行廣播發 送，還可以實現限定PU的範圍地發送數據、控制信息的廣播功能。結果， 例如在編譯程序，定義由並行處理某個任務的多個PU構成的PU分組時，可 以在該PU分組內一起開始任務處理，或者進行FV控制，整個系統的吞吐量 提高。
(任務處理時的FV控制概念)
然後，使用圖18a~圖18d，對各PU10 17中的任務處理時的電源電壓、 動作頻率(FV)控制方法的概念進行說明。各個PU執行的任務(程序)通 過後述的編-澤程序由輸入程序生成。即，該輸入程序首先通過後述的編譯對 該程序進行分析，由此，作為宏任務(MT)分割僅由賦值語句形成的基本塊 (BB)、重複塊(RB)、子程序(SB)等粒度較大的語句 塊。在本例中， 假設分割為三個宏任務MT301 ~ 303。這裡，宏任務是將輸入程序(原始碼) 分割為多個粒度的單位塊的任務。即，通過分割為宏任務，來進行多粒度並 行處理，在該多粒度並行處理對利用子程序等粗粒度任務之間的並行處理的 宏數據流處理、作為循環級別的並行處理的中粒度並行處理中，分級地組合。此外，在本實施方式中，假設將程序的構成要素作為
宏任務，將宏任務的構成要素作為任務，將任務分配給PU10 17。
然後，通過對該宏任務MT在任意PU中的運算成本等特性信息進行計 算，來決定在哪個PU上執行該宏任務MT，此外，通過對該宏任務MT之間 的數據依存性、控制依存性進行分析，來決定任務的執行順序。
圖18a是表示任務間的並行執行依存性的宏任務圖。本圖表示可以同時 執行宏任務MT1 ( 301 )和宏任務MT2( 302 )，而且還表示了宏任務MT3( 303 ) 可以在結束執行宏任務MT1 ( 301)以及宏任務MT2 ( 302 )之後執行。此外， 在本例中，對PUIO (CPUO)配置宏任務MTl,對PU12 (BMPO)配置宏任 務MT2，對PUIO (CPUO)配置宏任務MT3。
圖18b表示對如上那樣進行了調度的宏任務進行了通常處理(無電壓-頻 率控制)時的處理甘特圖。
在圖18b中，因為宏任務MT1和MT2可以並行執行，所以MT1由CPU (CPUO) ( 305 ), MT2由BMP ( BMPO ) (306)同時開始處理。在進行通常 處理時，作為對CPU、 BMP共同供給的電壓供給通常的VD，此外，作為動 作頻率也供給通常的FC。在本例中，CPU中的宏任務MT1的處理周期數小 於BMP中的宏任務MT2的處理周期數，所以CPU中的宏任務MT1的處理 (305 )在BMP中的宏任務MT2的處理(306 )之前結束。
CPU因為結束了宏任務MT1的處理(305 ),所以然後處理宏任務MT3 (307 ),但是根據宏任務MT之間的依存關係，可以在BMP中的宏任務MT2 的處理(306)結束之前不執行在CPU中下一個應該處理的宏任務MT3。因 此，CPU在BMP中的宏任務MT2的處理結束之前成為空閒狀態。因為即使 在該空閒狀態下，也對CPU供給通常的電源電壓VD以及時鐘FC,所以消 耗多餘的功率。
因此，作為解決以上問題的一個方法，當在CPU中執行宏任務MT1時， 為了使執行BMP宏任務MT2的處理所需要的時間與CPU執行宏任務MT1 的處理時間相等，通過使CPU的動作頻率低於通常時(FULL模式)的LOW 模式(圖9的供給1/4FC的模式)進行驅動(308)。即，通過通常時的FV 控制模式(FULL)驅動BMP,另一方面，將CPU的FV控制模式設為LOW
21模式，降低處理先結束一方的PU的動作頻率，並且為了在進行並行處理的
PU之間，使FV控制模式不同，進行FV控制寄存器的設定。圖18c表示應用本方法的FV控制時的甘特圖。編譯程序通過對CPU (CPU0)中的宏任務MT1的處理周期數以及BMP (BMP0)中的宏任務MT2的處理周期數進行
低CPU的動作頻率，所以還可以降低對該PU的電源電壓，可以使消耗功率最佳化。
即，在該例子中，關於宏任務MT1,將CPU的FV控制模式設定為圖9的[LOW模式],將並行進行處理的BMP的FV控制模式設定為[FULL]。
此外，作為解決上述圖18b的CPU空閒狀態的其他方法，在CPU中的宏任務MT1的處理(309)結束的時刻，切斷CPU的電源電壓以及動作時鐘的供給，置為待機狀態(310)。即，當CPU結束了宏任務MT1的處理時，將CPU的FV控制模式設定為圖9的[OFF]。而且，在開始執行宏任務MT3時，將FV控制模式設定為[FULL],重新開始處理。圖18d表示應用本方法的FV控制時的甘特圖。
在圖18d中，CPU的宏任務MTl的處理在BMP中的宏任務MT2 ( 306 )之前結束，但在該結束時刻使CPU為待機狀態(OFF),並且在BMP結束了宏任務MT2的處理(306 )的時刻，通過供給通常的電源電壓以及動作頻率再次使CPU恢復通常狀態，開始宏任務MT3的處理(307)。結果，因為不使CPU空閒而是使其停止動作，所以可以降低消耗功率。
如此，在對程序(任務)進行編譯時，編譯程序根據PU的結構預先估計事先的處理時間，關於在編譯時可以靜態地決定處理順序的部分事先決定處理順序，對每個PU細緻地進行動作頻率控制以及電源管理，由此，可以無損多處理器系統的性能地使功率最佳化。
(任務處理時(實時制約時)的FV控制概念)
以上，對宏任務(MT)的執行條件依存於其他宏任務MT時的FV控制方法進行了說明，但除此之外，還可以考慮任務在某一定時間內具有應進行處理的制約的、即如圖19a所示的以決定了該任務的處理期限(允許時間)的實時處理任務為對象的FV控制方法。
22在圖19a例示的宏任務(MT1 ) 311中，當在[FULL]模式下，即通過以通常的電源電壓以及時4中頻率動作的CPU進4亍處理時，處理在處理期限(Deadline)之前結束。此時，在處理結束的時刻CPU成為空閒狀態，但因為對於本來的處理期限具有富餘，所以可以在處理期限制約內降低CPU的動作頻率(312)。
圖19b表示應用本方法的FV控制時的甘特圖。編譯程序對在處理期限之前可以結束處理的動作頻率進行估計，如圖所示，將CPU的FV控制模式決定為[LOW]模式。結果，還可以降低供給電壓VL，可以使消耗功率最佳化。此外，還可以同樣地在宏任務MT1的處理(313)結束的時刻切斷CPU的電源以及動作時鐘(314),由此來降低消耗功率。圖19c表示應用本方法的FV控制時的甘特圖。此時，CPU通過[FULL]模式處理宏任務MTl,在處理期限之前結束處理，但可以通過在宏任務MT1結束時將動作模式置為[OFF]，來避免無用的功率消耗。(編譯程序的處理流程)
然後，按照以下的順序，對在上述多處理器.體系結構上，生成與處理器單元(PU)的特性相符合的調度以及生成根據電壓 頻率的動態變化進行消耗功率最佳控制的代碼的編譯方法、和採用了該方法的編譯程序的處理進行說明。圖20表示採用了本方法的編譯程序40的處理流程。(宏任務的生成)
使用C或Fortran等高級語言記述的逐次結構的輸入程序400,首先通過對該程序結構進行分析來分割為重複塊(RB: Repetition Block )、子程序(SB:Sub Routine )、偽賦值語句塊(BPA: Block of Pseudo Assignment statements )三個種類的粒度較大的宏任務(MT)，生成各宏任務(401)。 RB是各循環塊中各層最外側的循環，BPA是考慮調度開銷或者並行性，融合或者分割了由賦值語句形成的多個基本塊的塊。圖21中表示上述輸入程序(源程序400)的一例。
(Directive指定)
此外，在該源程序400中，可以預先記述PU的分配，例如還可以明確地指示將子程序分配給DSP,將另外某個子程序分配給CPU。結果，該DSP子程序通過編譯程序被進一步進行並行性的分析，例如在DSP為4個時，編
譯程序40對該4個DSP執行並行化調度。(數據依存 控制流分析)
然後，對分割生成的該宏任務之間的控制流以及數據依存性進行分析，提取宏任務MT的執行順序關係(402 )。圖21的輸入程序400因為是被逐次地進行記述，所以與該程序的結構相同地按照逐次的順序執行由通常的編譯程序40生成的執行代碼，當在宏任務MT之間來看時，很多情況不一定需要按照記述的順序來執行。
即，當在宏任務MT之間不存在控制或數據參照的依存性的情況下，特別在多處理器系統中，重要的是對多個PU配置多個宏任務MT,同時或者變更順序地進行調度，以使全體的動作時間縮短。
為了進行這樣的調度，需要對MT之間的並行性進行分析。因此，作為該分析的準備，通過數據依存 控制流分析處理402提取宏任務MT之間的^L行順序關係。
(循環級並行性分析)
然後，作為宏任務MT內的中粒度等級的並行性分析，進行循環級的並行化(403 )。在循環級並行化403中，對循環的重複(Iteration)單位間的數據依存性進行分析，判斷各重複是否可以獨立地進行處理，在為可以時，將各重複分配給多個PU來進4亍並ff處理。
此外，通過以下各種各樣的方法來實現循環的並行化將單一的循環分割為多個循環來提高並行性；或者通過數據的複製和數組變量的擴張，通過消除各個循環之間的數據依存性來進行並行化；或者將多個循環融合為單一的循環，由此減輕循環控制所需要的開銷。
(處理成本分析)
然後，進行對由各PU執行了上述生成的宏任務MT時所需要的處理周期進行估計的處理成本分析(404)。作為處理成本(運算成本)的估計方法，例如關於CPU等，將乘法運算或加法運算等命令級需要的周期數作為概要分析(profiling )信息保存在處理成本表420中，通過參照該表420可以估計由該PU才丸行宏任務MT時的逐次處理周期數。
24此外，在為DRP、 DSP等，難以對從程序中表現的命令級的周期數進行估計的情況下，該塊的程序對生成DRP、 DSP用執行代碼的各個本地編-澤程序進行一次調用，^^艮據轉換後的執行代碼進行概要分析，求出處理成本(413 )。此外，本地編譯程序對應PU的種類預先進行設定，例如，如果是DSP則使用DSP的本地編譯程序分析信息，如果是DRP則使用DRP的本地編譯程序概要分析信息。
此外，例如在包含分支的情況下，或者在循環的大小或數組的大小在宏任務MT執行前沒有被決定的情況下，還可以通過由本地編譯程序進行一次概要分析，來進行精度得到了提高的處理成本計算。此外，在不進行本概要分析，宏任務MT包含分支的情況下，將分支概率設為50%來進行成本計算。此外，在同樣不進行概要分析，循環或數組的大小沒有被決定的情況下，例如應用以下等方法將循環設為固定次數，此外設為數組宣言時的最大尺寸。
以上，將處理成本定義為處理周期數(時間)，此外，還可以通過將成本定義為功率，來進行功率為最小的調度。
例如，根據處理周期數和應該完成宏任務MT的處理期限，在可以設定的FV控制模式(頻率、動作電壓)中選擇在處理期限內為最小消耗功率的動作模式。或者，因為PU的消耗功率可以估計為
消耗功率=動作電壓2 x驅動頻率
所以可以選擇在處理期限內消耗功率為最小的FV控制模式的組合，進行調度。例如，如圖19b所示僅通過LOW模式執行處理的情況，和如圖19c所示對多個FV控制模式進行組合。或者，還可以選擇處理時間最短，並且消耗功率最小的FV控制模式的組合。
(宏任務間並行性分析=最早執行條件分析)
編譯程序40在宏任務MT的處理成本決定之後，根據同時對數據依存控制流分析處理402中提取出的宏任務MT之間的控制流和數據依存性進行分析後的結果，決定宏任務MT之間的並行性，即，決定可以最早執行各宏任務MT的條件(最早執行條件)(405 )。
在圖表中可視地表示該最早執行條件的是宏任務圖表(MTG)。圖22表示對圖21的輸入程序進行分析生成的MTG。此外，宏任務間並行性分析結
25果作為宏任務圖表表421被保存在外部存儲裝置中，在後面的編譯處理中使用。此外，該外部存儲裝置是指執行編譯程序40的未圖示的計算機自身。(宏任務圖表的說明)
以下，參照圖22對宏任務圖表MTG進行說明。本圖表中的各個節點表示宏任務MT,節點之間的實線表示宏任務之間的數據依存關係，節點之間的虛線表示宏任務之間的控制依存關係，節點內的小圓表示條件分支。例如，從宏任務MT1J (501)對MT1—2 (502)以及MT1—3 ( 503 )實現進行了延伸，這表示存在以下的依存關係粒度大的MT1—2以及MT1—3將執行MT1一1後生成的數據作為輸入數據使用，來執行處理。因此，作為執行順序，表示MT1—2以及MT1—3可以在MT1—1結束之後執行。
此外，從輸入程序400求出的宏任務MT1—2 ( 502),因為是由多個循環或子程序構成的粒度較大的塊，所以編譯程序40將該宏任務MT進一步分層地分割為多個宏任務MT。由此，在該宏任務圖表MTG中，在MT1—2中，在其他的分層中進一步構成宏任務圖表MTG1—2。宏任務MT1一3 ( 503 )也同樣地構成其他分層的宏任務圖表MTGMTG1 一3 。
當查看宏任務MT1—2 (502)內的宏任務圖表MTG1—2 (510)時，實線從任務MT1_2—1 (511 )向任務MT1—2—2 (512)、任務MT1一2—4 (514)以及任務MT1—2—5 (515)進行了延伸，所以可以在MT1—2—1 (511)結束之後同時扭J亍這些3個^壬務512、 514、 515。
此外，任務MT1—2_2 (512)還對任務MT1—2—3 (513)存在依存，這可以在MT1一2—2 (512)的任務結束之後執行MT1—2—3 (513)的任務。此外，實線從任務MT1—2—4 (514)以及MTL2—5 (515)對任務MT1—2—6 (516)進行延伸，所以可以在任務MT1—2—4 (514)以及MT1—2—5 (515)雙方的執行結束的時刻執行MT1—2—6 ( 516 )。
如上所述，在執行宏任務MTL2之前確定了並行順序關係，可以預先固定地(靜態地)調度任務。
然後，當查看宏任務MT1_3 ( 503 )內的宏任務圖表MTG (520)時，在宏任務MT1—3—1 (521)中存在小圓，這表示任務MT1—3—1 (521)包含條件分支。具有箭頭的虛線從小圓向任務MT1—3 2 ( 522)、 MT1—3_5 ( 525 )延伸，此外，對控制依存的OR條件進行表示的點劃線的弧線529重合，所以表示該條件分支為任務MT1—3—2或MT1—3—5中的某一個。
此外，沒有箭頭的虛線向任務MTl_3—3 ( 523 )延伸，表示控制依存的AND條件的實線的弧線528在向任務MT1—3—3 ( 523 )的沒有箭頭的該虛線和與任務MT1一3—2 ( 522)連接的虛線上重合。這表示如果在該條件下，向箭頭所指的任務MT1—3一2的方向分支，則可以同時執行控制依存於同一分支的任務MT1一3—3。此外，圖中的虛線表示了對任務的執行進行確定的控制依存關係，和不執行數據依存的任務時的條件。此外，帶有箭頭的虛線表示與通過數據依存.控制流解析(402)求出的控制流相同(即，原始的)的情況。
此外，任務MT1—3—1 (521)的條件分支因為在不執行該任務MT1—3一1時分支方向不確定，所以需要進行與執行時的狀況對應的調度。在該條件分支確定，向任務MT1—3_2 (522)以及任務MT1—3—3 ( 523 )的方向分支時，具有從任務MT1—3—2 ( 522 )以及任務MT1—3—3 ( 523 )到任務MT1_3—4 ( 524 )表示數據依存關係的實線，因此，可以在任務MT(522、 523 )雙方的處理結束的時刻執行MT1—3_4 ( 524 )的處理。
此外，在向任務MT1—3一5 ( 525 )的方向分支時，同樣地，可以根據依存關係在該任務525結束的時刻執行任務MT1—3__6( 526 )以及任務MT1一3一7(527)的處理。(處理器分組)
然後，編譯程序40參照所生成的宏任務圖表MTG表421，進行與宏任務圖表的形狀、並行性對應的，或者與用戶的指定對應的處理器分組(406)。
即，對在宏任務圖表MTG中表現的上位層的宏任務MT，例如宏任務MT1—2 (502)、 MT1—3 (503 )的形狀、並行性進行分析，對該宏任務MT的處理所需要的PU10-17進行分組，並對該分組分配任務MT。此外， 一個組成為至少包含一個用於對該分組內的特定用途處理器(DSP、 DRP、 BMP)進行控制的通用處理器(CPU)的集合。具體地說，在可以根據宏任務圖表MTG的結構，在進行編譯時判斷恰當的處理器PU的分組結構時，便宜程序40進行包含了特性用途處理器的分組。
此外，在根據宏任務圖表MTG的結構，在編譯時無法進行處理器分組時，即，在存在多層應該使用特定用途處理器的任務，無法恰當地進行分組的情況下，在進行編譯時，編譯程序40或者在執行時起到調度器作用的通用處理器，將任務對特定用途處理器組進行分配。此時，在向特定用途處理器的負荷較大的情況下，由通用處理器代為進行處理。此外，已決定的分組信
息，作為處理器分組表422保存在外部存儲裝置中，在後面的處理中使用。
在本實施方式中，在圖22的宏任務圖表MTG1 (500)中宏任務MT1—2(502)和MT1—3 (503 )的處理成本相同，為了執行這些宏任務內部的宏任
務圖表MTG1—2 (510)、 MTG1—3 ( 520),需要通過通用處理器的特定用途處
理器的控制，所以定義兩個處理器分組。
然後，根據宏任務MT1—2、 MT1一3對於各PU的處理成本、並行性，決
定在各處理器分組內所需要的特定用途處理器的構成。在本實施方式中，因
為可以通過宏任務圖表MTG1上可以利用的資源來實現所需要的處理器構
成，所以在編譯時將處理器分組決定為CPU0、DSP0、DRP0、DRP1以及CPU1、
DSP1、 BMPO、 BMP1。
(靜態調度和動態調度)
然後，編譯程序40接著作為調度方法，判斷是靜態調度還是動態調度(407)。在後面對各個調度方法進行詳細說明，而在下面先進行簡單的說明。首先，如果是在任務MT中沒有條件分支可以預先決定最早執行條件的MT流，則應用前者的靜態調度，編譯程序40預先進行任務MT的調度，在任務之間插入同步代碼以及FV控制代碼(調度代碼)。
此外，如果是在任務MT中具有條件分支，或者任務MT的處理時間在執行時進行變動等，在編^澤時無法預測的MT流，則應用後者的動態調度，編譯程序40生成在執行時進行與分支等的狀況對應的控制的調度程序。編譯程序40生成調度程序(調度代碼)的優點在於，如現有的多處理器那樣，在向OS或程序庫委託生成粗粒度任務，委託進行調度時，有可能產生數千至數萬個時鐘的開銷，而編譯程序40生成調度程序就可以避免該情況。(靜態調度)
首先，對靜態調度的處理流進行說明。在靜態調度中，因為在編譯時已經決定了任務MT的分配和執行順序，所以，首先通過宏任務調度處理408參照宏任務表421以及處理器分組表422,生成用於進行PU之間的執行任務間的同步和進行其他任務的啟動等的控制信息，決定該控制信息的插入部位。此外，還將任務程序或任務所需要的數據與從其他PU的本地存儲器LM、共享存儲器SM載入該PU的本地存儲器LM的數據傳送信息一同生成。通過這樣的數據定位方法，來有效地使用本地存儲器LM,使數據的傳輸量最小化。通過以上處理生成的調度信息作為宏任務調度表423保存在外部存儲裝置中。
然後，編譯程序40進行靜態FV調度處理409。在本處理中，根據圖18a ~圖18d中說明的執行並行處理時的FV控制概念，根據由宏任務調度408生成的調度信息(宏任務調度表)判定由任務的處理成本以及調度期限(處理期限)決定的餘裕度，並對決定與該餘裕度對應的動作頻率.供給電壓的PU動作模式進行設定，因此，生成FV控制信息。該FV控制信息作為電源.FV控制調度表被保存在外部存儲裝置中。此外，餘裕度，例如是根據從執行開始到執行結束的處理時間和到處理期限為止的時間求出的，表示各PU10 7性能上的餘裕的程度。例如，如圖19a所示，在從CPUO的執行結束到處理期限的時間較長時可以判定餘裕度較大，相反，在從執行結束到處理期限的時間較短時可以判定餘裕度較小。
此外，處理期限(允許時間)可以由輸入程序記述，也可以在編^^程序40的處理時由未圖示的控制臺輸入。
(動態調度)
然後，對動態調度的處理流進行說明。在動態調度時，由於任務MT內的條件分支等不確定要素，無法在編譯時決定調度內容。因此，控制程序40根據任務MT的處理結果生成在執行程序時動態地進行調度的調度程序(410)。本程序根據處理結果，進行任務MT的啟動和同步、以及該MT所需要的數據的裝入。此外，還根據圖18a 圖18d說明的任務並行處理執行時的FV控制概念，對決定PU的動作頻率 供給電壓的動作模式(FV控制模式)進行設定。生成的調度程序作為電源'FV控制調度表424保存在外部存儲裝置中。
(調度代碼的生成)
29421 ~ 424 )進行訪問，讀入任務的執行順序和數據傳送信息以及FV控制信息，對於輸入程序在靜態調度部中附加控制代碼(調度代碼)，此外在動態調度部中附加調度程序(411)。例如，使用作為分散存儲器型並行計算機中的並行編程標準接口的MPI ( Message PassingInterface)等生成控制代碼。附加了該代碼的輸入程序還通過對各個PU的每個種類準備的本地編:澤程序進行處理，由此轉換為該PU中的執行二進位代碼。此外，本地編譯程序如上所述，預先對CPU、 DSP、 DRP、 BMP的PU的每個種類進行準備，由編譯程序40調用與各PU的種類對應的本地編譯程序，來生成執行二進位代碼。(調度的結果)
圖23表示本調度結果的例子。圖23以時間軸對每個PU表示MT的調度結果。在本例中，CPUO進行任務的啟動、同步以及FV控制等管理，所以最初在CPUO上加載編i爭程序40生成的控制代碼550。該控制代碼550由進
即，CPUO為了對執行宏任務MTl一l的CPUO將動作模式置為FULL,將FV控制寄存器的值設定為"3"。此外，因為對於其他的PU不存在應該處理的MT,所以將FV控制寄存器的值設定為"0",來將動作模式置為OFF。然後，CPUO通過自身CPUO開始宏任務MT1_1的處理。
在通過CPUO進行的宏任務MT1—1的處理結束之後，執行編譯程序40生成的控制代碼551,來進行FV控制模式的設定。然後應該處理的任務是由宏任務MT1一2以及MT1一3的下層的宏任務圖表MTG指定的任務MT1—2—1以及任務MT1—3—1,前者由CPUO執行，後者由CPU1執行。
因此，CPUO將對任務MT1_3—1進行處理的CPU1的FV控制寄存器設定為通常模式(FULL)。此外，關於CPUO,雖然FV控制模式也已經為通常模式，但為了處理後續MT1—2—1,所以置為通常模式(FULL)。
此時，在所述任務MTL2—1以及所述任務MTL3—1的處理中，因為不存在其他PU上的處理任務，所以該其他的PU將後續動作模式置為OFF。然
30後，CPU0在自身開始任務MTl—2—1的處理，此外在CPUl中開始任務MTl—3—1的處理。
此外，如上所述，因為宏任務MTG1—2不包含條件分支，所以已經在編譯時進行了調度(靜態調度)，對CPUO、 DSPO、 DRPO、 DPI分組分配任務MT。此外，因為在宏任務MTG1一3中包含條件分支，所以附加在執行時進行調度的程序，根據執行結果對CPU1、 DSP1、 BMP0、 BMP1分組分配任務MT。
然後，對宏任務圖表MTG1一2的任務MT分組的調度進行說明。當任務MT1一2J的執行在CPU0中結束時，CPUO執行控制代碼552，為了處理任務MT1一2—2將FV控制寄存器設定為"3",以使DSP0置為通常動作模式。此外，對於任務MT1—2—4以及MT1—2_5,根據通過編譯時的FV調度進行的任務的餘裕度判定，將FV控制寄存器設定為"2",以將DSP0、 DRP0以及DRP1置為低功率動作模式MIDDLE。此外，雖然在CPUO中沒有應該執行的任務，但為了進行DSPO、 DRPO以及DRP1的任務的同步管理，調度程序對於CPUO將FV控制寄存器設定為'T，，以將其置為低功率動作模式LOW。然後，開始進行任務MTl—2—2、任務MT1—2—4以及任務MT1—2—5的處理。此外，因為在任務MT1—2—2的處理結束之後，同樣地在DSPO中執行任務MT1—2—3，
MTl—2—2結束之後啟動任務MT1一2—3。
然後，當CPUO判定所述任務MT1一2—4以及任務MTl—2—5的處理雙方已經結束時，該CPUO執行控制代碼553, CPUO將處理任務MTl—2—6的自身CPUO的動作模式設定為MIDDLE,此外，由於DRPO以及DRP1不存在應該處理的任務，所以將動作模式設定為OFF,在與通常相比降低了電壓和動作頻率的狀態下開始所述任務MT1_2—6的處理。當所述任務MT1一2—6的處理結束時，CPUO執行控制代碼554,在判定為任務MT1一2—3的處理結束時，因為MTG1—2分組內的任務處理已經結束，所以CPUO將DSPO的動作模式設定為OFF。
然後，對MTG1_3的任務MT分組進行說明。因為宏任務MT1一3在內部具有分支，所以不執行任務時無法得知分支方向。因此，在CPUl中執行用於根據執行時的狀況進行任務、數據的裝入、任務的啟動、同步以及FV
控制代碼的管理等的動態調度程序。因為首先執行任務MT1一3—1，所以該調 度程序555將CPU1的動作模式設定為FULL,啟動任務MT1—3—1。在任務 MT1_3—1的執行結束之後，調度程序556判定分支方向，判定然後啟動的任 務。
在圖23表示的調度中，任務MT1—3—2由DSP1處理，任務MT1—3—3由 BMP0處理。在該處理啟動之前，調度程序556"^姿照FV調度結果將DSP1的 動作模式設定為FULL,此外，將BMPO的動作模式設定為LOW。雖然在 CPU1中沒有應該執行的任務MT，但因為執行調度程序556進行DSP1以及 BMPO的任務管理，所以調度程序556將CPU1的動作模式設定為低功率模 式LOW。
務MT1—3—3雙方的處理結束時，將接著對任務MT1一3—4進行處理的自身 CPUO的動作模式(FV控制模式)設定為FULL,此外，將不存在應該執行 的任務的DSP1以及BMPO的動作模式設定為OFF。然後，在自身CPU0中 執行所述任務MT1—3—4。
根據以上，在由不同種類的PU10~ 17構成的多處理器中，在通過多粒 度並行處理，為了使執行時間最短而對輸入程序進行並行化並進行了調度之 後，對每個PU極細緻地進行動作頻率控制以及電源管理以使在各PU之間處 理時間均一，由此，可以以最短的執行時間無損性能地實現消耗功率的降低。 (編譯程序生成的目的程序)
在圖24以及圖25中表示通過編譯程序40將用於進行如上所述的調度的 調度代碼附加給輸入程序400,對每個PU輸出的輸出程序(目的代碼)的一 例。圖24、圖25對在上述圖23中表示的處理進行記述，圖24作為對宏任 務MTG1—2進行處理的處理器的分組，表示CPU0、 DSP0、 DRP0、 DRP1各 個PU用執行代碼。此外，圖25作為對宏任務MTG1—3進行處理的處理器的 分組，表示CPU1、 DSP1、 BMP0、 BMP1各個PU用執行代碼。編譯程序40 的生成代碼由偽代碼來表現，如上所述，實際上是按照MPI等接口規格進行 表現。 '(O士 、
如上所述，根據本發明，在集成多種處理器單元PU的多處理器系統中， 通過使PU高效動作的程序的分割配置以及生成控制代碼的編譯程序40，可 以最大限度地發揮該多處理器系統的性能，並且可以在最小限度的處理時間 內以低功率高效地進行處理。此外，無需軟體開發者識別處理單元的結構， 可以在短時間內極其高效地生成程序。 (補充)
此外，在上述實施方式中，表示了將本發明用於在一個晶片中具備多個 PU10-17的多處理器系統的例子，但還可以用於圖1所示的具備多個晶片的 並行計算機中，可以得到與上述相同的作用效果。
此外， 一種多粒度並行化編譯方法，根據對所述每個處理器單元設定的 分析信息求出處理所述單位塊的處理周期數，根據該處理周期求出所述運算 周期時間。
此外， 一種多粒度並行化編譯方法，所述運算周期時間，通過對所述每 個處理器單元設定的本地編譯程序將所述單位塊轉換為執行代碼，根據對所 述每個處理器單元設定的分析信息求出對所述單位塊進行處理的處理周期 數，根據該處理周期數求出所述運算周期時間。
此外， 一種多粒度並行化編譯方法，根據對所述每個處理器單元設定的 分析信息求出對所述單位塊進行處理的處理周期數，^^艮據該處理周期求出所 述功率。
此外， 一種多粒度並行化編譯方法，所述運算周期時間，通過對所述每
述每個處理器單元設定的分析信息求出對所述單位塊進行處理的處理周期 數，根據該處理周期數求出所述功率。
此外， 一種多粒度並行化編譯方法，提取所述單位塊的並行性的處理包 含將所述提取出的單位塊存儲在宏任務圖表表中，對處理所述單位塊所需 要的處理器單元進行分組，來存儲在處理器分組表中的處理，
生成所述調度代碼的處理，包含參照所述宏任務圖表表和處理器分組 表以及代碼信息，生成處理器單元的控制代碼的處理；和對應所述單位塊的
33執行順序插入所述控制^C碼的處理。
此外， 一種多粒度並行化編譯方法，提取所述單位塊的並行性的處理包 含將所述提取出的單位塊存儲在宏任務圖表表中，對處理所述單位塊所需 要的處理器單元進行分組，來存儲在處理器分組表中的處理，
生成所述調度代碼的處理，包含參照所述宏任務圖表表和處理器分組 表以及代碼信息，生成動態地進行所述單位塊的調度的調度程序的處理；和 對應所述單位塊的l^f於順序插入所述調度程序的處理。
產業上利用的可能性
根據本發明，在集成了多個種類的PU的多處理器系統中，通過使該PU 高效動作的程序的分割裝置以及生成控制代碼的編譯方法，可以最大限度地 發揮該多處理器系統的性能，並且可以以較低的功率高效地進行處理。此外， 無需軟體開發者意識處理單元的結構，就可以在短時間內高效地生成程序。 結果，可以將本發明用於被強烈希望具有高運算性能並且低功率進行處理的、 面向車輛導4元系統、行動電話、信息家電的LSI，可以實現高質量的動畫圖 像和聲音處理、以及圖像識別和聲音識別等功能。對於面向汽車的信息系統、 控制系統的LSI也可以適用，可以實現自動運轉、安全運轉系統等。此外， 還可以用於將來需要具有非常高的運算性能並且低功率化的超級計算機。
權利要求
1. 一種多粒度並行化編譯方法，其生成在具有多個單一或多種類的處理器單元的多處理器系統上執行的目的程序，其特徵在於，所述處理器單元，包含特定用途處理器單元和通用處理器單元，所述多粒度並行化編譯方法包括以下步驟讀入輸入程序的處理；對所述輸入程序進行分析，將所述輸入程序分割為多個粒度的單位塊的處理；對所述單位塊之間的控制依存性以及數據依存性進行分析，提取所述單位塊的並行性的處理；將在所述多處理器系統具備的各個處理器單元中處理所述塊單位所需要的運算周期時間或功率作為成本信息來求出的處理；根據所述成本信息，為使所述輸入程序的處理時間成為最小，選擇處理所述單位塊所需要的所述特定用途處理器單元，並且選擇至少一個通用處理器單元，生成將這些特定用途處理器單元和通用處理器單元作為一個分組來分配所述單位塊的調度代碼的處理；和將所述調度代碼附加給輸入程序，生成所述每個處理器單元的執行代碼，將其作為目的代碼進行輸出的處理。
2. 根據權利要求1所述的多粒度並行化編譯方法，其特徵在於， 生成所述調度代碼的處理，包含以下的處理在用通過調度分配了所述單位塊的處理器單元進行運算時，在所述運算 所需要的時間在所述調度允許的時間之內時，為了降低所述處理器單元進行運算時消耗的功率，生成用於變化或者切 斷給予處理器單元的動作電壓以及動作時鐘的控制代碼。
3. 根據權利要求1所述的多粒度並行化編譯方法，其特徵在於， 生成所述調度代碼的處理，對於通過調度分配了所述單位塊的處理器單無之外的處理器單元，生成 用於切斷動作時鐘以及動作電壓的供給的控制代碼。
4. 根據權利要求1所述的多粒度並行化編譯方法，其特徵在於，生成所述執行代碼、將其作為目的代碼進行輸出的處理為使用與所述各個處理器單元的種類對應的本地編譯程序來生成所述執行 代碼。
5. 根據權利要求1所述的多粒度並行化編譯方法，其特徵在於， 所述多處理器系統，具有將多個時鐘頻率中的一個作為動作時鐘供給所述處理器單元的時鐘供給部；將多個電壓中的一個作為動作電壓供給所述 處理器單元的功率供給部；和對所述時鐘供給部以及功率供給部對處理器單 元供給的動作時鐘和動作電壓進行設定的系統控制寄存器； 生成所述調度代碼的處理，包含以下的處理在用通過調度分配了所述單位塊的處理器單元進行運算時，在所述運算 所需要的時間在所述調度允許的時間之內時，為了降低所述處理器單元進行運算時消耗的功率，生成對在所述系統控 制寄存器中設定的值進行變更的控制代碼。
全文摘要
本發明提供了一種多粒度並行化編譯方法。在多處理器系統中，由編譯程序從成為處理對象的輸入程序中自動提取具有並行性的任務，並通過按照各個處理器單元的特性配置該任務，由此，進行使該處理器單元高效動作的調度，而且，通過估計該處理器單元的處理量，生成使動作頻率、電源電壓最佳化的代碼。
文檔編號G06F9/50GK101504619SQ20091000753
公開日2009年8月12日 申請日期2006年4月12日 優先權日2005年4月12日
發明者伊藤雅樹, 木村啟二, 白子準, 笠原博德, 鹿野裕明 申請人:學校法人早稻田大學