SPARTA: High-Level Synthesis of Parallel Multi-Threaded Accelerators

HLS is an established paradigm and an active area of research [16]; significant effort is dedicated to improving the QoR of generated accelerators, supporting flexible optimization and design space exploration, and introducing more and more system-level design features [9, 46, 50, 57]. Another important research topic is the synthesis of parallel accelerator designs starting from specifications written in user-friendly parallel programming application interfaces (APIs) such as OpenCL, CUDA, OpenMP, or Pthread.

Hardware vendors lead OpenCL efforts [32], but they mainly target data-parallel workloads with regular computation and often require significant restructuring of the code to match one of the supported parallel patterns. FCUDA [43] starts from kernels written using the CUDA API, designed targeting NVIDIA GPUs, and presents similar issues. The LegUP HLS tool [10] exploits OpenMP and Pthread specifications to generate architectures built of custom accelerators driven by a general-purpose microcontroller, only supporting two levels of nested parallelism (the external level through Pthread and the internal one through OpenMP) [15]. BŁYSK [47] extracts OpenMP tasks and maps them onto parallel accelerators that can share resources, also leveraging a microcontroller to perform the actual task scheduling. The CHAT methodology [24] extends the ROCCC HLS tool [54] to generate temporally multithreaded accelerators starting from loop constructs described in C without any support for synchronization. The Nymble HLS compiler supports multiple execution contexts [27] in spatially and temporally multithreaded accelerators generated from OpenMP loops [51]; the accelerators, however, can only access private memory and thus cannot share data across threads nor synchronize.

Svelto [39] is the synthesis methodology nearest to SPARTA: it synthesizes spatially and temporally multithreaded accelerators starting from OpenMP code, parallel cores access a shared memory through a multi-ported memory controller, and it supports synchronization through atomic memory operations. The main limitation of Svelto is that it can only map a small subset of OpenMP constructs to an architectural template, limiting the set of supported OpenMP pragmas (e.g., atomic memory operations are supported, but critical sections and barrier synchronization are not). Moreover, supported parallel constructs become kernel functions that do not allow inter-functional optimizations, local memories within each parallel core are not supported, and the multi-ported memory controller in the template has limited scalability.

Table 1 summarizes the considerations done in this section to highlight the differences between SPARTA and previous works. Looking at the supported input languages, we tried to identify how much a user would have to modify an input software implementation to use a certain tool: for example, FCUDA requires to heavily reorganize the code into data management and compute sections, Svelto requires the body of the OpenMP for loop to be outlined in a separate function, and SPARTA can process standard, unmodified OpenMP code. Methodologies that target a host+FPGA system use the processor to coordinate the execution of the accelerators, while SPARTA implements scheduling and synchronization within the accelerator itself. Finally, SPARTA supports different work-sharing and synchronization constructs, and nested parallelism; the addition of new constructs is simplified by using the low-level primitives of the OpenMP runtime.

Graph processing is an important element of data analytics, and it presents unique challenges (large datasets, unpredictable fine-grained memory accesses, unbalanced task-level parallelism) that are not well addressed by commodity processors relying on advanced cache architectures, data locality, and regular computation patterns, and might thus benefit from domain-specific accelerators [22].

Alongside proposals for processing-in-memory [3], flash-based [29], ASIC [25], and ReRAM-based [52] accelerators, multiple designs have targeted FPGAs to implement graph processing primitives. The FPGA co-processors on the hybrid Convey HC systems have been used to accelerate breadth-first search (BFS) [8], while [58] exploits an FPGA-Hybrid Memory Cube platform. Optimized implementations of PageRank (PR) and random walk are proposed in [59] and [20], respectively. GraphOps [45] provides a series of building blocks to implement graph analytics applications following a dataflow approach. Several designs are based on arrays of parallel processing engines [8, 13, 55]; some of them support the implementation of vertex-centric [44] or edge-centric [60, 61] graph algorithms. ScalaGraph [56] proposes a tile-based architecture that improves the scalability of the system as the number of processing elements increases. GraphLily [26] supports graph algorithms by accelerating their linear algebra formulation (i.e., by implementing custom Sparse-Matrix-Vector and Sparse-Matrix-Matrix multiplications units) and [2] provides a template for a GAS accelerator, requiring users to rewrite their applications and pre-partition the data.

All these works propose fixed or templated designs available as register-transfer level components, manually developed either with HDL or through HLS. Specializing the HLS process for the acceleration of graphs is not considered, thus similar approaches can only provide a limited library of primitives, and input applications may need to be restructured to allow mapping the computation onto the accelerators.

