ABSTRACT In Quantum chemical computation, numerical schemes such as the Hartree–Fock (HF) and density functional theory (DFT) are widely used to solve the Schrödinger equation numerically, to realize experiment‐free prediction and analysis of key molecular properties such as structure and energy. Computing one‐electron integrals, such as kinetic energy integrals and nuclear attraction integrals, is essential in both HF and DFT to characterize the molecular electronic states. However, as molecules of practical interest grow in size and angular momentum, computing one‐electron orbitals becomes computationally expensive in most cases. Although computing kinetic energy integrals on CPUs is straightforward, bottlenecks in CPU‐GPU data transfer have often been overlooked. In this study, we propose an efficient method to compute both the kinetic‐energy and nuclear‐attractive integrals on GPUs. First, we explicitly and symbolically expand recurrence relations based on the Obara–Saika and McMurchie–Davidson methods to eliminate redundant operations, thus improving computational efficiency. Second, we implemented a hybrid method that selects the best/fastest of both methods depending on the integration task. Third, we achieved further speedups by using CUDA streams to parallelize the execution of multiple kernels and efficiently utilize multiprocessor resources on the GPU. Computational experiments using NVIDIA A100 GPUs and Intel Xeon Gold 6338 CPU on relevant molecules of interest demonstrated the superiority of our one‐electron integral GPU implementations, achieving a speedup of 20.2 times over PySCF, and a speedup of 132.6 times over GPU4PySCF.

ABSTRACT In computational quantum chemistry, the computation of three‐center two‐electron repulsion integrals (also termed three‐center ERIs) is essential for density fitting. Due to the large number of integral elements and the induced combinatorial computational complexity, the community has actively pursued the acceleration/speedup of ERI calculations to achieve pragmatic levels of efficiency. From the perspective of GPU acceleration, atomicAdd is known to incur significant memory overhead: The frequent collisions and retrials of value aggregation in global GPU memory lead to substantial performance degradation. To tackle this issue, we propose new thread mapping strategies for three‐center two‐electron integrals on GPUs, aiming at reducing the computational cost associated with value aggregation. Our methods are based on the idea of suitable substitutions of device‐level reduction ( atomicAdd ) with efficient warp‐ and thread‐level reduction, such as warp‐shuffle and register accumulation. As a result, our computational experiments using an Intel Xeon Gold 6338 CPU, an NVIDIA A100 GPU, and relevant molecules of interest show the superiority against the conventional thread mapping scheme, achieving up to 2.76 speedups to compute three‐center ERIs more efficiently. Moreover, compared to well‐known quantum chemistry software such as PySCF and GPU4PySCF, our method achieved up to speedups over PySCF and up to speedups over GPU4PySCF. Our method has the potential to further enhance the performance, extensibility, and versatility of GPU‐accelerated quantum chemical computations.

ABSTRACT The Boys function, a mathematical integral function, plays a pivotal role and is frequently evaluated in ab initio molecular orbital computations. The main contribution of this paper is to accelerate the bulk evaluation of the Boys function through the effective utilization of GPUs. The proposed GPU implementation addresses GPU‐specific programming issues such as warp divergence and coalesced/stride access to global memory, and we employ the optimal numerical evaluation method from four methods based on input values to ensure efficient computation with sufficient accuracy. Moreover, to consider actual computation of molecular integrals, we have implemented and evaluated the proposed method in two scenarios: single evaluation, which computes a single value of the Boys function for a single input, and incremental evaluation, which computes multiple values of the Boys function incrementally. The execution time of the proposed GPU implementation was evaluated for both scenarios using an NVIDIA A100 Tensor Core GPU. As a result, the GPU‐accelerated bulk evaluation has achieved a throughput of computing the values of the Boys function times per second for the single evaluation and times per second for the incremental evaluation, respectively. Our parallelized CPU and GPU implementation is available at https://github.com/sstsuji/Boys‐function‐GPU‐library .

ABSTRACT An Ising model is a mathematical model defined by an objective function comprising a quadratic formula of multiple spin variables, each taking values of either or . The task of determining a spin value assignment to these variables that minimizes the resulting value of an Ising model is a challenging optimization problem. Recently, quantum annealers, consisting of qubit cells interconnected according to principles of quantum mechanics, have emerged as a solution for tackling such problems. Ising models characterized by fewer quadratic terms are preferable as they reduce the resource requirements of quantum annealers. Additionally, it is advantageous for the absolute values of coefficients associated with linear and quadratic terms to be small to facilitate the discovery of good solutions, given the inherent limitations in the resolution of quantum annealers. The primary contribution of this article lies in presenting Ising models tailored for solving the ‐Queens puzzle. The conventional Ising model for this puzzle involves quadratic terms, with the maximum absolute value of coefficients being . Our novel Ising model significantly reduces the number of quadratic terms to only , with a maximum absolute coefficient of 6. Furthermore, we provide embedding results for a quantum annealer D‐Wave Advantage utilizing a Pegasus graph . We succeeded in embedding our novel Ising model for up to the 21‐Queens puzzle, while the conventional Ising model can be embedded only for up to the 14‐Queens puzzle.

