數據流結構

數據流結構

數據流結構可以用由節點和連線節點的有向弧組成的數據流圖來表示,節點代表執行的運算或功能,有向弧代表節點被執行的次序,通常,數據流結構用一個五元組(N,A,V,v0,f)來描述。

概念

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

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

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

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

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

這種數據流結構的主要優點是省去了通用數據匯流排,傳統結構中的這條匯流排一直被取指令和其他系統運算元據占用著。

類型

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

變換型數據流圖

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

變換型DFD 變換型DFD

事務型數據流圖

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

事務型DFD 事務型DFD

基本模組

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

 一個可變數據流結構的模型  一個可變數據流結構的模型

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

實例

軟體數據流結構設計實例

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

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

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

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

相關詞條

熱門詞條

聯絡我們