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.

Inter-FPGA communication bandwidth has become a limiting factor in scaling memory-intensive workloads on FPGA-based systems. While modern FPGAs integrate high- bandwidth memory (HBM) to increase local memory throughput, network interfaces often lag behind, creating an imbalance between computation and communication resources. Data compression is a technique to increase effective communication bandwidth by reducing the amount of data transferred, but existing solutions struggle to meet the performance and operation latency requirements of FPGA-based platforms. This paper presents a high- throughput lossy compression framework that enables sub-microsecond latency communication in FPGA clusters. The proposed design addresses the challenge of aligning variable-length compressed data with fixed-width network channels by using transpose circuits, memory-bank reordering, and word- wise operations. A run-length encoding scheme with bounded error is employed to compress floating-point and fixed-point data without relying on complex fine-grained bit-level manipulations, enabling low-latency and scalable implementation. The proposed architecture is implemented on a custom Stratix 10 MX2100 FPGA card equipped with eight 50 Gbps network ports and silicon photonics transceivers. The system achieves up to 757 Gbps of aggregate bandwidth per FPGA in collective communication operations. Compression and decompression are performed within 590 ns total latency, while maintaining the quality of results in a GradAllReduce workload for deep learning.

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.

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 A host‐switch graph was originally proposed as a graph that represents a network topology of a computer systems with 1‐port host computers and ‐port switches. It has been studied from both theoretical and practical aspects in terms of the diameter, the average shortest path length, and the performance of real applications. In recent high‐performance computing systems, however, a host computer is connected to multiple switches by using InfiniBand, NVSwitch, or Omni‐Path, and consequently they provide high bandwidths. Since a host‐switch graph cannot represent such systems, this article extends a host‐switch graph so that it can represent such systems. As a result, a host‐switch graph can include multi‐ported hosts. Furthermore, we propose to use multi‐port hosts for reducing the diameter. We show that the diameter minimization is equivalent to solving the degree diameter problem for bipartite graphs of diameter three. Our experimental results show that we can drastically reduce the diameter as well as increasing the bandwidth and improves performance of MPI applications by up to 162% as compared with networks with single‐ported hosts.

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.

This paper aims at establishing a method for designing high-performance network topologies to bridge a gap between theoretical and practical studies. To this end, we present a novel graph called a host-switch graph, which consists of host vertices and switch vertices with maximum degree 1 and$r$, respectively. This graph represents a network topology of a practical parallel/distributed computer system with host computers connected by$r$-port switches. We discuss important metrics for designing high-performance interconnection networks: the host-to-host average shortest path length (h-ASPL) and the bisection width (BiW). In particular, we explore a method for constructing host-switch graphs with low h-ASPL and high BiW that connect the fixed number of hosts via any number of$r$-port switches. We demonstrate that the number of switches that provides the minimum h-ASPL can mathematically be approximated, and the minimum number of switches that provides a certain BiW can experimentally be approximated. On the basis of the approximations, we propose a randomized algorithm for searching host-switch graphs. We then apply the graphs to interconnection networks and compare them with typical network topologies. As compared with the torus, the dragonfly, and the fat-tree, our networks attain higher performance and smaller power and costs.

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.

We introduce a novel graph called a host-switch graph, which consists of host vertices and switch vertices. Using host-switch graphs, we formulate a graph problem called an order/radix problem (ORP) for designing low end-to-end latency interconnection networks. Our focus is on reducing the host-to-host average shortest path length (h-ASPL), since the shortest path length between hosts in a host-switch graph corresponds to the end-to-end latency of a network. We hence define ORP as follows: given order (the number of hosts) and radix (the number of ports per switch), find a host-switch graph with the minimum h-ASPL. We demonstrate that the optimal number of switches can mathematically be predicted. On the basis of the prediction, we carry out a randomized algorithm to find a host-switch graph with the minimum h-ASPL. Interestingly, our solutions include a host-switch graph such that switches have the different number of hosts. We then apply host-switch graphs to interconnection networks and evaluate them practically. As compared with the three conventional interconnection networks (the torus, the dragonfly, and the fat-tree), we demonstrate that our networks provide higher performance while the number of switches can decrease.

