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

Fault tolerant placement of stateful VNFs and dynamic fault recovery in cloud networks

COMPUTER NETWORKS 2020年 166卷

作者： Yuan, Guochang Xu, Zichuan Yang, Binxu Liang, Weifa Chai, Wei Koong Tuncer, Daphne Galis, Alex Pavlou, George Wu, Guowei Dalian Univ Technol Sch Software Key Lab Ubiquitous Network & Serv Software Liaoni Dalian Peoples R China UCL London England Australian Natl Univ Canberra ACT Australia Bournemouth Univ Poole Dorset England Imperial Coll London London England

Traditional network functions such as firewalls and Intrusion Detection Systems (IDS) are implemented in costly dedicated hardware, making the networks expensive to manage and inflexible to changes. Network function virtualization enables flexible and inexpensive operation of network functions, by implementing virtual network functions (VNFs) as software in virtual machines (VMs) that run in commodity servers. However, VNFs are vulnerable to various faults such as software and hardware failures. Without efficient and effective fault tolerant mechanisms, the benefits of deploying VNFs in networks can be traded-off. In this paper, we investigate the problem of fault tolerant VNF placement in cloud networks, by proactively deploying VNFs in stand-by VM instances when necessary. It is challenging because VNFs are usually stateful. This means that stand-by instances require continuous state updates from active instances during their operation, and the fault tolerant methods need to carefully handle such states. Specifically, the placement of active/stand-by VNF instances, the request routing paths to active instances, and state transfer paths to stand-by instances need to be jointly considered. To tackle this challenge, we devise an efficient heuristic algorithm for the fault tolerant VNF placement. We also propose two bicriteria approximation algorithms with provable approximation ratios for the problem without compute or bandwidth constraints. We then consider the dynamic fault recovery problem given that some placed active instances of VNFs may go faulty, for which we propose an approximation algorithm that dynamically switches traffic processing from faulty VNFs to stand-by instances. Simulations with realistic settings show that our algorithms can significantly improve the request admission rate compared to conventional approaches. We finally evaluate the performance of the proposed algorithm for the dynamic fault recovery problem in a real test-bed consisting of bo

关键词： Fault-tolerance Network function virtualization Cost minimization Bicriteria approximation algorithms algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

analysis of classic algorithms on highly-threaded many-core architectures

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2018年 82卷 528-543页

作者： Ma, Lin Chamberlain, Roger D. Agrawal, Kunal Tian, Chen Hu, Ziang Washington Univ St Louis MO USA Washington Univ Comp Sci & Engn St Louis MO USA Huawei Amer Res Ctr Programming Technol Lab Santa Clara CA 95050 USA Huawei Amer Res Ctr Parallel & Distributed Lab Santa Clara CA 95050 USA Huawei Amer Res Ctr Santa Clara CA 95050 USA

The recently developed Threaded Many-core Memory (TMM) model provides a framework for analyzing algorithms for highly-threaded many-core machines such as GPUs and Cray supercomputers. In particular, it tries to capture the fact that these machines hide memory latencies via the use of a large number of threads and large memory bandwidth. The TMM model analysis contains two components: computational and memory complexity. A model is only useful if it can explain and predict empirical data. In this work, we investigate the effectiveness of the TMM model. Under this model, we analyze algorithms for 5 classic problems suffix tree/array for string matching, fast Fourier transform, merge sort, list ranking, and all-pairs shortest paths on a variety of GPUs. We also analyze memory access, matrix multiply and a sequence alignment algorithm-on a set of Cray XMT supercomputers, the latest NVIDIA and AMD GPUs. We compare the results of the analysis with the experimental findings of ours and other researchers who have implemented and measured the performance of these algorithms on a spectrum of diverse GPUs and Cray appliances. We find that the TMM model is able to predict important, non-trivial, and sometimes previously unexplained trends and artifacts in the experimental data. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Threaded Many-core Memory (TMM) model GPU XMT algorithm analysis Modeling Simulation and evaluation techniques of HPC systems

来源：评论

学校读者我要写书评

暂无评论

Parallelization and scalability analysis of inverse factorization using the chunks and tasks programming model

引用

PARALLEL COMPUTING 2019年 89卷 102548-000页

作者： Artemov, Anton G. Rudberg, Elias Rubensson, Emanuel H. Uppsala Univ Dept Informat Technol Div Sci Comp Box 337 SE-75105 Uppsala Sweden

We present three methods for distributed memory parallel inverse factorization of block-sparse Hermitian positive definite matrices. The three methods are a recursive variant of the AINV inverse Cholesky algorithm, iterative refinement, and localized inverse factorization. All three methods are implemented using the Chunks and Tasks programming model, building on the distributed sparse quad-tree matrix representation and parallel matrix-matrix multiplication in the publicly available Chunks and Tasks Matrix Library (CHTML). Although the algorithms are generally applicable, this work was mainly motivated by the need for efficient and scalable inverse factorization of the basis set overlap matrix in large scale electronic structure calculations. We perform various computational tests on overlap matrices for quasi linear glutamic acid-alanine molecules and three-dimensional water clusters discretized using the standard Gaussian basis set STO-3G with up to more than 10 million basis functions. We show that for such matrices the computational cost increases only linearly with system size for all the three methods. We show both theoretically and in numerical experiments that the methods based on iterative refinement and localized inverse factorization outperform previous parallel implementations in weak scaling tests where the system size is increased in direct proportion to the number of processes. We show also that, compared to the method based on pure iterative refinement, the localized inverse factorization requires much less communication. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Parallel computing Sparse matrix algorithms Scalable algorithms Large-scale computing algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Bringing Real-World Data, Interactive Games and Visualizations into Early CS Courses 20

