We present an enhanced GPU implementation of the H-P sort algorithm, which is a widely used method for integer sorting based on histogram computation and prefix sum calculation. This work extends a previous high-performance GPU version of the algorithm, presented at the 2021 ICPP international conference. Through algorithmic refinements and optimizations, we demonstrate significant performance improvements compared to the conventional H-P sort. It achieves a maximum speedup of 3.45x over conventional H-P Sort. Furthermore, in scenarios where the H-P sort had previously lagged behind the fastest available library, our improved implementation now surpasses it in terms of execution speed. This advancement in GPU-based sorting techniques contributes to more efficient data processing in various computational applications, emphasizing the practical significance of this work.

In this paper, we propose integer sorting algorithms based on histogram and prefix-sums and we show that their GPU-implementations are faster than the fastest sorting GPU-implementations in Thrust and/or CUB library for several input data. In particular, our algorithm is very useful in the cases that the maximum value of input data is smaller than the number of input data and/or the number of kinds of input data is smaller than the maximum value of input data.

In last couple of years, parallel two or many objective MOPSO (Multi-objective Particle Swarm Optimization) have been proposed in literature. Denumerable implementations were published, however they had not achieved faster execution time and good Pareto fronts. They have alluded some limitation of archive handling, picked up nondominated solutions, high dimensional problems and so on for large swarm population. Moreover, none of the researchers have implemented MOPSO and tested the performance for large swarm population and high dimensional problem simultaneously. In particular, they skipped high dimensional problems. This paper presents a faster implementation of parallel MOPSO on a GPU based on the CUDA architecture, which uses coalescing memory access, pseudorandom number generator (PRNG), Thrust library, atomic function, parallel archiving and so on. In addition, our implementation has a positive impact on the performance to solve high dimensional optimization problems with large swarm population. Therefore, our proposed algorithm can be widely used in real optimizing problems. The proposed parallel implementation of MOPSO using a master-slave model provides up to 182 times speedup compared to the corresponding CPU MOPSO.

It is not realistic to connect all of cores in a multicore-processor each other because current multicore-processors have many cores. Therefore there are many studies about network topologies to connect cores. The order/degree problem is one of the tackled problems. It finds graphs with the minimum diameter and the minimum average shortest path length (ASPL) over all graphs for a given number n of vertices and a given degree deg. We present an algorithm to enumerate all of graphs with the minimum diameter and the minimum ASPL over all graphs such that each vertex of torus with n vertices is added edges regularly within degree deg. Also we report optimal graphs for the order/degree problem found by our algorithm.

Genetic algorithms (GAs) have parallelism among applications of genetic operators to individuals, but in order to extract high performance of a GPU, parallelizing each genetic operator is desirable. This paper presents parallelization of the OX (order crossover) operator and experimentally show that our parallelized OX is effective on a GPU based on the CUDA architecture. The experiments with an NVIDIA GeForce GTX580 GPU show that our GPU program for the traveling salesman problem (TSP) is about up to 101.3 times faster than the corresponding CPU program on a single core of 2.67 GHz Intel Xeon X5550.

In this paper, we describe an implementation of Node Histogram Sampling Algorithm (NHBSA) on GPUs with CUDA and apply the algorithm to solve large scale QAP instances. To solve large scale QAP instances, we combined the taboo search with NHBSA. In this implementation, we used an efficient thread assignment method, Move-Cost Adjusted Thread Assignment (MATA), which is proposed in a previous study. Through these experiments, we show that MATA plays an important role for efficient parallel computation in NHBSA. We also show the effectiveness of running NHBSA on multiple GPUs using the island model in independent run mode.

This paper proposes a parallel ant colony optimization (ACO) for solving quadratic assignment problems (QAPs) on a graphics processing unit (GPU) by combining fast, 2-opt local search in compute unified device architecture (CUDA). In 2-opt for QAP, 2-opt moves can be divided into two groups based on computing cost. In one group, the computing cost is O(1) and in the other group, the computing cost is O(n). We compute these groups of 2-opt moves in parallel by assigning the computations to threads of CUDA. In this assignment, we propose an efficient method that can reduce disabling time in each thread of CUDA. The results show GPU computation with 2-opt produces a speedup of x24.6 on average, compared to computation with CPU.