With the increasing availability of data generated by scientific instruments and simulations, today, solving many of our most important scientific and engineering problems requires high-end computing systems (HECS)1 that may be able to process and storage a huge amount of data.2 With this landscape, many synergies between extreme-scale computing, simulations, and data intensive applications might arise.(3, 4) However, the high-performance computing and data analysis platforms, paradigms, and tools have evolved in many cases in different fields, having their own specific methodologies, tools, and techniques. We need to evolve systems and paradigms to create High-End Data-Intensive Computing Systems (HEDICS) to create high-end resources that must be powerful enough in a broad sense (computation, storage, I/O capacity, communications, etc), but at the same time have to provide utilities from the Big Data computing (BDC) space to satisfy the data management and analytics needs of near future applications. Future HECS platforms will be likely characterized by a three to four orders of magnitude, increasing in concurrency, a substantially larger storage capacity, and a deepening of the storage hierarchy. Moreover, the advent of the Big Data challenges5 has generated new initiatives closely related to ultrascale computing systems in large scale distributed systems. The current uncoordinated development model of independently applying optimizations at each layer of the system software I/O software stack will not scale to the required levels of distribution, concurrency, storage hierarchy, and capacity.6 Thus, we need reusable, modular, and scalable frameworks for designing high-end reconfigurable computers, including novel data processing building block and innovative programming models. In those aspects, many new topics are open to research: parallel and distributed algorithms for HEDICS; algorithms for aggressive management of information and knowledge from massive data sources; resource management and scheduling in high-end data and computing systems; tools and environments for parallel/distributed high-end software development; new programming models, as well as machine and application abstractions; resilience issues in HEDICS; adaptive software; architectures, networks, and systems suited for extreme-scale and Big Data; massive distributed and parallel data analytics and feature extraction; new I/O and storage systems valid for HEDICS; and novel and redesigned high-end scientific and engineering computing. This special issue is intended to provide an overview of some key topics and state-of-the-art of recent advances in subjects relevant to High-End Data-Intensive Computing Systems. The general objectives are to address, explore, and exchange information on the challenges and current state-of-the-art in HEDICS, new programming models, run-times, and data facilities design and performance, and their application in various science and engineering domains. This special issue includes research papers addressing the state-of-the-art in high-end data-intensive computing systems. A set of carefully selected works was invited based on the original presentations at the 16th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2016),7 which was held in Granada, Spain, December 2016 and the Third International Workshop of Sustainable Ultrascale Network (NESUS 2016),8 held in Sofia, Bulgaria, October 2016. The extended works have been thoroughly reviewed by an international technical reviewing committee, and only nine papers covering a wide range of relevant challenges in HEDICS were selected for this special issue. The manuscripts present research works showing the convergence of High-End Data and Computing Systems, including new frameworks and platforms, system software enhancements, algorithm design and optimization, programming paradigms and techniques, data processing support in high-end computing systems, and run-time support for HEDICS and performance simulations, measurement, and evaluations. The set of accepted papers can be organized under the following key subjects and subsections and are briefly described in the remaining parts of this section. Current parallel and distributed programming frameworks aid developers to a great extent in implementing applications that exploit homogeneous resources. Nevertheless, it is generally accepted that the ability to develop large-scale distributed applications has lagged seriously behind other developments in cyber-infrastructure.9 Thus, developers strongly require additional expertise to properly port and tune their applications to operate efficiently on specific parallel and distributed platforms, which is not straightforward and demands considerable efforts and specific knowledge. One important cause is the lack of high-level parallel pattern abstractions in the existing frameworks. Dolz et al,10 in their paper A Generic Parallel Pattern Interface for Stream and Data Processing, propose GRPPI, a generic and reusable parallel pattern interface for both stream processing and data-intensive C++ applications available for high-end nodes. GRPPI accommodates a layer between developers and existing parallel programming back-ends targeting multi-core processors, such as C++ threads, OpenMP and Intel TBB, and accelerators back-end like CUDA Thrust. Furthermore, thanks to its high-level C++ API and pattern composability features, GRPPI enables users to easily expose parallelism via stand-alone patterns or pattern compositions matching in sequential applications. The authors evaluate this interface using an image processing use case and demonstrate its benefits from the usability, flexibility, and performance points of views. Furthermore, they analyse the impact of using stream and data pattern compositions on CPUs, GPUs, and heterogeneous configurations. To scale to the next level, as high-end data intensive computing systems become more widespread for scientific applications, there is a necessity of simplifying the development, deployment, and execution of complex data analysis applications for scientific discovery. The scientific workflow model is the leading approach for designing and executing data-intensive applications in high-performance computing infrastructures. Commonly, scientific workflows are built by a set of connected tasks generally arranged in a directed acyclic graph style, which communicate through storage abstractions. Regarding the paper A Data-aware Scheduling Strategy for Workflow Execution in Clouds, Marozzo et al11 present the integration between DMCF and Hercules solutions by using a data-aware scheduling strategy for exploiting data locality in data-intensive workflows. The Data Mining Cloud Framework (DMCF) is a system allowing users to design and execute data analysis workflows on cloud platforms, relying on cloud storage services for every I/O operation, while Hercules is an in-memory I/O solution that can be used in DMCF as an alternative to cloud storage services, providing additional performance and flexibility features. The experimental results demonstrate the performance improvements achieved using the proposed data-aware scheduling strategy in the Microsoft Azure cloud platform. In particular, with the new proposed scheduling strategy, the I/O overhead has been reduced by 55% with respect to the Azure storage, leading to a 20% reduction of the total execution time. In spite of former solutions, network traffic is always a major problem in HEDICS due to data movements. In their paper A scalable synthetic traffic model of Graph500 for computer networks analysis, Fuentes et al12 provide a simulation tool for network architects that need to evaluate the suitability of their interconnect for Big Data applications. Their development is a low computation- and memory-demanding synthetic traffic model that emulates the behaviour of the Graph500 communications and is publicly available in an open-source network simulator. The characterization of network traffic is inferred from a profile of several executions of the benchmark with different input parameters, and the equations in the model have been validated against an execution of benchmarks with a different set of parameters to measure also the impact of the node computation capabilities and network characteristics in the execution time of the model. To cope with huge jobs, some organizations use volunteer computing to get computing resources to scientific projects, so that organizations can be able to attain large computing power from volunteer clients instead of making a high investment in infrastructure. However, there are projects, like the ATLAS@Home project,13 in which the number of running jobs has reached a plateau, due to a high load on data servers and networks caused by file transfers. Alonso et al,14 in the paper A New Volunteer Computing Model for Data-Intensive Applications, provide an alternative, named ComBoS, to improve the performance of volunteer computing projects that have reached their limit due to the I/O bottleneck in data servers by having a percentage of the volunteer clients running as data servers, called data volunteers, to reduce the load on data servers. This solution also improves data locality, leveraging the network latencies of closer machines, as shown by the performance increase provides by their solution, applied to three different BOINC projects. Two current trends in Big Data processing have made the usage of GPGPUs very popular in HEDICS: information discovery and deep-learning techniques15 and collective video games.16 In both cases, there is an increasing trend to discharge client nodes by sending bulk computing to heterogeneous high-end computing nodes for data processing. Data compression is an important area in many data management applications, like training of deep learning, where data must be decompressed many times. Nakano et al,17 in their paper Adaptive Loss-Less Data Compression Method Optimized for GPU Decompression, present a novel lossless data compression method, called Adaptive LossLess (ALL) data compression, designed with the objective of performing decompression very efficiently on the GPU. Evaluations of the ALL data compression method against published lossless data compression methods implemented in GPU show improvements between 1.22 and 23.5 times running on the same GPU. Due to the massive extension of many mobile applications, such as sensors and smart phones, it is crucial for HEDICS to offload applications to high-end nodes so that low-power devices can be used as clients. One possible approach to deal with this problem is the solution proposed in the paper Accelerating Linux and Android applications on low-power devices through remote GPGPU offloading by Montella et al.18 They describe the architecture and integration of RAPID, a complete framework suite for computation offloading to help low-powered devices overcome these limitations. RAPID supports CPU and GPGPU computation offloading on Linux and Android devices, providing lightweight secure data transmission of the offloading operations. The proposed framework is highly modular and exposes a rich Application Programming Interface (API) to developers, making it highly versatile while hiding the complexity of the underlying networking layer. The evaluation results show that Java/Android GPGPU code offloading is possible, through a BioSurveillance application, a commercial real-time face recognition application. High-end networked scientific and engineering applications requires usually HPC for numerical computing and large storage capabilities at end nodes. As the problem grows, the scientific community, in its never-ending road of larger and more efficient computational resources, is in need of more efficient implementations that can adapt better to the current parallel platforms and in need of more new solutions for memory problems that are now memory bound. The memory problem is addressed by Valero19 in the paper Reducing Memory Requirements for Large Size LBM Simulations on GPUs, where he proposes some initiatives to minimize the memory requirements of the Lattice- Boltzmann Method for its usage on GPGPUs to run large scale simulations. The proposed approach allows the author to execute bigger simulations on the same platform without additional memory transfers, those achieving a high performance. In particular, the paper presents two new implementations, LBM-Ghost and LBM-Swap, which are deeply analysed, presenting the pros and cons of each of them. The need of parallelization at high-end nodes is addressed in the paper Parallel solvers for fractional power diffusion problems by Starikoviius et al. 20 The authors construct and investigate parallel solvers for problems described by fractional powers of elliptic operators, like fractional diffusion. Three state-of-the-art approaches are used to transform the non-local fractional-order differential problem into local partial differential equation problems formulated in a space of higher dimension. Scalability of the developed parallel algorithms is investigated, and their parallel performance is compared in the paper. Finally, the problem of accuracy and efficiency for statistic distributions is addressed by Monni et al21 in the paper Fitting Long-Tailed Distribution to Empirical Data. The authors discuss about the limits of the analysis of empirical fat-tailed distributions, which can describe a variety of evolving systems, both natural and man-made. An algorithm to fit fat-tailed distributions is presented and tested against samplings of the power law, the Yule, the log-normal, and Weibull distributions. The algorithm is general and can be applied to any numerical dataset. Thus, the authors compute the parameters defining the shape of each distribution and test the results against simulations. Their method with another state-of- the-art technique to estimate the parameters of empirical distributions. The accuracy of the estimations is discussed, and they conclude that their method based on a weighted iterated χ2 test performs better than the other. Power laws can fit a variety of distributions coming from real data, so a systematic approach to the measurement of the accuracy of fitting algorithms is essential. Articles presented in this special issue provide recent advances in some fields related to high-end data-intensive computing systems. They were selected by invitation of best ranked from two conferences and peer reviewed by journal selection. Acceptance rate for the special issue was below 50% of the invited papers. We hope that the ideas presented in this special issue can contribute to this strategically important, exciting, and fast growing research area and will be of interest for readers of the journal. As guest editors of this special issue, we would like to express our gratitude to all of the authors who submitted their papers to this special issue, and to the Reviewers that helped us with their hard work and the feedback provided to the authors. We also wish to express our gratitude to the Editor-in-Chief Geoffrey C. Fox for the opportunity to edit this special issue and his assistance during the special issue preparation. We acknowledge the following Reviewing Committee members: Pawe Czarnul (Poland), Guilherme Dinis (Sweden), Ece Guran Schmidt (Turkey), Massimiliano Ferrara (Italy), Shih-Hao Hung (Taiwan), Florin Isaila (Spain), Dingde Jiang (China), Amin Khan (Portugal), Marcin Kostur (Poland), Kenli Li (China), Francesco Longo (italy), Francesc Lordan (Spain), Najme Mansouri (Iran), Panagiotis Michailidis (Greece), Eike Mueller (UK), Tomas Potuzak (Cezch Republic), Philipp Reinecke (Germany), Francisco Rodrigo (Spain), Gopal Shyam (India), Shengen Yan (China), Wenwu Tang (USA), and Peng Zhang (USA).

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.

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 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 Discrete Memory Machine (DMM) is a theoretical parallel computing model that captures the essence of memory access by a streaming multiprocessor on CUDA-enabled GPUs. The DMM has w memory banks that constitute a shared memory, and each warp of w threads access the shared memory at the same time. However, memory access requests destined for the same memory bank are processed sequentially. Hence, it is very important for developing efficient algorithms to reduce the memory access congestion, the maximum number of memory access requests destined for the same bank. However, it is not easy to minimize the memory access congestion for some problems. The main contribution of this paper is to present novel and practical parallel computing models in which the congestion is small for any memory access requests. We first present the Super Discrete Memory Machine (SDMM), an extended version of the DMM, which supports a super warp with multiple warps. Memory access requests by multiple warps in a super warp are packed through pipeline registers to reduce the memory access congestion. We then go on to apply the random address shift technique to the SDMM. The resulting machine, the Random Super Discrete Memory Machine (RSDMM) can equalize memory access requests by a super warp. Quite surprisingly, for any memory access requests by a super warp on the RSDMM, the overhead of the memory access congestion is within a constant factor of perfectly scheduled memory access. Thus, unlike the DMM, developers of parallel algorithms do not have to consider the memory access congestion on the RSDMM. The congestion on the RSDMM is evaluated by theoretical analysis as well as by experiments.

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.

