With the widespread use of large language models (LLMs), and with the privacy and cost concerns on cloud-based services, vendors are now pushing LLM inference to consumer devices. However, current attempts only enable real-time inference of low-quality small-sized LLMs. Large-sized LLMs have to load most of their weights from Flash storage for every execution iteration, which dominates the execution time of both the prefill and the generation phase. This performance bottleneck is attributed to both the low internal Flash memory bandwidth and the low transmission bandwidth between Flash and the Neural Processing Unit (NPU). To tackle these two challenges, we present Lincoln, a device-architecture co-design solution with LPDDR-interfaced, Compute-Enabled Flash Memory. On the device level, we boost the Flash internal bandwidth by improving upon existing array shrinking methods, to enable lower read latency and more parallel Flash planes within each Flash die. We specifically leverage 3D hybrid bonding, which is already adopted in consumer Flash products, to maintain high area efficiency and low density loss. On the architecture level, to leverage such increased internal bandwidth for resolving the transmission bottleneck, we propose two solutions for the two distinct phases of LLMs. For the compute-intensive prefill phase, we let Flash devices use the existing high-speed LPDDR interface (originally for DRAM), which offers much higher transmission bandwidth to the NPU than the conventional Flash interface, while maintaining good cost and area efficiency. For the memory-intensive generation phase, we rely on hybrid-bonding-based near-Flash computing to fully utilize the internal Flash bandwidth, and further equip with speculative decoding to eventually reach the real-time latency goal. Our evaluation shows that Lincoln enables real-time inference, with up to $13.23 \times$ and $254.1 \times$ speedups for LLM prefill and generation phases over conventional SSD-based systems.

DIMM-based Near-Memory-Processing (NMP) kernel offloading enables a program to execute in computation-enabled DIMM buffer chips, bypassing the bandwidth-constrained CPU main memory bus for high performance. Yet, it also enables programs to access memory without restrictions and protection from CPU, resulting in potential security hazards. To protect general NMP kernel offloading even with malicious privileged software, a heterogeneous TEE is required. However, the conventional heterogeneous TEE design results in severe data movement bottleneck for DIMM-based NMP. Concretely, it isolates host CPU process from NMP kernel's memory and vice versa, such that CPU TEE and trusted NMP driver can protect CPU processes and NMP kernels in complete separation, simplifying the architectural design. Such isolation results in redundant input/output data movement between the two isolated memory spaces, with half of the movement performed by host CPU. Worsened by limited CPU memory bandwidth, we identify that such redundancy severely bottlenecks the performance of many potential NMP applications. To overcome this bottleneck, we propose to abandon isolation and share the NMP kernel memory with its host CPU process. Considering security, however, two challenges exist that fundamentally contradict the conventional separation-oriented TEE design. First, for protection against software attacks on the shared memory, consistent security guarantees have to be offered by the CPU TEE and the NMP driver respectively on CPU processes and NMP kernels, in terms of both memory ownership (allocation) and views (mapping). Second, to enable shared memory access while offering protection against physical attacks, cryptography metadata like keys and Merkle tree root have to be securely shared and synchronized between CPU and NMP unit. To overcome these challenges, we designSSS-DIMM, an efficient TEE for DIMM-based NMP kernel offloading that removes the redundant data movement viaSecureSpaceSharing. At its core, we devise secure, general and complexity-minimized instruction interfaces, which empower the trusted NMP driver with restricted authority to access the memory allocation/mapping recordings of CPU TEE, and to set and access cryptography metadata of the shared memory in both NMP unit and CPU. Along with carefully designed software workflows, these interfaces enable full resolve of the challenges. Compared with conventional heterogeneous TEE and the unprotected baseline, our evaluation shows that SSS-DIMM maintains both security and performance, achieving a geomean speedup of 9.1× for NMP kernel offloading over conventional TEE design.

