As random walk is a powerful tool in many graph processing, mining and learning applications, this paper proposes an efficient in-memory random walk engine named ThunderRW. Compared with existing parallel systems on improving the performance of a sin
gle graph operation, ThunderRW supports massive parallel random walks. The core design of ThunderRW is motivated by our profiling results: common RW algorithms have as high as 73.1% CPU pipeline slots stalled due to irregular memory access, which suffers significantly more memory stalls than the conventional graph workloads such as BFS and SSSP. To improve the memory efficiency, we first design a generic step-centric programming model named Gather-Move-Update to abstract different RW algorithms. Based on the programming model, we develop the step interleaving technique to hide memory access latency by switching the executions of different random walk queries. In our experiments, we use four representative RW algorithms including PPR, DeepWalk, Node2Vec and MetaPath to demonstrate the efficiency and programming flexibility of ThunderRW. Experimental results show that ThunderRW outperforms state-of-the-art approaches by an order of magnitude, and the step interleaving technique significantly reduces the CPU pipeline stall from 73.1% to 15.0%.
The Terahertz band is envisioned to meet the demanding 100 Gbps data rates for 6G wireless communications. Aiming at combating the distance limitation problem with low hardware-cost, ultra-massive MIMO with hybrid beamforming is promising. However, r
elationships among wavelength, array size and antenna spacing give rise to the inaccuracy of planar-wave channel model (PWM), while an enlarged channel matrix dimension leads to excessive parameters of applying spherical-wave channel model (SWM). Moreover, due to the adoption of hybrid beamforming, channel estimation (CE) needs to recover high-dimensional channels from severely compressed channel observation. In this paper, a hybrid spherical- and planar-wave channel model (HSPM) is investigated and proved to be accurate and efficient by adopting PWM within subarray and SWM among subarray. Furthermore, a two-phase HSPM CE mechanism is developed. A deep convolutional-neural-network (DCNN) is designed in the first phase for parameter estimation of reference subarrays, while geometric relationships of the remaining channel parameters between reference subarrays are leveraged to complete CE in the second phase. Extensive numerical results demonstrate the HSPM is accurate at various communication distances, array sizes and carrier frequencies.The DCNN converges fast and achieves high accuracy with 5.2 dB improved normalized-mean-square-error compared to literature methods, and owns substantially low complexity.
We study the hop-constrained s-t path enumeration (HcPE) problem, which takes a graph $G$, two distinct vertices $s,t$ and a hop constraint $k$ as input, and outputs all paths from $s$ to $t$ whose length is at most $k$. The state-of-the-art algorith
ms suffer from severe performance issues caused by the costly pruning operations during enumeration for the workloads with the large search space. Consequently, these algorithms hardly meet the real-time constraints of many online applications. In this paper, we propose PathEnum, an efficient index-based algorithm towards real-time HcPE. For an input query, PathEnum first builds a light-weight index aiming to reduce the number of edges involved in the enumeration, and develops efficient index-based approaches for enumeration, one based on depth-first search and the other based on joins. We further develop a query optimizer based on a join-based cost model to optimize the search order. We conduct experiments with 15 real-world graphs. Our experiment results show that PathEnum outperforms the state-of-the-art approaches by orders of magnitude in terms of the query time, throughput and response time.
Terahertz (THz) communications with multi-GHz bandwidth are envisioned as a key technology for 6G systems. Ultra-massive (UM) MIMO with hybrid beamforming architectures are widely investigated to provide a high array gain to overcome the huge propaga
tion loss. However, most of the existing hybrid beamforming architectures can only utilize the multiplexing offered by the multipath components, i.e., inter-path multiplexing, which is very limited due to the spatially sparse THz channel. In this paper, a widely-spaced multi-subarray (WSMS) hybrid beamforming architecture is proposed, which improves the multiplexing gain by exploiting a new type of intra-path multiplexing provided by the spherical-wave propagation among k widely-spaced subarrays, in addition to the inter-path multiplexing. The resulting multiplexing gain of WSMS architecture is k times of the existing architectures. To harness WSMS hybrid beamforming, a novel design problem is formulated by optimizing the number of subarrays, subarray spacing, and hybrid beamforming matrices to maximize the spectral efficiency, which is decomposed into two subproblems. An optimal closed-form solution is derived for the first hybrid beamforming subproblem, while a dominant-line-of-sight-relaxation algorithm is proposed for the second array configuration subproblem. Extensive simulation results demonstrate that the WSMS architecture and proposed algorithms substantially enhance the spectral efficiency and energy efficiency.