The main contribution of this work is to propose a distributed on-demand routing and wavelength assignment algorithm for WDM networks. The proposed algorithm, termed WDM-DSR, is capable to select routes and establish light-paths via message exchanges without imposing a major overhead on the network. Also, we show that the proposed scheme can be used to balance the load in a WDM network. The simulation results show that the proposed solution is comparable with the other algorithms that demands for a much higher computational and message costs.

The main contribution of this paper is to present efficient hardware algorithms for the modulo exponentiation PEmod M used in RSA encryption and decryption, and implement them on the FPGA. The key ideas to accelerate the modulo exponentiation are to use the Montgomery modulo multiplication on the redundant radix-64 K number system in the FPGA, and to use embedded 18 times 18-bit multipliers and embedded 18 k-bit block RAMs in effective way. Our hardware algorithms for the modulo exponentiation for R-bit numbers P, E, and M can run in less than (2R + 4)(R/16 + 1) clock cycles and in expected (1.5R + 4)(R/16 +1) clock cycles. We have implemented our modulo exponentiation hardware algorithms on Xilinx VirtexII Pro family FPGA XC2VP30-6. The implementation results shows that our hardware algorithm for 1024-bit modulo exponentiation can be implemented to run in less than 2.521 ms and in expected 1.892 ms.

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.