Summary Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.

The past years have seen a flurry of activity in the area of distributed computing and its related fields. Indeed, developments in computer communications and networks enabled the deployment of exciting new areas, including internet of things, vehicular networks, collaborative big data analysis, and so on. The design and implementation of energy efficient future generation communication and networking technologies fostered the development of mobile, pervasive, and large-scale computing technologies. The recent growth of high speed wired/wireless access and LANs, functional wireless terminals such as smart phones and tablets, and cost-effective sensor/tag devices increasingly stimulate the emergence of user-centric network services collecting and exploiting user-provided data. Likewise, general purpose computing on graphics processing unit (GPGPU) has superseded high-performance CPU in several important tasks, including computer graphics, physics calculations, encryption/decryption, and scientific computations. Indeed, GPGPUs are seen as a natural alternative to fulfill the computing needs for artificial intelligence and machine learning applications. Recent developments have shown intensive research activity in these fields. Novel parallel and distributed computational models reflected on the advances in new computational devices and environments such as optical interconnects, programmable logic arrays, networks of workstations, radio communications, mobile computing, DNA computing, quantum computing, sensor networks, and so forth. It is very encouraging to note that the advent of these new models has led to significant advances in the resolution of various difficult problems of practical interest. The International Symposium on Computing and Networking (CANDAR 2019), in its eighth edition, served as a forum for exchanging the latest findings and experiences ranging from theoretical research to practical system development in all aspects of computing and networking. The symposium is meant to bring together researchers and practitioners to share their views in an open and mutually beneficial exchanges of ideas among the participants. This special issue brings selected papers presented at the CANDAR2019 Symposium and its workshops. The first contribution, entitled “Efficient Parallel Implementations to Compute the Diameter of a Graph” by Takafuji et al., presents an efficient implementations of the Blocked Floyd-Warshall algorithm, which uses no barrier synchronization and invokes only one kernel call by using Single Kernel Soft Synchronization (SKSS) techniques. Experimental results using NVIDIA Tesla V100 show that the proposed implementation is 1.05–1.31 times faster than the previously published articles. Also, the authors proposed an efficient GPU implementation to execute the Blocked Floyd-Warshall algorithm for many graphs at the same time. The next contribution is given by Plauth et al., entitled “Improved Data Transfer Efficiency for Scale-Out GPU Workloads using On-the-Fly I/O Link Compression”. The paper evaluates the potential benefits of 842-based On-the-Fly I/O Link Compression in a scale-out scenario using matrix multiplication, a database query, and a text search kernel as common, data-intensive workloads. By augmenting the CloudCL framework with 842-based compression facilities, the paper demonstrates that transparent On-the-Fly I/O Link Compression can yield performance improvements on tested scale-out GPU workloads. In a different context, Farias et al. considered broadcast problem in vehicular networks. More precisely, the paper aims at reducing the rate of periodic messages (i.e., beacons) that report vehicular information required by safety applications. The proposed neighbor congestion avoidance protocol (NCAP) employs a proactive strategy to predict vehicle position using Kalman filter and an efficient event-driven message delivery mechanism. Compared to similar strategies, the authors show that NCAP reduced the number of beacons and event-driven message retransmissions significantly. Bénassy et al. submitted the paper entitled “Eventually Consistent Distributed Ledger Despite Degraded Atomic Broadcast”. The authors denote that distributed ledger or blockchain technologies have been widespread in recent years. This, in turn, motivates malicious users to attempt to break the system or take advantage of it. The paper focus on attacks that may damage underlying networks of distributed ledgers. Underlying networks offer useful communication primitives such as an atomic broadcast. However, such attacks may degrade the property of the primitives turning distributed ledgers relying on the primitives to no longer work. The authors proposed algorithms to make the distributed ledgers that still work even when some attacks degrade the primitives. The next contribution is given by Yasudo et al., entitled “Designing Low-Diameter Interconnection Networks with Multi-ported Host-Switch Graphs”. A host-switch graph represents a network topology of a computer systems with 1-port host computers and ∆-port switches. A host computer is usually connected to multiple switches using InfiniBand, NVSwitch, or Omni-Path to provide high bandwidths. However, as host-switch graph cannot represent such systems, the authors investigate interconnection networks with multi-port hosts by introducing a multi-ported host-switch graph. The paper presents method for minimizing the diameter of switch components by leveraging multi-port hosts. The method builds on the concept that one should maximize the number of switch components with the minimum diameter. The paper shows that the diameter minimization is equivalent to solving the degree diameter problem for bipartite graphs of diameter three. Experimental results show that diameter can be drastically reduced as well as improving bandwidth. The contribution by Matsumura et al., entitled “A Novel Structured Sparse Fully-Connected Layer in Convolutional Neural Networks”, is motivated by the fact that convolutional neural networks (CNNs) has been one of the drivers to support the rapid development of artificial intelligent techniques. However, as the ability of the network increases, the size of the network becomes larger. Hence, reduction of the network size has been presented in the literature. In many cases, the proposed approaches produce an unstructured network which prevents efficient parallel computation. To avoid this problem, the paper presents a novel structured sparse Fully-Connected Layer (FCL) for CNNs. The proposed approach reduces the number of network parameters in the FCLs which occupy a large part of network parameters. Unlike the general FCLs used in the popular CNNs such as AlexNet and VGG-16, the proposed approach reduces the connection between the last convolutional layer and the first FCL. In addition, the paper proposes an efficient implementation for the proposed sparse FCLs on the GPU. The authors evaluated the proposed approach for AlexNet and VGG-16 on ILSVRC-2012 dataset and various small datasets. The contribution by Ashkenazi et al., entitled “Forgive & Forget: Self-Stabilizing Swarms in Spite of Byzantine Robots”, considers the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating, and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. The authors demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane. We would like to express sincere gratitude to all the authors who submitted their valuable contributions to this special issue, as well as to all the experts who participated in the review process. We are immensely grateful to the Editor-in-Chief Prof. David Walker and the former Editor-in-Chief Prof. Geoffrey C. Fox for providing this opportunity to contribute to the Concurrency and Computation: Practice and Expertise journal as well for their invaluable support and guidance during the publication process.

