Hardware synthesis of weakly consistent C concurrency

File Description SizeFormat 
NadeshFPGA17.pdfFile embargoed until 01 January 10000620.38 kBAdobe PDF    Request a copy
Title: Hardware synthesis of weakly consistent C concurrency
Authors: Ramanathan, N
Fleming, S
Wickerson, J
Constantinides, GA
Item Type: Conference Paper
Abstract: Lock-free algorithms, in which threads synchronise not via coarse-grained mutual exclusion but via ne-grained atomic operations (`atomics'), have been shown empirically to be the fastest class of multi-threaded algorithms in the realm of conventional processors. This paper explores how these algorithms can be compiled from C to recon gurable hard- ware via high-level synthesis (HLS). We focus on the scheduling problem, in which software instructions are assigned to hardware clock cycles. We rst show that typical HLS scheduling constraints are insu cient to implement atomics, because they permit some instruction reorderings that, though sound in a single-threaded con- text, demonstrably cause erroneous results when synthesis- ing multi-threaded programs. We then show that correct be- haviour can be restored by imposing additional intra-thread constraints among the memory operations. We implement our approach in the open-source LegUp HLS framework, and provide both sequentially consistent (SC) and weakly consis- tent (`weak') atomics. Weak atomics necessitate fewer con- straints than SC atomics, but su ce for many concurrent al- gorithms. We con rm, via automatic model-checking, that we correctly implement the semantics de ned by the 2011 revision of the C standard. A case study on a circular bu er suggests that circuits synthesised from programs that use atomics can be 2.5x faster than those that use locks, and that weak atomics can yield a further 1.5x speedup.
Issue Date: 22-Feb-2017
Date of Acceptance: 20-Nov-2016
URI: http://hdl.handle.net/10044/1/43491
Publisher: ACM
Copyright Statement: This paper is embargoed until publication.
Sponsor/Funder: Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Royal Academy Of Engineering
Imagination Technologies Ltd
Funder's Grant Number: EP/I020357/1
11908 (EP/K034448/1)
Prof Constantinides Chair
Prof Constantinides Chair
Conference Name: ACM International Symposium on FPGAs 2017
Publication Status: Accepted
Start Date: 2017-02-22
Finish Date: 2017-02-24
Conference Place: Monterey, CA
Embargo Date: publication subject to indefinite embargo
Appears in Collections:Faculty of Engineering
Electrical and Electronic Engineering

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Creative Commonsx