The main contribution of this paper is to present hardware algorithms for redundant radix-2rnumber system in the FPGA to accelerate Montgomery modulo multiplication with many bits, which have applications in security systems such as RSA encryption and decryption. Quite surprisingly, our hardware algorithm for Montgomery modulo multiplication of two dr-bit numbers can be completed in only d+1 clock cycles. Since most FPGAs have 18-bit multipliers and 18 k-bit block RAMs, it makes sense to let r=16. Our hardware algorithm for Montgomery modulo multiplication for 256-bit numbers runs only 17 clock cycles using redundant radix-64 k (i.e.radix-216) number system. The experimental results for Xilinx Virtex-II Pro Family FPGA XC2VP100-6 show that the clock frequency of our circuit is independent of d. Further, the hardware algorithm for 1024-bit Montgomery modulo multiplication using the redundant number system is 3 times faster than that using the conventional number system. Also, for 256-bit Montgomery modulo multiplication, our hardware algorithm runs in 0.322 mus, while a previously known implementation runs in 1.22 mus although our implementation uses less than a half slices.

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.

The main contribution of this paper is to present hardware algorithms for redundant radix-2rnumber system in the FPGA to speed the arithmetic operations for numbers with many bits, which have applications in security systems such as RSA encryption and decryption. Our hardware algorithms accelerate arithmetic operations including addition, multiplication, and Montgomery modulo multiplication.Quite surprisingly, our hardware algorithms of the multiplication and Montgomery multiplication for two 1024-bit numbers runs only 64 clock cycles using redundant radix-216number system. Also, the experimental results for Xilinx Virtex-II Pro Family FPGA XC2VP100-6 show that the clock frequency of our circuit is independent of the number of bits. The speed up factors of our hardware algorithm using the redundant number system over those using the conventional number system are 8.3 for 1024-bit addition, 3.4 for 1024-bit multiplication, and 2.5 for 1024-bit Montgomery modulo multiplication. Further, for 256-bit Montgomery modulo multiplication, our hardware algorithm runs in 0.38 mus, while a previously known implementation runs in 1.22 mus. Thus, our approach using redundant number system for arithmetic operations is very efficient.

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.