ElasticFlow [53] extends HLS with a methodology for the synthesis of irregular loop nests into a pipelined architecture. The approach is thus well suited to graph kernels that often feature irregular memory accesses and imbalanced computation; however, it only uses small on-chip memories to store the graphs, and it does not support atomic memory operations, relying on a reorder buffer to provide consistency. Castellana et al. [11] start from OpenMP-annotated nested loops to synthesize graph database queries expressed as graph pattern matching routines. The methodology leverages a distributed controller to map loop iterations onto a parallel array of accelerators, and it was later extended with dynamic scheduling [40]. All these solutions exploit task parallelism only by replicating the accelerator datapaths with limited resource reuse. The aforementioned Svelto [39] methodology has been designed to support the synthesis of irregular parallel applications, in particular graph kernels and graph database queries.

The unique features of graph applications require architectural innovations to allow efficient execution under latency, throughput, or power consumption constraints. Particular care must be dedicated to the design of memory hierarchies [5] and to the interconnections between memory and computational elements, as graphs are large data structures that cannot be easily partitioned in a way that balances the work for each partition and require fine-grained, unpredictable, data accesses with poor spatial and temporal locality.

In SPARTA, we use a unidirectional, bufferless, deflection-routed NoC to connect the different parallel components. The idea of bufferless deflection-routed NoCs (BLESS) was proposed in [41] to reduce energy consumption and chip area by eliminating the need for routing or flow control buffers. While the deflection-based routing lowers the area and energy costs of the NoC, it might increase latency under high injection rates; however, SPARTA accelerator cores can tolerate a higher data access latency through asynchronous memory operations and CS. SPARTA uses a butterfly topology [18], where the last stage is connected to the first one (see also Figure 6 later). While adopting a different topology, the bufferless, deflection-based approach of SPARTA’s NoC is also similar to the one used in the Data Vortex network [34]. The Data Vortex network was originally devised for optical network interconnects due to its bufferless nature and was later implemented as a conventional network interconnect for high-performance computing systems. Its ability to support high injection rates of fine-grained transactions (memory word size) makes it effective for irregular applications [21]. The design has been later proposed as an intellectual property for a NoC [28], validated on FPGAs. Hoplite [30] is another noteworthy example of bufferless deflection routing NoC. Hoplite uses a torus topology with a very simple node switch implementation. The implementation of Hoplite’s node switch is similar to SPARTA’s one. However, SPARTA’s topology allows logarithmic hop counts. Kapre and Gray [31] thoroughly examine the cost of Hoplite’s switches, showing that the deflection routing algorithm can reach high clock frequencies while utilizing a minimal amount of resources of the FPGA fabric. Malik and Kapre [37] discuss an enhanced version of Hoplite with a butterfly topology; in the setup of this article, the parallel components are connected on the lower level of the network, while SPARTA can inject/receive requests through any of the network switches.

SPARTA generates a modular architecture following the content of the input OpenMP specification that can be customized through user-defined parameters. The main components are depicted in Figure 3: sequential parts of the computation go through the standard HLS flow, while parallel constructs are translated into a set of parallel processing units called cores. Each core contains a finite state machine with datapath (FSMD) implementing the computation described within an OpenMP parallel region (e.g., the loop body in an omp parallel for loop), a CS manager in case multiple threads are assigned to the same core, and local memory for data belonging to those threads. The number of cores and the number of threads (contexts) assigned to each core are configurable. The parallel region of the accelerator can also contain synchronization components, arbiters, and data shared among threads if needed. The accelerator is connected to a NoC that relays messages to an external memory (with support for multi-banked or pipelined memories); the number of channels between the accelerator and the NoC, as well as between the NoC and the external memory, is configurable. The user encodes information about parallelism, work-sharing policies, and synchronization requirements through the OpenMP annotations in the code and configures the rest of the architecture through command-line options.

Three synchronization modules represent a key component of the SPARTA architecture: the barrier manager, the reduction manager, and the critical manager. They are only included in the parallel region if they are needed, and their size is proportional to the number of cores that use them.

Barriers are added by the OpenMP runtime at the end of a parallel region to ensure that the execution can proceed safely if the threads have different execution times. In the OpenMP paradigm, when a thread encounters a barrier, it notifies all other threads in the same team that it has reached the barrier and waits until all other threads also signal that they have reached the end of their execution. To implement barrier synchronization, the SPARTA architecture includes local components for each core that generate completion signals and a centralized barrier manager that collects completion signals, updates a synchronization register, and, when all required threads have reached the barrier, sends them a command to resume execution. Sharing a unique barrier manager among all parallel cores ensures that synchronization happens safely without the possibility of race conditions. Furthermore, the same barrier manager component can also be used to implement the wait_thread OpenMP operation, which waits for the completion of one specific thread without adding more logic or duplicating the synchronization state.

