用於稀疏矩陣的自動重新排序的技術的製作方法

2023-11-08 07:03:27 2

背景技術：

稀疏數據結構（諸如圖和稀疏矩陣）上的高性能計算（hpc）在例如包含機器學習、計算科學、物理模型模擬、web搜索以及知識發現的廣泛領域中正在變得越來越重要。傳統高性能計算應用一般涉及規則和密集數據結構；然而，稀疏計算具有某些獨一無二的挑戰。例如，稀疏計算通常比密集計算具有低得多的計算密度，並且因此，其性能經常受存儲帶寬的限制。此外，存儲器存取模式和並行度的量變化很大，例如取決於輸入數據的特定稀疏度模式，這使優化複雜化了，因為某些優化信息經常是未知的先驗。

系統可修改輸入數據集以獲得高數據局部性，以便處理那些挑戰。例如，系統可採用重新排序，其置換矩陣的行和/或列以便集群彼此附近的非零項。例如，系統可重新排序稀疏矩陣100以生成帶狀矩陣102，其中非零項104在彼此附近群集，如圖1a-b所示的。通過這麼做，系統增大了具體存儲器讀取涉及更多非零項（即空間局部性）的機會，並且可導致比沒有重新排序在高速緩存當中更多的再用（即時間局部性）。已經開發並實現了各種重新排序算法，例如包含廣度優先搜索（bfs）、反向cuthill-mckee(rcm)、自迴避行走（saw）、metis劃分器和king's算法。具體地說，bfs及其更精細版本rcm由於其較小的複雜性和較大的效率而被頻繁用於優化稀疏矩陣向量乘法(spmv)中的高速緩存局部性。

附圖說明

本文描述的概念在附圖中作為示例而非作為限制圖示。為了圖示的簡潔和清晰起見，在附圖中圖示的元件不一定按比例繪製。視情況而定，附圖標記在圖之間已經被重複了以指示對應或類似元件。

圖1a是稀疏矩陣的至少一個實施例的簡化圖解；

圖1b是重新排序的稀疏矩陣的至少一個實施例的簡化圖解；

圖2是用於稀疏矩陣的自動重新排序的計算裝置的至少一個實施例的簡化框圖；

圖3是圖2的計算裝置的環境的至少一個實施例的簡化框圖；

圖4a是程序代碼段的至少一個實施例；

圖4b-4c是圖4a的程序代碼段的重新排序版本的實施例；

圖5是可由圖2的計算裝置執行的用於稀疏矩陣的自動重新排序的方法的至少一個實施例的簡化流程圖；

圖6是可由圖2的計算裝置執行的用於執行相互依賴的陣列（array）分析的方法的至少一個實施例的簡化流程圖；

圖7a是表達式（expression）樹的至少一個實施例的簡化圖解；

圖7b是根據圖7a的表達式樹生成的表達式子樹的集合的至少一個實施例的簡化圖解；

圖8是可由圖2的計算裝置執行的用於執行雙向數據流分析的方法的至少一個實施例的簡化流程圖；

圖9是來自應用雙向分析以便發現可重新排序陣列的結果的至少一個實施例的部分表；

圖10是代碼區域中程序代碼的簡化框圖；

圖11是來自向圖10的程序代碼應用沒有優化的雙向分析的結果的至少一個實施例的部分表；

圖12是基於圖11的沒有優化的雙向分析的結果的圖10的程序代碼的重新排序版本的簡化框圖；

圖13是來自基於活性向圖10的程序代碼應用沒有優化的雙向分析的結果的至少一個實施例的部分表；

圖14是基於圖13的基於活性的具有優化的雙向分析的結果的圖10的程序代碼的重新排序版本的簡化框圖；

圖15是來自基於執行頻率向圖10的程序代碼應用具有優化的雙向分析的結果的至少一個實施例的部分表；

圖16是基於圖15的基於執行頻率的具有優化的雙向分析的結果的圖10的程序代碼的重新排序版本的簡化框圖。

具體實施方式

雖然本公開的概念易受到各種修改和備選形式，但其特定實施例已經在附圖中作為示例示出，並且將在本文中詳細描述。然而，應該理解，沒有意圖將本公開的概念局限於所公開的具體形式，而是相反，本發明要覆蓋與本公開和所附權利要求書一致的所有修改、等效方案和備選。

在說明書中提到「一個實施例」、「實施例」、「圖示實施例」等指示所描述的實施例可包含具體特徵、結構或特性，但每一個實施例可以或者可以不必需包含該具體特徵、結構或特性。而且，此類短語不一定是指同一實施例。進一步說，當具體特徵、結構或特性結合實施例進行描述時，認為它在本領域技術人員的認知之內，以結合其它實施例實現此類特徵、結構或特性，不管是否明確描述了。此外，應該認識到，包含在以「a、b和c中的至少一個」的形式的列表中的術語可意味著(a)；(b)；(c)；(a和b)；（b和c）；(a和c)或(a,b和c)。類似地，包含在以「a、b或c中的至少一個」形式的列表中的術語可意味著(a)；(b)；(c)；(a和b)；（b和c）；(a和c)或(a,b和c)。

所公開的實施例在一些情況下可用硬體、固件、軟體或它們的任何組合來實現。所公開的實施例也可實現為由一個或多個暫時性或非暫時性機器可讀（例如計算機可讀）存儲介質攜帶或存儲在其上的指令，其可由一個或多個處理器讀取和執行。機器可讀存儲介質可實施為用於存儲或傳輸由機器（例如易失性或非易失性存儲器、媒體盤或其它媒體裝置）可讀形式的信息的任何存儲裝置、機制或其它物理結構。

在附圖中，一些結構或方法特徵可按特定布置和/或排序示出。然而，應該認識到，可能不需要此類特定布置和/或排序。而是，在一些實施例中，此類特徵可按與在說明性附圖中示出的不同的方式和/或次序布置。此外，在具體附圖中包含結構或方法特徵不打算暗示此類特徵在所有實施例中都需要，並且在一些實施例中，可能不被包含或者可與其它特徵組合。

現在參考圖2，示出了用於稀疏矩陣的自動重新排序的計算裝置200。如下面所詳細描述的，計算裝置200配置成將本文描述的一個或多個算法自動應用於任意重新排序函數（例如用於加速稀疏內核的執行）以自動確定重新排序是否對任意函數都可應用/可準許，並且如果是，則施加一個或多個算法，無需改變一個或多個基礎表達式的語義。應該認識到，此類自動重新排序技術甚至可改進專家編程人員的能力和/或效率，例如通過消除或減少對於人工重新排序優化的需要，其經常是易錯的並且耗時的過程。在說明性實施例中，計算裝置200通過如下方式確定重新排序的可行性：確認所關注的具體代碼區域中的語句是分布性的，並且如果是這樣，則識別在代碼區域之前、之後和/或之內的要重新排序和/或反向重新排序的一個或多個陣列（例如多維矩陣和/或一維向量），使得代碼區域外部的代碼不受重新排序影響。

