Search

In this paper, we propose a parallel cellular automaton tumor growth model that includes load balancing of cells distribution among computational threads with the introduction of adjusting parameters. The obtained results show a fair reduction in execution time and improved speedup compared with the sequential tumor growth simulation program currently referenced in tumoral biology. The dynamic data structures of the model can be extended to address additional tumor growth characteristics such as angiogenesis and nutrient intake dependencies.

Kaczmarz algorithm is an iterative projection method for solving system of linear equations that arise in science and engineering problems in various application domains. In addition to classical Kaczmarz, there are randomized and parallel variants. The main challenge of the parallel implementation is the dependency of each Kaczmarz iteration on its predecessor. Because of this dependency, frequent communication is required which results in a substantial overhead. In this study, a new distributed parallel method that reduces the communication overhead is proposed. The proposed method partitions the problem so that the Kaczmarz iterations on different blocks are less dependent. A frequency parameter is introduced to see the effect of communication frequency on the performance. The communication overhead is also decreased by allowing communication between processes only if they have shared non‐zero columns. The experiments are performed using problems from various domains to compare the effects of different partitioning methods on the communication overhead and performance. Finally, parallel speedups of the proposed method on larger problems are presented. [ABSTRACT FROM AUTHOR]

This study presents an asynchronous parallel strategy coordinating central processing unit (CPU) and graphic processing unit (GPU) to accelerate neighborhood operation (NO). Specifically, we propose a data partitioning method called multi-anchor task queuing and a task scheduling method called bi-direction task scheduling, which can support CPU and GPU to find the responsible data blocks rapidly and concurrently handle their tasks via a bi-direction merge. Moreover, we optimize the organization of threads distributed among the CPU and GPU. Experimental results show that when a 1.7 GB raster dataset is processed, the speedup ratio achieved by the proposed parallel algorithm reaches 29.63, which is 19% and 18% higher than those of the GPU and standard asynchronous parallel algorithm, respectively. Additionally, the load balance index is below 0.085, which is significantly better than the value achieved by a conventional algorithm. Thus, the strategy achieves a higher speedup ratio and more adaptable load balance, thereby accelerating the NO more efficiently. Further, the impacts of the data volume, computational intensity, organization mode of the GPU threads, and granularity of the GPU stream on the parallel efficiency are evaluated and discussed. We also test the efficiency of four other common NOs with our strategy. [ABSTRACT FROM AUTHOR]

Currently, lightweight small object detection algorithms for unmanned aerial vehicles (UAVs) often employ group convolutions, resulting in high Memory Access Cost (MAC) and rendering them unsuitable for edge devices that rely on parallel computing. To address this issue, we propose the SOD-YOLO model based on YOLOv7, which incorporates a DSDM-LFIM backbone network and includes a small object detection branch. The DSDM-LFIM backbone network, which combines Deep-Shallow Downsampling Modules (DSD Modules) and Lightweight Feature Integration Modules (LFI Modules), avoids excessive use of group convolutions and element-wise operations. The DSD Module focuses on extracting both deep and shallow features from feature maps using fewer parameters to obtain richer feature representations. The LFI Module, is a dual-branch feature integration module designed to consolidate feature information. Experimental results demonstrate that the SOD-YOLO model achieves an AP50 of 50.7% and a FPS of 72.5 on the VisDrone validation set. Compared to YOLOv7, our model reduces computational costs by 20.25% and decreases the number of parameters by 17.89%. After scaling the number of channels in the model, it achieves an AP50 of 33.4% with an inference time of 27.3ms on the Atlas 200I DK A2. These experimental results indicate that the SOD-YOLO model can effectively perform small object detection tasks in a large number of aerial images captured by UAVs. [ABSTRACT FROM AUTHOR]

Optical network-on-chip (ONoC) is an emerging architecture to realize high-performance and low power consumption for many-core processors. Multicast in ONoC is a vital communication pattern widely used in parallel computing and computational genomics. This paper proposes an efficient scheme for multiple multicast requests in ONoC. Firstly, we design an algorithm to construct two trees for two multicasts without duplicate edges in a mesh topology, and it only uses one wavelength. We propose a graph to represent the relationship between each multicast. Secondly, a group-based wavelength assignment scheme is designed to assign wavelengths for multiple multicasts. Finally, we used data analysis to extract helpful simulation results to form conclusions. The results indicate that our algorithm is superior to other tree-based schemes in communication latency and wavelength number usage. [ABSTRACT FROM AUTHOR]

Zero-knowledge succinct non-interactive proofs (zk-SNARK) have found extensive applications in various fields, including cryptocurrencies, due to their swift and efficient proof verification process. However, the computational intensity of the proof generation process poses a significant challenge, particularly at the number theoretic transform (NTT) stage. This paper proposed a GPU-based acceleration method for NTT computations, named PreNTT, to address this bottleneck. The method employed precomputation and optimization of twiddle factor powers to reduce the parallel computation overhead in NTT. It also introduced dynamic precomputation to enhance the efficiency of these computations. The algorithm made use of dynamic adaptive kernel scheduling, which allocated GPU resources on-chip according to the NTT input size, thereby boosting the computational efficiency for large-scale tasks. Additionally, the approach combined external global data shuffling with internal local data shuffling to avoid memory access conflicts. The use of CUDA multi-stream technology allowed for effective concealment of precomputation times during data transfer and computation processes. Experimental results indicate that the zk-SNARK system utilizing PreNTT achieves a speed-up ratio ranging from 1.7x to 9x in NTT module running times compared to Bellperson, the industryleading system. PreNTT effectively increases the parallelism of the NTT algorithm and reduces the computational overhead in zk-SNARK operations. [ABSTRACT FROM AUTHOR]