Bringing Real-World Data, Interactive Games and Visualizatio...

引用

Proceedings of the 51st ACM Technical Symposium on Computer Science Education

作者： Kalpathi Subramanian Erik Saule Jamie Payton The University of North Caroline at Charlotte Charlotte NC USA Temple University Philadelphia PA USA

ISBN: (纸本)9781450367936

This workshop provides instructors with a hands-on introduction to BRIDGES, a software infrastructure for programming assignments in early computer science courses, including introductory programming (CS1, CS2), data structures, and algorithm analysis. BRIDGES provides capabilities for creating more engaging programming assignments, including: (1) a simplified API for accessing real-world data sets, including from social networks; scientific, government, and civic organizations; and movie, music, and literature collections; (2) interesting visualizations of the data, (3) an easy to use API that supports creation of games that leverage real-world data, and, (4) algorithm benchmarking. Workshop attendees will engage in hands-on experience with BRIDGES with multiple datasets and will have the opportunity to discuss how BRIDGES can be used in their own courses.

关键词： algorithm analysis data structures interactive games visualization, real-world data

来源：评论

学校读者我要写书评

暂无评论

Pipeline-aware Logic Deduplication in High-Level Synthesis for Post-Quantum Cryptography algorithms 20

Pipeline-aware Logic Deduplication in High-Level Synthesis f...

引用

Proceedings of the 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays

作者： Changsu Kim Yongwoo Lee Shinnung Jeong Wen Wang Jakub Szefer Hanjun Kim POSTECH Seoul South Korea Yonsei University Seoul South Korea Yale University New Haven CT USA

ISBN: (纸本)9781450370998

With the technical advance of quantum computers that can solve intractable problems for conventional computers, many of the currently used public-key cryptosystems become vulnerable. Recently proposed post-quantum cryptography (PQC) is secure against both classical and quantum computers, but existing embedded systems such as smart card can not easily support the PQC algorithms due to their much larger key sizes and more complex arithmetics. To accelerate the PQC algorithms, embedded systems have to embed the PQC hardware blocks, which can lead to huge hardware design costs. Although High-Level Synthesis (HLS) helps significantly reduce the design costs, current HLS frameworks produce inefficient hardware design for the PQC algorithms in terms of area and performance. This work analyzes common features of the PQC algorithms and proposes a new pipeline-aware logic deduplication method in HLS. The proposed method shares commonly invoked logic across hardware design while considering load balancing in pipeline and resolving dynamic memory accesses. This work implements FPGA hardware design of seven PQC algorithms in the round 2 candidates from the National Institute of Standards and Technology (NIST) PQC standardization process. Compared to commercial HLS framework, the proposed method achieves an area-delay-product reduction by 34.5%.

关键词： pipeline processing algorithm analysis post-quantum cryptography high-level synthesis fpga resource sharing

来源：评论

学校读者我要写书评

暂无评论

On the Expressive Power of Declarative Constructs in Interactive Document Scripts 19

On the Expressive Power of Declarative Constructs in Interac...

引用

19th ACM Symposium on Document Engineering (DocEng)

作者： Boyer, John M.

ISBN: (纸本)9781450368872

It is difficult to generally compare the succinctness of declarative versus imperative programming as source code size varies. In imperative programs, basic operations have constant cost, but they tend to be more verbose than declarative programs, which increases the potential for defects. This paper presents a novel approach for a generalized comparison by transforming the problem into comparing executed code size of a benchmark imperative algorithm with a partially declarative variant of the same algorithm. This allows input size variation to substitute for source code size variation. For implementation, we use a multiparadigm language called XForms that contains both declarative XPath expressions and imperative script actions for interacting with XML data within web and office documents. A novel partially declarative variant of the quicksort is presented. Amortized analysis shows that only O(n) imperative actions are executed, so the expressive power of the declarative constructs is at least Omega(log n). In general, declarative constructs can have an order of magnitude expressive power advantage compared with only using basic imperative operations. The performance cost factor of the expressive power advantage was determined to be O(log(2) n) based on a novel dynamic projection from the generalized tree structure of XML data to a height balanced binary tree.

关键词： Interactive documents Multiparadigm languages algorithm analysis Document models and structures Document representation and standards Rich web applications

来源：评论

学校读者我要写书评

暂无评论

With Random Parametric Equation of Circle Inscribed Polygon Generation algorithm and analysis

With Random Parametric Equation of Circle Inscribed Polygon ...

