天天看點

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

本節書摘來自華章出版社《資訊實體融合系統(cps)設計、模組化與仿真——基于 ptolemy ii 平台》一書中的第3章,第3.1節,作者:[美]愛德華·阿什福德·李(edward ashford lee),更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

本文第二部分主要介紹一些常用于系統設計、模組化和仿真的計算模型。雖然不是一個很全面的集合,但也是一個比較有代表性的集合。這裡提到的計算模型(model of computation,moc)是相對成熟、容易了解并完全可以實作的計算模型。這些計算模型在ptolemy ii之外的工具上大部分也是可以實作的,但除ptolemy ii外沒有工具可全部實作它們。

ptolemy ii 能夠使異構系統的開發和仿真一同進行,将開發和仿真作為整個系統模組化的一部分。正如前兩章讨論的那樣,不同于其他設計和模組化環境,ptolemy ii的一個關鍵創新在于支援多種計算模型,這些計算模型可被剪裁以适應具體的模組化問題。這些計算模型定義模型的行為,計算模型的種類由模型中使用的訓示器決定。在ptolemy ii的術語中,訓示器實作了一個域,這是對計算模型的實作。是以,螢幕、域和計算模型就被綁定在一起。比如說,當建構一個包含sdf訓示器(一種同步資料流訓示器)的模型時,實際上已經通過sdf計算模型建立了一個“sdf域”模型。

本章對目前ptolemy ii中的可用資料流域(dataflow domain)進行描述,其包含同步(靜态)資料流模型和動态資料流模型。資料流域适用于那些涉及資料值流處理的應用,這些資料值流在一系列角色間流動,角色以一定的方式進行資料值流的轉化。這些模型通常叫作管道和濾波器(pipe and filter)模型,因為角色之間的連接配接類似于承載流的管道,并且角色就像對這些流做了一些改變的濾波器。資料流域幾乎是忽略時間的,盡管同步資料流(sdf)有能力在疊代之間建立有均勻時間間隔的流模型。後續的章節将讨論其他的域,以及其選擇和使用。

同步資料流(synchronous dataflow,sdf)域,也稱為靜态資料流(static dataflow),由lee and messerschmitt(1987b)提出,是ptolemy ii最先開發的域(或者計算模型)之一。它是資料流模型的一種特殊類型。在資料流模型中,當角色需要的資料輸入并可用時,角色開始執行(其被點火)。sdf是一種相對簡單的資料流,角色的執行順序是靜态的,不依賴被處理的資料(令牌的值在角色之間傳遞)。

在一個同構sdf(homogeneous sdf)模型中,當角色的每一個輸入端口都有令牌時,角色被點火,并在每一個輸出端口産生一個令牌。在這種情況下,訓示器僅需確定當角色獲得資料後再點火,并且模型中的一次疊代包含每個角色的一次點火。第2章的大多數例子就是同構sdf模型。

然而不是所有的角色每次點火都隻會産生和消耗一個令牌,某些角色在它們點火前需要多個輸入令牌并産生多個輸出令牌。負責決定角色執行順序的sdf排程程式支援比同構sdf更複雜的模型。隻要指定每個端口上的每個角色點火所産生和消耗的令牌數量來給出這些速率,sdf排程器就能夠對任意資料速率角色的執行進行排程。

例3.1 有些角色需要多個輸入令牌才能點火,spectrum角色就是這樣一個例子。如圖3-1所示為一個可以計算帶噪聲正弦波的頻譜的系統,該系統與圖2-20中構造的相同。spectrum角色有一個單獨的參數,用來指定快速傅裡葉變換(fft)的采樣點位數(order)。快速傅裡葉變換用來進行頻譜的計算。如圖3-1顯示了order設定為8以及疊代次數設定為1的模型的輸出(見17.2節)。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

圖3-1 一個多速率sdf模型。spectrum角色需要256個令牌才能點火,是以這個模型的疊代需要256個sinewave、channel、sequenceplotter firings角色的點火以及一次spectrum角色的點火

當order參數設定為8時,spectrum角色的點火需要28(256)個輸入樣本,并産生28個輸出樣本。為了使spectrum角色點火一次,為它提供輸入資料的sinewave和channel角色必須各自點火256次。sdf訓示器提取該關系,并定義模型的一個疊代由sinewave、channel、sequenceplotter角色的256個點火行為和spectrum角色的一個點火行為組成。