計算裝置200可被實施為能夠執行本文描述的功能的任何類型計算裝置或系統。例如，在一些實施例中，計算裝置200可被實施為桌上型計算機、膝上型計算機、平板計算機、筆記本、上網本、ultrabook™、智慧型電話、蜂窩電話、可穿戴計算裝置、個人數字助理、移動網際網路裝置、智能裝置、伺服器、路由器、交換機、混合裝置和/或任何其它計算/通信裝置。如圖2中所示，說明性計算裝置200包含處理器210、輸入/輸出("i/o")子系統212、存儲器214、數據存儲裝置216、通信電路118和一個或多個外圍裝置220。當然，在其它實施例中，計算裝置200可包含其它或附加組件，諸如通常在典型計算裝置(例如各種輸入/輸出裝置和/或其它組件)中發現的那些。此外，在一些實施例中，說明性組件的一個或多個可結合在另一組件中，或以其它方式形成另一組件的一部分。例如，在一些實施例中，存儲器214或其部分可被結合在處理器210中。

處理器210可被實施為能夠執行本文描述的功能的任何類型處理器。例如，處理器210可實施為單核或多核處理器（一個或多個）、數位訊號處理器、微控制器或其它處理器或處理/控制電路。類似地，存儲器214可實施為能夠執行本文描述的功能的任何類型易失性或非易失性存儲器或數據存儲裝置。在操作中，存儲器214可存儲在計算裝置200操作期間使用的各種數據和軟體，諸如作業系統、應用、程序、庫以及驅動程序。存儲器214以通信方式經由i/o子系統212耦合到處理器210，i/o子系統可實施為電路和/或組件以促進與計算裝置200的處理器210、存儲器214和/或其它組件的輸入/輸出操作。例如，i/o子系統212可實施為或以其它方式包含存儲器控制器集線器、輸入/輸出控制集線器、固件裝置、通信鏈路（即，點對點鏈路、總線鏈路、導線、電纜、光導、印刷電路板跡線等）和/或其它組件和子系統以促進輸入/輸出操作。在一些實施例中，i/o子系統212可形成片上系統(soc)的一部分，並與計算裝置200的處理器210、存儲器214和其它組件一起結合在單個集成電路晶片上。

數據存儲裝置216可實施為配置用於數據的短期存儲或長期存儲的任何類型裝置（一個或多個），諸如例如存儲器件和電路、存儲卡、硬碟驅動器、固態驅動器或其它數據存儲裝置。數據存儲裝置216和/或存儲器214可在如本文所描述的計算裝置200的操作期間存儲各種數據。

通信電路218可實施為能夠實現通過網絡在計算裝置200與其它移動裝置之間通信的任何通信電路、裝置或它們的集成。例如，在一些實施例中，計算裝置200可從遠程計算裝置接收用戶程序、要重新排序的第一陣列（far）的身份和/或用於執行本文描述的函數的其它有用數據。通信電路218可配置成使用任一個或多個通信技術（例如無線或有線通信）以及關聯的協議（例如乙太網、bluetooth®、wi-fi®、wimax、lte、5g等）來實現此類通信。

外圍裝置220可包含任何數量的傳統外圍裝置或接口裝置，諸如揚聲器、麥克風、附加存儲裝置等。包含在外圍裝置220中的具體裝置例如可取決於計算裝置200的類型和/或預期用途。

現在參考圖3，在使用中，計算裝置200建立用於稀疏矩陣的自動重新排序的環境300。說明性環境300包含區域標識模塊302、分布性分析模塊304、活性分析模塊306、相互依賴的陣列分析模塊308、可重新排序陣列發現模塊310和代碼變換模塊312。環境300的各種模塊可實施為硬體、軟體、固件或它們的組合。例如，環境300的各種模塊、邏輯和其它組件可形成處理器210或計算裝置200的其它硬體組件的一部分，或者以其它方式由其建立。像這樣，在一些實施例中，環境300的一個或多個模塊可實施為電路或電氣裝置的集合（例如標識電路302、分布性分析電路304、活性分析電路306、相互依賴的陣列分析電路308、可重新排序陣列發現電路310和/或代碼變換電路312）。應該認識到，在此類實施例中，標識電路302、分布性分析電路304、活性分析電路306、相互依賴的陣列分析電路308、可重新排序陣列發現電路310和/或代碼變換電路312中的一個或多個可形成處理器210、i/o子系統212、存儲器214、數據存儲裝置216、通信電路218和/或外圍裝置220中的一個或多個的一部分。此外，在一些實施例中，說明性模塊的一個或多個可形成另一模塊的一部分，和/或說明性模塊的一個或多個可彼此獨立。如圖3所示的，在一些實施例中，環境300的各種模塊的一個或多個可形成計算裝置200的編譯器314的一部分，或由其執行。

如本文所描述的，計算裝置200配置成例如向程序的代碼區域施加重新排序變換以便改進程序的執行時間。區域標識模塊302配置成識別要分析的代碼區域以便重新排序。應該認識到，代碼區域可以是任意表達式、塊、語句、語句/指令的集合/序列和/或程序的另一部分。例如，在一些實施例中，代碼區域可包含順序語句、循環語句（例如「for」、「repeat...until」、「while」等）、流控制語句（例如,「if...else」、「goto」、「break」、「exit」等）和/或其它語句。更確切地說，在一些實施例中，區域標識模塊302選擇不包含流語句作為代碼區域的線性循環區域。另外，在一些實施例中，區域標識模塊302可選擇其中程序花費了大量其執行時間（例如至少持續閾值時間段、至少持續閾值數量的時鐘周期和/或以其它方式確定的）的代碼區域。為了便於論述，取決於具體語境，在說明書通篇可互換使用術語「表達式」、「塊」和/或「語句」。

應該認識到，重新排序變換可通過在代碼區域內使用之前對一些陣列重新排序來影響代碼區域。此外，可在代碼區域之後使用的陣列可被反向重新排序（即，可施加重新排序的反向運算以將重新排序的陣列返回到其初始狀態），以確保代碼區域外部的程序代碼不受影響。另外，如果代碼區域包含流控制語句，則一個或多個陣列可沿代碼區域中的各種路徑排序和/或視情況而定反向重新排序以考慮到此類語句。在代碼區域是線性循環區域的一些實施例中，重新排序可僅發生在代碼區域外部。