In OpenMP reduction operations, the thread with ID 0 needs to retrieve partial reduction variables from all other threads and combine them. Each thread on a SPARTA core participating in a reduction communicates with the reduction manager to indicate the address of its reduction variable in its local memory; thread 0 then accesses the reduction manager to retrieve the addresses of all partial results it needs to merge. In fact, as will be explained in Section 3.3, a thread can access the local memory of another thread if it knows the correct address. Such a scheme could have also been implemented by storing the addresses of partial reductions in the external shared memory but with the considerable latency overhead of additional memory requests. Instead, the SPARTA reduction manager implemented inside the accelerator allows one-cycle access to the information required to perform the reduction.

We chose to implement the reduction following a linear pattern: after thread 0 finishes its part of the computation, it collects all the values computed by the others and merges the results. Other reduction schemes may result in a different tradeoff between area occupation and speed. For example, using more threads to merge the results is possible at the cost of duplicating more logic. However, a linear reduction operation often requires five or six cycles per thread to be merged, which is negligible when confronted with the duration of the computations. For this reason, when multiple contexts can be activated, the policy of the CS manager is to choose the thread with the lower thread ID: this gives priority to thread 0, which is the one that could perform a reduction operation, and then to the other threads in order since the reduction proceeds following the thread IDs.

In the OpenMP paradigm, the critical pragma is used to identify a set of instructions that can only be executed by a single thread at once. SPARTA adds a critical manager that behaves like a mutex and a local component for each thread that encounters the critical section. When a thread reaches the critical section, the local component sends a signal to request control of the lock, and the critical manager grants it only if it is not currently assigned to another thread. If the lock is not acquired by the current thread, the CS manager performs a CS. The critical manager stores the state of the requests and the current lock owner and, like the CS manager, prioritizes the thread with a lower ID when multiple threads require access. When the thread finishes the execution of the critical section, it sends a signal to release the acquired lock to avoid deadlock and allow other threads to resume their execution.

SPARTA exploits a hierarchical memory model that allows reducing the number of requests to the external memory and keeping data inside the accelerator as much as possible. There are three possibilities to store variables, visible in Figure 3: external memory outside the accelerator (high-latency memory), block RAM (BRAM) modules in the FPGA fabric inside the accelerator that are accessible by all cores, and private BRAM modules inside parallel cores. External memory is usually suitable for input and output parameters that cannot fit into on-chip BRAMs, while variables that are defined and used during the computation are better allocated inside the accelerator, whether in shared or private memory blocks, to lower access latency and improve performance.

The various levels of the memory hierarchy are connected through an ad hoc bus infrastructure, depicted in Figure 4, that can handle multiple concurrent memory requests. The local bus has one channel and connects cores within the same parallel region, while the main accelerator bus connects parallel regions with the on-chip shared memory and with the NoC toward the external memory. Each memory request originating from one of the parallel cores goes through a filter; the filter interprets its address and properly routes the request to internal BRAMs of other cores through the local bus or outside the parallel region through the main bus. Since BRAMs have two channels, local memories can support concurrent access from both the owner core and the local bus. SPARTA can connect the computation units directly to the local memory without using the local bus if it can infer at compile time the address of the requests and the variable is allocated inside the same core.

SPARTA memory addresses encode the physical location of the memory module where data is allocated; Figure 5 shows the structure of external and internal memory addresses, which have the same length because they travel on the same local bus. The size of the address depends on the external memory size (which is likely considerably larger than internal memory) plus one bit that is added to differentiate between internal and external addresses. This allows a very simple decoding logic: if the external bit is equal to 1, the request is propagated to the external memory. For internal memory, a dedicated pagination algorithm allocates each memory variable considering the parallel region and thread it belongs to. The address of internal variables is composed of three parts, representing the address of the variable in the memory module, the thread that owns the variable, and the parallel region in which the memory module is allocated, respectively. To build the address, SPARTA first finds the largest internal memory module and computes the number of bits needed to represent it, so this number of bits can be reserved to univocally identify a variable inside each memory module. Similarly, the size of the second part of the address is set by looking at the largest number of threads assigned to the different parallel regions. Finally, a unique code is assigned to each parallel region, which is used by the filters to determine whether an address is local to the parallel region. Looking at the appropriate bits of the address, filters and arbiters in the memory interconnection system can properly forward a memory request to a different bus or component using combinatorial logic without adding delays to the requests. For example, if the parallel region ID in an address matches the one stored in the filter, the request is forwarded to the local bus, where the arbiter will find the correct core by looking at the thread ID. Instead, if the parallel region ID does not match or if the address has the external bit set to one, the request is sent to the main bus.