這個例子實作了一個多速率(multirate)模型,即角色的點火速率并不是完全相同的。特别是,spectrum角色的執行速率比其他角色慢。對于多速率模型的執行,有且隻有一次疊代是很常見的。在下一節,訓示器将使用平衡方程來決定每次疊代中各個角色的點火次數。

3.1.1 平衡方程

考慮a和b兩個角色之間的單一連接配接,如圖3-2所示。圖中符号表示當a點火時,它在輸出端産生m個令牌,當b點之火時,它在輸入端消耗n個令牌。m和n是非負整數。a點火qa次,b點火qb次。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

當且僅當滿足下面的平衡方程時,a所産生的令牌才能都被b消耗掉,

qam = qbn(3-1)

給定的qa和qb滿足式(3-1)時,系統保持平衡,即a産生的令牌與b消耗的令牌數量一樣。

假設希望能處理任意數量的令牌,典型的流應用就是此類情況。一個簡單的政策是點火角色aqa次(qa為任意大的數)并點火角色bqb次,其中qa和qb滿足式(3-1)。然而,該政策是一個低級政策,因為它需要在一個緩沖區中存儲一個任意大數量的未消耗令牌。一個較優的政策是求出滿足式(3-1)的最小正整數qa和qb。然後建立一個排程表,點火角色aqa次,角色bqb次,并且也可以多次重複排程,而不需要更大的存儲空間來存儲未消耗的令牌。也就是說,可以在有界緩沖區(bounded buffer)(緩沖區中未消耗的令牌數量有限)内完成無限的執行(unbounded execution)(處理任意數量令牌的執行)。在每輪排程(被稱為一次疊代)中,角色b消耗的令牌數量與角色a産生的令牌數量恰好一緻。

例3.2 假設在圖3-2中,m = 2,n = 3。這裡有多種可能解來比對平衡方程,其中一種是qa=3和qb=2。根據這些值,可以重複以下排程:

a, a, a, b, b

另一個排程也可以使用:

a, a, b, a, b

事實上,後面這種排程有一個優勢,它用來存儲中間令牌的存儲器更少。一旦有足夠的令牌b就會點火,而不是等待a完成整個循環。

式(3-1)的另一組解是qa = 6和qb = 4。與上一個使系統保持嚴格平衡的解相比,這組解包含了更多次的點火行為。

qa = 0和qb = 0也滿足式(3-1),但是如果角色點火的數量是零,就會無法完成工作。顯然,這不是想要的解,負的解也是毫無意義的。

在預設情況下,sdf訓示器為平衡方程求最小的正整數解,并且依據該組解建構排程表,使模型中的角色保持應有的點火次數。對于一個執行序列,若每個角色的點火次數都與方程解出的結果完全一緻,則稱為一次完整疊代(complete iteration)。

在更複雜的sdf模型中,每個角色之間的連接配接都會導緻一個平衡方程。是以,模型定義一個方程組并求最小正整數解是重要的。

例3.3 圖3-3展示了一個由3個sdf角色組成的網絡。這些連接配接産生了如下平衡方程組:

qa = qb

2qb = qc

2qa = qc

這些方程的最小正整數解是:qa = qb = 1,qc = 2,是以下面的排程可以一直重複進而得到一個有界緩沖區内無限執行的情況:

a, b, c, c

平衡方程并不是總有非零解,如下所述。

例3.4 圖3-4顯示了一個有3個sdf角色的網絡,其平衡方程的唯一解是一個無效解,qa = qb = qc = 0。結果就是,對于該模型來說,沒有可以在有界緩沖區進行無限執行的可能。即它不能保持平衡。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

擁有平衡方程非零解的sdf模型稱為一緻的(consistent)。如果唯一解是零解,那麼它是不一緻的(inconsistent)。一個不一緻的模型不存在在有界緩沖區進行無限執行的情況。

lee and messerschmitt (1987b)說明如果平衡方程有非零解,那麼它也總有一個對于所有的角色i,qi都是非負整數的解。此外,對于連接配接模型(其中任意兩個角色之間都有通信路徑),他們給出了求最小正整數解的過程。該過程形成了sdf模型排程器的基礎。

