检索结果-内蒙古大学图书馆

7th World Conference on Computing and Communication Technologies, WCCCT 2024

作者： Lei, Yang Song, Wentao Wang, Zhilei Wang, Yu Gu, Naijie University of Science and Technology of China Hefei China

ISBN: (纸本)9798350372328

The Branch-and-Bound(B&B) algorithm is an effective method for solving the Mixed Integer Linear Programming (MILP) problem. Its performance significantly impacts the overall performance of the MILP solver Additionally, parallelizing the B&B algorithm can further speed up solver efficiency. In this paper, a novel B&B parallel algorithm is proposed to accelerate the solution process of MILP problems. A Master-Worker parallel structure is employed in this algorithm, fully leverages the serial performance of the solver. To minimize overhead, only necessary information is shared between the Master and Worker to utilizing shared memory communication. During the search of the B&B tree, the Master distributes problem nodes to Workers. Workers calculate problem nodes to update the information and subsequently return a sequence of new sub-problem nodes to the Master. Once optimality is achieved or the Master has no more problem nodes, the solution process is concluded. This research demonstrates that the proposed B&B parallel algorithm exhibits excellent acceleration performance. Research indicate that the B&B parallel algorithm presented in this study exhibits a substantial speedup factor of 1.53 for instances with over 10,000 nodes within the MIPLIB2017 benchmark. Furthermore, it demonstrates an even more impressive speedup factor of up to 2.53 for instances with more than 60,000 nodes, thereby underscoring excellent performance. It is noteworthy that the relationship between the speedup factor and the number of threads is predominantly linear. © 2024 IEEE.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Generative Adversarial Construction of parallel Portfolios

引用

IEEE TRANSACTIONS ON CYBERNETICS 2022年第2期52卷 784-795页

作者： Liu, Shengcai Tang, Ke Yao, Xin Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230026 Peoples R China Southern Univ Sci & Technol Dept Comp Sci & Engn Guangdong Prov Key Lab Brain Inspired Intelligent Shenzhen 518055 Peoples R China

Since automatic algorithm configuration methods have been very effective, recently there is increasing research interest in utilizing them for automatic solver construction, resulting in several notable approaches. For these approaches, a basic assumption is that the given training set could sufficiently represent the target use cases such that the constructed solvers can generalize well. However, such an assumption does not always hold in practice since in some cases, we might only have scarce and biased training data. This article studies effective construction approaches for the parallel algorithm portfolios that are less affected in these cases. Unlike previous approaches, the proposed approach simultaneously considers instance generation and portfolio construction in an adversarial process, in which the aim of the former is to generate instances that are challenging for the current portfolio, while the aim of the latter is to find a new component solver for the portfolio to better solve the newly generated instances. Applied to two widely studied problem domains, that is, the Boolean satisfiability problems (SAT) and the traveling salesman problems (TSPs), the proposed approach identified parallel portfolios with much better generalization than the ones generated by the existing approaches when the training data were scarce and biased. Moreover, it was further demonstrated that the generated portfolios could even rival the state-of-the-art manually designed parallel solvers.

关键词： Portfolios Training Training data Cybernetics parallel algorithms Tuning Computer science Automatic portfolio construction (APC) generative adversarial approach parallel algorithm portfolio parameter tuning

来源：评论

学校读者我要写书评

暂无评论

A parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2022年第4期33卷 929-940页

作者： Khanda, Arindam Srinivasan, Sriram Bhowmick, Sanjukta Norris, Boyana Das, Sajal K. Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA Virginia Commonwealth Univ Dept Radiat Oncol Richmond VA 23284 USA Univ North Texas Dept Comp Sci & Engn Denton TX 76201 USA Univ Oregon Dept Comp & Informat Sci Eugene OR 97403 USA

The Single Source Shortest Path (SSSP) problem is a classic graph theory problem that arises frequently in various practical scenarios;hence, many parallel algorithms have been developed to solve it. However, these algorithms operate on static graphs, whereas many real-world problems are best modeled as dynamic networks, where the structure of the network changes with time. This gap between the dynamic graph modeling and the assumed static graph model in the conventional SSSP algorithms motivates this work. We present a novel parallel algorithmic framework for updating the SSSP in large-scale dynamic networks and implement it on the shared-memory and GPU platforms. The basic idea is to identify the portion of the network affected by the changes and update the information in a rooted tree data structure that stores the edges of the network that are most relevant to the analysis. Extensive experimental evaluations on real-world and synthetic networks demonstrate that our proposed parallel updating algorithm is scalable and, in most cases, requires significantly less execution time than the state-of-the-art recomputing-from-scratch algorithms.

关键词： Heuristic algorithms Graphics processing units parallel algorithms Synchronization Multicore processing Complexity theory Wireless sensor networks Dynamic networks single source shortest path (SSSP) shared-memory parallel algorithm GPU implementation

来源：评论

