嵌入式系統數學運算最佳化技巧

在資源受限的嵌入式系統中，數學運算，尤其是浮點數運算，常常成為效能瓶頸。開發者經常採用查表法搭配線性插值來提升運算速度和精確度。對於浮點數運算，則可以考慮使用虛擬浮點數，也就是透過整數搭配位移運算來模擬浮點數，以避免複雜的浮點數運算單元和潛在的溢位問題。這種技巧在需要快速數值計算的場景，例如感測器校正或訊號處理等，特別有效。除了查表法和虛擬浮點數，也有其他最佳化技巧，例如使用二進位制縮放來表示小數，以及針對特定硬體平臺的數學函式庫進行最佳化等。

第12章：數學

在嵌入式系統中，數學運算往往是效能瓶頸。為了節省處理週期，開發人員經常使用查表法（lookup table）來實作數學函式。查表法是預先計算好某個函式的輸出值，並將其儲存在一張表中，以便快速查詢。

明確輸入查表法

明確輸入查表法（explicit input lookup table）是一種查表法，其輸入值是明確定義的。這種方法通常用於需要根據環境條件（如溫度）進行校準的感測器中。輸入值是溫度感測器的讀取值，輸出值是偏差值。

struct sPoint sinLookup[] = {
    { -3145, 3 },
    { -2121, -853 },
    { -1865, -958 },
    { -1609, -1000 },
    { -1353, -977 },
    { -1097, -890 },
    { 951, 813 },
    { 1207, 934 },
    { 1463, 994 },
    { 1719, 989 },
    { 1975, 919 },
    { 2999, 142 }
};

然而，明確輸入查表法需要搜尋表格以找到正確的輸入範圍。這可以透過以下函式實作：

int SearchLookupTable(int32_t target, struct sPoint const *table, int tableSize) {
    int i;
    int bestIndex = 0;
    for (i = 0; i < tableSize; i++) {
        if (target > table[i].x) {
            bestIndex = i;
        } else {
            return bestIndex;
        }
    }
    return bestIndex;
}

線性插值

線性插值（linear interpolation）是一種用於估計兩個已知點之間的未知點的方法。它可以用於查表法中，以提高精確度。

index = SearchLookupTable(x, sinLookup, sizeof(sinLookup));
if (index + 1 < sizeof(sinLookup)) {
    y = interpolate(x, sinLookup[index], sinLookup[index + 1]);
} else {
    y = interpolate(x, sinLookup[index - 1], sinLookup[index]);
}

模擬浮點數

浮點數運算在嵌入式系統中可能很昂貴。為了避免使用浮點數，開發人員可以使用模擬浮點數（fake floating-point numbers）的方法。這種方法使用有理數（rational numbers）來近似浮點數。

struct sFakeFloat {
    int32_t numerator;
    int8_t exponent;
};

有理數可以寫成分數的形式，即分子與分母的比率。透過使用二進位制縮放（binary scaling），我們可以避免除法運算，並實作模擬浮點數。

虛擬浮點數的實作

虛擬浮點數是一種使用結構體來表示浮點數的方法。這種方法可以用來表示大於或小於通常整數變數能夠表示的範圍的數值。

結構體定義

虛擬浮點數可以使用以下結構體來表示：

struct sFakeFloat {
    int32_t num; // 分子
    int8_t shift; // 右移位元（負數表示左移）
};

這個結構體中，num 代表分子，shift 代表右移位元。

虛擬浮點數的運算

虛擬浮點數可以使用以下公式來計算浮點數值：

floatingPointValue = num / 2 ^ shift;

或者使用位元運算來計算：

floatingPointValue = num >> shift;

例子

以下是一些例子：

• 1/4 可以表示為 {1, 2}，因為 1 / 2 ^ 2 = 1/4。
• 4 可以表示為 {1, -2}，因為 1 / 2 ^ -2 = 1 * 2 ^ 2 = 4。
• 十億零一 (10,000,000,001) 可以表示為 {1250000000, -3}，但這樣會失去最後一位數字，得到十億。

精確度

虛擬浮點數的精確度取決於分子的位元數和右移位元的位元數。使用 24 位元的分子和 8 位元的右移位元，可以保持在 32 位元的變數中，但可能會降低精確度。

例如，數字 12.345 可以表示為 49/4，誤差為 0.095。使用更大的右移位元可以得到更高的精確度，但如果分子太大，可能會導致溢位。

以下是使用二進位制縮放表示 12.345 的一些選項：

這些選項表明，虛擬浮點數可以用來表示大於或小於通常整數變數能夠表示的範圍的數值，但精確度取決於分子的位元數和右移位元的位元數。

瞭解假浮點數及其運算

在數字系統中，浮點數是一種常見的資料型別，用於表示小數。但是，在某些情況下，浮點數可能不夠精確或不適合特定的應用。這時，假浮點數（Fake Floating-Point Numbers）就派上用場了。