If two requests arrive in the same cycle, the bus arbiter can only accept one of them, and the other must be stalled; in this case, SPARTA generates a back pressure signal between arbiters and cores to resend requests that could not be accepted in the current cycle. With only one context in execution on the core, execution has to be stalled as it needs the result of the memory operation to proceed, but when multiple contexts are assigned to the same core, another context can be executed in the meantime. A First-In-First-Out (FIFO) queue holds requests before the memory filter so that the CS manager can switch the running context at the start of each memory request instead of when an arbiter accepts it; this prevents the effects of the arbitration from having repercussions on the core execution, as the FIFO is responsible for resending the requests to the arbiter while the core can continue its operation with another context.

The parallel accelerator generated by SPARTA is connected to an external memory module with a fixed number of memory channels. Thus, memory requests need arbitration as they can originate from multiple sources (i.e., the parallel cores) and be directed to multiple destinations. Instead of using dedicated hardware modules or another arbiter, we introduced a custom NoC interconnect that allows maintaining a short clock period. The NoC interconnect is composed of two unidirectional NoC components (Figure 6), one for the request from the cores to the memory and the other for the opposite path.

The proposed NoC consists of a group of interconnected nodes following a butterfly structure, organized in \(n\) levels where each level has a number of nodes equal to \(2^{n}\), for a total number of nodes equal to \(n*2^{n}\). The number of nodes in the NoC must be at least equal to the maximum between the number of banks in the external memory and the number of cores in the parallel region (destination and source of the NoC, respectively). Each node in the NoC can be configured to be registered or combinatorial, providing a tradeoff between the frequency of the NoC and the number of cycles needed to traverse it: in fact, combinatorial nodes produce output values in the same cycle, increasing the critical path, while registered nodes introduce a delay. Nodes connected to external components are called I/O nodes and must be registered to avoid latches; for the rest of the nodes, the choice to use combinatorial nodes or have only registered ones is left to the user.

The number of cycles needed to traverse the NoC is equal to the number of registered nodes on the path of the request and, at most, is equal to the number of levels. To minimize the average travel time inside the NoC, SPARTA organises the registered nodes filling entire levels before going to the next one. For example, consider a NoC connecting 16 memory banks to 16 parallel cores: the number of levels must be 3 (as \(2*2^{2}=8 {\lt} 16\)), but if we choose to use combinatorial nodes, it can be traversed in 2 cycles as only the 16 I/O nodes must be registered and they can be arranged in the first two levels. The NoC is resilient to congestion: if two requests want to go to the same node, there is no need to stall, as the node can redirect one of them on another route to the same destination. The NoC can thus accept multiple requests: each node has two internal inputs and two internal output connections, and an I/O node can take a request if one of its internal inputs is not active in the current cycle. Registered nodes can also store a request, while combinatorial nodes forward them immediately and do not store information. If both input internal connections are active, the I/O node of the NoC sends a back pressure signal to resend the request in the next cycle. When using multiple contexts, back pressure signals do not interfere with the execution of the cores as they are intercepted in the FIFO modules, which take the role of resending the requests, as described in Section 3.3.

The SPARTA architecture allows the accelerator to connect to different types of external memory, with simple or pipelined memory access, and for both unified and banked multi-channel memories. The accelerator does not assume that the memory is immediately ready to accept a request and uses a protocol with back pressure that can be used to synchronize with it. Furthermore, SPARTA cores work under the assumption that answers from the memory could come out of order, as traffic in the NoC or the external memory could change the relative order of requests. Each request is tagged with an ID used to identify the thread that performed it and correctly forward the answer. If the external memory is banked, it is possible to add one cache in front of each bank to further reduce the average latency of the memory accesses. (There is no need to introduce a cache consistency mechanism, as each cache has its own set of addresses associated with a different memory bank.)

We introduced a set of custom pragmas and parameters to specify information about the accelerator interfaces for variables that will be stored in external memory and model their behaviour during the simulation of the generated accelerator (Table 3). Specific variables can be allocated to specific banks to mimic access patterns of real memories. For example, #pragma HLS\(\_\)interface a banked bank\(\_\)number = 16 bank\(\_\)chunk = 256 specifies that the a variable needs to be stored in a multi-banked external memory that has 16 banks of 256 bytes each.

SPARTA accelerators, by default, exchange data with other accelerators and the external memory using a simple and efficient protocol called minimal memory interface, described in Table 2. The protocol requires a limited number of signals and logic elements to perform memory operations, reducing the size of internal components (particularly the NoC). However, SPARTA also supports more complex protocols such as AXI4 [4] by adding a bridge component before each memory bank that translates each request and response from the minimal protocol to AXI4. The translation is completely transparent to the accelerator, correctly propagating back pressure signals from and to the external memory.

We describe here two key transformations of the SPARTA methodology that reduce the impact of parallelization on resource utilization: thread ID propagation and parallel API pointer promotion.

