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

arXiv 2024年

作者： Hoppenworth, Gary Xu, Yinzhan Xu, Zixuan University of Michigan United States Massachusetts Institute of Technology United States

We study distance preservers, hopsets, and shortcut sets in n-node, m-edge directed graphs, and show improved bounds and new reductions for various settings of these problems. Our first set of results is about exact and approximate distance preservers. We give the following bounds on the size of directed distance preservers with p demand pairs: • Õ(n5/6p2/3 + n) edges for exact distance preservers in unweighted graphs, and • Ω(n2/3p2/3) edges for approximate distance preservers with any given finite stretch, in graphs with arbitrary aspect ratio. Additionally, we establish a new directed-to-undirected reduction for exact distance preservers. We show that if undirected distance preservers have size O(nλpµ + n) for constants λ, µ > 0, then directed distance preservers have size O (n 1 / 2−λ p 1+µ−λ / 2-λ + n1/2p + n) . As a consequence of the reduction, if state-of-the-art upper bounds for undirected preservers can be improved for some p ≤ n, then so can state-of-the-art upper bounds for directed preservers. Our second set of results is about directed hopsets and shortcut sets. For hopsets in directed graphs, we prove that the hopbound is: • Ω(n2/9) for O(m)-size shortcut sets, improving the previous Ω(n1/5) bound [Vassilevska Williams, Xu and Xu, SODA 2024], • Ω(n2/7) for O(m)-size exact hopsets in unweighted graphs, improving the previous Ω(n1/4) bound [Bodwin and Hoppenworth, FOCS 2023], and • Ω(n1/2) for O(n)-size approximate hopsets with any given finite stretch, in graphs with arbitrary aspect ratio. This result establishes a separation between this setting and O(n)size approximate hopsets for graphs with polynomial aspect ratio, which are known to have an Õ(n1/3) upper bound [Bernstein and Wein, SODA 2023]. Copyright © 2024, The Authors. All rights reserved.

关键词： data flow graphs

来源：评论

学校读者我要写书评

暂无评论

Resilient dataflow Graph Embedding for Programmable Software Switches 11

Resilient Dataflow Graph Embedding for Programmable Software...

引用

11th International Workshop on Resilient Networks Design and Modeling (RNDM)

作者： Levai, Tamas Retvari, Gabor Budapest Univ Technol & Econ Dept Telecommun & Media Informat Budapest Hungary Budapest Univ Technol & Econ MTA BME Informat Syst Res Grp Budapest Hungary

ISBN: (纸本)9781728146980

Programmable software switches have become crucial building blocks in a wide range of applications, from (virtual) data center networking to telco clouds. Modern usecases, such as 5G, require very low latency, large throughput, and high availability. Software switches generally realize the packet processing pipeline as a dataflow graph: graph nodes correspond to simple packet processing operations and graph edges represent the control flow. The efficiency and dependability of the software switch critically depends on the way the dataflow graph is mapped to the underlying hardware resources. In this paper, we focus on dataflow graph embedding in a software switching context. We present an embedding approach which minimizes performance loss on inter-CPU communication across packet-processing control flow chains, and is resilient against a single CPU failure. The embedding is easy to generalize to N CPU failures. We formulate the dataflow graph embedding problem as a mathematical program, characterize the computational complexity, and we propose optimal and heuristic algorithms to solve it. The viability of our approach is confirmed in comprehensive numerical analysis on a 5G packet processing pipeline, taken from an industrial 5G NFV benchmark suite.

关键词： software switches data flow graphs software-defined networks resilience

来源：评论

学校读者我要写书评

暂无评论

Transforming data flow diagrams for privacy compliance (long version)

arXiv

引用

arXiv 2020年

作者： Alshareef, Hanaa Stucki, Sandro Schneider, Gerardo Chalmers University of Technology Gothenburg Sweden University of Gothenburg Gothenburg Sweden

Recent regulations, such as the European General data Protection Regulation (GDPR), put stringent constraints on the handling of personal data. Privacy, like security, is a non-functional property, yet most software design tools are focused on functional aspects, using for instance data flow Diagrams (DFDs). In previous work, a conceptual model was introduced where DFDs could be extended into so-called Privacy-Aware data flow Diagrams (PA-DFDs) with the aim of adding specific privacy checks to existing DFDs. In this paper, we provide an explicit algorithm and a proof-of-concept implementation to transform DFDs into PA-DFDs. Our tool assists software engineers in the critical but error-prone task of systematically inserting privacy checks during design (they are automatically added by our tool) while still allowing them to inspect and edit the PA-DFD if necessary. We have also identified and addressed ambiguities and inaccuracies in the high-level transformation proposed in previous work. We apply our approach to two realistic applications from the construction and online retail sectors. Copyright © 2020, The Authors. All rights reserved.

关键词： data flow graphs

来源：评论

