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.

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.

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.

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.

In this work we present randomly optimized grid graphs that maximize the performance measure, such as diameter and average shortest path length (ASPL), with subject to limited edge length on a grid surface. We also provide theoretical lower bounds of the diameter and the ASPL, which prove optimality of our randomly optimized grid graphs. We further present a diagonal grid layout that significantly reduces the diameter compared to the conventional one under the edge-length limitation. We finally show their applications to three case studies of off-and on-chip interconnection networks. Our design efficiently improves their performance measures, such as end-to-end communication latency, network power consumption, cost, and execution time of parallel benchmarks.

The k-edge-connectivity augmentation problem of a graph with upper bounds on edge multiplicity is defined as follows: "Given a graph G=(V, E) and a function f: V/spl times/V/spl rarr/Z/sup +/ (nonnegative integers), find an edge set of minimum cardinality among those sets E' such that G'=(V, E/spl cup/E') is k-edge-connected and, for any pair of vertices u, v, the number of edges added between u and v is no more than f(u, v)." In this paper, we first show that this problem is NP-complete. Then we propose three heuristic algorithms and compare their capability through experiment.