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

Sequential and parallel Tools for Model Checking Conditional Stable Properties in a Layered Way

IEEE ACCESS 2022年 10卷 133749-133765页

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

We invented a divide & conquer approach to conditional stable model checking so as to ease the state space explosion problem. As indicated by its name, the technique concentrates on conditional stable properties expressed as phi(1)??phi(2) , where phi(1) and phi(2) are state propositions. The properties can be used to formalize desired properties that self-stabilizing systems should satisfy. Self-stabilization in distributed systems was first introduced by Dijkstra and became a very crucial concept in fault tolerance to design robust systems. However, designing self-stabilizing systems need much more effort than non-stabilizing ones because the former are subject to transient errors at any time. Therefore, it is worth dedicating to conditional stable properties. In this paper, we report a sequential tool and a parallel technique/tool for the divide & conquer approach to conditional stable model checking. Some experiments are also conducted showing that our sequential and parallel tools can ease the state space explosion and improve the running performance of model checking for conditional stable properties to a certain scope, respectively.

关键词： Self-stabilizing systems conditional stable properties state space explosion divide and conquer approach parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

The Impact of Asynchrony on parallel Model-Based EAs 23

The Impact of Asynchrony on Parallel Model-Based EAs

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Guijt, Arthur Thierens, Dirk Alderliesten, Tanja Bosman, Peter A. N. Ctr Wiskunde & Informat Amsterdam Netherlands Univ Utrecht Utrecht Netherlands Leiden Univ Med Ctr Leiden Netherlands Delft Univ Technol Delft Netherlands

ISBN: (纸本)9798400701191

In a parallel EA one can strictly adhere to the generational clock, and wait for all evaluations in a generation to be done. However, this idle time limits the throughput of the algorithm and wastes computational resources. Alternatively, an EA can be made asynchronous parallel. However, EAs using classic recombination and selection operators (GAs) are known to suffer from an evaluation time bias, which also influences the performance of the approach. Model-Based Evolutionary algorithms (MBEAs) are more scalable than classic GAs by virtue of capturing the structure of a problem in a model. If this model is learned through linkage learning based on the population, the learned model may also capture biases. Thus, if an asynchronous parallel MBEA is also affected by an evaluation time bias, this could result in learned models to be less suited to solving the problem, reducing performance. Therefore, in this work, we study the impact and presence of evaluation time biases on MBEAs in an asynchronous parallelization setting, and compare this to the biases in GAs. We find that a modern MBEA, GOMEA, is unaffected by evaluation time biases, while the more classical MBEA, ECGA, is affected, much like GAs are.

关键词： Genetic algorithms Model-Based Evolutionary algorithms Linkage Learning parallel algorithms Asynchronous algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast and scalable routing protocols for data center networks

引用

Digital Communications and Networks 2023年第6期9卷 1340-1350页

作者： Mihailo Vesovic Aleksandra Smiljanic Dusan Kostic School of Electrical Engineering University of Belgrade11120BelgradeSerbia Amazon Web Services(AWS) ZurichSwitzerland

Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link *** are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize *** such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive *** routing protocols were proposed to overcome this problem by focusing on network utilization rather than ***,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing ***,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data *** aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose *** propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.

关键词： Routing protocols Data center networks parallel algorithms Distributed algorithms Algorithm design and analysis Shortest-path problem Scalability

来源：评论

学校读者我要写书评

暂无评论

Constructing parallel Association algorithms from Function Blocks 15th

Constructing Parallel Association Algorithms from Function B...

引用

15th Industrial Conference on Data Mining (ICDM)

作者： Kholod, Ivan Kuprianov, Mikhail Shorov, Andrey St Petersburg Electrotech Univ LETI St Petersburg Russia

ISBN: (纸本)9783319209104;9783319209098

The article describes the method of construction of association rules retrieval algorithms out from function blocks having a unified interface and purely functional properties. The usage of function blocks to build association rules algorithms allows modifying the existing algorithms and building new algorithms with minimum effort. Besides, the function block properties allow to transform the algorithms into parallel form, thus improving their efficiency.

关键词： Data mining parallel data mining Data mining algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Software Framework for the parallel Computation of Ground Wave Propagation Delay and Attenuation 24

A Software Framework for the Parallel Computation of Ground ...

引用