例3.5 圖3-5顯示了一個sdf模型,它大量使用了sdf的多速率功能。模型在機器上運作,audiocapture角色從機器的麥克風中捕獲聲音,在每秒8000次采樣的預設速率下産生一系列樣本。chop角色從包含500個樣本的輸入塊中提取128個樣本塊(見3.1.3節補充閱讀)。spectrum角色計算功率譜,得到功率随着頻率變化的情況,即功率是頻率的函數。兩個sequencetoarray角色構造數組,然後arrayplotter角色将數組用圖形表示(見第17章)。圖中兩個特殊點是對哨聲的響應。注意,頻譜的峰值約出現在1700hz

和-1700hz處。

模型中的sdf訓示器計算出每點火一次chop、spectrum、sequencetoarray和繪圖儀都需要點火audiocapture角色500次。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

圖3-5 該模型從麥克風中擷取聲音信号并計算其功率譜。此圖展示了一個頻率大約為1700hz的哨聲功率譜

補充閱讀:sdf排程器

使用sdf的一個關鍵優勢是,對于包含一些并行執行角色的給定模型),有多種可能的排程。在這種情況下,資料流圖中的角色可以被映射到多核結構或者分布式體系結構中不同的處理器中以便提高性能。lee and messerschmitt (1987a)通過把sdf圖轉換為一個無環優先圖(apg),将一些經典作業工廠中的房間排程算法(coffman, 1976),特别是hu(1961)提出的那些算法,運用在sdf中。lee and ha(1989)将排程政策分為完全動态排程(fully dynamic scheduling)(所有排程決策在運作時完成)、靜态配置設定排程(static assignment scheduling)(除了處理器配置設定的決策外其他所有決策都在運作時完成)、自定時排程(self-timed scheduling)(隻有角色點火的時間安排在運作時決定)和完全靜态排程(fully-static scheduling)(排程的每個方面都在運作時前完成)。sih and lee (1993a)對作業工廠中的房間排程技術進行了解釋,用以說明解釋處理器之間的通信開銷(見 sih and lee (1993b))。pino et al. (1994)展示了如何建構異構多處理器的排程。falk et al.(2008)給出了一個基于聚類的并行排程政策,并說明了該政策在多媒體應用中可帶來顯著的性能提升。

除了并行排程政策外,其他的排程優化也很有用(見bhattacharyya et al.(1996b))。ha and lee (1991)放松了sdf的限制,允許資料依賴的角色疊代點火(一種稱為準靜态排程(quasi-static scheduling)的技術)。bhattacharyya and lee(1993)為角色疊代調用提出優化排程政策(也見bhattacharyya et al. (1996a))。bhat-tacharyya et al.(1993)提出的優化排程主要減少對記憶體的使用,随後并将這些優化應用到嵌入式處理器的代碼生成中(bhattacharyya et al.,1995)。murthy and bhattacharyya (2006)收集通過排程和緩沖區共享來最小化記憶體使用的算法。geilen et al.(2005)的研究表明,模型檢測技術可以用于記憶體優化。stuijk et al. (2008)探究吞吐量與緩沖之間的折中(見moreira et al. (2010))。sriram and bhattacharyya (2009)開發了減少并行sdf中同步操作數量的調優化度。同步確定一個角色在它接收需要點火的資料前不會被點火,然而,如果一個之前的同步已經確定資料準時到達,那麼該同步就不需要了。通過操作排程,可以減少所需同步點的數量。

補充閱讀:頻率分析

sdf域對信号處理特别有效。信号分析的一種基本操作方式是将時域信号轉換成頻域信号,反之亦然(見lee and varaiya(2011))。支援這一操作的角色可以在actors→ signalprocessing →spectrum庫中找到,如下所示。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

fft和ifft利用快速傅裡葉變換算法對一個信号分别進行離散傅裡葉變換(dft)和逆變換。order參數用于指定每個fft計算的輸入令牌數。它是“基2”算法,這意味着需要的令牌數是2的幂,且order參數指定指數的值。比如,如果order=10,那麼用于每個點火的輸入令牌數就是210=1024。剩下的角色可實作多種頻譜估計算法,它們都是使用fft作為元件的複合角色。這些算法以分貝(db)為機關輸出信号功率,作為頻率的函數。輸出頻率範圍為-fn~fn,

其中fn是奈奎斯特頻率(采樣頻率的一半)。也就是說,最先輸出的一半代表負頻率,餘下的一半代表正頻率。