The reconfigurable mesh is a processor array that consists processors arranged in 1-dimensional or 2- dimensional grids with a reconfigurable bus system. The main contribution of this paper is to show initialization algorithms on the 1-dimensional reconfigurable mesh with n processors. We assume that processors are identical, and does not have unique IDs. Initialization is a task that assigns sequential IDs to processors in the reconfigurable mesh. We first show a simple deterministic initialization algorithm for the I-dimensional reconfigurable mesh that runs inO(n) time. This deterministic algorithm is optimal, because no deterministic solution can perform initialization in less thanO(n) time. Quite surprisingly, we show that expected sublinear-time initialization is possible if we use randomized techniques. Our initialization algorithm runs inO((log n + log f) log log n) time with probability at least 1-1/4 for every real number f ges 1. It follows that the initialization algorithm runs in expected O(log n log log n) time. We also proved that any randomized initialization need to run inO(log n) time. Thus, our randomized initialization algorithm running inO(log n log log n) time is very close to a theoretical lower bound Omega(log n) time.

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

Despite the efforts to leverage the network performance through the use of Directional Communications, most protocols still rely on the basic mechanisms employed by the IEEE802.11 standards. While this might be desirable to facilitate compatibility, nodes empowered with directional antennas should be able to explore the benefits of directional communications whenever possible. With that in mind, we propose two mechanisms, termed Adaptive Carrier Sensing and Adaptive Packet Sending, aiming to allow nodes equipped with directional antennas to exploit the advantages of such systems to improve network performance.

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.

The main contribution of this paper is to present an image retrieval system using FPGAs. Given a template image T and a database of a number of Images I1, I2,..., our system lists all images that contain a subimage similar to T. More specifically, a hardware generator in our system creates the Verilog HDL source of a hardware that determines whether Ii has a similar subimage to T for any image Ii and a particular template T. The created Verilog HDL source is embed in an FPGA using the design tool provided by the FPGA vendor. Since the hardware embedded in the FPGA is designed for a particular template T, it is an instance-specific hardware that allows us to achieve extreme acceleration. We evaluate the performance of our image matching hardware using a PCI-connected Xilinx FPGA and a timing analyzer. Since the generated hardware attains up to 3000 speed-up factor over the software solution, our approach is promising.

The main contribution of this work is to propose an efficient parallel prefix sums architecture based on the recently-developed technique of shift switching with domino logic, where the charge/discharge signals propagate along the switch chain producing semaphores in a network that is fast and highly hardware-compact. The proposed architecture for computing the prefix sums of N-1 bits features a total delay of (4 log N + /spl radic/N-2)/sub */T/sub d/, where T/sub d/ is the delay for charging or discharging a row of two prefix sum units of eight shift switches. Our simulation results show that, under 0.8-micron CMOS technology, the delay T/sub d/ does not exceed 1 ns. As it turns out, our design is faster than any design known to us for values on N in the range 1 /spl les/ N /spl les/ 2/sup 10/. Yet, another important and novel feature of the proposed architecture is that it requires very simple controls, partially driven by the semaphores. This significantly reduces the hardware complexity of the design and fully utilizes the inherent speed of the process.

A broadcast communication model (BCM) is a distributed system with no central arbiter populated by n processing units referred to as stations. The stations can communicate by broadcasting/receiving data packets in one of k communication channels. We assume that the stations run on batteries and expands power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate algorithms on the BCM is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the BCM smaller than its own key. The main contribution of the paper is to present an optimal randomized ranking algorithm on the k-channel BCM. Our algorithm solves the ranking problem, with high probability, in O(n/k+log n) time slots with no station being awake for more than O(log n) time slots. We also prove that any randomized ranking algorithm is required to run in expected /spl Omega/(n/k+log n) time slots with at least one station being awake for expected /spl Omega/(log n) time slots. Therefore, our ranking algorithm is optimal.

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. In this work, we focus on single-channel, single-hop radio networks. We assume that time is slotted and all transmissions occur at slot boundaries. In each time slot, the stations transmit on the channel with some probability until, eventually, one of the stations is declared leader. A leader election protocol is said to be uniform if, in each time slot, every station transmits with the same probability. In a seminal paper, Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open for more than 15 years whether Willard's protocol featured the same time performance with "high probability." One of our main contributions is to show that, unfortunately, this is not the case. Specifically, we prove that for every parameter f/spl isin/e/sup O(n)/, in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+/spl Omega/(/spl radic/f) time slots. The highlight of this work is a novel uniform leader election protocol that terminates, with probability exceeding 1-1/f, in log log n+o(log log n)+O(log f) time slots. Finally, we provide simulation results that show that our leader election protocol outperforms Willard's protocol in practice.

The broadcast communication model (BCM, for short) is a distributed system with no central arbiter populated by p stations denoted by S(1),S(2),...,S(p) that communicate by transmitting messages on a communication channel. The stations are assumed to have the computing power of a laptop computer and to be synchronous, in particular, they all run the same program, albeit on different data. We assume that a station is expending power while transmitting or receiving messages. As it turns out, one of the most effective energy-saving strategies is to mandate individual stations to power their transceiver off (i.e., go to sleep) whenever they are not transmitting or receiving messages. Suppose that the p stations of the BCM store collectively n items such that station S(i), (1 /spl les/ i /spl les/ p), stores s/sub i/ items. Each of the items has a unique destination which is the identity of the station to which the item must be routed. The goal is to route all the items to their destinations, while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every routing protocol must take at least n time slots to terminate. Furthermore, station S(i), (1 /spl les/ i /spl les/ p), must be awake for at least s/sub i/ + d/sub i/ time slots, where d/sub i/ denotes the number of items destined for S(i). Since, in the BCM, every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial. An additional complication stems from the inherent asymmetry of the routing problem: no destination knows the identity of the sender, precluding a priori arrangements between senders and receivers. The main contribution of this work is to present an energy-efficient routing protocol for the single-channel, p-station BCM. We show that for every f /spl ges/ 1, the task of routing n items in this model can be completed with probability exceeding 1 - 1/f, in n + O(q + ln f) time slots and that no station S(i), (1 /spl les/ i /spl les/ p), has to be awake for more than s/sub i/ + d/sub i/ + O(q/sub i/ + r/sub i/ log p + log f) time slots, where q/sub i/ is the number of stations that have items destined for S(i), q = q/sub 1/ + q/sub 2/ +/spl middot//spl middot//spl middot/+ q/sub p/, and r/sub i/ is the number of stations for which S(i) has items. Since q/sub i/ /spl les/ d/sub i/, r/sub i/ /spl les/ s/sub i/ and q /spl les/ n, our protocol is close to optimal both in terms of overall completion time and energy efficiency.

