井下聲波數(shù)據(jù)壓縮系統(tǒng)中FIFO深度的研究

在測(cè)井?dāng)?shù)據(jù)高速增長(zhǎng)的背景下，實(shí)時(shí)硬件無(wú)損壓縮系統(tǒng)得到了廣泛應(yīng)用。不少系統(tǒng)中均使用了Hash查找來(lái)提高壓縮系統(tǒng)的工作效率。但是，由于Hash沖突的無(wú)法避免，Hash查找的查找時(shí)間往往是隨機(jī)的，這就使得下一個(gè)待壓縮數(shù)據(jù)進(jìn)入壓縮系統(tǒng)的時(shí)間也是隨機(jī)的。因此，壓縮系統(tǒng)數(shù)據(jù)輸入前端的工作頻率和壓縮模塊的工作頻率就難以保持同步。為了解決系統(tǒng)模塊間異步時(shí)鐘域同步問(wèn)題，異步FIFO（FirstInFirstOut）得到了廣泛的應(yīng)用。在異步FIFO設(shè)計(jì)中的一個(gè)關(guān)鍵問(wèn)題就是FIFO深度的選取，選取合適的FIFO深度不僅可以提高系統(tǒng)性能,而且還可以?xún)?yōu)化系統(tǒng)的面積和功耗叫目前,針對(duì)FIFO深度問(wèn)題的研究也有很多。比如，在讀寫(xiě)頻率確定的情況下的FIFO深度經(jīng)驗(yàn)公式；讀寫(xiě)頻率成比例時(shí)，通過(guò)等時(shí)長(zhǎng)間隔測(cè)井FIFO中已有數(shù)據(jù)量來(lái)確定FIFO深度；建立FIFO模型，但是在FIFO內(nèi)無(wú)排隊(duì)現(xiàn)象的前提下等。多數(shù)研究并沒(méi)有給出FIFO應(yīng)用的具體環(huán)境，沒(méi)有考慮FIFO深度對(duì)具體某一數(shù)字系統(tǒng)的影響。針對(duì)實(shí)際井下聲波數(shù)據(jù)壓縮系統(tǒng)（數(shù)據(jù)輸入速率即數(shù)據(jù)采樣頻率一定），本文首先研究了Hash桶深的概率分布統(tǒng)計(jì)特征，以此得到FIFO輸出端數(shù)據(jù)的概率分布統(tǒng)計(jì)特性。在此基礎(chǔ)上，利用隨機(jī)服務(wù)系統(tǒng)理論對(duì)異步FIFO建模，從理論上得到了FIFO深度，對(duì)異步FIFO和整個(gè)數(shù)據(jù)實(shí)時(shí)壓縮系統(tǒng)的設(shè)計(jì)具有重要的指導(dǎo)意義。

1Hash映射的概率分布特性及FIFO建模

1.1Hash映射的概率分布特性

在基于字典的無(wú)損壓縮算法（如LZW算法）中，經(jīng)常會(huì)使用Hash函數(shù)來(lái)提高數(shù)據(jù)查找效率，從而提高壓縮系統(tǒng)的壓縮速率。Hash函數(shù)本質(zhì)上是在數(shù)據(jù)和它的存儲(chǔ)地址之間建立一個(gè)確定的映射，因而在查找時(shí)只需要根據(jù)這個(gè)映射關(guān)系便可以找到此數(shù)據(jù)的存儲(chǔ)位置。然而，對(duì)不同的數(shù)據(jù)經(jīng)過(guò)哈希映射后卻可能得到同一個(gè)哈希地址即存儲(chǔ)地址，這種現(xiàn)象稱(chēng)為哈希沖突。在一般情況下，沖突只能盡可能地減少，而不能完全避免。不少測(cè)井?dāng)?shù)據(jù)壓縮系統(tǒng)均采用散列性能好，且利于硬件實(shí)現(xiàn)的移位異或Hash函數(shù)叫可以證明[8]:當(dāng)Hash映射散列性能好，近似服從均勻分布的情況下，每個(gè)Hash桶中的數(shù)據(jù)量服從Poisson分布，即每個(gè)數(shù)據(jù)到達(dá)某個(gè)Hash桶的時(shí)間間隔服從指數(shù)分布。

1.2壓縮系統(tǒng)等效和FIFO建模

