Hardware Synthesis of Weakly Consistent C Concurrency
Hardware Synthesis of Weakly Consistent C Concurrency
复制标题
弱一致性C并发的硬件综合
DOI：
10.1145/3020078.3021733
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ramanathan N
中科院分区：
文献类型：
--
作者：
Ramanathan N
无锁算法，其中线程同步不是通过粗粒度的互斥，而是通过细粒度的原子操作（“原子”），已被经验证明是最快的一类多线程算法在传统的处理器领域。本文探讨了如何将这些算法从C编译到可重构硬件通过高级综合（HLS）。我们专注于调度问题，其中软件指令分配给硬件时钟周期。我们首先表明，典型的HLS调度约束是不足以实现原子，因为它们允许一些指令重新排序，虽然在单线程的情况下，声音，合成多线程程序时，显然会导致错误的结果。然后，我们表明，正确的行为可以恢复施加额外的线程内的内存操作之间的约束。我们实现我们的方法在开源的LegUp HLS框架，并提供顺序一致（SC）和弱一致（“弱”）原子。弱原子比SC原子需要更少的约束，但足以满足许多并发算法。我们通过自动模型检查确认，我们正确地实现了C标准2011年修订版定义的语义。循环缓冲区的一个案例研究表明，使用原子的程序合成的电路可以比使用锁的程序快2.5倍，弱原子可以产生进一步的1.5倍加速。
Lock-free algorithms, in which threads synchronise not via coarse-grained mutual exclusion but via fine-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 reconfigurable hardware via high-level synthesis (HLS). We focus on the scheduling problem, in which software instructions are assigned to hardware clock cycles. We first show that typical HLS scheduling constraints are insufficient to implement atomics, because they permit some instruction reorderings that, though sound in a single-threaded context, demonstrably cause erroneous results when synthesising multi-threaded programs. We then show that correct behaviour 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 consistent ('weak') atomics. Weak atomics necessitate fewer constraints than SC atomics, but suffice for many concurrent algorithms. We confirm, via automatic model-checking, that we correctly implement the semantics defined by the 2011 revision of the C standard. A case study on a circular buffer 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.
登录
查看更多内容
从 OpenMP 程序生成硬件
DOI：
--
发表时间：
2006
期刊：
2006 IEEE International Conference on Field Programmable Technology
影响因子：
--
作者：
Y. Y. Leow;C. Ng;W. Wong
通讯作者：
W. Wong
用于比较内存一致性模型的 Litmus 测试：它们需要多长时间？
DOI：
--
发表时间：
2011
期刊：
Design Automation Conference
影响因子：
--
作者：
Sela Mador;R. Alur;Milo M. K. Martin
通讯作者：
Milo M. K. Martin
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
Mike Dodds;Mark Batty;Alexey Gotsman;Mark
通讯作者：
Mark
基于 OpenMP 的高效且可扩展的系统级设计
DOI：
--
发表时间：
2013
期刊：
Design, Automation and Test in Europe
影响因子：
--
作者：
A. Cilardo;L. Gallo;A. Mazzeo;N. Mazzocca
通讯作者：
N. Mazzocca
编译器优化对 FPGA 高级综合的影响
DOI：
--
发表时间：
2013
期刊：
2013 IEEE 21st Annual International Symposium on Field-Programmable Custom Computing Machines
影响因子：
--
作者：
Qijing Huang;Ruolong Lian;Andrew Canis;Jongsok Choi;R. Xi;S. Brown;J. Anderson
通讯作者：
J. Anderson