AI Model Sparsity Pruning Compression

Posted on | In

AI 模型稀疏性及相關技術

機器學習模型中的稀疏性涉及減少非零參數的數量，從而導致（1）更高效的內存占用和帶寬，以及（2）更快的計算。稀疏性是優化大型神經網絡的一項關鍵技術，它是通過幾個步驟實現的：

1. 修剪

  • 目的： 修剪通過移除神經網絡中不必要的權重，減少其大小和複雜性，同時旨在保持準確性。
  • 類型：
    • 非結構化修剪： 此方法根據某些標準（例如基於幅度的修剪）移除個別權重，沒有任何特定模式。這對於減少模型大小是有效的，但在硬件上優化可能會面臨挑戰。
    • 結構化修剪： 此方法移除整個結構，如神經元或通道，通常導致參數區塊被置零。結構化修剪在硬件上實施更容易，並且與壓縮技術相得益彰。

      結構化稀疏性

  • 定義： 結構化稀疏性涉及在模型參數中創建零的模式，例如強制某一百分比的權重在過濾器或神經元內為零。
  • 2:4 稀疏模式： 一個常見例子是每四個權重組中，有兩個保證為零，但可以隨機位置。這種模式平衡了壓縮與計算效率。
  • 用例： 結構化稀疏性在硬件實現中受到青睞，因為它允許可預測的模式，更容易進行優化。

2. 壓縮

  • 目的： 壓縮通過有效編碼稀疏模型來減少內存占用和帶寬需求。
  • 方法：
    • 稀疏矩陣格式： 只存儲非零元素及其索引，使用如壓縮稀疏行（CSR）或壓縮稀疏列（CSC）等格式。
    • 熵編碼： 像霍夫曼編碼這樣的技術通過為更頻繁的值分配較短代碼來壓縮稀疏數據，進一步減小大小。

問題: 為什麼不直接移除零組件？

3. 解壓縮

  • 目的： 在計算之前，需要對壓縮後的稀疏數據進行解壓。解壓從其壓縮形式重建原始的稀疏矩陣或張量。
  • 實施方式： 解壓通常由硬件或軟件堆棧處理，使模型能夠高效地加載到內存中以進行推理。

4. 零跳過技術

  • 目的： 零跳過通過繞過涉及零值的操作來提高計算效率，有效地為某些操作翻倍計算能力。
  • 實施方式： 專門設計的硬件，如某些GPU，被設計用來檢測並跳過對零值的計算。當與結構化稀疏性相結合時，這種技術最有效，其中零模式是可預測的。

通過遵循此順序——首先通過修剪獲得稀疏性，然後對數據進行壓縮和解壓，最後使用零跳過技術——模型可以在內存效率和計算性能上獲得顯著改善。

NVIDIA 稀疏 TOPS - 專注於 2 倍 TOPS，但不強調記憶體佔用和帶寬

NVIDIA 一直利用稀疏性提升其 GPU 的性能和效率，特別是在其 Ampere 架構中。NVIDIA 宣稱其 sparse TOPS 比 dense TOPS 提高了兩倍 (因為使用 2:4 structured pattern + zero-skipping)。

NVIDIA 的方法主要圍繞 結構化稀疏性，即修剪模型權重，使得剩餘的非零權重形成一種規則模式，這樣硬件可以有效利用。具體而言，他們使用 2:4 稀疏模式，意味著在每四個連續的權重中，至少有兩個為零。這種模式的選擇是因為它允許他們的硬件加速矩陣乘法運算，而這是深度學習計算的一個核心部分。

以下是 NVIDIA 如何利用這一點：

  1. 張量核心：NVIDIA 的張量核心是專門用於加速混合精度矩陣乘法的單元，已經針對稀疏矩陣進行了優化。當使用 2:4 稀疏模式時，張量核心可以 跳過涉及零權重的操作，有效地將某些矩陣運算的吞吐量翻倍。

  2. 軟件支持：NVIDIA 提供了一些軟件工具在其庫中，如 cuSPARSELt 和 CUDA，幫助開發人員實現並利用稀疏性。這些工具可以自動修剪模型以實現所需的稀疏性，然後使用優化後的稀疏矩陣進行推理。

  3. 性能提升：通過使用稀疏性，NVIDIA 的 GPU 可以在每瓦特性能上取得更高的增益，這對於數據中心應用和邊緣設備至關重要。2:4 稀疏模式使他們能夠在某些工作負載下幾乎將計算效率翻倍，而不會顯著損失模型準確性。

NVIDIA 的策略特別適用於推理，在此情況下計算需求可能非常高，而效率在稍微犧牲準確性的情況下至關重要。

為什麼選擇零跳過而不是直接從模型中移除零？

