Summary An out‐of‐core branch‐and‐bound (B&B) method to solve large 0‐1 knapsack problems on a graphics processing unit (GPU) is proposed. Given a large problem that produces many subproblems, the proposed method dynamically swaps subproblems to CPU memory. Because such a CPU‐centric subproblem management scheme increases CPU‐GPU data transfer, we adopt three data‐centric strategies to eliminate this side effect. The first is an out‐of‐order search (O3S) strategy that reduces the data transfer overhead by adaptively transferring subproblems between the CPU and GPU. The second is an explicitly‐managed pipelining strategy that hides the data transfer overhead by overlapping data transfer with GPU‐based B&B operations. The third is a GPU‐based stream compaction strategy that reduces the sparseness of arrays to be transferred. Experimental results demonstrate that the proposed out‐of‐core method stored 41 times as many subproblems as a previous in‐core method that manages subproblems in GPU memory, solving approximately twice as many problem instances on the GPU. In addition, compared to a previous breadth‐first search (BFS) strategy, the proposed O3S strategy achieved an average speedup of 7.5 times.

In this study, to substantially improve the runtimes of exact and approximate string matching algorithms, we propose a tribrid parallel method for bit-parallel algorithms such as the Shift-Or and Wu-Manber algorithms. Our underlying idea is to interpret bit-parallel algorithms as inclusive-scan operations, which allow these bit-parallel algorithms to run efficiently on a graphics processing unit (GPU); we achieve this speed-up here because inclusive-scan operations not only eliminate duplicate searches between threads but also realize a GPU-friendly memory access pattern that maximizes memory read/write throughput. To realize our ideas, we first define two binary operators and then present a proof regarding the associativity of these operators, which is necessary for the parallelization of the inclusive-scan operations. Finally, we integrate the inclusive-scan scheme into a previous segmentation-based scheme to maximize search throughput, identifying the best tradeoff point between synchronization cost and duplicate work. Through our experiments, we compared our proposed method with previous segmentation-based methods and indexing-based sequence aligners. For online string matching, our proposed method performed 6.7-16.7 times faster than previous methods, achieving a search throughput of up to 1.88 terabits per second (Tbps) on a GeForce GTX TITAN X GPU. We therefore conclude that our proposed method is quite effective for decreasing the runtimes of online string matching of short patterns.

This paper presents a source-to-source OpenACC optimizer that automatically optimizes a histogram computation code for a graphics processing unit (GPU). Parallel histogram computation codes typically deploy multiple copies of histograms and update them with atomic operations. This duplication method can be implemented as an OpenACC code. However, the structure of sequential code blocks must be manually rewritten owing to the limitation on OpenACC directives. Such a rewritten code does not always achieve the highest performance on arbitrary platforms, and thus, the duplication method degrades the performance portability of the code. To tackle this issue, we propose an optimizer that identifies histogram-related blocks in a naive OpenACC code and automatically rewrites the detected blocks such that multiple copies of histograms can be exploited for acceleration. In experiments, we apply our optimizer to three practical applications and investigate their performance on three platforms: an NVIDIA GPU, an AMD GPU and an Intel CPU. Experimental results show that our automated approach is useful for OpenACC codes to maximize the performance of histogram computation, and thereby enhancing the performance portability of the code.

BACKGROUND: The Smith-Waterman algorithm is known to be a more sensitive approach than heuristic algorithms for local sequence alignment algorithms. Despite its sensitivity, a greater time complexity associated with the Smith-Waterman algorithm prevents its application to the all-pairs comparisons of base sequences, which aids in the construction of accurate phylogenetic trees. The aim of this study is to achieve greater acceleration using the Smith-Waterman algorithm (by realizing interpair block pruning and band optimization) compared with that achieved using a previous method that performs intrapair block pruning on graphics processing units (GPUs). RESULTS: We present an interpair optimization method for the Smith-Waterman algorithm with the aim of accelerating the all-pairs comparison of base sequences. Given the results of the pairs of sequences, our method realizes efficient block pruning by computing a lower bound for other pairs that have not yet been processed. This lower bound is further used for band optimization. We integrated our interpair optimization method into SW#, a previous GPU-based implementation that employs variants of a banded Smith-Waterman algorithm and a banded Myers-Miller algorithm. Evaluation using the six genomes of Bacillus anthracis shows that our method pruned 88% of the matrix cells on a single GPU and 73% of the matrix cells on two GPUs. For the genomes of the human chromosome 21, the alignment performance reached 202 giga-cell updates per second (GCUPS) on two Tesla K40 GPUs. CONCLUSIONS: Efficient interpair pruning and band optimization makes it possible to complete the all-pairs comparisons of the sequences of the same species 1.2 times faster than the intrapair pruning method. This acceleration was achieved at the first phase of SW#, where our method significantly improved the initial lower bound. However, our interpair optimization was not effective for the comparison of the sequences of different species such as comparing human, chimpanzee, and gorilla. Consequently, our method is useful in accelerating the applications that require optimal local alignments scores for the same species. The source code is available for download from http://www-hagi.ist.osaka-u.ac.jp/research/code/.