Thread ID propagation. SPARTA generates an array of cores by replicating the datapaths of omp\(\_\)outlined functions corresponding to the content of an OpenMP parallel region. While simply replicating the whole datapath provides a functional design, considering which parts are effectively used at runtime can reduce resource utilization. Because thread IDs are statically assigned to each core, our approach can use them to determine the resources of the datapath that each thread actually uses. In fact, in the OpenMP work-sharing model, it is possible to differentiate the computation assigned to threads in the same group, but only depending on the thread ID. Bambu features several code analyses and transformations that SPARTA can exploit to statically propagate thread IDs through the replicated datapaths and to automatically perform dead code elimination, leading to the generation of the minimum set of resources required for each of the cores. Static thread ID propagation also avoids the replication of sections of the datapath only used by one thread, such as resources that execute reduction operations.

Pointer promotion. The OpenMP API makes extensive use of pointers and multiple levels of indirection to exchange references to internal data structures and parameters between threads; such a programming model is generic and versatile, but it determines an overhead for memory accesses and pointer resolution. In fact, memory operations on FPGA typically need to access external memories and are thus significantly more expensive in terms of latency and energy with respect to arithmetic operations. Whenever possible, SPARTA leverages static resolution of multiple indirections to reduce the number of memory operations. Because the input application and the architectural parameters (e.g., number of contexts per core and memory architecture) are fixed, the SPARTA frontend can apply function versioning for each call to functions of the parallel API. After versioning, each function represents an instance of a hardware component, and static analysis can be performed on the IR to infer dynamically allocated data structures and memory accesses: simple and multiple indirections are solved with pointer promotion, and statically allocated data structures enable further optimizations during the HLS flow. Once parallel APIs versioning is completed, it is also possible to perform a more detailed alias analysis on pointers to understand what memory structures are accessed by each operation. In this way, it is possible to pinpoint shared memory variables whose location will be shared at runtime between threads and allocate them in shared BRAMs while the remaining private memory variables are allocated in the local memories.

The GAPBS [7] is a collection of benchmarks intended to standardize evaluation for graph research, and it uses OpenMP to parallelize execution. We tested SPARTA on a subset of GAPBS benchmarks, excluding the ones that use OpenMP primitives that have not yet been implemented in SPARTA. The target is an AMD/Xilinx Alveo U280 board with a clock frequency of 250 MHz. In all experiments, the input graph, in Compressed Sparse Row format [49], is assumed to be stored outside the FPGA in an external DRAM memory.

The connected components (CC) benchmark finds the largest connected subgraph in the undirected input graph; we synthesized it with configurations that vary from one to eight cores and from one to eight contexts per core. With a larger number of cores/contexts, the memory channels utilization saturates, and there can be no further improvement, as the primary source of latency for the CC application is the access to the external memory. As can be seen in Figure 7(a), the increase in performance over a sequential version of the application (one core, one context) grows linearly with the number of cores, keeping the number of contexts constant; in fact, having more cores that perform memory requests increases the utilization of the memory channels and the overall performance. We can see the same effect with more contexts on the same core to hide the memory latency: the configuration with eight contexts on one core has the same speedup as the one with eight cores and a single context. The configuration with eight cores and eight contexts is 36 times faster than the sequential version; this is slower than the theoretical speedup because the memory access pattern is irregular, bringing multiple requests on the same memory bank at the same time and thus producing delays and congestion on the NoC. LUTs and registers scale differently with the number of cores/contexts, as can be seen in Figure 7(b): the number of LUTs grows with the number of OpenMP threads (e.g., 7\(\times\) increase with respect to the sequential version with eight cores, eight contexts), while liveness analysis during the synthesis flow identifies the minimum number of registers to be replicated for CS, so the number of registers is mostly linked to the number of cores (4\(\times\) more than in the sequential version).

The second GAPBS kernel we evaluated is PR, which assigns a value to each graph node based on its relative importance compared to the other nodes. Figure 8(a) shows that the speedup over a sequential baseline proportionally increases with the number of cores, similar to the CC benchmark. However, in this case, increasing the number of contexts per core from four to eight does not lead to the same performance improvement because some sections of PR are computation-bound rather than memory-bound, leading to competition for parallel cores rather than stalls due to memory access operations. With the largest configuration, we achieve a 30\(\times\) speedup with 6.5\(\times\) the area occupation (considering LUTs, registers occupation only increases 4.5 times).