Abstract Stroke‐based rendering is a rendering method that mimics the actual painting technique by drawing a stroke by stroke on a blank canvas image. In this paper, we propose a watercolor image generation method using stroke‐based rendering. The proposed method generates an image that is a good approximation of the input image as well as having the characteristics of a watercolor painting by repeatedly painting strokes while referring to the input image. To generate a high‐quality image, that is, an image that closely resembles an actual watercolor painting, various techniques are employed: modeling of watercolor paper, detailed physical simulation of the movement of water and pigment, strokes using a brush model, among others. The proposed method generates a large number of strokes and performs computationally intensive watercolor simulations for each stroke. Therefore, this paper also presents its parallel algorithm using a Graphics Processing Unit (GPU). We implemented this parallel algorithm on an NVIDIA A100 GPU. The experimental results show that the CPU implementations with sequential and parallel executions take 34,651 and 867 s to generate a 4K‐watercolor image of size , respectively. In contrast, the GPU implementation with parallel execution succeeded in reducing the time to 44 s.

Abstract An independent set of a graph is a subset of the nodes such that no two nodes in it are adjacent. The maximum independent set (MIS) problem is an optimization problem to find a largest independent set. The main contribution of this article is to introduce a generic iterative trial search algorithm that we call iMIS for finding approximate solutions for the MIS problem. The generic algorithm iMIS is designed so that it can be implemented to run on GPUs very efficiently. Since the performance of the algorithm varies depending on its search strategy, we present a hybrid algorithm that combines three strategies of the iMIS such that best one of them for an input graph is automatically selected. We have implemented our hybrid algorithm to run on a multi‐GPU server with eight NVIDIA A100 GPUs. And evaluated the performance for 66 DIMACS benchmark graphs and 78 random graphs with up to 256M nodes. We have also evaluated the performance of three previously published algorithms for the MIS problem and an approach using Gurobi linear programming solver. The experimental results show that our hybrid algorithm can find larger independent sets for all 144 graphs compared to other methods.

Abstract Quadratic unconstrained binary optimization (QUBO) is a combinatorial optimization problem. Since various NP‐hard problems such as the traveling salesman problem can be formulated as a QUBO instance, QUBO is used with a wide range of applications. The main contribution of this article is to propose high‐throughput FPGA implementations for the QUBO solver. We perform the local search using different bit‐selection strategies based on the simulated annealing in the proposed implementation. The hardware is a pipeline structure with no pipeline hazards using multiple instances, where the bit‐flip operation is always performed every clock cycle. We implemented the proposed circuit on Xilinx UltraScale+ FPGA VU9P. The implementation result shows that the circuit can search solutions per second. Besides, by sharing the block RAM that stores a weight matrix, we implemented a dual annealer architecture that has two QUBO solvers into the FPGA. As a result, the dual annealer architecture can search solutions per second.

