A Case for Work-stealing on FPGAs with OpenCL Atomics
Authors:
Open Access
- 21 February 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 48-53
Abstract
We provide a case study of work-stealing, a popular method for run-time load balancing, on FPGAs. Following the Cederman-Tsigas implementation for GPUs, we synchronize work-items not with locks, mutexes or critical sections, but instead with the atomic operations provided by Altera's OpenCL SDK. We evaluate work-stealing for FPGAs by synthesizing a K-means clustering algorithm on an Altera P385 D5 board, both with work-stealing and with a statically-partitioned load. When block RAM utilization is maximised in both cases, we find that work-stealing leads to a 1.5x speedup. This demonstrates that the ability to do load balancing at run-time can outweigh the drawback of using `expensive' atomics on FPGAs. We hope that our case study will stimulate further research into the high-level synthesis of fine-grained, lock-free, concurrent programs.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/L016796/1, EP/I020357/1, EP/K015168/1)
This publication has 16 references indexed in Scilit:
- Heterogeneous work-stealing across CPU and DSP cores2015
- Optimised OpenCL workgroup synthesis for hybrid ARM-FPGA devices2015
- A study of data partitioning on OpenCL-based FPGAs2015
- Automatic support for multi-module parallelism from computational patterns2015
- More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms2015
- An FPGA implementation of wait-free data synchronization protocols2013
- Towards a Universal FPGA Matrix-Vector Multiplication Architecture2012
- Dynamic Load Balancing Using Work-Stealing2012
- An efficient k-means clustering algorithm: analysis and implementationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- Thread scheduling for multiprogrammed multiprocessors1998