24th International Conference on the Computation of Electromagnetic Fields (COMPUMAG)

作者： Hehenkamp, Niklas Rizzi, Filippo Giacomo Grundhoefer, Lars Gewies, Stefan German Aerosp Ctr DLR Inst Commun & Nav Neustrelitz Germany

ISBN: (纸本)9798350301052

Radionavigation systems that operate in the low and medium frequency band require an accurate prediction of the electromagnetic ground wave propagation delay that is caused by the finite conductivity and permittivity of the earth's surface. To consider the complex pattern of the mixed land-sea propagation path in the application of the terrestrial MF Ranging-Mode (R-Mode) system, a parallel processing software framework for the calculation of the ground wave propagation delay and the attenuation was developed. It combines existing approaches for the calculation of electromagnetic ground-wave propagation with algorithms for the calculation of ground conductivity and permittivity following recommendation ITU-R P.527-6. Beside R-Mode, the framework enables the fast computation of propagation parameters for ground-waves in the high, medium and low frequency band on a 2D grid.

关键词： Electromagnetic propagation Ground-wave Propagation Radio navigation parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A parallel compensated Horner scheme for SIMD architecture 30

A parallel compensated Horner scheme for SIMD architecture

引用

30th IEEE Symposium on Computer Arithmetic (ARITH)

作者： Graillat, Stef Ibrahimy, Youness Jeangoudoux, Clothilde Lauter, Christoph Sorbonne Univ CNRS LIP6 Paris France IDEMIA Paris France Univ Texas El Paso Dept Comp Sci El Paso TX USA

ISBN: (纸本)9798350319224

A parallel algorithm for accurate polynomial evaluation is proposed for SIMD architectures. This is a parallelized version of the compensated Horner scheme using error-free transformations. The proposed parallel algorithm in this paper is fast and is designed to achieve a result as if computed in twice the working precision and then rounded to the working precision. Numerical results are presented showing the performance of this new parallel algorithm.

关键词： polynomial evaluation compensated algorithms error-free transformations Horner scheme rounding errors parallel algorithms SIMD AVX

来源：评论

学校读者我要写书评

暂无评论

parallel Polynomial-Time Approximation Scheme (PTAS) for Finding Compact Structural Motifs 10

Parallel Polynomial-Time Approximation Scheme (PTAS) for Fin...

引用

10th International Conference on Biomedical and Bioinformatics Engineering (ICBBE)

作者： Brocka, Bernard Yap, Sharlene Clemente, Jhoirene Univ Philippines Diliman Dept Comp Sci Quezon City Philippines

ISBN: (纸本)9798400708343

Structural motifs refer to patterns in 3D space that bear biological significance as they can indicate regions in the protein that have important roles in biochemical functions. Finding structural motifs given a set of peptides are NP-hard. Thus, there is no known polynomial-time algorithm that solves the problem optimally except when the quality of the solution is compromised. Although computationally hard, the problem is approximable and has a known polynomial-time approximation scheme (PTAS). With an existing PTAS, the problem can have a guaranteed quality that is inversely proportional to the running time. For a small error bound, the running time of the algorithm can become impractical. In this study, we design and implement a parallel version of the PTAS for the (R-C)-compact structural motif problem. Based on the empirical results, we obtained a speedup between 4x - 5x from the sequential version of the algorithm using three different protein data sets.

关键词： structural motifs approximation parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Discrete Sampling via Continuous Walks 2023

Parallel Discrete Sampling via Continuous Walks

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Anari, Nima Huang, Yizhi Liu, Tianyn Vuong, Thuy-Duong Nu, Brian Yu, Katherine Stanford Univ Stanford CA 94305 USA Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450399135

