執行基於圖的程序規範的製作方法
2023-05-23 21:29:16 2
本申請要求於2014年9月2日提交的美國申請序列號62/044,628以及於2015年5月20日提交的美國申請序列號62/164,175的優先權。
技術領域
本說明書涉及一種用於執行基於圖的程序規範的方法。
背景技術：
一種用於數據流計算的方法利用基於圖的表示，其中對應於圖的節點(頂點)的計算組件通過與圖的鏈路(有向邊)對應的數據流(稱為「數據流圖」)耦合。通過數據流鏈路連接到上遊組件的下遊組件接收輸入數據元素的有序流，並且以所接收的順序處理輸入數據元素，可選地生成一個或多個對應的輸出數據元素流。用於執行這種基於圖的計算的系統描述於發明名稱為「EXECUTING COMPUTATIONS EXPRESSED AS GRAPHS(執行表達為圖的計算)」的在先美國專利5,966,072中，其通過引用併入本文。在與該在先專利中描述的方法相關的實現方式中，每個組件被實現為駐留在通常多個計算機伺服器之一上的進程。每個計算機伺服器可以具有在任何一個時間活動的多個這樣的組件進程，並且作業系統(例如，Unix)調度器在該伺服器上託管的組件之間共享資源(例如，處理器時間和/或處理器內核)。在這種實現方式中，組件之間的數據流可以使用作業系統的數據通信服務和連接伺服器的數據網絡(例如，命名管道，TCP/IP會話等)來實現。組件的子集通常用作來自整體計算的數據的源和/或數據宿(或數據接收器，sink)，例如，去往和/或來自數據文件、資料庫表和外部數據流。然後，在例如通過協調進程建立組件進程和數據流之後，數據流過整個計算系統，該計算系統實現表達為通常由每個組件處的輸入數據的可用性控制的圖的計算並且為每個組件調度計算資源。因此，至少通過使不同的組件能夠由不同的進程(託管在相同或不同的伺服器計算機或處理器內核上)並行地執行，可以實現並行性，其中不同組件在通過數據流圖的不同路徑上並行地執行在本文中被稱為組件並行性，並且不同組件通過數據流圖在相同路徑的不同部分上並行執行在本文中被稱為流水線並行性。
其他形式的並行性也得到這種方法的支持。例如，輸入數據集可以例如根據數據集的記錄中欄位的值的分區來分割，其中每個部分被發送到處理數據集的記錄的組件的單獨副本。組件的這種單獨的副本(或「實例」)可以在單獨的伺服器計算機或伺服器計算機的單獨的處理器內核上執行，從而實現本文所稱的數據並行性。可以合併單獨組件的結果以再次形成單個數據流或數據集。用於執行組件實例的計算機或處理器內核的數量將由開發人員在開發數據流圖時指定。
可以使用各種方法來提高這種方法的效率。例如，組件的每個實例不一定必須在其自己的作業系統進程中託管，例如使用一個作業系統進程來實現多個組件(例如，形成更大圖的連接子圖的組件)。
上述方法的至少一些實現方式受到與在底層計算機伺服器上所得到的進程的執行效率有關的限制。例如，這些限制可能涉及重新配置圖的運行實例以改變數據並行度、改變到託管各種組件的伺服器和/或平衡不同計算資源上的負載的困難。現有的基於圖的計算系統也具有的缺陷是啟動時間慢，這通常是因為太多的進程被不必要地啟動，浪費了大的存儲量。通常，進程在啟動圖的執行時開始，並在圖的執行完成時結束。
已經使用了用於分布計算的其他系統，其中將整體計算劃分為更小的部分，並且將這些部分從一個主計算機伺服器分發到各個其他(例如，「從屬」)計算機伺服器，從屬計算機伺服器各自獨立地執行計算並將其結果返回到主伺服器。一些這樣的方法被稱為「網格計算」。然而，除了經由調用那些部分的主計算機伺服器之外，這樣的方法通常依賴於每個計算的獨立性，而不提供用於在計算部分之間傳遞數據或調度和/或對這些部分的執行進行排序的機制。因此，對於託管涉及多個組件之間的交互的計算，這樣的方法沒有提供直接有效的解決方案。
用於大型數據集的分布式計算的另一種方法使用MapReduce框架，例如，如在Apache 系統中體現的。通常，Hadoop具有分布式文件系統，其中分發針對每個命名文件的部分。用戶根據兩個函數指定計算：以分布式方式在命名輸入的所有部分上執行的映射函數，以及在映射函數執行的輸出的部分上執行的歸約(reduce)函數。映射函數執行的輸出被分割並再次存儲在分布式文件系統中的中間部分中。然後以分布式方式執行歸約函數以處理這些中間部分，從而產生整體計算的結果。儘管可以有效地執行可以在MapReduce框架中表示並且其輸入和輸出可修改以用於在MapReduce框架的文件系統中存儲的計算，但是許多計算不匹配該框架和/或不容易適應於使得它們的所有輸入和輸出都在分布式文件系統中。
總體而言，與組件(或組件的並行執行副本)託管在不同伺服器上的上述方法相比，需要提高計算的底層規範是圖的計算的計算效率(例如，增加給定計算資源的每單位處理的記錄的數量)。此外，期望能夠適應變化的計算資源和需求。還需要提供一種計算方法，其允許適應在一個或多個基於圖的計算的執行期間可用的計算資源的變化，和/或允許適應例如由於正在處理的數據的特性導致的這樣的計算的不同組件的計算負載的變化或者負載的時間變化。還需要提供能夠有效地利用具有不同特性的計算資源的計算方法，例如使用具有每個伺服器不同數量的處理器、每個處理器不同數量的處理器內核等的伺服器，以有效地支持同質和異質環境。還期望使基於圖的計算快速啟動。提供這種效率和適應性的一個方面是在創建圖時(在設計時)開發人員做出的選擇、(在編譯時)編譯器所採取的動作和(在運行時)運行時系統所採取的動作之間提供適當的分離和抽象屏障。
技術實現要素：
在一個方面，一般性地，一種計算系統包括：存儲系統，存儲一個或多個基於圖的程序規範，至少第一基於圖的程序規範包括對應於任務的多個組件和所述多個組件的埠之間的有向鏈路，所述第一基於圖的程序規範包括：(1)由連結的組件的相應輸出埠和輸入埠定義的第一類型的鏈路配置，以及(2)由連結的組件的相應輸出埠和輸入埠定義的第二類型的鏈路配置，其中所述第二類型的鏈路配置不同於所述第一類型的鏈路配置。計算系統包括編譯器，被配置為根據所述第一基於圖的程序規範生成目標程序規範，其中所述編譯器識別不同類型的鏈路配置，並且在所述目標程序規範中提供目標原語的一次或多次出現，用於為流過具有所述第二類型的鏈路配置的鏈路的數據元素的每次出現執行函數。計算系統包括一個或多個計算節點，每個計算節點包括至少一個處理器，所述計算節點中的至少第一計算節點被配置為：啟動所述目標程序規範的執行，以及對於與所述目標原語的所述一次或多次出現相關聯的一個或多個組件，在運行時確定以下中的至少一個：(1)對應於組件的任務的實例將被調用的順序，或者(2)執行對應於組件的任務的實例將所位於的計算節點。
各個方面可以包括以下特徵中的一個或多個。
所述第一計算節點還被配置為：對於從所述第一基於圖的程序規範中第一組件的埠到所述第一基於圖的程序規範中第二組件的埠具有所述第一類型的鏈路配置的第一鏈路，串行調用對應於所述第一組件和所述第二組件的任務，並且對於從所述第一基於圖的程序規範中第三組件的埠到所述第一基於圖的程序規範中第四組件的埠具有所述第二類型的鏈路配置的第二鏈路，調用對應於所述第四組件的任務的多個實例，用於處理由所述第三組件提供的數據元素的不同相應子集。
所述第一計算節點還被配置為將所述多個實例中的至少一些實例分配到多個計算節點中的不同計算節點上執行。
所述目標原語標識與一個或多個任務的任務集相對應的函數，並且標識與具有所述第二類型的鏈路配置的鏈路相對應的數據元素的集合。
所述多個實例中的至少一些實例被應用於由所述目標原語標識的所述集合中的不同的相應數據元素。
被調用實例的數量等於由所述目標原語標識的所述集合中數據元素的數量，並且每個實例被應用於不同的相應數據元素。
獨立於所述第一基於圖的程序規範中的任何信息來確定被調用實例的數量。
被調用實例的數量與存儲由所述第一基於圖的程序規範引用的數據的計算節點的數量至少一樣多。
將由所述目標原語標識的函數應用於一數據元素包括：使用該數據元素作為與該函數相對應的所述一個或多個任務的任務集的數據源來執行所述一個或多個任務。
將所述多個實例中的至少一些實例分配到不同計算節點上執行包括：在運行時確定所述多個實例將在其上執行的計算節點的數量。
具有所述第一類型的鏈路配置的鏈路向所述編譯器指示將在所連結的組件之間傳遞單個數據元素，並且具有所述第二類型的鏈路配置的鏈路向所述編譯器指示將在所連結的組件之間傳遞多個數據元素。
所述第一基於圖的程序規範包括由連結的組件的相應輸入和輸出埠定義的鏈路的第三類型的鏈路配置，所述第三類型的鏈路配置向所述編譯器指示所連結的組件將串行執行，並且向所述編譯器指示將在所連結的組件的任務之間傳遞單個數據元素。
所述編譯器被配置為識別與相應組件對應的一個或多個任務的一個或多個任務集。
一個或多個任務的每個任務集具有作為數據源的數據元素的單個集合，其向一個或多個任務的該任務集的不同實例提供不同的數據元素。
一個或多個任務的每個任務集對應於一個或多個節點的至少一個有向無環圖，其中有向無環圖的每個節點對應於一任務或被標識的任務集，並且有向無環圖的每個有向邊對應於具有所述第一類型的鏈路配置的鏈路。
一個或多個節點的有向無環圖具有單個根節點。
每個計算節點被配置為執行至少一個調度器，用於派生進程以執行對應隊列中的任務。
所述第一計算節點被配置為將一個或多個任務從由所述第一計算節點執行的第二調度器的隊列移動到由所述第一計算節點執行的第一調度器的隊列中。
所述第一計算節點被配置為將一個或多個任務從由所述第一計算節點執行的調度器的隊列移動到由第二計算節點執行的調度器的隊列中。
在另一方面中，一般性地，一種方法包括：存儲一個或多個基於圖的程序規範，至少第一基於圖的程序規範包括對應於任務的多個組件和所述多個組件的埠之間的有向鏈路，所述第一基於圖的程序規範包括：(1)由連結的組件的相應輸出埠和輸入埠定義的第一類型的鏈路配置，以及(2)由連結的組件的相應輸出埠和輸入埠定義的第二類型的鏈路配置，其中所述第二類型的鏈路配置不同於所述第一類型的鏈路配置。所述方法包括根據所述第一基於圖的程序規範生成目標程序規範，並且識別不同類型的鏈路配置，並且在所述目標程序規範中提供目標原語的一次或多次出現，用於為流過具有所述第二類型的鏈路配置的鏈路的數據元素的每次出現執行函數。所述方法包括使用至少一個計算節點，啟動所述目標程序規範的執行，以及對於與所述目標原語的所述一次或多次出現相關聯的一個或多個組件，在運行時確定以下中的至少一個：(1)對應於組件的任務的實例將被調用的順序，或者(2)執行對應於組件的任務的實例將所位於的計算節點。
在另一方面中，一般性地，一種以非暫時形式存儲在計算機可讀介質上的軟體，所述軟體包括用於使得計算系統執行以下操作的指令：存儲一個或多個基於圖的程序規範，至少第一基於圖的程序規範包括對應於任務的多個組件和所述多個組件的埠之間的有向鏈路，所述第一基於圖的程序規範包括：(1)由連結的組件的相應輸出埠和輸入埠定義的第一類型的鏈路配置，以及(2)由連結的組件的相應輸出埠和輸入埠定義的第二類型的鏈路配置，其中所述第二類型的鏈路配置不同於所述第一類型的鏈路配置；根據所述第一基於圖的程序規範生成目標程序規範，並且識別不同類型的鏈路配置，並且在所述目標程序規範中提供目標原語的一次或多次出現，用於為流過具有所述第二類型的鏈路配置的鏈路的數據元素的每次出現執行函數；以及使用至少一個計算節點，啟動所述目標程序規範的執行，以及對於與所述目標原語的所述一次或多次出現相關聯的一個或多個組件，在運行時確定以下中的至少一個：(1)對應於組件的任務的實例將被調用的順序，或者(2)執行對應於組件的任務的實例將所位於的計算節點。
各個方面可以具有一個或多個以下優點。
本文所描述的技術還便於在其層級結構的各個層級處使用非常規技術特徵來高效處理計算系統中的大量數據。這些技術特徵在計算系統的各種操作階段(包括設計時，編譯時和運行時)一起工作。編程平臺使得基於圖的程序規範能夠在設計時指定期望的計算。編譯時編譯器準備目標程序規範，以便在運行時在計算系統的多個伺服器之間有效地分配細粒度任務。例如，根據基於圖的程序規範中的任何控制流和數據流約束來配置多個任務。運行時系統支持以提高計算效率(例如，以給定計算資源的每單位被處理記錄的數量為單位)的方式對並發執行的這些任務進行動態分配。各種技術特徵一起工作以實現相對於常規系統的效率增益。
例如，計算系統能夠以合併計算資源的動態優化和用戶設置的控制流約束和數據流約束兩者的方式，使用對應於數據處理圖(或其它基於圖的程序規範)的組件的任務來處理數據元素。基於圖的程序規範的組件的子集(「執行集」)由編譯器識別，使得當處理記錄的子集時，構成組件的單獨的任務可以作為單元來執行。為了支持這些執行集，使用計算系統在其不同層級中內置的各種技術特徵。基於圖的程序規範可以包括連結的組件的埠之間的多種類型的鏈路配置。然後，編譯器能夠識別這些不同的鏈路配置並且包括在目標程序規範內的適當類型的目標原語的任何出現。目標原語(例如，forall(對於所有)原語)使得對於流過相應鏈路的數據元素的每次出現，在運行時執行對應於執行集的函數，如下面更詳細描述的。運行時系統能夠根據這些原語，確定影響運行時效率的執行的方面，諸如對對應於組件的任務的實例將被調用的順序，和/或執行對應於組件的任務的實例將所位於的計算節點的約束。
當執行本文所描述的方法時，這些技術還表現出對計算系統的內部功能的進一步的技術效果，諸如減少對存儲器和其他計算資源的需求，以及減少系統在處理各個數據元素時的延遲。特別地，這些優點有助於數據處理圖的高效執行。例如，由於在執行圖時由其他進程(例如，Unix進程)啟動多個進程，因而傳統的基於圖的計算系統可能具有相對較高的延遲(例如，幾十毫秒的量級)，導致這些進程的累積啟動時間。然而，本文描述的技術通過允許單個進程內的程序代碼直接啟動其他程序代碼而不需要進程啟動開銷，從而有利於實現相對較低的延遲(例如，幾十微秒的數量級)以及每秒處理的數據的更高的吞吐量。有助於數據處理圖的高效執行的其他方面在以下描述中將顯而易見。
從下面的描述和權利要求書中，本發明的其它特徵和優點將變得顯而易見。
附圖說明
圖1是基於任務的計算系統的框圖。
圖2A是具有控制和數據埠的數據處理圖的一部分的示例。
圖2B-圖2C是具有控制埠和數據埠的數據處理圖的示例。
圖3A是包括多個標量輸出埠到標量輸入埠連接的數據處理圖。
圖3B是包括多個集合輸出埠到集合輸入埠連接的數據處理圖。
圖3C是包括集合輸出埠到標量輸入埠連接和標量輸出埠到集合輸入埠連接的數據處理圖。
圖4A是兩個組件之間的標量埠到標量埠連接。
圖4B是兩個組件之間的集合埠到集合埠連接。
圖4C是兩個組件之間的集合埠到標量埠連接，包括執行集入口點。
圖4D是兩個組件之間的標量埠到集合埠連接，包括執行集出口點。
圖5是應用基於堆棧的分配算法的數據處理圖。
圖6是應用基於全局映射的分配算法的數據處理圖。
圖7是具有用戶定義的執行集的數據處理圖。
圖8A和圖8B示出了數據處理圖中的「相同集」關係。
圖9是具有複製數據元素的入口點的數據處理圖。
圖10A-圖10C示出了用戶界面工作流。
圖11A是具有非法執行集的數據處理圖。
圖11B是具有非法執行集循環的數據處理圖。
圖12A-圖12B是數據處理圖和對應的控制圖的示例的圖。
圖13A-圖13B是示例性執行狀態機的狀態轉換圖。
圖14是一組處理引擎的圖。
具體實施方式
參考圖1，基於任務的計算系統100使用高級程序規範110來控制計算平臺150的計算資源和存儲資源，以執行由程序規範110指定的計算。編譯器/解釋器120接收高級程序規範110並生成可由基於任務的運行時接口/控制器140執行的形式的基於任務的規範130。編譯器/解釋器120識別一個或多個「組件」的一個或多個「執行集」，其可以單獨地或作為單元被實例化為要應用於多個數據元素中每一個元素的細粒度任務。如下面更詳細描述的，編譯或解釋進程的一部分涉及識別這些執行集並且準備所述執行集用於執行。應當理解，編譯器/解釋器120可以使用包括諸如解析高級程序規範110、驗證語法、類型檢查數據格式、生成任何錯誤或警告以及準備基於任務的規範130之類的步驟的各種算法中的任何算法，並且例如編譯器/解釋器120可以利用各種技術來優化在計算平臺150上執行的計算的效率。由編譯器/解釋器120生成的目標程序規範本身可以是將由系統100的另一部分進一步處理(例如，進一步編譯、解釋等)以產生基於任務的規範130的中間形式。下面的討論概述了這種變換的一個或多個示例，但是當然，例如由編譯器設計的技術人員將理解的，用於變換的其他方法也是可能的。
通常，計算平臺150由多個計算節點152(例如，提供分布式計算資源和分布式存儲資源這二者的個體伺服器計算機)組成，從而實現高度並行性。如下面進一步詳細討論的，在高級程序規範110中表示的計算在計算平臺150上被執行為相對細粒度的任務，進一步實現指定計算的高效並行執行。
1 數據處理圖
在一些實施例中，高級程序規範110是稱為「數據處理圖」的一種基於圖的程序規範，其包括一組「組件」，每個組件指定要對數據執行的總體數據處理計算的一部分。組件例如在編程用戶界面和/或計算的數據表示中表示為圖中的節點。與一些基於圖的程序規範(例如在上述背景技術中描述的數據流圖)不同，數據處理圖可以包括代表數據傳送或控制傳送中的任何一個或兩者的節點之間的鏈路。指示鏈路特性的一種方式是在組件上提供不同類型的埠。鏈路是從上遊組件的輸出埠耦合到下遊組件的輸入埠的有向鏈路。埠具有表示如何從鏈路寫入和讀取數據元素和/或如何控制組件以處理數據的特性的指示符。
這些埠可以具有多個不同的特性。埠的一個特性是其作為輸入埠或輸出埠的方向性。有向鏈路表示從上遊組件的輸出埠傳送到下遊組件的輸入埠的數據和/或控制。允許開發人員將不同類型的埠連結在一起。數據處理圖的一些數據處理特性取決於不同類型的埠如何連結在一起。例如，如下面更詳細描述的，不同類型的埠之間的鏈路可以導致提供層級形式的並行性的不同「執行集」中的組件的嵌套子集。某些數據處理特性由埠的類型所暗示。組件可能具有的不同類型的埠包括：
·集合輸入或輸出埠，意味著組件的實例將分別讀取或寫入將通過耦合到該埠的鏈路的集合(collection)的所有數據元素。對於在它們的集合埠之間具有單個鏈路的一對組件，通常允許下遊組件在上遊組件正在寫入數據元素時讀取這些數據元素，從而實現上遊組件和下遊組件之間的流水線並行性。如下面更詳細描述的，數據元素也可以被重新排序，這使得並行化具有效率。在一些圖形表示中，例如在編程圖形界面中，這樣的集合埠通常由組件處的正方形連接符指示。
·標量輸入或輸出埠，意味著組件的一個實例將分別從耦合到埠的鏈路讀取或寫入至多一個數據元素。對於在其標量埠之間具有單個鏈路的一對組件，在上遊組件已經完成執行之後通過使用作為控制傳送的單個數據元素的傳送來強制下遊組件的串行執行。在一些圖形表示中，例如在編程圖形界面中，這樣的標量埠通常由該組件處的三角形連接符指示。
·控制輸入或輸出埠，類似於標量輸入或輸出，但是不需要發送數據元素，並且用於在組件之間通信控制的傳送。對於具有在它們的控制埠之間的鏈路的一對組件，在上遊組件已經完成執行之後強制下遊組件的串行執行(即使那些組件也具有集合埠之間的鏈路)。在一些圖形表示中，例如在編程圖形界面中，這樣的控制埠通常由組件處的圓形連接符指示。
這些不同類型的埠實現了數據處理圖的靈活設計，允許數據流和控制流與埠類型的重疊屬性的強大組合。特別地，存在兩種類型的埠(稱為「數據埠」)：集合埠和標量埠，用於傳送一些形式的數據；還存在兩種類型的埠(稱為「串行埠」)：標量埠和控制埠，用於強制串行執行。數據處理圖通常將具有作為「源組件」而沒有任何連接的輸入數據埠的一個或多個組件，以及作為「宿(sink)組件」而沒有任何連接的輸出數據埠的一個或多個組件。一些組件將具有連接的輸入和輸出數據埠。在一些實施例中，不允許圖具有循環，因此必須是有向無環圖(DAG)。該特徵可以用於利用DAG的某些特性，如下面更詳細描述的。
在數據處理圖的組件上使用專用控制埠還使得能夠靈活控制計算的不同部分，這種靈活控制使用某些其他控制流技術是不可能實現的。例如，能夠在數據流圖之間應用依賴性約束的作業控制解決方案無法提供由定義單個數據流圖內的組件之間的依賴性約束的控制埠實現的精細粒度控制。此外，將組件分配到順序運行的不同階段的數據流圖不允許對單個組件排序方面的靈活性。例如，使用簡單階段不可能的嵌套控制拓撲可以使用本文描述的控制埠和執行集來定義。這種更大的靈活性也可以潛在地通過允許更多的組件儘可能地並發運行來提高性能。
通過以不同的方式連接不同類型的埠，開發人員能夠在數據處理圖的組件的埠之間指定不同類型的鏈路配置。例如，一種類型的鏈路配置可以對應於連接到相同類型的埠的特定類型的埠(例如，標量到標量鏈路)，另一種類型的鏈路配置可以對應於連接到不同類型的埠的特定類型的埠(例如，集合到標量鏈路)。這些不同類型的連結配置既用作開發人員在視覺上識別與數據處理圖的一部分相關聯的預期行為的方式，又用作向編譯器/解釋器120指示啟用該行為所需的對應類型的編譯進程的方式。雖然本文描述的示例使用用於不同類型的埠的獨特形狀以可視地表示不同類型的鏈路配置，但是系統的其他實現方式可以通過提供不同類型的鏈路並且為每種類型的鏈路分配獨特的視覺指示符(例如，厚度，線型，顏色等)來區分不同類型的鏈路配置的行為。然而，為了用上面列出的三種類型的埠使用鏈路類型而不是埠類型來表示相同種類的鏈路配置，將存在多於三種類型的鏈路(例如，標量到標量、集合到集合、控制到控制、集合到標量、標量到集合、標量到控制等)。其他示例可以包括不同類型的埠，但是沒有在數據處理圖內可視地明確指示埠類型。
編譯器/解釋器120執行準備數據處理圖用於執行的過程。第一過程是執行集發現預處理過程，用於識別組件的潛在的嵌套執行集的層級結構。第二過程是控制圖生成過程，用於為每個執行集生成對應的控制圖，編譯器/解釋器120將使用該控制圖來形成控制代碼，該控制代碼將在運行時有效地實現狀態機，用於控制每個執行集內的組件的執行。下面將更詳細地描述這些過程中的每一個。
具有至少一個輸入數據埠的組件指定要對每個輸入數據元素或集合(或其多個輸入埠上的一元組的數據元素和/或集合)執行的處理。這種規範的一種形式是作為將要對一個或一元組輸入數據元素和/或集合執行的過程。如果組件具有至少一個輸出數據埠，則其可以產生對應的一個或一元組輸出數據元素和/或集合。可以以高級的基於語句的語言(例如，使用Java源語句或例如在美國專利8,069,129「Editing and Compiling Business Rules(編輯和編譯業務規則)」中使用的數據操作語言(DML))來指定這樣的過程，或者可以以一些完全或部分編譯的形式提供(例如，如Java Bytecode(Java字節碼))。例如，組件可以具有工作過程，所述工作過程的自變量包括其輸入數據元素和/或集合及其輸出數據元素和/或集合，或更一般地，包括對這樣的數據元素或集合或對過程或數據對象的引用(本文稱為「句柄」)，所述引用用於獲取輸入並提供輸出數據元素或集合。
工作過程可以有各種類型。本文不希望限制可以指定的過程的類型，一種類型的工作過程根據記錄格式指定對數據元素的離散計算。單個數據元素可以是來自表格(或其他類型的數據集)的記錄，並且記錄的集合可以是表中的所有記錄。例如，具有單個標量輸入埠和單個標量輸出埠的組件的一種類型的工作過程包括接收一個輸入記錄，對該記錄執行計算，以及提供一個輸出記錄。另一種類型的工作過程可以指定從多個標量輸入埠接收的一元組輸入記錄如何被處理以形成在多個標量輸出埠上發出的輸出記錄的一元組。
由數據處理圖指定的計算的語義定義固有地是平行的，因為它表示對由圖定義的計算的處理的順序和並發性的約束和/或無約束。因此，計算的定義不要求結果等同於計算步驟的某種順序排序。另一方面，計算的定義確實提供了需要對計算的部分進行排序的特定約束以及對計算的部分的並行執行的限制。
在數據處理圖的討論中，假定將組件的多個實例實現為運行時系統中的分開的「任務」，作為表示排序和並行約束的方式。在討論基於圖的規範本身的特性之後，將更全面地進行將數據處理圖實現為基於任務的規範的更具體討論，其實現與語義定義一致的計算。
通常，數據處理圖中的每個組件將在圖的執行期間在計算平臺中被多次實例化。每個組件的實例的數量可以取決於該組件被分配給多個執行集中的哪一個。當實例化組件的多個實例時，多於一個實例可以並行執行，並且不同的實例可以在系統中的不同計算節點中執行。組件的互連(包括埠的類型)決定由指定的數據處理圖允許的並行處理的性質。
儘管如下文所述，在組件的不同實例的執行之間通常不保持狀態，但在系統中提供某些規定用於明確地引用可以跨越組件的多個實例的執行的持久存儲。
在工作過程指定如何處理單個記錄以產生單個輸出記錄並且埠被指示為集合埠的示例中，可以執行組件的單個實例，並且迭代工作過程以處理連續的記錄以生成連續的輸出記錄。在這種情況下，可能從迭代到迭代在組件內維持狀態。
在工作過程指定如何處理單個記錄以產生單個輸出記錄並且埠被指示為標量埠的示例中，可以執行組件的多個實例，並且在工作過程的多次執行之間沒有為不同的輸入記錄保持狀態。
此外，在一些實施例中，系統支持不遵循上面介紹的最細粒度規範的工作過程。例如，工作過程可以在內部實現迭代，例如，其通過標量埠接受單個記錄並通過集合埠提供多個輸出記錄。
如上所述，存在兩種類型的數據埠：集合埠和標量埠，用於傳送一些形式的數據；還存在兩種類型的串行埠：標量埠和控制埠，用於強制串行執行。在一些情況下，一種類型的埠可以通過鏈路連接到另一類型的埠。這些情況中的一些將在下面描述。在某些情況下，一種類型的埠將連結到同一類型的埠。兩個控制埠之間的鏈路(稱為「控制鏈路」)在連結的組件之間施加串行執行排序，而不需要通過鏈路發送數據。兩個數據埠之間的鏈路(稱為「數據鏈路」)提供數據流，並且還在標量埠的情況下強制串行執行排序約束，並且在集合埠的情況下不需要串行執行排序。典型的組件通常具有至少兩種埠，包括輸入和輸出數據埠(集合埠或標量埠)以及輸入和輸出控制埠。控制鏈路將上遊組件的控制埠連接到下遊組件的控制埠。類似地，數據鏈路將上遊組件的數據埠連接到下遊組件的數據埠。
開發人員可以使用圖形用戶界面從一組組件中指定特定的數據處理計算，每個組件執行特定的任務(例如，數據處理任務)。開發人員通過在顯示屏幕上顯示的畫布區域上組裝數據處理圖來進行這樣的指定。這涉及將組件放置在畫布上，用適當的鏈路連接它們的各個埠，以及適當地配置組件。以下簡單示例說明了在具有單對集合埠和單對控制埠的組件的情況下的某些行為。
圖2a示出了被組裝的數據處理圖的一部分包括第一組件210A的示例，第一組件210A具有輸入控制埠212A和輸出控制埠214A以及輸入集合埠216A和輸出集合埠218A。控制鏈路220A，222A將輸入控制埠212A和輸出控制埠214A連接到數據處理圖中其他組件的控制埠。類似地，數據鏈路224A，226A將輸入集合埠216A和輸出集合埠218A連接到數據處理圖中其他組件的埠。集合埠216A，218A在圖中表示為矩形，而控制埠212A，214A用圓形表示。
通常，輸入集合埠216A接收要由組件210A處理的數據，並且輸出集合埠214提供已經由組件210A處理的數據。在集合埠的情況下，所述數據通常是未指定數量的數據元素的無序集合。在整體計算的特定實例中，集合可以包括多個數據元素，或單個數據元素，或沒有數據元素。在一些實現方式中，集合與確定集合中的元素是無序的還是有序的(並且如果有序的話，什麼決定順序)的參數相關聯。如下面將更詳細地描述的，對於無序集合，數據元素由數據鏈路的接收側的組件處理的順序可以不同於數據鏈路的發送側的組件提供這些數據元素的順序。因此，在集合埠的情況下，它們之間的數據鏈路用作數據元素的「包」，從其中可以以任意順序拉取數據元素，而不同於以特定順序將數據元素從一個組件移動到另一個組件的「傳送帶」。
控制鏈路用於在控制埠之間傳送控制信息，其確定組件是否開始執行以及何時開始執行。例如，控制連結222A指示組件210B將在組件210A已經完成之後開始執行(即，以串行順序)，或者指示組件210B將不開始執行(即，被「禁止」)。因此，雖然沒有數據通過控制鏈路發送，但是它可以被視為向接收側的組件發送信號。發送該信號的方式可以根據實現方式而變化，並且在一些實現方式中可以涉及在組件之間發送控制消息。其他實現方式可以不涉及發送實際的控制消息，而是可以改為涉及直接調用進程或調取與由接收側的組件表示的任務相關聯的函數的進程(或者在禁止的情況下省略這種調用或函數調取)。
連結控制埠的能力因此使得開發人員能夠控制由數據處理圖的不同組件表示的數據處理計算的不同部分之間的相對排序。另外，使用組件上的控制埠提供這種排序機制使得能夠混合與數據流和控制流相關聯的邏輯。實際上，這使得數據能夠用於做出關於控制的決定。
在圖2A所示的示例中，控制埠連接到其他控制埠，並且數據埠連接到其他數據埠。然而，數據埠上的數據固有地攜帶兩種不同種類的信息。第一種是數據本身，第二種是數據的存在。該第二種信息可以用作控制信號。結果，通過使標量數據埠能夠連接到控制埠，可以提供額外的靈活性。
圖2B示出了示例性數據處理圖230，其利用了由將標量埠連接到控制埠的能力所賦予的靈活性。
數據處理圖230的特徵如下：標記為「計算日期信息」的第一組件231，標記為「製作每月報告？」的第二組件232，標記為「製作每周報告」的第三組件233，標記為「每月報告」的第四組件234，標記為「製作每周報告？」的第五組件235和標記為「每周報告」的第六組件236。數據處理圖230執行過程，該過程總是產生每日報告、每日報告和每周報告、或所有三種報告。關於這些結果中的哪些將發生的決定取決於對由第一組件231提供的某些日期信息的評估。因此，圖2B示出了有效地控制執行的數據的示例。
當第一組件231將日期信息從輸出標量埠提供到第二組件232的輸入標量埠和第三組件233的輸入標量埠時，執行開始。沒有連接的輸入控制埠的第二組件232立即工作。包括第三組件233的所有其他組件具有連接的輸入控制埠，並且必須等待由適當的正控制信號激活。
第二組件232檢查該日期信息並確定是否適合製作每月報告。有兩種可能的結果：需要每月報告，或者不需要。第二組件232和第三組件233都具有兩個輸出標量埠，並且都被配置為執行選擇函數，該選擇函數提供數據元素，該數據元素在一個輸出標量埠(即，所選埠)上用作正控制信號並且在另一個輸出標量埠上用作負控制信號。
如果基於日期信息，第二組件232確定不需要每月報告，則第二組件232將數據元素從其底部輸出標量埠發送到第三組件233的輸入控制埠。該數據元素被解釋為正控制信號，其向第三組件233指示第二組件232已經完成了對由第一組件231提供的數據的處理，並且第三組件233現在可以開始處理其接收的日期信息數據。
另一方面，如果第二組件232基於由第一組件231提供的日期信息確定需要每月報告，則第二組件232改為將被解釋為正控制信號的數據元素從其輸出標量埠發送到第四組件234的輸入控制埠。雖然數據元素不僅僅是控制信號，但是第四組件234將其視為正控制信號，因為它正被提供給其輸入控制埠。第四組件234忽略數據元素中的實際數據，並且僅使用數據元素的存在作為正控制信號。
第四組件234繼續創建每月報告。在完成時，第四組件234從其輸出控制埠輸出控制信號到第三組件233的輸入控制埠。這告訴第三組件233它(即第三組件233)現在可以開始處理第一組件231提供給它的日期信息。
因此，第三組件233將總是最終經由其輸入標量埠處理由第一組件231提供的數據。唯一的區別在於哪個組件觸發它開始處理：是第二組件232還是第四組件234。這是因為第三組件233上的兩個輸入控制埠將使用OR邏輯進行組合，使得在任一埠(或兩者)接收的正控制信號將觸發處理。
圖230的其餘部分以基本上相同的方式操作，只是第三組件233接管第二組件232的角色，第六組件236接管第四組件234的角色。
在被其輸入控制埠處來自第二組件232或第四組件234的控制信號激活時，第三組件233通過將第一組件231連接到第三組件233的數據鏈路檢查由第一組件231提供的日期信息。如果第三組件233基於日期信息確定不需要每周報告，則第三組件233將被解釋為正控制信號的數據元素從其輸出標量埠之一發送到第五組件235的輸入控制埠。
另一方面，如果第三組件233確定需要每周報告，則第三組件233將被解釋為正控制信號的數據元素從其另一輸出標量埠發送到第六組件236的輸入控制埠。第六組件236繼續創建每周報告。在完成時，第六組件236將被解釋為正控制信號的數據元素從其輸出標量埠發送到第五組件235的輸入控制埠。
因此，第五組件235將總是最終執行，唯一的區別是第三組件233還是第六組件236最終觸發第五組件235開始執行。在從第三組件233或第六組件236接收到控制信號時，第五組件235創建每日報告。
圖2C還示出了標量和集合數據埠的使用。
圖2C示出了數據處理圖240，其具有標記為「輸入文件」的第一組件241，標記為「從請求獲取文件名」的第二組件242，標記為「讀取文件」的第三組件243，標記為「是壞記錄？」的第四組件244，標記為「無效記錄」的第五組件245，標記為「生成壞記錄文件名」的第六組件246，標記為「任何驗證錯誤？」的第七組件247和標記為「發送警報」的第八組件248。此圖旨在將壞記錄寫入文件，並在檢測到這種壞記錄時發送警報。
組件241和243是用作數據的源的組件的示例，並且組件245是用作數據的宿(接收器)的組件的示例。組件241和243使用可以以文件系統(諸如本地文件系統或分布式文件系統)中的各種格式中的任一種存儲的輸入文件作為其源。輸入文件組件讀取文件的內容，並從該文件產生記錄的集合。標量輸入埠(如組件243所示)提供指定要讀取的文件的位置(例如，路徑或統一資源定位符)和要使用的記錄格式的數據元素。在一些情況下，位置和記錄格式可以作為參數提供給輸入文件組件，在這種情況下，輸入標量埠不需要連接到任何上遊組件，並且不需要顯示(對於組件241也是如此)。集合輸出埠(如組件241和243兩者上的所示)提供記錄的集合。類似地，輸出文件組件(諸如組件245)將通過輸入集合埠接收的記錄的集合寫到輸出文件(其位置和記錄格式可以可選地由輸入標量埠指定)。輸入文件組件或輸出文件組件還可以包括連結到另一組件(諸如組件245)的控制埠的控制輸入或輸出埠。
在所示的數據處理圖240中，較大的虛線矩形內的組件是執行集(execution set)的一部分。此執行集包含嵌套在其中的另一個執行集。該嵌套執行集也在虛線矩形內示出，其僅包含第四組件244。下面更詳細地討論執行集。
在操作中，第一組件241讀取輸入文件。當第一組件241正在執行時，第一組件241經由從輸出集合數據埠到第二組件242的輸入集合數據埠的數據鏈路將輸入文件內的記錄的集合提供給第二組件。第二組件242的不同實例和其他下遊組件(它們在同一執行集中)可以針對集合中的每個記錄執行，如下面將更詳細描述的。由於第二組件242沒有連接到其控制輸入的任何東西，所以第二組件242立即開始處理。在完成時，第二組件242在其輸出標量埠上提供文件名。該文件名在相應輸入標量埠處由第三組件243和第六組件246兩者接收。
第三組件243立即讀取由文件名標識的文件，並且在輸出集合埠上提供文件的內容以用於遞送到第四組件244的實例的輸入標量埠。同時，第六組件246接收相同的文件名並輸出另一文件名，其提供到連接於第五組件245和第七組件247的對應輸入標量埠的輸出標量埠上。
在從第六組件246接收到文件名和從第四組件244接收到壞記錄時，第五組件245將壞記錄寫入文件名由第六組件246標識的輸出文件。
第七組件247是唯一一個在其數據輸入埠接收數據時沒有準備好被啟動執行的組件。當第五組件245完成對輸出文件的寫入時，第五組件245將控制信號從其控制輸出埠發送到第七組件247的輸入控制埠。如果第七組件247確定存在錯誤，則第七組件247提供數據到第八組件248的輸入標量埠。這使得第八組件248生成警報。這提供了控制埠用於限制數據處理圖中的某些組件的執行的示例。
應當清楚的是，當一組多個上遊組件都已達到特定狀態時，基於一個組件的狀態控制另一個組件中的處理的能力使得該組件可以控制處理。例如，數據處理圖可以支持去往或來自同一控制埠的多個控制鏈路。可替代地，在一些實現方式中，組件可以包括多個輸入和輸出控制埠。默認邏輯可以被編譯器/解釋器120應用。開發人員還可以提供用於確定如何組合控制信號的定製邏輯。這可以通過適當地布置組合邏輯以應用於上遊組件的各種控制鏈路，並且僅當達到某個邏輯狀態時(例如，在默認OR邏輯的情況下，當所有上遊組件已經完成時，並且當至少一個上遊組件已經發送激活控制信號時)觸發組件的啟動來實現。
通常，控制信號可以是觸發處理開始或觸發處理禁止的信號。前者是「正控制信號」，後者是「負控制信號」。然而，如果使用組合邏輯來確定是否應該調用任務(觸發處理的開始)，則邏輯可以「反轉」通常的解釋，使得僅當所有輸入提供負控制信號時調用任務。通常，組合邏輯可以提供用於確定與控制圖對應的狀態機中的下一狀態的任意「真值表」，下面將更詳細描述。
未連接的控制埠可以被分配默認狀態。在一個實施例中，默認狀態對應於正控制信號。如下面更詳細地描述的，這可以通過在表示數據處理圖的控制圖中使用隱式開始組件和結束組件來實現。
各種組件上的不同類型的數據埠允許數據以不同的方式在組件之間通過鏈路傳遞，這取決於連結這些組件的輸入和輸出埠的類型。如上所述，標量埠表示至多單個數據元素(即，0或1個數據元素)的生產(對於標量輸出埠)或消耗(對於標量輸入埠)。而集合埠表示一組潛在的多個數據元素的生產(對於集合輸出埠)或消耗(對於集合輸入埠)。通過在單個數據處理圖中支持兩種類型的數據埠，可以更有效地分配計算資源，並且可以在任務之間生成更複雜的控制流和數據流，從而允許開發人員容易地指示期望的行為。
參考圖3A，數據處理圖300包括一連串三個連接的組件：第一組件(A1)302，第二組件(B1)304和第三組件(C1)306。第一組件包括集合型輸入埠308以及標量型輸出埠310。第二組件304包括標量型輸入埠312和標量型輸出埠314。第三組件包括標量型輸入埠316和集合型輸出埠318。
第一鏈路320將第一組件302的標量輸出埠310連接到第二組件304的標量輸入埠312，這允許數據在第一組件302和第二組件304之間傳遞，並且同時強制第一組件302和第二組件304的串行執行。類似地，第二鏈路322將第二組件304的標量輸出埠314連接到第三組件306的標量輸入埠316，這允許數據在第二組件304和第三組件306之間傳遞，並且強制第二組件304和第三組件306的串行執行。
由於圖3A中標量埠的互連，第二組件304僅在第一組件302完成之後開始執行(並且在第一鏈路320上傳遞單個數據元素)，並且第三組件306僅在第二組件304完成之後開始執行(並且在第二鏈路322上傳遞單個數據元素)。也就是說，數據處理圖中三個組件中的每一個以嚴格的順序A1/B1/C1運行一次。
在一些示例中，一個或多個組件可以被置於禁止狀態，這意味著一個或多個組件不執行，並因此不將任何數據元素從其輸出埠傳遞出去。例如，通過確保將不執行任何有用處理的組件不需要專用於它們的計算資源(例如，進程或存儲器)，使得能夠禁止組件，避免浪費資源。具有僅連接到被禁止組件的輸出埠的標量輸入埠的任何組件不會執行，因為它們不接收數據。例如，如果第一組件302被置於禁止狀態，則第二組件304的標量輸入埠312不從第一組件302的標量輸出埠310接收數據，因此不執行。由於第二組件304不執行，因此第三組件306的標量輸入埠316不接收來自第二組件304的標量輸出埠314的數據，並且也不執行。因此，在兩個標量埠之間傳遞的數據也用作正控制信號，類似於在兩個連結的控制埠之間發送的信號。
在圖3A的示例性數據處理圖中，第一組件302的輸入埠308和第三組件318的輸出埠恰好是集合埠，其對連接它們的標量埠強加的第一組件302、第二組件304和第三組件306的串行執行行為沒有影響。
通常，集合埠用於在組件之間傳遞數據元素的集合(collection)，並且同時可以向運行時系統授予重新排序該集(set)中的數據元素的許可。允許對無序集合的數據元素重新排序，因為對從一個數據元素到另一個數據元素的計算的狀態沒有依賴性，或者如果存在處理每個數據元素時被訪問的全局狀態，則最終狀態獨立於處理這些數據元素的順序。此重新排序的許可提供了將關於並行化的決策推遲到運行時的靈活性。
參考圖3B，數據處理圖324包括一連串三個連接的組件：第一組件(A2)326、第二組件(B2)328和第三組件(C2)330。第一組件326包括集合型輸入埠332和集合型輸出埠334。第二組件328包括集合型輸入埠336和集合型輸出埠338。第三組件330包括集合型輸入埠340和集合型輸出埠342。
三個組件326、328、330中的每一個指定如何處理一個或多個輸入元素的集合以生成一個或多個輸出元素的集合。在特定輸入元素和特定輸出元素之間並不必然存在一一對應關係。例如，第一組件326和第二組件328之間的數據元素344的第一集合中的多個數據元素可以不同於第二組件328和第三組件330之間的數據元素346的第二集合中的多個數據元素。對集合埠之間的連接施加的唯一約束是集合中的每個數據元素從一個集合埠傳遞到另一個集合埠，同時允許第一組件326和第二組件328之間以及第二組件328和第三組件330之間相對於它們被處理的順序任意重新排序。可替代地，在其他示例中，集合埠可以可選地被配置為保持順序。在該示例中，三個組件326、328、330一同啟動並且並發運行，從而允許流水線並行性。
參照圖1描述的編譯器/解釋器120被配置為識別集合埠到集合埠連接，並且以適合於正在執行的計算的方式將計算轉換為可執行代碼。集合數據鏈路的無序性質使得編譯器/解釋器120在如何實現這一點方面具有靈活性。例如，如果對於第二組件328，恰好基於單個輸入元素計算每個輸出元素(即，沒有跨數據元素維持的狀態)，則編譯器/解釋器120可以允許運行時系統通過對每個數據元素實例化多達一個組件的實例來動態地並行化數據元素的處理(例如，取決於運行時可用的計算資源)。可選地，在特殊情況下，可以在具有多個輸入集合埠的組件中跨數據元素維護狀態。但在一般情況下，可以允許運行時系統對組件的任務並行化。例如，如果運行時系統檢測到沒有被維持的全局狀態，則可以允許對任務並行化。一些組件還可以被配置為支持維持狀態，在這種情況下可以不允許並行化。如果集合是無序的，則不需要在數據元素之間保持順序意味著第二組件328的每個實例一旦可用就可以向第三組件330提供其輸出數據元素，並且第三組件330可以在第二組件328的所有實例已經完成之前開始處理這些數據元素。
在一些示例中，圖開發者可以明確地指示可以通過將一個組件的集合型輸出埠連接到另一個組件的標量型輸入埠來動態地並行化數據集合中數據元素的處理。這種指示還要求在集合的不同元素的處理之間無需維持狀態。參考圖3C，數據處理圖348包括一連串三個連接的組件：第一組件(A3)350、第二組件(B3)352和第三組件(C3)354。第一組件350包括集合型輸入埠356和集合型輸出埠358。第二組件352包括標量型輸入埠360和標量型輸出埠362。第三組件354包括集合型輸入埠364和集合型輸出埠366。
第一組件的集合型輸出埠358通過第一鏈路368連接到第二組件352的標量型輸入埠360，並且第二組件352的標量型輸出埠362通過第二連接370連接到集合型輸入埠364。如下面更詳細描述的，從集合型輸出埠到標量型輸入埠的鏈路意味著進入執行集的入口點，並且從標量型輸出埠到集合型輸入埠的鏈路意味著執行集的出口點。非常普遍的情況是，如下面更詳細地描述的，包括在執行集中的多個組件可以由運行時控制器動態地並行化以處理來自數據元素集合的數據元素。
在圖3C中，第一組件350的集合型輸出埠358和第二組件352的標量型輸入埠360之間的鏈路368意味著進入執行集的入口點。第二組件352的標量型輸出埠362和第三組件354的集合型輸入埠364之間的鏈路370意味著執行集的出口點。也就是說，第二組件352是執行集中的唯一組件。
由於第二組件352包括在執行集中，因此針對從第一組件350的集合型輸出埠358接收的每個數據元素啟動第二組件352的單獨實例。至少一些單獨的實例可以並行地運行，這取決於直到運行時才能做出的決策。在該示例中，第一組件(350)和第三組件(354)一同啟動並且並發運行，而第二組件(352)針對通過鏈路368接收的集合內的每個數據元素運行一次。可替代地，針對集合中每多個數據元素的元組，第二組件352運行一次。
2 執行集
如上面參照圖1所描述的，編譯器/解釋器120對數據處理圖實施執行集發現預處理過程，以準備用於執行的數據處理圖。在一般意義上，如本文所使用的，術語「執行集」是指可以作為單元被調用並應用於數據的一部分(諸如輸出集合埠的數據元素的一部分)的一個或多個組件的集合。因此，對於每個輸入數據元素(或呈現給執行集的一個或多個輸入埠的多個輸入數據元素的元組)實施執行集中的每個組件的至多一個實例。在執行集內，通過到標量和控制埠的鏈路強加排序約束，只要不違反排序約束，就允許執行集中組件的並行執行。由編譯器/解釋器120為執行集準備的代碼可以包括指示在執行代碼時如何實施與組件相對應的任務(例如，並行度)的嵌入信息(例如，注釋或修改符)。在對接收到的集合中多個數據元素的元組執行執行集的一個實例的示例中，所述元組可包括例如固定數量的數據元素或共享一些特性(例如，公共鍵值)的多個數據元素。在存在被允許並行執行的至少一些組件的示例中，可以使用多個任務來實現執行集，例如，用於作為整體的執行集的任務，以及用於一個或多個組件的實例的並發執行的一個或多個子任務。因此，表示執行集的不同實例的任務本身可以被分解成甚至更細粒度的任務，例如具有可以並發執行的子任務。用於不同執行集的任務通常可以獨立並行地執行。因此，如果大型數據集有例如一百萬條記錄，則可能有一百萬個獨立的任務。一些任務可以在計算平臺150的不同節點152上執行。任務可以使用可以被有效地並發執行的輕量線程來執行，甚至在單個節點152上也是如此。
通常，由分配算法標識的執行集(即，除根執行集之外的執行集)通過在執行集的邊界處的「驅動」標量數據埠來接收數據元素。對於在執行集的驅動輸入標量數據埠處接收的每個數據元素，執行集內的每個組件執行一次(如果激活)或根本不執行(如果禁止)。執行集的多個實例可以被實例化並且並行地執行以處理從上遊集合埠對執行集可用的多個數據元素。可以在運行時確定執行集的並行度(並且包括不使執行集並行化的可能決策)，並且並行度僅受到運行時可用的計算資源的限制。執行集的獨立實例的各個輸出在執行集的(多個)輸出埠處被聚集，而不管順序如何，並且被提供給下遊組件。可替代地，在其他實施例中，可以識別不同於根執行集的不需要驅動輸入標量數據埠的執行集(在一些情況下，基於用戶輸入)。這樣的沒有驅動輸入標量數據埠的執行集如果合適的話可以使用本文所述的過程在單個實例中執行(例如，下面描述的鎖定的執行集)或在多個實例中並行地執行。例如，可以設置確定執行集將被執行的次數和/或將被執行的執行集的並行實例的數量的參數。
非常常見的情況是，執行集發現過程使用確定數據處理圖內的組件的子集的分配算法，所述子集將被應用為對數據元素的無序集合的輸入元素的集。分配算法遍歷數據處理圖並基於分配規則將每個組件分配給子集。如在以下示例中清楚可見的，給定數據處理圖可以包括嵌套在執行集層級結構的不同級別中的多個執行集。
在本文所述的數據處理圖中，存在兩種類型的數據埠：標量數據埠和集合數據埠。通常，如果一對連結的組件(即，圖4A到圖4D的上遊組件A 402和下遊組件B 404)通過相同類型的埠之間的鏈路連接，則在默認情況下它們將在相同的執行集中(除非它們由於另一個原因在不同的執行集中)。在圖4A中，組件A 402具有輸出埠406，該埠具有標量類型，並且組件B 404具有輸入埠408，該埠具有標量類型。由於組件A 402和組件B 404之間的鏈路410連接兩個標量型埠，因此在該示例中組件A 402和組件B 404處於相同的執行集中。在圖4A中，由於組件A 402和組件B 404之間的鏈路是標量到標量鏈路，所以0個數據元素或1個數據元素通過鏈路410在上遊組件A 402和下遊組件B 404之間傳遞。在上遊組件A 402的處理完成時，通過鏈路410傳遞數據元素，除非上遊組件A 402被禁止(如上所述)，在這種情況下沒有數據元素通過鏈路410傳遞。
參考圖4B，組件A 402具有輸出埠412，該埠具有集合類型，並且組件B 404具有輸入埠414，該埠具有集合類型。由於組件A 402和組件B 404之間的鏈路410連接兩個集合型埠，因此在該示例中組件A 402和組件B 404也處於相同的執行集中。在圖4B中，由於組件A 402和組件B 404之間的鏈路410是集合到集合鏈路，所以通過鏈路410在上遊組件和下遊組件之間傳遞一組數據元素。
當鏈路兩端的埠類型之間存在不匹配時，執行集層級結構的級別中存在隱性更改。具體地，不匹配的埠表示在執行集層級結構的特定級別處的執行集的入口點或出口點。在一些示例中，執行集入口點被定義為集合型輸出埠和標量型輸入埠之間的鏈路。在圖4C中，在組件A 402和組件B 404之間的鏈路410處示出了執行組入口點424的一個示例，這是因為組件A 402的輸出埠416是集合型埠，而組件B 404的輸入埠418是標量型埠。
在一些示例中，執行集出口點被定義為標量型輸出埠和集合型輸入埠之間的鏈路。參考圖4D，在組件A 402與組件B 404之間的鏈路410處示出了執行組出口點426的一個示例，這是因為組件A 402的輸出埠420是標量型埠，而組件B 404的輸入埠422是集合型埠。
在編譯器/解釋器120進行編譯和/或解釋之前實現的分配算法使用執行集入口點和執行集出口點來發現數據處理圖中存在的執行集。
2.1基於堆棧的分配算法
為了說明的目的，在第一示例中，數據處理圖具有簡單的一維圖結構，並且使用基於堆棧的算法示出更簡單的分配算法。在基於堆棧的分配算法中，數據處理圖中的每個組件用一個或多個「ID字符串」標記，該「ID字符串」由以分隔字符『/』分隔的整數組成。分隔字符『/』出現在給定組件的ID字符串中的次數確定執行集層級結構中的組件的級別。在一些示例中，組件可以具有多個輸入鏈路，並且因此可以具有多個ID字符串。在這種情況下，算法具有下面更詳細描述的規則，用於確定使用哪個ID字符串。
在基於堆棧的分配算法的一個示例中，編譯器/解釋器120根據以下過程在上遊到下遊方向上遍歷數據處理圖。最初，最上遊的組件用ID字符串『0』標記，指示它是執行集層級結構中根級別上的組件。
然後遍歷從最上遊組件到最下遊組件的路徑上的鏈路和組件。如果遇到上遊組件的集合型輸出埠和下遊組件的集合型輸入埠之間的鏈路，則上遊組件的ID字符串被傳播到下遊組件。類似地，如果遇到上遊組件的標量型輸出埠和下遊組件的標量型輸入埠之間的鏈路，則上遊組件的ID字符串被傳播到下遊組件。
如果遇到上遊組件的集合型輸出埠和下遊組件的標量型輸入埠之間的鏈路，則向下遊組件分配包括上遊組件的標記其末尾附加『/n』的標記，其中n是+l。如果遇到上遊組件的標量型輸出埠和下遊組件的集合型輸入埠之間的鏈路，則向下遊組件分配包括上遊組件的標記去除其最右邊的ID字符串整數(以及其分隔字符『/』)的標記。
在一些示例中，各種條件可以被認為是非法的，並且將導致算法中的錯誤(例如，如果組件在執行集層級結構中相同級別上具有兩個不同的ID字符串，或者在執行集中存在循環)。
參考圖5，將上述基於堆棧的分配算法應用於示例性數據處理圖550，導致發現兩個執行集(除了根以外，「0級」執行集551)：第一「1級」執行集570和嵌套在第一「1級」執行集670內的第二「2級」執行集572。為了實現兩個執行集570、572的發現，基於堆棧的分配算法首先標記最上遊組件，具有ID字符串『0』的第一數據集656。然後基於堆棧的分配算法遍歷通過數據處理圖550的一維路徑的組件。在遍歷該路徑時，基於堆棧的分配算法首先遍歷從第一數據集556到第一組件558的鏈路。由於第一數據集556的輸出埠是集合型輸出埠，並且第一組件558的輸入埠是標量型輸入埠，所以第一組件558被分配ID字符串『0/1』，其是第一數據集556的ID字符串在其末尾附加『/1』的標記，其中1是所有現有ID字符串整數的最大值+1。通常，將『/1』附加到第一組件558的ID字符串是從根「0級」執行集551到「1級」執行集570的轉換的指示。在一些示例中，該轉換使用第一執行集入口點指示符557表示。
然後，分配算法遍歷從第一組件558到第二組件560的鏈路。由於第一組件558的輸出埠是集合型輸出埠並且第二組件560的輸入埠是標量型輸入埠，所以第二組件560被分配ID字符串『0/1/2』，其是第一組件558的ID字符串其末尾附加『/2』，其中2是所有現有ID字符串整數的最大值+1。通常，將『/2』附加到第二組件560的ID字符串是從「1級」執行集570到「2級」執行集572的轉換的指示。在一些示例中，該轉換使用第二執行集入口點指示符559表示。
然後，分配算法遍歷從第二組件560到第三組件562的鏈路。由於第二組件560的輸出埠是標量型輸出埠，並且第三組件562的輸入埠是標量型輸入埠，所以第二組件560的ID字符串(即，『0/1/2』)被傳播到第三組件562。
然後，分配算法遍歷從第三組件562到第四組件564的鏈路。由於第三組件562的輸出埠是標量型輸出埠，並且第四組件564的輸入埠是集合型輸入埠，所以第四組件被分配ID字符串『0/1』，其是第三組件562的ID字符串去除其最右邊ID字符串『2』(及其分隔字符『/』)的ID字符串。通常，從第三組件562的ID字符串中去除『/2』是從「2級」執行集572到「1級」執行集570的轉換的指示。在一些示例中，該轉換使用第一執行集出口點指示符563表示。
然後，分配算法遍歷從第四組件564到第五組件566的鏈路。由於第四組件564的輸出埠是標量型輸出埠，並且第五組件566的輸入埠是集合型輸入埠，所以第五組件566被分配ID字符串『0』，其是第四組件564的ID字符串去除其最右邊的ID字符串整數(及其分隔字符『/』)。通常，從第四組件564的ID字符串中去除『/1』是從「1級」執行集570到根「0級」執行集551的轉換的指示。在一些示例中，該轉換使用第二執行集出口點指示符565來表示。
最後，分配算法遍歷從第五組件566到第二數據集568的鏈路。由於第五組件566的輸出埠是集合型輸出埠，並且第二數據集568的輸入埠是集合型輸入埠，所以第五組件566的ID字符串(即，『0』)被傳播到第二數據集568。
在一些示例中，除了入口點指示符和出口點指示符之外，可以使用用戶界面內的附加視覺提示在視覺上表示數據元素的集合的流和個體標量數據元素之間的變化。例如，表示鏈路的線在集合埠和指示符之間可以更粗，而在指示符和標量埠之間更細。
基於堆棧的分配算法的結果包括數據處理圖550的版本，其中每個組件用ID字符串標記。在圖5的示例中，第一數據集556、第二數據集568和第五組件566都用ID字符串『0』標記。第一組件558和第四組件564用ID字符串『0』標記。第二組件560和第三組件562各自用ID字符串『0/1/2』標記。
每個唯一ID字符串表示執行集層級結構中的唯一執行集。具有ID字符串『0』的那些組件被分組到執行層級中的根「0級」執行集551中。具有ID字符串『0/1』的那些組件被分組到嵌套在根執行集651中的「1級」執行集670中(其中『0/1』可以被讀取為嵌套在執行集0中的執行集1)。具有ID字符串『0/1/2』的那些組件被分組到「2級」執行集572，其嵌套在根「0級」執行集551和「1級」執行集570內。
2.2基於全局映射的分配算法
在一些示例中，對於更一般的數據處理圖，基於堆棧的分配算法可能不足以正確地確定執行集的層級結構。例如，在一般的數據處理圖中，任何給定的組件可以具有多個輸入埠和/或多個輸出埠，使一般的數據處理圖與基於堆棧的方法不兼容。在這樣的示例中，使用基於全局映射的分配算法來確定執行集層級結構。
基於全局映射的分配算法利用數據處理圖被限制為有向無環圖的事實。可以使用拓撲排序後的順序來處理有向無環圖，以確保圖的每個組件僅在緊鄰該組件的上遊的所有組件被處理之後得到處理。由於已知已經處理了組件的緊接上遊的所有組件，所以可以通過選擇該組件直接上遊的(在執行集層級結構中)最深嵌套組件的ID字符串來確定該組件的ID字符串。
在一些示例中，基於全局映射的分配算法使用諸如Kahn算法的標準拓撲排序算法來獲得給定數據處理圖的拓撲排序後的順序。Kahn算法通過以下偽代碼概述：
L←將要包含被排序元素的空列表
S←沒有進入邊的所有節點的集合
只要S是非空的，進行以下動作：
從S去除節點n
將n添加到L的尾部
對於具有n到m的邊e的每個節點m，進行以下動作：
從圖中去除邊e
如果m沒有其它進入邊，則
將m插入S
如果圖具有多個邊，則
返回錯誤(圖具有至少一個循環)
否則
返回L(拓撲排序後的順序)
在確定拓撲排序後的順序之後，基於全局映射的分配算法以拓撲排序後的順序遍歷數據處理圖的組件，以確定每個組件的適當ID字符串(或簡稱ID號)。特別地，當遍歷組件時，數據處理圖的每個組件將其ID字符串複製到其輸出埠。直接位於上遊組件下遊且沒有由於執行集入口點或執行集出口點而與上遊組件分離的組件從上遊組件的輸出埠讀取ID字符串，並使用該ID字符串作為其ID字符串。
對於由於執行集入口點而與下遊組件分離的上遊組件，在執行集入口點處分配新的ID字符串，並將其提供給下遊組件以用作其ID字符串。上遊組件的ID字符串到下遊組件的ID字符串的映射(即，父/子映射)被存儲在全局映射數據存儲中以供以後使用。
對於由於執行集出口點而與下遊組件分離的上遊組件，上遊組件的輸出埠處的ID字符串由執行集出口點讀取。然後查詢全局映射數據存儲以確定輸出埠處的ID字符串的父ID字符串。將父ID字符串提供給下遊組件以用作其ID字符串。
參考圖6，使用上述基於全局映射的分配算法來分析示例性一般二維數據處理圖628的一個示例。數據處理圖628包括第一數據集(D1)632，第一組件(C1)638，第二組件(C2)640，第三組件(C3)645，第四組件(C4)646，第五組件(C5)642，第六組件(C6)644和第二數據集(D2)634。在將ID字符串分配給數據處理圖表628的各個組件之前，將拓撲排序算法(例如，Kahn算法)應用於數據處理圖，得到以下拓撲排序後的順序：D1，C1，C2，C3，C4，C5，C6，D2。
利用確定的拓撲排序後的順序，基於全局映射的分配算法以拓撲排序後的順序遍歷數據處理圖的組件，以確定每個組件的適當ID字符串，從而導致發現「1級」執行集630和「2級」執行集631(除了根「0級」執行集以外)。為了實現兩個執行集630、631的發現，基於全局映射的分配算法首先標記最上遊組件，具有ID字符串『0』的第一數據集(D1)632。然後基於堆棧的分配算法以拓撲排序後的順序遍歷數據處理圖628的組件和鏈路。
基於全局映射的分配算法首先遍歷從第一數據集(D1)632到第一組件(C1)638的鏈路。由於第一數據集(D1)632的輸出埠是集合型輸出埠，並且第一組件(C1)638的輸入埠是集合型輸入埠，所以沒有標識執行集入口點或出口點，並且從第一數據集(D1)632的輸出埠讀取第一數據集(D1)632的ID字符串(即『0』)並且將該ID字符串分配給第一組件(C1)638。
然後，分配算法遍歷第一組件(C1)638和第二組件(C2)640之間的鏈路。由於第一組件(C1)638的輸出埠是集合型輸出埠，並且第二組件(C2)640的輸入埠是標量型輸入埠，所以在兩個組件638、640之間標識第一執行集入口點639。在第一執行集入口點639處，分配新的ID字符串(即，『1』)，並且該ID字符串被分配作為第二組件(C2)640的ID字符串。第一執行集入口點639的父ID字符串(即『0』)到第一執行集入口點639的子ID字符串(即『1』)的映射653被存儲在全局映射數據存儲649中以供以後使用。
然後，分配算法遍歷從第二組件(C2)640到第三組件(C3)645的鏈路。由於第二組件(C2)640的輸出埠是集合型輸出埠，並且第三組件645的輸入埠是標量型輸入埠，所以在兩個組件640、645之間標識第二執行集入口點641。在第二執行集入口點641處，分配新的ID字符串(即，『2』)並將其分配作為第三組件(C3)645的ID字符串。第二執行集入口點641的父ID字符串(即，『1』)到第二執行集入口點641的子ID字符串(即『2』)的映射651被存儲在全局映射數據存儲649中以供以後使用。
然後，分配算法遍歷從第三組件(C3)645到第四組件(C4)646的鏈路。由於第三組件(C3)645的輸出埠是集合型輸出埠，並且第四組件(C4)646的輸入埠是集合型輸入埠，所以未識別執行集入口點或出口點，並且從第三組件(C3)645的輸出埠讀取第三組件(C3)645的ID字符串(即，『2』)645並且將其分配給第四組件(C4)646。
然後，分配算法遍歷從第四組件(C4)646到第五組件(C5)642的鏈路。由於第四組件(C4)646的輸出埠是標量型輸出埠，並且第五組件(C5)642的輸入埠是集合型輸入埠，所以在兩個組件646、642之間識別第一執行集出口點647。在第一執行集出口點647處，從第四組件(C4)646的輸出埠讀取第四組件(C4)646的ID字符串並且該ID字符串用於查詢全局映射數據存儲649。全局映射數據存儲649返回與第二執行集入口點641相關聯地存儲的父子關係651(即，『1/2』)。父/子關係651中的父ID字符串(即，『1』)被分配作為第五組件(C5)642的ID字符串。
然後，分配算法遍歷從第五組件(C5)642到第六組件(C6)644的鏈路。由於第五組件(C5)642的輸出埠是標量型輸出埠，並且第六組件(C6)644的輸入埠是集合型輸入埠，所以在兩個組件642、644之間識別第二執行集出口點643。在第二執行集出口點643處，從第五組件(C5)642的輸出埠讀取第五組件(C5)642的ID字符串並且該ID字符串用於查詢全局映射數據存儲649。全局映射數據存儲649返回與第一執行集進入點639相關聯存儲的父/子關係653(即，『0/1』)。父/子關係653中的父ID字符串(即，『0』)被分配作為第六組件(C6)644的ID字符串。
最後，分配算法遍歷從第六組件(C6)644到第二數據集(D2)634的鏈路。由於第六組件(C6)644的輸出埠是集合型輸出埠，並且第二數據集(D2)634的輸入埠是集合型輸入埠，所以沒有識別執行集入口點或出口點，並且從第六組件(C6)644的輸出埠讀取第六組件(C6)644的ID字符串(即『0』)並且將其分配給第二數據集(D2)634。
基於全局映射的分配算法的結果包括數據處理圖628的版本，其中每個組件用ID字符串標記。在圖6的示例中，第一數據集(D1)632，第一組件(C1)638，第六組件(C6)644和第二數據集(D2)634都用ID字符串『0』標記。第二組件(C2)640和第五組件(C5)642都用ID字符串『1』標記。第三組件(C3)645和第四組件(C4)646都用ID字符串『2』標記。
每個唯一的ID字符串表示執行集層級結構中的唯一執行集。具有ID字符串『0』的那些組件被分組到執行層級結構中的根「0級」執行集629中。具有ID字符串『1』的那些組件被分組到嵌套在根執行集629內的「1級」執行集630中。具有ID字符串『2』的那些組件被分組到「2級」執行集631，「2級」執行集631嵌套在根「0級」執行集629內，並且進一步嵌套在「1級」執行集630內。
2.3用戶定義的執行集
在上述示例中，(多個)分配算法用於自動發現存在於數據處理圖中的執行集，而無需任何用戶幹預。然而，在一些示例中，用戶可能需要除了由分配算法提供的功能之外的功能。在這種情況下，用戶可以明確地添加執行集入口點和出口點，以明確定義執行集開始和/或結束的位置。參考圖7，數據處理圖776包括第一數據集774，第一組件778，第二組件780和第二數據集790。將上述分配算法應用於數據處理圖776將導致發現包括第一組件778和第二組件780的單個執行集。然而，在這種情況下，用戶已明確定義了用於數據處理圖776的兩個執行集(即，第一執行集782和第二執行集786)。具體地，用戶已經將執行集出口點組件784插入到從第一組件778的輸出埠出來的鏈路中，並且已經將執行集入口點788插入到進入第二組件780的輸入埠的鏈路中。通過將執行集出口點784和執行集入口點788添加到第一組件778和第二組件780之間的鏈路，用戶實質上已經將原本單個執行集分解為兩個單獨的執行集782、786。
在一些示例中，用戶為數據處理圖定義所有執行集入口點和出口點。在其他示例中，用戶定義一些執行集入口點和出口點，然後將其留給分配算法以發現數據處理圖的其餘執行集入口點和出口點。
2.4相同集關係
在一些示例中，用戶可能希望明確地指定給定組件屬於哪個執行集。例如，如圖8A所示，數據處理圖892包括從創建數據組件896和讀表組件898接收數據元素的第一執行集894。這些組件類似於輸入文件組件，不同之處在於它們具有用於它們提供的數據元素的集合的不同的源。對於創建數據組件896，沒有用來指定文件位置的標量輸入埠，而是存在用來指定多個記錄數據元素將如何產生的(可選的)標量輸入埠，並且還存在用來指定每個數據元素將如何生成的參數。對於讀表組件898，沒有用來指定文件位置的標量輸入埠，而是存在用來指定資料庫中的表的(可選的)標量輸入埠。第一執行集894包括第一組件891和第二組件893，它們一起處理來自創建數據組件896和讀表組件898的數據元素，以生成提供給第一數據集899的輸出。
在圖8A中，讀表組件898在第一執行集894外部，意味著它運行一次，並從其集合型輸出埠輸出數據元素的集合。數據元素的集合遍歷第一執行集894的邊界，並被提供給第一組件891上的集合型輸入埠。對於執行集894中的組件的每個並行實例，在第一組件891上的集合型輸入埠處創建數據元素集合的副本。通常，無論鏈路來自集合埠、標量埠還是控制埠，被分配給不同執行集的組件之間的鏈路將數據元素或控制元素複製到流入執行集的鏈路的所有實例，並且從流出執行集的鏈路的所有實例聚集數據元素或控制元素。數據元素被聚集成集合，並且控制元素被聚集成向量，該向量可以根據下遊組件的控制邏輯被適當地處理(包括可能將其標示為錯誤)。
參考圖8B，在一些示例中，用戶可以要求對執行集894中的組件的每個並行實例執行讀表組件898。為了實現該功能，用戶可以在讀表組件898和第一組件891之間指定「相同集」關係。作為用戶指定「相同集」關係的結果，讀表組件898被移動到與第一組件891相同的執行集(即，第一執行集894)。由於讀表組件898被包括在第一執行集894中，所以第一執行集894中的組件的每個並行實例執行讀表組件898的實例。
在一些示例中，用戶可以通過從與源執行集相關聯的菜單選擇目標執行集，或者通過將組件從源執行集拖動到目標執行集(例如，經由下面更詳細描述的用戶界面)來指定「相同集」關係。在一些示例中，實施錯誤檢查以驗證被拖拽的組件可以合法地位於目標執行集中。例如，可以在要彼此具有「相同集」關係的任何兩個組件上強加的一個可能的要求是，必須具有通過數據處理圖的包括這些組件的至少一個路徑。
2.5集合數據複製
在一些示例中，執行集中的多個組件可以各自具有經由執行集入口點連接到上遊組件的單個集合輸出埠的標量輸入埠。類似地，執行集中的多個組件可以各自具有連接到執行集下遊的組件的單個集合輸入埠的標量輸出埠。
在一些示例中，為了從多個組件的集合型輸出埠向標量輸入埠提供相同的數據，執行集入口點從集合為每個標量輸入埠創建每個數據元素的複製本，並且將複製本提供到它們相應的標量輸入埠。類似地，為了合併由多個組件的標量輸出埠(來自執行集的不同的相應迭代)輸出的數據，執行集出口點可以從多個標量輸出埠接收輸出數據元素，合併輸出數據元素，然後將合併的輸出數據元素提供到下遊組件的集合輸入埠。通常，下遊組件的集合輸入埠被配置為處理合併的數據元素。
如圖9所示，數據處理圖923包括第一數據集924，第二數據集926和執行集928。執行集928包括兩個組件：第一組件930和第二組件932。第一數據集924具有集合輸出埠934，其連接到執行集928的執行集入口點936並向其提供數據元素的集合。第二數據集926具有集合輸入埠938，集合輸入埠938連接到執行集合928的執行集出口點940並從其接收數據元素的集合。
在執行集928內，第一組件930具有第一標量輸入埠942，並且第二組件932具有第二標量輸入埠944。第一標量輸入埠942和第二標量輸入埠944均連接到執行集入口點936並從該執行集入口點936接收各個數據元素。如上文所述，執行集入口點936複製從集合輸出埠934接收的數據元素，以向連接到執行集入口點936的每個標量輸入埠提供數據元素集合的每個數據元素的複製本。在圖9中，執行集入口點936創建每個數據元素的兩個複製本，並將其中一個複製本提供給第一標量輸入埠942，將另一個複製本提供給第二標量輸入埠944。從圖中可以看出，在一些示例中，圖形用戶界面中的執行集入口點936的可視表示提供了由執行集入口點936創建了數據元素的多少複製本的表示。此外，在其他示例中，表示複製本的不同副本的不同入口點指示符可以被分離，並且圍繞執行集的邊界分布為與執行集內需要從饋送給該執行集的集合輸出埠提供的每個複製的數據元素的副本的組件一樣多的組件。
第一組件930和第二組件932處理它們各自的數據元素，並且經由標量輸出埠946、948將它們各自處理後的數據元素提供給執行集出口點940。在一些示例中，執行集出口點940將處理後的數據元素分組成對，將處理後的數據元素對輸出到第二數據集926的集合輸入埠938。從圖中可以看出，在一些示例中，圖形用戶界面中的執行集出口點940的可視表示提供了關於由執行集入口點936分組了多少數據元素的複製本的表示。
2.6資源鎖定
在一些示例中，給定執行集中的組件可以在並行實例中運行多次。在一些示例中，並行運行實例的組件可能需要訪問共享資源。為了防止競爭情況以及與訪問共享資源的多個進程相關的其他問題，可以使用鎖定機制(latching mechanism)。通常，鎖定機制允許執行集中的組件的一個實例在共享資源上獲得時長為該實例完成運行時間的運行時鎖定。在實例使共享資源鎖定期間，只有實例中的組件才能訪問該共享資源，並且其他實例的組件必須等待鎖定被解除。實例完成後，它會解除運行時鎖定，從而允許其他實例訪問共享資源。鎖定機制必須在單個執行集內鎖定和解鎖共享資源(例如，使用上遊端處的顯式鎖定組件和下遊端處的顯式解鎖組件)。在一些實施例中，這樣的「鎖定的執行集」不能被嵌套，也不能彼此重疊。
2.7其他
注意，雖然基於全局映射的分配算法是關於二維數據處理圖描述的，但是也可以使用該算法來發現一維數據處理圖的執行集。
通常，執行集可以任意嵌套。
通常，執行集具有為執行集的每個實例從連結的輸出集合埠接收到的至多一個驅動數據元素。然而，如果跨越執行集的邊界顯式地或隱式地複製相同的數據元素，則多個標量輸入埠可以接收該相同的數據元素。
通常，具有跨越執行集的邊界的鏈路的所有輸出標量埠具有來自執行集的多個實例中的每一個的所有數據元素，這些數據元素被聚集到提供給連結的輸入採集埠的同一集合中。但是，如果執行集僅具有單個實例，則具有跨越執行集的邊界的鏈路的輸出標量埠可以連結到輸入標量埠。
通常，相同類型的兩個埠之間的鏈路可以遍歷執行集邊界，假設執行集的遍歷不會導致數據處理圖中的任何循環。
在一些示例中，默認地為每個執行集分配唯一標識符(例如，『1』)。在其他示例中，每個執行集可以被分配執行集ID路徑(例如，『1/3/6』)。在一些示例中，用戶明確地提供執行集ID字符串。執行集ID字符串不一定是唯一的。在執行集ID字符串不是唯一的情況下，執行集ID字符串可以與其父、祖父節點等的執行集ID字符串組合，從而形成唯一的ID字符串。
在一些示例中，基於全局映射的分配算法導致組件被分配對應於最深嵌套執行集的ID字符串。在一些示例中，當為執行集被分配了執行集ID路徑時，執行集ID路徑不一定是唯一的。為了補償執行集ID路徑不唯一的情況，對執行集ID路徑施加約束，要求給定執行集上遊的執行集ID路徑必須是「兼容的」，其中兩個執行集ID路徑是兼容若且唯若它們是相同的，或者一個是另一個的適當前綴。例如：
·/1/2/3和/1/2/3兼容
·/1/2/3和/1/2兼容
·/1/2和/1/2/3兼容
·1/2/3和/1兼容
·1/2/3和1/4不兼容
·/1/2/3和/1/4/5不兼容
上述實施例基本上沒有對標量塊的實例的執行強加排序/並發約束。但是，在一些實施例中，提供其他輸入以控制從饋送給執行集的集合接收的數據元素的子集的允許並發性和所需串行化。在一些實施例中，可以對數據元素的一些子集強加根據部分排序的順序處理。
在默認情況下，執行集的實例可以完全並行地運行。然而，在一些情況下，用戶可能期望不同的行為。例如，如果正在處理的數據是帳戶級數據，則用戶可能希望對每個帳戶內的數據強制某些限制。例如，用戶可能想強制串行執行。在這種情況下，可以允許跨帳戶的任何並行度，但是不能同時(即，並發地)處理同一帳戶的兩個數據元素。可選地，附加限制可以是有序處理，使得相同帳戶的兩個數據元素不得根據由鍵限定的順序或者通過例如接收的順序來進行無序處理。
為了實現這一點，可以為執行集提供串行化鍵。具有相同串行化鍵值的所有數據元素必須串行處理，並且在某些情況下必須按照明確定義的順序處理。運行時系統對具有相同串行化鍵的數據元素強制串行執行的一種方式是通過串行化鍵來對執行集實例進行分區：將其驅動數據元素具有特定串行化鍵(或串行化鍵的哈希值)的實例分配為在特定計算節點152上執行。在運行時，系統可以通過掃描數據元素的集合來確保工作均勻分布在多個計算節點152上，以確保可運行任務的隊列保持充滿。在不需要明確定義的順序(例如在集合中)的情況下，順序可以是與它們從輸出埠(甚至集合輸出埠)產生的順序相同的順序，或者與控制串行化鍵組內的處理順序的不同的校對鍵相關聯的順序相同的順序。在一些情況下，可以通過提供預定義的值作為串行化鍵來強制執行集完全串行運行。
在一些實施例中，可以表面保持順序被保留，即使沒有嚴格根據該順序實施處理也是如此。如果執行集的輸入和輸出兩者處的數據與特定順序(例如，向量內的元素的順序)相關聯，則用戶可能希望保留該順序。即使在數據元素的處理中沒有串行化，也可以例如使用處理數據元素時與數據元素一起攜帶的排序鍵來對輸出數據元素進行排序，以恢復與對應的一組輸入數據元素相關聯的排序。可替代地，並行產生的輸出數據元素可以以與它們進入執行集的順序相同的順序合併，而不一定需要實施顯式排序操作。
與為執行集準備的執行代碼相關聯的各種計算特性可以由編譯器/解釋器120來配置，可以有或沒有來自用戶的輸入。例如，上述用於指示如何實施與特定執行集內的組件相對應的任務的嵌入信息可以包括以下任何內容。所述信息可以包括指示任務將完全串行執行(即，沒有並行性)的編譯器注釋。所述信息可以包括指示以與排序約束所允許的並行性一樣多的並行性來實施任務的編譯器注釋。所述信息可以包括指示與相同鍵值相關的任務被串行執行並且與不同鍵值相關的任務被並行執行的編譯器注釋(即，如上所述按鍵串行化)。
編譯器注釋或修改符可以用於指示各種計算特性中的任何一種：
·並發性(例如，如上所述的並行、串行、按鍵串行)
·不同執行集之間的優先性(precedence)(例如，一個執行集的所有任務發生在另一執行集的所有任務之後)
·事務性(例如，執行集的任務作為資料庫事務(database transaction)處理)
·資源鎖定(例如，執行集的任務通過特定資源(例如共享變量)實施，鎖住，允許任務將資源作為原子單元訪問)
·排序(例如，保留數據元素之間的排序)
·元組大小(例如，將由執行集的每個實例操作的數據元素的數量)
編譯器/解釋器120可以基於自動分析作為整體的執行集或數據處理圖的屬性，和/或基於接收來自用戶的輸入(例如，圖中的用戶注釋)確定這些特性。例如，如果在執行集中引用鍵值，則編譯器注釋可以指示按鍵串行化。如果在執行集內使用資源，則編譯器修改符可以在該執行集之前/之後允許鎖定/解鎖該資源。如果在執行集內存在資料庫操作，則執行集的每個實例可以被配置為作為資料庫事務執行。如果可以在編譯時確定可用的核的數量，則編譯器注釋可以指示每個核將對由數量為等於集合的總大小除以核的數量的數據項組成的數據項元組執行執行集的實例。
編譯器注釋和修改符可以被添加到以目標語言準備的代碼，諸如合適的高級語言(例如，DML)或低級可執行代碼，或數據處理圖的目標中間形式。例如，編譯器/解釋器120可以將組件插入到明確指示到執行集的入口點或出口點的數據處理圖中，或者用來開始/結束事務的組件可以放置在用於處理事務的組件集的入口/出口點，或者組件可以用於鎖定/解鎖資源。可替代地，編譯器/解釋器120可以將修改符添加為修改類型的數據流鏈路。
3 數據處理圖的用戶界面
在一些示例中，用戶界面允許用戶通過將組件拖動到畫布上並使用鏈路將組件的埠連接在一起來開發數據處理圖。在一些示例中，用戶界面在用戶開發數據處理圖時重複地將上述分配算法應用於數據處理圖。例如，當用戶向正在開發的數據處理圖中添加組件時，分配算法可以應用於具有被添加組件的圖。然後可以將由分配算法發現的結果執行集顯示為例如圍繞用戶界面中的組件繪製的框，或者顯示為包圍組件的任意形狀的區域，其可以通過用於在同一執行集中呈現包含多個組件的區域的唯一的顏色、陰影、紋理或標記來區分。在一些示例中，用戶然後可以通過向執行集添加組件或從執行集中去除組件來修改由分配算法發現的執行集。在一些示例中，分配算法驗證修改後的執行集是合法的。例如，各種埠之間可以存在組件和鏈路的一些配置，其可以潛在地以各種合法方式中的任一種劃分為多個執行集。在這樣的模糊情況下，分配算法可以默認地選擇執行集的一個分配，但是用戶可能已經期望進行執行集的不同分配，在這種情況下，用戶可以修改分配(例如，通過插入出口點以在組件鏈中更早地關閉執行集)。可替代地，分配算法可以被配置為識別其中可能有多個合法分配的模糊配置，並且提示用戶輸入以選擇一個配置。
參考圖10A，用戶已將三個組件(第一數據集1022，第一計算組件1024和第二數據集1026)拖動到數據處理圖開發用戶界面的畫布1028上。用戶還沒有使用鏈路將組件1022、1024、1026的埠連接在一起，並且分配算法尚未在數據處理圖中發現任何執行集(除了根執行集)。
參考圖10B，當用戶用鏈路將組件1022、1024、1026的埠連接在一起時，分配算法自動發現第一執行集1030，第一執行集1030包括第一計算組件1024。通過用戶界面將第一執行集1030顯示給用戶。當用戶繼續向圖中添加組件和鏈路時，分配算法自動發現執行集，並通過用戶界面顯示執行集。
參考圖10C，在一些示例中，用戶可能需要打破鏈路(例如，將另一組件插入到鏈路中)。在這樣的示例中，如果分配算法被允許重新分析數據處理圖，則第一執行集1030將被去除，可能導致用戶的工作中斷和丟失。
為了避免這種中斷，當用戶從數據處理圖中去除流或組件時，可以不執行分配算法，而是保持其餘組件及它們的執行集關聯未受影響。例如，在圖10C中，其輸入和輸出埠斷開，第一組件1024仍然包括在第一執行集1030中。在一些示例中，當斷開的組件被重新連接時，則允許分配算法自動地發現和顯示與重新連接的組件相關聯的任何執行集。
在一些示例中，如果數據處理圖的組件不具有明確的(例如，用戶定義的)執行集指定，則允許分配算法發現組件屬於哪個執行集。否則，如果組件具有明確的用戶定義的執行集指定，則不允許分配算法選擇該組件包括在哪個執行集中。例如，如果用戶將組件手動移動到給定的執行集中，則不允許分配算法將該組件包括在除用戶指定的執行集之外的任何執行集中。也就是說，對數據處理圖的任何用戶修改不能被分配算法重寫(overridden)。
在一些示例中，用戶界面允許用戶使用手勢或通過輸入設備進行的其他交互來將組件提升到給定執行集中和/或將組件從給定執行集中降級。在一些示例中，用戶可以使用菜單選項或其他提示來提升或降級組件。在其他示例中，用戶可以簡單地將組件拖動到用戶界面中的期望執行集中。
在一些示例中，用戶界面允許用戶為數據處理圖中的執行集指定一個或多個約束。例如，用戶可以將執行約束為在給定時間並行運行不超過N次。
在一些示例中，編譯器/解釋器120接收包括手動定義的執行集和由分配算法發現的執行集的混合的數據處理圖的表示。
在一些示例中，用戶可以使用界面定義另一類型的執行集，稱為啟用/禁止執行集。例如，用戶可以圍繞他們希望被包括在啟用/禁止執行集中的一個或多個組件繪製框。啟用/禁止執行集包括一個或多個組件並且具有標量輸入埠。如果上遊組件的標量輸出埠向啟用/禁止執行集的標量輸入埠提供一個數據元素，則允許啟用/禁止執行集中的組件執行。如果上遊組件的標量輸出埠向啟用/禁止執行集的標量輸入埠提供零數據元素，則啟用/禁止執行集中包括的組件被禁止。任何執行集(包括啟用/禁止執行集)可以包括控制輸入和輸出埠，其可用於確定整個執行集是否將被執行以及是否將控制信號傳播到其他組件或執行集。如果執行集被並行化(即具有多個實例)，則在執行任何實例之前必須激活輸入控制埠，並且在所有實例完成執行之後激活輸出控制埠。在一些示例中，通過將埠的可視表示放置在執行集的邊界上來提供這些輸入和輸出控制埠。在其他示例中，通過將這些輸入和輸出控制埠放置在執行集前方的附加組件上來提供這些輸入和輸出控制埠。例如，該附加的「對於所有組件」可以(例如，由用戶界面自動地或由用戶手動地)插入在上遊集合輸出數據埠和入口點指示符之間，或者代替入口點指示符(即，在上遊集合輸出數據埠和驅動輸入標量數據埠之間)。
如上文參照圖7注意到的，在一些示例中，用戶可以通過沿著數據處理圖的流放置執行集入口點和出口點組件來明確地定義執行集入口點和出口點。
在一些示例中，用戶界面提供實時反饋以在他們的圖包括非法操作時通知用戶。例如，如果存在由在用戶指定的執行集中的組件引起的衝突，則分配算法可以通過用戶界面向用戶發出警告。為了提供實時反饋，分配算法將驗證規則應用於數據處理圖以通知用戶數據處理圖是否合法。參考圖11A，非法數據處理圖配置1195的一個示例包括兩個數據源：將數據元素的第一集合饋送到第一執行集1197中的第一組件1102的標量埠的第一數據源1191，以及將數據元素的第二集合饋送到第二執行集1199中的第二組件1104的標量埠的第二數據源1198。第二執行集1199輸出數據元素的第三集合，然後該第三集合被輸入到第一執行集1197中的第三組件1106的標量數據埠。由於兩個不同的數據元素的集合連接到第一執行集1197中的不同標量埠，所以沒有辦法知道應該實例化第一執行集1197中的組件的多少並行實例(因為針對存在於第一執行集1197的邊界處的每個數據元素生成組件的一個實例)。在一些示例中，通過在例如第二組件1104上顯示錯誤指示符1108來通知用戶此衝突。
參考圖11B，非法數據處理配置1110的另一示例包括將數據元素的集合饋送到第一執行集1116中的第一組件1114的標量輸入埠的數據源1112。第一組件1114的標量輸出將其輸出作為數據的集合提供到第一執行集1116外部的第二組件1118的集合埠。第二組件1118從集合型輸出埠將數據元素的集合提供到第一執行集1116中的第三組件1120的標量數據埠。
通過從第一執行集1116外的第一組件1114的集合型輸出埠傳遞數據元素的集合，在第二組件1118處處理數據元素的集合，然後將處理後的數據元素的集合傳遞迴第三組件1120的標量埠，定義了「執行集循環」。
通常，執行集循環是非法的，因為它們不利於執行排序。例如，通常允許具有進入執行集或離開執行集的附加流，因為對於輸入而言，輸入數據可以在執行集被執行之前得到緩存，對於輸出而言，輸出數據可以在執行集完成執行之後被聚集。但是，如果需要外部組件在執行集之前和之後運行，則這是不可能的。
在一些示例中，通過在一個或多個組件上顯示錯誤指示符1108來通知用戶執行集循環。
在一些示例中，如果每個執行集入口點與至少一個對應的執行集出口點不匹配，則數據處理圖被認為是非法的。可替代地，具有入口點但沒有對應出口點的執行集可以被允許作為用戶定義的執行集，即使其不會被分配算法自動識別。在這些情況下，在(一個或多個)最下遊組件完成執行之後，執行集可以結束(而不提供任何輸出數據元素)。在一些示例中，如果每個鎖定操作不與對應的解鎖操作匹配，則數據處理圖被認為是非法的。可替代地，如果沒有明確指定，則可以推斷解鎖操作，並且如果推斷的解鎖操作將需要在與鎖定操作不同的執行集中，則僅指示為非法。在一些示例中，如果鎖定操作及其對應的解鎖操作不存在於同一執行集中，則數據處理圖被認為是非法的。
4控制圖的狀態機
在為執行準備數據處理圖的過程中，編譯器/解釋器120還在控制圖生成過程中生成控制圖。在一些實現方式中，生成控制圖包括生成用於執行與各個組件相對應的任務的可執行代碼和與確定任務之間的數據流和控制流的各種組件間鏈路相對應的代碼。這包括由編譯器/解釋器120發現的執行集的層級結構中的數據傳送和控制傳送。
生成這樣的可執行代碼的一部分包括在一些數據結構表示中為每個執行集生成對應的控制圖，包括任何啟用/禁止執行集。執行集內的任何嵌套執行集被視為表示該嵌套執行集的單個組件，用於生成控制圖。此代表性組件的埠對應於嵌套執行集內連接到跨越嵌套執行集邊界的鏈路的組件的埠。編譯器/解釋器120然後將使用該控制圖來生成控制代碼。這個生成的控制代碼有效地實現了在運行時控制執行的狀態機。特別地，一旦執行開始，則該生成的控制代碼控制組件或埠何時從該狀態機的一個狀態轉換到另一個狀態。
圖12A示出了編譯器/解釋器120如何將根執行集的第一組件對1202和第二組件對1204組合成控制圖1206的示例。在該示例中，第一組件對1202包括由相應集合數據埠1212、1214連接的第一組件1208和第二組件1210。第二組件對1204包括由相應標量數據埠1220、1222連接的第三組件1216和第四組件1218。
編譯器/解釋器120通過添加開始組件1224和完成組件1226並且按照數據處理圖的拓撲的指示將組件連接到開始組件1224和完成組件1226來創建控制圖。開始組件和完成組件不執行任何計算任務，但編譯器/解釋器120將使用開始組件和完成組件來管理控制信號，該控制信號將用於開始某些組件的執行並確定執行集中的所有組件何時已完成執行。
為了確定特定組件是否需要連接到開始組件1224，編譯器/解釋器120檢查至該組件的輸入，以基於到上遊串行埠的現有鏈路確定該組件是否沒有被指定開始執行，如上所述，上遊串行埠包括控制埠和標量埠。
例如，如果組件沒有至其控制輸入埠的鏈路，則它可能永遠不會開始執行，因為將永遠不會有控制信號來指示它開始。另一方面，即使沒有控制輸入，也可能取決於組件具有的數據輸入的類型，針對數據的到達而觸發該組件的執行。例如，如果組件具有標量輸入埠，則即使在其控制輸入埠處沒有控制信號，一旦該組件在其標量輸入埠處看到數據，該組件仍將開始執行。另一方面，如果組件只有集合數據輸入，那麼這種情況不會發生。如果這樣的組件不具有用來觸發執行的控制輸入或標量數據輸入，則它將需要至開始組件1224的連接。
在圖12A的上下文中，第一組件1208既不具有控制輸入也不具有標量數據輸入。因此，第一組件1208將無法自己開始執行。因此，第一組件1208必須連結到開始組件1224。第三組件1216同樣既不具有控制輸入也不具有標量數據輸入。因此，第三組件1216也必須連結到開始組件1224。
第四組件1218沒有控制輸入。但是它被連接以從第三組件1216接收標量數據輸入。因此，它將在通過其輸入標量埠1222接收到數據時開始執行。因此，第四組件1218不需要連接到開始組件1224。
第二組件1210被配置為從第一組件1208接收數據。然而，在輸入集合埠1214而不是在輸入標量埠處接收該數據。結果，類似於第一組件，第二組件1210也必須連接到開始組件1224。
編譯器/解釋器120還需要識別哪些組件將需要連接到完成組件1226。
通常，當組件缺少控制輸出鏈路或(任何類型的)數據輸出鏈路時，將組件連接到完成組件1226。在圖12A的左側的圖中，僅第二組件1210和第四組件1218滿足該條件。因此，如圖12A的右側所示，僅這兩個組件連接到完成組件1226。
圖12B類似於圖12A，不同的是在圖的左側的第一組件1208和第三組件1216之間存在控制鏈路。與規則一致，不再需要在得到的替代控制圖1206'中將第三組件1216連接到開始組件1224。
控制圖有效地定義分布式狀態機，其中組件及其串行埠響應於上遊組件和串行埠發生的轉換從一個狀態轉換到另一個狀態。通常，上遊組件將從一個狀態轉換到另一個狀態，導致其輸出串行埠轉換，這使得下遊組件的連結串行輸入埠轉換，這使得這些下遊組件轉換，等等。下面參照用於組件及其串行埠的狀態轉換圖更詳細地描述用於實現該行為的特定類型的狀態機的一個示例。
為了提供對狀態機的轉換的控制，編譯器/解釋器120移植額外的控制代碼到用於執行由特定組件表示的任務的代碼中。如本文所使用的，「移植(graft)」意指前附、後附或既前附又後附的控制代碼。前附的控制代碼在本文被稱為「前序(prologue)」代碼，而後附的控制代碼被稱為「結束(epilogue)」代碼。組件的前序代碼在組件執行其任務之前執行。組件的結束代碼在組件610A已經完成執行其任務之後執行。
移植的控制代碼檢查所存儲的狀態信息，例如累加器的值(例如，計數器倒計數到指示輸入已為調用組件準備就緒的值)或標誌的狀態(例如，設置為指示組件已被禁止的值的標誌)，以確定是否使一個或多個下遊組件執行其相應的任務。
在一個實施例中，前序代碼監視上遊輸出串行埠的狀態，並更新組件的輸入串行埠的狀態和組件的狀態，而結束代碼在組件完成實施其任務之後更新組件的輸出串行埠。
在另一個實施例中，代替監視上遊輸出串行埠的下遊組件的前序代碼，上遊組件的結束代碼更新下遊輸入串行埠的集合狀態，並監視該集合狀態以觸發下遊組件的前序代碼在適當的時間(例如當初始化為輸入串口數量的計數器達到零時)執行。可替代地，代替計數器從輸入埠的數量倒計數(或向上計數到輸入埠的數量)，可以使用另一形式的累加器來存儲用於觸發組件的狀態信息，例如存儲表示不同組件的不同埠的狀態的位的位圖。
作為該移植的控制代碼的結果，基於在特定組件的執行開始和結束時一個或多個上遊邏輯狀態的集合的發生，任務的完成自動導致以與由控制圖表示的數據控制依賴性一致的方式、並且以允許多個組件的並發操作並且允許使用條件控制邏輯來控制的方式自動執行其他任務。
圖13A和圖13B示出了可用於組件(圖13A的狀態轉換圖1300)和其串行埠(圖13B的狀態轉換圖1310)的示例性狀態機的狀態轉換圖。這兩個狀態轉換圖是類似的，不同之處在於，由於活動狀態1304與正在進行的執行相關聯，並且由於只有組件而不是埠實施執行，所以只有組件可以處於活動狀態1304。
將描述兩個狀態轉換圖的所有可能狀態，以及遵循狀態之間的每個轉換所需的條件，需要參考圖13A和圖13B。在狀態轉換圖的此描述中涉及的所有輸入和輸出埠均是串行埠，因為控制圖中的組件僅需要連結串行埠(而不是集合埠)。控制圖中的特定組件可以處於狀態轉換圖1300中的四個邏輯狀態之一。第一狀態是未決(pending)狀態1302。這是當與控制圖相關聯的執行集開始執行時，組件開始的狀態。如果組件的任何輸入埠處於未決狀態1312，則組件保持未決狀態1302。如果組件恰好沒有輸入埠，則它在未決狀態1302中開始，但是立即有資格從未決狀態1302轉換出。
從未決狀態1302，組件可以轉換到活動狀態1304或禁止狀態1306。
如果組件沒有輸入埠處於未決狀態1312並且並非其所有輸入埠都處於禁止狀態1316(即，至少一個輸入埠處於完成狀態1314)，則組件轉換到活動狀態1304。埠默認為「必需」，但可標記為「可選」。可選埠可以保持未連接到另一個埠，而不會導致錯誤(雖然可能有警告)。未連接的任何可選埠自動地處於完成狀態1314。只要組件仍在執行其任務，該組件就保持在活動狀態1304。當組件處於活動狀態1304時，其多個輸出埠可以在不同時間轉換或一起從未決狀態1312轉換到完成狀態1314或禁止狀態1316。在完成其任務的執行時，組件轉換從活動狀態1304轉換到完成狀態1308。
如果組件的任務已經完成執行，並且其所有輸出埠被「決斷(resolved)」，即不再未決，則組件轉換到完成狀態1308。
如果由於定製控制邏輯，或由於其所有輸入埠被禁止，或由於禁止了其所需輸入埠中的至少一個，或由於組件中的未處理錯誤而導致該組件的前序已觸發至禁止狀態1306的轉換，則該組件處於禁止狀態1306。組件的所有輸出埠也決斷到禁止狀態1316以向下遊傳播這種禁止。
對於埠，狀態轉換規則取決於埠是輸入埠還是輸出埠。
埠的初始狀態是未決狀態1312。輸入埠通常跟隨它所連結到的上遊輸出埠的狀態。因此，當上遊輸出埠轉換時，在控制圖中連結到該輸出埠的輸入埠轉換到相同的狀態。輸出埠保持未決，直到組件在其活動狀態期間確定輸出埠應決斷到什麼狀態。
如上所述，輸入埠跟隨它們所連結的上遊輸出埠。因此，對於連結到單個上遊輸出埠的輸入埠，當其所連結的上遊輸出埠轉換到完成狀態1314時，該輸入埠轉換到完成狀態1314。如果輸入埠通過多個鏈路連結到多個上遊輸出埠，則輸入埠在其上遊輸出埠中的至少一個轉換到完成狀態1314之後轉換到完成狀態1314。否則，如果所有上遊輸出埠轉換到禁止狀態1316，則輸入埠轉換到禁止狀態1316。一些實施例使用與該默認「或邏輯」不同的其他邏輯來確定是將輸入埠轉換到完成狀態1314還是禁止狀態1316(例如，「與邏輯」，其中僅當所有上遊輸出埠處於完成狀態1314時輸入埠才轉換到完成狀態1314)。如果組件的輸入數據埠決斷為完成狀態1314，則數據元素準備就緒供該組件處理。如果組件的輸出數據埠決斷為完成狀態1314，則數據元素準備就緒從該組件向下遊發送。
與輸入埠跟隨它們所連結到的上遊輸出埠的狀態的規則一致，當與其連結的上遊輸出埠決斷為禁止狀態1316時，輸入埠決斷為禁止狀態1316。輸出埠決斷為禁止狀態1316，或者因為活動的組件計算出的結果確定輸出埠應當被禁止，或者為了使得禁止從上遊被禁止組件向下遊傳播，或者如果組件中存在未處理的錯誤。在一些實施例中，編譯器可以通過禁止根在被禁止組件處的下遊組件的樹來優化執行，而不必一個組件接一個組件地向下遊傳播禁止。
在其他實施例中，可以使用各種替代狀態機，其中集合埠之間的鏈路也可以包括在控制圖中。在一些這樣的實施例中，集合埠的狀態轉換圖可以包括除未決狀態、完成狀態和禁止狀態之外的活動狀態，諸如在組件的狀態轉移圖1300中。當集合埠(作為輸出埠)產生數據或(作為輸入埠)消耗數據時，集合埠處於活動狀態。對於輸入集合埠，例如，一旦確定不是所有輸入埠都將被禁止，就可以在上遊產生第一數據元素時觸發活動狀態。在一些實施例中，沒有集合埠的禁止狀態。包括集合埠的狀態轉換的控制圖中的組件所遵循的轉換規則可以以與為輸入標量埠或控制埠處理完成狀態相同的方式來處理輸入集合埠的活動狀態。
5 計算平臺
回看圖1，數據處理圖的組件的實例在執行數據處理圖的情境中被派生(spawn)為任務，並且通常在計算平臺150的多個計算節點152中執行。如下面更詳細討論的，控制器140提供這些任務的調度和執行軌跡的監督控制方面，以便實現例如與計算負荷的分配，通信或輸入/輸出開銷的減少以及存儲器資源的使用相關的系統的性能目標。
通常，在由編譯器/解釋器120翻譯之後，整個計算被表達為可由計算平臺150執行的目標語言的過程的基於任務的規範130。這些過程利用原語，諸如「派生(spawn)」和「等待」，並且可以在過程中包括原語，或調用由程式設計師為高級(例如，基於圖的)程序規範110中的組件指定的工作過程。
在許多情況下，組件的每個實例被實現為任務，其中一些任務實現單個組件的單個實例，一些任務實現執行集的多個組件的單個實例，以及一些任務實現組件的連續實例。來自組件及其實例的特定映射取決於編譯器/解釋器的特定設計，使得所得到的執行保持與計算的語義定義一致。
通常，運行時環境中的多個任務被分層級排列，例如，一個頂級任務派生多個任務，例如，一個任務用於數據處理圖的每個頂級組件。類似地，執行集的計算可以具有用於處理整個集合的一個任務，其中多個(即許多)子任務分別用於處理集合的元素。
在運行時環境中，已經派生的每個任務可以處於一組可能狀態之一。在第一次派生時，任務在被初始執行之前處於派生狀態。在執行時，它處於執行狀態。任務時而可能處於暫停狀態。例如，在某些實現方式中，調度器可以在任務已經超過處理器利用的量、正在等待資源等時將任務置於暫停狀態。在一些實現方式中，任務的執行不被搶佔，並且任務必須放棄控制。有三個暫停子狀態：可運行，被阻止和已做完。例如，如果任務在完成其計算之前放棄控制，則任務是可運行的。當例如在父任務檢索到任務的返回值之前該任務完成其處理時，該任務是已做完的。如果任務正在等待該任務外部的事件，例如另一個任務的完成(例如，因為它已經使用了「等待」原語)或數據記錄的可用性(例如，阻止in.read或out.write函數的一次執行)，則任務是被阻止的。
再次參考圖1，每個計算節點152具有一個或多個處理引擎154。在至少一些實現方式中，每個進程引擎與在計算節點150上執行的單個作業系統進程相關聯。取決於計算節點的特性，在單個計算節點上執行多個處理引擎可能是有效的。例如，計算節點可以是具有多個單獨處理器的伺服器計算機，或者伺服器計算機可以具有帶多個處理器內核的單個處理器，或者可以是具有多個內核的多個處理器的組合。在任何情況下，執行多個處理引擎都可能比在計算節點152上僅使用單個處理引擎更有效。
處理引擎的一個示例託管在虛擬機的情境中。一種類型的虛擬機是Java虛擬機(JVM)，其提供在其中可以執行以Java Bytecode(Java字節碼)的編譯形式指定的任務的環境。但是也可以使用其他形式的處理引擎，其可以使用或可以不使用虛擬機架構。
參考圖14，計算節點152的每個處理引擎154具有一個或多個運行器1450。每個運行器1450使用一個或多個進程或進程線程來執行可運行任務。在一些實現方式中，每個運行器具有相關聯的進程線程，但是運行器與線程的這種關聯不是必需的。在任何時候，每個運行器正在執行計算的最多一個可運行任務。每個運行器具有單獨的可運行隊列1466。計算的每個可運行任務在系統的運行器1450的一個可運行隊列1466中。每個運行器1450具有調度器/解釋器1460，其監視當前運行的任務，並且當該任務將狀態改變為已做完，被阻止或暫停時，從運行隊列1466中選擇另一個任務並執行它。任務與運行器相關聯，並且不可運行的運行器的任務被保持在可運行隊列1466之外，例如，如圖中所示，在被阻止和已做完隊列1468中。
例如，當初始化處理引擎154時，可以創建運行器1450，為每個引擎創建預配置數量的運行器。如下所述，在一些實現方式中，可以向處理引擎添加或去除運行器，並且甚至在數據處理圖的執行期間，可以從計算平臺150添加和去除處理引擎本身。然而，對於下面的初始描述，我們假設處理引擎的數量以及每個處理引擎內運行器的數量保持恆定。
作為示例，對數據處理圖的處理開始於在頂層任務中執行主過程。例如，基於任務的控制器140指示與處理引擎1450之一的監視器1452通信的計算節點中的一個開始執行主過程。在該示例中，監視器1452將用於執行主過程的任務放置在處理引擎之一的可運行隊列1466中。在該示例中，運行器是空閒的(即，此時沒有其他任務在運行，並且在可運行隊列中沒有其他可運行任務)，所以該運行器的調度器/解釋器1460從可運行隊列中取出該任務並且開始執行任務。當以需要解釋的語言表達過程時，調度器/解釋器1460解釋過程的連續語句。
在該示例中，主過程的第一語句為支持無序集合的流的鏈路創建鏈路緩存器1470(即，分配存儲器)，其在該示例中包括無序無界緩存器，即緩存器1，緩存器2和緩存器3。可以使用各種方法創建這種類型的組件間鏈路，並且管理用於這些鏈路的相關聯的計算資源(包括鏈路緩存器1470)，其包括其上遊埠是集合埠的任何鏈路。在一些示例中，鏈路緩存器1470包括用於表示集合的源的輸出集合埠的緩存器和用於表示集合的目標的輸入集合埠的單獨緩存器。這些緩存器可以在開始處理集合之前在運行時分配，並且在對集合的處理結束之後被解除分配(即，釋放用於緩存器的內存)。在該示例中，這些鏈路緩存器1470被分配在其中任務的運行器正在執行的處理引擎154的存儲器中。通常，其中創建緩存器的存儲器在半導體隨機存取存儲器(RAM)中，儘管在一些實現方式中，諸如磁碟之類的其他存儲設備可以用於存儲至少一些緩存數據。注意，在其他方法中，緩存器對運行器本身而言可以是本地的。在實踐中，如果處理引擎154被實現為作業系統進程，則緩存器被創建為該進程的地址空間中的存儲器區域。因此，直接基於硬體地址對緩存器的訪問限於在該進程內執行的指令。注意，在這種方法中，如果多個運行器將能夠讀取或寫入緩存器，則可能對緩存器需要至少進行一些同步和訪問控制，例如使用鎖(lock)或信號量(semaphore)。在其中每個運行器在作業系統進程內被實現為單個線程的方法中，緩存器可以與特定運行器相關聯，並且所有訪問可以被限制到該運行器，從而避免來自多個線程的潛在爭用。在下面的討論中，我們假設可以從處理引擎中的任何運行器訪問緩存器，並且實現適當的訪問控制以允許這樣的共享訪問。
主進程的後續步驟涉及派生或主過程調用的forall(用於所有)原語。通常，至少在默認情況下，任務或子任務的派生使得這些任務最初在與父進程相同的運行器中形成。例如，派生的Work_Read_External_Data(工作讀取外部數據)任務在同一個運行器上派生。在任務正在訪問外部數據的程度上，任務可以利用至該外部數據的I/O接口1464。例如，該接口可以包括到外部資料庫、網絡數據連接的端點等的開放連接。這樣的I/O接口可以綁定到特定的運行器，因此使用該接口的任務可能需要訪問僅來自該運行器的接口，如下面在運行器之間任務的潛在遷移的情境中進一步討論的。在該示例中，我們假設任務以合理計量的方式填充緩存器1，並且不會例如通過使緩存器1增長超過處理引擎的容量而「淹沒(overwhelm)」系統。下面還討論對控制方面的方法，例如，以避免資源的擁塞或耗盡。
與Work_Read_External_Data任務的執行並發地，forall_Work A導致針對從緩存器1讀取的每個記錄派生任務。特別地，「forall」原語引起由要執行原語的自變量標識的任務的多個實例，其中實例的數量通常由在運行時接收的數據元素的數量確定，並且其中它們被執行的位置和它們被調用的順序可以不受編譯器限制而用於在之後的運行時確定。如上所述，在默認情況下，這些任務也在相同的運行器1450上創建，並且在沒有其他控制的情況下，與從緩存器1可得到的數據一樣快地派生這些任務。Work_B和Work_Read_External_Data的任務類似地在相同的運行器上創建。
注意，基於任務的規範使用「forall」原語，而沒有明確地指定運行時控制器將如何實現任務的分布，以導致所有數據待處理。如上所述，運行時控制器可以使用的一種方法是在同一計算節點上派生單獨的任務，然後依賴於遷移特徵以使得任務在分開的節點上執行，從而平衡負載。可以使用其他方法，其中「forall」原語導致在多個節點上直接執行多個任務。在遊標(cursor)定義內存資料庫的表的行的基於索引的子集的情況下，遊標「forall」原語的實現可以使得遊標被分割成多個部分，每個部分與存儲在不同節點上的記錄相關聯，並且為不同節點上的遊標的單獨部分派生任務，從而導致處理和數據存儲的局部性。但是應當理解，可以在運行時控制器和分布式計算平臺的一個或多個實施例中實現多種方法來執行在作為編譯器120輸出的基於任務的規範130中使用的「forall」原語。在一些示例中，方法的選擇可以取決於例如基於記錄的數量，計算節點上的數據分布，節點上的負載等的運行時決策。在任何情況下，用於實現「forall」原語的方法不一定對於數據處理圖的開發人員或編譯器的設計者是已知的。
系統的特徵在於任務可以在創建運行器之後在運行器之間傳送。非常一般地，這種任務傳送的一種方式是通過「挪用」或「拉動」機制來實現的，其中空閒或至少輕微加載的運行器使得來自另一運行器的任務被傳送給它。雖然可以使用各種標準，但是運行器可運行隊列1466中的多個可運行任務可以基於本地標準(諸如在其可運行隊列中是否有少於閾值數量的任務)來確定該運行器是否應當尋求從其他運行器挪用的任務。在一些實現方式中，更全局性的決策進程可用於在多個運行器上重新平衡任務隊列，但總體效果是類似的。
在至少一些實施例中，將任務從一個運行器挪用到另一個運行器不是必然涉及轉移該任務的所有數據。例如，只有當前執行「框架」中可訪問的數據(例如，用於從當前程序範圍可訪問的局部和全局變量的數據，例如當前子例程調用)與引用一起打包回任務「主(home)」運行器。此數據足以在遷移的目標運行器處創建任務的可運行副本，並且目標可運行隊列中的條目準備好在在該運行器中執行。
當遷移的運行器完成執行時，或者通過從局部變量可用的程序範圍返回該遷移的運行器耗盡了傳送到該運行器的數據時，任務被傳送回主運行器，其中用於任務的數據被合併，並且任務再次在其主運行器處可運行。
注意，在單個處理引擎內傳送任務期間，運行器之間的通信可以通過本地存儲器(即，避免磁碟或網絡通信)，從而消耗相對少的資源。在允許處理引擎之間進行挪用和遷移的實現方式中，在從一個運行器轉換到另一個運行器時，任務消耗相對較少的資源，例如，主要消耗處理引擎之間的通信資源而不是計算資源。此外，這種通信的等待時間相對不顯著，因為主運行器和目標運行器被假定為在傳送期間忙於計算，主運行器是因為其可運行隊列被大量填充並且因此不可能空，而目標運行器是因為挪用是在預期在目標處的可運行隊列被清空的情況下進行的。
在與圖2A-圖2B中所示的計算相關聯的任務的執行的示例中，任務挪用機制將用於計算的負載分布在一個或多個處理引擎的運行器上。然而，注意，某些數據訪問被限於特定運行器(或可能限於特定處理引擎)。例如，如上文所述，緩存器2的數據可以由單個運行器(或可能一組運行器)訪問，然而可能需要寫入緩存器2的Work_A任務可能已經被無法寫入緩存器2的運行器挪用。在這樣的情況下，當任務需要採取必須在與當前正在執行的任務所在的運行器不同的運行器上執行的動作時，以「遷移」或「推動」方式將任務遷移到合適的運行器。
在至少一些示例中，計算平臺150支持一組全局變量對(鍵，值)的全局數據存儲。該數據存儲可以分布在多個計算節點(或處理引擎)上的存儲器(例如，RAM或磁碟)上。鍵的名稱空間是全局的，因為鍵的規範在所有計算節點152及其運行器1450處具有相同的含義。這些變量的值在任務被實例化、執行和終止時持續，從而提供了一種在任務之間傳遞信息的方式，而不需要經由共同的父任務將這種信息從一個任務傳遞到另一個任務。如下所述，根據鍵對進行的訪問被控制，使得值的使用和更新不會導致任務之間的衝突。在一些示例中，任務對於它們的一些或全部執行而獲得對特定(鍵，值)對的獨佔訪問。
通常，(鍵，值)對的存儲是分布的，並且任何特定(鍵，值)對與特定計算節點152相關聯。例如，(鍵，值)對存儲在該計算節點處的分布式表存儲1480中。在一些實現方式中，派生原語允許指定鍵和從相關聯的變量到任務的局部變量的映射。當指定一個鍵時，派生的任務在其執行的持續時間內獲得對鍵的獨佔訪問。在執行開始之前，將值從存儲傳遞到任務的本地上下文中，並且在執行完成後，本地上下文中的值將被傳遞迴全局存儲。如果一個派生原語指定另一個正在執行的任務使用的鍵，則這個新派生的任務將被阻止，直到它可以獲得對該鍵的獨佔訪問。在一些實現方式中，每個計算節點可以確定特定鍵的主節點，並且當請求派生任務時，該請求由(鍵，值)對駐留的計算節點處理，並且任務的執行將最初在該節點開始。在替代實施例中，用於獲得對這種全局共享(鍵，值)對的類似的獨佔訪問的其他方法不是必然涉及在與存儲相同的位置發起任務，例如通過傳送獨佔訪問的請求並且隨後使用更新的鍵值來傳送獨佔訪問的釋放。任務可以創建新的(鍵，值)對，在默認情況下，在創建新(鍵，值)對時新的(鍵，值)對存儲在任務運行的節點上。
全局狀態變量的一種用途是在執行集合的連續記錄的函數期間進行聚集。例如，全局存儲維護分配給鍵的值的窗口，而不是作為單項的值。因此，在編程模型中，可以將值添加到與鍵相關聯地維護的歷史中，並且可以提供先前添加的值的函數。值的窗口可以根據項目的數量(即，最後的100項)定義，通過時間窗口定義(即，例如在最後10分鐘中添加的項目，由值被添加時的時間定義或由每個值被添加時提供的顯式時間戳定義)。注意，編程模型不需要明確刪除落在窗口外的舊值，窗口的定義允許實現自動執行這樣的刪除。編程模型包括用於創建這種基於窗口的鍵控全局變量的多個原語(例如，定義窗口的性質和範圍)，將值添加到鍵以及值的窗口的計算函數(例如，最大值，平均值，不同值的數量，等等)。一些原語將針對鍵的新值的添加和窗口函數的返回(例如，將新值添加到鍵並返回添加的最後100個值的平均值)組合。
在至少一些示例中，全局存儲還包括經由稱為句柄的標識符訪問的面向記錄的共享數據。例如，句柄可以標識數據記錄的源或宿，或者作為另一示例，句柄可以標識數據集中的特定記錄。通常，句柄被鍵入，因為句柄點提供了訪問數據的方式，並且還提供被訪問的數據結構的定義。例如，句柄可以具有與其相關聯的數據記錄的欄位(列)結構。
在至少一些示例中，全局存儲器(例如，在計算節點的存儲器中)包括針對多行類型化數據的一個或多個表的表存儲，其中該表格或表格的特定記錄經由稱為句柄的標識符被訪問。表的行類型可以是具有向量、記錄向量等的層級記錄類型。在一些示例中，表可以具有提供對行的哈希或B樹(有序)訪問的一個或多個索引，並且遊標可以基於表、索引或索引和鍵值創建。行可以單獨插入、更新或刪除。為了支持事務處理，任務可以鎖定一個或多個表的一行或多行，例如，用於在對數據處理圖的組件的處理期間讀取或更新訪問。表可以被視為用於數據並行操作的集合，例如，作為數據處理圖中的數據的源或目標。通常，對表進行索引，並且可以基於產生遊標的索引來選擇表的行的子集，然後使用該遊標來提供所選擇的行作為數據源。在一些示例中，另外的原語對任務可用，用於諸如分割遊標和估計與句柄相關聯的記錄的數量的動作。當提供遊標作為用於執行集的數據源時，遊標可以被分割成多個部分，每個部分將表的一些行提供給執行集的對應實例，從而提供並行性並且適當地分割遊標使得能夠在存儲行的節點上執行。數據表還可以由實現事務的任務訪問，使得維護數據表的修改，以便在任務之外不可見，直到由任務明確地提交這些修改。在一些示例中，可以通過鎖定表的一個或多個行來實現這樣的事務支持，而在其他示例中，可以實現涉及行的多個版本的更複雜的方法，以比可以僅使用鎖定提供更高的潛在並發性。
文件、數據流和內存表都是被稱為集合的示例。讀取器任務從集合中讀取記錄，並且寫入器任務將記錄寫入集合。一些任務既是讀取器又是寫入器。
如上所述，表示集合的流可以使用內存緩存器在運行時系統中實現。可替代地，在各種實現方式中可以使用任何形式的存儲，包括資料庫內的表或分布式存儲系統。在一些實現方式中，使用內存中分布式資料庫。在一些實現方式中，編譯器以不是必然暴露給數據處理圖的開發人員的方式使用內存表來實現這樣的流。例如，編譯器可以使上遊組件填充表的多個行，並且下遊組件讀取先前填充的行，從而實現無序數據流。運行時間控制器可以調用與執行集相對應的任務的多個實例，從而通過以數據元素被接收到存儲中的順序不同的順序從存儲中取出這些數據元素，對來自上遊集合埠的驅動數據元素進行處理，防止某些形式的阻塞。例如，可以調用任務的實例而不阻止任何特定的其他實例調用任何實例(即，直到任何特定的其他實例完成處理一個或多個數據元素之後)。
通常，集合中的記錄可以在該記錄中的數據被首次寫入之前具有句柄。例如，可以將表設置為索引的一組記錄的目標，並且即使在寫入那些記錄的數據之前，各個記錄也可以具有句柄。
6 實現方式
上述方法可以例如使用執行合適的軟體指令的可編程計算系統來實現，或者可以在諸如現場可編程門陣列(FPGA)或一些混合形式的合適的硬體中實現。例如，在編程方法中，軟體可以包括在一個或多個編程或可編程計算系統(其可以是諸如分布式、客戶端/伺服器或網格的各種架構)上執行的一個或多個電腦程式中的過程，每個計算系統包括至少一個處理器，至少一個數據存儲系統(包括易失性和/或非易失性存儲器和/或存儲元件)，至少一個用戶界面(用於使用至少一個輸入設備或埠接收輸入，並且用於使用至少一個輸出設備或埠提供輸出)。軟體可以包括例如提供與數據處理圖的設計、配置和執行相關的服務的更大程序的一個或多個模塊。程序的模塊(例如，數據處理圖的組件)可以被實現為符合存儲在數據倉庫中的數據模型的數據結構或其他有組織的數據。
軟體可以使用持續一段時間(例如，動態存儲器裝置(例如動態RAM)的刷新周期之間的時間)的介質的物理特性(例如，表面凹坑和平臺、磁疇或電荷等)以非暫時性形式存儲，例如被實施在易失性或非易失性存儲介質或任何其它非暫時性介質中。在準備加載指令時，軟體可以提供在有形、非暫時性介質上，例如CD-ROM或其他計算機可讀介質(例如，可由通用或專用計算系統或設備讀取)，或者可以通過網絡的通信介質被遞送(例如，被編碼成傳播信號)到其被執行的計算系統的有形、非暫時性介質。可以在專用計算機上或使用諸如協處理器或現場可編程門陣列(FPGA)或特定的專用集成電路(ASIC)的專用硬體來執行處理中的一些或全部。處理可以以分布式方式實現，其中由軟體指定的計算的不同部分由不同的計算元件執行。每個這樣的電腦程式優選地存儲在或下載到可由通用或專用可編程計算機訪問的存儲設備的計算機可讀存儲介質(例如，固態存儲器或介質，或磁介質或光介質)上，用於當計算機讀取存儲設備介質以執行本文所述的處理時，配置和操作計算機。本發明的系統還可以被認為可實現為配置有電腦程式的有形的、非暫時性介質，其中如此配置的介質使得計算機以特定和預定義的方式操作以執行本文描述的一個或多個處理步驟。
已經描述了本發明的多個實施例。然而，應當理解，前述描述旨在說明而不是限制本發明的範圍，本發明的範圍由所附權利要求的範圍限定。因此，其他實施例也在所附權利要求的範圍內。例如，在不脫離本發明的範圍的情況下可以進行各種修改。另外，上述的一些步驟可以是與順序無關的，並且因此可以以與所描述的順序不同的順序來執行。
權利要求書(按照條約第19條的修改)
1.一種計算系統，包括：
存儲系統，存儲一個或多個基於圖的程序規範，至少第一基於圖的程序規範包括對應於任務的多個組件和所述多個組件的埠之間的有向鏈路，所述第一基於圖的程序規範包括：
(1)由連結的組件的相應輸出埠和輸入埠定義的第一類型的鏈路配置，以及
(2)由連結的組件的相應輸出埠和輸入埠定義的第二類型的鏈路配置，其中所述第二類型的鏈路配置不同於所述第一類型的鏈路配置；
編譯器，被配置為根據所述第一基於圖的程序規範生成目標程序規範，其中所述編譯器識別不同類型的鏈路配置，並且在所述目標程序規範中提供目標原語的一次或多次出現，用於為流過具有所述第二類型的鏈路配置的鏈路的數據元素的每次出現執行函數；以及
一個或多個計算節點，每個計算節點包括至少一個處理器，所述計算節點中的至少第一計算節點被配置為：
啟動所述目標程序規範的執行，以及
對於與所述目標原語的所述一次或多次出現相關聯的一個或多個組件，在運行時確定以下中的至少一個：(1)對應於組件的任務的實例將被調用的順序，或者(2)執行對應於組件的任務的實例將所位於的計算節點。
2.根據權利要求1所述的計算系統，其中所述第一計算節點還被配置為：
對於從所述第一基於圖的程序規範中第一組件的埠到所述第一基於圖的程序規範中第二組件的埠具有所述第一類型的鏈路配置的第一鏈路，串行調用對應於所述第一組件和所述第二組件的任務，並且
對於從所述第一基於圖的程序規範中第三組件的埠到所述第一基於圖的程序規範中第四組件的埠具有所述第二類型的鏈路配置的第二鏈路，調用對應於所述第四組件的任務的多個實例，用於處理由所述第三組件提供的數據元素的不同相應子集。
3.根據權利要求2所述的計算系統，其中所述第一計算節點還被配置為將所述多個實例中的至少一些實例分配到多個計算節點中的不同計算節點上執行。
4.根據前述權利要求中任一項所述的計算系統，其中所述目標原語標識與一個或多個任務的任務集相對應的函數，並且標識與具有所述第二類型的鏈路配置的鏈路相對應的數據元素的集合。
5.根據當從屬於權利要求2或3時的權利要求4所述的計算系統，其中所述多個實例中的至少一些實例被應用於由所述目標原語標識的所述集合中的不同的相應數據元素。
6.根據權利要求5所述的計算系統，其中被調用實例的數量等於由所述目標原語標識的所述集合中數據元素的數量，並且每個實例被應用於不同的相應數據元素。
7.根據權利要求5所述的計算系統，其中獨立於所述第一基於圖的程序規範中的任何信息來確定被調用實例的數量。
8.根據權利要求7所述的計算系統，其中被調用實例的數量與存儲由所述第一基於圖的程序規範引用的數據的計算節點的數量至少一樣多。
9.根據權利要求5至8中任一項所述的計算系統，其中將由所述目標原語標識的函數應用於一數據元素包括：使用該數據元素作為與該函數相對應的所述一個或多個任務的任務集的數據源來執行所述一個或多個任務。
10.根據權利要求3所述的計算系統或當從屬於權利要求3時的權利要求4至9中任一項所述的計算系統，其中將所述多個實例中的至少一些實例分配到不同計算節點上執行包括：在運行時確定所述多個實例將在其上執行的計算節點的數量。
11.根據前述權利要求中任一項所述的計算系統，其中具有所述第一類型的鏈路配置的鏈路向所述編譯器指示將在所連結的組件之間傳遞單個數據元素，並且具有所述第二類型的鏈路配置的鏈路向所述編譯器指示將在所連結的組件之間傳遞多個數據元素。
12.根據前述權利要求中任一項所述的計算系統，其中所述第一基於圖的程序規範包括由連結的組件的相應輸入和輸出埠定義的鏈路的第三類型的鏈路配置，所述第三類型的鏈路配置向所述編譯器指示所連結的組件將串行執行，並且向所述編譯器指示將在所連結的組件的任務之間傳遞單個數據元素。
13.根據前述權利要求中任一項所述的計算系統，其中所述編譯器被配置為識別與相應組件對應的一個或多個任務的一個或多個任務集。
14.根據權利要求13所述的計算系統，其中一個或多個任務的每個任務集具有作為數據源的數據元素的單個集合，其向一個或多個任務的該任務集的不同實例提供不同的數據元素。
15.根據權利要求13所述的計算系統，其中一個或多個任務的每個任務集對應於一個或多個節點的至少一個有向無環圖，其中有向無環圖的每個節點對應於一任務或被標識的任務集，並且有向無環圖的每個有向邊對應於具有所述第一類型的鏈路配置的鏈路。
16.根據權利要求15所述的計算系統，其中一個或多個節點的有向無環圖具有單個根節點。
17.根據前述權利要求中任一項所述的計算系統，其中每個計算節點被配置為執行至少一個調度器，用於派生進程以執行對應隊列中的任務。
18.根據權利要求17所述的計算系統，其中所述第一計算節點被配置為將一個或多個任務從由所述第一計算節點執行的第二調度器的隊列移動到由所述第一計算節點執行的第一調度器的隊列中。
19.根據權利要求17所述的計算系統，其中所述第一計算節點被配置為將一個或多個任務從由所述第一計算節點執行的調度器的隊列移動到由第二計算節點執行的調度器的隊列中。
20.一種方法，包括：
存儲一個或多個基於圖的程序規範，至少第一基於圖的程序規範包括對應於任務的多個組件和所述多個組件的埠之間的有向鏈路，所述第一基於圖的程序規範包括：
(1)由連結的組件的相應輸出埠和輸入埠定義的第一類型的鏈路配置，以及
(2)由連結的組件的相應輸出埠和輸入埠定義的第二類型的鏈路配置，其中所述第二類型的鏈路配置不同於所述第一類型的鏈路配置；
根據所述第一基於圖的程序規範生成目標程序規範，並且識別不同類型的鏈路配置，並且在所述目標程序規範中提供目標原語的一次或多次出現，用於為流過具有所述第二類型的鏈路配置的鏈路的數據元素的每次出現執行函數；以及
使用至少一個計算節點，
啟動所述目標程序規範的執行，以及
對於與所述目標原語的所述一次或多次出現相關聯的一個或多個組件，在運行時確定以下中的至少一個：(1)對應於組件的任務的實例將被調用的順序，或者(2)執行對應於組件的任務的實例將所位於的計算節點。
21.一種以非暫時形式存儲在計算機可讀介質上的軟體，所述軟體包括用於使得計算系統執行以下操作的指令：
存儲一個或多個基於圖的程序規範，至少第一基於圖的程序規範包括對應於任務的多個組件和所述多個組件的埠之間的有向鏈路，所述第一基於圖的程序規範包括：
(1)由連結的組件的相應輸出埠和輸入埠定義的第一類型的鏈路配置，以及
(2)由連結的組件的相應輸出埠和輸入埠定義的第二類型的鏈路配置，其中所述第二類型的鏈路配置不同於所述第一類型的鏈路配置；
根據所述第一基於圖的程序規範生成目標程序規範，並且識別不同類型的鏈路配置，並且在所述目標程序規範中提供目標原語的一次或多次出現，用於為流過具有所述第二類型的鏈路配置的鏈路的數據元素的每次出現執行函數；以及
使用至少一個計算節點，
啟動所述目標程序規範的執行，以及
對於與所述目標原語的所述一次或多次出現相關聯的一個或多個組件，在運行時確定以下中的至少一個：(1)對應於組件的任務的實例將被調用的順序，或者(2)執行對應於組件的任務的實例將所位於的計算節點。
22.根據權利要求1所述的計算系統，其中所述編譯器為具有所述第二類型的鏈路配置的每個鏈路提供所述目標原語的出現，而不為具有所述第一類型的鏈路配置的任何鏈路提供所述目標原語的出現。