1. 硬件兼容性和規律性：

  • 結構化操作： 特別是那些為深度學習優化的GPU（如NVIDIA），被設計用來對大型、密集的矩陣進行高度並行化的操作。如果完全移除矩陣中的零，將會破壞數據的規則結構，使得GPU難以高效地並行化操作。
  • 內存訪問模式： GPU被優化為以結構化方式訪問內存。移除零將導致不規則的內存訪問模式，這可能會降低內存子系統的效率，抵消稀疏性的好處。

2. 實施簡單性：

  • 零跳過： 通過保留零並在計算過程中跳過它們，GPU仍然可以以規則、可預測的模式處理數據。這種方法允許GPU避免不必要的計算，而無需重新設計整個計算過程。
  • 軟件-硬件集成： 現有的軟件和硬件堆棧已經針對密集矩陣操作進行了大量優化。引入處理完全稀疏矩陣的機制將需要對架構和軟件進行重大更改，增加複雜性，並可能降低一般工作負載下的整體性能。

3. 維持可預測延遲：

  • 可預測執行： 當跳過零但不移除時，操作的延遲可以更具可預測性，因為GPU的管道仍在以一致的模式處理數據。如果移除了零，每次操作所需時間可能會根據存在多少個零而有所不同，這會導致性能的不確定性，而這在高性能計算中是不可取的。

是否可以直接從模型中移除零？

1. 雖然可以，但很棘手：

2:4 稀疏模式的挑戰在於每組四個元素中兩個非零元素的位置並不是固定的——它們可以出現在該組中的任何位置。這種隨機性帶來了一些複雜性：

隨機位置如何使零計算的移除變得複雜

  1. 不規則的計算模式：

    • 如果兩個非零元素可以在組內的任何位置，那麼 GPU 必須動態處理各種可能的配置。這使得設計能夠完全消除零計算的硬件變得困難，因為模式事先無法預測。

  2. 動態分支和控制邏輯：

    • 若要完全移除零計算，硬件需要實施動態分支或控制邏輯，以根據它們的位置跳過零，這可能引入效率低下，例如分支懲罰或管理此控制流程的額外開銷。

  3. 對並行性的影響：

    • GPU 依賴高度並行操作。如果非零元素的位置是固定的，則硬件可以針對該特定模式進行優化，使所有處理單元協同工作。然而，隨著隨機位置的一出現，如果某些處理單元被分配到必須動態跳過的零上，它們可能會被低效利用。

2. 取捨：

  • 開銷和複雜性: 完全移除零會引入管理稀疏數據結構的開銷，這可能抵消稀疏性的好處，尤其是在通用 GPU 計算中。開銷包括存儲索引、處理不規則內存訪問以及可能需要重建計算管道的大部分內容。

  • 靈活性降低: 設計用於處理完全稀疏數據結構的硬件在面對密集數據時可能表現不佳，使其在不同類型工作負載中不那麼多功能。

結構零稀疏性問題

2:4 稀疏模式確實涉及一些額外的開銷，超過基本的壓縮比。以下是更詳細的分析：

2:4 稀疏模式中的開銷

  • 索引存儲： 雖然 2:4 模式本質上有 50% 的元素為零，但管理這個模式涉及存儲額外的元數據，例如索引或掩碼，以指示非零元素的位置。這些元數據增加了一些開銷，減少了有效壓縮比，相較於簡單的 50% 減少。

  • 數據表示： 開銷不僅包括存儲索引或掩碼，還包括將數據結構對齊以符合該模式。這可能影響內存的使用效率以及數據處理的方式。

  • 實際壓縮比： 因為這些開銷，實際的壓縮比低於理論上的 50%。具體比例取決於如何有效地管理和存儲索引和模式。

與其他模式的比較

  • 更高壓縮模式： 對於更激進的壓縮，如 3:4 稀疏或專門的稀疏矩陣格式，可以實現更高的壓縮比，但可能需要更複雜的處理，如果管理不當，可能會影響性能。

  • 權衡取捨： 2:4 模式是在實現良好的計算性能與維持可管理開銷之間的一個折衷。它允許 GPU 高效地跳過零，同時保持系統複雜度在可控範圍內。

因此，雖然 2:4 模式通過利用稀疏性提供了性能改善，但實際上，由於需要處理稀疏表示和管理開銷，其壓縮效益在某種程度上有所降低。

Dense TOPS但專注於壓縮以減少內存帶寬和占用

  1. 稀疏修剪，但使用更高的壓縮模式或半結構模式。即使不修剪到零，也可以使用一些質心。
  2. 使用先進的壓縮技術來減少內存占用和帶寬。
  3. 在計算過程中即時解壓。
  4. 可能實施或不實施零跳過技術以提高TOPS，如果內存帶寬是主要考量。
  Nvidia GPU 其他方法