学校读者我要写书评

暂无评论

SCATTER SEARCH WITH STOCHASTIC BEAM SEARCH ON THE COALITION FORMATION PROBLEM

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2024年第3期20卷 1156-1176页

作者： Oz, Dindar Altuntas, Tolga Bugra Yasar Univ Bornova Turkiye

The coalition formation problem (CFP) is a crucial component of multi-agent systems (MAS), taking place in various areas in the real world with different variants. This study proposes a parallel metaheuristic algorithm for CFP. Our hybrid method combines two metaheuristic algorithms: the Scatter Search and the Beam Search. While the former ensures that the algorithm thor-oughly explores the search space, the latter exploits the visited regions. We re-design Scatter Search's original implementation to perform the time-consuming independent areas of the task in parallel. We employ a perturbation mechanism inside the Beam Search that performs a big jump in the search space when it cannot find any improvement. Moreover, we design a problem-specific repre-sentation that stores meta-information to save significant computational time. The proposed method is examined in parallel and sequential configurations and compared with an exact solver, recent metaheuristic algorithms, and the standard implementation of the Scatter Search. The experimental results show that our solution achieves considerable improvements in both configurations.

关键词： Coalition formation problem Scatter Search Beam Search multi-agent systems parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

TARIS: Scalable Incremental Processing of Time-Respecting algorithms on Streaming Graphs

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2024年第12期35卷 2527-2544页

作者： Bhoot, Ruchi Ghanmode, Suved Sanjay Simmhan, Yogesh Indian Inst Sci Bangalore 560012 India

Temporal graphs change with time and have a lifespan associated with each vertex and edge. These graphs are suitable to process time-respecting algorithms where the traversed edges must have monotonic timestamps. Interval-centric Computing Model (ICM) is a distributed programming abstraction to design such temporal algorithms. There has been little work on supporting time-respecting algorithms at large scales for streaming graphs, which are updated continuously at high rates (Millions/s), such as in financial and social networks. In this article, we extend the windowed-variant of ICM for incremental computing over streaming graph updates. We formalize the properties of temporal graph algorithms and prove that our model of incremental computing over streaming updates is equivalent to batch execution of ICM. We design TARIS, a novel distributed graph platform that implements these incremental computing features. We use efficient data structures to reduce memory access and enhance locality during graph updates. We also propose scheduling strategies to interleave updates with computing, and streaming strategies to adapt the execution window for incremental computing to the variable input rates. Our detailed and rigorous evaluation of temporal algorithms on large-scale graphs with up to 2B edges show that TARIS out-performs contemporary baselines, Tink and Gradoop, by 3-4 orders of magnitude, and handles a high input rate of 83k-587 M Mutations/s with latencies in the order of seconds-minutes.

关键词： Social networking (online) Heuristic algorithms Topology Computational modeling Network topology Data structures Clustering algorithms Space exploration Roads COVID-19 Discrete Mathematics distributed programming distributed systems general graph algorithms graph theory information storage and retrieval information technology and systems mathematics of computing numerical analysis programming techniques parallel algorithms systems and software software/software engineering

来源：评论

学校读者我要写书评

暂无评论

An overset interpolation algorithm for multi-phase flows using 3D multiblock polyhedral meshes

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2024年 161卷 155-173页

作者： Zafeiris, Spiros Papadakis, George Natl Tech Univ Athens NTUA Sch Naval Architecture & Marine Engn Athens 15780 Attiki Greece

In this study, we present a novel interpolation scheme for chimera simulations in CFD that treats flows with discontinuities. This scheme is suitable for interpolation over polyhedral meshes using only scattered data and without the use of stencils. During the interpolation data transfer among overset meshes, both solution variables and their gradients are communicated and then used for the interpolation process. First, the overset topology problem in partitioned polyhedral meshes is addressed, and then a new interpolation algorithm for generally discontinuous fields is introduced. Then, we describe how the gradient approximation of the Finite Volume (FV) method is utilized in order to construct bounded approximations on values on the direction of discontinuities and enhance the accuracy of the low order Nearest Neighbor value (NNV) algorithm. The performance of the proposed algorithm is quantified and validated in various test cases, together with a comparison with NNV. Finally, scalability tests are presented to prove computational efficiency. The method is proved to be highly accurate in propagation cases and performs well in unsteady two-phase problems executed using parallel architectures.

关键词： Overset Chimera parallel algorithms Two-phase flows Unstructured interpolation Multi-block searching

来源：评论

学校读者我要写书评

暂无评论

Fast parallel Index Construction for Efficient K-truss-based Local Community Detection in Large Graphs 23

Fast Parallel Index Construction for Efficient K-truss-based...

引用

52nd International Conference on parallel Processing (ICPP)

作者： Faysal, Md Abdul Motaleb Bremer, Maximilian Chan, Cy Shalf, John Arifuzzaman, Shaikh Univ Nevada Las Vegas NV 89154 USA Lawrence Berkeley Natl Lab Berkeley CA USA