引用

International Conference on Applied Mechanics and Materials (ICAMM 2012)

作者： Sun, Yanhai Song, Laizhong Shen, Tao China Three Gorges Univ Coll Sci Yichang 443002 Peoples R China

ISBN: (纸本)9783037855911

For getting the parametric equation of random polygon, by the basic extension factor to stretch the round, there generates polygon of meeting the required conditions. Such algorithm overcomes the disadvantage in the generation of polygon from round under control of a single parameter and the complication of mathematical background. Firstly, a detailed introduction is given to the basic extension factor and the selection of relevant coefficient, and then the errors of such algorithm are analyzed. And the experimental result shows that the mathematical background of such method is relatively easy, the parameters are easy to control and constitute, and the generation of arbitrary polygon is available with high precision. Such the parametric equation of random polygon and method can be used in relevant fields such as geometric modeling, CAD/CAM, and computer graphics.

关键词： Random polygon parametric equation Free deformation Polygonal aggregate model algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

New algorithms for Computing Field of Vision over 2D Grids

New Algorithms for Computing Field of Vision over 2D Grids

引用

作者： Evan Debenham University of Western Ontario

学位级别：硕士

In many computer games checking whether one object is visible from another is very important. Field of Vision (FOV) refers to the set of locations that are visible from a specific position in a scene of a computer game. Once computed, an FOV can be used to quickly determine the visibility of multiple objects from a given position. This thesis summarizes existing algorithms for FOV computation, describes their limitations, and presents new algorithms which aim to address these limitations. We first present an algorithm which makes use of spatial data structures in a way which is new for FOV calculation. We then present a novel technique which updates a previously calculated FOV, rather than re-calculating FOV from scratch. We then compare our algorithms to existing FOV algorithms and show that they provide substantial improvements to running time and efficiency of memory access.

关键词： Field of Vision (FOV) Computer Games Visibility Determination algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

An Efficient algorithm for the Shortest Vector Problem

引用

IEEE ACCESS 2018年 6卷 61478-61487页

作者： Chuang, Yu-Lun Fan, Chun-, I Tseng, Yi-Fan Natl Sun Yat Sen Univ Dept Comp Sci & Engn Kaohsiung 81424 Taiwan Natl Sun Yat Sen Univ Informat Secur Res Ctr Kaohsiung 80424 Taiwan Natl Sun Yat Sen Univ Intelligent Elect Commerce Res Ctr Kaohsiung 80424 Taiwan

Lattice is widely used in cryptography since it has potential for defending quantum attacks. One of the significant problems in such cryptography is the shortest vector problem (SVP). This problem is to find the non-zero shortest vector in lattice. The SVP is an NP-hard problem under randomized reductions proven by Ajtai, and many cryptosystems are secure under the assumption that SVP is hard, such as NTRU. On the other hand, some primitives of lattice-based cryptography require relatively short vectors. In this paper, we propose a new SVP algorithm that can be performed in time complexity O(n(3)). We also prove that the Hermite factor of the proposed algorithm is polynomial-bounded.

关键词： Shortest vector problem algorithm analysis optimization theory lattice lattice-based cryptography

来源：评论

学校读者我要写书评

暂无评论

Throughput optimization for admitting NFV-enabled requests in cloud networks

引用

COMPUTER NETWORKS 2018年第Oct.9期143卷 15-29页

作者： Xu, Zichuan Liang, Weifa Galis, Alex Ma, Yu Xia, Qiufen Xu, Wenzheng Dalian Univ Technol Dalian Peoples R China Australian Natl Univ Canberra ACT Australia UCL London England Sichuan Univ Chengdu Sichuan Peoples R China

Network softwarization is emerging as a techno-economic transformation trend that impacts the way that network service providers deliver their network services significantly. As a key ingredient of such a trend, network function virtualization (NFV) is shown to enable elastic and inexpensive network services for next-generation networks, through deploying flexible virtualized network functions (VNFs) running in virtual computing platforms. Different VNFs can be chained together to form different service chains for different network services, to meet various user data routing demands. From the service provider point of view, such services are usually implemented by VNF instances in a cloudlet network consisting of a set of data centers and switches. In this paper we consider provisioning network services in a cloud network for implementing VNF instances of service chains, where the VNF instances in each data center are partitioned into K types with each hosting one type of service chain. We investigate the throughput maximization problem with the aim to admit as many user requests as possible while minimizing the implementation cost of the requests, assuming that limited numbers of instances of each service chain have been instantiated in data centers. We first show the problem is NP-Complete, and propose an optimal algorithm for a special case of the problem when all requests have identical packet rates;otherwise, we devise two approximation algorithms with approximation ratios, depending on whether the packet traffic of each request is splittable. If arrivals of future requests are not known in advance, we study the online throughput maximization problem by proposing an online algorithm with a competitive ratio. We finally conduct experiments to evaluate the performance of the proposed algorithms by simulations. Simulation results show that the performance of the proposed algorithms are promising. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Throughput maximization Cost minimization Approximation algorithms Online algorithms Network function virtualization algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：