学校读者我要写书评

暂无评论

Contextualisation of data flow Diagrams for security analysis

arXiv

引用

arXiv 2020年

作者： Faily, Shamal Scandariato, Riccardo Shostack, Adam Sion, Laurens Ki-Aries, Duncan Department of Computing & Informatics Bournemouth University Poole United Kingdom Chalmers and University of Gothenburg Gothenburg Sweden Shostack & Associates Seattle United States imec-DistriNet KU Leuven Leuven Belgium

data flow diagrams (DFDs) are popular for sketching systems for subsequent threat modelling. Their limited semantics make reasoning about them difficult, but enriching them endangers their simplicity and subsequent ease of take up. We present an approach for reasoning about tainted data flows in design-level DFDs by putting them in context with other complementary usability and requirements models. We illustrate our approach using a pilot study, where tainted data flows were identified without any augmentations to either the DFD or its complementary models. Copyright © 2020, The Authors. All rights reserved.

关键词： data flow graphs

来源：评论

学校读者我要写书评

暂无评论

AROM: Processing big data with data flow graphs and functional programming

AROM: Processing big data with Data Flow Graphs and function...

引用

2012 4th IEEE International Conference on Cloud Computing Technology and Science, CloudCom 2012

作者： Tran, Nam-Luc Skhiri, Sabri Lesuisse, Arthur Zimanyi, Esteban Euranova RandD Belgium Université Libre de Bruxelles Belgium

ISBN: (纸本)9781467345095

The development in computational processing has driven towards distributed processing frameworks performing tasks in parallel setups. The recent advances in Cloud Computing have widely contributed to this tendency. The MapReduce model proposed by Google is one of the most popular despite the well-known limitations inherent to the model which constrain the types of jobs that can be expressed. On the other hand models based on data flow graphs (DFG) for the processing and the definition of the jobs, while more complex to express, are more general and suitable for a wider range of tasks, including iterative and pipelined tasks. In this paper we present AROM, a framework for large scale distributed processing based on DFG to express the jobs and which uses paradigms from functional programming to define the operators. The former leads to more natural handling of pipelined tasks while the latter enhances genericity and reusability of the operators, as shown by our tests on a parallel and pipelined job performing the calculation of PageRank. © 2012 IEEE.

关键词： data flow graphs

来源：评论

学校读者我要写书评

暂无评论

Isomorphic Subgraph-based Problem Reduction for Resource Minimal Modulo Scheduling

Isomorphic Subgraph-based Problem Reduction for Resource Min...

引用

International Conference on Reconfigurable Computing and FPGAs (ReConFig)

作者： Patrick Sittel Nicolai Fiege Martin Kumm Peter Zipf University of Kassel University of Applied Sciences Fulda

ISBN: (纸本)9781728119588

Modulo scheduling is a powerful method to increase throughput in high-level synthesis for digital hardware design. When facing large designs, optimal approaches are likely to time out and heuristics fail to provide satisfying throughput and latency. We propose an isomorphic subgraph-based reduction of the input data-flow graph (DFG) that is applied before scheduling, in order to solve the modulo scheduling problem faster without changing the optimal initiation interval (II) and allocated hardware. Our results show a solving time speedup of 5× on average and up to 102× for large designs. Using the proposed pre-processing step, the II achieved could be reduced by 33% on average for SDC-based modulo schedulers. And in ILP-based scheduling, we could classify 15% more solutions as optimal within the same time compared to solutions provided without applying our transformation.

关键词： data flow graphs field programmable gate arrays graph theory high level synthesis logic design optimisation pipeline processing processor scheduling high level synthesis Field programmable gate arrays data flow graphs Pipeline processing scheduling of multiprocessor Logic design Graph theory Modulo Problem Reduction Time out Isomorphic

来源：评论

学校读者我要写书评

暂无评论

Design and Implementation of Integrated Software Research and Community Service at State Polytechnic of Manado 2

Design and Implementation of Integrated Software Research an...

引用

2nd International Joint Conference on Science and Technology (IJCST)

作者： Saroinsong, T. Kondoj, M. A. S. Kandiyoh, G. Pontoh, G. State Polytech Manado Mech Engn Manado City North Sulawesi Indonesia State Polytech Manado Informat Engn Manado City North Sulawesi Indonesia State Polytech Manado Civil Engn Manado City North Sulawesi Indonesia

The State Polytechnic of Manado (Polimdo) is one of the reliable institutions in North Sulawesi that first implemented ISO 9001. But the accreditation of the institution has not been satisfactory, it means there is still much to be prepared to achieve the expected target. One of the criteria of assessment of institutional accreditation is related to research activities and social work in accordance with the standard seven. data documentation systems related to research activities and social work are not well integrated and well documented in all existing work units. This causes the process of gathering information related to the activities and the results of research and social work in order to support the accreditation activities of the institution is still not efficient. This study aims to build an integrated software in all work units in Polimdo to obtain documentation and data synchronization in support of activities or reporting of documents accreditation institution in accordance with standard seven specifically in terms of submission of research proposal and dedication. The software will be developed using RUP method with analysis using data flow diagram and ERM so that the result of this research is documentation and synchronization of data and information of research activity and community service which can be used in preparing documents report for accreditation institution.