Abstract Convolutional Neural Networks (CNNs) are one of the factors supporting the rapid development of artificial intelligent techniques. However, as the ability of the network increases, the size of the network becomes larger. Thus far, several works related to reduction of the network size have been tackled. In many cases, these approaches produce an unstructured network which prevents efficient parallel computation. To avoid this problem, we propose a novel structured sparse fully connected layer (FCL) in the CNNs. The aim of our proposed approach is reduction of the number of network parameters in the FCLs which occupy a large part of network parameters. Unlike the general FCLs used in the popular CNNs such as VGG‐16, the proposed approach reduces the connection between the last convolutional layer and the first FCL. In addition, we show an implementation for the proposed sparse FCLs on the GPU using cuBLAS. As a result for ILSVRC‐2012 dataset, the proposed approach achieves a 21.3 times compression with 0.68% top‐1 accuracy and 0.31% top‐5 accuracy decreases for VGG‐16. The implementation of the proposed FCLs achieves speed‐up factor 14.97 and 16.67 for forward and backward propagation compared to that for the noncompressed FCLs, respectively.

Summary The Floyd‐Warshall algorithm is a well‐known algorithm to compute the distance of all pairs of nodes of a graph. The Blocked Floyd‐Warshall algorithm, a variant of the Floyd‐Warshall has been proposed to accelerate the Floyd‐Warshall algorithm by means of a graphics processing unit (GPU) architecture. The previously published GPU implementations for the Blocked Floyd‐Warshall algorithm perform many separated kernel calls for costly barrier synchronization. The main contribution of this article is to present efficient implementations of the Blocked Floyd‐Warshall algorithm, which performs no barrier synchronization and invokes only one kernel call. Experimental results using NVIDIA Tesla V100 show that our implementation runs 1.05‐1.31 times faster than the previously published one. Our implementation with SIMD functions also runs 1.00‐1.28 times faster than it. Second, we propose efficient GPU implementations to execute the Blocked Floyd‐Warshall algorithm for many graphs at the same time. From the experimental results, our single kernel implementation runs 1.03‐1.60 times faster than multiple kernel one. In terms of implementations with SIMD functions, our single kernel implementation runs 1.01‐1.89 times faster than it. We also propose the low‐latency implementations for many graphs. Finally, we implemented the parallel Floyd‐Warshall algorithm on the multicore processors.

Summary Deflate coding is a very popular lossless data compression method used in zlib, gzip (GNU zip), and zip, which performs the LZSS compression algorithm with Huffman coding. Deflate encoding and decoding involve sequential operations and their parallel acceleration using a GPU is quite hard. The main purpose of this paper is to present GPU implementations for encoding and decoding of Deflate coding. For efficient GPU implementations of Deflate coding, we have used multiple small hash tables for finding matching subsequences in the dictionary by multiple threads in parallel and applied the Single Kernel Soft Synchronization (SKSS) technique to fully utilize GPU computing resources. We have also adopted Huffman coding with gap arrays to accelerate parallel Huffman decoding. We have evaluated the performance of our GPU implementations using an NVIDIA A100 GPU and compared them with parallel/sequential Deflate encoding and decoding on the Intel X86 multicore CPUs using multiple threads/a single thread. Our GPU implementation of Deflate decoding is 1.66x–8.33x faster than the multiple thread implementation and 4.13x–36.56x faster than the single thread implementation.

Summary Tile art image generation is one of the non‐photorealistic rendering methods. The generated digital image resembles artistic representation given digital photos and illustrations. The first contribution of this paper is to propose a tile image generation based on the greedy approach. The greedy approach is based on the characteristic of the human visual system to optimize generated images. In addition, to shorten the computation time, we show the parallel algorithm and its GPU acceleration technique. We have implemented it on NVIDIA Tesla V100 GPU. The experimental result shows that the GPU implementation attains a speed‐up factor of 318 and 16.19 over the sequential CPU implementation and the parallel multi‐core CPU implementation with 160 threads, respectively. The second contribution of this paper is to propose an approximation method using machine learning with deep neural networks. After learning the network with the tile art images generated by the greedy approach as training dataset, it can generate tile art images that well‐reproduce the original images with tile patterns. Moreover, we show an additional machine learning technique by repeating the forwarding computation for the generated tile art image as an input image. As a result, using this technique, we can generate a tile art images with clear shape of tiles.