圖4a中示出了程序代碼400的部分的示範實施例。如所示的，通用代碼區域400包含由區域標識模塊302識別的代碼區域402以及所識別的代碼區402外部的「print(x)」語句。應該認識到，代碼區域402包含外部循環語句以及外部循環語句內的各種操作語句。如本文所描述的，在代碼區域中使用的變量/陣列的一個或多個可被重新排序，其影響在程序代碼400中呈現的語句/指令。例如，在一些實施例中，重新排序可涉及在代碼區域402內插入「reorder」語句和/或「reverse_reorder」語句（如圖4b所示的）（例如，除了將此類語句插入在代碼區域402外部）以生成程序代碼400的修改版本。在其它實施例中，重新排序可僅涉及將此類重新排序語句插入在代碼區域402（例如線性循環區域）外部（如圖4c中所示的）（例如緊接在代碼區域402之前和之後）以生成程序代碼400的修改版本。

分布性分析模塊304配置成確定在所識別的代碼區域中定義的表達式的一個或多個（例如每個）的分布性。也就是，分布性分析模塊304可掃描代碼區域中的所有表達式，並且確定重新排序是否在每個表達式上都是分布性的。在說明性實施例中，定義重新排序r可根據：如果x是矩陣（即相似性變換），則；如果x是向量，則；或者如果x是標量數字，則，其中p是置換矩陣，並且是p的轉置/逆。另外，在說明性實施例中，如果其語義保持不變，則表達式上的重新排序r是分布性的（不管其輸出是否被重新排序和/或其輸入是否被重新排序）。換言之，，其中是輸入的集合。

在一些實施例中，沒有流控制語句的代碼區域可被共同解釋為單個表達式。如果重新排序在具體代碼區域中的所有表達式上都是分布性的，則應該認識到，重新排序在作為說明性實施例中的共同表達式的整個區域上也是分布性的。像這樣，為了對代碼區域的結果重新排序，計算裝置200可對到代碼區域的輸入重新排序，無需修改區域內部的代碼。在代碼區域的確包含流控制語句的實施例中，輸入的一個或多個可能是有條件的，並且因此，那些輸入的重新排序可能也是有條件的（例如參見圖4b）。

應該認識到，一些常見的陣列相關表達式經常是分布性的。例如，表達式、、、、、、、、和一般是分布性的，其中m和n是矩陣，v和w是向量，並且n是標量數字。此外，重新排序在沒有輸入和輸出的表達式（例如條件「if(n)」和「goto」語句）上和在具有標量輸入和輸出的表達式上一般是分布性的。相比之下，一些其它常見的陣列相關的表達式不是分布性的。例如，要求輸入和/或輸出是具體「形狀」（例如假定輸入是上三角矩陣或下三角矩陣的三角求解器）的表達式、輸入/輸出表達式（例如列印命令）、要求逐位可再生性的表達式和/或對編譯器314未知的函數一般可被視為非分布性的。應該認識到，如果用於具體用戶定義的函數的原始碼可用，則原始碼可與本文描述的技術一致地進行分析以確定其分布性。儘管代碼區域形成/標識和分布性分析在本文分開進行描述，但在一些實施例中，代碼區域形成和分布性可同時進行分析。例如，在一些實施例中，計算裝置200可開始於空區域，並且通過添加確認為分布性的語句來逐步「生長」區域。

活性分析模塊306配置成確定在代碼區域內一個或多個位置的一個或多個（例如每個）變量/陣列的活性（即，變量/陣列是活的還是死的）。例如，在一些實施例中，活性分析模塊306可以確定在代碼區域中的每個語句/表達式之前和/或之後的每個變量的活性。在說明性實施例中，變量/陣列被視為在程序代碼中的具體編程點是活的，如果有可能該變量在將來（即在那個編程點之後）將被使用的話。應該認識到，計算裝置200（例如編譯器314）可利用用於確定變量活性的任何適合的技術、算法和/或機制。

相互依賴的陣列分析模塊308配置成分析具體表達式以構造或者以其它方式確定表達式的相互依賴的陣列/變量的集群。在說明性實施例中，陣列的集合被視為彼此相互依賴的，如果那些陣列中的任何陣列的重新排序都會使其它陣列的重新排序成為必要的話。例如，如果表達式中的稀疏矩陣a被重新排序（例如一些列和/或行被交換），則向量x和y必須被重新排序。類似地，如果x或y重新排序，則a必須相應地重新排序。應該認識到，一般而言，向另一陣列指配涉及一個或多個陣列的表達式的語句指示那些陣列中每個陣列之間的相互依賴性。例如，如果代碼區域包含語句，其中是陣列和的表達式，則陣列、和是相互依賴的陣列。如下面所更詳細描述的，在一些實施例中，相互依賴的陣列分析模塊308可生成具體語句的表達式樹，以便確定表達式的哪些變量/陣列是彼此相互依賴的，並由此生成集群。當然，在一些實施例中，語句可用3-地址格式（結果，算子和兩個運算數）表達，其隱含地是表達式樹，沒有明確生成表達式樹。

可重新排序陣列發現模塊310配置成對所識別的代碼區域執行雙向數據流分析，以便發現代碼區域中的可重新排序陣列。如下所述，在一些實施例中，可重新排序陣列發現模塊310可基於後向傳送函數（transferfunction）通過代碼區域中的一個或多個表達式迭代地執行可重新排序陣列的後向傳播，並基於前向傳送函數執行前向傳播。例如，在一些實施例中，可重新排序陣列發現模塊310可識別具有數據局部性的可通過重新排序變換改進的稀疏陣列，並且通過雙向流分析來分析/傳播該陣列（例如以確定要重新排序的其它陣列）。在一些實施例中，此類陣列可以是與已知對代碼區域重要的一些運算（例如稀疏矩陣向量乘法(spmv)）相關的前一個或幾個稀疏陣列。在另一實施例中，可重新排序陣列發現模塊310可從用戶接收要重新排序的第一陣列（far）（例如，經由代碼區域的用戶注釋以便由編譯器314分析）。

代碼變換模塊312配置成重新排序和/或反向重新排序代碼區域中和/或程序代碼中的代碼區域周邊（例如緊接在代碼區域之前或之後）內的一個或多個陣列。在說明性實施例中，應該認識到，代碼變換模塊312確定要重新排序和/或反向排序的具體陣列以及在程序代碼中的具體位置（在其處基於可重新排序陣列發現模塊310的雙向流分析執行此類操作）。另外，應該認識到，代碼變換模塊312可取決於具體實施例採用任何適合的重新排序算法，並且可利用任何適合的算法、技術和/或機制來實際實現程序代碼的變換。