This article studies the problem of scheduling independent jobs on parallel machines with a common server, the objective of which is to minimize the makespan. In this case, the common server is responsible for performing the setup operations and, therefore, there must be no conflicts while conducting them. Four alternative time-indexed formulations for the problem are considered and evaluated computationally. Moreover, two algorithms are presented that can significantly improve the performance of the best time-indexed formulation. The results obtained on two benchmark datasets involving up to 100 jobs suggest that the proposed improved algorithms are substantially better than existing approaches. [ABSTRACT FROM AUTHOR]

Many computation tasks in science and engineering with large amount of data involve complex optimization problems for researchers. Nature Inspired based Algorithms (NIAs) are mostly know for solving complex problems in real world but also these algorithms have one of the major drawbacks of computation cost due to complex problems or increase in the dimension of the problems. Hence, several efforts are made to achieve better computation cost by using parallelization in Nature Inspired Algorithms (NIAs). Parallel Nature Inspired Algorithms (P-NIAs) come forward to overcome the cost of these type of optimization problems. Naturally some of the NIAs are inherently parallel and known for fast processing task. This survey presents a systematic review of existing literature related to parallelization in NIAs. We offered a systematic search to identify the literature through well-reputed publications as IEEE, Elsevier, Springer, ACM, Hindawi, Inderscience, and Wiley. Out of 100 studies 77 reputable studies were selected to identify the current research trends, challenges and opportunities for parallelization in NIAs. Moreover, some problems are also discussed related to algorithm's computation and performance. [ABSTRACT FROM AUTHOR]

To enhance solution accuracy and training efficiency in neural network approximation to partial differential equations, partitioned neural networks can be used as a solution surrogate instead of a single large and deep neural network defined on the whole problem domain. In such a partitioned neural network approach, suitable interface conditions or subdomain boundary conditions are combined to obtain a convergent approximate solution. However, there has been no rigorous study on the convergence and parallel computing enhancement on the partitioned neural network approach. In this paper, iterative algorithms are proposed to enhance parallel computation performance in the partitioned neural network approximation. Our iterative algorithms are based on classical additive Schwarz domain decomposition methods. For the proposed iterative algorithms, their convergence is analyzed under an error assumption on the local and coarse neural network solutions. Numerical results are also included to show the performance of the proposed iterative algorithms. [ABSTRACT FROM AUTHOR]

The aim of this paper is to implement the high-order local discontinuous Galerkin method (LDGM) for solving partial integro-differential equations (PIDEs) in two dimensions. Time marching method and the transform-based method known as the non-time marching method can be used to discretize temporal terms. The combination of a small time step size in time marching methods and a high-order scheme in space with many degrees of freedom requires a considerable amount of computational time. In order to address this limitation, we propose an algorithm based on a combination of the Laplace transform and LDGM for solving fourth-order time-fractional (TF) PIDEs with weakly singular kernels. Unlike time-marching approaches, the transform-based method has a much lower computational complexity and can take advantage of parallel computing. A numerical experiment validates the accuracy and applicability of the proposed temporal discretization approach and also shows that k-degree LDG solutions have a k + 1 convergence rate. [ABSTRACT FROM AUTHOR]

Top-K and selection operations are critical in data processing and analysis, and their efficient implementation on GPUs is increasingly important due to the growing demands of data analysis. Existing methods, primarily relying on the bucket partition execution model, encounter challenges such as uneven bucket distribution and latency in merging processes. To address these issues, we introduce a novel Split-Bucket Partition (SBP) execution model that specifically addresses these challenges. Additionally, we propose task and control flow optimizations targeted at top-K and selection algorithms, which further contribute to performance improvements. Our optimized algorithms significantly outperform existing approaches, delivering performance gains of up to 2.3 times and 1.6 times for different bucket partitioning rules. Our algorithms show robust performance improvements in non-uniform data scenarios, with gains ranging from 1.9 times to 15.5 times. However, it should be noted that the SBP model has limitations related to shared memory and register utilization, potentially impacting performance. Tests on TU102 and A100 GPU architectures validate the effectiveness of our approach, achieving a maximum speedup of 2.9 times. The study suggests that while the SBP model is effective for top-K and selection algorithms, it also holds promise for other computational tasks, setting the stage for future research. [ABSTRACT FROM AUTHOR]

This paper introduces a parallel implementation of an exact two-phase method for solving the bi-objective knapsack problem on a CPU-GPU system. We utilize the Branch-and-Bound procedure in both phases, along with a highly efficient reduction technique to generate all efficient solutions. However, in the first phase, we focus on identifying all supported extreme efficient solutions, followed by reducing the dimension of the problem using an object efficiency reduction algorithm. The second phase is responsible for generating all unsupported efficient solutions. We develop a combined algorithm incorporating both phases, which is implemented in the CUDA language. Our study investigates the impact of parallel computing performance on various numerical instances compared to other exact methods in the literature. Additionally, we confirm the effectiveness of our proposed parallel-solving method by testing uncorrelated instances. [ABSTRACT FROM AUTHOR]

The parallel computing power of quantum computing and the special properties of qubits provide an effective solution for image processing tasks. This paper presents a quantum image encryption algorithm based on Fisher–Yates algorithm and Logistic mapping. Firstly, the Fisher–Yates algorithm is used to generate three key sequences, one of which is used to encode the coordinate qubits of the image. Using the other two keys and the preset rules, the quantum coordinate scrambling operation is designed based on the encoded coordinate qubit, which effectively scrambles the spatial information of the plaintext image. Next, another set of key sequences is generated, one of which is used to encode the color qubits of the image. Using two other key sequences and different rules, a qubit plane scrambling operation based on coded color qubits is designed, and the color information of image is scrambled successfully. Finally, the quantum key image is generated based on Logistic mapping, and the key image is scrambled based on Fisher–Yates algorithm to improve the key complexity. The final ciphertext image is obtained by performing XOR operation between the original image and the scrambled key image. The complete quantum circuit diagram of the scheme is given in this paper. The experimental results and security analysis prove the effectiveness of the scheme, which provides a large key space and the computational complexity is only O(n). [ABSTRACT FROM AUTHOR]