Summary This paper presents efficient FPGA implementations for the Bloom filter, in which a large set P of L‐byte patterns are registered beforehand. Our Bloom filter circuit performs the byte stream pattern test such that it receives an input byte stream t and outputs the bit stream in every clock cycle. Each bit of the output bit stream is 1 if an L‐byte sequence of t starting from the corresponding position is identical with one of the patterns in P. Our circuits use rolling hash functions to compute signatures of all patterns in P registered in Ultra RAMs of the Xilinx UltraScale+ FPGA VU9P. We present two types of implementations, DSP‐based implementation and RAM‐based implementation to compute rolling hash functions of L‐byte sequences using DSP slices and Block RAMs in the FPGA, respectively. The experimental results show that both DSP‐based and RAM‐based Bloom filter circuits for 4800K patterns of length 1024 can perform the byte stream pattern test for 1.1 Gps and 1.3 Gbps input byte streams, respectively, with false positive probability 10−12. Moreover, we can configure DSP‐based and RAM‐based Bloom filter circuits for 100K patterns to work for 54.9 Gbps and 62.2 Gbps input byte streams, respectively, with false positive probability 10−12.

Huffman coding is a fundamental lossless data compression scheme used in many data compression file formats such as gzip, zip, png, and jpeg. Huffman encoding is easily parallelized, because all 8-bit symbols can be converted into codewords independently. On the other hand, since an encoded codeword sequence has no separator to identify each codeword, parallelizing Huffman decoding is a much harder task. This work presents a new data structure called gap array to be attached to an encoded codeword sequence of Huffman coding for accelerating parallel Huffman decoding. In addition, it also shows that GPU Huffman encoding and decoding can be accelerated by several techniques including (1) the Single Kernel Soft Synchronization (SKSS), (2) wordwise global memory access and (3) compact codebooks. The experimental results for 10 files on NVIDIA Tesla V100 GPU show that our GPU Huffman encoding and decoding run 2.87x-7.70x times and 1.26x-2.63x times faster than previously presented GPU Huffman encoding and decoding, respectively. Also, Huffman decoding can be further accelerated by a factor of 1.67x-6450x if a gap array is attached to an encoded codeword sequence. Since the size and computing overhead of gap arrays in Huffman encoding are small, we can conclude that gap arrays should be introduced for GPU Huffman encoding and decoding.

The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.

Summary The bulk execution is to execute some computation for many different inputs in turn or at the same time. The main contribution of this paper is to propose a parallel processing technique for the bulk execution of the dynamic programming using the GPU (Graphics Processing Unit). Especially, we focus on the optimal polygon triangulation problem for a lot of polygons. We consider programming issues of the GPU architecture such as coalesced memory access of the global memory, warp divergence avoidance, and reduction of CUDA kernel calls. In the GPU implementation, we propose two thread assignment methods that efficiently perform the parallel execution with a lot of threads on thousands of cores in the GPU. The experimental results show that our GPU implementation on NVIDIA TITAN V attains a speed‐up factor of up to 106.05 and 26.78 over the single‐thread and 8‐thread CPU implementations on Intel Core i7‐6700K CPU, respectively.

The complete Voronoi map of a binary image with black and white pixels is a matrix of the same size such that each element is the closest black pixel of the corresponding pixel. The complete Voronoi map visualizes the influence region of each black pixel. However, each region may not be connected due to exclave pixels. The connected Voronoi map is a modification of the complete Voronoi map so that all regions are connected. The Euclidean distance map of a binary image is a matrix, in which each element is the distance to the closest black pixel. It has many applications of image processing such as dilation, erosion, blurring effects, skeletonization and matching. The main contribution of this paper is to present simple and fast parallel algorithms for computing the complete/connected Voronoi maps and the Euclidean distance map and implement them in the GPU. Our parallel algorithm first computes the mixed Voronoi map, which is a mixture of the complete and connected Voronoi maps, and then converts it into the complete/connected Voronoi by exposing/hiding all exclave pixels. After that, the complete Voronoi map is converted into the Euclidean distance map by computing the distance to the closest black pixel for every pixel in an obvious way. The experimental results on GeForce GTX~1080 GPU show that the computing time for these conversions is relatively small. The throughput of our GPU implementation for computing the Euclidean distance maps of 2K × 2K binary images is up to 2.08 times larger than the previously published best GPU implementation, and up to 172 times larger than CPU implementation using Intel Core i7-4790.

Summary There is no doubt that data compression is very important in computer engineering. However, most lossless data compression and decompression algorithms are very hard to parallelize, because they use dictionaries updated sequentially. The main contribution of this paper is to present a new lossless data compression method that we call adaptive loss‐less (ALL) data compression. It is designed so that the data compression ratio is moderate, but decompression can be performed very efficiently on the graphics processing unit (GPU). This makes sense for applications such as training of deep learning, in which compressed archived data are decompressed many times. To show the potentiality of ALL data compression method, we have evaluated the running time using five images and five text data and compared ALL with previously published lossless data compression methods implemented in the GPU, Gompresso, CULZSS, and LZW. The data compression ratio of ALL data compression is better than the others for eight data out of these 10 data. Also, our GPU implementation on GeForce GTX 1080 GPU for ALL decompression runs 84.0 to 231 times faster than the CPU implementation on Core i7‐4790 CPU. Further, it runs 1.22 to 23.5 times faster than Gompresso, CULZSS, and LZW running on the same GPU.