Read mapping is a crucial task in computational genomics. Recently, there has been a significant paradigm shift from sequence-to-sequence mapping (S2S) to sequence-to-graph mapping (S2G). The S2G mapping incurs high graph processing overheads and leads to an unnoticed shift of performance hotspots. This presents a substantial challenge to current software implementations and hardware accelerators.

In-memory key-value store (KVS) has become crucial for many large-scale Internet services providers to build highperformance data centers. While most of the state-of-the-art KVS systems are optimized for read-intensive applications, a wide range of applications have been proven to be insert-intensive or scan-intensive, which scale poorly with the current implementations. With the availability of FPGA-based smart NICs in data centers, hardware-aided and hardware-based KVS systems are gaining their popularity. In this paper, we present HeteroKV, a scalable line-rate KVS on heterogeneous CPU-FPGA platforms, aiming to provide high throughput in read-, insert- and scan-intensive scenarios. To achieve this, HeteroKV leverages a heterogeneous data structure consisting of a b+ tree, whose leaf nodes are cache-aware partitioned hash tables. Experiments demonstrate HeteroKV's high performance in all scenarios. Specifically, a single node HeteroKV is able to achieve 430M, 315M and 15M key-value operations per second in read-, insert- and scan-intensive scenarios respectively, which are more than 1.5x, 1.4x and 5x higher than state-of-the-art implementations.

Near-Memory Processing (NMP) systems that integrate accelerators within DIMM (Dual-Inline Memory Module) buffer chips potentially provide high performance with relatively low design and manufacturing costs. However, an inevitable communication bottleneck arises when considering the main memory bus among peer DIMMs and the host CPU. This communication bottleneck roots in the bus-based nature and the limited point-to-point communication pattern of the main memory system. The aggregated memory bandwidth of DIMM- based NMP scales with the number of DIMMs. When the number of DIMMs in a channel scales up, the per-DIMM point-to-point communication bandwidth scales down, whereas the computation resources and local memory bandwidth per DIMM stay the same. For many important sparse data-intensive workloads like graph applications and sparse tensor algebra, we identify that communication among DIMMs and the host CPU easily dominates their processing procedure in previous DIMM-based NMP systems, which severely bottlenecks their performance.To tackle this challenge, we propose that inter-DIMM broadcast should be implemented and utilized in the main memory system of DIMM-based NMP. On the hardware side, the main memory bus naturally scales out with broadcast, where per- DIMM effective bandwidth of broadcast remains the same as the number of DIMMs grows. On the software side, many sparse applications can be implemented in a form such that broadcasts dominate their communication. Based on these ideas, we design ABC-DIMM, which Alleviates the Bottleneck of Communication in DIMM-based NMP, consisting of integral broadcast mechanisms and Broadcast-Process programming framework, with minimized modifications to commodity software-hardware stack. Our evaluation shows that ABC-DIMM offers an 8.33 × geo-mean speedup over a 16-core CPU baseline, and outperforms two NMP baselines by 2.59 × and 2.93 × on average.

Coarse-grained reconfigurable architectures (CGRAs) are increasingly employed as domain-specific accelerators due to their efficiency and flexibility. A CGRA typically relies on compilers to perform task scheduling. The longstanding problem of static scheduling is that it suffers from insufficient parallelism in handling irregularities due to over-serialization and workload imbalance, which leads to severe resource underutilization and performance loss. To counteract the limitations of static scheduling in CGRAs, it is essential to exploit dynamic parallelism automatically and manage hardware resources adaptively. However, existing dynamic scheduling mechanisms, e.g., work stealing, often reschedule aggressively for instant performance but sacrifice efficiency, which is unfavorable to CGRAs that emphasize efficiency and fewer reconfigurations. This article proposes an elastic task scheduling scheme that enables lightweight dynamic scheduling in CGRAs. Tasks are rescheduled at runtime according to the classic tagged-token dataflow paradigm to enable dynamic task-level parallelism. Meanwhile, tasks are dynamically resized according to run-time throughputs via duplication, combination, and substitution operators for balanced multitask execution. We implement the elastic task scheduling scheme on a well-known reconfigurable architecture - triggered instruction architecture (TIA). Evaluation on the MachSuite benchmarks shows that the proposed scheme is effective in improving performance and energy efficiency. The average speedup is 2× over the baseline. Also, our design attains a 57 percent improvement in the area-normalized performance and a 49 percent better energy efficiency. Compared with a state-of-the-art dynamic scheduling method, our scheme achieves 1.6× speedup and 1.6× energy efficiency than work-stealing mechanism on the same substrate.