The study proposes two innovative algorithms in the field of multi-beam echo sounder (MBES) simulation: distance-aided sound ray marching (DASRM) and height-aided sound ray marching (HASRM). These algorithms aim to enhance the efficiency and accuracy of MBES simulations, particularly when dealing with long-distance propagation and real-time processing limitations. DASRM addresses issues related to simulation accuracy by efficiently utilizing the KD-tree for spatial indexing and intersection detection instead of the signed distance field (SDF). Building upon the further analysis of DASRM, HASRM is proposed, which improves the search strategy for ray intersections and utilizes a height field pyramid for sampling and retrieval, thereby reducing memory usage while enhancing indexing efficiency. The experimental results demonstrate that both algorithms significantly outperform traditional methods in terms of simulation time, with HASRM exhibiting particular advantages in parallel computing due to its data structure and improved strategies. Additionally, DASRM is well suited for applications requiring complex scene construction, while HASRM proves especially effective in simulating MBES with a focus on underwater terrain due to its effectiveness in handling large incident angles and long-distance propagation. [ABSTRACT FROM AUTHOR]

The article outlines a contemporary method for creating software for multi-processor computers. It describes the identification of parallelizable sequential code structures. Three structures were found and then carefully examined. The algorithms used to determine whether or not certain parts of code may be parallelized result from static analysis. The techniques demonstrate how, if possible, existing sequential structures might be transformed into parallel-running programs. A dynamic evaluation is also a part of our process, and it can be used to assess the efficiency of the parallel programs that are developed. As a tool for sequential programs, the algorithms have been implemented in C#. All proposed methods were discussed using a common benchmark.

Parallel computing is a current algorithmic approach to looking for efficient solutions; that is, to define a set of processes in charge of performing at the same time the same task. Advances in hardware permit the massification of accessibility to and applications of parallel computing. Nonetheless, some algorithms include steps that require or depend on the results of other steps that cannot be parallelized. Speculative computing allows parallelizing those tasks and reviewing different execution flows, which can involve executing invalid steps. Speculative computing solutions should reduce those invalid flows. Product configuration refers to selecting features from a set of available options respecting some configuration constraints; a not complex task for small configurations and models, but a complex one for large-scale scenarios. This article exemplifies a videogame product line feature model and a few configurations, valid and non-valid, respectively. Configuring products of large-scale feature models is a complex and time-demanding task requiring algorithmic solutions. Hence, parallel solutions are highly desired to assist the feature model product configuration tasks. Existing solutions follow a sequential computing approach and include steps that depend on others that cannot be parallelized at all, where the speculative computing approach is necessary. This article describes traditional sequential solutions for conflict detection and diagnosis, two relevant tasks in the automated analysis of feature models, and how to define their speculative parallel version, highlighting their computing improvements. Given the current parallel computing world, we remark on the advantages and current applicability of speculative computing for producing faster algorithmic solutions. [ABSTRACT FROM AUTHOR]

The sparse triangular solver (SpTRSV) is mostly used for scientific and engineering applications. The structured-grid triangular solver of regular dependencies (STRSV) is a special kind of SpTRSV. Some general SpTRSVs that disregards the regularity of the matrix are unsuitable for solving this problem. This paper proposes an efficient parallel algorithm for STRSV on the SW26010 (a kind of China independently designed many-core processors), namely swStructTRSV. The algorithm makes full use of the fine-grained and low latency communication characteristics of the SW26010 to reduce the waiting time for synchronization, maximizes the regularity of access to improve memory access bandwidth, and achieves overlap between memory access and computation simultaneously. Moreover, the idea of the algorithm can be extended to incomplete LU factorization (ILU factorization) because of consistent dependencies. The experimental results on a core group(8 * 8 network composed of 64 cores) of SW26010 show that swStructTRSV can achieve an average speedup of over 30 in the sequential version. swStructTRSV on SW26010 achieves solving speedups of 2.2 and 6.3 over the fast STRSV (fSpTRSV) previously implemented on SW26010 and MKL on Intel Xeon Gold 6132, respectively. swStructTRSV significantly outperforms cuSparse on NVIDIA TITAN RTX in terms of overall execution time. [ABSTRACT FROM AUTHOR]

This paper presents a massively parallel approach of the multilevel fast multipole algorithm (PMLFMA) on homegrown many-core SW26010 cluster of China, noted as (SW-PMLFMA), for 3-D electromagnetic scattering problems. In this approach, the multilevel fast multipole algorithm (MLFMA) octree is first partitioned among management processing elements (MPEs) of SW26010 processors following the ternary partitioning scheme using the message passing interface (MPI). Then, the computationally intensive parts of the PMLFMA on each MPI process, matrix filling, aggregation and disaggregation are accelerated by using all the 64 computing processing elements (CPEs) in the same core group of the MPE via the Athread parallel programming model. Different parallelization strategies are designed for many-core accelerators to ensure a high computational throughput. In coincidence with the special characteristic of local Lagrange interpolation, the compressed sparse row (CSR) and the compressed sparse column (CSC) sparse matrix storage format is used for storing interpolation and anterpolation matrices, respectively, together with a specially designed cache mechanism of hybrid dynamic and static buffers using the scratchpad memory (SPM) to improve data access efficiency. Numerical results are included to demonstrate the efficiency and versatility of the proposed method. The proposed parallel scheme is shown to have excellent speedup. [ABSTRACT FROM AUTHOR]

This paper analyzes a parareal approach based on fractional-step methods for the nonstationary Navier-Stokes equations. As an efficient parallel computing framework, the coarse propagator often determines the performance of the parareal algorithm. We present a parareal algorithm using the fractional-step method, a very efficient time discrete scheme for the Naiver-Stokes equations, as the coarse propagator for the Navier-Stokes equations. Then we give the specific stability and convergence analysis of this specific parareal algorithm. Finally, numerical experiments are done to show efficiency and illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

