# CuAlgo
CuAlgo is a Python library benefiting from GPU-accelerated computing, featuring a collection of fundamental algorithms implemented with CUDA. Currently, it includes the Floyd-Warshall algorithm for graph analysis, showcasing the potential of GPU acceleration.
[](https://repology.org/project/python:cualgo/versions) [](https://pypi.org/project/cualgo/) [](https://pypi.org/project/cualgo/) [](https://github.com/anderson101866/cualgo/actions/workflows/python-app.yml)
## Key Features
#### Graph Algorithms:
- Floyd-Warshall algorithm
## Why CuAlgo?
- **Significant Speedup**: Experience substantial performance gains with CuAlgo's GPU-accelerated algorithms compared to their CPU approaches.
- **User-Friendly Python Interface**: CuAlgo provides convenient interface for Python users. It is compatible with **NumPy**, allowing for easy data interchange with existing scientific computing workflows. Ensuring that python developers can leverage GPU acceleration without delving into CUDA programming details.
- **Cross-Platform Compatibility**: Developed with CMake, CuAlgo supports cross-platform development, enabling seamless compilation on various operating systems.
## Performance Evaluation
Explore different implementations of the Floyd-Warshall algorithm using datasets of sizes N=40, N=1000, and N=2000. This section presents a comprehensive analysis of the efficiency improvements achieved through GPU acceleration.
### Methodology
- **CPU Version**: The algorithm is executed on the CPU without GPU acceleration.
- **CPU (12 threads) Version**: Runs on the CPU with 12 threads using OpenMP.
- **GPU (Unoptimized) Version**: Initial GPU implementation with similar parallelism as the next GPU (Optimized) Version.
- **GPU (Optimized) Version**: GPU implementation with optimizations, including loop/block unrolling, dynamic parallelism, and coalesced memory access, fully leveraging GPU resources efficiently.
<img src="https://github.com/anderson101866/cualgo/assets/15830675/9d6d4b2e-d4fa-4db1-9a52-fd3d42d325cc" width="600">
<img src="https://github.com/anderson101866/cualgo/assets/15830675/4e3a0fd1-ff81-4d92-9531-b06c1483a9d0" width="600">
The charts illustrate the speedup achieved by CuAlgo's GPU-accelerated algorithms over CPU-based implementations. Notably, the optimized GPU version outperforms both the unoptimized GPU and CPU versions when N grows large, emphasizing the impact of optimization on algorithm efficiency.
### Hardware and Software Information:
| <!-- --> | <!-- --> |
|-----------|-------------------------------------|
| CPU | AMD Ryzen 9 5900X 12-Core Processor |
| GPU | NVIDIA GeForce RTX 3060 Ti - 8GB |
| RAM | 32GB DDR4 3600 Mhz |
| CUDA Toolkit Version | 12.2 |
| GPU Driver Version | 537.13 |
## Prerequisites
(For linux, need GCC compiler with C++ support (gcc works better with CUDA's compiler), and GNU make)
1. Latest [NVIDIA GPU driver](https://www.nvidia.com.tw/Download/index.aspx)
2. *Python 3.7+ with pip available*
3. *Latest CUDA toolkit installed with nvcc compiler. [(download here)](https://developer.nvidia.com/cuda-downloads)*
**NOTE: [Recommended]** You can skip 2 and 3. by using [conda](https://repo.anaconda.com/archive/), see [Installation](#Installation) below
## Installation
### Linux / Windows [Recommended]:
```bash
conda install cuda -c nvidia
python -m pip install --upgrade pip
pip install cualgo
```
### Windows (without conda):
1. Install NVIDIA latest GPU driver by yourself
2. `python -m pip install --upgrade pip && pip install cualgo`
## Sample Code
Support data type of `Numpy`.
```python
from cualgo import graph as cg
import numpy as np
graph = np.array([
[0 , 7 , np.inf, 8],
[np.inf, 0 , 5 , np.inf],
[np.inf, np.inf, 0 , 2],
[np.inf, np.inf, np.inf, 0]
], dtype=np.float64)
print(cg.floydwarshall(graph))
# [[0.0, 7.0, 12.0, 8.0], [inf, 0.0, 5.0, 7.0], [inf, inf, 0.0, 2.0], [inf, inf, inf, 0.0]]
```
Or just simply pass 2D `list` in python
```python
from cualgo import graph as cg
INF = 9999
graph = [
[0 , 7 , INF, 8],
[INF, 0 , 5 , INF],
[INF, INF, 0 , 2],
[INF, INF, INF, 0]
]
print(cg.floydwarshall(graph))
# [[0, 7, 12, 8], [9999, 0, 5, 7], [9999, 9999, 0, 2], [9999, 9999, 9999, 0]]
```
Raw data
{
"_id": null,
"home_page": "https://github.com/anderson101866/cualgo",
"name": "cualgo",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "python,cuda,gpu,algorithm,numpy",
"author": "Anderson Meng",
"author_email": "andersonchi1018@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/dc/e8/d977970fa1ebc7a0e3b1e592edb45ec5554aae791ff4fe88ec9f814de8fb/cualgo-0.2.0.tar.gz",
"platform": null,
"description": "# CuAlgo\r\n\r\nCuAlgo is a Python library benefiting from GPU-accelerated computing, featuring a collection of fundamental algorithms implemented with CUDA. Currently, it includes the Floyd-Warshall algorithm for graph analysis, showcasing the potential of GPU acceleration.\r\n\r\n[](https://repology.org/project/python:cualgo/versions) [](https://pypi.org/project/cualgo/) [](https://pypi.org/project/cualgo/) [](https://github.com/anderson101866/cualgo/actions/workflows/python-app.yml)\r\n\r\n## Key Features\r\n#### Graph Algorithms: \r\n - Floyd-Warshall algorithm\r\n\r\n## Why CuAlgo?\r\n\r\n- **Significant Speedup**: Experience substantial performance gains with CuAlgo's GPU-accelerated algorithms compared to their CPU approaches.\r\n- **User-Friendly Python Interface**: CuAlgo provides convenient interface for Python users. It is compatible with **NumPy**, allowing for easy data interchange with existing scientific computing workflows. Ensuring that python developers can leverage GPU acceleration without delving into CUDA programming details.\r\n- **Cross-Platform Compatibility**: Developed with CMake, CuAlgo supports cross-platform development, enabling seamless compilation on various operating systems.\r\n\r\n## Performance Evaluation\r\nExplore different implementations of the Floyd-Warshall algorithm using datasets of sizes N=40, N=1000, and N=2000. This section presents a comprehensive analysis of the efficiency improvements achieved through GPU acceleration.\r\n\r\n### Methodology\r\n- **CPU Version**: The algorithm is executed on the CPU without GPU acceleration.\r\n- **CPU (12 threads) Version**: Runs on the CPU with 12 threads using OpenMP.\r\n- **GPU (Unoptimized) Version**: Initial GPU implementation with similar parallelism as the next GPU (Optimized) Version.\r\n- **GPU (Optimized) Version**: GPU implementation with optimizations, including loop/block unrolling, dynamic parallelism, and coalesced memory access, fully leveraging GPU resources efficiently.\r\n\r\n<img src=\"https://github.com/anderson101866/cualgo/assets/15830675/9d6d4b2e-d4fa-4db1-9a52-fd3d42d325cc\" width=\"600\">\r\n<img src=\"https://github.com/anderson101866/cualgo/assets/15830675/4e3a0fd1-ff81-4d92-9531-b06c1483a9d0\" width=\"600\">\r\n\r\nThe charts illustrate the speedup achieved by CuAlgo's GPU-accelerated algorithms over CPU-based implementations. Notably, the optimized GPU version outperforms both the unoptimized GPU and CPU versions when N grows large, emphasizing the impact of optimization on algorithm efficiency.\r\n\r\n### Hardware and Software Information:\r\n| <!-- --> | <!-- --> |\r\n|-----------|-------------------------------------|\r\n| CPU | AMD Ryzen 9 5900X 12-Core Processor |\r\n| GPU | NVIDIA GeForce RTX 3060 Ti - 8GB |\r\n| RAM | 32GB DDR4 3600 Mhz |\r\n| CUDA Toolkit Version | 12.2 |\r\n| GPU Driver Version | 537.13 |\r\n\r\n\r\n\r\n## Prerequisites\r\n(For linux, need GCC compiler with C++ support (gcc works better with CUDA's compiler), and GNU make)\r\n1. Latest [NVIDIA GPU driver](https://www.nvidia.com.tw/Download/index.aspx)\r\n2. *Python 3.7+ with pip available*\r\n3. *Latest CUDA toolkit installed with nvcc compiler. [(download here)](https://developer.nvidia.com/cuda-downloads)*\r\n\r\n**NOTE: [Recommended]** You can skip 2 and 3. by using [conda](https://repo.anaconda.com/archive/), see [Installation](#Installation) below\r\n\r\n## Installation\r\n### Linux / Windows [Recommended]:\r\n```bash\r\nconda install cuda -c nvidia\r\npython -m pip install --upgrade pip\r\npip install cualgo\r\n```\r\n### Windows (without conda):\r\n1. Install NVIDIA latest GPU driver by yourself\r\n2. `python -m pip install --upgrade pip && pip install cualgo`\r\n\r\n\r\n## Sample Code\r\n\r\nSupport data type of `Numpy`.\r\n```python\r\nfrom cualgo import graph as cg\r\nimport numpy as np\r\ngraph = np.array([\r\n [0 , 7 , np.inf, 8],\r\n [np.inf, 0 , 5 , np.inf],\r\n [np.inf, np.inf, 0 , 2],\r\n [np.inf, np.inf, np.inf, 0]\r\n], dtype=np.float64)\r\nprint(cg.floydwarshall(graph))\r\n# [[0.0, 7.0, 12.0, 8.0], [inf, 0.0, 5.0, 7.0], [inf, inf, 0.0, 2.0], [inf, inf, inf, 0.0]]\r\n```\r\n\r\nOr just simply pass 2D `list` in python\r\n```python\r\nfrom cualgo import graph as cg\r\nINF = 9999\r\ngraph = [\r\n [0 , 7 , INF, 8],\r\n [INF, 0 , 5 , INF],\r\n [INF, INF, 0 , 2],\r\n [INF, INF, INF, 0]\r\n]\r\nprint(cg.floydwarshall(graph))\r\n# [[0, 7, 12, 8], [9999, 0, 5, 7], [9999, 9999, 0, 2], [9999, 9999, 9999, 0]]\r\n```\r\n\r\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "A Pytnon library containing basic algorithm with GPU-accelerated computing.",
"version": "0.2.0",
"project_urls": {
"Download": "https://github.com/anderson101866/cualgo/archive/refs/tags/v0.2.0.tar.gz",
"Homepage": "https://github.com/anderson101866/cualgo"
},
"split_keywords": [
"python",
"cuda",
"gpu",
"algorithm",
"numpy"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c42fd3b25ae9b8d0a14c149224b5b06af5399b5940d6eac0ebc8605b15efa635",
"md5": "b57446bb2ce5eb9ab99e4b80557d3150",
"sha256": "aa53e41aa19fd3bef0defcd6413ad1b28ce4984541ad7e20353eabceb51c7c2c"
},
"downloads": -1,
"filename": "cualgo-0.2.0-cp310-cp310-win_amd64.whl",
"has_sig": false,
"md5_digest": "b57446bb2ce5eb9ab99e4b80557d3150",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.7",
"size": 1406339,
"upload_time": "2023-10-15T12:30:05",
"upload_time_iso_8601": "2023-10-15T12:30:05.552530Z",
"url": "https://files.pythonhosted.org/packages/c4/2f/d3b25ae9b8d0a14c149224b5b06af5399b5940d6eac0ebc8605b15efa635/cualgo-0.2.0-cp310-cp310-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "60021c390c567b2e98d379dfeabce9de1ecb3a0e3bc4fb3ec94df387c9754a66",
"md5": "71b21568fe236e6077d3547f33213061",
"sha256": "d2ed89f1e58bf1a0b83dc27e86eec3c8f6ac584bbcfd226a49cdc8fcbc6957e0"
},
"downloads": -1,
"filename": "cualgo-0.2.0-cp311-cp311-win_amd64.whl",
"has_sig": false,
"md5_digest": "71b21568fe236e6077d3547f33213061",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.7",
"size": 1407205,
"upload_time": "2023-10-15T12:30:08",
"upload_time_iso_8601": "2023-10-15T12:30:08.052987Z",
"url": "https://files.pythonhosted.org/packages/60/02/1c390c567b2e98d379dfeabce9de1ecb3a0e3bc4fb3ec94df387c9754a66/cualgo-0.2.0-cp311-cp311-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "457229e0fa5ca4f8c78a5127c3d4bda26c773e3ef7a5e87b5d68395bed9722a2",
"md5": "93f2336acbf954529dd613cfb30fced6",
"sha256": "9214e95a73b777157c7ecbb271703b62172dda61e07f5f6c170da869fe7d52f1"
},
"downloads": -1,
"filename": "cualgo-0.2.0-cp312-cp312-win_amd64.whl",
"has_sig": false,
"md5_digest": "93f2336acbf954529dd613cfb30fced6",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.7",
"size": 1406492,
"upload_time": "2023-10-15T12:30:09",
"upload_time_iso_8601": "2023-10-15T12:30:09.780570Z",
"url": "https://files.pythonhosted.org/packages/45/72/29e0fa5ca4f8c78a5127c3d4bda26c773e3ef7a5e87b5d68395bed9722a2/cualgo-0.2.0-cp312-cp312-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "0e4f7b46a385e8eee40c7944cdd56c671c20b12bc205b313caccf693b29bdacd",
"md5": "9c979fc8d68c0bf145f860ac5a56d705",
"sha256": "7a21e51013b34d2900c47b716295cf71d040fef255c501adfbfbaac521842f2c"
},
"downloads": -1,
"filename": "cualgo-0.2.0-cp37-cp37m-win_amd64.whl",
"has_sig": false,
"md5_digest": "9c979fc8d68c0bf145f860ac5a56d705",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 1406624,
"upload_time": "2023-10-15T12:30:11",
"upload_time_iso_8601": "2023-10-15T12:30:11.678741Z",
"url": "https://files.pythonhosted.org/packages/0e/4f/7b46a385e8eee40c7944cdd56c671c20b12bc205b313caccf693b29bdacd/cualgo-0.2.0-cp37-cp37m-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "a7cbbfdf18d268906492b4e926e01b3704375b62e5b1c7f227673141c68f8b73",
"md5": "d22049a1a332b8736381b4a5acf2b4e2",
"sha256": "cc2827c79099af0627d455bc5017f5969994aba9448ffdb1a3d4ee335a5aaa84"
},
"downloads": -1,
"filename": "cualgo-0.2.0-cp38-cp38-win_amd64.whl",
"has_sig": false,
"md5_digest": "d22049a1a332b8736381b4a5acf2b4e2",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.7",
"size": 1406263,
"upload_time": "2023-10-15T12:30:13",
"upload_time_iso_8601": "2023-10-15T12:30:13.905132Z",
"url": "https://files.pythonhosted.org/packages/a7/cb/bfdf18d268906492b4e926e01b3704375b62e5b1c7f227673141c68f8b73/cualgo-0.2.0-cp38-cp38-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "c3ed578a02f424bdd0c8c6bfb239f385bb99276d70021b79a4ba795aadd9db12",
"md5": "693aa95f7c4d8f35503c4b62b023469d",
"sha256": "f9274cbb798d41912b4cd7277bd4ef8cef17a72ccc202910b07df6b4934db573"
},
"downloads": -1,
"filename": "cualgo-0.2.0-cp39-cp39-win_amd64.whl",
"has_sig": false,
"md5_digest": "693aa95f7c4d8f35503c4b62b023469d",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.7",
"size": 1406344,
"upload_time": "2023-10-15T12:30:16",
"upload_time_iso_8601": "2023-10-15T12:30:16.134400Z",
"url": "https://files.pythonhosted.org/packages/c3/ed/578a02f424bdd0c8c6bfb239f385bb99276d70021b79a4ba795aadd9db12/cualgo-0.2.0-cp39-cp39-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "dce8d977970fa1ebc7a0e3b1e592edb45ec5554aae791ff4fe88ec9f814de8fb",
"md5": "284599056840f1c86cd4f6437a61cda1",
"sha256": "dc00f6742907433f0d6b97cbb891a68141422fbe2c64ff6c874ce444a196fb32"
},
"downloads": -1,
"filename": "cualgo-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "284599056840f1c86cd4f6437a61cda1",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 2441599,
"upload_time": "2023-10-15T12:30:18",
"upload_time_iso_8601": "2023-10-15T12:30:18.657578Z",
"url": "https://files.pythonhosted.org/packages/dc/e8/d977970fa1ebc7a0e3b1e592edb45ec5554aae791ff4fe88ec9f814de8fb/cualgo-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-10-15 12:30:18",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "anderson101866",
"github_project": "cualgo",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"lcname": "cualgo"
}
JSON