現在參考圖5，在使用中，計算裝置200可執行用於稀疏矩陣的自動重新排序的方法500（例如沒有用戶定向和/幹預）。說明性方法500開始於框502，其中計算裝置200接收包含可重新排序的一個或多個稀疏矩陣的程序（例如程序代碼）。更確切地說，在一些實施例中，程序代碼可由計算裝置200的編譯器314檢索。在框504，計算裝置200識別要分析的程序代碼的代碼區域以便重新排序陣列。如上所述，代碼區域可以是程序代碼的任何任意部分；然而，在一些實施例中，所識別/選擇的代碼區域是線性循環區域或程序代碼的另一部分，在其處存在大量執行時間的。

在框506，計算裝置200執行程序代碼的代碼區域的分布性分析以便確定在所識別的代碼區域中定義的表達式的一個或多個（例如每個）的分布性。相應地，在框508，計算裝置200可識別代碼區域中的具體表達式，並且在框510，確定表達式上重新排序算法的分布性。例如，計算裝置200可掃描代碼區域中的所有表達式，並且確定重新排序是否在每一個表達式上都是分布性的。如上所述，在說明性實施例中，如果其語義保持不變，則表達式上的重新排序r是分布性的，不管其輸出是否被重新排序和/或其輸入是否被重新排序。也就是，如果，其中是輸入的集合，則重新排序r在表達式上是分布性的。在一些實施例中，表達式可包含通常使用的已知是分布性的或非分布性的陣列相關表達式。相應地，在一些實施例中，計算裝置200可確定在給定表達式中的具體陣列上執行的運算的類型。儘管分布性分析被描述為在代碼標識之後，但在一些實施例中，分布性分析和代碼標識可同時發生。例如，在一些實施例中，計算裝置200可開始於空區域，並且通過添加識別為/已知是分布性的語句來逐步「生長」代碼區域。

如果計算裝置200在框512確定代碼區域中的表達式的一個或多個是非分布性的，則方法500終止。然而，如果計算裝置200確定重新排序在代碼區域中的每一個表達式上都是分布性的，並且因此在總體代碼區域上是分布性的，則在框514，計算裝置200對代碼區域執行活性分析以確定在代碼區域內的各種編程點的陣列的一個或多個（例如每個）的活性。例如，在一些實施例中，計算裝置200確定在代碼區域中的每個語句/表達式之前和之後陣列是「活的」還是「死的」。如上面所指示的，計算裝置200（例如編譯器314）可採用用於確定變量活性的任何適合的技術、算法和/或機制。另外，儘管活性分析在圖5中被顯示為在分布性分析之後，但在一些實施例中，活性分析可在分布性分析之前執行。

在框516，計算裝置200對代碼區域中的一個或多個（例如每個）表達式執行相互依賴的陣列分析，以對於那些表達式中的每個，確定表達式的哪些陣列/變量是彼此相互依賴的，並基於該確定生成適當集群。換言之，計算裝置200確定表達式陣列的重新排序是否會使表達式其它陣列的重新排序成為必要。例如，如上面所指示的，如果代碼區域包含語句，其中是陣列和的表達式，則陣列、和是相互依賴的陣列。在一些實施例中，計算裝置200可執行方法600以生成並分析如圖6中所示的表達式樹，以便確定表達式的哪些變量/陣列彼此相互依賴，並由此生成集群。當然，在一些實施例中，語句可用3-地址格式（結果，算子和兩個運算數）表達，其隱含地是表達式樹，沒有明確生成表達式樹。

現在參考圖6，說明性方法600開始於框602，其中計算裝置200識別並選擇代碼區域的語句/表達式用於分析。作為示例，代碼區域可包含由計算裝置200選擇的表達式，其中、、、和是向量，m是矩陣，並且是點積函數。在框604，計算裝置200生成所選擇的語句/表達式的表達式樹。具體地說，計算裝置200可生成表達式樹700，如圖7a所示的。如所示的，表達式樹700包含多個內部節點和端節點。具體地說，在說明性實施例中，表達式樹700包含指示運算(=、+、*和)的內部節點，並且包含指示對應運算的運算數的子節點。此外，表達式樹700包含指示變量/陣列和/或標量常數（、、、、和m）的端節點。儘管示範表達式，並且因此表達式樹700僅包含二進位運算，但應該認識到，任何具體表達式和表達式樹在其它實施例中都可包含具有不同數量運算數的運算（例如由於表達式中的三元算子）。像這樣，在其它實施例中，表達式樹的具體操作節點可包含多於或少於2個的子節點。

在框606，如果可能的話，計算裝置200將表達式樹分成多個子樹702。在這麼做時，在框608，計算裝置200可確定表達式樹的內部節點的結果類型。在說明性實施例中，如果內部節點的結果類型是數字，則該節點與其父節點之間的邊緣被打破，以將表達式樹分成兩個子樹。如果內部節點是函數，則在一些實施例中，可分析函數的原始碼以確定其結果類型。在其它實施例中，計算裝置200可依靠函數的元數據（從計算裝置200的用戶接收的）來確定相互依賴的陣列分析的結果類型。在說明性實施例中，表達式樹和/或子樹被分解，直到原始表達式樹不能被分成更小的子樹。在涉及表達式樹700的示範實施例中，運算生成標量值。相應地，通過打破節點與其父節點之間的鏈路將表達式樹700分成2個子樹702，如圖7b中所示的。

在圖6的框610，計算裝置200生成或確定每個生成的表達式子樹的相互依賴的陣列的集合/集群。具體地說，在說明性實施例中，具體子樹中的每個陣列/變量都被包含在與該具體子樹關聯的結合/集群中。例如，在圖7a-b的示範實施例中，第一子樹702的陣列/變量、和被包含在第一集群中，而第二子樹的陣列/變量、和被包含在第二集群中。在圖6的框612中，計算裝置200確定是否分析另一語句/表達式。例如，在說明性實施例中，計算裝置200確定是否存在尚未對於表達式的陣列的相互依賴性進行分析的其它表達式。如果計算裝置200確定分析另一表達式，則方法600返回到框602，其中計算裝置200識別並選擇另一表達式用於分析。