In recent decades with the increase in the complexity of the problems, the need for high-performance and scalable optimization tools has been inevitable. Among different phenomena introduced to optimization problems, naturally inspired algorithms are favored. Also, encountering large-scale problems, high-performance tools like parallel implementations should be needed. In order to tackle this problem, the framework has been proposed that can wrap any swarm algorithm into an outperformer parallel and hybrid version. Six accepted swarm algorithms are selected to evaluate performance and compare the wrapped version with standard versions. Six nonlinear high-dimension benchmark functions are used to test the proposed algorithms. The experimental results show that wrapped versions outperform standard versions with the measurement of average best fitness. [ABSTRACT FROM AUTHOR]

This paper proposes an unconventional architecture and algorithm for implementing reservoir computing on FPGA. An architecture-oriented algorithm with improved throughput and architecture designed to reduce memory and hardware resource requirements are presented. The proposed architecture exhibits good performance in terms of benchmarks for reservoir computing. A prediction accelerator for reservoir computing that operates on 55.45 mW at 450 K fps with <3000 LEs is realized by implementing the architecture on FPGA. The proposed approach presents a novel FPGA implementation of reservoir computing focussing on both algorithms and architecture that may serve as a basis for applications of AI at network edge. [ABSTRACT FROM AUTHOR]

Huber robust regression (HRR) has attracted much attention in machine learning due to its greater robustness to outliers compared to least-squares regression. However, existing algorithms for HRR are computationally much less efficient than those for least-squares regression. Based on a maximally split alternating direction method of multipliers (MS-ADMM) for model fitting, a highly computationally efficient algorithm referred to as the modified MS-ADMM is derived in this article for HRR. After analyzing the convergence of the modified MS-ADMM, a parameter selection scheme is presented for the algorithm. With the parameter values calculated via this scheme, the modified MS-ADMM converges very rapidly, much faster than several typical HRR algorithms. Through applications in the training of stochastic neural networks and comparisons with existing algorithms, the modified MS-ADMM is shown to be computationally much more efficient than the convex quadratic programming method, the Newton method, the iterative reweighted least-squares method, and Nesterov's accelerated gradient method. Implementation of the proposed algorithm on a GPU-based parallel computing platform demonstrates its higher GPU acceleration ratio compared to the competing methods and, thus, its greater superiority in computational efficiency over the competing methods. [ABSTRACT FROM AUTHOR]

The object of this study is a clustering algorithm using various technologies. This paper compares clustering algorithms that are more commonly used to analyze urban road network trajectories, the growth curve model, with the elbow method and the x-means algorithm. Experiments were conducted with various volumes of big data to determine calculation time, accuracy, and ways to increase calculation time. These results can be used to manage traffic jams in congested areas and city streets. Considering the widespread use of clustering algorithms for solving various problems, this study proposes to introduce GCM, SPGK methods for monitoring and analyzing the state of congestion on city roads. The work was carried out in the following steps: research and selection of methods based on efficiency and time, implementation of parallel computing technologies to improve computation speed, demonstration of the selected method based on collected data from a real city with visualization of the results. The growth curve model algorithm has been proven to be almost 5 times more effective than the elbow method and the x-means algorithm. The time allocated for data processing has been calculated. An increase in the volume of processed data showed an almost stable execution time t=3 s for the GCM algorithm for data with a volume of up to almost 2,000 units. The effectiveness of SPGK-means was shown for different values of the number of points. Models of the Chengdu transport network obtained using a clustering algorithm with maximum grid density of neighborhoods are presented. There are some deviations between the grid and the road network due to the large grid size. This error is explained by an error of up to one between the points and the real grid. The results obtained clearly show how optimization of congested roads can be influenced. They provide information to obtain data on available routes, which allows you to analyze the road network individually and as a whole. [ABSTRACT FROM AUTHOR]

Multiple-point geostatistics (MPS) has more advantages than two-point geostatistics in reproducing the continuity of geobodies in subsurface reservoir modeling. For fluvial reservoir modeling, the more continuous a channel, the more consistent it is with geological knowledge in general, and fluvial continuity is also of paramount importance when simulating fluid flow. Based on the pixel-based MPS algorithm Snesim, this study proposes a method that utilizes multiple search trees (MSTs) to enhance simulation continuity in 2D fluvial reservoir modeling. The objective of the MST method is to capture complete data events from a training image (TI), which aims to achieve enhanced continuity in fluvial reservoir sublayer modeling. By resorting to search neighborhoods based on their proximity to the central node of the data template, multiple data templates that correspond to the MSTs will be generated. Here, four data templates were generated by arranging the relative search neighborhood coordinates in ascending and descending order with respect to the central node. Parallel computing was tried for the construction of the search trees. This work calculated the conditional probability distribution function (CPDF) of the simulating nodes by averaging the CPDFs derived from the MSTs, and double retrieval was employed to filter out the search trees that possessed an inaccurate local CPDF for the simulating nodes. In addition, the connected component labeling (CCL) method was introduced to evaluate the simulation continuity in MPS. The results indicated that the MST method can enhance the simulation continuity of the Snesim algorithm by reproducing the fine connectivity of channel facies in 2D fluvial reservoir modeling. [ABSTRACT FROM AUTHOR]

The dynamic star simulator is a commonly used ground-test calibration device for star sensors. For the problems of slow calculation speed, low integration, and high power consumption in the traditional star chart simulation method, this paper designs a FPGA-based star chart display algorithm for a dynamic star simulator. The design adopts the USB 2.0 protocol to obtain the attitude data, uses the SDRAM to cache the attitude data and video stream, extracts the effective navigation star points by searching the starry sky equidistant right ascension and declination partitions, and realizes the pipelined displaying of the star map by using the parallel computing capability of the FPGA. Test results show that under the conditions of chart field of view of Φ 20 ° and simulated magnitude of 2.0 ∼ 6.0   Mv , the longest time for calculating a chart is 72 μs under the clock of 148.5 MHz, which effectively improves the chart display speed of the dynamic star simulator. The FPGA-based star map display algorithm gets rid of the dependence of the existing algorithm on the computer, reduces the volume and power consumption of the dynamic star simulator, and realizes the miniaturization and portable demand of the dynamic star simulator. [ABSTRACT FROM AUTHOR]

