Pigmnts now uses threads to achieve data parallelism in the assignment step of the K-means++ algorithm. The implementation follows the concept of MapReduce and makes use of crossbeam crate for scoped threads. The number of threads is set to a constant value of 5 in the library.
speedup achieved increases as the number of colors in palette "k" increases and stabilizes at higher values of k.
In all k > 1 cases, there is a speedup > 1 achieved.
While the number of threads, for now, is fixed to 5 in the library, further experiments can be done to find an optimal number of threads to achieve a good speedup.
Memory consumption from this change hasn't been tested extensively, but some observations have shown an increase in memory consumption.
WebAssembly?
Getting threads to get working with WebAssembly as of now is a little challenging and this experiment was majorly to test whether threads would enhance the performance in any way. Over time, these changes would be brought over to the WebAssembly library too but for now, the WebAssembly version continues to work on a single thread.
K-means and K-means++ have a lot of synchronous steps involved and parallelizing it are not very straightforward. Data parallelism here does show an improvement in the performance of the algorithm in general.
Pigmnts Library 0.7.0 :racing_car:
Crate only: Data parallelism via threads.
Conditional compilation to separate WebAssembly and Rust crate level code.
Removed usage of extern keyword from the source.
Pigmnts CLI 0.1.3 :racing_car:
Updated Pigmnts Library to 0.7.0
Brings improved performance from v0.7.0 of the library.
Update conditional_vec macro to call closure thus evaluating RHS only when LHS is truthy.
Data parallelism with threads :thread:
Pigmnts now uses threads to achieve data parallelism in the assignment step of the K-means++ algorithm. The implementation follows the concept of MapReduce and makes use of
crossbeamcrate for scoped threads. The number of threads is set to a constant value of 5 in the library.Coming to the interesting part of this change, threads have made pigmnts 1.5x - 2.5x faster than previous versions! :tada: The data from the tests can be found here https://docs.google.com/spreadsheets/d/1SJWTBTX9OjOPI9zdSc1T-hGUIiIv9osia1WB936vp8k/edit
Conclusions from the tests
k > 1cases, there is aspeedup > 1achieved.WebAssembly?
Getting threads to get working with WebAssembly as of now is a little challenging and this experiment was majorly to test whether threads would enhance the performance in any way. Over time, these changes would be brought over to the WebAssembly library too but for now, the WebAssembly version continues to work on a single thread.
K-means and K-means++ have a lot of synchronous steps involved and parallelizing it are not very straightforward. Data parallelism here does show an improvement in the performance of the algorithm in general.
Pigmnts Library 0.7.0 :racing_car:
externkeyword from the source.Pigmnts CLI 0.1.3 :racing_car:
conditional_vecmacro to call closure thus evaluating RHS only when LHS is truthy.externkeyword from the source.