Global Analysis of C Concurrency in High-Level Synthesis
Global Analysis of C Concurrency in High-Level Synthesis
复制标题
DOI：
10.1109/tvlsi.2020.3026112
复制
发表时间：
2020-10
影响因子：
2.8
通讯作者：
Nadesh Ramanathan;G. Constantinides;John Wickerson
中科院分区：
文献类型：
--
作者：
Nadesh Ramanathan;G. Constantinides;John Wickerson
在将C程序映射到硬件时，高级综合（high-level synthesis， HLS）工具会对独立指令重新排序，目的是获得一个需要尽可能少的时钟周期的调度。然而，在合成多线程C程序时，重新排序的机会受到原子操作（“原子”）的限制，原子操作是C中的基本并发原语。现有的HLS工具孤立地分析和调度每个线程。在本文中，我们认为线程局部分析是保守的，特别是因为HLS编译器可以访问整个程序。因此，我们建议在调度每个线程时利用所有线程的内存访问信息进行全局分析。在LegUp HLS工具中实现，我们的分析对顺序一致性（SC）和弱原子敏感，并支持循环流水线。由于C原子的语义很复杂，我们使用Alloy模型检查器正式验证我们的分析是否正确地实现了C内存模型。与线程本地分析相比，我们的全局分析在一组无锁数据结构和数据流模式上实现了平均2.3倍的加速。我们还将我们的分析应用于一个更大的应用程序：b谷歌的PageRank的无锁、流化和负载均衡实现，与线程本地分析相比，我们看到了1.3倍的平均加速。
When mapping C programs to hardware, high-level synthesis (HLS) tools reorder independent instructions, aiming to obtain a schedule that requires as few clock cycles as possible. However, when synthesizing multithreaded C programs, reordering opportunities are limited by the presence of atomic operations (“atomics”), the fundamental concurrency primitives in C. Existing HLS tools analyze and schedule each thread in isolation. In this article, we argue that thread-local analysis is conservative, especially since HLS compilers have access to the entire program. Hence, we propose a global analysis that exploits information about memory accesses by all threads when scheduling each thread. Implemented in the LegUp HLS tool, our analysis is sensitive to sequentially consistent (SC) and weak atomics and supports loop pipelining. Since the semantics of C atomics is complicated, we formally verify that our analysis correctly implements the C memory model using the Alloy model checker. Compared with thread-local analysis, our global analysis achieves a $2.3\times $ average speedup on a set of lock-free data structures and data-flow patterns. We also apply our analysis to a larger application: a lock-free, streamed, and load-balanced implementation of Google’s PageRank, where we see a $1.3\times $ average speedup compared with the thread-local analysis.