SUMMARY This paper proposes a parallel scheme for accelerating parameter sweep applications on a graphics processing unit. By using hundreds of cores on the graphics processing unit, we found that our scheme simultaneously processes multiple parameters rather than a single parameter. The simultaneous sweeps exploit the similarity of computing behaviors shared by different parameters, thus allowing memory accesses to be coalesced into a single access if similar irregularities appear among the parameters’ computational tasks. In addition, our scheme reduces the amount of off‐chip memory access by unifying the data that are commonly referenced by multiple parameters and by placing the unified data in the fast on‐chip memory. In several experiments, we applied our scheme to practical applications and found that our scheme can perform up to 8.5 times faster than a naive scheme that processes a single parameter at a time. We also include a discussion on application characteristics that are required for our scheme to outperform the naive scheme. Copyright © 2013 John Wiley & Sons, Ltd.

In this paper, we propose an efficient acceleration method for the nonrigid registration of multimodal images that uses a graphics processing unit. The key contribution of our method is efficient utilization of on-chip memory for both normalized mutual information (NMI) computation and hierarchical B-spline deformation, which compose a well-known registration algorithm. We implement this registration algorithm as a compute unified device architecture program with an efficient parallel scheme and several optimization techniques such as hierarchical data organization, data reuse, and multiresolution representation. We experimentally evaluate our method with four clinical datasets consisting of up to 512 × 512 × 296 voxels. We find that exploitation of on-chip memory achieves a 12-fold increase in speed over an off-chip memory version and, therefore, it increases the efficiency of parallel execution from 4% to 46%. We also find that our method running on a GeForce GTX 580 card is approximately 14 times faster than a fully optimized CPU-based implementation running on four cores. Some multimodal registration results are also provided to understand the limitation of our method. We believe that our highly efficient method, which completes an alignment task within a few tens of seconds, will be useful to realize rapid nonrigid registration.

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.

SUMMARY This paper presents a cooperative multitasking method for concurrent execution of scientific and graphics applications on the graphics processing unit (GPU). Our method is designed to accelerate compute unified device architecture‐based applications using idle GPU cycles in the office. To prevent significant slow‐down of graphics applications, the method divides scientific tasks into smaller pieces, which are then sequentially executed at the appropriate intervals. The method also has flexibility in finding the best tradeoff point between scientific applications and graphics applications. Experimental results show that the proposed method is useful to control the frame rate of the graphics application and the throughput of the scientific application. For example, biological sequence alignment can be processed at approximately 30% of the dedicated throughput while achieving interactive rendering at 58 frames per second. We also show that matrix multiplication can be efficiently processed at 60% of the dedicated throughput during word processing and web browsing. Copyright © 2011 John Wiley & Sons, Ltd.

In this paper, we propose a Fine Grained Cycle Sharing (FGCS) system capable of exploiting idle Graphics Processing Units (GPUs) for accelerating sequence homology search in local area network environments. Our system exploits short idle periods on GPUs by running small parts of guest programs such that each part can be completed within hundreds of milliseconds. To detect such short idle periods from the pool of registered resources, our system continuously monitors keyboard and mouse activities via event handlers rather than waiting for a screensaver, as is typically deployed in existing systems. Our system also divides guest tasks into small parts according to a performance model that estimates execution times of the parts. This task division strategy minimizes any disruption to the owners of the GPU resources. Experimental results show that our FGCS system running on two nondedicated GPUs achieves 111-116 percent of the throughput achieved by a single dedicated GPU. Furthermore, our system provides over two times the throughput of a screensaver-based system. We also show that the idle periods detected by our system constitute half of the system uptime. We believe that the GPUs hidden and often unused in office environments provide a powerful solution to sequence homology search.