回頭參考圖5，在框518，計算裝置200對所識別的代碼區域執行雙向數據流分析，以便發現代碼區域中的可重新排序陣列。如下所描述的，應該認識到，計算裝置200可利用前向和後向傳播函數、前向和後向傳送函數和/或其它函數，以便例如基於所提供的要重新排序的第一陣列（far）來發現可重新排序陣列。例如，可根據定義前向相互依賴的陣列傳播函數，非空，其中是前向傳播函數，b是表達式，x是要通過的輸入陣列的集合，c是集群，並且c.rhs是集群的右手側（即，指示由對應表達式使用的陣列）。此外，可根據定義後向相互依賴的陣列傳播函數，非空，其中是後向傳播函數，並且c.lhs是集群的左手側（即，指示由對應表達式定義的陣列）。

例如，基於上面描述的示範表達式，相互依賴的陣列分析得出兩個集群（例如基於兩個子樹702）：第一集群和第二集群，其中|將定義的陣列/變量（即在左手側的）與使用的陣列/變量（即在右手側的）分開。

作為示例，在此類實施例中，應該認識到，，因為v1不包含在第一集群或第二集群的右手側，，因為v2在第一集群的右手側，，因為v2在第一集群的右手側並且u不在集群的右手側不影響結果，，因為v2在第一集群右手側並且v4在第二集群的右手側，，因為v1在第一集群的左手側，並且，因為v1在第一集群的左手側並且v4不在集群的左手側不影響結果。

在說明性實施例中，可根據定義前向傳送函數，其中是前向傳播函數，b是表達式，x是要通過的可重新排序陣列的集合，是在語句b中定義的陣列的集合，並且是在語句b中使用的陣列的集合。應該認識到，前向傳送函數指示從語句b前面到它後面按次序通過語句的右手側和左手側。應該進一步認識到，有兩種情況可在通過具有前向傳送函數的語句b傳播期間發生，對於其可發生進一步「生長」：滿足第一項的陣列和滿足第二項的陣列。像這樣，如果x中的輸入陣列由語句b使用，則可重新排序陣列的新集合包含具有集群右手側的陣列的所有集群。應該認識到，第一語句反映表達式右手側的重新排序的陣列可使同一集群中的每個其它陣列的重新排序成為必要。另外，如果表達式b既不使用也不定義輸入陣列，則該陣列也被包含在重新排序的陣列的新集合中。換言之，如果重新排序的輸入陣列被通過，並且既不影響表達式b的任何陣列影響也不受其影響，則重新排序的輸入陣列應該在表達式之後保持重新排序。

可根據定義後向傳送函數，其中是前向傳播函數，是後向傳播函數，b是表達式，x是要通過的可重新排序陣列的集合，是在語句b中定義的陣列的集合，是在語句b中使用的陣列的集合，並且.rhs定義集群的右手側。應該認識到，後向傳送函數指示從語句b後面到它前面按次序通過語句的左手側和右手側。此外，應該進一步認識到，有三種情況可在通過具有後向傳送函數的語句b傳播期間發生，對於其可發生進一步「生長」：滿足第一項的陣列、滿足第二項的陣列或滿足第三項的陣列。

在一些實施例中，計算裝置200可執行方法800以執行雙向數據流分析，如圖8中所示的。在一些實施例中，雙向數據流分析工作在控制流圖（cfg）上，其中每個塊b都是語句/表達式。說明性方法800開始於框802，其中計算裝置200初始化代碼區域中的語句/表達式的輸入和輸出集/狀態。為了這麼做，在代碼區域外部的任何語句/表達式的輸入和輸出集可首先被初始化成空集。此外，在說明性實施例中，對於每個區域條目，輸出集都被初始化成要重新排序的第一陣列（far）。如上面所指示的，far可由計算裝置200的用戶提供，或以其它方式由編譯器314確定。對於代碼區域中的其它語句，輸出集可被初始化成全集。在一些實施例中，代碼區域中的語句的輸入集不初始化，因為他們可在隨後的步驟中自動例示。更正式地說，在一些實施例中，代碼區域外部的所有語句b都可根據初始化，其中是輸入集，並且是輸出集，並且代碼區域內部的所有語句都可被初始化，使得如果b是條目，則，並且否則等於全集。

在框804，計算裝置200預先調節代碼區域中語句的輸入和輸出集。為了這麼做，在框806，計算裝置200可向語句應用前向傳送函數。像這樣，應該認識到，對於每個語句b，輸入集都包含在其每個前任（predecessor）後面可重新排序的陣列，並且輸出集是基於前向傳送函數通過語句b傳播的結果，其可被重複，直到輸入集和輸出集沒有改變。更正式地說，在一些實施例中，可根據和預先調節代碼區域中（對於其b不是代碼區域的條目）的所有語句b，其中pred是b的前任表達式的集合。

在一些實施例中，在框808，計算裝置200可選擇傳送函數優化（例如對於後向傳送函數）。具體地說，在說明性實施例中，計算裝置200可沒有優化、具有基於陣列活性的優化或者具有基於代碼區域中各種表達式的執行頻率的優化，而應用後向傳送函數。

在框810，計算裝置200向代碼區域中的語句應用後向傳送函數。為了這麼做，在框812，計算裝置200可基於選擇的優化應用後向傳送函數。在說明性實施例中，後向傳送函數可通過添加陣列（在其每個後繼前面可重新排序）來擴大，和/或可通過添加基於具體後向傳送函數通過b傳播的結果的陣列來擴大。在採用活性優化的實施例中，如果在後繼之前變量是「死」（即，在通過後繼的任何執行路徑中都不使用），則它可在後繼前面人工重新排序，因為這麼做不影響程序語義（例如，該陣列在那點無論如何都不使用）。在採用執行頻率優化的實施例中，如果語句b具有多於一個後繼塊，並且執行頻率顯著不同（例如基於預先確定的閾值），則最頻繁的後繼x可以總是允許中的可重新排序陣列被傳播到。例如，如果具體後繼x在循環內，並且所有其它的都在循環外，則該後繼x的傳播可避免在語句b與x之間插入陣列的重新排序；當然，在一些實施例中，可能有必要在b與後繼而不是x之間插入那些陣列中的一個或多個的反向重新排序函數。更正式地說，在一些實施例中，對於區域中的所有語句b，應用後向傳送函數可根據：如果採用活性優化，則根據和中的一個，如果採用執行頻率優化，則根據，或者如果不採用優化，則根據，其中是語句b的所有後繼的集合，，，其中，並且在b的所有後繼之間最頻繁執行，是在後繼s前面是死的但在其它後繼前面不是死的（即，它們在所有後繼之間是「部分死的」）的變量/陣列的集合，並且是在後繼s前面是活的的變量/陣列的集合。

