Decomposing a matrix$\mathbf {A}$into a lower matrix$\mathbf {L}$and an upper matrix$\mathbf {U}$, which is also known as LU decomposition, is an essential operation in numerical linear algebra. For a sparse matrix, LU decomposition often introduces more nonzero entries in the$\mathbf {L}$and$\mathbf {U}$factors than in the original matrix. Asymbolic factorizationstep is needed to identify the nonzero structures of$\mathbf {L}$and$\mathbf {U}$matrices. Attracted by the enormous potentials of the Graphics Processing Units (GPUs), an array of efforts have surged to deploy various LU factorization steps except for the symbolic factorization, to the best of our knowledge, on GPUs. This article introducesgSoFa, the firstGPU-basedsymbolicfactorization design with the following three optimizations to enable scalable LU symbolic factorization fornonsymmetric patternsparse matrices on GPUs. First, we introduce a novel fine-grained parallel symbolic factorization algorithm that is well suited for theSingle Instruction Multiple Thread(SIMT) architecture of GPUs. Second, we tailor supernode detection into a SIMT friendly process and strive to balance the workload, minimize the communication and saturate the GPU computing resources during supernode detection. Third, we introduce a three-pronged optimization to reduce the excessive space consumption problem faced by multi-source concurrent symbolic factorization. Taken together,gSoFaachieves up to 31× speedup from 1 to 44 Summit nodes (6 to 264 GPUs) and outperforms the state-of-the-art CPU project, on average, by 5×. Notably,gSoFaalso achieves up to 47 percent of the peak memory throughput of a V100 GPU in the Summit Supercomputer.

Attracted by the enormous potentials of Graphics Processing Units (GPUs), an array of efforts has surged to deploy Breadth-First Search (BFS) on GPUs, which, however, often exploits the static mechanisms to address the challenges that are dynamic in nature. Such a mismatch prevents us from achieving the optimal performance for offloading graph traversal on GPUs. To this end, we propose XBFS that leverages the runtime optimizations atop GPUs to cope with the nondeterministic characteristics of BFS with the following three techniques: First, XBFS adaptively exploits four either new or optimized frontier queue generation designs to accommodate various BFS levels that present dissimilar features. Second, inspired by the observation that the workload associated with each vertex is not proportional to its degree in bottom-up, we design three new strategies to better balance the workload. Third, XBFS introduces the first truly asynchronous bottom-up traversal which allows BFS to visit vertices for multiple levels at a single iteration with both theoretical soundness and practical benefits. Taken together, XBFS is, on average, 3.5×, 4.9×, 11.2× and 6.1× faster than the state-of-the-art Enterprise, Tigr, Gunrock on a Quadro P6000 GPU and Ligra on a 24-core Intel Xeon Platinum 8175M CPU. Note, the CPU used for Ligra is more expensive than the GPU for XBFS.

The pseudonymous nature of Bitcoin has sparked the twin rivaling researches in Bitcoin community, that is, either protecting or attacking anonymity. In spite of this intense battle, the answer to a primary question is absent – Do Bitcoin users themselves care about anonymity? This paper demystifies this doubt via analyzing the Bitcoin transaction graphs with the following three contributions: 1). We outline three representative metrics that can signify whether users concern about anonymity. 2). We examine the collective trend of anonymity concerns from a macroscope. 3). We pay particular attention on critical addresses in a microscope to unveil their anonymity concerns.This paper arrives at both expected conclusions and unexpected surprises. In particular, the expected ones are: rich addresses concern more about anonymity than poor ones. Miner addresses start caring about anonymity when exchange rate soars. Stock addresses never hide their intent of jump-and-dump. The surprises are: the majority of the users show weak concerns on anonymity. One can easily find both hot and cold wallet addresses owned by big organizations.