Summary Digital halftoning is an important process to convert a grayscale image into a binary image with black and white pixels. Local exhaustive search‐based halftoning is one of the halftoning methods that can generate high‐quality binary images. However, considering the computing time, it is not realistic for most applications. As a first contribution, this paper proposes a graphics processing unit (GPU) implementation for digital halftoning employing local exhaustive search to produce high‐quality binary images. Programming issues of the GPU architecture have been carefully assessed for implementing the proposed method. Experimental results show that the proposed GPU implementation on NVIDIA (Santa Clara, CA, USA) GeForce GTX TITAN X attains a speed‐up factor of up to 48 over a CPU implementation. Our second contribution is a GPU implementation for cluster‐dot halftoning tailored for local exhaustive search. This implementation attains a speed‐up factor of 92 over a sequential CPU implementation. Copyright © 2016 John Wiley & Sons, Ltd.

Summary Several important tasks, including matrix computation, signal processing, sorting, dynamic programming, encryption, and decryption, can be performed by oblivious sequential algorithms. A sequential algorithm is oblivious if an address accessed at each time does not depend on the input data. A bulk execution of a sequential algorithm is to execute it for many independent inputs in turn or in parallel. A number of works have been devoted to design and implement parallel algorithms for a single input. However, none of these works evaluated the bulk execution performance of these algorithms. The first contribution of this paper is to present a time‐optimal implementation for bulk execution of an oblivious sequential algorithm. Our second contribution is to develop a tool, named C2CU, which automatically generates a CUDA C program for a bulk execution of an oblivious sequential algorithm. The C2CU has been used to generate CUDA C programs for the bulk execution of the bitonic sorting, Floyd‐Warshall, and Montgomery modulo multiplication algorithms. Compared to a sequential implementation on a single CPU, the generated CUDA C programs for the above algorithms run, respectively, 199, 54, and 78 times faster.

The main contribution of this paper is to show a new GPU implementation for the digital half toning by the local exhaustive search that can generate high quality binary images. We have considered programming issues of the GPU architecture to implement these two methods on the GPU. The experimental result shows that our GPU implementation for the local exhaustive search on NVIDIA GeForce GTX 980 for a 512×512 gray scale image runs in 732 seconds, while the CPU implementation runs in 37,364 seconds. Thus, our GPU implementation attains a speed-up factor of 50.98. Additionally, we also propose a GPU implementation for the digital half toning by the partial exhaustive search of which the search space of the local exhaustive search is reduced. Similarly, we can accelerate the computation of the partial exhaustive search 30.73 times faster.