The last GAPBS benchmark we considered is Triangle Count (TC), which counts the number of triangles in the input graph. After assessing how performance and resource consumption scale with varying numbers of cores and contexts (Figure 9) on the Alveo target, we used this benchmark to perform a first comparison against the Svelto synthesis methodology [39]. There are a few differences between the two methods that need to be considered. Svelto is based on a gcc/g++ frontend, while SPARTA uses Clang; the crossbar used in Svelto has a different behaviour with respect to the NoC used in SPARTA, and the comparison is further complicated by the fact that Svelto uses atomic-based synchronization while SPARTA implements OpenMP reductions. They also operate under different assumptions regarding the behaviour of the memory (i.e., SPARTA allows to use asynchronous external memories that can accept multiple requests at the same time while Svelto only sends one request at a time), and Svelto dynamically assigns loop iterations to the cores while SPARTA uses static scheduling. Nevertheless, Svelto remains the state-of-the-art methodology closest to SPARTA, as described in Section 2.1, and it is worthwhile to examine the QoR of accelerators generated with the two methods. Furthermore, since both use Bambu as HLS backend, we can safely state that the comparison only refers to the differences in the implementation of parallel accelerators rather than being influenced by different choices in the scheduling, allocation, and code generation steps.

The results in Figure 10(a) show the relative performance of SPARTA against the Svelto baseline with both tools targeting a Virtex 7 FPGA at 100 MHz; bars higher than one, thus represent configurations where SPARTA outperforms Svelto. While Svelto is faster on smaller configurations, SPARTA can achieve a higher level of parallelization as the number of cores and contexts grows. There are two main reasons for this: the first one is that the NoC in SPARTA is designed to be effective when there are many requests from different sources, which is achieved when the number of cores is higher; the second reason lies in the ability of SPARTA to allow multiple memory requests simultaneously, which is critical to exploit memory-level parallelism when multiple memory channels are available. In fact, SPARTA adds a tag to external memory requests, allowing it to send multiple pipelined, asynchronous requests, while Svelto must wait for the memory to answer before performing the next request. With a number of OpenMP threads greater than the number of banks in the external memory, SPARTA can execute more requests in parallel than Svelto, resulting in a higher speedup. Regarding area usage, as can be seen in the relative comparisons of Figure 10(b) and (c), SPARTA consumes more resources than Svelto on the TC benchmark. However, the area-delay product (ADP) of SPARTA scales better with the number of cores/contexts: using the formulawe can see that, for example, the ADP of a SPARTA accelerator with 1 core and 1 context is 1.14 times the ADP of a Svelto accelerator with the same configuration, and the ratio drops to 0.47 with 32 cores and 8 contexts (SPARTA is 3.8 times faster using only 1.7 times the LUTs and 2.4 times the registers). One reason for the higher resource consumption is that SPARTA is more general than Svelto: SPARTA explicitly implements multiple OpenMP primitives and synchronization mechanisms, while Svelto only supports a few patterns, and thus, it can make assumptions on the behaviour of the input program that simplifies the underlying architecture. Moreover, SPARTA implements reduction operations that require fewer cycles and memory operations but more area than the atomic operations implemented in Svelto. Finally, Svelto has a centralized dispatcher that distributes loop iterations to the cores, while each core in SPARTA contains dedicated logic to compute the current iteration index.

In this section, we evaluate the performance cost of the NoC and the effect of back pressure on the latency of memory operations. Table 5 shows data collected synthesizing and running the TC, PR and CC benchmarks with 32 cores and eight contexts, as it is the configuration with the largest occurrence of back pressure signals. We tested two different configurations of the NoC: one that registers only the 32 I/O nodes and leaves the other 32 combinatorial and one that only uses registered nodes. The difference between the two configurations of the NoC is the number of requests it can store, which is equal to the number of registered nodes, and the maximum latency of the NoC, which is two clock cycles in the first case and four in the second. The actual number of cycles needed to traverse the NoC equals the number of registered nodes on the request’s path plus the effect of congestion (NoC latency).

BP represents the total number of times the NoC could not accept a memory request because of congestion, measured through the number of back pressure signals received by the FIFO modules in front of all cores, while the number of memory operations is the sum of the requests from all cores on all memory channels. We can compute the average delay spent by a single request in the FIFO modules before entering the NoC by dividing the total number of back pressure signals by the number of memory operations; this is the effect of the arbitration on the main memory bus, and it is very small when compared with the latency of the memory (20 cycles) or the latency of the NoC. The average NoC latency is measured as the average time that it takes for a request to traverse it.

Using a registered NoC, which can store more requests and thus reduce the effect of the arbitration delay, has a negative effect on the total number of cycles for two reasons: while a registered NoC reduces the number of back pressure signals, it increases the minimum time needed to traverse the NoC from two cycles to four, and it increases the internal congestion (visible in the higher average NoC latency). For these reasons, we ran all the experiments in Section 4.1 with a NoC with only the I/O nodes registered.