spectrum是最簡單的譜估計器。它計算輸入信号的fft,并将結果轉換為以分貝計量的功率。

smoothedperiodogram通過首先估計輸入的自相關性來計算功率譜。該方法對輸入進行平均,并且對噪聲不敏感。

maximumentropyspectrum是一個參數譜估計器。它使用levinson-durbin算法構造回歸(ar)模型的參數,該模型能合理地産生輸入信号。然後選擇最大化熵的模式(見kay (1988))。它是最複雜的譜估計器,通常産生最平滑的估計。

如圖3-6所示為3個譜估計器輸出的比較,其中輸入由3個含噪聲的正弦曲線組成。為一個應用選擇正确的譜估計器是個複雜的主題,超出了本書的範圍。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

圖3-6  spectrum、smootheperiodogram和maximumentropyspectrum譜估計技術的比較

3.1.2 回報回路

在sdf中,一個回報回路必須至少包含一個sampledelay角色的執行個體(在flowcontrol→

sequencecontrol子庫中)。若沒有該角色,回路将産生死鎖(deadlock),即回報回路中的角色将無法點火,因為它們依賴彼此的令牌。sampledelay角色通過在模型開始點火前在它的輸出端産生初始令牌來解決這一問題。初始令牌通過initialoutputs參數來指定,該參數定義了一個令牌數組。這些初始令牌能使下遊角色點火,并打破無初始令牌時将在回報回路中的循環依賴。

例3.6 如圖3-7中所示的模型。為一個同構sdf模型,其使用回報回路産生一個計數序列。sampledelay角色通過在它的輸出能産生一個值為0的令牌來開始該過程。這個令牌與從const角色來的一個令牌一起,能使addsubtract角色點火。該角色的輸出能使下一個sampledelay點火。在初始點火之後,sampledelay角色将輸入無修改地複制到輸出。輸入到它的輸出不變。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

圖3-7 帶回報回路的sdf模型其中必須至少有一個sampledelay角色的執行個體

一緻性對保證緩存區有界是充分條件,但是并不足以保證一個模型的無限執行。即使模型是一緻的,它也可能産生死鎖。sdf訓示器分析模型的一緻性和死鎖。為了允許回報,它對待延時角色(delay actor)與其他角色不同。延時角色在它接收到輸入令牌之前能夠産生初始輸出令牌。它之後的行為與普通的sdf角色類似,在每次點火時消耗與産生固定數量的令牌。在sdf域中,初始令牌了解為執行的初始條件,而不是執行本身的一部分。是以,排程器将保證在sdf執行開始前産生所有的初始令牌。從概念上,sampledelay角色可以被放在回報連接配接上的初始令牌代替。

例3.7 如圖3-8所示為一個在回報回路上有初始令牌的sdf模型,平衡方程為:

3qa = 2qb

2qb = 2qa

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

最小正整數解存在,是:qa=2、qb=3,是以模型是一緻的。如圖3-8所示,在回報連接配接上有4個初始令牌,下面的排程可以一直疊代

a, b, a, b, b

這個排程從角色a開始,因為在執行的開始;僅有角色a可以點火,因為角色b沒有足夠的令牌。當a點火時,它從4個初始令牌中消耗3個令牌,留下1個令牌。它傳送3個令牌給b。此時,僅有b可以點火,消耗由a發送來的3個令牌中的2個。并且又提供2個令牌給它的輸出。此時,角色a可以再次點火,因為它的輸入端有3個令牌。它将消耗所有令牌并産生3個令牌。在此,b在它的輸入擁有4個令牌,能夠點火2次。在那2次點火之後,2個角色都已經點火了必要的次數,并且回報緩沖區再一次擁有了4個令牌。排程由此将資料流圖傳回到它的初始情況。

然而,若在回報路徑上的初始令牌少于4個,模型就會死鎖。例如,如果隻有3個令牌,那麼a可以在b之後點火,但是不會有足夠的輸入令牌使其再次點火。

lee and messerschmitt (1987b) 讨論了求解平衡方程的過程,還讨論了一個要麼為無限執行提供排程,要麼證明這樣的排程不存在的過程。通過這些過程,sdf模型的有界緩沖區和死鎖就可解決 (這意味着,ptolemy可以确定在任何sdf模型中是否會發生死鎖或者存在無界緩沖區)。