This paper presents a FIFO-based parallel merge sorter optimized for the latest FPGA. More specifically, we show a sorter that sorts K keys in latency K+log2K-1 using log2K comparators. It uses K/M +log2K +log2M-1 memory blocks with capacity M to implement FIFOs. It receives K keys one by one in every clock cycle and outputs the sorted sequence of them from K + log2K - 1 clock cycles after. Since K clock cycles are necessary to input all K keys, our sorter is almost optimal in terms of the latency. Also, since the total FIFO capacity is only K +M log2K +M log2M -M and at least K keys must be stored in the sorter, our sorter is also almost optimal in terms of the total FIFO capacity if M is small. This paper also presents top K-sorter, which outputs top K keys in N input keys for any large N. Our top K-sorter runs in latency N + log2K using log2K + 1 comparators. It uses memory blocks of size M and the total FIFO capacity is only 2K+M log2K +M log2M - 2M. Quite surprisingly, the total FIFO capacity is independent of N. Also, since the latency must be at least N, that of our top Ksorter is almost optimal in terms of the latency. Finally, we have implemented our K-sorter and top K-sorter in a Xilinx Virtex-7 FPGA using built-in Distributed RAMs and Block RAMs. The implementation results show that our K-sorter reduces the used memory resources by half, and both K-sorter and top K-sorter are practical and efficient.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of CUDA-enabled GPU architecture. It has multiple streaming multiprocessors with a shared memory, and the global memory that can be accessed by all threads. The HMM has several parameters: the number d of streaming multiprocessors, the number p of threads per streaming multiprocessor, the number w of memory banks of each shared memory and the global memory, shared memory latency l, and global memory latency L. The main purpose of this paper is to discuss optimality of fundamental parallel algorithms running on the HMM. We first show that image convolution for an image with n × n pixels using a filter of size (2v+1) × (2v+1) can be done in O(n2/w+n2L/dp+n2v2/dw+n2v2l/dp) time units on the HMM. Further, we show that this parallel implementation is time optimal by proving the lower bound of the running time. We then go on to show that the product of two n × n matrices can be computed in O(n3/mw+n3L/mdp+n3/dw+n3l/dp) time units on the HMM if the capacity of the shared memory in each streaming multiprocessor is O(m2). This implementation is also proved to be time optimal. We further clarify the conditions for image convolution and matrix multiplication to hide the memory access latency overhead and to maximize the global memory throughput and the parallelism. Finally, we provide experimental results on GeForce GTX Titan to support our theoretical analysis.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computing on CUDA-enabled GPUs. The summed area table (SAT) of a matrix is a data structure frequently used in the area of computer vision which can be obtained by computing the column-wise prefix-sums and then the row-wise prefix-sums. The main contribution of this paper is to introduce the asynchronous Hierarchical Memory Machine (asynchronous HMM), which supports asynchronous execution of CUDA blocks, and show a global-memory-access-optimal parallel algorithm for computing the SAT on the asynchronous HMM. A straightforward algorithm (2R2W SAT algorithm) on the asynchronous HMM, which computes the prefix-sums in every column using one thread each and then computes the prefix-sums in every row, performs 2 read operations and 2 write operations per element of a matrix. The previously published best algorithm (2R1W SAT algorithm) performs 2 read operations and 1 write operation per element. We present a more efficient algorithm (1R1W SAT algorithm) which performs 1 read operation and 1 write operation per element. Clearly, since every element in a matrix must be read at least once, and all resulting values must be written, our 1R1W SAT algorithm is optimal in terms of the global memory access. We also show a combined algorithm ((1 + r)R1W SAT algorithm) of 2R1W and 1R1W SAT algorithms that may have better performance. We have implemented several algorithms including 2R2W, 2R1W, 1R1W, (1 + r)R1W SAT algorithms on GeForce GTX 780 Ti. The experimental results show that our (1 + r)R1W SAT algorithm runs faster than any other SAT algorithms for large input matrices. Also, it runs more than 100 times faster than the best SAT algorithm using a single CPU.

The Hierarchical Memory Machine (HMM) is a theoretical parallel computing model that captures the essence of computation on CUDA-enabled GPUs. The offline permutation is a task to copy numbers stored in an array a of size n to an array b of the same size along a permutation P given in advance. A conventional algorithm can complete the offline permutation by executing b[p[i]] ← a[i] for all i in parallel, where an array p stores the permutation P. This conventional algorithm simply performs three rounds of memory access for reading from a, reading from p, and writing in b. The main contribution of this paper is to present an optimal offline permutation algorithm running in O(n/w + L) time units using n threads on the HMM with width w and latency L. We also implement our optimal offline permutation algorithm on GeForce GTX-680 GPU and evaluate the performance. Quite surprisingly, our optimal offline permutation algorithm achieves better performance than the conventional algorithm in most permutations, although it performs 32 rounds of memory access. For example, the bit-reversal permutation for 4M float (32-bit) numbers can be completed in 780ms by our optimal permutation algorithm, while the conventional algorithm takes 2328ms. We can say that the experimental results of this paper provide a good example of GPU computation showing that a complicated but ingenious implementation with a larger constant factor in computing time can outperform a much simpler conventional algorithm.

Consider the following operation on an arbitrary positive number: if the number is even, divide it by two, and if the number is odd, triple it and add one. The Collatz conjecture assert that, starting from any positive number n, repeated iteration of the operations eventually produces the value 1. The main contribution of this paper is to present hardware-software cooperative approach to verify the Collatz conjecture. The key idea of our approach is to sieve numbers n that produces 1 using a circuit implemented on an FPGA. The numbers that fail to be verified by overflow are reported to the host PC. The host PC verifies those numbers using unlimited bits operations by software. We have implemented 24 coprocessors on the Vertex II family FPGA XC2V3000-4. The experimental results show that our hardware-software cooperative approach can verify 2.89 times 10964-bit numbers per second.

The main contribution of this paper is to present an efficient parallel sorting "psort" compatible with the standard qsort. Our parallel sorting "psort" is implemented such that its interface is compatible with "qsort" in C Standard Library. Therefore, any application program that uses standard "qsort" can be accelerated by simply replacing "qsort" call by our "psort" . Also, "psort" uses standard "qsort" as a subroutine for local sequential sorting. So, if the performance of "qsort" is improved by anyone in the community, then that of our "psort" is also automatically improved. To evaluate the performance of our "psort", we have implemented our parallel sorting in a Linux server with two Intel quad-core processors (i. e. eight processor cores). The experimental results show that our "psort" is approximately 6 times faster than standard "qsort" using 8 processors. Since the speed up factor cannot be more than 8 if we use 8 cores, our algorithm is close to optimal. Also, as far as we know, no previously published parallel implementations achieve a speed up factor less than 4 using 8 cores.