It is of vital importance to efficiently process large graphs for many data-intensive applications. As a result, a large collection of graph analytic frameworks has been proposed to improve the per-iteration performance on a single kind of computation resource. However, heavy coordination and synchronization overhead make it hard to scale out graph analytic frameworks from single platform to heterogeneous platforms. Furthermore, increasing the convergence rate, i.e. reducing the number of iterations, which is equally vital for improving the overall performance of iterative graph algorithms, receives much less attention. In this paper, we introduce the Block Coordinate Descent (BCD) view of graph algorithms and propose an asynchronous heterogeneous graph analytic framework, GraphABCD, using the BCD view. The BCD view offers key insights and trade-offs on achieving high convergence rate of iterative graph algorithms. GraphABCD features fast convergence under the algorithm design options suggested by BCD. GraphABCD offers algorithm and architectural supports for asynchronous execution, without undermining its fast convergence properties. With minimum synchronization overhead, GraphABCD is able to scale out to heterogeneous and distributed accelerators efficiently. To demonstrate GraphABCD, we prototype its whole system on Intel HARPv2 CPU-FPGA heterogeneous platform. Evaluations on HARPv2 show that GraphABCD achieves geo-mean speedups of 4.8x and 2.0x over GraphMat, a state-of-the-art framework in terms of convergence rate and execution time, respectively.

TCAM (Ternary Content-Addressable Memory) is the essential component for high-speed packet classification in modern hardware switches. However, due to its relatively slow update process, recent advances in Software-Defined Network (SDN) regard them as the bottleneck to the agile deployment of network services. Rule installation in commodity switches suffers from non-deterministic delays, ranging from a few milliseconds to nearly half a second. The crux of the problem is that TCAM prioritizes rules based on physical addresses. Corresponding entries have to be reallocated according to the priority of an incoming rule, such that the insertion delay grows linearly with the number of existing rules in a TCAM. In this paper, we present Constant-time Alteration Ternary CAM (CATCAM) that can accomplish both lookup queries and update requests for packet classification in a few nanoseconds. The key to fast update is to decouple rule priorities from physical addresses. We propose a matrix-based priority encoding scheme that records the priority relation between rules and can be implemented in 8T SRAM arrays with the emerging Processing In-Memory (PIM) technique. CATCAM also comes with a hierarchical architecture to scale out, its interval-based scheduling scheme guarantees deterministic update performance in all scenarios. CATCAM is developed under full-custom design in the 28 nm process. Evaluation across benchmark workloads shows that CATCAM provides at least three orders of magnitude speedup over state-of-the-art TCAM update algorithms and offers equivalent search capability to conventional TCAM while incurring 0.3% power and 20% area overhead.

The performance of High-Level Synthesis (HLS) applications with irregular data structures is limited by its imperative programming paradigm like C/C++. In this paper, we show that constructing concurrent data structures with channels, a programming construct derived from CSP (communicating sequential processes) paradigm, is an effective approach to improve the performance of these applications. We evaluate concurrent data structure for FPGA by synthesizing a K-means clustering algorithm on the Intel HARP2 platform. A fully pipelined KMC processing element can be synthesized from OpenCL with the help of a SPSC (single-producer-single-consumer) queue and stack built from channels, achieving 15.2x speedup over a sequential baseline. The number of processing element can be scaled up by leveraging a MPMC (multiple-producer-multiple-consumer) stack with work distribution for dynamic load balance. Evaluation shows that an additional 3.5x speedup can be achieved when 4 processing element is instantiated. These results show that the concurrent data structure built with channels has great potential for improving the parallelism of HLS applications. We hope that our study will stimulate further research into the potential of channel-based HLS.

