Concurrency-aware thread scheduling for high-level synthesis

File Description SizeFormat 
cats_FCCM18.pdfFile embargoed until 01 January 10000249.93 kBAdobe PDF    Request a copy
Title: Concurrency-aware thread scheduling for high-level synthesis
Authors: Ramanathan, N
Constantinides, G
Wickerson, JP
Item Type: Conference Paper
Abstract: When mapping C programs to hardware, high-level synthesis (HLS) tools seek to reorder instructions so they can be packed into as few clock cycles as possible. However, when synthesising multi-threaded C, instruction reordering is inhibited by the presence of atomic operations (‘atomics’), such as compare- and-swap. Atomics, the fundamental concurrency primitive in C, are the basis of more abstract concurrency mechanisms such as locks, and also of efficient lock-free data structures. Whether a particular atomic can be legally reordered within a thread can depend on the memory access patterns of other threads. Existing HLS tools that support atomics typically sched- ule each thread independently, and so must be conservative when optimising around atomics. Yet HLS tools are distinguished from conventional compilers by having the entire program available. Can this information be exploited to allow more reorderings within each thread, and hence to obtain more efficient schedules? In this work, we propose a global analysis that determines, for each thread, which pairs of instructions must not be reordered. Our analysis is sensitive to the C consistency mode of the atomics involved (e.g. relaxed, release, acquire, and sequentially- consistent). We have used the Alloy model checker to validate our analysis against the C language standard, and have implemented it in the LegUp HLS tool. An evaluation on several lock-free data structure benchmarks indicates that our analysis leads to a 1.6 × average global speedup.
Issue Date: 29-Apr-2018
Date of Acceptance: 5-Mar-2018
URI: http://hdl.handle.net/10044/1/58385
Copyright Statement: This paper is embargoed until publication.
Sponsor/Funder: Engineering & Physical Science Research Council (E
Imperial College London
Engineering and Physical Sciences Research Council
Funder's Grant Number: 11908 (EP/K034448/1)
Imperial College London
EP/K034448/1
Conference Name: IEEE Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)
Publication Status: Accepted
Start Date: 2018-04-29
Finish Date: 2018-05-01
Conference Place: Boulder, CO, USA
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 Commons