Weihua Zhang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Weihua Zhang has a total of 61 co-authors. Here are the top co-authors by number of shared publications:
- Haibo Chen
Shanghai Jiao Tong University, Shanghai, China
5 shared publications - Lu Peng
Tulane University
5 shared publications - Haojun Wang
Software School, Shanghai Key Laboratory of Data Science
4 shared publications - Pen-Chung Yew
Department of Computer Science and Engineering University of Minnesota Minneapolis MN USA
4 shared publications Jinhu Jiang
School of Computer Science Fudan University Shanghai China
3 shared publicationsBin-Yu Zang
2 shared publications
Latest Publications
- 30 March 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37  (6) , 1280-1294
Communication-Partition Co-Optimization for Quantum Circuit Simulation on CPU+GPU Clusters
Simulating the behavior of quantum circuits on classical computers is one of the widely used approaches for current quantum computing device and quantum algorithm research. State-vector simulators keep all the quantum states in main memory, thus consuming a large amount of memory and resulting in significant memory access and communication overhead far longer than calculation time. Consequently, data communication time often becomes the primary bottleneck in quantum circuit simulation. Many classical simulators, such as QuEST, are designed to execute quantum gates serially without exploiting data locality, and all amplitudes need to be exchanged. Such a gate-unaware full-data communication scheme forces powerful computation such as GPUs to spend substantial time waiting for data transfers. In this paper, we propose a gate-aware on-demand communication quantum simulation framework to optimize communication overhead. We analyze the on-demand communication process and develop a communication cost model to elucidate the relationship between communication costs and circuit partition. Since greedy circuit partition method can only yield locally optimal solutions, we propose a choice-start-node quantum circuit partition method guided by the communication cost model to further reduce communication overhead in quantum circuit simulation. We evaluate on a 4-node cluster with 2 NVIDIA A100 GPUs on each node and our design achieves 59.32× speedup compared to the gate-unaware full-data communication scheme. Furthermore, compared to the greedy circuit partition method, our partition method can achieve simulation acceleration of 1.79×.
- 30 March 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37  (6) , 1280-1294
Communication-Partition Co-Optimization for Quantum Circuit Simulation on CPU+GPU Clusters
Simulating the behavior of quantum circuits on classical computers is one of the widely used approaches for current quantum computing device and quantum algorithm research. State-vector simulators keep all the quantum states in main memory, thus consuming a large amount of memory and resulting in significant memory access and communication overhead far longer than calculation time. Consequently, data communication time often becomes the primary bottleneck in quantum circuit simulation. Many classical simulators, such as QuEST, are designed to execute quantum gates serially without exploiting data locality, and all amplitudes need to be exchanged. Such a gate-unaware full-data communication scheme forces powerful computation such as GPUs to spend substantial time waiting for data transfers. In this paper, we propose a gate-aware on-demand communication quantum simulation framework to optimize communication overhead. We analyze the on-demand communication process and develop a communication cost model to elucidate the relationship between communication costs and circuit partition. Since greedy circuit partition method can only yield locally optimal solutions, we propose a choice-start-node quantum circuit partition method guided by the communication cost model to further reduce communication overhead in quantum circuit simulation. We evaluate on a 4-node cluster with 2 NVIDIA A100 GPUs on each node and our design achieves 59.32× speedup compared to the gate-unaware full-data communication scheme. Furthermore, compared to the greedy circuit partition method, our partition method can achieve simulation acceleration of 1.79×.
- Open Access
- 9 April 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9  (OOPSLA1) , 113-142
JavART: A Lightweight Rule-Based JIT Compiler using Translation Rules Extracted from a Learning Approach
The balance between the compilation/optimization time and the produced code quality is very important for Just-In-Time (JIT) compilation. Time-consuming optimizations can cause delayed deployment of the optimized code, and thus more execution time needs to be spent either in the interpretation or less optimized code, leading to a performance drag. Such a performance drag can be detrimental to mobile and client-side devices such as those running Android, where applications are often shorting-running, frequently restarted and updated. To tackle this issue, this paper presents a lightweight learning-based, rule-guided dynamic compilation approach to generate good-quality native code directly without the need to go through the interpretive phase and the first-level optimization at runtime. Different from existing JIT compilers, the compilation process is driven by translation rules, which are automatically learned offline by taking advantage of existing JIT compilers. We have implemented a prototype of our approach based on Android 14 to demonstrate the feasibility and effectiveness of such a lightweight rule-based approach using several real-world applications. Results show that, compared to the default mode running with the interpreter and two tiers of JIT compilers, our prototype can achieve a 1.23× speedup on average. Our proposed compilation approach can also generate native code 5.5× faster than the existing first-tier JIT compiler in Android, with the generated code running 6% faster. We also implement and evaluate our approach on a client-side system running Hotspot JVM, and the results show an average of 1.20× speedup.
- 9 April 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9  (OOPSLA1) , 113-142
Open AccessJavART: A Lightweight Rule-Based JIT Compiler using Translation Rules Extracted from a Learning Approach
The balance between the compilation/optimization time and the produced code quality is very important for Just-In-Time (JIT) compilation. Time-consuming optimizations can cause delayed deployment of the optimized code, and thus more execution time needs to be spent either in the interpretation or less optimized code, leading to a performance drag. Such a performance drag can be detrimental to mobile and client-side devices such as those running Android, where applications are often shorting-running, frequently restarted and updated. To tackle this issue, this paper presents a lightweight learning-based, rule-guided dynamic compilation approach to generate good-quality native code directly without the need to go through the interpretive phase and the first-level optimization at runtime. Different from existing JIT compilers, the compilation process is driven by translation rules, which are automatically learned offline by taking advantage of existing JIT compilers. We have implemented a prototype of our approach based on Android 14 to demonstrate the feasibility and effectiveness of such a lightweight rule-based approach using several real-world applications. Results show that, compared to the default mode running with the interpreter and two tiers of JIT compilers, our prototype can achieve a 1.23× speedup on average. Our proposed compilation approach can also generate native code 5.5× faster than the existing first-tier JIT compiler in Android, with the generated code running 6% faster. We also implement and evaluate our approach on a client-side system running Hotspot JVM, and the results show an average of 1.20× speedup.
- Open Access
Open Challenges and Opportunities in Federated Foundation Models Towards Biomedical Healthcare
This survey explores the transformative impact of foundation models (FMs) in artificial intelligence, focusing on their integration with federated learning (FL) for advancing biomedical research. Foundation models such as ChatGPT, LLaMa, and CLIP, which are trained on vast datasets through methods including unsupervised pretraining, self-supervised learning, instructed fine-tuning, and reinforcement learning from human feedback, represent significant advancements in machine learning. These models, with their ability to generate coherent text and realistic images, are crucial for biomedical applications that require processing diverse data forms such as clinical reports, diagnostic images, and multimodal patient interactions. The incorporation of FL with these sophisticated models presents a promising strategy to harness their analytical power while safeguarding the privacy of sensitive medical data. This approach not only enhances the capabilities of FMs in medical diagnostics and personalized treatment but also addresses critical concerns about data privacy and security in healthcare. This survey reviews the current applications of FMs in federated settings, underscores the challenges, and identifies future research directions including scaling FMs, managing data diversity, and enhancing communication efficiency within FL frameworks. The objective is to encourage further research into the combined potential of FMs and FL, laying the groundwork for groundbreaking healthcare innovations.
Open AccessOpen Challenges and Opportunities in Federated Foundation Models Towards Biomedical Healthcare
This survey explores the transformative impact of foundation models (FMs) in artificial intelligence, focusing on their integration with federated learning (FL) for advancing biomedical research. Foundation models such as ChatGPT, LLaMa, and CLIP, which are trained on vast datasets through methods including unsupervised pretraining, self-supervised learning, instructed fine-tuning, and reinforcement learning from human feedback, represent significant advancements in machine learning. These models, with their ability to generate coherent text and realistic images, are crucial for biomedical applications that require processing diverse data forms such as clinical reports, diagnostic images, and multimodal patient interactions. The incorporation of FL with these sophisticated models presents a promising strategy to harness their analytical power while safeguarding the privacy of sensitive medical data. This approach not only enhances the capabilities of FMs in medical diagnostics and personalized treatment but also addresses critical concerns about data privacy and security in healthcare. This survey reviews the current applications of FMs in federated settings, underscores the challenges, and identifies future research directions including scaling FMs, managing data diversity, and enhancing communication efficiency within FL frameworks. The objective is to encourage further research into the combined potential of FMs and FL, laying the groundwork for groundbreaking healthcare innovations.
- Open Access
- 7 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 294-297
QuickTree: A Fast Hardware BVH Construction Engine
Ray tracing has emerged as a powerful technique for generating visually stunning and realistic images compared to rasterization. With the continuous advancements in computer hardware, modern GPUs have integrated specialized ray tracing acceleration units to enhance rendering capabilities further. However, achieving realtime ray tracing presents a challenge in dynamic scenes, where spatial data structures used for accelerated rendering must be reconstructed or updated when there are changes in the scene primitives. This paper introduces QuickTree, a novel Bounding Volume Hierarchy (BVH) construction engine based on the linear BVH (LBVH) optimization algorithm. QuickTree addresses the challenge of dynamic scenes support by employing a highly parallel and pipelined system design. This innovative approach ensures fast construction speed. QuickTree demonstrates significant performance improvements. Compared to the currently fastest MergeTree, it has increased construction speed by 10% and reduced area by 45% compared to RayCore, which has the smallest chip area.
- 7 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 294-297
Open AccessQuickTree: A Fast Hardware BVH Construction Engine
Ray tracing has emerged as a powerful technique for generating visually stunning and realistic images compared to rasterization. With the continuous advancements in computer hardware, modern GPUs have integrated specialized ray tracing acceleration units to enhance rendering capabilities further. However, achieving realtime ray tracing presents a challenge in dynamic scenes, where spatial data structures used for accelerated rendering must be reconstructed or updated when there are changes in the scene primitives. This paper introduces QuickTree, a novel Bounding Volume Hierarchy (BVH) construction engine based on the linear BVH (LBVH) optimization algorithm. QuickTree addresses the challenge of dynamic scenes support by employing a highly parallel and pipelined system design. This innovative approach ensures fast construction speed. QuickTree demonstrates significant performance improvements. Compared to the currently fastest MergeTree, it has increased construction speed by 10% and reduced area by 45% compared to RayCore, which has the smallest chip area.
- Open Access
A System-Level Dynamic Binary Translator using Automatically-Learned Translation Rules
System-level emulators have been used extensively for system design, debugging and evaluation. They work by providing a system-level virtual machine to support a guest operating system (OS) running on a platform with the same or different native OS that uses the same or different instruction-set architecture. For such system-level emulation, dynamic binary translation (DBT) is one of the core technologies. A recently proposed learning-based DBT approach has shown a significantly improved performance with a higher quality of translated code using automatically learned translation rules. However, it has only been applied to user-level emulation, and not yet to system-level emulation. In this paper, we explore the feasibility of applying this approach to improve system-level emulation, and use QEMU to build a prototype. ... To achieve better performance, we leverage several optimizations that include coordination overhead reduction to reduce the overhead of each coordination, and coordination elimination and code scheduling to reduce the coordination frequency. Experimental results show that it can achieve an average of 1.36X speedup over QEMU 6.1 with negligible coordination overhead in the system emulation mode using SPEC CINT2006 as application benchmarks and 1.15X on real-world applications.
Open AccessA System-Level Dynamic Binary Translator using Automatically-Learned Translation Rules
System-level emulators have been used extensively for system design, debugging and evaluation. They work by providing a system-level virtual machine to support a guest operating system (OS) running on a platform with the same or different native OS that uses the same or different instruction-set architecture. For such system-level emulation, dynamic binary translation (DBT) is one of the core technologies. A recently proposed learning-based DBT approach has shown a significantly improved performance with a higher quality of translated code using automatically learned translation rules. However, it has only been applied to user-level emulation, and not yet to system-level emulation. In this paper, we explore the feasibility of applying this approach to improve system-level emulation, and use QEMU to build a prototype. ... To achieve better performance, we leverage several optimizations that include coordination overhead reduction to reduce the overhead of each coordination, and coordination elimination and code scheduling to reduce the coordination frequency. Experimental results show that it can achieve an average of 1.36X speedup over QEMU 6.1 with negligible coordination overhead in the system emulation mode using SPEC CINT2006 as application benchmarks and 1.15X on real-world applications.
- Open Access
- 7 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 203-212
Communication Optimizations for State-vector Quantum Simulator on CPU+GPU Clusters
Simulating the behavior of quantum circuits on classical computers are one of the widely used approaches for current quantum computing device and quantum algorithm research. State-vector simulators keep all the quantum states in main memory, thus consuming a large amount of memory and resulting in great memory access and communication overhead far longer than calculation time. Many classical simulators, such as QuEST, are designed by serial execution of quantum gates without using the data locality, and all amplitudes need to be exchanged. Such a gate-unaware full data communication scheme forces powerful computation such as GPUs to spend a lot of time on waiting for data transmission. In this paper, we propose a gate-aware on-demand communication quantum simulation framework to optimize communication overhead. A quantum circuit partition method through gate fusion is first proposed to avoid unnecessary communications. Moreover, a on-demand data communication scheme is proposed to optimize data transfer among computation nodes. Based on these designs, a prototype has been implemented on QuEST. We evaluated on an 8-node cluster with four NVIDIA Tesla V100 GPUs on each node and our designs can achieve 3.0x-15.6x speedup compared to QuEST for 32-34-qubit quantum systems. Moverover, it can scale to simulate 37-qubit quantum system instead of 34-qubit quantum system for QuEST.
- 7 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 203-212
Open AccessCommunication Optimizations for State-vector Quantum Simulator on CPU+GPU Clusters
Simulating the behavior of quantum circuits on classical computers are one of the widely used approaches for current quantum computing device and quantum algorithm research. State-vector simulators keep all the quantum states in main memory, thus consuming a large amount of memory and resulting in great memory access and communication overhead far longer than calculation time. Many classical simulators, such as QuEST, are designed by serial execution of quantum gates without using the data locality, and all amplitudes need to be exchanged. Such a gate-unaware full data communication scheme forces powerful computation such as GPUs to spend a lot of time on waiting for data transmission. In this paper, we propose a gate-aware on-demand communication quantum simulation framework to optimize communication overhead. A quantum circuit partition method through gate fusion is first proposed to avoid unnecessary communications. Moreover, a on-demand data communication scheme is proposed to optimize data transfer among computation nodes. Based on these designs, a prototype has been implemented on QuEST. We evaluated on an 8-node cluster with four NVIDIA Tesla V100 GPUs on each node and our designs can achieve 3.0x-15.6x speedup compared to QuEST for 32-34-qubit quantum systems. Moverover, it can scale to simulate 37-qubit quantum system instead of 34-qubit quantum system for QuEST.
- Open Access
- 30 June 2023
- Published by EDP Sciences in Security and Safety
- Vol. 2
Multikernel: Operating system solution to generalized functional safety
With the trend of digitalization, intelligence, and networking sweeping the world, functional safety and cyber security are increasingly intertwined and overlapped, evolving into the issue of generalized functional safety. Traditional system reliability technology and network defense technology cannot provide quantifiable design implementation theories and methods. As the cornerstone of software systems, operating systems in particular are in need of efficient safety assurance. The DHR architecture is a mature and comprehensive solution, and it is necessary to implement an OS-level DHR architecture, for which the multi-kernel operating system is a good carrier. The multi-kernel operating system takes the kernel as the processing scenario element and constructs redundancy, heterogeneity, and dynamism on the kernel, so it has the generalized robustness of the DHR architecture. This article analyzes the significance and requirements of OS-level DHR architecture, and systematically explains how the multi-kernel operating system responds to the requirements of OS-level DHR architecture by analyzing the technical routes of multi-kernel operating systems and develops an operating system solution idea for the generalized functionally safety.
- 30 June 2023
- Published by EDP Sciences in Security and Safety
- Vol. 2
Open AccessMultikernel: Operating system solution to generalized functional safety
With the trend of digitalization, intelligence, and networking sweeping the world, functional safety and cyber security are increasingly intertwined and overlapped, evolving into the issue of generalized functional safety. Traditional system reliability technology and network defense technology cannot provide quantifiable design implementation theories and methods. As the cornerstone of software systems, operating systems in particular are in need of efficient safety assurance. The DHR architecture is a mature and comprehensive solution, and it is necessary to implement an OS-level DHR architecture, for which the multi-kernel operating system is a good carrier. The multi-kernel operating system takes the kernel as the processing scenario element and constructs redundancy, heterogeneity, and dynamism on the kernel, so it has the generalized robustness of the DHR architecture. This article analyzes the significance and requirements of OS-level DHR architecture, and systematically explains how the multi-kernel operating system responds to the requirements of OS-level DHR architecture by analyzing the technical routes of multi-kernel operating systems and develops an operating system solution idea for the generalized functionally safety.
- Open Access
- 28 March 2022
- Published by Association for Computing Machinery (ACM)
- p. 443-444
High performance GPU concurrent B+tree
Concurrent B+trees have been widely used in many systems from file systems to databases. With the volume of data requests expanding exponentially, the systems are facing tremendous performance pressure. GPUs have shown their potential to accelerate the concurrent B+trees operations with their high volume of parallel computing resources and large memory bandwidth. In concurrent B+tree, the conflicts should be detected and resolved when multiple concurrent requests are traversing and operating on the tree. However, conflict detection and handling in concurrent B+tree complicates the request processing logic, increases the number of memory accesses and leads to execution path divergence. That leads to performance degradation and increased response time variance. We present a high performance GPU concurrent B+tree. To reduce the performance impact introduced by conflict detection, an optimization is proposed to detect and resolve key conflicts before concurrent requests are issued to the execution phase. Then another optimization is used to reduce structure conflicts and concurrent control overheads. Finally, an optimization is used to reduce structure conflicts and improve memory performance by exploiting the locality among requests. Evaluations on a TITAN V GPU show that our GPU concurrent B+tree is efficient with a throughput of 1.23 billion per second. Compared to a state-of-the-art GPU B+tree system, it can achieve 5.1X speedup and reduce the response time variance from 38% to 4%.
- 28 March 2022
- Published by Association for Computing Machinery (ACM)
- p. 443-444
Open AccessHigh performance GPU concurrent B+tree
Concurrent B+trees have been widely used in many systems from file systems to databases. With the volume of data requests expanding exponentially, the systems are facing tremendous performance pressure. GPUs have shown their potential to accelerate the concurrent B+trees operations with their high volume of parallel computing resources and large memory bandwidth. In concurrent B+tree, the conflicts should be detected and resolved when multiple concurrent requests are traversing and operating on the tree. However, conflict detection and handling in concurrent B+tree complicates the request processing logic, increases the number of memory accesses and leads to execution path divergence. That leads to performance degradation and increased response time variance. We present a high performance GPU concurrent B+tree. To reduce the performance impact introduced by conflict detection, an optimization is proposed to detect and resolve key conflicts before concurrent requests are issued to the execution phase. Then another optimization is used to reduce structure conflicts and concurrent control overheads. Finally, an optimization is used to reduce structure conflicts and improve memory performance by exploiting the locality among requests. Evaluations on a TITAN V GPU show that our GPU concurrent B+tree is efficient with a throughput of 1.23 billion per second. Compared to a state-of-the-art GPU B+tree system, it can achieve 5.1X speedup and reduce the response time variance from 38% to 4%.
- 17 December 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 31  (5) , 1107-1120
Architectural Support for NVRAM Persistence in GPUs
Non-volatile Random Access Memories (NVRAM) have emerged in recent years to bridge the performance gap between the main memory and external storage devices, such as Solid State Drives (SSD). In addition to higher storage density, NVRAM provides byte-addressability, higher bandwidth, near-DRAM latency, and easier access compared to block devices such as traditional SSDs. This enables new programming paradigms taking advantage of durability and larger memory footprint. With the range and size of GPU workloads expanding, NVRAM will present itself as a promising addition to GPU's memory hierarchy. To utilize the nonvolatility of NVRAMs, programs should allow durable stores, maintaining consistency through a power loss event. This is usually done through a logging mechanism that works in tandem with a transaction execution layer which can consist of a transactional memory or a locking mechanism. Together, this results in a transaction processing system that preserves the ACID properties. GPUs are designed with high throughput in mind, leveraging high degrees of parallelism. Transactional memory proposals enable fine-grained transactions at the GPU thread-level. However, with lower write bandwidths compared to that of DRAMs, using NVRAM as-is may yield sub-optimal overall system performance when threads experience long latency. To address this problem, we propose using Helper Warps to move persistence out of the critical path of transaction execution, alleviating the impact of latencies. Our mechanism achieves a speedup of 4.4 and 1.5 under bandwidth limits of 1.6 GB/s and 12 GB/s and is projected to maintain speed advantage even when NVRAM bandwidth gets as high as hundreds of GB/s in certain cases. Due to the speedup, our proposed method also results in reduction in overall energy consumption.
- 17 December 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 31  (5) , 1107-1120
Architectural Support for NVRAM Persistence in GPUs
Non-volatile Random Access Memories (NVRAM) have emerged in recent years to bridge the performance gap between the main memory and external storage devices, such as Solid State Drives (SSD). In addition to higher storage density, NVRAM provides byte-addressability, higher bandwidth, near-DRAM latency, and easier access compared to block devices such as traditional SSDs. This enables new programming paradigms taking advantage of durability and larger memory footprint. With the range and size of GPU workloads expanding, NVRAM will present itself as a promising addition to GPU's memory hierarchy. To utilize the nonvolatility of NVRAMs, programs should allow durable stores, maintaining consistency through a power loss event. This is usually done through a logging mechanism that works in tandem with a transaction execution layer which can consist of a transactional memory or a locking mechanism. Together, this results in a transaction processing system that preserves the ACID properties. GPUs are designed with high throughput in mind, leveraging high degrees of parallelism. Transactional memory proposals enable fine-grained transactions at the GPU thread-level. However, with lower write bandwidths compared to that of DRAMs, using NVRAM as-is may yield sub-optimal overall system performance when threads experience long latency. To address this problem, we propose using Helper Warps to move persistence out of the critical path of transaction execution, alleviating the impact of latencies. Our mechanism achieves a speedup of 4.4 and 1.5 under bandwidth limits of 1.6 GB/s and 12 GB/s and is projected to maintain speed advantage even when NVRAM bandwidth gets as high as hundreds of GB/s in certain cases. Due to the speedup, our proposed method also results in reduction in overall energy consumption.
- 23 September 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 31  (3) , 707-720
A High Throughput B+tree for SIMD Architectures
B+tree is one of the most important data structures and has been widely used in different fields. With the increase of concurrent queries and data-scale in storage, designing an efficient B+tree structure has become critical. Due to abundant computation resources, SIMD architectures provide potential opportunities to achieve high query throughput for B+tree. In this paper, we first identify the gaps between B+tree and SIMD architectures. Based on that, we propose Harmonia to bridge the gaps. In Harmonia, a B+tree structure is divided into a key region and a child region. The key region stores the nodes with its keys. The child region is organized as a prefix-sum array, which only stores each node's first child index. Since the child region is small and the children's index can be retrieved through index computations, most of it can be stored in on-chip caches and achieve good cache locality. To make it more efficient, Harmonia also includes two optimizations: partially-sorted aggregation and narrowed thread-group traversal, which can mitigate divergence and improve resource utilization. Evaluations on a 28-core INTEL CPU show that Harmonia can achieve up to 207 million queries per second, which is about 1.7X faster than that of CPU-based HB+Tree, a recent state-of-the-art solution. And on a Volta TITAN V GPU, it can achieve up to 3.6 billion queries per second, which is about 3.4X faster than that of GPU-based HB+Tree.
- 23 September 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 31  (3) , 707-720
A High Throughput B+tree for SIMD Architectures
B+tree is one of the most important data structures and has been widely used in different fields. With the increase of concurrent queries and data-scale in storage, designing an efficient B+tree structure has become critical. Due to abundant computation resources, SIMD architectures provide potential opportunities to achieve high query throughput for B+tree. In this paper, we first identify the gaps between B+tree and SIMD architectures. Based on that, we propose Harmonia to bridge the gaps. In Harmonia, a B+tree structure is divided into a key region and a child region. The key region stores the nodes with its keys. The child region is organized as a prefix-sum array, which only stores each node's first child index. Since the child region is small and the children's index can be retrieved through index computations, most of it can be stored in on-chip caches and achieve good cache locality. To make it more efficient, Harmonia also includes two optimizations: partially-sorted aggregation and narrowed thread-group traversal, which can mitigate divergence and improve resource utilization. Evaluations on a 28-core INTEL CPU show that Harmonia can achieve up to 207 million queries per second, which is about 1.7X faster than that of CPU-based HB+Tree, a recent state-of-the-art solution. And on a Volta TITAN V GPU, it can achieve up to 3.6 billion queries per second, which is about 3.4X faster than that of GPU-based HB+Tree.