As core algorithms of geographic computing, overlay analysis algorithms typically have computation-intensive and data-intensive characteristics. It is highly important to optimize overlay analysis algorithms by parallelizing the vector polygons after reasonable data division. To address the problem of unbalanced data partitioning in the task decomposition process for parallel polygon overlay analysis and calculation, this paper presents a data partitioning method based on shape complexity index optimization, which achieves data equalization among multicore parallel computing tasks. Taking the intersection operator and difference operator of the Vatti algorithm as examples, six polygon shape indexes are selected to construct the shape complexity model, and the vector data are divided in accordance with the calculated shape complexity results. Finally, multicore parallelism is achieved based on OpenMP. The experimental results show that when a data set with a large amount of data is used, the effect of the multicore parallel execution of the Vatti algorithm's intersection operator and difference operator based on shape complexity division is clearly improved. With 16 threads, compared with the serial algorithm, speedups of 29 times and 32 times can be obtained. Compared with the traditional multicore parallel algorithm based on polygon number division, the speed can be improved by 33% and 29%, and the load balancing index is reduced. For a data set with a small amount of data, the acceleration effect of this method is similar to that of traditional methods involving multicore parallelism. [ABSTRACT FROM AUTHOR]

Bayesian optimization (BO) is challenging for problems with large number of observations. The main limitation of the Gaussian Process (GP) based BO is the computational cost which grows cubically with the number of sample points. To alleviate scalability issues of standard GP we propose to use the generalized product of experts (gPoE) model. This model is not only very flexible and scalable but can be efficiently computed in parallel. Moreover, we propose a new algorithm gPoETRBO for global optimization with large number of observations which combines trust region and gPoE models. In our experiments, we empirically show that our proposed algorithms are computationally more efficient and achieve similar performance to other state-of-the-art algorithms without using any specialized hardware. [ABSTRACT FROM AUTHOR]

Multiple sequence alignment (MSA) stands as a critical tool for understanding the evolutionary and functional relationships among biological sequences. Obtaining an exact solution for MSA, termed exact-MSA, is a significant challenge due to the combinatorial nature of the problem. Using the dynamic programming technique to solve MSA is recognized as a highly computationally complex algorithm. To cope with the computational demands of MSA, parallel computing offers the potential for significant speedup in MSA. In this study, we investigated the utilization of parallelization to solve the exact-MSA using three proposed novel approaches. In these approaches, we used multi-threading techniques to improve the performance of the dynamic programming algorithms in solving the exact-MSA. We developed and employed three parallel approaches, named diagonal traversing, blocking, and slicing, to improve MSA performance. The proposed method accelerated the exact-MSA algorithm by around 4×. The suggested approaches could be basic approaches to be combined with many existing techniques. These proposed approaches could serve as foundational elements, offering potential integration with existing techniques for comprehensive MSA enhancement. [ABSTRACT FROM AUTHOR]

As the size of graph data grows exponentially, it is usually processed by parallel and distributed computing environment. During parallel processing, the first step is to divide the graph data into many subgraphs and then place them on different computational nodes. However, the existing graph clustering methods cannot adapt to parallel processing or improve computing performance. The main reason is that these methods only focus on the graph data but do not care about the graph's application algorithm. Therefore, this paper addresses a graph clustering method that supports parallel processing by perceiving the application algorithm semantics. We specifically focus on the characteristic of "tight inside and loose outside". Based on this characteristic, we give a new formula for calculating the modularity of the subgraph. In a graph application, graph data and its associated application algorithm are not separated from each other. Thus, we also focus on the execution patterns of the application algorithm. Combining the modularity of a subgraph and execution patterns of an application algorithm, we present the critical concept of semantic serial degree as a new criterion for big graph clustering. Consequently, we propose a graph clustering method that effectively balances the importance between the graph data and its associated application algorithm. By achieving this balance, our approach ensures that the final clustering results are more suitable for parallel and distributed processing. Extended experiments show that our proposed graph clustering method is more general and compatible with traditional clustering methods. Compared with FastUnfolding, a state-of-the-art graph clustering method, the completion times of an application algorithm are significantly reduced due to the help of the proposed graph clustering method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a proximal fully parallel splitting method with a relaxation factor for solving separable convex minimization model with linear constraints, where the objective function is the sum of m individual functions without coupled variables. With a full Jacobian decomposition, we decompose the subproblem associated with the augmented Lagrangian method into m smaller subproblems and then add a quadratic proximal term to each decomposed subproblem, which makes the resulting ones easier to solve for many applications. In order to accelerate the numerical performance, we attach a positive relaxation factor to update the Lagrange multiplier, which also allows more flexibility in the design of algorithms. Moreover, we refine the step size of the underrelaxation step, which enlarges several existing ones in the literature. We prove that the proposed method is globally convergent, and show the worst-case O (1 / k) convergence rate in a nonergodic sense. Finally, the efficiency and robustness of the proposed method are also demonstrated by solving the ℓ 1 norm problem, the ℓ 1 -regularized least squares problem, the exchange problem and the total variation image restoration problem. [ABSTRACT FROM AUTHOR]

Clustering algorithms are part of algorithms of unsupervised-learning that are commonly used in different fields. Two major impacts on the data clustering algorithm have been the rapid developments and creation of electronic data. This includes the view of how the big data is stored as well as how it is processed. A cluster has a high level of resemblance to the same cluster and a low level of resemblance to other clusters. Clustering algorithms are commonly used in all fields, such as retail, banking, development, etc.. Even though different methodologies are proposed with different scenarios, but none of the existing methodologies are proven to be a better approaches. Here, in our work we have adopted an improved Map- Reduce programming model to combine the Canopy clustering and K-means clustering algorithms to process the Microarray data with the available commodity hardware with an aim to achieve better performance. The results obtained from different scenarios shown that the proposed method was capable of improving computational speed significantly by increasing the nodes as required. In this research, this paper explored the efficiency by evaluating and implementing the proposed Improved k-means with Improved Map Reduce algorithm which runs on Hadoop Frame work using Microarray dataset along with different datasets. [ABSTRACT FROM AUTHOR]

