Concurrency-aware thread scheduling for high-level synthesis
File(s)
Accepted version
Author(s)
Ramanathan, Nadesh
Constantinides, George
Wickerson, JP
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.
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.
Date Acceptance
2018-03-05
Sponsor
Imperial College London
Engineering and Physical Sciences Research Council
Engineering & Physical Science Research Council (E
Grant Number
Imperial College London
EP/K034448/1
11908 (EP/K034448/1)
Source
IEEE Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)
Subjects
Science & Technology
Technology
Computer Science, Hardware & Architecture
Computer Science, Theory & Methods
Engineering, Electrical & Electronic
Computer Science
Engineering
Publication Status
Accepted
Start Date
2018-04-29
Finish Date
2018-05-01
Coverage Spatial
Boulder, CO, USA