Sparse Matrix-Vector Multiplication (SpMV) is the most important sparse linear algebra kernel in both scientific and engineering applications. Due to its irregular control flow and data access pattern, Von Neumann architectures like CPUs and GPUs cannot fully exploit the inherent parallelism of S pMV. Although FPGAs can efficiently accelerate SpMV in a dataflow manner, their performance is degraded in face of large matrices that exceed the capacity of on-chip memory because of excessive rescheduling of data. In this paper we propose ReDESK, a Reconfigurable Dataflow Engine for Sparse Kernels, for emerging tightly-coupled CPU-FPGA heterogeneous platforms. To fully exploit the heterogeneity, we design a novel representation of sparse matrix that is tailored for data prefetching on CPU-side and streaming processing on FPGA-side. In this way ReDESK can fully utilize the memory bandwidth regardless of the scale of SpMV problem. We evaluate ReDESK on Intel HARP-2 platform with a set of matrices from the University of Florida sparse matrix collection. The result demonstrates an average bandwidth utilization of 0.094 GFLOP/GB, which is 1.6-4.3x more efficient than previous SpMV on FPGAs.

Transactional Memory (TM) has been considered as a promising alternative to existing synchronization operations, which are often the largest stumbling block to unleashing parallelism of applications. Efficient implementations of TM, however, are challenging due to the tension between lowering performance overhead and avoiding unnecessary aborts.

The pipeline stall in distributed-controlled coarse-grained reconfigurable arrays is a major source stumbling performance. This work presents a Triggered-Issue and Triggered-Execution (TITE) paradigm motivated from the Triggered Instruction Architecture (TIA) which converts control and data dependencies into predicate dependencies as triggers for spatial parallelism. TITE separately triggers the issuing and execution of instructions to further relax the predicate dependencies in TIA. Triggered dual instructions and tag forwarding are proposed to minimize pipeline stalls of both intra and inter-processing elements. Experiments show that TITE improves performance, energy efficiency, and area efficiency by 21%, 17%, and 12%, respectively, compared with TIA.

This paper presents a static-placement, dynamic-issue (SPDI) framework for the coarse-grained reconfigurable architecture (CGRA) in order to tackle the inefficiencies of the static-issue, static-placement (SISP) CGRA. This framework includes the compiler that statically places the operations and hardware design, a SPDI CGRA, that automatically schedule the operations. We stress on introducing the SPDI CGRA in this paper. This newly designed hardware model adds the token buffer, which is capable of automatically scheduling the operations inside processing elements (PE), along with a router network that can effectively transform and control data flow among the PE array. This design lets the hardware share the responsibility for the compiler, making them cooperate to deal with the issuing, placement and routing problem. Evaluation of our study shows that our framework can reach on average 1.28, 1.30 and 1.33 higher than three state-of-the-art SISP CGRA using REGIMap, RS compile flow and the EPIMap approaches respectively. The area overhead is nearly 0.93% per token buffer entry for each PE relative to SISP CGRA.

With the prevalence of reconfigurable computing, many relevant courses are designed and taught to graduate students. Traditional Field Programmable Gate Arrays (FPGAs) based hardware platforms are far from satisfying to reflect the important criteria characterizing a general reconfigurable computing system. In order to provide students a comprehensive understanding of reconfigurable computing system in a broader way, this paper presents a mixed-grained educational hardware platform. Different from the traditional ones, the proposed hardware platform includes not only fine-grained reconfigurable fabrics (e.g. FPGAs), but also coarse-grained ones which makes it possible to reveal essential features and intrinsic mechanisms of reconfigurable computing system. Utilizing this hardware platform, a course including four hands-on laboratory projects is designed. The feedback from students and teachers confirms that with the help of the proposed hardware platform, a thorough understanding of reconfigurable computing systems is achieved in an intuitive way and the practical experience is also significantly enhanced.