关键词： data flow graphs

来源：评论

学校读者我要写书评

暂无评论

Modeling and Investigating a Race Condition Detection Algorithm for Multithread Computational Systems

Modeling and Investigating a Race Condition Detection Algori...

引用

International Conference on Complex Systems: Control and Modeling Problems

作者： Polina Barabanova Valery Zasov Samara State Transport University SamaraRussia

The paper presents the results of the comparative analysis of various methods for detecting and localizing race conditions in multithread systems with shared memory. The paper highlights the advantages of the static method, one of the effective implementations of which is an algorithm based on the analysis of a program presented as a control flow graph or one of its varieties - a joint flow execution graph. To solve applied problems, we carried out a software implementation of this algorithm, which served as the basis for developing a test program package for automated detection of race conditions in multithread systems. The reliability and efficiency of the program package is confirmed by the results of computer simulation illustrated using the Peterson algorithm.

关键词： data flow graphs multiprocessing programs multi-threading Multithreading data flow graphs control flow diagram Computer Simulation hazards and race conditions software implementation algorithms Modeling Racial Stocks Detection algorithms

来源：评论

学校读者我要写书评

暂无评论

Design and research of operational and pipelined binary number sorting devices 18

Design and research of operational and pipelined binary numb...

引用

18th International Multidisciplinary Scientific Geoconference, SGEM 2018

作者： Gryga, Volodymyr Karpinski, Mikolaj Kochan, Roman Voronych, Artur Kogut, Igor Vasyl Stefanyk Precarpathian National University Ukraine University of Bielsko-Biala Poland Ivano-Frankivsk National Technical University Oil and Gas Ukraine

ISBN: (纸本)9786197408355

There is carried out the analysis of parallel methods of binary numbers sorting, which allows to represent the algorithm in a graphical form. Particular attention is paid to the methods of binary numbers sorting, which are subject to hardware implementation, namely: the Batcher’s method, the method of "even-odd" permutation, the merging method, the method of "ideal shuffling" and the modified "bubbles" method. The theory of data flow graph of algorithm is studied, which is the basis of graphically specified sorting algorithm and can be paralleled by tiers in the so-called "tier-parallel form", which is the basis for constructing operational and pipelined operating device of binary numbers from the graphical representation of executable algorithms. When applying this theory, the functional operators of the algorithm are replaced by the operating blocks, and arcs-by the lines of data transmission. The theory of spatio-temporal graphs is considered, which allows the same type of functional operators of the data flow graph of the sorting algorithm to combine, using compression along the width and height of the graph, resulting in the corresponding type of spatio-temporal graph with improved computational complexity, which makes it possible to design sequential, serial-parallel, iterative and combined multi-step operating devices with significant reduction of hardware costs and reduced area of the crystal of the integrated circuit for it implementation. There is developed the structures of algorithmic, pipelined and multi-step operating devices of the studied methods of parallel binary numbers sorting and their complexity characteristics are calculated. The advanced circuit design solutions for constructing components of data structures have been proposed, which made it possible to reduce the hardware complexity and increase their time complexity. The analytical expressions for the evaluation of the complexity of the developed operating devices are obtained. It has been

关键词： data flow graphs

来源：评论

学校读者我要写书评

暂无评论

A Thread Modularity Approach for Verification Concurrent Software Based on Abstract Interpretation 25

A Thread Modularity Approach for Verification Concurrent Sof...

引用

25th Asia-Pacific Software Engineering Conference (APSEC)

作者： Jiang, Qingyu Liu, Jing Hu, Haodong East China Normal Univ Shanghai Key Lab Trustworthy Comp Shanghai 200062 Peoples R China AECC Aero Engine Control Syst Inst Wuxi 214100 Jiangsu Peoples R China

ISBN: (纸本)9781728119700

Ensuring the reliability of concurrency software systems is difficult due to the interaction between threads. This article discusses the requirements for formal verification of concurrent embedded software and proposes a constraint-based flow-sensitive static analysis for concurrent avionics software by iteratively composing thread-modular abstract interpreters. These constraint are based on data-flow graphs and used to rule out patterns of thread interference that can not occur in a real program execution. Our new method has the advantage of being more accurate than existing, flow-insensitive, static avionics analyzers while remaining scalable and providing the expected soundness and termination guarantees. We implemented our method and evaluated it on an industrial setting, hinting at the maturity of our approach.

关键词： Concurrency Abstract interpretation Thread invariants Thread-modular data flow graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：