CSI-380: Innov III; Emerging Languages
This project is an implementation for the KNN (K nearest neighbors) algorithm in Rust using the CIFAR-10 dataset. We are comparing a single threaded sequentially run baseline with two parallel implementations of choice. The first parallel implementation is with std::thread partitioning and the second parallel implementation of choice is Rayon data-parallel iterators. The way that performance is monitored and evaluated is through classification accuracy, wall-clock execution time, parallel speedup as well as thread efficiency. This will be tested across two different machines in order to note any differences that may occur.
Algorithm: K Nearest Neighbors (KNN)
Dataset: CIFAR-10 (50k training images and 10k test images [32x32 RGB, 10 classes])
Evaluation metrics: Classification accuracy, execution time (ms), parallel speedup, thread efficiency
Benchmarks were run on two machines:
| System 1 | System 2 | |
|---|---|---|
| Owner | Adrian Bassir | Matthew Kane |
| CPU | Intel Core Ultra 7 255U | Intel Core i7-12700H |
| Physical cores | 12 | 14 |
| RAM | 32 GB DDR5-7600 | 32 GB DDR5-4800 |
| OS | Windows 11 Home | Windows 11 Home |
- Rust toolchain (rustc 1.75.0 or later)
- 16GB RAM recommended (more is fine too)
- 4 or more physical CPU cores (this is for meaningful speedup)
- External crates (managed by cargo): rayon, indicatif, criterion
Note: This project runs entirely on the CPU so no GPU is required
-
Make sure you are in the correct project directory. "cd ImageProcessing" will get you there.
-
Download the CIFAR-10 dataset from the official website. This repository will not include the dataset. Here is the official website: https://www.cs.toronto.edu/~kriz/cifar.html. From the website, go ahead and download the binary version (for C programs). It should download "cifar-10-binary.tar.gz". This will need to be extracted.
-
Once extracted, place the extracted CIFAR-10 folder into the data folder so it looks like "data/cifar-10-batches-bin/(bin files)
-
Run build command: "cargo build --release"
-
Run the program: "cargo run --release" (this will run the entire dataset with k=5)
-
Run tests: "cargo test"
-
Run criterion benchmarks: "cargo bench"
| Implementation | Accuracy |
|---|---|
| Sequential | 35.69% |
| Threaded-4 | 35.69% |
| Rayon | 35.69% |
| Configuration | Threads | Time (ms) | Speedup | Efficiency |
|---|---|---|---|---|
| sequential | 1 | 112122 | 1.000 | 1.000 |
| threaded-1 | 1 | 100645 | 1.114 | 1.114 |
| threaded-2 | 2 | 58695 | 1.910 | 0.955 |
| threaded-4 | 4 | 39209 | 2.860 | 0.715 |
| threaded-8 | 8 | 29311 | 3.825 | 0.478 |
| rayon | 14 | 27762 | 4.039 | 0.288 |
| Configuration | Threads | Time (ms) | Speedup | Efficiency |
|---|---|---|---|---|
| sequential | 1 | 102893 | 1.000 | 1.000 |
| threaded-1 | 1 | 105840 | 0.972 | 0.972 |
| threaded-2 | 2 | 58643 | 1.755 | 0.877 |
| threaded-4 | 4 | 39092 | 2.632 | 0.658 |
| threaded-8 | 8 | 23210 | 4.433 | 0.554 |
| rayon | 20 | 23510 | 4.376 | 0.219 |
On system 1 (Adrian Bassir), speedup increases as more threads are added to the equation, however, this does not scale linearly as doubling threads does not double the speedup since efficiency does go down as more cores are added. This can be noticed as efficiency drops quite noticeably as we get into the higher core range going down to less than 0.5 of what we saw for a sequential run (as of threaded-8), an indicator that around half of CPU time is effectively wasted. Rayon shows an efficiency in the high 0.2 range which is an interesting result (marginally better than threaded-8 but also uses 14 threads instead of 8). This shows that returns significantly diminish past 8 cores. On system 2 (Matthew Kane), stronger absolute speedup is achieved at 8 threads (4.443x on system 2 vs only 3.825x on system 1). In this run, threaded-8 and rayon run nearly twice as fast in wall-clock time (about 23 seconds versus about 27 to 29 seconds). Both systems show that rayon uses far more threads than the threaded implementations (8 vs 14/20) but have nearly an identical wall-clock time. In the case of the second systems, more threads seems to be slower than the threaded-8 time. Both machines have similar efficiency curves which is an expected result as more cores should have an efficiency drop off.
- Krizhevsky, A. (2009). Learning Multiple Layers of Features from Tiny Images. University of Toronto. CIFAR-10 dataset available at: https://www.cs.toronto.edu/~kriz/cifar.html
- The Rayon crate documentation: https://docs.rs/rayon
- Rust
std::threaddocumentation: https://doc.rust-lang.org/std/thread/