This paper proposes a parallelization scheme for parameter sweep (PS) applications using the compute unified device architecture (CUDA). Our scheme focuses on PS applications with irregular access patterns, which usually result in lower performance on the GPU. The key idea to resolve this irregularity is to exploit the similarity of data accesses between different parameters. That is, the scheme simultaneously processes multiple parameters instead of a single parameter. This simultaneous sweep allows data accesses to be coalesced into a single access if the irregularity appears similarly at every parameter. It also reduces the amount of off-chip memory access by using fast on-chip memory for the data commonly accessed for multiple parameters. As a result, the scheme achieves up to 4.5 times higher performance than a naive scheme that processes a single parameter by a kernel invocation.

Exploiting the graphics processing unit (GPU) is useful to obtain higher performance with a less number of host machines in grid systems. One problem in GPU-accelerated grid systems is the lack of efficient multitasking mechanisms. In this paper, we propose a cooperative multitasking method capable of simultaneous execution of a graphics application and a CUDA-based scientific application on a single GPU. To prevent significant performance drop in frame rate, our method (1) divides scientific tasks into smaller subtasks and (2) serially executes them at the appropriate intervals. Experimental results show that the proposed method is useful to control the frame rate of the graphics application and the throughput of the scientific application. For example, matrix multiplication can be processed at 50% of the dedicated throughput while achieving interactive rendering at 54 frames per second.

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.

We describe a general purpose master-worker parallel computation Python module called PyMW. PyMW is intended to support rapid development, testing and deployment of large scale master-worker style computations on a desktop grid or volunteer computing environment. This module targets non-expert computer users by hiding complicated task submission and result retrieval procedures behind a simple interface. PyMW also provides a unified interface to multiple computing environments with easy extension to support additional environments. In this paper, we describe the internal structure and external interface to the PyMW module and its support for the Condor computing environment and the Berkeley Open Infrastructure for Network Computing (BOINC) platform. We demonstrate the effectiveness and scalability of PyMW by performing master-worker style computations on a desktop grid using Condor and a BOINC volunteer computing project.

This paper presents a parallel system capable of accelerating biological sequence alignment on the graphics processing unit (GPU) grid. The GPU grid in this paper is a desktop grid system that utilizes idle GPUs and CPUs in the office and home. Our parallel implementation employs a master-worker paradigm to accelerate Liu's OpenGL-based algorithm that runs on a single GPU. We integrate this implementation into a screensaver-based grid system that detects idle resources on which the alignment code can run. We also show some experimental results comparing our implementation with three different implementations running on a single GPU, a single CPU, or multiple CPUs. As a result, we find that a single non-dedicated GPU can provide us almost the same throughput as two dedicated CPUs in our laboratory environment, where GPU-equipped machines are ordinarily used to develop GPU applications.

Internet based volunteer computing projects such as SETI@home are currently restricted to performing coarse grained, embarrassingly parallel master-worker style tasks. This is partly due to the “pull” nature of task distribution in volunteer computing environments, where workers request tasks from the master rather than the master assigning tasks to arbitrary workers. In this paper we propose algorithms for computing batches of medium grained tasks with deadlines in pull-style volunteer computing environments. We develop models of unreliable workers based on analysis of trace data from an actual volunteer computing project. These models are used to develop algorithms for task distribution in volunteer computing systems with a high probability of meeting batch deadlines. We develop algorithms for perfectly reliable workers, computation-reliable workers and unreliable workers. Finally, we demonstrate the effectiveness of the algorithms through simulations using traces from actual volunteer computing environments.

This paper describes a design and implementation of the Smith-Waterman algorithm accelerated on the graphics processing unit (GPU). Our method is implemented using compute unified device architecture (CUDA), which is available on the nVIDIA GPU. The method efficiently uses on-chip shared memory to reduce the data amount being transferred between off-chip memory and processing elements in the GPU. Furthermore, it reduces the number of data fetches by applying a data reuse technique to query and database sequences. We show some experimental results comparing the proposed method with an OpenGL-based method. As a result, the speedup over the OpenGL-based method reaches a factor of 6.4 when using amino acid sequence database.We also find that shared memory reduces the amount of data fetches to 1/140, providing a peak performance of 5.65 giga cell updates per second (GCUPS). This performance is approximately three times faster than a prior CUDA-based implementation.

Internet based volunteer computing projects such as SETI@home are currently restricted to performing coarse grained, embarrassingly parallel tasks. This is partly due to the "pull" nature of task distribution in volunteer computing environments, where workers request tasks from the master rather than the master assigning tasks to arbitrary workers. In this paper we develop algorithms for computing batches of medium grained tasks with soft deadlines in pull- style volunteer computing environments. Using assumptions about worker availability intervals based on previous studies, we develop models of unreliable workers in volunteer computing environments. These models are used to develop algorithms for task distribution in volunteer computing systems with a high probability of meeting batch deadlines. We develop algorithms for perfectly reliable workers, computation-reliable workers and unreliable workers. The effectiveness of the algorithms is demonstrated by using traces from actual execution environments.