在框814，計算裝置200向代碼區域中的語句應用前向傳送函數。應該認識到，對於前向傳送函數的應用類似於上面相對於預先調節所描述的；然而，和保持它們的原始值，並且隨著新陣列「生長」。更正式地說，在一些實施例中，對於代碼區域中的所有語句b都可根據和應用前向傳送函數。在框818，計算裝置200確定無論輸入和輸出集都不改變。如果否，則方法800返回到框810，其中再次向語句應用後向傳送函數。換言之，迭代地應用後向和前向傳送函數，直到輸入和輸出集不改變並且穩定。

回頭參考圖5，在框520，計算裝置200基於所發現的可重新排序陣列變換程序代碼。具體地說，計算裝置200配置成重新排序和/或反向重新排序代碼區域中和/或程序代碼中的代碼區域周邊（例如緊接在代碼區域之前或之後）內的一個或多個陣列。如上面所指示的，計算裝置200可利用任何適合的技術來實現程序代碼本身的變換。在一些實施例中，對於代碼區域中的任何語句b1，如果存在從語句b1到隨後語句b2的邊緣（例如在控制流圖（cfg）中），其中b2例如是cfg中的另一塊，則對於每個變量/陣列，如果但是，則程序代碼「x=reorder(x)」可被插入在那個邊緣，並且如果但是，則程序代碼「x=reverse_reorder(x)」可被插入在那個邊緣。在語句b2是代碼區域的條目的實施例中，對於每個變量/陣列，如果，則程序代碼「x=reorder(x)」可被插入在b2前面。

應該認識到，在一些實施例中，方法400、500、600和/或800中的任一個或多個可被實施為存儲在計算機可讀媒體上的各種指令，它們可由處理器210和/或計算裝置200的其它組件執行以使計算裝置200執行相應方法400、500、600和/或800。計算機可讀媒體可被實施為能夠由計算裝置200讀取的任何類型媒體，包含但不限於存儲器214、數據存儲裝置216、計算裝置200的其它存儲器或數據存儲裝置、由計算裝置200的外圍裝置220可讀的可攜式媒體和/或其它媒體。

部分表900描繪了來自向僅包含兩個語句/塊：和的簡單代碼區域應用雙向分析的結果。如所示的，在初始化階段期間，b1的輸出集被指配了要發現的第一陣列（far），其在此具體實施例中是（例如由用戶選擇的），並且b2的輸出集被指配了全集。在預先調節期間，計算裝置200如上所述應用前向傳送函數的前向傳遞902，這導致b2被指配了的輸出集。如所示的，語句b2的輸入集與語句b1的輸出集相同，因為在b1與b2之間沒有改變該集合的語句。計算裝置200隨後應用後向傳送函數的後向傳遞904，這導致b2具有的輸入集，並且b1具有的輸出集和的輸入集。如所示的，在此類實施例中，計算裝置200迭代地應用後向傳送函數和前向傳送函數，直到語句b1和b2中的每個的輸入和輸出集都不改變。

現在參考圖10，示出了描繪來自程序代碼的識別的代碼區域的控制流圖1000。如所示的，圖100包含描繪程序代碼的各種語句的多個塊b1-b13。在說明性實施例中，所識別的代碼區域包含塊b1-b12，而塊b13在代碼區域外部。應該認識到，圖11-16描繪了來自應用各種雙向流分析算法（即具有和沒有優化）的結果以及結果變換的程序代碼。應該進一步認識到，儘管來自應用一種雙向流分析算法（即具有優化）的結果變換代碼可被視為來自另一雙向流分析算法（例如沒有優化）的結果變換代碼中的提升/移動一些語句的後果，但用本文描述的技術可能沒有必要這麼做。在一些實施例中，可僅基於對應雙向流分析算法的結果，生成每個結果變換的代碼。

在圖11中示出來自向圖10的程序代碼應用雙向分析（沒有優化）的結果的部分表1100。應該認識到，部分表1100（以及下面描述的表1300和1500）僅包含本文描述的初始化、預先調節和第一後向通過階段。然而，實際上，可基於本文描述的技術完成整個表。如在與表1100對應的圖12的控制流圖1200中所示出的，變換程序代碼以重新排序和反向重新排序在代碼區域內各種編程點的變量/陣列（例如p、x、r和i）。

如上面所描述的，在一些實施例中，可優化雙向流分析以考慮變量活性。在圖13的表1300中部分示出了應用具有此類優化的雙向流分析的結果，且在圖14的控制流圖1400中示出了對應變換的程序代碼。如上面示出和描述的，與「部分死的」變量（例如a、p、r和i）關聯的重新排序函數從代碼區域內移動到代碼區域之前以便更有效執行。在又其它實施例中，可優化雙向流分析以考慮如上所述的執行頻率。在圖15的表1500中部分示出了應用具有此類優化的雙向流分析的結果，而在圖16的控制流圖1600中描繪了對應變換的程序代碼。如上面示出和描述的，在程序代碼或者更確切地說代碼區域（例如循環）的頻繁執行區域內出現的重新排序函數可被移動到循環外部（例如在循環和/或代碼區域前面）以改進執行。然而，在此類實施例中，可能有必要（例如在程序代碼中存在條件語句的情形下）將附加反向重新排序函數放在代碼區域內。例如，在說明性實施例中，在語句b2與b13之間包含反向重新排序函數，以確保到緊跟代碼區域的「print(x)」語句的陣列/變量輸出是準確的。

示例

下面提供了本文公開的技術的說明性示例。技術的實施例可包含下面描述的示例中的任一個或多個示例以及它們的任何組合。

示例1包含一種用於稀疏矩陣的自動重新排序的計算裝置，所述計算裝置包括：分布性分析模塊，用於確定在程序代碼的代碼區域中定義的表達式的分布性，其中如果所述表達式的語義不受所述表達式的輸入或輸出的重新排序的影響，則所述表達式被確定成是分布性的；相互依賴的陣列分析模塊，用於對所述表達式執行相互依賴的陣列分析以確定所述表達式的相互依賴的陣列的一個或多個集群，其中所述一個或多個集群的集群的每個陣列相互依賴於所述集群的每個其它陣列；以及可重新排序陣列發現模塊，用於基於所述相互依賴的陣列的所述一個或多個集群藉助於通過所述代碼區域中的所述表達式的可重新排序陣列的迭代的後向傳播和前向傳播對所述代碼區域執行雙向數據流分析，其中所述後向傳播基於後向傳送函數，而所述前向傳播基於前向傳送函數。

示例2包含示例1的主題，並且進一步包含區域標識模塊以識別所述程序代碼的所述代碼區域。

示例3包含示例1和示例2中任一示例的主題，並且其中識別所述代碼區域包括識別包含循環體內的代碼而不包含流控制語句的所述程序代碼的線性循環區域。

示例4包含示例1-3中任一示例的主題，並且其中識別所述代碼區域包括由所述計算裝置的編譯器識別所述代碼區域。

