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

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

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

1.1Hash映射的概率分布特性

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

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

隨機服務系統(tǒng)理論也稱排隊論，是通過對服務對象來到和服務時間的統(tǒng)計研究，研究性態(tài)問題、最優(yōu)化問題、排隊系統(tǒng)的統(tǒng)計推斷問題，進而對整個系統(tǒng)進行建模和優(yōu)化的一門科學図。典型的排隊系統(tǒng)如圖1所示。

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

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

2FIFO深度的確定

正是利用這一原理，文獻[6]推導出了計算FIFO深度的公式：

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

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

3結(jié)語

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

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