數據流結構

數據流結構可以用由節點和連接節點的有向弧組成的數據流圖來表示，節點代表執行的運算或功能，有向弧代表節點被執行的次序，通常，數據流結構用一個五元組(N，A，V，v₀，f)來描述。其中:N={n_1，n₂，…，n_M}是節點的集合，A={a₁，a₂，…，a_l}∈N×N是節點之間弧的集合;V={v₁，v₂…，v_L}∈V₁×V₂×…×V_L是弧所代表的數值的集合，v_i∈V_i是弧a_i代表的數值;v₀∈V是弧的初始值;f=定義了各個節點n_i∈N實現的功能，I(n_i)和O(n_i)分別是節點n_i∈N上入弧和出弧代表的數值。

數據流結構直觀地表達了數學公式，非常適用於描述計算密集的系統。在硬件實現時，為了提高系統的吞吐率往往運用流水線技術，相連的各個節點之間用寄存器或先入先出(FIFO)隊列連接。在數字視頻信號、數字電視信號以及高速無線傳輸碼流處理器中，待處理的碼流具有不同的速率和處理要求。為了適應不同速率和不同結構的碼流，對應的數據流結構必須可以動態地改變結構，即處理節點間的連接關係必須是可變的。同時，由於各個節點完成的功能不同，其處理速度也有差異，必須用足夠大的FIFO來銜接不同處理速度的節點。由於FIFO的大小會直接影響到最後硬件實現數據流結構的面積和功耗，在設計階段需要對數據流結構的處理時序進行動態模擬，以此確定在保證處理性能前提下FIFO的最佳大小。 ^[1] 

數據流結構化設計其主要的目標是將軟件設計為多個結構合理、功能單一的模塊，從而形成系統的模塊結構圖。這主要是將分層次的結構圖作為一種主要的表示方式。

數據流結構不需傳統的程序記數器，也不要從存貯器取指令。這種結構的系統中流動着帶有標記的數據，每個數據都包括了足夠的信息，説明必須對它進行的處理內容。每項數據是個32位的令牌，其中有16位工作數據、4位控制區、7位識別標誌(它還告訴處理機該數據的用途)、4位處理機字和1位冗餘位。控制區含有區分16位工作數據類別的信息。這個數據可以是象素信息，也可以是控制功能，例如來自宿主機的程序指令。一旦這個32位令牌到達了指定的處理機，它的識別標誌區域就不甩了，這個部分可作為另一個4位域使用。

隨着數據在處理機內從一個結點流到另一個結點，該數據的拷貝在不同的結點上也在被並行地處理這樣就縮短了對指令序列中後續處理步驟的硬件無效等待時間。數據在一個系統結點上完成一次運算後，就流到下一個結點；第一個結點就可以處理後面的數據項。

這種數據流結構的主要優點是省去了通用數據總線，傳統結構中的這條總線一直被取指令和其他系統操作數據佔用着。 ^[2] 

將數據流圖轉化為軟件的結構，就需要DFD（數據流圖）類型的研究。而由於軟件系統是複雜龐大的，就需要人工智能軟件的加入。數據流類型主要可分為變換型和事務型。

這主要是由輸入、變換、輸出組成。如圖1。變換型數據處理的工作其可以分為三個步驟，第一步是取得數據，第二步是變換數據，第三步是給出數據，這是DFD的基本思想。變換是系統的主加工，變換輸入端的數據流是系統的邏輯輸入，輸出端為邏輯輸出。 ^[3] 

對輸入流分離成許多發散的數據流，通過某個加工形成許多路徑，並根據輸入值來選擇一條路徑進行執行，這種特徵的DFD是事務型的數據流圖，這個加工可以稱為事務處理中心，如圖2所示。 ^[3] 

PetriNets是結構化、可視化的建模方法，是一個模型化的工具，它用於模型化某一類問題，即有並行事件的離散事件的系統的問題，特別是系統內事件和條件間的關係，有效地描述製造系統資源衝突、死鎖、緩衝區容量等問題。PetriNets在硬件設計中的運用研究主要集中於異步數字電路的設計綜合，以及對系統的性能評估等領域。

