Paper Link : https://ieeexplore.ieee.org/document/8192500
Github : https://github.com/jiecaoyu/scalpel-1
Introduction
ISCA에 2017년에 게재된 논문입니다. 이 논문에서는 network pruning을 함에도 불구하고 실제로는 inference시에 퍼포먼스가 떨어지는 것을 지적한 뒤 하드웨어의 병렬성에 최적화하여 pruning 하는 기법을 소개합니다. 병렬성 수준에 따라 SIMD-aware pruning, Node pruning을 소개하며 5개의 DNN에 대해 3가지 하드웨어 플랫폼에 따른 실험을 통해 기존의 방법들을 얼마나 outperform 하는지 보여줍니다.
전통적인 pruning의 경우 가장 많이 이야기되는 것은 이전에 리뷰한 Song.H의 방법입니다. 하지만 이 방법은 기존의 dense matrix를 irregular 한 형태로 만듭니다. irregular 한 형태의 matrix는 후에 CSR format으로 저장되고 이를 디코드 할 때 오버헤드를 발생시킵니다. 우리가 pruning을 하는 것은 네트워크 사이즈를 작게 만들어 SRAM에 올린 뒤 memory reference시에 생기는 bottleneck을 원천적으로 없애기 위함입니다. 하지만 전통적인 기법으로 만들어진 network의 퍼포먼스는 이러한 motivation을 무색하게끔 만듭니다.
Microcontroller의 경우 weight pruning시 DNN의 퍼포먼스를 일관되게 향상시킵니다. 이는 microcontroller가 단순한 구조라 memory access latency에 영향을 받기 때문에 model size를 줄여주는 것만으로도 sparse matrix를 계산할 때의 비효율성을 보완해줄 수 있기 때문입니다.
CPU의 경우, pruning의 효과가 convolution layer인지 fully connected layer인지에 따라 달라집니다. FC layer의 경우에는 전체 메모리 접근이 줄어들기 때문에 성능이 향상됩니다. 하지만 Conv layer는 matrix-matrix multiplication을 수행하기 때문에 메모리 재사용이 많아 메모리 접근에서 이득을 취할 수 없고 sparse matrix format으로 인해서 퍼포먼스가 하락하게 됩니다.
GPU에서는 sparse matrix computation 자체가 하드웨어적인 특성인 memory coalecing 때문에 적합하지 않기 때문에 퍼포먼스가 줄어듭니다.
Challenge
Weight pruning을 하는 것은 DNN의 model size와 MAC operation의 수를 줄여주지만 기존의 방법들은 여러 가지 문제점들이 있습니다.
첫 번째로는 sparse matrix를 CSR format과 같은 sparse matrix format으로 저장 시에 용량이 증가하는 것입니다. CSR format은 sparse matrix를 저장하는 자료구조 중 하나인데, 이는 sparse matrix를 non-zero value in matrix, index of the first non-zero element in each row, column index of the non-zero element로 저장합니다. 이때 column index array의 크기가 data array의 크기와 같기 때문에 CSR format의 데이터 중 절반 이상이 sparse matrix format을 저장하는 데 사용됩니다.
두 번째로는 weight pruning시 computation performance가 줄어드는 것입니다. 위의 표는 전통적인 pruning을 사용했을 때 나타나는 execution time을 hardware에 따라 정리한 표입니다. 여기서 눈 여겨볼 수 있는 것은 MAC operation이 증가하는 정도보다 relative execution time이 증가하는 정도가 훨씬 크다는 것입니다. 이에 대해 논문에서는 CPU 위에서의 dense DNN model과 sparse DNN model을 분석했습니다.
위의 표는 sparse DNN의 expected execution time을 보여줍니다. FC layer의 경우 전통적인 pruning을 적용하였을 때 execution time이 상당히 줄어든 것을 볼 수 있습니다. 반면, Conv layer의 경우 오히려 execution time이 상당히 증가한 것을 볼 수 있습니다.
우리가 CNN에서 연산할 때 FC layer에서는 matrix-vector multiplication을 Conv layer에서는 matrix-matrix multiplication을 합니다. CSR format으로 SPMV을 할 때 첫 번째로 matrix의 원소에 해당하는 column index를 불러옵니다. 그리고 이를 input vector에서 input value를 불러오는 데 사용합니다. 이때 input value를 indexing 하는 과정에서 부가적인 computation과 memory access가 필요합니다. 그런데 sparse matrix가 regularity를 잃게 된다면 matrix tiling과 같은 optimization을 하기 힘듭니다. 그래서 우리가 pruning을 하고 난 뒤 예상하는 execution time과 실제 execution time이 차이가 나게 되는 것입니다.
그래도 FC layer의 경우에는 Conv layer의 경우보다는 상황이 괜찮습니다. 왜냐하면 CPU computation의 경우 Conv layer와 비교했을 때 computation/memory access ratio가 적기 때문입니다. (이에 대해서는 FC layer에서 computation은 MV multiplication이라 matrix내의 row를 한 줄 읽어오고 연산 후에 버려도 괜찮은데 Conv layer는 filter로 MM multiplication을 해서 re-using이 많기 때문입니다.)
위의 표는 AlexNet의 두 번째 Conv layer에서 matrix-matrix multiplication을 했을 시에 일어나는 cache access, miss를 분석한 것입니다. 이를 보면 알 수 있다시피 sparsity를 키울수록 access, miss 하는 수가 점점 많아짐을 알 수 있습니다. sparsity를 80%까지는 올려줘야 access, miss하는 수가 60% 일 때 보다 줄어들지만 여전히 dense 한 경우보다는 좋지 않은 결과를 보여줍니다.
Scalpel
SIMD-Aware Weight Pruning
우선 모든 weight matrix를 SIMD의 길이와 같은 크기의 aligned group으로 나눕니다. 그리고 각 group의 RMS를 계산한 뒤, 이를 중요도로 사용해 일정 threshold 이하로 내려간 group들을 제거해줍니다. 그리고 pruned 된 network를 다시 학습시킵니다. 이 과정을 반복해서 original network의 성능이 유지되기 전까지 진행합니다. 이는 layer 단위로 진행되는데, 맨 처음에 각 layer에서의 execution time을 계산하고 이것이 가장 큰 layer부터 pruning을 합니다. 이후 iteration마다 execution time을 확인하고 높은 layer부터 다시 진행합니다.
학습 과정에는 dropout 또한 사용되었습니다. 이때 dropout ratio는 Song.H이 사용했던 방법과 같은 방법을 이용하여 이를 조절하였습니다.
학습이 끝난 뒤에는 sparse matrix를 저장하기 위해서 CSR format을 group 단위로 수정합니다. 이때 원소는 matrix 내의 group의 원소로, column index는 group의 index로 저장해줍니다. 이때 column index를 group단위로 저장하기 때문에 index array와 model size를 줄이는 데 상당한 효과가 있습니다.
Node Pruning
Node pruning에서는 개별적인 weight 대신 node를 pruning 합니다. 이때 node는 FC layer에서의 neuron, Conv layer에서의 feature map을 의미합니다. 이들은 activation map 이후, mask layer를 두어 중요하지 않은 node를 찾아 그 출력에 0을 씌워 출력을 막아버립니다. 이렇게 하면 model size는 줄이면서 matrix내의 sparsity는 감소시키지 않으며, dense 한 구조를 그대로 유지시킬 수 있습니다. 이때 각 node mask는 α, β 두 개의 파라미터를 갖습니다. α는 0, 1만을 값으로 가질 수 있고, β는 0과 1 사이의 실수 값을 가집니다. α가 0인 경우는 해당 노드를 제거하는 것을 의미하며, β는역전파 시에 업데이트되는 파라미터입니다.
맨 처음에는 α, β 를 모두 1로 초기화하며, 학습을 반복하면서 α를 다음과 같이 업데이트합니다.
이때 pruning 할 node를 제어하기 위해서 mask layer의 β에 대해 L1 regularization을 사용했습니다. 이는 다음과 같이 계산합니다.
여기서 lamda는 weight decay를 의미합니다. 학습이 끝날 때마다 weight decay를 증가시켜 더 많은 노드들이 제거될 수 있도록 반복해줍니다. Dropout 또한 pruning 과정 중에 사용되었는데, 이는 Song.H의 방법을 node 버전으로 바꾸어 사용했습니다. 이 방법 또한 original network의 accuracy를 유지하지 못할 때까지 반복하고, 마지막으로는 mask 된 node와 mask layer를 제거하고 retraining을 시켜줍니다.
Combined Pruning
CPU 정도의 병렬성을 가진 하드웨어의 경우에는 SIMD-aware pruning과 node pruning을 같이 씁니다. CNN의 경우에는 FC layer와 Conv layer로 나누어져 있는데, FC layer에는 SIMD-aware pruning을 Conv layer에는 node pruning을 적용합니다. 이때 Conv layer에 대해 node pruning을 먼저 적용하여 Conv layer를 고정시킨 뒤 FC layer에 SIMD-aware pruning을 적용합니다.
여하튼, 이렇게 SIMD-aware pruning을 하게 되면 크게 세 가지 장점이 있습니다.
1. Grouping을 해서 sparse matrix format으로 저장했기 때문에 index 수가 감소해 memory footprint를 줄일 수 있습니다.
2. Weight들이 grouping 되고 grouping index로 정렬되기 때문에 reading weights과 corresponding input 간의 spatial locality를 증가시킬 수 있습니다.
3. 각 group과 corresponding input value에 대해서 하나의 index만 load 하면 되기 때문에 computation instruction 수가 줄어듭니다.
SPMV의 경우 SIME-aware pruning이 novelty가 있는 것을 볼 수 있지만 SPMM은 SIMD-aware pruning을 할 경우 traditional pruning을 한 뒤, MKL library를 통해 계산을 한 것이 더 나은 퍼포먼스를 보여줍니다. 이런 문제 때문에 SPMM을 하는 Conv layer의 경우 node pruning을 진행했습니다.
Experiment Methodology
Hardware platform
Low parallelism: ARM Cortex-M4
- 3-stage in-order pipeline, 2-way SIMD units for 16-bit FP
Moderate parallelism: Intel Core i7-6700
- 8-way SIMD instructions for 32-bit FP
- MKL BLAS GEMV/GEMM
- MKL Spars BLAS CSRMB/CSRMM
High parallelism: NVIDIA GTX Titan X
- cuDNN implementation
- cuBLAS GEMV/GEMM
- cuSPARSE CSRMV/CSRMM
Benchmarks