數據流編程

數據流編程是一種解決多核處理器的效率利用問題的高性能並行編程模型。數據流編程與傳統編程語言有着明顯區別，它通過數據驅動的方式執行，將需要處理的數據分配到各個核上，將數據的計算與通信相分離，通過任務調度與分配，利用軟件流水的並行特性來充分的挖掘流程序中潛在的並行性，使各個核之間負載均衡。在數據流範例中，一個數據流程序的靜態實例會按照它的結構被描述成一張有向圖。圖中節點表示計算單元，邊代表數據傳輸路徑。相鄰節點間通過邊傳輸數據，節點消耗數據進行計算，並將產生的數據輸出到輸入輸出序列作為下一個計算單元的輸入。

數據流編程語言主要關注程序的狀態，並根據狀態的變化導致操作發生。數據流編程語言本質上是並行的，因為操作依賴於滿足時會導致操作執行的輸入。這意味着與一個正常程序不同，後一個操作後跟着一個操作，在數據流程序中，只要滿足輸入並且沒有設定順序，操作就會執行。 通常，數據流編程語言使用大型哈希表，其中鍵是程序的數據，而表的值是指向程序操作的指針。這使得多核程序更易於在數據流編程語言中創建，因為每個核心只需要散列表就可以工作。 數據流編程語言的一個常見示例是電子表格程序，它具有受其他數據列影響的數據列。如果一列中的數據發生變化，其他列中的其他數據可能會隨之變化。

應用流編程模型的數據流編程語言（Data Flow Programming Language）是一種面向領域的編程語言（Domain Specific Language，DSL），將流應用領域中以數據為驅動和功能獨立的特性融入語言中，將計算和通信分離，同時隱藏通信的具體細節。一系列獨立的計算單元中藴含了大量的並行，採用數據流語言進行編程的難點在於如何充分利用流應用中的潛在並行性，如何利用數字媒體領域的流程序的特性來對流程序的調度劃分進行優化。當前主要的流編程語言，有Stream It和 CUDA，它們針對不同的專業應用，如 Stream It 主要針對科學計算與編解碼處理，而 CUDA 主要針對 GPU 應用。這些語言對於不同的體系結構支持不夠，存在一定的侷限性。

麻省理工學院(MIT)的 Saman Amarasinghe 教授帶領的團隊設計出一種 Stream It數據流編程語言，它是為了方便大規模的流應用編程而開發的流編程模型，同時，Stream It 能夠適用於多樣的體系結構，包括現有的商業型的單處理器，多核結構以及集羣平台。在 Stream It中的基本計算單元叫做 filter，它是一個單輸入單輸出程序塊，程序塊中是用户定義的將輸入數據轉換成輸出數據的過程。每一個 filter 都包含一個用作初始化的 init 函數以及用來描述穩態下最細粒度過程的 work 函數。filter 能夠通過FIFO 隊列與它相鄰的 filter 進行通信，並且使用了 push、pop 和 peek 操作，這 3種操作所需用到的窗口值大小在 work 函數中指定。filter 組合的基本程序設計結構有3 種，分別是 pipeline、splitjoin 與 feedbackloop。

Imagine是斯坦福大學開發的一種可編程流處理器，它採用了一種新的層次化的流編程模型，該模型將數據組織成流，將計算單元表示成核心(kernel),Imagine 在計算時分為兩級：流級和核心級，這兩級分別在主機和 Imagine 上運行。Imagine 流編程模型的主要目標是能夠很好的開發數據的並行性，由於它支持的 SIMD 方式要求程序具有簡單的控制機制，因此，kernel的主要組織方式是循環結構。流語言從 MIT 的 Stream It 後來又發展到了 UMich 的Flexstream。這種新的流編程模型比 Stream It 更為靈活，而且它在 Stream It 的基礎上增加了動態調度部分，這種調度策略會根據底層結構的改變來相應的改變流程序的調度和劃分方法，從而使得流程序的效率不會隨着底層平台的改變而大幅降低 ^[1]  。

數據流是指一組有順序的、有起點和終點的字節集合，程序從鍵盤接收數據或向文件中寫數據，以及在網絡連接上進行數據的讀寫操作，都可以使用數據流來完成。數據的性質、格式不同，則對流的處理方法也不同，因此，在Java的輸入/輸出類庫中，有不同的流類來對應不同性質的輸入/輸出流。在java．io包中，基本輸入/輸出流類可按其讀寫數據的類型之不同分為兩種：字節流和字符流。

數據流分為輸入流(InputStream)和輸出流(OutputStream)兩類。輸入流只能讀不能寫，而輸出流只能寫不能讀。通常程序中使用輸入流讀出數據，輸出流寫入數據，就好像數據流入到程序並從程序中流出。採用數據流使程序的輸入輸出操作獨立與相關設備。輸入流可從鍵盤或文件中獲得數據，輸出流可向顯示器、打印機或文件中傳輸數據。

為了提高數據的傳輸效率，通常使用緩衝流(Buffered Stream)，即為一個流配有一個緩衝區(buffer)，一個緩衝區就是專門用於傳輸數據的內存塊。當向一個緩衝流寫入數據時，系統不直接發送到外部設備，而是將數據發送到緩衝區。緩衝區自動記錄數據，當緩衝區滿時，系統將數據全部發送到相應的設備。

當從一個緩衝流中讀取數據時，系統實際是從緩衝區中讀取數據。當緩衝區空時，系統就會從相關設備自動讀取數據，並讀取儘可能多的數據充滿緩衝區。