This paper proposes a fast method for computing the costs of all-pairs shortest paths (APSPs) on the graphics processing unit (GPU). The proposed method is implemented using compute unified device architecture (CUDA), which offers us a development environment for performing general-purpose computation on the GPU. Our method is based on Harish's iterative algorithm that computes the cost of the single-source shortest path (SSSP) for every source vertex. We present that exploiting task parallelism in the APSP problem allows us to efficiently use on-chip memory in the GPU, reducing the amount of data being transferred from relatively slower off-chip memory. Furthermore, our task parallel scheme is useful to exploit a higher parallelism, increasing the efficiency with highly threaded code. As a result, our method is 3.4--15 times faster than the prior method. Using on-chip memory, our method eliminates approximately 20% of data loads from off-chip memory.

In this paper, we examine load distributions to minimize total run time in multi-cluster parallel computing algorithms by applying divisible load theory techniques. Even with homogeneous processor speeds, parallel computations in multi-clusters that evenly assign load can run at less than maximum efficiency due to communication heterogeneity. Using a modified version of the LogP parallel computing model, we propose a general technique of assigning load among multiple clusters to minimize the time each processor spends waiting. This technique is used to determine optimal load distribution for spin glass simulation and parallel bucket sort in multi-cluster systems. It also allows fast analysis of the effects of adding processors or clusters to the computation. We experimentally demonstrate the accuracy of our model, and show how it eliminates wait time in multi-cluster parallel computations. Using load distributions derived from our technique results in an execution time decrease of up to 50%, depending on the degree of heterogeneity among clusters and communication characteristics of the computation.

A computational method for implementation of evolution strategies (ES) in grid computing environments is discussed. In this paper, list scheduling with round-robin order replication (RR) is adopted to reduce waiting times due to synchronization in ES. However, RR is suitable for coarse grained tasks. For ES as medium-grained tasks, we propose a new technique to reduce the communication overhead, called the remote work queue (RWQ) method. We then define round robin replication remote work queue (R3Q) as RWQ with RR. Our results show that R3Q can reduce both the synchronous waiting time and communication time, and provides efficient forced termination of tasks compared to other methods.

First, this paper gives a very simple 2-approximation algorithm for scheduling n independent tasks onto a uniform parallel machine with m processors. Best known results so far are (1 + epsiv)-approximation algorithm (03.5L2) time where L is the bit length of the linear program. In contrast, the proposed algorithm runs in O(n log n + mn) time. Next, this paper proves that, if a criterion of a schedule is total computing power consumed by the schedule and accurate performance prediction is possible, the proposed algorithm is a 2-approximation algorithm also for a uniform parallel machine such that processor speed varies over time. Such a parallel machine corresponds to a so-called desktop grid

Graphics processing units (GPUs) are providing increasingly higher performance with programmable internal processors, namely vertex processors (VPs) and fragment processors (FPs). Such newly added capabilities motivate us to perform general-purpose computation on GPUs (GPGPU) beyond graphics applications. Although VPs and FPs are connected in a pipeline, many GPGPU implementations utilize only FPs as a computational engine in the GPU. Therefore, such implementations may result in lower performance due to highly loaded FPs (as compared to VPs) being a performance bottleneck in the pipeline execution. The objective of our work is to improve the performance of GPGPU programs by eliminating this bottleneck. To achieve this, we present a code motion technique that is capable of reducing the FP workload by moving assembly instructions appropriately from the FP program to the VP program. We also present the definition of such movable instructions that do not change the I/O specification between the CPU and the GPU. The experimental results show that (1) our technique improves the performance of a Gaussian filter program with reducing execution time by approximately 40% and (2) it successfully reduces the FP workload in 10 out of 18 GPGPU programs.

Web crawlers collect Web content on the Internet and index them to be retrieved when demanded by a user query. To provide usefulWeb search services, we need a quick crawler that can collect and index the massive amount of content continually accumulating in an efficient way. We introduce a new Web crawler that collects Web content suitable for viewing on mobile terminals such as PDA or cell phones. Moreover, we describe "Mobile Search Service" that provides content suitable for mobile terminals. As of the beginning of 2006, the service offers tens of millions of mobile content entries. In this paper we present the system architecture of our crawler and its performance in actual service.