The article outlines a contemporary method for creating software for multi-processor computers. It describes the identification of parallelizable sequential code structures. Three structures were found and then carefully examined. The algorithms used to determine whether or not certain parts of code may be parallelized result from static analysis. The techniques demonstrate how, if possible, existing sequential structures might be transformed into parallel-running programs. A dynamic evaluation is also a part of our process, and it can be used to assess the efficiency of the parallel programs that are developed. As a tool for sequential programs, the algorithms have been implemented in C#. All proposed methods were discussed using a common benchmark. [ABSTRACT FROM AUTHOR]

Cluster analysis is one of the most fundamental methods in data mining, and it has been widely used in economics, social sciences and computer science. However, with the rapid development of Internet technology, the volume of data required for various web applications has grown rapidly, making the traditional clustering analysis methods face technical challenges. How to obtain useful information in a large amount of data quickly and efficiently is an urgent problem in many industrial fields. With the continuous development of cloud computing technology, large amounts of data can be performed quickly and efficiently. Hadoop is an open source distributed cloud computing platform with HDFS (Digital File System) and MapReduce as its core. HDFS provides massive data storage, while MapReduce uses the MapReduce programming model to achieve parallel processing. Compared with the traditional parallel programming model, it contains basic functions such as data partitioning, task scheduling, and parallel processing, making it possible for users to develop distributed applications on their own without understanding the basics of distributed basics, thus facilitating the design of parallel programs. K-means algorithm is a typical clustering analysis method, which is widely used in industry, but the number of iterations will increase significantly due to the growth of data volume, thus reducing the efficiency of computation. In order to better apply to the cluster analysis of large-scale data, this paper firstly implements a parallelization algorithm based on MapReduce on Hadoop platform using the basic idea of MapReduce and improves the K-means algorithm for the problems of blindness and easy to fall into local optimum when selecting randomly in clusters. [ABSTRACT FROM AUTHOR]

High resolution remains a primary goal in the advancement of synthetic aperture radar (SAR) technology. The backprojection (BP) algorithm, which does not introduce any approximation throughout the imaging process, is broadly applicable and effectively meets the demands for high-resolution imaging. Nonetheless, the BP algorithm necessitates substantial interpolation during point-by-point processing, and the precision and effectiveness of current interpolation methods limit the imaging performance of the BP algorithm. This paper proposes a TSU-ICSI (Time-shift Upsampling-Improved Cubic Spline Interpolation) interpolation method that integrates time-shift upsampling with improved cubic spline interpolation. This method is applied to the BP algorithm and presents an efficient implementation method in conjunction with the GPU architecture. TSU-ICSI not only maintains the accuracy of BP imaging processing but also significantly boosts performance. The effectiveness of the BP algorithm based on TSU-ICSI is confirmed through simulation experiments and by processing measured data collected from both airborne SAR and spaceborne SAR. [ABSTRACT FROM AUTHOR]

We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capacity in each time period is the summation of capacities of a subset of n available modules (machines or vehicles) of different capacities. We refer to this problem as Multi-module Capacitated Lot-Sizing Problem without or with Subcontracting, and denote it by MCLS or MCLS-S, respectively. These are NP-hard problems if n is a part of the input and polynomially solvable for n = 1. In this article we address an open question: Does there exist a polynomial time exact algorithm for solving the MCLS or MCLS-S with fixed n ≥ 2 ? We present exact fixed-parameter tractable (polynomial) algorithms that solve MCLS and MCLS-S in O (T 2 n + 3) time for a given n ≥ 2. It generalizes algorithm of Atamtürk and Hochbaum [Management Science 47(8):1081–1100, 2001] for MCLS-S with n = 1. We also present exact algorithms for two-generalizations of the MCLS and MCLS-S: (a) a lot-sizing problem with piecewise concave production cost functions (denoted by LS-PC-S) that takes O (T 2 m + 3) time, where m is the number of breakpoints in these functions, and (b) two-echelon MCLS that takes O (T 4 n + 4) time. The former reduces run time of algorithm of Koca et al. [INFORMS J. on Computing 26(4):767–779, 2014] for LS-PC-S by 93.6%, and the latter generalizes algorithm of van Hoesel et al. [Management Science 51(11):1706–1719, 2005] for two-echelon MCLS with n = 1. We perform computational experiments to evaluate the efficiency of our algorithms for MCLS and LS-PC-S and their parallel computing implementation, in comparison to Gurobi 9.1. The results of these experiments show that our algorithms are computationally efficient and stable. Our algorithm for MCLS-S addresses another open question related to the existence of a polynomial time algorithm for optimizing a linear function over n-mixing set (a generalization of the well-known 1-mixing set). [ABSTRACT FROM AUTHOR]

With the rapid advancement of computer graphics and three-dimensional modeling technology, the processing and optimization of three-dimensional (3D) models have become contentious research topics. In the context of mobile devices or web applications, situations may arise where it becomes necessary to load a 3D model with a substantial memory footprint in real-time or dynamically adjust the level of detail of a model based on the scene's proximity. In such cases, it is imperative to optimize the original model to ensure smoothness and responsiveness. Due to the simplicity of their algorithm, quadric error metrics (QEMs) can deliver excellent results in simplifying 3D models while maintaining high efficiency. Therefore, QEM is widely employed in engineering applications within the realm of computer graphics development. Moreover, in the pursuit of enhanced quality and efficiency, numerous scholars have improved it based on QEM algorithms. This study aims to provide a systematic review and summary of the principles and applications of current research on QEM algorithms. First, we conducted a bibliometric analysis of 128 studies in related fields spanning from 1998 to 2022 using CiteSpace. This allowed us to sort QEM algorithms and gain insights into their development status and emerging trends. Second, we delve into the fundamental principles and optimizations of the QEM algorithms to provide a deeper understanding of their implementation process. Following that, we explore the advantages and limitations of the QEM algorithms in practical applications and analyze their potential in various domains, including virtual reality and game development. Finally, this study outlines future research directions, which encompass the development of more efficient error metric calculation methods, the exploration of adaptive simplification strategies, and the investigation of potential synergies with deep learning technologies. Current research primarily centers on enhancing QEM algorithms by incorporating additional geometric constraints to better differentiate between flat and irregular areas. This enables a more accurate determination of the areas that should be prioritized for folding. Nevertheless, it is important to note that these improvements may come at the cost of reduced computational efficiency. Therefore, future research directions could involve exploring parallel computing techniques and utilizing GPUs to enhance computational efficiency. [ABSTRACT FROM AUTHOR]