修剪 軟件  
零模式 2:4 結構零 結構化或半結構化
壓縮 壓縮比低於50% 更好的壓縮比
解壓 在GPU內部  
零跳過 是，二倍TOPS 可能或不可能
目的 二倍TOPS，計算，50-70%的內存占用和帶寬減少  

Sparsity in machine learning models involves reducing the number of non-zero parameters, leading to (1) more efficient memory footprint and bandwidth and (2) faster computations. Sparsity is a key technique used in optimizing large neural networks, and it is implemented through several steps:

1. Pruning

  • Purpose: Pruning removes unnecessary weights in a neural network, reducing its size and complexity while aiming to maintain accuracy.
  • Types:
    • Unstructured Pruning: This method removes individual weights based on certain criteria (e.g., magnitude-based pruning) without any specific pattern. It’s effective for reducing model size but can be challenging to optimize in hardware.
    • Structured Pruning: This method removes entire structures, like neurons or channels, often resulting in zeroed-out blocks of parameters. Structured pruning is easier to implement in hardware and aligns well with compression techniques.

      Structured Sparsity

  • Definition: Structured sparsity involves creating patterns of zeros in the model parameters, such as enforcing that a certain percentage of weights within a filter or neuron is zero.
  • 2:4 Sparsity Pattern: A common example where in every group of four weights, two are guaranteed to be zero but can be at random location. This pattern balances compression with computational efficiency.
  • Use Cases: Structured sparsity is favored in hardware implementations because it allows for predictable patterns that are easier to optimize.

2. Compression

  • Purpose: Compression reduces the memory footprint and bandwidth requirements by efficiently encoding the sparse model.
  • Methods:
    • Sparse Matrix Formats: Only non-zero elements are stored, along with their indices, using formats like Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC).
    • Entropy Encoding: Techniques like Huffman coding compress sparse data by assigning shorter codes to more frequent values, further reducing the size.

Question: why not remove the zero component directly?

3. Decompression

  • Purpose: Before computation, the compressed sparse data needs to be decompressed. Decompression reconstructs the original sparse matrix or tensor from its compressed form.
  • Implementation: Decompression is usually handled by the hardware or software stack, enabling the model to be loaded into memory efficiently for inference.

4. Zero-Skip Technique

  • Purpose: Zero-skipping enhances computational efficiency by bypassing operations involving zero values, effectively doubling the computational capability for certain operations.
  • Implementation: Specialized hardware, like certain GPUs, is designed to detect and skip computations on zero values. This technique is most effective when combined with structured sparsity, where zero patterns are predictable.

By following this sequence—starting with sparsity through pruning, then compressing and decompressing data, and finally using zero-skipping techniques—models can achieve significant improvements in both memory efficiency and computational performance.

Nvidia Sparse TOPS - Focus on 2X TOPS, but not Memory Footprint and BW

NVIDIA has been leveraging sparsity to enhance the performance and efficiency of their GPUs, particularly in their Ampere architecture. Nvidia claim the sparse TOPS is 2X better than the dense TOPS because of using 2:4 structured pattern plus zero-skipping.

NVIDIA’s approach primarily revolves around structured sparsity, where they prune model weights in a way that ensures the remaining non-zero weights form a regular pattern, which the hardware can efficiently exploit. Specifically, they use a 2:4 sparsity pattern, meaning that out of every four consecutive weights, at least two are zeros. This pattern is chosen because it allows their hardware to accelerate matrix multiplication operations, a core part of deep learning computations.

Here’s how NVIDIA takes advantage of this:

  1. Tensor Cores: NVIDIA’s Tensor Cores, which are specialized units for accelerating mixed-precision matrix multiplications, have been optimized to handle sparse matrices. When the 2:4 sparsity pattern is used, the Tensor Cores can skip operations involving the zero weights, effectively doubling the throughput for certain matrix operations.

  2. Software Support: NVIDIA provides software tools in their libraries, such as cuSPARSELt and CUDA, that help developers implement and take advantage of sparsity. These tools can automatically prune models to achieve the desired sparsity and then run inference using the optimized sparse matrices.

  3. Performance Gains: By using sparsity, NVIDIA GPUs can achieve higher performance per watt, which is crucial for both data center applications and edge devices. The 2:4 sparsity pattern allows them to nearly double the computational efficiency for certain workloads without a significant loss in model accuracy.

NVIDIA’s strategy is particularly useful for inference, where the computational demands can be extremely high, and efficiency is crucial at a slightly price of accuracy.

Why Zero Skipping Instead of Removing Zeros Directly From Model?

1. Hardware Compatibility and Regularity:

  • Structured Operations: GPUs, especially those optimized for deep learning like NVIDIA’s, are designed to perform highly parallelized operations on large, dense matrices. If zeros were entirely removed from the matrix, it would disrupt the regular structure of the data, making it difficult for the GPU to efficiently parallelize operations.
  • Memory Access Patterns: GPUs are optimized for accessing memory in a structured way. Removing zeros would lead to irregular memory access patterns, which could reduce the efficiency of the memory subsystem, negating the benefits of sparsity.