3.1.3 資料流模型中的時間

到目前為止,在已示的sdf例子中,使用了sequenceplotter角色,而不是timedplotter角色(見第17章)。這是因為sdf域通常不使用其模型中的時間概念。在預設情況下,時間不會随着sdf模型的執行而推進(即使sdf訓示器确實包含了一個稱為period的參數,該參數可以通過在模型的每次疊代中的一個固定量來推進時間)。是以,在大多數的sdf模型中,timedplotter角色顯示的時間軸通常等于零。相比之下,sequenceplotter角色進行一個非基于時間值序列的描述,是以經常用于sdf模型。在第7章和第9章中讨論的離散事件和連續域包含了大量的更強的時間概念,是以經常使用timeplotter。

補充閱讀:多速率資料流角色

ptolemy ii的庫提供了一些産生“與/或”的角色,它們在每點火一次需要消耗多個令牌。最基本的一些如下所示:

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

commutator和distributor在flowcontrol→aggregators子庫中,将來自多個信号的令牌轉換為一個令牌序列,反之亦然。commutator有一個多重端口輸入,在每次點火時,它從每個輸入通道中讀取固定數量的令牌(由其blocksize參數給出),并把所有來自輸入通道的令牌輸出為一個序列。distributor則為其逆過程。

downsample和upsample位于signalprocessing→filtering中,丢棄或者插入令牌。downsample 讀取固定數量的令牌(由它的factor參數給出),并輸出其中一個令牌(由phase參數選擇)。upsample在輸入令牌之間插入固定數量的零值令牌。

repeat位于flowcontrol→sequencecontrol中,除了用疊代方式輸入令牌代替插入零值令牌外,其他方面類似于upsample。

arraytosequence和sequencetoarray位于array庫中,将數組令牌轉換為一個令牌序列,反之亦然。兩個角色都有一個arraylength參數,它指定傳入(或傳出)數組的長度。arraytosequence 也有一個enforcearraylength參數,如果其設定為真,将導緻在接收到一個錯誤長度的數組時角色将産生一個錯誤資訊。在sequencetoarray中,arraylength是端口參數(portparameter,)是以讀取的輸入令牌數量可以不同。僅當數組長度為常數時,這些角色是sdf角色。

chop,在flowcontrol→sequencecontrol中,讀取指定數量的輸入令牌并産生這些輸入的特定子集,可以用零值令牌或者以前消耗的令牌填充。

補充閱讀:信号處理角色

除了前文描述的頻譜分析角色,ptolemy ii還包含了其他幾個信号處理角色,如下所示。

iir 實作無限脈沖響應濾波器,也稱為遞歸濾波器(見lee and varaiya(2011))。濾波器系數由兩個數組提供,一個提供傳輸函數的分子多項式,一個提供傳輸函數的分母多項式。

fir實作有限脈沖響應濾波器,也稱為抽頭延遲線濾波器,它的系數由taps參數來指定。而iir是同構sdf(單速率)角色,fir是内在的多速率角色。當decimation(interpolation)參數不等于1時,濾波器的行為就好像在使用downsample(upsample)角色之後(之前)。然而,該實作比使用upsample或downsample角色實作會更高效,内部使用了多相結構,避免了不必要的記憶體使用和乘零操作。用這種方法通過合理的因素可以完成對任意樣本速率的轉換。

delayline産生一個數組而不是像fir那樣産生一個标量。delayline 不輸出權重平均延遲線的内容(這是fir産生的),而是僅僅簡單地輸出延遲線為一個數組。

variablefir與fir相同,除了系數是由輸入端口(是以可以改變)的數組提供而不是由角色參數來定義外。

lmsadaptive類似于fir,除了在每次點火時使用梯度下降自适應濾波算法來調整系數外,該算法試圖在錯誤的(error)輸入端口将信号的功率最小化。

除了這裡描述的角色外,信号處理(signal processing)庫還包括固定點(?xed)和自适應格型(lattice)濾波器、統計分析角色等、通信系統的角色(如源和通道編碼器與解碼器)音頻采集和回放、圖像和視訊處理角色等。

補充閱讀:動态變化速率