隨機(jī)服務(wù)系統(tǒng)理論也稱(chēng)排隊(duì)論，是通過(guò)對(duì)服務(wù)對(duì)象來(lái)到和服務(wù)時(shí)間的統(tǒng)計(jì)研究，研究性態(tài)問(wèn)題、最優(yōu)化問(wèn)題、排隊(duì)系統(tǒng)的統(tǒng)計(jì)推斷問(wèn)題，進(jìn)而對(duì)整個(gè)系統(tǒng)進(jìn)行建模和優(yōu)化的一門(mén)科學(xué)図。典型的排隊(duì)系統(tǒng)如圖1所示。

按照此排隊(duì)系統(tǒng)典型結(jié)構(gòu)，可以把數(shù)據(jù)壓縮系統(tǒng)的輸入前端即異步FIFO等效為圖1中的“顧客排隊(duì)”，把數(shù)據(jù)壓縮模塊等效為圖1中的“服務(wù)機(jī)構(gòu)”，就可以建立FIFO的隨機(jī)服務(wù)系統(tǒng)模型。

由于壓縮系統(tǒng)的壓縮速率的不確定主要是由Hash沖突引起的，且數(shù)據(jù)到達(dá)某個(gè)Hash桶的時(shí)間間隔是服從指數(shù)分布的，因此整個(gè)壓縮模塊完成數(shù)據(jù)的壓縮時(shí)間間隔也近似服從指數(shù)分布，也就是異步FIFO的讀時(shí)鐘周期服從指數(shù)分布。所以,異步FIFO可以用M/M/1/m的排隊(duì)混合制系統(tǒng)進(jìn)行建模(M表示指數(shù)分布，m表示異步FIFO容量)。在X/Y/Z/A排隊(duì)系統(tǒng)中，X為顧客到達(dá)時(shí)間間隔概率分布，Y為服務(wù)時(shí)間概率分布，Z為服務(wù)臺(tái)數(shù)量，A為服務(wù)臺(tái)容量。

2FIFO深度的確定

正是利用這一原理，文獻(xiàn)[6]推導(dǎo)出了計(jì)算FIFO深度的公式：

式中，t=n，表示單位時(shí)間內(nèi)數(shù)據(jù)能夠到達(dá)FIFO的概率。由于本文所設(shè)計(jì)的壓縮系統(tǒng)是實(shí)時(shí)壓縮系統(tǒng)，因此式(1)所求的FIFO深度應(yīng)該是當(dāng)q趨近于1時(shí)的深度，"是根據(jù)常見(jiàn)的壓縮系統(tǒng)的壓縮速率所取的值。顯然，當(dāng)P>1時(shí)，F(xiàn)IFO內(nèi)是不存在排隊(duì)問(wèn)題的。圖2所示是在Matlab中計(jì)算出的FIFO的深度情況。

由圖2可知，當(dāng)數(shù)據(jù)源不暫停向壓縮系統(tǒng)發(fā)送數(shù)據(jù)時(shí)，由于哈希沖突問(wèn)題將會(huì)造成FIFO中可能產(chǎn)生排隊(duì)現(xiàn)象。根據(jù)圖2，異步FIFO的容量應(yīng)設(shè)置為4×8b。盡管這樣的逼近一定會(huì)存在不少誤差，但這樣大致給出了FIFO深度的范圍，最大的好處是改變了以往靠設(shè)計(jì)者經(jīng)驗(yàn)設(shè)置FIFO深度的問(wèn)題，而且能有效節(jié)省存儲(chǔ)器的硬件資源，為后面的硬件系統(tǒng)設(shè)計(jì)建立一個(gè)理論基礎(chǔ)，從而提供理論指導(dǎo)。

3結(jié)語(yǔ)

本文利用排隊(duì)論模型對(duì)FIFO深度進(jìn)行建模，并且把FIFO深度和實(shí)際的數(shù)字系統(tǒng)聯(lián)系起來(lái)分析，這在以往是少見(jiàn)的。FIFO深度的確定可以有效避免依靠設(shè)計(jì)者經(jīng)驗(yàn)確定FIFO深度時(shí)帶來(lái)的資源浪費(fèi)或者容量不夠問(wèn)題，為硬件數(shù)據(jù)壓縮系統(tǒng)提供了理論指導(dǎo)，并且有很好的應(yīng)用前景。

20211020_617022c63c136__井下聲波數(shù)據(jù)壓縮系統(tǒng)中FIF