In recent years, the areas of mobile computing and wireless networks have seen explosive growth both in terms of the number of services provided and the types of technologies that have become available. Indeed, cellular telephony, radio paging, cellular data, and even rudimentary cellular multimedia services have become commonplace and the demand for enhanced capabilities will continue to grow into the foreseeable future. It is anticipated that, in the not-so-distant future, mobile users will be able to access their data and other services, such as electronic mail, video telephony, stock market news, map services, electronic banking, while on the move. Already today, there are more portable phones than computers connected to the Internet. However, the trend toward the Internet with its protocols around IP as the common basis for all communication applications seems to be quite clear.

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. A leader election protocol is said to be uniform if in each time slot every station transmits with the same probability. In a seminal paper Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open whether Willard's protocol featured the same time performance with "high probability". We propose a uniform leader election protocol that terminates, with probability exceeding 1-1/f for every f/spl ges/1, in log log n+o(log log n)+O(log f) time slots. We also prove that for every f/spl isin/e/sup O(n)/, in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+/spl Omega/(/spl radic/f) time slots. Finally, we provide simulation results that show that our leader election outperforms Willard's leader election protocol in practice.

The main contribution of this work is to present energyefficient protocols that compute the sum of n numbers over any commutative and associative binary operator stored in n wireless sensor nodes arranged in a two-dimensional grid # n. We first present a protocol that computes the sum in O(r 3 ) time slots with no sensor node being awake for more than O(1) time slots, where r is the transmission range of the sensor nodes. We then show a fault-tolerant protocol that computes the sum in the same number of time slots with no sensor node being awake for more than O(log r) time slots.

The main contribution of this work is to show that a number of fundamental and seemingly unrelated problems in database design, pattern recognition, robotics, computational geometry, and image processing can be solved simply and elegantly by stating them as instances of a unifying algorithmic framework that we call the multiple query problem. The multiple query problem (MQ, for short) is a 5-tuple (Q, A, D, /spl phi/, /spl oplus/), where Q is a set of queries, A is a set of items, D is a set of solutions, /spl phi/: Q/spl times/A/spl rarr/D is a function, and /spl oplus/ is a commutative and associative binary operator over D. The input to the MQ problem consists of a sequence Q=of m queries from Q and of a sequence A=of n items from A. The goal is to compute, for every query q/sub i/ (1/spl les/i/spl les/m) its solution defined as /spl phi/(q/sub i/,A)=/spl phi/(q/sub i/,a/sub 1/)/spl oplus//spl phi/(q/sub i/,a/sub 2/)/spl oplus//spl middot//spl middot//spl middot//spl oplus//spl phi/(q/sub i/,a/sub n/). We begin by discussing a generic algorithm that solves a large class of MQ problems in O(/spl radic/m+f(n)) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n, where f(n) is the time necessary to compute the expression d/sub 1/ /spl oplus/ d/sub 2/ /spl oplus//spl middot//spl middot//spl middot//spl oplus/ d/sub n/ with d/sub i/ /spl isin/ D on such a platform. We then go on to show that the MQ framework affords us an optimal algorithm for the multiple point location problem on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. Given a set A of n points and a set Q of m (m/spl les/n) points in the plane, our algorithm reports, in O(/spl radic/m+log log n) time, all points of Q that lie inside the convex hull of A. Quite surprisingly, our algorithm solves the multiple point location problem without computing the convex hull of A which, in itself, takes /spl Omega/(/spl radic/n) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. Finally, we prove an /spl Omega/(/spl radic/m+g(n)) time lower bound for nontrivial MQ problems, where g(n) is the lower bound for evaluating the expression d/sub 1/ /spl oplus/ d/sub 2/ /spl oplus//spl middot//spl middot//spl middot//spl oplus/ d/sub n/ with d/sub i/ /spl isin/ D, on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n.

A radio network (RN, for short) is a distributed system populated by small, hand-held commodity devices running on batteries. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy efficient. One of the most effective energy-saving strategies is to mandate that the stations go to sleep whenever they do not transmit or receive messages. It is well known that a station is expending power while its transceiver is active, that is, while transmitting or receiving a packet. It is perhaps surprising at first that a station is expending power even if it receives a packet that is not destined for it. Since, in single-hop radio networks, every station is within transmission range from every other station, the design of energy-efficient protocols is highly nontrivial. An instance of the permutation routing problem involves p stations of an RN, each storing n/p items. Each item has a unique destination which is the identity of the station to which the item must be routed. The goal is to route all the items to their destinations while expending as little energy as possible. Since, in the worst case, each item must be transmitted at least once, every permutation routing protocol must take n/k time slots. Similarly, each station must be awake for at least n/p time slots to transmit and/or receive packets. Our main contribution is to present an almost optimal energy-efficient permutation routing protocol for a k-channel, a p-station RN that routes n packets in at most (2d+2b+1)n/k+k time slots with no station being awake for more than (4d+7b-1)n/p time slots, where d=[(logp/k)/(logn/p)], b=[(log k)/(logn/p)] and k/spl les//spl radic/(p/2). Since, in most real-life situations, the number n of packets to route, the number p of stations in the RN, and the number k of channels available satisfy the relation k/spl Lt/p/spl Lt/n, it follows that d and b are very small.