ISBN: (纸本)9798400708435

Finding cohesive subgraphs is a crucial graph analysis kernelwidely used for social and biological networks (graphs). There exist various approaches for discovering insightful substructures in a network, such as finding cliques, community discovery, and truss decomposition. Finding cliques is a computationally intractable problem, making it difficult to identify cohesive subgraphs in large graphs. One possible solution is k-truss decomposition, which is a relaxed form of finding cliques that can be solved in polynomial time. Further, unlike global community detection-which focuses on breaking down the entire graph into disjoint communities-a local or goaloriented community search aims at finding the community of an entity of interest. In this work, we identify a k-truss-induced community discovery technique that can detect local communities in polynomial time. However, most previous studies have explored k-truss-induced local community formation in a serial setting, making them unsuitable for large graphs. In this paper, we design a parallel k-truss-induced local community construction method using multi-core parallelism. To the best of our knowledge, this is the first attempt to parallelize this algorithmic approach with extensive performance analysis. Our experiments demonstrate a significant performance improvement, with speedups from 19x to 55x for graphs with hundreds of millions to billions of edges, using NERSC Perlmutter compute nodes.

关键词： Graph algorithms parallel algorithms k-truss local community discovery large graphs connected components sparse graphs

来源：评论

学校读者我要写书评

暂无评论

parallel Specification-Based Testing for Concurrent Programs

引用

IEEE ACCESS 2022年 10卷 24955-24975页

作者： Minh Do, Canh Ogata, Kazuhiro Japan Adv Inst Sci & Technol JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan

The paper proposes a new testing technique for concurrent programs. The technique is a specification-based testing. For a formal specification S and a concurrent program P, state sequences are generated from P and checked to be accepted by S. We suppose that S is specified in Maude and P is implemented in Java. Java Pathfinder (JPF) and Maude are then used to generate state sequences from P and to check if such state sequences are accepted by S, respectively. Even without checking any property violations with JPF, JPF often encounters the notorious state space explosion while only generating state sequences. Thus, we propose a technique to generate state sequences from P and check if such state sequences are accepted by S in a stratified way. A tool is developed to support the proposed technique that can be processed naturally in parallel. Some experiments demonstrate that the proposed technique mitigates the state space explosion, which cannot be achieved with the straightforward use of JPF.

关键词： Programming Testing Concurrent computing Protocols Explosions Java Codes Simulation divide & conquer approach parallel algorithms concurrent programs specification-based testing

来源：评论

学校读者我要写书评

暂无评论

High-performance parallel algorithms based on smoothed particles hydrodynamics for solving continuum mechanics problems

引用

DOKLADY MATHEMATICS 2014年第3期90卷 773-777页

作者： Evstigneev, N. M. Zaitsev, F. S. Ryabkov, O. I. New Inflow Ltd Moscow Russia Moscow MV Lomonosov State Univ Fac Computat Math & Cybernet Moscow 119992 Russia Russian Acad Sci Inst Syst Anal Moscow 117312 Russia Russian Acad Sci Sci Res Inst Syst Studies Moscow 117218 Russia

The article presents a mathematical research which develops and examines the properties of high-performance smoothed particles hydrodynamics (SPH)-based algorithms for solving continuum mechanics problems in central processing unit (CPU) and hybrid architectures. Details include the advantages of using SPH, estimates of errors in the case of SPH-type approximations, and the selection of parameters. Also mentioned are parallel algorithms for SPH, including the computation time and acceleration.

关键词： Continuum mechanics Hydrodynamics smoothing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A stochastic method for solving time-fractional differential equations

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2024年 159卷 240-253页

作者： Guidotti, Nicolas L. Acebron, Juan A. Monteiro, Jose Univ Lisbon INESC ID Inst Super Tecn Lisbon Portugal Carlos III Univ Madrid Dept Math Madrid Spain

We present a stochastic method for efficiently computing the solution of time -fractional partial differential equations (fPDEs) that model anomalous diffusion problems of the subdiffusive type. After discretizing the fPDE in space, the ensuing system of fractional linear equations is solved resorting to a Monte Carlo evaluation of the corresponding Mittag-Leffler matrix function. This is accomplished through the approximation of the expected value of a suitable multiplicative functional of a stochastic process, which consists of a Markov chain whose sojourn times in every state are Mittag-Leffler distributed. The resulting algorithm is able to calculate the solution at conveniently chosen points in the domain with high efficiency. In addition, we present how to generalize this algorithm in order to compute the complete solution. For several large-scale numerical problems, our method showed remarkable performance in both shared -memory and distributed -memory systems, achieving nearly perfect scalability up to 16, 384 CPU cores.

关键词： Monte Carlo method Time-fractional differential equations Anomalous diffusion Mittag-Leffler function Matrix functions parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：