sdf的變體,稱為參數化的sdf(psdf),由bhattacharya and bhattacharyya (2000)提出,它端口的産生速率和消耗速率是由參數給出,而不是常數。參數的值允許改變,但僅僅是在兩次完整的疊代之間改變。當這個參數的值改變時,新的排程必須用于下一次完整的疊代。

圖3-9中的例子說明如何用ptolemy ii中的sdf訓示器實作psdf。首先,注意訓示器的allowratechanges參數已經設定為真。這表明訓示器可能需要計算不止一個排程,是以在執行模型期間(rate)速率參數可能改變。

其次,注意repeat角色的numberoftimes參數設定為與模型參數rate相等,其初始值為零。是以,當模型執行它的第一次疊代時,repeat角色将産生零個令牌,是以display角色不會點火。ramp角色的初始輸出為1,将不會被顯示。

在第一次疊代期間,expression和setvariable角色都隻點火一次。expression 角色設定它的輸出等于輸入,除非它的輸入等于interations(疊代)參數(它沒在這個首次疊代中)的值。 setvariable角色設定rate參數的值為1。在預設情況下,setvariable有一個delayed參數的值為真,這意味着隻有在目前疊代完成之後rate參數才能改變。

在第二次疊代中,rate參數的值是1,是以repeat角色複制一次它的輸入(值為2)給輸出。expression和setvariable 角色把現在的rate參數設定為2,是以在第三次疊代中,repeat角色複制它的輸入(有值為3)兩次給它的輸出。是以顯示的輸出序列為2,3,3,4,4,4...。

為了終止模型,訓示器的iterations參數設定為5。在最後一次執行疊代中,expression角色保證rate參數重置為0。是以,在下一次模型執行時,它将會随着rate參數設定為0重新開始。

在這個例子中,每次rate參數變化,sdf訓示器都會重新計算排程。在psdf更好的實作中,它在計算排程前預計算排程與緩存,但是這個實作做不到預計算與緩存。它僅僅在疊代之間重新計算排程。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

圖3-9 一個有動态變化速率的sdf模型

補充閱讀:streamit

thies et al.(2002)給出一種基于sdf的文本程式語言——streamlt,該語言主要針對使用流資料的應用(如多媒體)。軟體元件(稱為濾波器而不是角色)産生和消耗固定數量資料。該語言為組成角色的常見模式提供緊湊的結構設計,如濾波器鍊、并行濾波器鍊和回報回路等。

streamit中的一個關鍵創新是消息傳遞(teleport message)的概念(thies et al., 2005)。消息傳遞通過允許一個角色偶爾地發送一個消息給另一個角色來提高sdf的表達力。也就是說,不是每一個點火行為都發送消息,而是某些點火行為發送消息。盡管消息傳遞機制采用以下方式:當發送角色每次點火發出消息時,接收角色會産生同樣的點火行為,確定該資訊被接收。但是它避免了為每個點火行為發送消息的開銷。這種方法建立了一個通信通道模型,其中令牌的産生和消耗不是總存在的而是偶爾存在的。但是它保留了sdf模型的确定性,任何有效排程執行的結果都相同。

補充閱讀:其他資料流的變體