The Parallel and Distributed Computing group belonging to the Integrated Technological Research Complex (CITI). has been engaged in the creation of general-purpose components that support the processing of large volumes of information that characterize the problems involved in parallel computing. Using the oblivious cache model, which works independently of the computer architecture, and the divide and conquer principle, an algorithm for matrix transposition is implemented to reduce the execution time of this algebraic operation. The algorithm ensures that most of the data content is loaded to the cache for fast processing, and makes the most of its stay in the cache to minimize missed reads and achieve greater speed. The work includes conclusions and statistical tests carried out from experiments on computers with different architectures, reflecting the superiority of the algorithm that uses oblivious cache from an order of matrix determined according to the characteristics of each PC. [ABSTRACT FROM AUTHOR]

High-utility itemset mining (HUIM) is an effective technique for discovering significant information in data. However, data containing sensitive and private information may cause privacy concerns. Therefore, privacy preserving utility mining (PPUM) has recently become a critical research area. PPUM is the process of transforming a quantitative transactional database into a sanitised one, thus ensuring that utility mining algorithms cannot discover sensitive information. The sanitisation process can have several side effects, including the loss of non-sensitive information and the introduction of redundant information. Additionally, the running times of heuristic algorithms for sanitising data are high. To minimise negative effects and lower the execution time of the hiding process, we propose the G-ILP algorithm with a GPU parallel programming method for preprocessing and a new efficient constraint satisfaction problem for hiding data. The experimental evaluations of G-ILP show the algorithm's efficiency in terms of running time and its ability to minimise side effects in large datasets. [ABSTRACT FROM AUTHOR]

Copyright of Chinese Journal of Liquid Crystal & Displays is the property of Chinese Journal of Liquid Crystal & Displays and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Hadoop is a framework for storing and processing huge volumes of data on clusters. It uses Hadoop Distributed File System (HDFS) for storing data and uses MapReduce to process that data. MapReduce is a parallel computing framework for processing large amounts of data on clusters. Scheduling is one of the most critical aspects of MapReduce. Scheduling in MapReduce is critical because it can have a significant impact on the performance and efficiency of the overall system. The goal of scheduling is to improve performance, minimize response times, and utilize resources efficiently. A systematic study of the existing scheduling algorithms is provided in this paper. Also, we provide a new classification of such schedulers and a review of each category. In addition, scheduling algorithms have been examined in terms of their main ideas, main objectives, advantages, and disadvantages. [ABSTRACT FROM AUTHOR]

Copyright of Revista Cubana de Ciencias Informáticas is the property of Universidad de las Ciencias Informaticas (UCI) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Early High-density electroencephalographic (EEG) systems are utilized in the study of the human brain and its underlying behaviours. However, working with the EEG data requires a well-cleaned signal, which is often obtained using independent component analysis (ICA) methods. The longer the calculation time for these types of algorithms is, the more data is obtained. This paper presents a hybrid implementation of the fastICA algorithm that uses parallel programming techniques (libraries and extensions of the Intel processors and CUDA programming), which results in a significant acceleration of execution time on selected architectures. [ABSTRACT FROM AUTHOR]

Tensor trains are a versatile tool to compress and work with high-dimensional data and functions. In this work we introduce the streaming tensor train approximation (STTA), a new class of algorithms for approximating a given tensor T in the tensor train format. STTA accesses T exclusively via two-sided random sketches of the original data, making it streamable and easy to implement in parallel--unlike existing deterministic and randomized tensor train approximations. This property also allows STTA to conveniently leverage structures in T, such as sparsity and various low-rank tensor formats, as well as linear combinations thereof. When Gaussian random matrices are used for sketching, STTA is admissible for an analysis that builds and extends upon existing results on the generalized Nyström approximation for matrices. Our results show that STTA can be expected to attain a nearly optimal approximation error if the sizes of the sketches are suitably chosen. A range of numerical experiments illustrates the performance of STTA compared to existing deterministic and randomized approaches. [ABSTRACT FROM AUTHOR]

Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The ItemCF algorithm is currently the most widely used recommendation algorithm in commercial applications. In the early days of recommender systems, most recommendation algorithms were run on a single machine rather than in parallel. This approach, coupled with the rapid growth of massive user behavior data in the current big data era, has led to a bottleneck in improving the execution efficiency of recommender systems. With the vigorous development of distributed technology, distributed ItemCF algorithms have become a research hotspot. Hadoop is a very popular distributed system infrastructure. MapReduce, which provides massive data computing, and Hive, a data warehousing tool, are the two core components of Hadoop, each with its own advantages and applicable scenarios. Scholars have already utilized MapReduce and Hive for the parallelization of the ItemCF algorithm. However, these pieces of literature make use of either MapReduce or Hive alone without fully leveraging the strengths of both. As a result, it has been difficult for parallel ItemCF recommendation algorithms to feature both simple and efficient implementation and high running efficiency. To address this issue, we proposed a distributed ItemCF recommendation algorithm based on the combination of MapReduce and Hive and named it HiMRItemCF. This algorithm divided ItemCF into six steps: deduplication, obtaining the preference matrixes of all users, obtaining the co-occurrence matrixes of all items, multiplying the two matrices to generate a three-dimensional matrix, aggregating the data of the three-dimensional matrix to obtain the recommendation scores of all users for all items, and sorting the scores in descending order, with Hive being used to carry out steps 1 and 6, and MapReduce for the other four steps involving more complex calculations and operations. The Hive jobs and MapReduce jobs are linked through Hive's external tables. After implementing the proposed algorithm using Java and running the program on three publicly available user shopping behavior datasets, we found that compared to algorithms that only use MapReduce jobs, the program implementing the proposed algorithm has fewer lines of source code, lower cyclomatic complexity and Halstead complexity, and can achieve a higher speedup ratio and parallel computing efficiency when processing all datasets. These experimental results indicate that the parallel and distributed ItemCF algorithm proposed in this paper, which combines MapReduce and Hive, has both the advantages of concise and easy-to-understand code as well as high time efficiency. [ABSTRACT FROM AUTHOR]