In this section, we generate accelerators for the same parallel database queries used in [39], which are SPARQL queries from the LUBM benchmark and dataset [23] translated into C++ and parallelized with OpenMP. SPARQL is a query language for graph databases in the resource description format (RDF). RDF databases are naturally described as single labelled graphs, and SPARQL queries are defined as (sub)graph matching operations. The resulting code features nested for loops with different behaviours (e.g., number of OpenMP threads, number of loop iterations assigned to each thread) and irregular memory accesses. We compared results obtained with SPARTA and Svelto on several different parallel queries and also ran the same experiments, adding a cache in the SPARTA accelerators in front of each memory bank (512 lines, 512 bits per line). Figure 11 shows the relative performance of SPARTA against the Svelto baseline, with and without caches; as before, bars higher than one represent configurations where SPARTA outperforms Svelto.

The results we obtained are different depending on the specific query considered and the characteristics of its workload. In Q1, SPARTA without caches is always slower than Svelto, as it contains a small group of OpenMP threads, each performing a large number of operations, and we have shown how SPARTA performs best with memory-bound workloads. Q4 and Q5 terminate in a few tens of thousands of cycles and are not very indicative of the achievable speedup, as most cycles are spent in synchronization operations. Data for Q5 with 8 cores and 8 contexts is missing as Svelto does not terminate in that configuration. The results observed align with the ones from TC: SPARTA without caches has worse performances when using few threads but improves when the number of cores and contexts grows. In Q2, Q3, and Q7, SPARTA drastically outperforms Svelto, even considering the higher resource utilization (Figure 12), with between 6 and 11.5 times faster execution. In Q1 and Q6 instead, Svelto is faster, and this can be explained by a lack of parallelism in the query: a lot of the work has to be executed by a small subset of the threads and the dynamic assignment of iterations in Svelto is better suited for this than the static division of work in SPARTA. However, even in these cases, with enough cores and contexts, SPARTA can recover the disadvantage and at least reach the same performance, although using a larger area.

When using caches, SPARTA is almost always faster than Svelto, and this is particularly effective in the test cases where previously SPARTA was struggling: in both Q1 and Q6, the introduction of caches in SPARTA makes the generated accelerators more than twice as fast than before. With the largest configurations in Q2, Q3, and Q7, adding the cache reduces the speedup compared with the base version of SPARTA: these tests are the ones in which static scheduling can divide the computations between multiple cores and keep all of them working. Under this circumstance, the main advantage of SPARTA is the ability to parallelize multiple requests running different contexts and hide the memory latency while advancing the state of all the contexts simultaneously; adding caches reduces the average memory latency, and it can cause a loss of parallelization when using CS. In fact, if the memory requests are answered faster, the execution of the different contexts can become serialized and, depending on the data access pattern, lead to worse results.

In Figure 13, we investigated the influence of CS across various configurations. Due to space constraints, we focused on analyzing the speedup resulting from increasing the number of contexts from 1 to 2, 4, and 8 for query Q7. The speedup was visualized using bar charts and compared against different numbers of cores and tools (Svelto, SPARTA, and SPARTA with caches). When the number of contexts was fixed at 1, we noticed that Svelto and SPARTA exhibited similar execution times, except in the case of 32 cores (see Figure 11). As expected, introducing caches improved SPARTA’s performance across all scenarios. Transitioning from spatial to temporal parallelism, SPARTA and SPARTA with cache approaches demonstrated superior scalability compared to Svelto. In fact, in Figure 13, the maximum speedup achieved by increasing the number of cores tended to decrease as expected, but the rate of decrease was lower for SPARTA and SPARTA with caches compared to Svelto. This limited scalability of Svelto is due to its interconnection, which scales less efficiently than the NoC used by SPARTA. Furthermore, SPARTA initiates a new memory operation before completing the previous one, enhancing channel utilization. Finally, with caches enabled in SPARTA, the impact of spatial parallelism is heightened while the impact of temporal parallelism is reduced. In Figure 13, the maximum speedup with Svelto and SPARTA is around 6–7, while with SPARTA with caches, it is around 4.

Commercial tool Vitis HLS from AMD/Xilinx provides a library of pre-optimized C++ kernels to implement graph processing accelerators.² The kernels from the Vitis library have been optimized for HLS through parallelization, loop pipelining, and the introduction of caches to reduce memory access times.

We utilized identical graphs to compare the results obtained through the Vitis Graph library with the SPARTA approach. Although our graphs are smaller in scale compared to those used with the Vitis Graph Library, they still provide a reasonable simulation and analysis time for conducting design space exploration. The graph characteristics are detailed in Table 6. The graphs are stored in the Compressed Sparse Row matrix format as undirected. For TC and PR, directed graphs are required, thus only the lower triangular part of the matrix is utilized. The SPARTA configurations for TC, CC, and PR are optimized to fully utilize spatial and temporal parallelism, using 32 cores and eight contexts each. However, due to issues in the place and route phase, SPARTA cannot achieve the same frequency as Vitis with such large designs. As a result, the post-routing frequency achieved is 200/220 MHz instead of the 250 MHz obtained with smaller configurations.