A radio network (RN, for short) is a distributed system consisting of n radio stations. The initialization problem is to assign each of the n stations of the RN a unique ID. The initialization problem is non-trivial since the stations are assumed to be indistinguishable. The main contribution of this work is to propose energy-efficient randomized initialization protocols for RNs lacking collision detection capabilities. We show that if the number n of stations is known beforehand, the single-channel RN can be initialized by a protocol that terminates, with probability exceeding 1-1/n, in O(n) time slots, with no station being awake for more than O(log log n) time slots.

A radio network (RN, for short) is a distributed system populated by small, bulk-produced, handheld radio transceivers, running on batteries. Since recharging batteries may not be possible while on mission, it is important to design protocols that are highly energy-efficient. In this work we address the problem of energy-efficient routing in k-channel RNs. An important subproblem is that of permutation routing an instance of which involves p stations each storing n/p items. Since in the worst case each item must be transmitted at least once, every permutation routing protocol must take n/k time slots. Similarly, each station must be awake for at least n/p time slots. Our main contribution is to present an almost optimal energy-efficient permutation routing protocol on the k-channel, p-station RN that routes n items in at most (2d+2b+1)n/k+k time slots, with no station being awake for more than (4d+7b-1)n/p time slots, where d=[log p/k/log n/p], b=[log k/log n/p], and k/spl les//spl radic/(p/2).

We address the problem of designing efficient and scalable hardware-algorithms for computing the sum and prefix sums of a w/sup k/-bit, (k/spl ges/2), sequence using as basic building blocks linear arrays of at most w/sup 2/ shift switches, where w is a small power of 2. An immediate consequence of this feature is that in our designs broadcasts are limited to buses of length at most w/sup 2/. We adopt a VLSI delay model where the "length" of a bus is proportional with the number of devices on the bus. We begin by discussing a hardware-algorithm that computes the sum of a w/sup k/-bit binary sequence in the time of 2k-2 broadcasts, while the corresponding prefix sums can be computed in the time of 3k-4 broadcasts. Quite remarkably, in spite of the fact that our hardware-algorithm uses only linear arrays of size at most w/sup 2/, the total number of broadcasts involved is less than three times the number required by an "ideal" design. We then go on to propose a second hardware-algorithm, operating in pipelined fashion, that computes the sum of a kw/sup 2/-bit binary sequence in the time of 3k+[log/sub w/ k]=3 broadcasts. Using this design, the corresponding prefix sums can be computed in the time of 4k+[log/sub w/ k]-5 broadcasts.

AbstractÐAd hoc networks are self-organizing entities that are deployed on demand in support of various events including collaborative computing, multimedia classroom, disaster-relief, search-and-rescue, interactive mission planning, and law enforcement operations. One of the fundamental tasks that have to be addressed when setting up an ad hoc network (AHN, for short) is initialization. This involves assigning each of the n stations in the AHN a distinct ID number (e.g., a local IP address) in the range from 1 to n. Our main contribution is to propose efficient randomized initialization protocols for AHNs. We begin by showing that if the number 1 n of stations is known beforehand, an n-station, single-channel AHN can be initialized with probability exceeding 1 n,inen‡ p O … n log n† time slots, regardless of whether the AHN has collision detection capability. We then go on to show that even if n is not 1 known in advance, an n-station, single-channel AHN with collision detection can be initialized with probability exceeding 1 n,in

A radio network (RN, for short) is a distributed system consisting of n radio stations. We assume that the stations are small, bulk-produced, hand-held devices running on batteries and cannot be distinguished by serial or manufacturing number. Since recharging batteries may not be possible while on mission, we are interested in designing protocols that are highly energy-efficient. The initialization problem is to assign each of the n stations in the RN a unique ID. The initialization problem is nontrivial since the stations are assumed to be indistinguishable. The problem is fundamental, since practically all communication protocols for RNs proceed under the assumption that the RN has been initialized in advance. The main contribution of this work is to propose energy-efficient randomized initialization protocols for single-hop RNs lacking collision detection capabilities. First, we show that if the number n of stations is known beforehand, the single-channel RN can be initialized by a protocol that terminates, with probability exceeding 1-/sup 1///sub n/ in O(n) time slots, with no station being awake for more than O(log log n) time slots. We then go on to address the multichannel case and show that if k, (k/spl ges/1), channels are available, an n-station RN can be initialized, with probability exceeding 1-/sup 1///sub n/, in O(/sup n///sub k/+log n) time slots, with no station being awake for more than O(log log n) time slots.