示例5包含示例1-4中任一示例的主題，並且其中識別所述代碼區域包括識別由所述計算裝置至少在閾值時段內要執行的代碼區域。

示例6包含示例1-5中任一示例的主題，並且其中所述區域標識模塊進一步由所述計算裝置的編譯器接收所述程序代碼。

示例7包含示例1-6中任一示例的主題，並且其中確定所述表達式的所述分布性包括確定在所述代碼區域中定義的每個表達式的所述分布性。

示例8包含示例1-7中任一示例的主題，並且其中執行所述相互依賴的陣列分析包括響應於每個表達式是分布性的確定而執行所述相互依賴的陣列分析。

示例9包含示例1-8中任一示例的主題，並且其中確定所述表達式的所述分布性包括確定語句，其中是所述表達式；其中r是所述表達式上的重新排序；並且其中是輸入的集合。

示例10包含示例1-9中任一示例的主題，並且其中確定所述表達式的所述分布性包括響應於確定如下至少一項而確定所述表達式是非分布性的：(i)所述表達式要求輸入或輸出結構具有特定形狀；(ii)所述表達式定義所述程序代碼的輸入-輸出函數；(iii)所述表達式要求逐位可再生性；或(iv)所述表達式包含對所述計算裝置的編譯器未知的函數。

示例11包含示例1-10中任一示例的主題，並且其中所述一個或多個集群的集群的每個陣列相互依賴於所述集群的每個其它陣列，使得所述一個或多個集群的具體集群中的一個陣列的重新排序影響所述具體集群的每個其它陣列。

示例12包含示例1-11中任一示例的主題，並且其中執行所述相互依賴的陣列分析包括：生成所述表達式的表達式樹，其中所述表達式樹的每個內部節點指示所述表達式的運算，而所述表達式樹的每個端節點指示陣列或標量；基於所述陣列的相互依賴性將所述表達式樹分成表達式子樹的集合；以及基於包含在所述表達式子樹中的所述陣列確定每個表達式子樹的相互依賴的陣列的對應集群。

示例13包含示例1-12中任一示例的主題，並且其中將所述表達式樹分成表達式子樹的集合包括確定所述表達式樹的每個內部節點的結果類型。

示例14包含示例1-13中任一示例的主題，並且其中執行所述雙向數據流分析包括：初始化所述表達式的輸入集和輸出集；通過向要重新排序的第一陣列應用所述前向傳送函數來預先調節所述表達式的所述輸入集和所述輸出集；以及迭代地應用所述後向傳送函數和所述前向傳送函數，直到所述輸入集和所述輸出集不改變。

示例15包含示例1-14中任一示例的主題，並且其中所述可重新排序陣列發現模塊進一步從所述計算裝置的用戶接收所述要重新排序的第一陣列。

示例16包含示例1-15中任一示例的主題，並且其中迭代地應用所述後向傳送函數和所述前向傳送函數包括：迭代地應用所述後向傳送函數和所述前向傳送函數，直到每個表達式的輸入集和輸出集都不改變。

示例17包含示例1-16中任一示例的主題，並且進一步包含代碼變換模塊以基於所述雙向數據流分析變換所述程序代碼以重新排序至少一個陣列。

示例18包含示例1-17中任一示例的主題，並且進一步包含活性分析模塊以確定在所述代碼區域內的每個語句的所述代碼區域中的每個變量的活性。

示例19包含一種稀疏矩陣的自動重新排序的方法，所述方法包括：由計算裝置確定在程序代碼的代碼區域中定義的表達式的分布性，其中如果所述表達式的語義不受所述表達式的輸入或輸出的重新排序的影響，則所述表達式被確定成是分布性的；由所述計算裝置對所述表達式執行相互依賴的陣列分析以確定所述表達式的相互依賴的陣列的一個或多個集群，其中所述一個或多個集群的集群的每個陣列相互依賴於所述集群的每個其它陣列；以及由所述計算裝置基於所述相互依賴的陣列的所述一個或多個集群藉助於通過所述代碼區域中的所述表達式的可重新排序陣列的迭代的後向傳播和前向傳播對所述代碼區域執行雙向數據流分析，其中所述後向傳播基於後向傳送函數，而所述前向傳播基於前向傳送函數。

示例20包含示例19的主題，並且進一步包含：由計算裝置識別程序代碼的代碼區域。

示例21包含示例19和20中任一示例的主題，並且其中識別所述代碼區域包括識別包含循環體內的代碼而不包含流控制語句的所述程序代碼的線性循環區域。

示例22包含示例19-21中任一示例的主題，並且其中識別所述代碼區域包括由所述計算裝置的編譯器識別所述代碼區域。

示例23包含示例19-22中任一示例的主題，並且其中識別所述代碼區域包括識別由所述計算裝置至少在閾值時段內要執行的代碼區域。

示例24包含示例19-23中任一示例的主題，並且進一步包含由計算裝置的編譯器接收程序代碼。

示例25包含示例19-24中任一示例的主題，並且其中確定所述表達式的所述分布性包括確定在所述代碼區域中定義的每個表達式的所述分布性。

示例26包含示例19-25中任一示例的主題，並且其中執行所述相互依賴的陣列分析包括響應於確定每個表達式是分布性而執行所述相互依賴的陣列分析。

示例27包含示例19-26中任一示例的主題，並且其中確定所述表達式的所述分布性包括確定語句，其中是所述表達式；其中r是所述表達式上的重新排序；並且其中是輸入的集合。

示例28包含示例19-27中任一示例的主題，並且其中確定所述表達式的所述分布性包括響應於確定如下至少一項而確定所述表達式是非分布性的：(i)所述表達式要求輸入或輸出結構具有特定形狀；(ii)所述表達式定義所述程序代碼的輸入-輸出函數；(iii)所述表達式要求逐位可再生性；或(iv)所述表達式包含對所述計算裝置的編譯器未知的函數。

示例29包含示例19-28中任一示例的主題，並且其中所述一個或多個集群的集群的每個陣列相互依賴於所述集群的每個其它陣列，使得所述一個或多個集群的具體集群中的一個陣列的重新排序影響所述具體集群的每個其它陣列。

示例30包含示例19-29中任一示例的主題，並且其中執行所述相互依賴的陣列分析包括：生成所述表達式的表達式樹，其中所述表達式樹的每個內部節點指示所述表達式的運算，而所述表達式樹的每個端節點指示陣列或標量；基於所述陣列的相互依賴性將所述表達式樹分成表達式子樹的集合；以及基於包含在所述表達式子樹中的所述陣列確定每個表達式子樹的相互依賴的陣列的對應集群。

