Solid State Drives (SSDs) based on the NVMe Zoned Namespaces (ZNS) interface can notably reduce the costs of address mapping, garbage collection, and over-provisioning by dividing the storage space into multiple zones for sequential writes and random reads. The Log-Structured Merge (LSM) tree, which is extensively used in key-value storage systems, converts random writes to sequential writes, hence a suitable scenario to utilize ZNS SSDs. However, LSM tree associated data significantly varies in lifetime due to the levels and merging mechanisms of the LSM tree. Therefore, without an accurate method to estimate data lifetime, data with disparate lifetimes may be placed in the same zone, thus causing low space utilization and high write amplification within the SSD. To address these issues, the article proposes two data overlapping aware optimizations to realize intelligent data placement: a zone allocation scheme and a garbage collection scheme. The key technique of these optimizations is an accurate data-lifetime estimation by considering both the associated tree level of the data and the data overlapping ratio between the data and those in the neighboring level. Using the estimation technique, the zone allocation optimization can place data with similar lifetimes in the same zone. Besides, the garbage collection optimization can reclaim zones in an adaptive manner based on overlapping ratios to reduce the amount of data migration. Experimental results demonstrate that the optimization schemes effectively reduce garbage collection-incurred data copy by average factors of 2.11× and 1.50× in comparison to a conventional work and a state-of-the-art work, respectively. Consequently, the proposed work successfully alleviates the write amplification effect by 18% and 6%, compared to the conventional work and the state-of-the-art work, respectively.

This article proposes two quantum operation scheduling methods for accelerating parallel state-vector-based quantum circuit simulation using multiple graphics processing units (GPUs). The proposed methods reduce all-to-all communication caused by qubit reordering, which can dominate the overhead of parallel simulation. Our out-of-order approach eliminates redundant reorderings by introducing intentional delays in reordering communications such that multiple reorderings can be aggregated into a single reordering. The delays are carefully introduced based on the principles of time-space tiling, or a cache optimization technique for classical computers, which we use to arrange the execution order of quantum operations. Moreover, we develop these methods tailored for two primary procedures in variational quantum eigensolver simulation: quantum state update (QSU) and expectation value computation (EVC). Our QSU simulation takes an advantage of the hierarchical interconnection of GPU systems to avoid slow inter-node communication. On the other hand, our EVC simulation reduces the number of reorderings by diagonalization of Pauli strings. Experimental validation on 32-GPU executions demonstrates acceleration in QSU and EVC—up to 54× and 1,657×, respectively—compared to an inorder-based method. We believe that our out-of-order approach is useful for accelerating large-scale quantum circuit simulations, including QSU and/or EVC that operate qubits in a regular manner.

We propose an acceleration method for phenotypic analysis of monozygotic twins based on joint investigation of single-nucleotide polymorphisms (SNPs) and methylated cytosine-phosphate-guanine (mCpG) sites. The phenotypic analysis consists of the following two procedures: (1) identification of mCpG-SNP pairs closely located in base sequences and (2) t-tests on the identified mCpG-SNPs. The proposed method accelerates these procedures with bitwise search and batched computation. The bitwise search exploits the bit-level parallelism of the first procedure by simultaneously processing every 64 bases in sequences of over three billion bases. On the other hand, the batched computation exploits the data-parallelism of the second procedure, where millions of small t-tests must be processed for phenotypic analysis. Experimental results show that the proposed method on a single-core CPU is approximately 3.8 times faster than a previous method. Furthermore, the proposed method achieves a 14.6× speedup on two 10-core CPUs. We therefore believe that the proposed method is useful for accelerating genomewide association analysis, where large-scale data should be investigated in short time.

This paper proposes an extension to Apache Spark that provides automated and efficient in-memory cache management based on post-mortem dependency graph analysis. This extension allows programmers to focus on algorithmic issues without code modification for caching decision. We realized this extension with two techniques: (1) a selection algorithm for intermediate data to be cached and (2) a cache replacement algorithm looking ahead to the whole execution. For avoiding all recalculations in case of no cache replacement, the selection algorithm implicitly activates the necessary cache directives. When cache replacement is unavoidable, the cache replacement algorithm prevents frequent cache replacement that came from excessive cache directives. Experimental results demonstrate that machine learning applications on the extended runtime achieved competitive or higher performance up to 1.3 times compared to manually optimized programs, except for very simple cases. We expect that the proposed method is useful to reduce the cache management burden on programmers without regard to the amount of processing data.

Flint is a simulator that numerically integrates heterogeneous biophysical models described by a large set of ordinary differential equations. It uses an internal bytecode representation of simulation-related expressions to handle various biophysical models built for general purposes. We propose two acceleration methods for Flint using a graphics processing unit (GPU). The first method interprets multiple bytecodes in parallel on the GPU. It automatically parallelizes the simulation using a level scheduling algorithm. We implement an interpreter of the Flint bytecode that is suited for running on the GPU, which reduces both the number of memory accesses and divergent branches to achieve higher performance. The second method translates a model into a source code for both the CPU and the GPU through the internal bytecode, which speeds up the compilation of the generated source codes, because the code size is diminished because of bytecode unification. With large models such that tens of thousands or more expressions can be evaluated simultaneously, the translated code running on the GPU achieves computational performance of up to 2.7 higher than that running on a CPU. Otherwise, with small models, the CPU is faster than the GPU. Therefore, the translated code dynamically determines on which to run either the CPU or the GPU by profiling initial few iterations of the simulation.

This paper describes the implementation of a large bandwidth multi-GPU signal processing system for radio astronomy observation. This system performs very large Fast Fourier Transform (FFT) and spectrum analysis to achieve real-time analysis of a large bandwidth spectrum. This is accomplished by implementing a four-step FFT algorithm in Compute Unified Device Architecture (CUDA). The key feature of this implementation is that the data size transferred between CPU and GPU is reduced using redundant calculation. We also apply pipeline execution to our system to minimize idle processor time, even with multiple GPUs on a shared bus. Using a single GPU, this system can analyze 1 GB of signal data (128 MHz bandwidth at 1 Hz resolution in single precision floating-point complex format) in 0.44 seconds. With the multi-GPU setup, using four GPUs enables 4 GB of signal data to be processed in 0.82 seconds. This is equivalent to a processing speed of around 60 GFLOPS. In particular, we focus on using this system in the Search for Extraterrestrial Radio Emissions from Nearby Developed Intelligent Populations (SERENDIP) project. By using multiple GPUs we can get enough practical performance for high bandwidth radio astronomy projects such as SERENDIP.