數據流圖是一種有向圖， 用來表示數據驅動計算。數據流計算有兩種不同方法。第一種方法是數據驅動法， 一旦操作要求的全部輸人數據是有效的，操作被點火。另一種方法是需求驅動法，僅當某些操作需要它的結果時，操作被點火，必要時進行計算。
基本介紹
- 中文名：數據流計算
- 外文名：Data flow calculation
- 類型：計算機科學
- 學科：跨學科
- 性質：計算
- 分類：數據驅動法、需求驅動法
數據流概念,數據流系統,來源,
數據流概念
傳統計算機馮·諾依曼計算機以控制流計算模型為基礎， 它是某些計算模型的實現。這種計算機進行計算， 必須規定操作或程式序列以控制機器。近些年來， 已深入研究另外一些計算模型， 如數據流模型。在數據流模型中， 實現操作取決於數據的內部依賴性和資源的可利用性。數據流機單處理單元的框圖可說明基本數據流系統結構。如圖1所示。
圖1
數據流圖是一種有向圖， 用來表示數據驅動計算。在數據流圖中，每個節點表示一個運算元。數據和控制被封裝在令牌內它在連線節點的弧上流動。當輸人令牌出現在節點的所有輸人弧上時, 實現操作,也就是說節點被點火。節點點火條件的語句描述稱為點火規則。一個節點的點火引起數據和控制新令牌的產生。最終導致進一步計算的發生。
數據流的主要優點有：
（1）發揮了並行性。
（2）用數據流語言寫一個程式比較簡單。
（3）說明並行控制並不要求程式設計師了解全部操作和測定數據的內部依賴性， 這樣簡化了編程。
（4）使通信手段和同步機製成為其系統結構的不可分割部分， 它比現存的機器更可靠。
（5）保證多處理機計算以可重複的方式運行， 而現存的江多處理機不提供這種保證。
（6）解決了存貯等待時間問題，以分階段方式實現輸人存貯。
（7）提高了機器的性能和計算機專業人員的生產率。
數據流系統
MIT靜態數據流
MIT靜態結構的框圖如圖2所示。
圖2
存貯部件分成若干模組， 每個模組保存操作和運算元以及節點的目標地址。如同傳統計算機那樣， 程式裝人存貯器內。被啟動的指令通過R2從存貯器送到凡。其結果通過R1從PEs傳送到存貯器。當沒有指令被啟動時， 程式執行完成。用這種結構設計成的系統支持虛存和多用戶系統頁面調度。這種設計的優點包括指令的顯同步和保證多處理機以再現方式運行。靜態結構不能最完善地發揮並行性， 因為任何給定時刻任意輸人弧上僅有一個令牌。這就禁止不同功能行為和疊代的同時執行。
關聯模型數據流系統結構
關聯模型數據流ATD(Associative model data flow)避免使用令牌作同步工具， 而利用在有效通道上傳播的信息修正所有分布控制狀態以回響每個操作的執行。關聯存貯機制如內容可定址的存貯器用來實現存貯， 對全部修正傳送加以監測， 如果修正同關聯存貯器的數據單元有關， 那么， 進行修正， 否則， 信息被忽略。
ATD其它最重要的特徵是以每個操作為基礎，避免爭奪共享資源如存貯器讀和寫緩衝器的爭奪。ATD是一種靜態系統結構， 它具有靜態系統結構的所有優點。在成為一種健壯的計算機模型以前還必須作更進一步的研究和仿真。
P-RISC系統結構
並行P-RISC系統結構完全刪除了等待和匹配單元， 而對所有操作使用一個RISC狀的APU。P-RISC系統結構的主要特性有使用一個RISC狀指令集；改變系統結構支持多道計算；加入分叉和聯結結構管理多通道；用指令實現完全存貯以分階段方式實現輸人存貯指令。
P-RISC系統結構由一組呢和許多存貯單元組成， 通過一組開關網將他們聯結起來。P-RISC沒有等待一匹配單元， 取而替之， 它將計算順序鍵有關的全部運算數存貯一組存貯器內。為解決存貯器爭奪問題以分階段方式實現輸人存貯指令。在等待輸人結果到達時， 處理器不封鎖，它僅僅執行下一條被啟動的指令。每當輸人到達， 中止的指令將再被啟動並且， 最終將平穩地執行。每個現存的程式都能在P-RISC上執行， 這一事實總結了這種系統結構的優點， 此外， 它還保持數據流機發揮並行性方面的優點。
來源
數據流計算來自於一個概念：數據的價值隨著時間的流逝而降低，所以事件出現後必須儘快地對它們進行處理，最好數據出現時便立刻對其進行處理，發生一個事件進行一次處理，而不是快取起來成一批處理。例如商用搜尋引擎，像Google、Bing和Yahoo 等，通常在用戶查詢回響中提供結構化的Web結果，同時也插入基於流量的點擊付費模式的文本廣告。為了在頁面上最佳位置展現最相關的廣告，通過一些算法來動態估算給定上下文中一個廣告被點擊的可能性。上下文可能包括用戶偏好、地理位置、歷史查詢、歷史點擊等信息。一個主搜尋引擎可能每秒鐘處理成千上萬次查詢，每個頁面都可能會包含多個廣告。為了及時處理用戶反饋，需要一個低延遲、可擴展、高可靠的處理引擎。
對於這些實時性要求很高的套用，若把持續到達的數據簡單地放到傳統資料庫管理系統（DBMS）中，並在其中進行操作，是不太切實的。傳統的DBMS並不是為快速連續的存放單獨的數據單元而設計的，而且也並不支持“持續處理”，而“持續處理”是數據流套用的典型特徵。另外，現在人們都認識到，“近似性”和“自適應性”是對數據流進行快速查詢和其他處理（如數據分析和數據採集）的關鍵要素，而傳統DBMS的主要目標恰恰與之相反：通過穩定的查詢設計，得到精確的答案。
另外一些方案是採用MapReduce來進行實時數據流處理。但是，儘管MapReduce做了實時性改進，仍然很難穩定地滿足套用需求。這是因為MapReduce（Hadoop）框架為批處理做了高度最佳化，系統典型地通過調度批量任務來操作靜態數據，任務不是常駐服務，數據也不是實時流入；而數據流計算的典型範式之一是不確定數據速率的事件流流入系統，系統處理能力必須與事件流量匹配。
最近Facebook在SIGMOD’ 2011上發表了利用Hbase/Hadoop進行實時處理數據的論文，通過一些實時性改造，讓批處理計算平台也具備實時計算的能力。這類基於MapReduce流式處理的特點有三：
1）將輸入數據分隔成固定大小的片段，再由MapReduce平台處理，缺點在於處理延遲與數據片段的長度、初始化處理任務的開銷成正比。小的分段會降低延遲，增加附加開銷，並且分段之間的依賴管理更加複雜（例如一個分段可能會需要前一個分段的信息）；反之，大的分段會增加延遲。最最佳化的分段大小取決於具體套用。
2）為了支持流式處理，MapReduce需要被改造成Pipeline的模式，而不是reduce直接輸出；考慮到效率，中間結果最好只保存在記憶體中等等。這些改動使得原有的MapReduce框架的複雜度大大增加，不利於系統的維護和擴展。
3）用戶被迫使用MapReduce的接口來定義流式作業，這使得用戶程式的可伸縮性降低。
綜上所述，流式處理的模式決定了要和批處理使用非常不同的架構，試圖搭建一個既適合流式計算又適合批處理的通用平台，結果可能會是一個高度複雜的系統，並且最終系統可能對兩種計算都不理想。
數據流計算有兩種不同方法。第一種方法是數據馭動法， 一旦操作要求的全部輸人數據是有效的，操作被點火。另一種方法是需求驅動法，僅當某些操作需要它的結果時，操作被點火，必要時進行計算。這樣避免了許多冗餘計算, 從而減少了循環的令牌數。但大量研究已集中在數據驅動上，這種計算是兩種方法中不太複雜的一種。
