In this paper, efficient and portable shared memory based parallel computation models for the string matching problem are presented and analyzed for their performances. For exploiting the parallelism in the computatio...
详细信息
In this paper, efficient and portable shared memory based parallel computation models for the string matching problem are presented and analyzed for their performances. For exploiting the parallelism in the computation models, parallel broadcasting method that is a dataflow scheme is applied. thus the models are time and space efficient since they are based on the dataflow mechanism. Several computation models are designed and tested for checking the aspects that affect the parallel programming performance such as granularity, communication, and I/O. For the implementation, Java threads that is a built-in support for the portable parallel programming in the shared memory environment is used. Experimental results demonstrate that the computation models are practical, portable, and scalable parallel solutions to the problem, and the comparative testing reveals facts between the theory and the practice.
the Voronoi diagram of a set of n sites on the plane has application in many diverse areas such as Geographical Information systems (GIS), Visualization, Robotics, Computer Graphics and Computer Aided Design (CAD). Un...
详细信息
the Voronoi diagram of a set of n sites on the plane has application in many diverse areas such as Geographical Information systems (GIS), Visualization, Robotics, Computer Graphics and Computer Aided Design (CAD). Unfortunately, its construction is very costly for large input sizes, and fast parallel algorithms for the problem are desired. there are no known parallel algorithms for the problem that are optimal with respect to the time-processor product. Best sequential algorithms work in O(n lg(n)) time. In this paper, an O(lg3n) time parallel algorithm for constructing the Voronoi Diagram of a set of n sites in the plane is presented on a hypercube with n processors. Our technique parallelizes the well-known seemingly inherent sequential technique of Shamos and Hoey, and makes use of a number of special properties of the dividing polygonal chain and the Batcher's bitonic sort.
As a popular type of parallel evolutionary algorithms, distributed evolutionary algorithms (DEAs) are widely used in a variety of fields. To get better solutions of concrete problems, a scheme of subpopulation diversi...
详细信息
ISBN:
(纸本)9781479920815
As a popular type of parallel evolutionary algorithms, distributed evolutionary algorithms (DEAs) are widely used in a variety of fields. To get better solutions of concrete problems, a scheme of subpopulation diversity based accepting immigrant in DEAs is proposed in this paper. In migration withthis scheme, an immigrant will be put into its target subpopulation only if its current diversity is lower than a threshold value. Algorithm analysis shows that the extra cost of time for this scheme is acceptable in many DEAs. Experiments are conducted on instances of the Traveling Salesman Problem from the TSPLIB. Results show that the DEA based on the proposed scheme can get better solutions than the one without it.
parallel traffic simulation is a critical component in large-scale traffic simulations and real-time traffic simulations. Dividing workloads evenly to multi-cores and multi-machines is a challenge in parallel traffic ...
详细信息
ISBN:
(纸本)9781479920815
parallel traffic simulation is a critical component in large-scale traffic simulations and real-time traffic simulations. Dividing workloads evenly to multi-cores and multi-machines is a challenge in parallel traffic simulations. Current researches focus on map decomposition algorithms. However, without effective workload estimation algorithms, map decomposition algorithms tend to output imbalanced partitions. this paper proposes an elliptical-shaped workload estimation algorithm. the main idea of the algorithm is to assign the computational cost of a vehicle to links in an ellipse, whose centers (or foci points) are the vehicle's origin node and the destination node. the algorithm is evaluated on a test-bed using a mesoscopic traffic simulator on the Lower Westchester County network. Case studies show that the new algorithm reduces 36% of the estimation errors in current length of links based workload estimation algorithms.
Searching for data location in P2P systems is a message-intensive task. Basically, a query needs to reach all the nodes in order to find the locations of a specified data. this search involves a broadcast, and an inap...
详细信息
Searching for data location in P2P systems is a message-intensive task. Basically, a query needs to reach all the nodes in order to find the locations of a specified data. this search involves a broadcast, and an inappropriate broadcast strategy may not only lead to inefficient data sharing, but also directly affect the scalability of the P2P system. We propose the utilization of an ad-hoc spanning tree for distributed search in P2P systems. this spanning tree is built as an overlay network. We define algorithms to maintain the ad-hoc spanning tree, and we compare the search time obtained withthe ad-hoc spanning tree withthe time obtained with other structures used for broadcasting in parallel and distributedsystems. this comparison is done with an MPI emulation.
distributed storage systems comprise a large number of commodity hardware distributed across several data centers. Even in the presence of failures (permanent failures) the system should provide reliable storage. Whil...
详细信息
ISBN:
(纸本)9780769543284
distributed storage systems comprise a large number of commodity hardware distributed across several data centers. Even in the presence of failures (permanent failures) the system should provide reliable storage. While replication has advantages because of its simplicity there exist coding techniques that provide adaptable reliability properties with an optimal redundancy ratio at the same time e.g. MDS (maximum distance separable) erasure codes. the coding and distribution scheme influences the prospective storage reliability. In this paper we present reliability models for erasure coding and replication techniques especially for their application in wide-area storage systems. Furthermore we utilize these models to quantify the reliability properties of concrete data storage scenarios.
Update methods are an important aspect of the burgeoning Artificial Life research area. Artificial Life models, like the Predator-Prey model, are able to operate quite efficiently when implemented in a sequential mann...
详细信息
Update methods are an important aspect of the burgeoning Artificial Life research area. Artificial Life models, like the Predator-Prey model, are able to operate quite efficiently when implemented in a sequential manner only while population numbers are low to moderate. We find that for large populations sequential implementations are too slow to extract meaningful measurement statistics. In this paper we discuss the parallelisation of sequential update methods for use in Artificial Life systems. We also discuss the ramifications that parallel update algorithms introduce to data dependencies and also the meaning of correctness in parallel models.
We present optional locking as a method for significantly speeding up distributed locks, and we generalize it to multiple lock types obeying a conflict relation. the generalized version can simulate the message passin...
详细信息
We present optional locking as a method for significantly speeding up distributed locks, and we generalize it to multiple lock types obeying a conflict relation. the generalized version can simulate the message passing paradigm on top of distributed Shared Memory (DSM) with no more messages than explicit message passing would need. thus we argue that message passing can be viewed as a true special case of optional locking. As a consequence, the attractiveness of DSM programming models should increase significantly due to well-recognized advantages such as simplicity and reduced software engineering cost;mixtures of both message passing and shared data access patterns can be treated uniformly. Measurements and simulations based on database benchmarks indicate a substantial performance improvement of optional locking over conventional locking even in presence of multiple lock types.
Recently, there have been several developments in the scientific community to model and solve complex optimization problems by employing natural metaphors. In some cases, due to their distributed schema, these algorit...
详细信息
ISBN:
(纸本)9780769543284
Recently, there have been several developments in the scientific community to model and solve complex optimization problems by employing natural metaphors. In some cases, due to their distributed schema, these algorithms can be adapted to distributedcomputing environments. A distributed and asynchronous bees (DAB) grid-based approach is here used to optimise the magnetic configuration in order to reduce the neoclassical transport of particles in a nuclear fusion device. Large-scale problems (as several plasma physics can be classified) present open challenges that need a large computing capacity to be solved. thus, the use of large distributed infrastructures is mandatory in many of these problems. the use of grid computing offers a new paradigm where the distributed nature of foraging can be reproduced and applied to complex optimisation problems.
暂无评论