示例31包含示例19-30中任一示例的主題，並且其中將所述表達式樹分成表達式子樹的集合包括確定所述表達式樹的每個內部節點的結果類型。

示例32包含示例19-31中任一示例的主題，並且其中執行所述雙向數據流分析包括：初始化所述表達式的輸入集和輸出集；通過向要重新排序的第一陣列應用所述前向傳送函數來預先調節所述表達式的所述輸入集和所述輸出集；以及迭代地應用所述後向傳送函數和所述前向傳送函數，直到所述輸入集和所述輸出集不改變。

示例33包含示例19-32中任一示例的主題，並且進一步包含：由計算裝置從計算裝置的用戶接收要重新排序的第一陣列。

示例34包含示例19-33中任一示例的主題，並且其中迭代地應用所述後向傳送函數和所述前向傳送函數包括：迭代地應用所述後向傳送函數和所述前向傳送函數，直到每個表達式的輸入集和輸出集都不改變。

示例35包含示例19-34中任一示例的主題，並且進一步包含：基於所述雙向數據流分析變換所述程序代碼以重新排序至少一個陣列。

示例36包含示例19-35中任一示例的主題，並且進一步包含：由計算裝置確定在代碼區域內的每個語句的代碼區域中的每個變量的活性。

示例37包含計算裝置，計算裝置包括：處理器；以及存儲器，所述存儲器具有多個指令存儲在其上，所述指令當由處理器執行時使計算裝置執行示例19-36中任一示例的方法。

示例38包含一個或多個機器可讀存儲媒體，其包括多個指令存儲在其上，所述指令響應於被執行而導致計算裝置執行示例19-36中任一示例的方法。

示例39包含包括用於執行示例19-36中任一示例的方法的部件的計算裝置。

示例40包含一種用於稀疏矩陣的自動重新排序的計算裝置，所述計算裝置包括：用於確定在程序代碼的代碼區域中定義的表達式的分布性的部件，其中如果所述表達式的語義不受所述表達式的輸入或輸出的重新排序的影響，則所述表達式被確定成是分布性的；用於對所述表達式執行相互依賴的陣列分析以確定所述表達式的相互依賴的陣列的一個或多個集群的部件，其中所述一個或多個集群的集群的每個陣列相互依賴於所述集群的每個其它陣列；以及用於基於所述相互依賴的陣列的所述一個或多個集群藉助於通過所述代碼區域中的所述表達式的可重新排序陣列的迭代的後向傳播和前向傳播對所述代碼區域執行雙向數據流分析的部件，其中所述後向傳播基於後向傳送函數，而所述前向傳播基於前向傳送函數。

示例41包含示例40的主題，並且進一步包含：用於識別程序代碼的代碼區域的部件。

示例42包含示例40和41中任一示例的主題，並且其中用於識別所述代碼區域的部件包括用於識別包含循環體內的代碼而不包含流控制語句的所述程序代碼的線性循環區域的部件。

示例43包含示例40-42中任一示例的主題，並且其中用於識別所述代碼區域的部件包括用於由所述計算裝置的編譯器識別所述代碼區域的部件。

示例44包含示例40-43中任一示例的主題，並且其中用於識別所述代碼區域的部件包括用於識別由所述計算裝置至少在閾值時段內要執行的代碼區域的部件。

示例45包含示例40-44中任一示例的主題，並且進一步包含：用於由計算裝置的編譯器接收程序代碼的部件。

示例46包含示例40-45中任一示例的主題，並且其中用於確定所述表達式的所述分布性的部件包括用於確定在所述代碼區域中定義的每個表達式的所述分布性的部件。

示例47包含示例40-46中任一示例的主題，並且其中用於執行所述相互依賴的陣列分析的部件包括用於響應於確定每個表達式是分布性的而執行所述相互依賴的陣列分析的部件。

示例48包含示例40-47中任一示例的主題，並且其中用於確定表達式的分布性的部件包括用於確定語句的部件，其中是所述表達式；其中r是所述表達式上的重新排序；並且其中是輸入的集合。

示例49包含示例40-48中任一示例的主題，並且其中用於確定所述表達式的所述分布性的部件包括用於響應於確定如下至少一項而確定所述表達式是非分布性的部件：(i)所述表達式要求輸入或輸出結構具有特定形狀；(ii)所述表達式定義所述程序代碼的輸入-輸出函數；(iii)所述表達式要求逐位可再生性；或(iv)所述表達式包含對所述計算裝置的編譯器未知的函數。

示例50包含示例40-49中任一示例的主題，並且其中所述一個或多個集群的集群的每個陣列相互依賴於所述集群的每個其它陣列，使得所述一個或多個集群的具體集群中的一個陣列的重新排序影響所述具體集群的每個其它陣列。

示例51包含示例40-50中任一示例的主題，並且其中用於執行相互依賴的陣列分析的部件包括：用於生成所述表達式的表達式樹的部件，其中所述表達式樹的每個內部節點指示所述表達式的運算，而所述表達式樹的每個端節點指示陣列或標量；用於基於所述陣列的相互依賴性將所述表達式樹分成表達式子樹的集合的部件；以及用於基於包含在所述表達式子樹中的所述陣列確定每個表達式子樹的相互依賴的陣列的對應集群的部件。

示例52包含示例40-51中任一示例的主題，並且其中用於將所述表達式樹分成表達式子樹的集合的部件包括用於確定所述表達式樹的每個內部節點的結果類型的部件。

示例53包含示例40-52中任一示例的主題，並且其中用於執行所述雙向數據流分析的部件包括：用於初始化所述表達式的輸入集和輸出集的部件；用於通過向要重新排序的第一陣列應用所述前向傳送函數來預先調節所述表達式的所述輸入集和所述輸出集的部件；以及用於迭代地應用所述後向傳送函數和所述前向傳送函數直到所述輸入集和所述輸出集不改變的部件。

示例54包含示例40-53中任一示例的主題，並且進一步包含：用於從計算裝置的用戶接收要重新排序的第一陣列的部件。

示例55包含示例40-54中任一示例的主題，並且其中用於迭代地應用所述後向傳送函數和所述前向傳送函數的部件包括：用於迭代地應用所述後向傳送函數和所述前向傳送函數直到每個表達式的輸入集和輸出集都不改變的部件。

示例56包含示例40-55中任一示例的主題，並且進一步包含：用於基於所述雙向數據流分析變換所述程序代碼以重新排序至少一個陣列的部件。

示例57包含示例40-56中任一示例的主題，並且進一步包含：用於確定在代碼區域內的每個語句的代碼區域中的每個變量的活性的部件。