Final Project Proposal

# 112-1 Parallel Programming Final Project Draft ## Title Sparse Matrix Parallelization for Optimizing Deep Learning on Edge Devices ## The participant(s) - Yong Cheng Liaw yongchengliaw.ii12@nycu.edu.tw - 312581014 陳禹勳 - Shih Chi Cheng eziotiar@gmail.com ## Abstract This study delves into optimizing deep learning on edge devices through two parallelization methods: OpenMP and std::thread. Harnessing the power of OpenMP's parallel computing framework and the flexibility of std:thread in C++, we aim to efficiently manage sparse matrices within neural network structures. Experimental assessments on representative edge hardware platforms will showcase the effectiveness of OpenMP and std:thread in accelerating inference and training processes. This research provides crucial insights into deploying resource-efficient deep learning models on edge devices, addressing computational demands and leveraging the concurrency capabilities of both OpenMP and std:thread.  ## Introduction In recent years, the field of deep learning has experienced an unprecedented surge in model scale, marked by a substantial increase in the number of parameters. While this evolution captivates both academic and industrial attention, a critical concern arises regarding the widening gap between model scales and available computational resources. This is particularly evident in instances like the GPT-3 model with its staggering 175 billion parameters, posing significant challenges in training and deploying such large-scale models even on high-performance servers, let alone on average PCs and mobile devices. To address these challenges, researchers and engineers have explored various techniques, including quantization, to mitigate model size and computational requirements. However, when it comes to edge computing devices such as IoT gadgets and smartphones, characterized by a lack of GPU accelerators, the challenge intensifies. Traditionally, quantization techniques have been favored, albeit with precision trade-offs. In this context, Pruning emerges as a promising technique. Studies reveal that a substantial number of neural network parameters have values close to zero, and by employing Pruning, these negligible values can be set to zero, significantly reducing model size and memory demands. This approach not only diminishes storage requirements but also ensures retained model accuracy, providing a novel direction for future neural network model deployments. In our recent studies, we observed that the application of Pruning techniques transforms a significant portion of parameters in large models to zero. By utilizing Sparse Matrix storage methods, we can bypass the need to store all parameters, conservatively utilizing memory resources. However, prevalent frameworks like PyTorch tend to exhibit suboptimal performance in Sparse Matrix Multiplication, impacting computational efficiency as matrix size grows. This study focuses on the execution of neural networks and related applications on edge devices, aiming to efficiently run large models on devices without GPUs and limited DRAM. We propose the transformation of matrices into Sparse Matrix through Pruning as a viable solution, emphasizing the need to optimize Sparse Matrix Multiplication, particularly in the context of Dense multiplied by Sparse Matrix. Our investigation aims to accelerate this multiplication, enhancing the feasibility of running neural network models on edge devices.  ## Proposed Solution 1. pytorch serial algorithm The following is a serial version of the program. However, in the version below, there is a data dependency issue when placing the answers into the corresponding array. Therefore, we have refactored the program's structure while still adhering to its original algorithm. ``` \begin{algorithm} \caption{Sparse Matrix Multiplication} \begin{algorithmic}[1] \For{$i \gets 0$ \textbf{to} $n_{\text{row}} - 1$} \State $head, \text{length} \gets -2, 0$ \For{$jj \gets \text{Ap}[i]$ \textbf{to} $\text{Ap}[i + 1] - 1$} \State $j, v \gets \text{Aj}[jj], \text{Ax}[jj]$ \For{$kk \gets \text{Bp}[j]$ \textbf{to} $\text{Bp}[j + 1] - 1$} \State $k \gets \text{Bj}[kk]$ \State $\text{sums}[k] \mathrel{+}= v \times \text{Bx}[kk]$ \If{$\text{next}[k] = -1$} \State $\text{next}[k], \text{head}, \text{length} \gets \text{head}, k, \text{length} + 1$ \EndIf \EndFor \EndFor \For{$jj \gets 0$ \textbf{to} $\text{length} - 1$} \State $\text{Cj}[\text{nnz}], \text{Cx}[\text{nnz}] \gets \text{head}, \text{sums}[\text{head}]$ \State $\text{nnz} \mathrel{+}= 1$ \State $\text{temp}, \text{head} \gets \text{head}, \text{next}[\text{head}]$ \State $\text{next}[\text{temp}], \text{sums}[\text{temp}] \gets -1, 0$ \EndFor \State $\text{col\_indices\_acc}, \text{val\_acc} \gets \text{Accessor}(\text{Cj} + \text{nnz} - \text{length}, 1), \text{Accessor}(\text{Cx} + \text{nnz} - \text{length}, 1)$ \State $\text{kv\_acc} \gets \text{CompositeAccessor}(\text{col\_indices\_acc}, \text{val\_acc})$ \State $\text{Sort}(\text{kv\_acc}, \text{kv\_acc} + \text{length}, \lambda \text{lhs, rhs} \rightarrow \text{get\_first(lhs) < get\_first(rhs)})$ \State $\text{Cp}[i + 1] \gets \text{nnz}$ \EndFor \end{algorithmic} \end{algorithm} ``` 2. paralllel algorithm - openmp The code below represents the result of resolving the data dependency issue. We addressed this by using a two-dimensional array to store all the results and then sequentially placing the answers into the array. Originally, this action was performed simultaneously during calculations, allowing us to achieve the same result with just a one-dimensional array. Since there is no data dependency, we directly parallelized the for loop. ``` \begin{algorithm} \caption{Parallel Sparse Matrix Multiplication} \begin{algorithmic}[1] \For{$i \gets 0$ \textbf{to} $n_{\text{row}} - 1$} \For{$jj \gets \text{Ap}[i]$ \textbf{to} $\text{Ap}[i + 1] - 1$} \State $j, v \gets \text{Aj}[jj], \text{Ax}[jj]$ \For{$kk \gets \text{Bp}[j]$ \textbf{to} $\text{Bp}[j + 1] - 1$} \State $k \gets \text{Bj}[kk]$ \State $\text{sums}[i][k] \mathrel{+}= v \times \text{Bx}[kk]$ \If{$\text{next}[i][k] = -1$} \State $\text{next}[i][k], \text{head}[i], \text{length}[i] \gets \text{head}[i], k, \text{length}[i] + 1$ \EndIf \EndFor \EndFor \EndFor \State $\text{tempNnz} \gets 0$ \For{$i \gets 0$ \textbf{to} $n_{\text{row}} - 1$} \State $\text{tempNnz} \mathrel{+}= \text{length}[i]$ \State $\text{Cp}[i + 1] \gets \text{tempNnz}$ \EndFor \For{$i \gets 0$ \textbf{to} $n_{\text{row}} - 1$} \State $\text{previous\_nnz} \gets \text{Cp}[i]$ \For{$jj \gets 0$ \textbf{to} $\text{length}[i] - 1$} \State $\text{Cj}[\text{previous\_nnz}], \text{Cx}[\text{previous\_nnz}] \gets \text{head}[i], \text{sums}[i][\text{head}[i]]$ \State $\text{previous\_nnz} \mathrel{+}= 1$ \State $\text{next}[i][\text{head}[i]], \text{sums}[i][\text{head}[i]] \gets -1, 0$ \EndFor \State $\text{Sort}(\text{Cj} + \text{previous\_nnz} - \text{length}[i], \text{Cx} + \text{previous\_nnz} - \text{length}[i], \text{length}[i])$ \EndFor \end{algorithmic} \end{algorithm} ``` - std::thread This code implements a parallel sparse matrix multiplication algorithm. thread_matmul computes the matrix multiplication by traversing each row, while thread_put_answer inserts the results into the output matrix with sorting for specific data structure requirements. _csr_matmult initializes the required data structures and utilizes multiple threads for efficient parallel computation. ``` \documentclass{article} \usepackage{algorithm} \usepackage{algpseudocode} \begin{document} \begin{algorithm} \caption{Threaded Sparse Matrix Multiplication} \begin{algorithmic}[1] \Function{thread\_matmul}{$\text{start\_row}, \text{end\_row}, \text{Ap}, \text{Aj}, \text{Ax}, \text{Bp}, \text{Bj}, \text{Bx}, \text{next}, \text{sums}, \text{head}, \text{length}$} \For{$i \gets \text{start\_row}$ \textbf{to} $\text{end\_row} - 1$} \State $\text{jj\_start}, \text{jj\_end} \gets \text{Ap}[i], \text{Ap}[i + 1]$ \For{$jj \gets \text{jj\_start}$ \textbf{to} $\text{jj\_end} - 1$} \State $j, v \gets \text{Aj}[jj], \text{Ax}[jj]$ \For{$kk \gets \text{Bp}[j]$ \textbf{to} $\text{Bp}[j + 1] - 1$} \State $k, \text{sums}[i][k] \mathrel{+}= \text{Bj}[kk], v \times \text{Bx}[kk]$ \If{$\text{next}[i][k] = -1$} \State $\text{next}[i][k], \text{head}[i], \text{length}[i] \gets \text{head}[i], k, \text{length}[i] + 1$ \EndIf \EndFor \EndFor \EndFor \EndFunction \Function{thread\_put\_answer}{$\text{start\_row}, \text{end\_row}, \text{Cp}, \text{Cj}, \text{Cx}, \text{next}, \text{sums}, \text{head}, \text{length}$} \For{$i \gets \text{start\_row}$ \textbf{to} $\text{end\_row} - 1$} \State $\text{previous\_nnz} \gets \text{Cp}[i]$ \For{$jj \gets 0$ \textbf{to} $\text{length}[i] - 1$} \State $\text{Cj}[\text{previous\_nnz}], \text{Cx}[\text{previous\_nnz}] \gets \text{head}[i], \text{sums}[i][\text{head}[i]]$ \State $\text{previous\_nnz} \mathrel{+}= 1$ \State $temp, \text{head}[i] \gets \text{head}[i], \text{next}[i][\text{head}[i]]$ \State $\text{next}[i][temp], \text{sums}[i][temp] \gets -1, 0$ \State $\text{Sort}(\text{Accessor}(\text{Cj} + \text{previous\_nnz} - \text{length}[i], 1), \text{Accessor}(\text{Cx} + \text{previous\_nnz} - \text{length}[i], 1), \lambda \text{lhs, rhs} \to \text{get\_first}(\text{lhs}) < \text{get\_first}(\text{rhs}))$ \EndFor \EndFor \EndFunction \Function{\_csr\_matmult}{$\text{num\_threads}, \text{n\_row}, \text{n\_col}, \text{Ap}, \text{Aj}, \text{Ax}, \text{Bp}, \text{Bj}, \text{Bx}, \text{Cp}, \text{Cj}, \text{Cx}$} \State \text{initialize\_matrices}($\text{Ap}, \text{Aj}, \text{Ax}, \text{Bp}, \text{Bj}, \text{Bx}, \text{next}, \text{sums}, \text{head}, \text{length}$) \State \text{\#pragma omp parallel for} \For{$\text{each thread}$} \State \text{thread\_matmul}($\text{start\_row}, \text{end\_row}, \text{Ap}, \text{Aj}, \text{Ax}, \text{Bp}, \text{Bj}, \text{Bx}, \text{next}, \text{sums}, \text{head}, \text{length}$) \EndFor \State \text{\#pragma omp parallel for} \For{$\text{each thread}$} \State \text{thread\_put\_answer}($\text{start\_row}, \text{end\_row}, \text{Cp}, \text{Cj}, \text{Cx}, \text{next}, \text{sums}, \text{head}, \text{length}$) \EndFor \EndFunction \end{algorithmic} \end{algorithm} \end{document} ``` 3. memory issue From the above algorithm, we can see that we let each thread process different rows in the matrix respectively, and there will be some temporary variables required in the operation of processing each row. In the parallel algorithm, before we perform multi-thread operations, we directly let each row allocate its own local variable. This simple method can quickly achieve the effect of ensuring that each row gets the correct operation result. But our goal is to run neural networks on edge devices, and we hope to achieve this goal in a more efficient way, so we later proposed a memory efficiency algorithm. We later discovered that although it is simple to allow each row to allocate its own local variable, it will cause excess memory usage. In fact, we only need to let each thread allocate its own local memory. 5. mem efficiency algorithm ![image](https://hackmd.io/_uploads/ByJstapDT.png) In order to save memory usage, we further propose the Memory Efficiency Parallel SPMM algorithm, which mainly improves the previous _csr_matmult function. The biggest improvement from the previous one is that we merged the two originally separate for-loops into one. The reason why two for-loops cause redundant memory allocation is that the program must bring all the temporary variables of each row in the first for-loop to the second for-loop. If there is only one for-loop now, we only need each thread to remember its own local variables. The reason why two for-loops can be merged is because we use the directive called ordered provided by OpenMP to force the executing threads to execute in the order of thread IDs, and at the same time make the order of row indices through schedule(static, 1) Consistent with thread IDs. In this way, the code block contained in ordered can be executed in the order of row indices, and there is no need to write another for-loop outside omp parallel for, so the two for-loops become one . ## Experimental Methodology In the previous section, we discussed the implementation of different strategies for sparse matrix multiplication within PyTorch extensions. We evaluated these functions through two methods and conducted benchmarks on an AMD 16-core machine, which helped avoid the performance cores and efficiency cores issues commonly faced with Intel processors. The first method we used was to measure the time it takes for the entire function to run, known as end-to-end function latency. To do this, we recorded the time before and after running the function in different situations using Python’s time.perf_counter(). These situations included using matrices of various densities and sizes, and running the process with a different number of threads. The goal of this method was to show how well our parallel implementation works with different kinds of matrices, ranging from small to large, from sparse to nearly dense, and from processing on a single core to processing on multiple cores. We also tested real applications by using sparse matrix-matrix multiplication (SpMM) in an MNIST image classification task. First, we trained the model in standard conditions. After training, we pruned the matrix weights in an unstructured manner. During the testing phase, we replaced the original sparse matrix multiplication with various methods from our study. This was done to compare the performance in the MNIST classification task, particularly with a dataset of 10,000 images. ## Experimental Results Table: End-To-End Function Latency | Left Matrix Size | Left Matrix Density | Right Matrix Size | Right Matrix Density | Number Of Threads | Serial(ms) | std::thread(ms) | OpenMP(ms) | Memory Efficient(ms) | | ---------------- | ------------------- | ----------------- | -------------------- | ----------------- | ---------- | --------------- | ---------- | -------------------- | | 512 x 512 | 0.4 | 512 x 512 | 0.4 | 4 | 33.14 | 11.08 | 15.09 | 14.72 | | 512 x 512 | 0.4 | 512 x 512 | 0.4 | 16 | 34.55 | 6.05 | 4.85 | 8.41 | | 4096 x 4096 | 0.4 | 4096 x 4096 | 0.4 | 4 | 15601.41 | 4623.11 | 5100.09 | 4959.83 | | 4096 x 4096 | 0.4 | 4096 x 4096 | 0.4 | 16 | 15669.71 | 2267.18 | 2295.48 | 2488.18 | | 512 x 512 | 0.8 | 512 x 512 | 0.8 | 4 | 97.93 | 27.63 | 32.65 | 30.84 | | 512 x 512 | 0.8 | 512 x 512 | 0.8 | 16 | 98.21 | 10.63 | 12.32 | 10.90 | | 4096 x 4096 | 0.8 | 4096 x 4096 | 0.8 | 4 | 54057.24 | 17256.11 | 19494.78 | 18926.22 | | 4096 x 4096 | 0.8 | 4096 x 4096 | 0.8 | 16 | 53786.42 | 4570.78 | 5170.98 | 5632.70 | Table: Mnist Classification Inference Latency | Prune Density | Number Of Threads | Serial(ms) | std::thread(ms) | OpenMP(ms) | Memory Efficient(ms) | | ------------- | ----------------- | ---------- | --------------- | ---------- | -------------------- | | 0.4 | 2 | 30130.89 | 20241.05 | 19254.14 | 18818.39 | | 0.4 | 4 | 24921.64 | 14594.13 | 14189.46 | 12516.93 | | 0.4 | 8 | 23164.92 | 14185.33 | 13427.95 | 11108.49 | | 0.4 | 16 | 23020.99 | 15422.17 | 13544.77 | 11220.92 | The first part of our evaluation involved measuring the end-to-end function latency for various matrix sizes, densities, and thread counts. The std::thread strategy consistently outperformed other methods, most notably in smaller matrix sizes (512x512). This superior performance can be attributed to its one-time thread creation and closure mechanism, minimizing the overhead associated with dynamic job assignment found in other methods like OpenMP and memory efficiency. However, it's notable that as matrices increase in size and density, the advantages of parallel processing become more pronounced. This is due to a higher number of non-zero values in larger or denser matrices, providing more opportunities for performance enhancement through parallel computation. In the context of a real-world application, using the MNIST image classification task, different threading strategies were evaluated. Here, memory-efficient algorithms emerged as the most effective. These algorithms excel in handling unbalanced real-world matrices due to their superior workload management and scheduling strategies, which outperform the fixed workload approach of standard threads and the original coordination in OpenMP. Interestingly, the results indicate that increasing the number of threads does not always correlate with enhanced performance. Particularly, using 16 threads showed negligible improvements over 8 threads. This can be attributed to the overhead involved in thread creation, which becomes significant in smaller matrices. Hence, a mixed approach, tailoring the number of threads to the matrix size, could potentially yield better performance. Based on the observation, we have following insights and future directions: (1) Thread Strategy Optimization: The std::thread strategy's dominance in smaller, balanced matrices and the memory-efficient strategy's effectiveness in unbalanced real-world scenarios suggest a need for adaptive threading strategies. Future implementations could dynamically select the optimal threading strategy based on matrix characteristics. (2) Performance in Varied Matrix Sizes: The varying effectiveness of different threading strategies across different matrix sizes and densities highlights the importance of context-specific optimizations. Future research could focus on developing more nuanced, matrix-specific parallel processing techniques. (3) Thread Count Optimization: The observation that increasing the number of threads beyond a certain point does not yield proportional performance gains is crucial. This insight could guide the development of algorithms that dynamically adjust thread counts based on matrix size and computational complexity. (4) Benchmarking and Real-World Performance Discrepancies: The disparity between benchmarking results and real-world application performance emphasizes the need for more representative benchmarking methods. Future benchmarks should incorporate a wider range of matrix sizes and densities to more accurately reflect real-world scenarios. The benchmarks indicate significant performance improvements, with small matrices showing up to 9.24 times faster processing and large matrices up to 11.76 times faster. In MNIST classification, a performance boost of up to 2.09 times was observed. These findings underscore the effectiveness of optimized sparse matrix multiplication strategies in both synthetic and real-world applications.   ## Related Work \paragraph{PyTorch} PyTorch is a popular deep learning framework that provides powerful tools and libraries for building and training neural network models. It is widely used in research and applications, particularly for deep learning tasks. \paragraph{Edge Device} An edge device refers to a computing device located at the network's edge, close to data sources or end-users. These devices are typically used for data processing and decision-making to reduce data transmission and latency. DRAM stands for Dynamic Random-Access Memory, which is a type of memory used in computer systems for storing data and programs. DRAM limitation indicates that a computing device has limited memory capacity, which may result in memory constraints affecting performance or application execution. \paragraph{Model Pruning} Pruning is an optimization technique for deep learning models. It involves removing unnecessary neurons or weights to reduce the model's complexity and memory footprint while striving to maintain model performance. This helps accelerate the inference process and reduce model storage requirements. \paragraph{Sparse Matrix Characteristics} Sparse matrices are matrices in which the majority of elements are zero. Sparse matrices exhibit specific characteristics that can be utilized for optimizing storage and computations. COO (Coordinate Format) and CSR (Compressed Sparse Row Format) are two common formats used to represent sparse matrices. The COO format uses coordinates to represent the positions of non-zero elements, while the CSR format reduces memory usage by efficiently encoding the values and positions of non-zero elements. These formats are valuable in sparse matrix operations. ## Conclusions 1. chatgpt ## References 1. 根據我們寫完的全文補reference ## 分工 1. 陳 1. Abstract 2. Introduction 3. Proposed Solution (1, 2) 2. 鄭 1. Proposed Solution (4, 5) 2. Related Work 3. Conclusions 4. Reference 5. Overleaf 3. 廖 1. Experimental Methodology 2. Experimental Methodology

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.