Finding a vast array of applications, the problem of computing the convex hull of a set of sorted points in the plane is one of the fundamental tasks in pattern recognition, morphology and image processing. The main contribution of this paper is to show a simple parallel algorithm for computing the convex hull of a set of n sorted points in the plane and evaluate the performance on the dual quad-core processors. The experimental results show that, our implementation achieves a speed-up factor of approximately 7 using 8 processors. Since the speed-up factor of more than 8 is not possible, our parallel implementation for computing the convex hull is close to optimal. Also, for 2 or 4 processors, we achieved a super linear speed up.

This paper reports the design of two courses, "embedded hardware'' and "embedded software" offered in 2008 spring semester at Hiroshima University. These courses use 16-bit processor TINYCPU, cross assembler TINYASM, and cross compiler TINYC. They are designed very simple and compact: The total number of lines of the source code is only 427. Thus, students can understandthe entire design easily, and can learn the basics of computer and embedded system, including processor architecture, assembler and compiler design, assembler programming in a unified way by experiment.

Connected component labeling is a task that assigns unique IDs to the connected components of a binary image. The main contribution of this paper is to present a hardware connected component labeling algorithm for k-concave binary images designed and implemented in FPGA. Pixels of a binary image are given to the FPGA in raster order, and the resulting labels are also output in the same order. The advantage of our labeling algorithm is small latency and to use a small internal storage of the FPGA. We have implemented our hardware labeling algorithm in an Altera Stratix Family FPGA, and evaluated the performance. The implementation result shows that for a 10-concave binary image of 2048 × 2048, our connected component labeling algorithm runs in approximately 70ms and its latency is approximately 750ns.

Connected component labeling is a task that assigns unique IDs to the connected components of a binary image. The main contribution of this paper is to present a hardware connected component labeling algorithm for k-concave binary images designed and implemented in FPGA. Pixels of a binary image are given to the FPGA in raster order, and the resulting labels are also output in the same order. The advantage of our labeling algorithm is low latency and to use FPGA effectively. We have implemented our hardware labeling algorithm in an Altera Stratix Family FPGA, and evaluated the performance. The implementation result shows that for a 20-concave binary image of 2048 times 2048, our connected component labeling algorithm runs in approximately 72 ms and its latency is approximately 2.9 ms.

Screening is an important task to convert a continuous-tone image into a binary image with pure black and white pixels. The main contribution of this paper is to show a new algorithm for cluster-dot screening using the local exhaustive search. Our new algorithm generates 2-cluster, 3-cluster, and 4-cluster binary images, in which all dots have at least 2, 3, and 4 pixels, respectively. The experimental results show that it produces high quality and sharp cluster-dot binary images. We also implemented it on an FPGA to accelerate the computation and achieved a speedup factor of more than 200 over the software implementations.

An "n choose k" counter (C(n, k) counter for short) is a counter which lists all n-bit numbers with (n - k) 0's and k 1's. The "n choose k" counter has applications to solving combinatorial optimization problems and image processing. The main contribution of this work is to present an efficient hardware implementation of the C(n, k) counter. In some applications, C(n, k) counters are used only for small k. The second contribution is to show more efficient implementations that support C(n, k) counters only for small k. We evaluate the performance of our new implementation and known implementations in terms of the number of used slices and the clock frequency for the Xilinx VirtexII family FPGA XC2V3000-4. Although the theoretical analysis shows that our implementation is not the best, it runs in higher clock frequency using fewer number of slices than the other implementations

Summary form only given. The main contribution of this paper is to show a new approach for FM screening which we call local exhaustive search (LES) method, and to present ways to accelerate the computation using an FPGA. FM screening, as opposed to conventional AM screening, keeps unit dot size when converting an original gray-scale image into the binary image for printing. FM screening pays great attention to generate moire-free binary images reproducing continuous-tone and fine details of original photographic images. Our basic approach for FM screening is to generate a binary image whose projected image onto human eyes is very close to the original image. The projected image is computed by applying a Gaussian filter to the binary image. LES performs an exhaustive search for each of the small square subimages in the binary image and replaces the subimage by the best binary pattern. The exhaustive search is repeated until no more improvement is possible. The experimental results show that LES produces high quality sharp binary images. We also implemented LES on an FPGA to accelerate the computation and achieved a speedup factor of up to 43 over the software implementations.