sdf的一個缺點是每個角色必須産生和消耗固定數量的資料。生産和消耗的速率不能取決于資料。ddf(3.2節)取消了這一限制,代價是不能再對點火進行靜态排程。此外,正如前面章節中所讨論的,分析所有模型的死鎖和有界緩沖區已經不再可能了(這些問題是不可判定的。但是,研究人員已經開發了大量的資料流變種,它們比sdf更富有表達力,但仍然服從某些靜态分析的形式。

循環靜态資料流(cyclo-static dataflow,csdf)允許産生和消耗的速率呈周期性變化(bilsen et al.,1996)。一個例子是singletokencommutator角色(在flowcontrol→

aggregators中)。這個角色類似于commutator角色,但是它不是在單次點火行為中消耗所有輸入,而是一次點火僅消耗其中一個通道的輸入,并且通過在連續點火行為中的輸入通道旋轉。對于每個輸入通道,消耗速率在0和1之間交替。這個角色在回報系統中很有用,其中第二通道的輸入依賴于第一通道的輸入。

sdf也可以分層地結合有限狀态機(fsm)來建立模态模型,這将在第8章介紹。有限狀态機的每個狀态與子模型相關聯(其中每個模型的細化都可以有不同的産生和消耗速率)。如果有限狀态機的狀态轉換被限制為隻發生在某些時刻,那麼該模型仍然是确定的。這種結合由girault et al.(1999)提出,他稱之為異步資料流(heterochronous dataflow,hdf)。sdf scenarios(geilen and stuijk, 2010)類似于hdf,因為它們也使用一個fsm,但不是模型細化,在sdf scenarios中有限狀态機的每個狀态與一組單一sdf模型的産生和消耗相關聯。bhattacharya and bhattacharyya (2000)提出了參數化的sdf(psdf),其中産生和消耗速率可以依賴輸入資料,同樣的依賴關系可以在參數化的排程中表示。

murthy and lee (2002) 介紹了多元sdf(multidimensional sdf ,mdsdf)。mdsdf中的一個通道傳遞一個令牌的多元數組,而sdf中的一個通道傳遞一個令牌序列。也就是說,令牌的記錄可以增加為多個次元。這個模型對表示确定種類的信号處理應用是很有效的,特别是圖像處理、音頻處理、雷達和聲呐。

補充閱讀:petri網絡

petri網,以carl adam petri的名字命名,是一種流行的與資料流相關的模組化形式(murata,1989)。它們有兩種類型的元素,庫所(place)和變遷(transition),分别用白色圓圈和矩形表示。一個庫所可以包含任意數量的令牌,表示為黑色圓點。如果所有的庫所都連接配接到變遷,則變遷将被使能,它的輸入至少包含了一個令牌。

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

一旦變遷被使能,它可以被點火(fire),從每個輸入的庫所消耗一個令牌,并在每個輸出庫所存放一個令牌。網絡的狀态,稱為标記(marking),是網絡中的每個庫所上令牌的數量。上圖顯示了一個在點火行為之前和之後的簡單網絡的标記。如果一個庫所提供輸入給不止一個變遷,那麼庫所的一個令牌可能觸發其中的一個目标變遷的點火(非确定的一個或其他點火)。

petri網的變遷類似于資料流角色。當有足夠的輸入可用時它們将點火。在基本的petri網中,令牌沒有值,變遷的點火行為并不涉及任何令牌的計算。點火行為僅僅扮演移動令牌從一個庫所到另一個庫所的角色。另外,與資料流緩沖區不同,庫所不會維持令牌順序。與同構sdf一樣,變遷是通過每個輸入庫所上的令牌使能的。與sdf不同,一個庫所可能供給了不止一個變遷,導緻了模型的不确定性。

有很多petri網的變種,至少有一種與sdf等價。特别地,令牌可以擁有值(這些令牌在文獻中被稱為着色令牌(colored token),其中令牌的顔色代表它的值)。變遷可以操控令牌顔色(類似于資料流的點火功能)。連接配接庫所和變遷的弧可以被權重,這意味着點火變遷需要多個令牌,或者一個變遷産生多個令牌。這類似于sdf的産生和消耗速率。最後,petri網圖結構可以被限制,這樣對于每個庫所,都有一個明确的源變遷和一個明确的目的變遷。這種有保序庫所的petri網是sdf圖。

補充閱讀:邏輯角色

這些角色可以在logic庫中找到,它們對建立控制邏輯很有幫助:

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

comparator角色比較兩個double類型的值(或者任何可以無損地轉換成double的類型,如第14章所解釋的那樣)。可用的比較操作是>、>=、<、<=和==。輸出為布爾值。

equals角色比較任意數量的任意類型輸入令牌的相等性,如果它們相等,則輸出一個布爾真值,否則輸出假。

ispresent角色:如果它的輸入在點火時到達,則輸出布爾真值,否則輸出假。在資料流域,輸入總是會到達,是以輸出總是為真。這個角色在sr和de域會更有用(第5章和第7章)。

logicalnot接收一個輸入布爾值并輸出該布爾值的相反值。

logicgate實作以下6個邏輯功能(不同的邏輯功能對應不同的圖示):

《資訊實體融合系統(CPS)設計、模組化與仿真——基于 Ptolemy II 平台》——第3章 資料流 3.1同步資料流

truegate角色:當輸入為布爾真值時,它産生一個布爾真值輸出;否則,它不産生任何令牌。這很明顯不是sdf角色,但它可以與ddf一起使用。它在sr中同樣有用(第5章)。

繼續閱讀