2. Simplicity of Implementation:

  • Zero Skipping: By retaining the zeros and skipping them during computation, the GPU can still process the data in a regular, predictable pattern. This approach allows the GPU to avoid unnecessary calculations without needing to redesign the entire computation process.
  • Software-Hardware Integration: Existing software and hardware stacks are heavily optimized for dense matrix operations. Introducing mechanisms to handle entirely sparse matrices would require significant changes in the architecture and software, adding complexity and potentially reducing overall performance for general workloads.

3. Maintaining Predictable Latency:

  • Predictable Execution: When zeros are skipped but not removed, the latency of operations can be more predictable, as the GPU’s pipelines are still processing data in a consistent pattern. If zeros were removed, each operation might take a different amount of time depending on how many zeros were present, leading to less predictable performance, which is undesirable in high-performance computing.

Can Zeros Be Removed Directly from Model?

1. It’s Possible, But Tricky:

The challenge with the 2:4 sparsity pattern is that the locations of the two non-zero elements within each group of four are not fixed—they can appear in any position within that group. This randomness introduces some complexity:

Why Random Locations Complicate Removal of Zero Calculations

  1. Irregular Computation Patterns:

    • If the two non-zero elements could be in any position within the group, it means the GPU has to handle various possible configurations dynamically. This makes it difficult to design hardware that can completely eliminate zero computations because the pattern isn’t predictable in advance.

  2. Dynamic Branching and Control Logic:

    • To remove zero calculations entirely, the hardware would need to implement dynamic branching or control logic to skip over zeros based on their positions, which could introduce inefficiencies, such as branching penalties or additional overhead in managing this control flow.

  3. Impact on Parallelism:

    • GPUs rely on highly parallel operations. If the positions of non-zero elements were fixed, the hardware could be optimized for that specific pattern, allowing all processing units to work in unison. However, with random positions, the processing units may end up underutilized if some of them are assigned to zeros, which they must skip dynamically.

2. Trade-offs:

  • Overhead and Complexity: Removing zeros entirely introduces overhead in managing the sparse data structure, which can offset the benefits of sparsity, especially in general-purpose GPU computing. The overhead includes storing indices, handling irregular memory accesses, and potentially having to rebuild large portions of the computation pipeline.
  • Reduced Flexibility: Hardware designed to handle fully sparse data structures might not perform as well on dense data, making it less versatile for different types of workloads.

Structure Zero Sparsity Issues

The 2:4 sparsity pattern does indeed involve some additional overhead beyond just the basic compression ratio. Here’s a more detailed breakdown:

Overhead in 2:4 Sparsity Pattern

  • Index Storage: While the 2:4 pattern inherently has 50% of its elements as zero, managing this pattern involves storing additional metadata, such as indices or masks, to indicate the positions of the non-zero elements. This metadata adds some overhead, reducing the effective compression ratio compared to a straightforward 50% reduction.

  • Data Representation: The overhead includes not only storing indices or masks but also aligning data structures to fit the pattern. This can affect how efficiently the memory is utilized and how data is processed.

  • Practical Compression Ratio: Because of this overhead, the practical compression ratio is lower than the theoretical 50%. The actual ratio depends on how efficiently the indices and patterns are managed and stored.

Comparison with Other Patterns

  • Higher Compression Patterns: For more aggressive compression, patterns like 3:4 sparsity or specialized sparse matrix formats can achieve higher compression ratios, but they might require more complex handling and could impact performance if not managed carefully.

  • Trade-Offs: The 2:4 pattern is a compromise between achieving good computational performance and maintaining a manageable level of overhead. It allows GPUs to skip over zeros efficiently while keeping the system’s complexity under control.

So, while the 2:4 pattern offers performance improvements by utilizing sparsity, the actual compression benefit is somewhat reduced by the need to handle the sparse representation and manage overhead.

Dense TOPS But Focus on Compression to Reduce the Memory BW and Footprint

  1. Sparsity pruning, but use higher compression patterns or semi-structure pattern. Even not pruning to zero, but some centroids.
  2. Use advanced compression technologies to reduce the memory footprint and BW.
  3. Perform decompress on the fly during computation
  4. May or may not to implement zero skipping to increase TOPS if memory BW is the primarily concerns. 4.
  Nvidia GPU Other method
Pruning SW  
Zero pattern 2:4 structure zeros structured or semi-structu d
Compression Less than 50% compression ratio Much better compression r io
Decompression inside GPU  
Zero-skipping Yes, x2 TOPS May or M
Purpose x2 TOPS, computation 50-70% memory footprint and BW reduction and BW