浮動陣列的最大abs-max

我需要實時繪製音頻峯值表。每秒最少44100個採樣次，最少40個流。每個緩衝區介於64到1024個樣本之間。我需要從每個緩衝區中獲取最大值。（然後通過一種低通濾波器饋送，並以大約20ms的間隔進行繪製）。浮動陣列的最大abs-max

for(int i = 0; i < numSamples; i++) 
{ 
     absMaxOfBuffer = MAX(fabs(buffer[i]), absMaxOfBuffer); 
}

這就是我現在要做的。我想更快地做到這一點。緩衝區浮點數在-1到1範圍內，因此晶圓廠。

問題，是否有一些棘手的comp-sci quicksort-esque這樣做的方式更快？

失敗，浮點數的無分支ABS和MAX函數，它們是否存在？主要平臺是Linux/gcc，但Windows端口計劃（可能與mingw）。

編輯，第二個：
由於關於問題的中心問題的實際算法結構，我給了一個接受。
我會嘗試展開循環到四個時間，零符號位，然後得到最大與SSE（maxps指令），看看是否不剝離香蕉。感謝這些建議，我已經投票選出了幾名亞軍。 :)

來源

2009-05-03 Eric_DE

什麼編譯器？什麼平臺？如果你使用gcc，你可能會對諸如__builtin_expect之類的東西感興趣。 – 2009-05-03 19:04:33

工廠和比較對於IEEE浮點數都是非常快的（例如，原則上單整數運算速度快）。

如果編譯器沒有內聯這兩個操作，那麼要麼戳到它，要麼爲您的架構找到實現並自行內聯。

你也許可以得到一些事實，正數 IEEE浮點數與具有相同位模式的整數順序相同。也就是說，

f > g iff *(int*)&f > *(int*)&g

所以一旦你fabs'ed，我認爲一個自由分支最大爲INT還將爲浮動工作（假設他們是當然的大小相同）。有一個解釋爲什麼這在這裏工作：http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm。但是你的編譯器已經知道了所有這些，你的CPU也是如此，所以它可能沒有任何區別。

沒有複雜性 - 更快的方式。你的算法已經是O（n）了，你不能打敗它，仍然看每個樣本。

我想有可能是一些在你的處理器的SIMD（即，SSE2英特爾），這將幫助，比你的代碼處理每個時鐘週期更多的數據。但我不知道是什麼。如果有，那麼它很可能會快幾倍。

你也許可以並行多核CPU上，特別是因爲你所面對的40分獨立的流反正。這將是最快的幾個因素。「只需」啓動適當數量的額外線程，在它們之間分配工作，並使用可以指示何時全部完成（可能是線程障礙）的最輕量級基元。我不太清楚你是在繪製所有40個流的最大值還是每個流的最大值，所以也許你實際上不需要同步工作線程，除了確保結果被傳送到下一個階段沒有數據損壞。

這可能是值得考慮看看拆解，看看有多少的編譯器展開循環。嘗試展開它多一點，看看是否有任何區別。

另一個要思考的是多少緩存未命中你得到，以及是否有可能通過給高速緩存中的一些線索的人數減少，因此可以提前加載右頁。但我沒有這方面的經驗，我也不抱太多希望。 __builtin_prefetch是gcc的神奇咒語，我想第一個實驗就像「在進入該塊的循環之前預取下一個塊的開始」。

多少百分比所需的速度是你目前？或者這是「儘可能快」的情況？

來源

2009-05-03 18:30:59

「太多了」。只要這個函數已經在多個線程中使用。否則，如果一個線程正在完成所有工作，那麼無論現有線程的原始數量如何，您都無法充分利用CPU。你可以有1000個線程，他們都圍坐在等待這個線程，那麼你沒有足夠的線程;-) – 2009-05-03 18:54:56

正確的，我不知道一個更好的算法，假設你必須看看每一個樣品。你也許可以嘗試只採取每個緩衝區前半部分的最大值，看看你錯了多少次，多少次，然後決定你是否在意。當然，如果wave被削減，你知道它不會變得更大，並且可以忽略該緩衝區的其餘部分。但要檢測到您需要在循環中進行額外的比較，這會在未剪切的情況下降低速度。而且我假設浮動音頻數據並不一定是什麼數量級構成「剪輯」。 – 2009-05-03 19:18:53

回答與另一個問題的問題不完全回答，但嘿...我也不是C++開發人員。因爲你在C++中開發這個，你正在做DSP，你不能連接到matlab，或八度（這是開源）到你的數學，只是得到結果嗎？

在這些軟件中已經實現了函數（如conv，fft，ifft，fir和plotting util函數，如freqz，stem，graph，plot，mesh等）。我看了一下Photoshop，並且有一個叫做MATLAB的大文件夾...，其中有一些.m文件可以從應用程序中獲取調用信息，然後將它發送給動態matlab，然後將結果返回給應用程序。

希望它有幫助。

來源

2009-05-03 18:30:31

事情嘗試：

晶圓廠（）可能不是一個內聯函數。
特殊裝配說明可能會有所幫助。在Intel上，SSE有一條指令，一次計算最多四個浮點數。
做不到這一點，IEEE 754規範是這樣的，如果a和b是非負浮筒，然後一個< b爲相當於*（INT *）&一個< *爲（int *）&灣此外，對於任何一個，你可以通過翻轉MSB來計算-a。總之，這些屬性可能會導致一些混亂的黑客攻擊。
你是否真的需要每個樣本的最大值？也許最多可能發生超過一次，從而開放不檢查每個輸入的可能性。
你能以流媒體的方式計算最大值嗎？

來源

2009-05-03 18:34:13 Dave

「fabs（）可能不是內聯函數」。這是令人沮喪的... – 2009-05-03 18:49:56

有記錄的http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

也請注意，最近的GCC的版本將內聯網點fabs爲您網點晶圓廠，採用MMX指令。還有fmin和fmax，但GCC將不會內聯的（你會得到一個call fmin）。

來源

2009-05-03 18:35:43 pts

輕鬆優化我看到：

翻譯循環到指針運算版本（假設你的編譯器不看到這一點）
IEEE 754標準的代表性定義爲符號 - 幅度。因此，將最重要的位設置爲0將與調用fabs（）相同。也許這個功能已經使用這個技巧。

來源

2009-05-03 18:47:16 GogaRieger

你可能想看看Eigen。

它是一個C++模板庫，它使用SSE（2及更高版本）和AltiVec指令集，優雅地回退到非矢量化代碼。

快。（見基準）。
表達式模板允許智能地刪除臨時對象並啓用延遲評估（如果適當的話） - Eigen會自動處理並在大多數情況下也處理別名。
針對SSE（2及更高版本）和AltiVec指令集執行顯式矢量化，並優雅地回退到非矢量化代碼。表達式模板允許爲整個表達式全局執行這些優化。
對於固定大小的對象，可以避免動態內存分配，並且在有意義時展開循環。
對於大型矩陣，應特別注意緩存友好性。

來源

2009-05-04 03:54:23 lothar

爲了您的目的，您可以將其平方而不是取絕對值;如數學| a | < | b |如果a^2 < b^2，反之亦然。在某些機器上，乘法可能比fabs（）更快（？），我不知道。

來源

2009-05-04 06:29:27 newacct

浮動陣列的最大abs-max

回答

相關問題