RANGE-BLOCKS: A Synchronization Facility for Domain-Specific Architectures

Current domain-specific architectures (DSAs) work predominantly with static data structures and find it challenging to insert or remove data (they only support in-place updates). However, as DSAs target real-world applications, it is neces- sary to support mutable and dynamically resizable data structures. DSAs cannot support dynamic data structures since they lack a synchronization facility. DSAs are forced to either use address-based atomics or batch updates on the host. Unfortunately, both approaches introduce prohibitive performance penalties and require large caches for the locks. Range-blocks (RBlox) develops a hardware synchronization facility for DSAs to support dynamic data structures. Our idea is to use key ranges to capture synchronization boundaries and tap into the inherent parallelism of the data-structure layout. We make two novel observations that enable a practical hardware implementation: i) Range locks are symbolic and can compactly represent mutexes on multiple nested objects. Thus, any operation requires fewer range locks, and a small on-chip table suffices (2kb) compared to large caches (256kb) for address-based locks [79, 81]. ii) Ranges also explicitly represent the region of interest, and we can instantly achieve mutual exclusion (instead of relying on ordering). On a 128-tile dataflow DSA, we improve performance by 15×, reduce DRAM bandwidth by 4×, save 70% of on-chip traffic, and require 6.6% of on-chip energy.