Recently, the 62nd Design Automation Conference (DAC), a top academic conference in the field of electronic design automation, was held in San Francisco, USA. The team led by Associate Professor He Zhezhi from the School of Computer Science at Shanghai Jiao Tong University had two papers selected, one of which, titled “PICK: An SRAM-based Processing-in-Memory Accelerator for K-Nearest-Neighbor Search in Point Clouds,” won the Best Paper Nomination Award. This year, DAC received a total of 1862 submissions, of which 420 were accepted, and only 7 papers were nominated for the Best Paper Award. Doctoral student Nie Chen from the School of Computer Science is the first author of this paper, with collaborators Jiang Chao, Xiao Liming, and Zhang Weifeng, and Associate Professor He Zhezhi as the corresponding author. This research was supported by the National Natural Science Foundation and the National Key R&D Program.

Research Background

Point clouds are a commonly used data format for accurately characterizing spatial structures and have been widely applied in cutting-edge applications such as autonomous driving, robotic navigation, and augmented reality. In these applications, the most commonly used computation is the kNN search algorithm, which is primarily used to handle the geometric adjacency relationships between points in point clouds. It is a core component of several key algorithms such as SLAM, point cloud registration, object recognition, and semantic segmentation. However, kNN search faces significant challenges in both computation and storage: its distance calculations and Top-k search operations are not only computation-intensive and require high memory bandwidth but can also account for over 80% of the total latency in the entire point cloud processing pipeline.

Figure: Schematic of point cloud data

Although some accelerators have attempted to reduce the load through data structure optimization (such as kd-trees, octrees, etc.) or approximate computations, they often suffer from issues such as precision loss or high preprocessing overhead. Particularly on resource-constrained edge devices, achieving low-power, low-latency, and high-precision kNN search remains a key challenge and technical hurdle faced by both industry and academia.

Research Achievements

To address the aforementioned bottlenecks, the team proposed an SRAM-based in-memory computing acceleration architecture, achieving efficient, precise, and fully hardware-deployable kNN point cloud search acceleration for the first time. The paper presents several key innovations at the architecture and circuit levels:

(1) Bit-serial in-memory computing technology: Introduced a mature bit-serial in-memory computing microarchitecture design, converting the multiply-accumulate operations in traditional kNN into logical operations that can be executed in situ within SRAM, significantly reducing data movement overhead and eliminating runtime access to DRAM, achieving true “compute-in-storage” and significantly optimizing data locality and reusability.

(2) Bit-width pruning technology: Proposed an innovative pruning strategy that dynamically reduces irrelevant bit-width by identifying effective information bits, typically reducing the number of logical operations for distance calculations by 56% with minimal impact on precision, greatly shortening latency and reducing energy consumption.

Figure: Bit pruning algorithm can significantly reduce computational load

(3) Filtering and selection-based Top-k search mechanism: To support efficient searches for arbitrary k values, a two-stage “filtering-selection” mechanism was designed, combined with dynamic threshold binary adjustment, achieving approximately constant latency processing for Top-k searches, breaking the limitations of existing solutions that are insensitive to k values or have low resource utilization.

Figure: Efficient Top-k search mechanism based on filtering and selection

(4) Two-level pipeline structure design: Achieved hardware pipeline parallelism for distance calculations and Top-k searches, accelerating the entire query process and effectively improving throughput.

Experimental results show that PICK demonstrates excellent performance across multiple real point cloud datasets: on the KITTI dataset, compared to the current best design BitNN, PICK achieved a 4.17× speedup and a 4.42× reduction in energy consumption while maintaining almost no precision loss. This architecture supports full-chip deployment for large-scale point cloud processing tasks and has broad potential for edge computing applications.

Figure: Precision tests prove that this work can ensure good accuracy

Figure: Performance evaluation shows that this design outperforms existing designs

Author Introduction

Nie Chen is a doctoral student at the School of Computer Science at Shanghai Jiao Tong University, focusing on high-performance computing architecture, in-memory computing architecture design, and hardware-software co-design and optimization, with publications in Nature Communication, TC, DAC, etc.

He Zhezhi is an associate professor at the School of Computer Science at Shanghai Jiao Tong University, primarily researching intelligent computing hardware and software design, brain-like computing, computer architecture, and electronic design automation.

Source: Shanghai Jiao Tong University

Previous HighlightsReviewof Exciting Events

Guarding Voice Security: How the CPSS Team at Huazhong University of Science and Technology Built an Anti-Deepfake System to Win the Creative Works Competition?

Guidelines for “Surviving” Top Conference Papers: A Review of the IEEE S&P Review Process from the Perspective of Reviewers

Under the “Five-Color Stone” Plan, Southeast University Innovates the “Password” of Cybersecurity Talent Training Model

“Cybersecurity + Law” Dual Degree | See how Nankai University, Southeast University, and Chongqing University of Posts and Telecommunications are Accelerating on the New Track

A New Paradigm for Training “Practical” Cybersecurity Talents: How Shanghai Jiao Tong University, Jinan University, and Hunan University are Transforming Models to Cultivate Cybersecurity Practitioners

Information Network Security

“Information Network Security” was founded in 2001, supervised by the Ministry of Public Security, and co-sponsored by the Third Research Institute of the Ministry of Public Security and the China Computer Federation. It is one of the first domestic journals in the field of information security, becoming a core journal of Chinese science and technology in 2015, a source journal of the Chinese Science Citation Database in 2017, a core journal in Chinese in 2018, and selected in the CCF high-quality scientific journal grading directory in 2022.

Chinese Core Journal

Chinese Science and Technology Core Journal

Source Journal of the Chinese Science Citation Database

CCF High-Quality Scientific Journal in Computing Field

We are continuously striving for improvement and look forward to your attention and support!