Anomaly detection of sequences is a hot topic in data mining. Anomaly detection using piecewise aggregate approximation in the amplitude domain (called ADPAAD) is one of the widely used methods in anomaly detection of sequences. The core step in the classical algorithm for performing ADPAAD is to construct an approximate representation of the subsequence, where the elements of each subsequence are divided into several subsections according to the amplitude domain, and then the average of the subsections is computed. It is computationally expensive when processing large‐scale sequences. In this paper, a quantum algorithm for ADPAAD is proposed, which can divide the subsequence elements and compute the average in parallel. The quantum algorithm can achieve polynomial speedups on the number of subsequences and the length of subsequences over its classical counterpart. [ABSTRACT FROM AUTHOR]

Space vehicles such as missiles and aircraft have relatively long tracking distances. Infrared (IR) detectors are used for small target detection. The target presents point target characteristics, which lack contour, shape, and texture information. The high-brightness cloud edge and high noise have an impact on the detection of small targets because of the complex background of the sky and ground environment. Traditional template-based filtering and local contrast-based methods do not distinguish between different complex background environments, and their strategy is to unify small-target template detection or to use absolute contrast differences; so, it is easy to have a high false alarm rate. It is necessary to study the detection and tracking methods in complex backgrounds and low signal-to-clutter ratios (SCRs). We use the complexity difference as a prior condition for detection in the background of thick clouds and ground highlight buildings. Then, we use the spatial domain filtering and improved local contrast joint algorithm to obtain a significant area. We also provide a new definition of gradient uniformity through the improvement of the local gradient method, which could further enhance the target contrast. It is important to distinguish between small targets, highlighted background edges, and noise. Furthermore, the method can be used for parallel computing. Compared with the traditional space filtering algorithm or local contrast algorithm, the flexible fusion strategy can achieve the rapid detection of small targets with a higher signal-to-clutter ratio gain (SCRG) and background suppression factor (BSF). [ABSTRACT FROM AUTHOR]

Nowadays, almost all network traffic is encrypted. Attackers hide themselves using this traffic and attack over encrypted channels. Inspections performed only on packet headers and metadata are insufficient for detecting cyberattacks over encrypted channels. Therefore, it is important to analyze packet contents in applications that require control over payloads, such as content filtering, intrusion detection systems (IDSs), data loss prevention systems (DLPs), and fraud detection. This technology, known as deep packet inspection (DPI), provides full control over the communication between two end stations by keenly analyzing the network traffic. This study proposes a multi-pattern-matching algorithm that reduces the memory space and time required in the DPI pattern matching compared to traditional automaton-based algorithms with its ability to process more than one packet payload character at once. The pattern-matching process in the DPI system created to evaluate the performance of the proposed algorithm (PA) is conducted on the graphics processing unit (GPU), which accelerates the processing of network packets with its parallel computing capability. This study compares the PA with the Aho-Corasick (AC) and Wu–Manber (WM) algorithms, which are widely used in the pattern-matching process, considering the memory space required and throughput obtained. Algorithm tables created with a dataset containing 500 patterns use 425 and 688 times less memory space than those of the AC and WM algorithms, respectively. In the pattern-matching process using these tables, the PA is 3.5 and 1.5 times more efficient than the AC and WM algorithms, respectively. [ABSTRACT FROM AUTHOR]

This paper investigates an FPGA architecture whose primary function is to accelerate parallel computations involved in the rapid-exploring random tree (RRT) algorithm. The RRT algorithm is inherently serial, while in each computing step there are many computations that can be executed simultaneously. Nevertheless, how to carry out these parallel computations on an FPGA so that a high degree of acceleration can be realized is the key issue. Membrane computing is a parallel computing paradigm inspired from the structures and functions of eukaryotic cells. As a newly proposed membrane computing model, the generalized numerical P system (GNPS) is intrinsically parallel; so, it is a good candidate for modeling parallel computations in the RRT algorithm. Open problems for the FPGA implementation of the RRT algorithm and GNPS include: (1) whether it possible to model the RRT with GNPS; (2) if yes, how to design such an FPGA architecture to achieve a better speedup; and (3) instead of implementing GNPSs with a fixed-point-number format, how to devise a GNPS FPGA architecture working with a floating-point-number format. In this paper, we modeled the RRT with a GNPS at first, showing that it is feasible to model the RRT with a GNPS. An FPGA architecture was fabricated according to the GNPS-modeled RRT. In this architecture, computations, which can be executed in parallel, are accommodated in different inner membranes of the GNPS. These membranes are designed as Verilog modules in the register transfer level model. All the computations within a membrane are triggered by the same clock impulse to implement parallel computing. The proposed architecture is validated by implementing it on the Xilinx VC707 FPGA evaluation board. Compared with the software simulation of the GNPS-modeled RRT, the FPGA architecture achieves a speedup of a 10 4 order of magnitude. Although this speedup is obtained on a small map, it reveals that this architecture promises to accelerate the RRT algorithm to a higher level compared with the previously reported architectures. [ABSTRACT FROM AUTHOR]