Multicore clusters are widely used to solve combinatorial optimization problems, which require high computing power and a large amount of memory. In this sense, Hash Distributed A* (HDA*) parallelizes A*, a combinator...
详细信息
ISBN:
(纸本)9783319654829;9783319654812
Multicore clusters are widely used to solve combinatorial optimization problems, which require high computing power and a large amount of memory. In this sense, Hash Distributed A* (HDA*) parallelizes A*, a combinatorial optimization algorithm, using the MPI library. HDA* scales well on multicore clusters and on multicore machines. Additionally, there exist several versions of HDA* that were adapted for multicore machines, using the Pthreads library. In this paper, we present Hybrid HDA* (HHDA*), a hybrid parallelsearch algorithm based on HDA* that combines message-passing (MPI) with shared-memory programming (Pthreads) to better exploit the computing power and memory of multicore clusters. We evaluate the performance and memory consumption of HHDA* on a multicore cluster, using the 15-puzzle as a case study. The results reveal that HHDA* achieves a slightly higher average performance and uses considerably less memory than HDA*. These improvements allowed HHDA* to solve one of the hardest 15-Puzzle instances.
This paper presents a possible solution for the text inference problem-extracting information unstated in a text, but implied. Text inference is central td natural language applications such as information extraction ...
详细信息
This paper presents a possible solution for the text inference problem-extracting information unstated in a text, but implied. Text inference is central td natural language applications such as information extraction and dissemination, text understanding, summarization, and translation. Our solution takes advantage of a semantic English dictionary available in electronic form that provides the basis for the development of a large linguistic knowledge base. The inference algorithm consists of a set of highly parallelsearch methods that, when applied to the knowledge base, find contexts in which sentences are interpreted. These contexts reveal information relevant to the text. Implementation, results, and parallelism analysis are discussed.
We presents the parallelization of Satz using work stealing for workload balancing, based on the master/slave communication model. We define a simple way to evaluate the workload of every busy slave. The master then s...
详细信息
We presents the parallelization of Satz using work stealing for workload balancing, based on the master/slave communication model. We define a simple way to evaluate the workload of every busy slave. The master then steals the first remaining subtree of the most loaded slave for an idle slave. Special attention is paid to prevent pingpong phenomenon. Our approach easily supports fault tolerance computing and accumulation of intermediate results over time. Encouraging experimental results are presented.
Comprising the coordination of various maintenance levels, flight maintenance planning (FMP) constitutes an appealing and hard-to-solve optimisation problem. In this article, a modified version of the typical FMP prob...
详细信息
Comprising the coordination of various maintenance levels, flight maintenance planning (FMP) constitutes an appealing and hard-to-solve optimisation problem. In this article, a modified version of the typical FMP problem is studied for a typical-size military fleet, focusing on engine maintenance: a disruption of the depot level maintenance (DLM) facilities is considered, causing long-term shortage of serviceable engine parts. In this context, an optimisation strategy is proposed to schedule engine and part exploitation so that engine availability be retained until the recovery of the DLM supply lines, and flight and maintenance requirements be fulfilled to the maximum possible extent. To incorporate the effects of stochastic events, model their interaction with the capacity of the available maintenance resources and assess the outcome of the proposed plans, Monte-Carlo simulations are employed. A computationally efficient variant of the asynchronous particle swarm optimisation method is introduced to find the optimal solutions, combining parallelisation of the evaluation calls with a metamodel-based pre-evaluation strategy to reduce the optimisation turnaround time. Tested on a full-scale application, the proposed method is shown to be capable of producing robust FMP solutions and, also, quantifying the maintenance chain's operating status to aid in long-term planning.
暂无评论