In the Vitis benchmarks, the delay of the HBM interface between the accelerator and the memory ranges from 100 to 140 ns, depending on the address of the request. To approximate this behaviour in the SPARTA benchmarks, we increased the memory delay to 32 cycles, which at 200/220 MHz is equivalent to 160/145 ns. Additionally, we utilized the AXI4 protocol instead of the minimal interface to exchange data between the accelerators and the external memory.

It is worth noting that both SPARTA and Vitis target an Alveo U250 FPGA, part of the Ultrascale family. The results for each algorithm are reported separately in Tables 7, 8, and 9.

SPARTA and Vitis can achieve different maximum frequencies. To account for this difference, we calculated the kernel execution time as the achieved clock period times the number of cycles (Time in the Tables). In addition, we computed the AreaXTime metric to normalize the performance of the different designs.

In the CC benchmark, SPARTA outperforms Vitis in terms of execution time by a factor of 10, with only a 30% greater area occupation. Additionally, the AreaXTime metric favours SPARTA by almost an order of magnitude.

In the TC benchmark, SPARTA achieves, on average, a faster execution time. It requires 14% less time to complete the computation of the four graphs. However, it occupies four times more of Vitis’s area.

In the PR benchmark, SPARTA achieves a speedup between four and six times compared to Vitis, occupying only twice the area. Consequently, it achieves an AreaXTime metric at most half of Vitis.

As performance results for the BFS graph library kernel are not available, we also used Vitis HLS to synthesize a C++ implementation of the BFS algorithm loosely based on the one available in MachSuite [48]. Note that we are using the common frontier-based implementation rather than the direction-optimizing implementation [6] (also provided in GAPBS). BFS is the prototypical irregular kernel [1] where the number of iterations for each thread can be highly unbalanced and requires critical sections to synchronize the different threads.

We tried different configurations for SPARTA, varying the number of cores and contexts using the accelerator produced by Vitis HLS as a baseline. Table 10 compares the accelerators produced by Vitis HLS and SPARTA without parallelization (one core and one context). There is only a small difference between the number of cycles for the two tools, while the area is more difficult to compare: Bambu does not require BRAMs for this design as it maps all logic on LUTs and registers, and almost half of the LUTs and registers used are dedicated to the 16 node NoC (as reported in Table 4).

Figure 14(a) displays the speedup achieved using different configurations of SPARTA with respect to the number of cycles required by Vitis HLS. In the sequential version, most of the time is spent waiting for the external memory to provide data in both the SPARTA and Vitis implementations. In the SPARTA parallel accelerators, a similar pattern arises when the number of contexts per core is small: each core spends most of the time waiting for new data to process. As we increase the number of contexts, each core spends a greater fraction of time doing useful computations. Even when using multiple contexts, BFS does not achieve the same speedup as more regular applications such as the ones described in Section 4.1: during the exploration of the graph, each thread can find a different number of elements, leading to a high load imbalance. Furthermore, all threads must be periodically synchronized to avoid exploring the same node of the graph multiple times and to compute the correct length of the shortest path from the origin. Despite this, SPARTA can achieve good speedup when using four contexts per core: with four cores, it achieves a speedup of almost five times, and with two cores, a speedup of three times compared to the Vitis HLS baseline. Figure 14(b) compares the area utilization of SPARTA and Vitis HLS. When adding a core, SPARTA replicates almost the entire design and adds necessary communication and synchronization logic. Hence, resource utilization increases a little more than linearly: with four cores and one context, the area occupied is six times more than the baseline. Note that with 4 cores, the NoC is larger than the entire design generated by Vitis HLS. However, its size does not increase when more contexts per core are added.

We compare SPARTA even with the published results obtained by LegUp [15]. Specifically, we are using the Mandelbrot kernel from the latest open-source version of LegUp. This kernel is a parallelized version of the Mandelbrot iterative mathematical benchmark, which produces a fractal image and is parallelized with OpenMP for pragmas. The results obtained by LegUp on this benchmark are reported in Table 11, as published in [15]. SPARTA achieves better performance across all metrics when using the same Mandelbrot kernel on a Stratix IV device (see Table 12). This performance advantage can be attributed to several factors, including SPARTA’s use of external memory for storing the Mandelbrot picture, its independence from a soft processor for OpenMP parallelization, and its simpler architecture.

Results from other benchmarks in [15] will only further widen the performance gap between SPARTA and LegUp. These other benchmarks rely on Pthread primitives in addition to the OpenMP pragmas. Pthread primitives are partially implemented as software to control hardware threads, increasing the overhead introduced by the soft processor and affecting the overall execution.