PetriNets一般用來建立系統的控制模型，而數據流結構的PetriNets模型並不是系統的計算模型，不能用來驗證數據流結構的功能。該模型只是數據流結構的時序模型，主要描述數據流結構中各模塊的狀態變化。通過數據流結構PetriNets模型的執行，數據流結構中各模塊在實際運行中的狀態可以得到模擬，以此來幫助優化數據流結構設計。數據流結構的硬件實現可以分為以下5種基本模塊:

(1)2個節點通過寄存器連接。

(2)2個節點通過FIFO連接。

(3)節點具有流水線計算能力

(4)2個數據流匯聚到1個節點。

(5)1個節點分叉出2個數據流。

給出了對應着5種基本模塊的PetriNets模型。在這些基本模塊的PetriNets模型中，處理節點映射為PetriNets的變遷，連接寄存器或FIFO映射為PetriNets的位置，數據流映射為PetriNets的令牌。利用這5種基本模型可以構建任意複雜的具有固定組成的數據流結構。對於可變的數據流結構，提出了一種稱為Prophid的結構。該結構由一個協處理器陣列、一個可編程切換矩陣和一個全局控制器組成。協處理器陣列中任意一個處理單元的輸出FIFO通過可編程切換矩陣可以連接至協處理器陣列中其他各個處理單元的輸入FIFO，全局控制器控制可編程切換矩陣，改變協處理器的連接關係，從而實現可變結構的數據流結構。實際上，這種數據流結構更像一種數據流結構和控制器的混合體。

Prophid結構比較規則，易於硬件實現，但是需要一個額外的控制器模型。在模擬階段對於具有確定變化的可變數據流結構可以通過適當的激發延時來實現，大大簡化了模型的建立過程，而模型的時序特徵卻基本保持不變。

圖3所示為一個可變的數據流結構，圖3a為在t₀時刻節點A和節點B相連，在t₁時刻節點C和節點B相連。圖3b所示為在Prophid結構中，節點A，節點B，節點C之間連接關係的改變是通過控制器控制一個2選1選擇器來實現的.圖3c為在簡化的PetriNets模型中，位置P0代表節點A的輸出FIFO，位置P1代表節點C的輸出FIFO，位置P2代表節點B的輸入FIFO，遷移T₀的延時為0，遷移T₁的延時為(t₁-t₀)，在模擬時由於T₁延時激發，令牌的遷移路徑和時序與根據圖3b建立的PetriNets模型相同。 ^[1] 

對於銷售管理系統，其數據流圖轉化為軟件結構。就其分層圖來看可以清晰地表明其所具有的四個主要功能：訂貨處理、進貨處理、缺貨處理和銷售統計，這四個都可以進行平行處理。所以從整體上分析根據事務類型數據流圖進行設計，並利用功能來對四個處理選擇。

“藍牙”是近年來短距無線互連較為標準的一種方式，這主要是利用較為低端的數據通信及語音傳輸場合，Bluetooth這是在2.4GHz的開放頻段來進行工作，這也較為容易受到其他的使用該頻段的無線設備干擾。無線傳輸的數據往往會含有前向差錯控制編碼、循環冗餘碼編碼等差錯控制技術。藍牙還採用了跳頻技術。這也使得結構極其複雜。

通過建立人工智能軟件，可以更好的對不同的數據包進行動態模擬的打包過程，來使得Bluetooth打包器在數據流結構設計上得到更好的優化。

數據流結構設計其在早期對軟件進行精化，可以利用不同的軟件結構導出實現，再通過評價和比較，從而得到較好的結果，這種優化，其是將軟件結構設計和過程設計有效的分開。人工智能軟件的使用，使得軟件結構可以在沒有時間的影響因素下更好的開發和精化；還可以在詳細設計階段將一些較為耗費時間的模塊進行仔細的設計、處理，以求在效率上得到提高；利用高級程序設計語言來進行程序的編寫；利用人工智能軟件可以將大量的佔用處理機資源孤立出來。 ^[3]