假浮點數的概念

假浮點數是一種模擬浮點數的方法，透過使用整數和移位運算來近似浮點數的運算。這種方法可以用於特定的應用中，例如音訊處理或影像處理。

加法和減法運算

假浮點數的加法和減法運算需要將兩個數字的分母（即移位值）調整為相同。這可以透過左移或右移運算來實作。

以下是一個例子，使用 byte 來表示假浮點數的分子：

struct sFakeFloat {
    int8_t num;
    int8_t shift;
};

假設我們有兩個假浮點數 a 和 b，分別表示為 12.375 和 3.46875。我們可以透過以下步驟進行加法運算：

1. 找到兩個數字的最小公分母（Least Common Denominator, LCD）。
2. 將兩個數字的分子左移或右移，使其分母相同。
3. 將兩個數字的分子相加。
4. 如果結果太大，則需要右移以避免溢位。

以下是示例程式碼：

struct sFakeFloat a = { 99, 3 }; // 12.375
struct sFakeFloat b = {111, 5 }; // 3.46875
struct sFakeFloat result;

int16_t tmp = a.num;
tmp = tmp << (b.shift - a.shift);
tmp = tmp + b.num;

// 如果結果太大，則需要右移
if (tmp > 255) {
    tmp = tmp >> 1;
    result.shift = b.shift + 1;
} else {
    result.shift = b.shift;
}

result.num = tmp;

內容解密：

在上述示例中，我們使用 byte 來表示假浮點數的分子，這可以用於不需要太大範圍的應用中。假浮點數的加法和減法運算需要將兩個數字的分母調整為相同，這可以透過左移或右移運算來實作。結果需要注意溢位問題，如果結果太大，則需要右移以避免溢位。

圖表翻譯：

  flowchart TD
    A[開始] --> B[找到最小公分母]
    B --> C[左移或右移分子]
    C --> D[相加分子]
    D --> E[檢查溢位]
    E -->|是| F[右移結果]
    E -->|否| G[結束]

在這個流程圖中，我們可以看到假浮點數的加法運算的步驟，包括找到最小公分母、左移或右移分子、相加分子、檢查溢位和右移結果。

數學運算與機器學習

在嵌入式系統中，數學運算和機器學習是兩個重要的議題。數學運算涉及到浮點數的運算，包括加法、乘法和除法等。在浮點數的運算中，需要考慮到溢位和精確度的問題。

浮點數運算

浮點數運算可以使用假浮點數（fake floating-point）來實作。假浮點數使用一個整數來表示數字的值，另一個整數來表示數字的位移。這樣可以避免使用浮點數運算的複雜性和溢位的問題。

加法

假浮點數的加法需要先將兩個數字的位移對齊，然後進行加法運算。如果結果超過了最大值，需要進行位移調整。

乘法

假浮點數的乘法需要先將兩個數字的值相乘，然後將結果的位移進行調整。如果結果超過了最大值，需要進行位移調整。

機器學習

機器學習是一個巨大的領域，涉及到各種統計方法和演算法。機器學習可以用於各種應用，包括分類別、檢測和控制系統等。在嵌入式系統中，機器學習通常用於推論階段，即將新資料輸入到已經訓練好的模型中，以得到預測結果。

訓練和推論

機器學習的訓練階段通常在更強大的電腦上進行，而推論階段則在嵌入式系統中進行。訓練階段需要大量的計算資源，而推論階段則需要盡可能少的計算資源。

最佳化和限制

在嵌入式系統中，最佳化和限制是兩個重要的議題。最佳化需要盡可能地減少計算資源的使用，而限制需要考慮到系統的硬體和軟體限制。

最佳化技術

最佳化技術包括減少計算量、使用更快的演算法和減少記憶體使用等。在嵌入式系統中，最佳化技術可以用於提高系統的效率和可靠性。

限制

限制包括系統的硬體限制、軟體限制和安全性限制等。在嵌入式系統中，限制需要考慮到系統的可靠性和安全性。

從效能最佳化視角來看，本章深入探討了嵌入式系統中數學運算的效能瓶頸及最佳化策略。查表法，特別是結合線性插值的應用，有效降低了複雜函式的計算開銷，但需要權衡儲存空間的消耗。而模擬浮點數和虛擬浮點數的技巧，則在不使用浮點數運算單元的情況下，巧妙地平衡了計算精確度和效能需求，展現了開發者在資源受限環境下的創造力。然而，這些方法也存在精確度損失的限制，需根據實際應用場景謹慎選擇。展望未來，隨著嵌入式系統硬體效能的提升和演算法的最佳化，更高效的數學運算函式庫和專用硬體加速器將成為主流，進一步提升嵌入式系統的運算能力。對於嵌入式系統開發者而言，深入理解這些數學最佳化策略，並根據專案需求靈活運用，將是提升系統效能的關鍵所在。