We develop a framework for sampling from discrete distributions on the hypercube {+/-1}(n)= by sampling from continuous distributions supported on R= obtained by convolution with spherical Gaussians. We show that for well-studied families of discrete distributions , convolving with Gaussians yields well-conditioned log-concave distributions, as long as the variance of the Gaussian is above an $ (1)1 degrees threshold. We then reduce the task of sampling from mu to sampling from Gaussian-convolved distributions. Our reduction is based on a stochastic process widely studied under different names: backward diffusion in diffusion models, and stochastic localization. We discretize this process in a novel way that allows for high accuracy and parallelism. As our main application, we resolve open questions Anari, Hu, Saberi, and Schild raised on the parallel sampling of distributions that admit parallel counting. We show that determinantal point processes can be sampled via RNC algorithms, that is in time log (n)(O(1))= log (n)(O(1)) using = log (n)(O(1)) processors. For a wider class of distributions, we show our framework yields Quasi-RNC sampling, i.e., log (n)(O(1)) time using log (n)(O(1)) processors. This wider class includes non-symmetric determinantal point processes and random Eulerian tours in digraphs, the latter nearly resolving another open question raised by prior work. Of potentially independent interest, we introduce and study a notion of smoothness for discrete distributions that we call transport stability, which we use to control the propagation of error in our framework. Additionally, we connect transport stability to constructions of optimally mixing local random walks and concentration inequalities.

关键词： sampling counting stochastic localization transport stability parallel algorithms determinantal point processes Eulerian tours

来源：评论

学校读者我要写书评

暂无评论

Minimizing spread of misinformation in social networks: a network topology based approach

引用

SOCIAL NETWORK ANALYSIS AND MINING 2025年第1期15卷 1-21页

作者： Ghoshal, Arnab Kumar Das, Nabanita Das, Soham Dhar, Subhankar Asutosh Coll Comp Sci Kolkata India BP Poddar Inst Management & Technol Comp Sci & Engn Kolkata India Microsoft Corp Redmond WA USA San Jose State Univ Sch Informat Syst & Technol San Jose CA USA

In the emerging landscape of online social networks (OSNs), the rapid dissemination of misinformation poses a significant challenge to the integrity of information shared among users. Hence, misinformation containment problem in OSNs has drawn significant attention nowadays. In this paper, given a fixed budget, the problem is formulated as minimizing misinformation spread (MMS) problem, which is shown to be an NP-hard problem. With the objective to combat the misinformation in real time, this paper explores a new direction to leverage the network topology to minimize the search space drastically. Based on the community structure of the OSN along with the trust relationship among nodes, a novel linear-time seed node selection algorithm is proposed here that is independent of the positions of the misinformed nodes. Once the set of seed nodes is selected, it can combat any situation of misinformation spread in the OSN, provided the community structure of the network does not change significantly. To the best of our knowledge, this work is the first where trust relationship among users is considered along with the community structure of the network, to control the spread of misinformation in real time. To analyze the diffusion dynamics pertaining to both true information and misinformation, competitive linear threshold model (LTM) with provision for belief switching is followed to provide a more realistic and comprehensive understanding of information diffusion dynamics. Extensive experimental studies on large scale OSNs demonstrate that in comparison to earlier works, the proposed technique obtains 47-74% improvements in performance parameters. Not only that, its parallel implementations also achieve around 51x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$51\times$$\end{document} speedup

关键词： Online social networks (OSNs) Trust relationships Competitive linear threshold model Community structure Misinformation minimization parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Fine-Grained parallel Cycle Enumeration algorithms

arXiv

引用

arXiv 2022年

作者： Blanuša, Jovan Ienne, Paolo Atasu, Kubilay IBM Research Europe Zurich Switzerland School of Computer and Communication Sciences LausanneCH-1015 Switzerland School of Computer and Communication Sciences Switzerland

Enumerating simple cycles has important applications in computational biology, network science, and financial crime analysis. In this work, we focus on parallelising the state-of-the-art simple cycle enumeration algorithms by Johnson and Read-Tarjan along with their applications to temporal graphs. To our knowledge, we are the first ones to parallelise these two algorithms in a fine-grained manner. We are also the first to demonstrate experimentally a linear performance scaling. Such a scaling is made possible by our decomposition of long sequential searches into fine-grained tasks, which are then dynamically scheduled across CPU cores, enabling an optimal load balancing. Furthermore, we show that coarse-grained parallel versions of the Johnson and the Read-Tarjan algorithms that exploit edge- or vertex-level parallelism are not scalable. On a cluster of four multi-core CPUs with 256 physical cores, our fine-grained parallel algorithms are, on average, an order of magnitude faster than their coarse-grained parallel counterparts. The performance gap between the fine-grained and the coarse-grained parallel algorithms widens as we use more CPU cores. When using all 256 CPU cores, our parallel algorithms enumerate temporal cycles, on average, 260× faster than the serial algorithm of Kumar and Calders. Copyright © 2022, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：