# Parallel Programming Final Project Proposal Draft

### Title

Sparse Matrix Parallelization for Optimizing Deep Learning on Edge Devices

### The participant(s)

- Yong Cheng Liaw [e-mail]
- 312581014 陳禹勳
- Shih Chi Cheng [e-mail]

### Introduction/motivation

#### Introduction

In recent years, the scale of deep learning models has witnessed a staggering increase. Transitioning from foundational models of the past to the advanced architectures of today, a marked surge in the number of parameters is evident. This evolution, while capturing academia's interest, also garners significant attention in the industrial sector. A pressing concern that emerges is the rate at which model scales are outpacing the advancements in computational resources. Even with state-of-the-art hardware, we're presented with challenges in efficiently training and deploying these large-scale models.

Take GPT-3 as an illustrative example. With over 175 billion parameters, operating it on standard computational devices becomes a formidable challenge. Training such a model on even high-performance servers necessitates significant time and resource commitments, rendering it nearly impossible for average PCs and mobile devices. Furthermore, similar challenges persist in other domains, such as recommendation systems and image processing. Consequently, researchers and engineers are exploring quantization and other methods to mitigate model size and computational requirements. This not only facilitates easier model deployment across devices but also ensures commendable performance within constrained computational environments.

Indeed, when considering edge computing devices like IoT gadgets and smartphones, the challenge intensifies. Typically devoid of GPU accelerators, finding efficient ways to run neural network models on these platforms becomes paramount. Historically, the community leaned towards quantization techniques, transitioning from float32 to representations like int8 or 4 bits. However, this often resulted in a trade-off with precision.

Yet, Prunning emerges as a promising technique. Studies, such as these Prunning-related papers, reveal that a substantial number of neural network parameters have values close to zero. By employing Prunning, these negligible values can be set to zero, substantially reducing model size and memory demands. This approach not only diminishes storage requirements but also retains model accuracy, paving a novel direction for future neural network model deployments.

#### Motivation

In recent studies, we have observed that the application of Prunning techniques can transform a significant portion of parameters in large models to zero. By utilizing Sparse Matrix storage methods, we can bypass the necessity to store all parameters, thereby conservatively using memory resources. In contrast, if we continue to store these Prunned models in a Dense Matrix format, we won't truly reap the benefits of memory savings, as even the zero values remain stored. Therefore, to genuinely save on memory, it is crucial to employ Sparse Matrix formats, focusing only on storing non-zero values. This highlights the significance of Sparse Matrix in scenarios where memory savings through Prunning is desired.

However, based on our empirical observations, the prevalent PyTorch framework, when handling Sparse Matrix Multiplication, predominantly adopts the CSR Format for Sparse Matrix storage and resorts to Serial algorithms for computation. Through comparative analysis with Dense Matrix Multiplication, a noteworthy finding is that computational efficiency of Sparse Matrix operations tends to exponentially decrease as the size of the Matrix grows. This sheds light on the current suboptimal performance of Sparse Matrix Multiplication in neural network applications: while it indeed saves memory, the trade-off in computational efficiency is substantial. Consequently, exploring avenues to optimize Sparse Matrix Multiplication and enhance its computational performance has emerged as a pivotal research concern.

### Statement of the problem (Which application did you choose for this project? Why did you choose this problem?)

The primary concern of this study revolves around the execution of neural networks and related applications on edge devices. With the contemporary growth in the size of neural network models, we are challenged with the task of efficiently running these vast models on devices devoid of GPUs and with limited DRAM. We propose that transforming matrices into Sparse Matrix through the technique of Prunning could be a viable solution. However, based on the current architecture of Pytorch, directly applying its existing framework results in a notable setback: the inherent computation speed for Sparse Matrix in Pytorch is considerably slow, hindering its practical applicability. Consequently, our approach emphasizes on speeding up Sparse Matrix Multiplication by leveraging parallel computation.

Importantly, our investigation specifically delves into the scenario of Dense multiplied by Sparse Matrix. This is primarily because, in neural networks, model input features are often in a Dense format. Our main objective in Prunning targets the model weights, aiming to convert them into a Sparse Matrix. Given that the predominant operations in neural networks involve multiplication of the Input and Weight, we believe that accelerating the multiplication in the Dense-to-Sparse context is pivotal. If we can achieve optimized multiplication between Dense and Sparse matrices, it promises to greatly enhance the feasibility of running neural network models on edge devices.

### Proposed approaches, which include the block diagram (or architecture) of you system. Please describe the function of each components, and the interaction among these components.

1. block diagram / flow chart


2. description

We will implement a operator of multiplication between sparse matrix and dense matrix by pytorch C++ extension, allowing for fine-grained control, optimization, and integration with the existing PyTorch ecosystem. For easier use, we will wrap this operator into a separate Python package.

### Language selection (What parallel language do you use? Why do you use this parallel language?)

In the implementation of the operator for multiplying a sparse matrix by a dense matrix, we utilize C++ standard threading library, std::thread, for parallelization. The reason why we use std::thread to implement it is due to :
1. Ease of Integration: Since we are implementing the operator as a PyTorch C++ extension, it is beneficial to use a threading library that easily integrates with C++ and does not introduce additional dependencies. std::thread fulfills this requirement as it is natively supported by C++.
2. Efficient Utilization of Resources: By parallelizing the sparse-dense matrix multiplication operation using std::thread, we can efficiently utilize available CPU cores. This is particularly important for large-scale matrix operations, where the computational load can be distributed across multiple threads to achieve faster execution times.
3. Granular Control: std::thread provides a low-level interface for thread management, giving the developer granular control over thread creation, synchronization, and termination. This is crucial for performance-critical applications like matrix multiplication, where optimizing thread utilization and minimizing overhead can lead to significant performance gains. This is the main difference with OpenMP.

### Related work

1. 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.
2. 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 limitation : 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.
3. 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.
4. 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 and CSR Formats: 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.

### Statement of expected results

While striving to conserve memory through the utilization of sparse data characteristics, we anticipate achieving a significant reduction in memory usage without compromising performance to a significant extent. This implies that we aim to efficiently store and process extensive datasets while minimizing the system's memory requirements. By employing effective strategies for handling sparse data, such as zero values and repetitiveness, we seek to reduce memory footprint.

The desired outcomes encompass the implementation of various optimization techniques in data processing to make full use of the sparsity of the data, ensuring that these optimizations do not significantly impact the speed and quality of data processing, meeting the requirements of applications or tasks.

By successfully implementing these memory optimization measures, we aim to reduce memory demands while maintaining satisfactory performance, enhancing the scalability of applications, reducing hardware costs, and facilitating larger-scale data processing and analysis. In summary, our expectation is to strike an ideal balance between memory and performance by capitalizing on data sparsity, resulting in more efficient computations and resource utilization.

### A timetable


### References
- A Systematic Survey of General Sparse Matrix-Matrix Multiplication. https://arxiv.org/pdf/2007.03179.pdf
- GE-SpMM: General-purpose Sparse Matrix-Matrix Multiplication on GPUs for Graph Neural Networks. https://arxiv.org/pdf/2002.11273.pdf
- Pytorch https://github.com/pytorch