This paper presents a performance study of a nonrigid registration algorithm for investigating lung disease on clusters. Our algorithm combines two conventional acceleration techniques in order to achieve fast registration: a data-parallel processing technique for accelerating the registration procedure; and a precomputation technique for reducing the computational complexity. We perform some experiments on three clusters with different CPU and network performance in order to make clear what kinds of acceleration techniques and computing environments provide higher performance. The results show that a cluster with Gigabit Ethernet (GbE) network is the most cost effective solution that reduces registration time from ten hours to ten minutes with a linear speedup.

This paper presents a framework for a cluster system that is suited for high-resolution image processing over the Internet during surgery. The system realizes high-performance computing (HPC) assisted surgery, which allows surgeons to utilize HPC resources remote from the operating room. One application available in the system is an intraoperative estimator for the range of motion (ROM) adjustment in total hip replacement (THR) surgery. In order to perform this computation-intensive estimation during surgery, we parallelize the ROM estimator on a cluster of 64 PCs, each with two CPUs. Acceleration techniques such as dynamic load balancing and data compression methods are incorporated into the system. The system also provides a remote-access service over the Internet with a secure execution environment. We applied the system to an actual THR surgery performed at Osaka University Hospital and confirmed that it realizes intraoperative ROM estimation without degrading the resolution of images and limiting the area for estimations.

The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the computing power of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid. A novel criterion of a schedule is proposed. The proposed criterion is called total processor cycle consumption, which is the total number of instructions the grid could compute until the completion time of the schedule. Moreover, for the criterion, this gives a (l+ m(loge(m-1)+1)/n)-approximation algorithm for scheduling n independent coarse-grained tasks with the same length onto a grid with m processors. The proposed algorithm does not use any prediction information on the performance of underlying resources. This result implies a nontrivial result that the computing power consumed by a parameter sweep application can be limited in such a case within (1+m(loge(m-1)+1)/n) times that required by an optimal schedule, regardless how the speed of each processor varies over time

The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the speed of each processor of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid. In contrast, recently the authors proposed the computing power consumed by a schedule as a criterion of the schedule. For the criterion, this Ä Ô Ò ¡Ñ ÐÓ� � Ñ paper gives a Ò-approximation algorithm for scheduling precedence constrained coarsegrained tasks with the same length onto a grid where Ò is the number of tasks, Ñ is the number of processors, and Ä Ô Ò is the length of the critical path of the task graph. The proposed algorithm does not use any prediction information on the performance of underlying resources. Ä Ô Ò is usually a sublinear function of Ò. So, the above performance guarantee converges to one as Ò grows. This result implies a non-trivial result that the computing power consumed by an application on a grid can be limited within Ä Ô Ò ¡Ñ ÐÓ� � Ñ Ò times that required by an optimal schedule in such a case. 1

The bulk synchronous task scheduling problem (BSSPO) is known as an effective task scheduling problem for distributed memory machines. We present a proof of NP-completeness of the decision counterpart of BSSPO, even in the case of makespan of at most five. This implies nonapproximability of BSSPO, meaning that there is no approximation algorithm with performance guarantee smaller than 6/5 unless P = NP. We also give an approximation algorithm with a performance guarantee of two for BSSPO in several restricted cases.

We present a new parallel computational model, named LogGPS, which captures synchronization.

Area and computation time are considered to be important measures with which VLSI circuits are evaluated. In this paper, the area-time complexity for nontrivial n-input m-output Boolean functions, such as a decoder and an encoder, is studied with a model similar to Brent-Kung's model. A lower bound on area-time-product (ATαaα.≥1) for these functions is shown: for example, ATα= ω(2n. nα-l) for an n-input 2V-output decoder, and ATα= ω( n . logα-1n) for an n-input ⌈log n⌉-output encoder. The results shown in this paper are complementary to those by Brent-Kung or Thompson, and are useful for a class of functions of rather simple structures, e.g., a priority encoder, a comparator, and symmetric functions.

Two decision problems related to multivalued dependencies in a relational database are considered. In this paper, an algorithm is presented for deciding whether or not a multivalued dependency can be derived from sets F of functional dependencies and M of multivalued dependencies on a set U of attributes, whose running time is proportional to min $(k^2 |U|,||F \cup M||^2 )$ where k and $|U|$ are the numbers of dependencies in $F \cup M$ and attributes in U, respectively, and $||F \cup M||$ is the size of description of F and M. A related algorithm is also considered which decides whether or not there exists a nontrivial multivalued dependency that is valid in a projection of the original relation.