This paper proposes a parallel ant colony optimization (ACO) for solving quadratic assignment problems (QAPs) on a graphics processing unit (GPU) by combining tabu (TS) with ACO in CUDA (ompute unified device architecture). In TS for QAP, all neighbor moves are tested. These moves form two groups based on computing of move cost. In one group, the computing of cost is O(1) and in the other group, the computing of move cost is O(n). We compute these two groups of moves in parallel by assigning the computations to threads of CUDA. In this assignment, we propose an efficient method which we call Move-Cost Adjusted Thread Assignment (MATA). The results with GPU computation with MATA show a promising speedup compared to computation with the CPU. It is also shown that MATA is effective in applying 2-opt local search.

This paper proposes an evolutionary algorithm for solving QAPs with parallel independent run using GPU computation and gives a statistical analysis on how speedup can be attained with this model. With the proposed model, we achieve a GPU computation performance that is nearly proportional to the number of equipped multi-processors (MPs) in the GPUs. We explain these computational results by performing statistical analysis. Regarding performance comparison to CPU computations, GPU computation shows a speedup of x4.4 and x7.9 on average using a single GPU and two GPUs, respectively.

A computational method for the implementation of an evolutionary multi-robotics (EMR) problem in grid computing environments is discussed. Due to the synchronization requirements of Evolutionary Algorithms (EAs), when the EMR problem is deployed in the grid environment there is a higher waiting time overhead because of medium-grained tasks. The round-robin replication remote work queue (R3Q) is adopted to reduce both the synchronous waiting time and communication time. In the current research, the performance of the grid scheduling is evaluated using uniform computational granularity despite that many problems such as EMR have nonuniform computational granularity. Therefore, in order to evaluate R3Q on nonuniform computational granularity, the cooperative object pushing EMR problem is adopted; and R3Q is compared with grid scheduling algorithms Work Queue (WQ), and list scheduling with round-robin order replication (RR). Our results show that R3Q is effective for tasks which have nonuniform computational granularity.

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.

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.

Grid technology has been studied and developed by numerous researchers in recent years. Data in conventional grid environments are changed by using TCP/IP. However, as long as the architecture is based on packet switching, highly efficient computing is difficult to achieve. We thus propose a new architecture, the λ computing environment, where network switches and computing nodes are connected to one another with optical fibers, thereby offering high-performance computing by establishing an optical wavelength path between shared memories on computing nodes. We established the lambda computing environment using the AWG-STAR system, and designed a data-sharing structure for the OpenMP library, which is a parallel-computing programming language utilizing shared memory. Moreover, we evaluated its performance against existing parallel computing in a PC-cluster environment by executing OpenMP applications.

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.

Although BOA is effective at finding solutions for optimization problems, small population sizes in a model can result in premature convergence to a sub-optimal solution. One way of avoiding premature convergence is to increase population diversity with a mutation operator. In our experiments, we compare several mutation operators for use with BOA. We examine in detail the probabilistic model utilizing (PMU) bit flipping mutation operator. We compare the effectiveness of the PMU operator with standard BOA, self-adaptive evolution and local search of substructural neighborhoods.

Web image retrieval is often used to obtain images of what a searcher does not know well. In such situation, existing Web image eetJ?evalsystems are not so usefirl becaiise the retrieval results include almost no information, except images, about the concerned object. Since in general the retrieval results inchrde not onlv relevant inrages but also bwlevant image.?, a searcher is fo~red to check whether the shown images are relevant or not by vi.viting Web page.? which include the slrown images. This is a lime-consuming task because Web pages mav describe information not onlv about the concerned object but also about other topicr This paper describes the design, implernentation. and evaluation of a Web image retrieval system which pmvides a searcher not onlv images but also the corresponding annotations of the images. Otrrsystem can reduce time to check Web pages and can accelerate to collect various knowlerlpe Jim the Web.

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

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 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.