The main contribution of this work is to present elegant broadcast-efficient protocols for permutation routing, ranking, and sorting on single-hop Mobile Radio Networks with p stations and k radio channels, denoted by MRN(p,k). Clearly, any protocol performing these tasks on n items must perform /sup n///sub k/ broadcast rounds because each item must be broadcast at least once. We begin by presenting an optimal off-line permutation routing protocol using /sup n///sub k/ broadcast rounds for arbitrary k, p, and n. Further, we show that optimal on-line routing can be performed in /sup n///sub k/ broadcast rounds, provided that either k=1 or p=n. We then go on to develop an online routing protocol that takes 2/sup n///sub k/+k-1 broadcast rounds on the MRN(p,k), whenever k/spl les//spl radic//sup p///sub 2/. Using these routing protocols as basic building blocks, we develop a ranking protocol that takes 2/sup n///sub k/+o(/sup n///sub k/) broadcast rounds as well as a sorting protocol that takes 3/sup n///sub k/+o(/sup n///sub k/) broadcast rounds, provided that k /spl epsiv/ o(/spl radic/n) and p=n. Finally, we develop a ranking protocol that takes 3/sup n///sub k/+o(/sup n///sub k/) broadcast rounds, as well as a sorting protocol that takes 4/sup n///sub k/+o(/sup n///sub k/) broadcast rounds on the MRN(p,k), provided that k/spl les//spl radic//sup p///sub 2/ and p /spl epsiv/ o(n). Featuring very low proportionality constants, our protocols offer a vast improvement over the state of the art.

Consider a set P of points in the plane sorted by the x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be time-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate; this algorithm runs in O(log log n) time using n/logn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp, time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems.

The problem of computing the convex hull of a set of n sorted points in the plane is one of the fundamental tasks in image processing, pattern recognition, cellular network design, and robotics, among many others. Somewhat surprisingly, in spite of a great deal of effort, the best previously known algorithm to solve this problem on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n was running in O(log2 n) time. It was open for more than ten years to obtain an algorithm for this important problem running in sublogarithmic time. Our main contribution is to provide the first breakthrough: we propose an almost optimal convex hull algorithm running in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/n/spl times//spl radic/n. With slight modifications, this algorithm can be implemented to run in O((log log n)/sup 2/) time on a reconfigurable mesh of size /spl radic/n/loglogn/spl times//spl radic/n/loglogn. Clearly, the latter algorithm is work-optimal. We also show that any algorithm that computes the convex hull of a set of n sorted points on an n-processor reconfigurable mesh must take /spl Omega/(log log n) time. Our result opens the door to an entire slew of efficient convex-hull-based algorithms on reconfigurable meshes.

For 2/spl les/k/spl les/n, the k-merge problem is to merge a collection of ksorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it provides a common generalization of both merging and sorting. The main contribution of this work is to give simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models, thus settling the status of the k-merge problem. We first prove that /spl Omega/(n log k) work is required to solve the k-merge problem on the PRAM models. We then show that the EREW-PRAM and both the CREW-PRAM and the CRCW require /spl Omega/(log n) time and /spl Omega/(log log n+log k) time, respectively, provided that the amount of work is bounded by O(n log k). Our first k-merge algorithm runs in /spl Theta/(log n) time and performs /spl Theta/(n log k) work on the EREW-PRAM. Finally, we design a work-time optimal CREW-PRAM k-merge algorithm that runs in /spl Theta/(log log n+log k) time and performs /spl Theta/(n log k) work. This latter algorithm is also work-time optimal on the CREW-PRAM model. Our algorithms completely settle the status of the k-merge problem on the three main PRAM models.

A matrix A of size m/spl times/n containing items from a totally ordered universe is termed monotone if, for every i, j, 1/spl les/i2. In case m=n/sup /spl epsiv// for some constant /spl epsiv/, (0

We present simple and broadcast-efficient ranking and sorting algorithms on the broadcast communication model (BCM, for short) with few communication channels. At the heart of our algorithms is a new and elegant sampling and bucketing scheme whose main feature is that the resulting buckets are well balanced, making costly rebalancing unnecessary. The resulting ranking algorithm uses only 2 n/k+o(n/k) broadcast rounds, while 3 n/k+o(n/k) broadcast rounds are needed for sorting on a L-channel, n-processor BCM whenever k/spl les//spl radic/(n/log n). These bounds are fairly tight, when compared with the trivial lower bound of n/k broadcast rounds necessary to permute n items using k communication channels.

Given a set S of n points in the plane and two directions r/sub 1/ and r/sub 2/, the Angle-Restricted All Nearest Neighbor problem (ARANN, for short) asks to compute, for every point p in S, the nearest point in S lying in the planar region bounded by two rays in the directions r/sub 1/ and r/sub 2/ emanating from p. The ARANN problem generalizes the well-known ANN problem and finds applications to pattern recognition, image processing, and computational morphology. Our main contribution is to present an algorithm that solves an instance of size n of the ARANN problem in O(1) time on a reconfigurable mesh of size n/spl times/n. Our algorithm is optimal in the sense that /spl Omega/(n/sup 2/) processors are necessary to solve the ARANN problem in O(1) time. By using our ARANN algorithm, we can provide O(1) time solutions to the tasks of constructing the Geographic Neighborhood Graph and the Relative Neighborhood Graph of n points in the plane on a reconfigurable mesh of size n/spl times/n. We also show that, on a somewhat stronger reconfigurable mesh of size n/spl times/n/sup 2/, the Euclidean Minimum Spanning Tree of n points can be computed in O(1) time.