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

Fast In-kernel Traffic sketching in eBPF

ACM SIGCOMM COMPUTER COMMUNICATION REVIEW 2023年第1期53卷 3-13页

作者： Miano, Sebastiano Chen, Xiaoqi Ben Basat, Ran Antichi, Gianni Queen Mary Univ London London England Princeton Univ Princeton NJ 08544 USA UCL London England Politecn Milan Milan Italy

The extended Berkeley Packet Filter (eBPF) is an infrastructure that allows to dynamically load and run micro-programs directly in the Linux kernel without recompiling it. In this work, we study how to develop high-performance network measurements in eBPF. We take sketches as case-study, given their ability to support a wide-range of tasks while providing low-memory footprint and accuracy guarantees. We implemented NitroSketch, the state-of-the-art sketch for user-space networking and show that best practices in user-space networking cannot be directly applied to eBPF, because of its different performance characteristics. By applying our lesson learned we improve its performance by 40% compared to a naive implementation.

关键词： Sketch eBPF XDP Software Switch sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

ON APPROXIMATING MATRIX NORMS IN DATA STREAMS

引用

SIAM JOURNAL ON COMPUTING 2019年第6期48卷 1643-1697页

作者： Li, Yi Nguyen, Huy L. Woodruff, David P. Nanyang Technol Univ Div Math Singapore 637371 Singapore Northeastern Univ Khoury Coll Comp Sci Boston MA 02115 USA Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

This paper presents a systematic study of the space complexity of estimating the Schatten p-norms of an n x n matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered. Furthermore, two sketching models, general linear sketching and bilinear sketching, are considered. When p is not an even integer, we show that any one-pass algorithm with constant success probability requires near-linear space in terms of bits. This lower bound holds even for sparse matrices, i.e., matrices with O(1) nonzero entries per row and per column. However, when p is an even integer, we give for sparse matrices an upper bound which, up to logarithmic factors, is the same as estimating the pth moment of an n-dimensional vector. These results considerably strengthen lower bounds in previous work for arbitrary (not necessarily sparse) matrices. Similar near-linear lower bounds are obtained for Ky Fan norms, SVD entropy, eigenvalue shrinkers, and M-estimators, many of which could have been solvable in logarithmic space prior to this work. The results for general linear sketches give separations in the sketching complexity of Schatten p-norms with the corresponding vector p-norms, and rule out a table-lookup nearest-neighbor search for p = 1, making progress on a question of Andoni. The results for bilinear sketches are tight for the rank problem and nearly tight for p >= 2;the latter is the first general subquadratic upper bound for sketching the Schatten norms.

关键词： Schatten norm matrix norm streaming algorithm approximation algorithm sketching algorithm numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

LEARNING APPROACH FOR FAST APPROXIMATE MATRIX FACTORIZATIONS 47

LEARNING APPROACH FOR FAST APPROXIMATE MATRIX FACTORIZATIONS

引用

47th IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Yu, Haiyan Qin, Zhen Zhu, Zhihui Univ Denver Elect & Comp Engn Denver CO 80208 USA

ISBN: (纸本)9781665405409

Efficiently computing an (approximate) orthonormal basis and low-rank approximation for the input data X plays a crucial role in data analysis. One of the most efficient algorithms for such tasks is the randomized algorithm, which proceeds by computing a projection XA with a random sketching matrix A of much smaller size, and then computing the orthonormal basis as well as low-rank factorizations of the tall matrix XA. While a random matrix A is the de facto choice, in this work, we improve upon its performance by utilizing a learning approach to find an adaptive sketching matrix A from a set of training data. We derive a closed-form formulation for the gradient of the training problem, enabling us to use efficient gradient-based algorithms. We also extend this approach for learning structured sketching matrix, such as the sparse sketching matrix that performs as selecting a few number of representative columns from the input data. Our experiments on both synthetical and real data show that both learned dense and sparse sketching matrices outperform the random ones in finding the approximate orthonormal basis and low-rank approximations.

关键词： Low-rank matrix approximation learning approach sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

NitroSketch: Robust and General Sketch-based Monitoring in Software Switches 19

NitroSketch: Robust and General Sketch-based Monitoring in S...

引用

Conference of the ACM-Special-Interest-Group-on-Data-Communication (SIGCOMM)

作者： Liu, Zaoxing Ben-Basat, Ran Einziger, Gil Kassner, Yaron Braverman, Vladimir Friedman, Roy Sekar, Vyas Carnegie Mellon Univ Pittsburgh PA 15213 USA Harvard Univ Cambridge MA 02138 USA Ben Gurion Univ Negev Beer Sheva Israel Technion Haifa Israel Johns Hopkins Univ Baltimore MD 21218 USA

ISBN: (纸本)9781450359566

Software switches are emerging as a vital measurement vantage point in many networked systems. sketching algorithms or sketches, provide high-fidelity approximate measurements, and appear as a promising alternative to traditional approaches such as packet sampling. However, sketches incur significant computation overhead in software switches. Existing efforts in implementing sketches in virtual switches make sacrifices on one or more of the following dimensions: performance (handling 40 Gbps line-rate packet throughput with low CPU footprint), robustness (accuracy guarantees across diverse workloads), and generality (supporting various measurement tasks). In this work, we present the design and implementation of NitroSketch, a sketching framework that systematically addresses the performance bottlenecks of sketches without sacrificing robustness and generality. Our key contribution is the careful synthesis of rigorous, yet practical solutions to reduce the number of per-packet CPU and memory operations. We implement NitroSketch on three popular software platforms (Open vSwitch-DPDK, ***-VPP, and BESS) and evaluate the performance. We show that accuracy is comparable to unmodified sketches while attaining up to two orders of magnitude speedup, and up to 45% reduction in CPU usage.

关键词： Sketch Software Switch Virtual Switch Flow Monitoring sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

Large Covariance Estimation from Streaming Data with Knowledge-Based Sketch Matrix 29th

Large Covariance Estimation from Streaming Data with Knowled...

引用

29th International Conference on Database Systems for Advanced Applications (DASFAA)

作者： Tan, Xiao Wang, Zhaoyang Wang, Meng Shen, Dian Chen, Weitong Wang, Beilun Southeast Univ Nanjing Peoples R China Adelaide Univ Adelaide SA 5005 Australia

ISBN: (纸本)9789819755684;9789819755691

Covariance matrix estimation is an important problem in statistics, with wide applications in finance, neuroscience, meteorology, oceanography, and other fields. However, when the data are high-dimensional and constantly generated and updated in a streaming fashion, the covariance matrix estimation faces huge challenges, including the curse of dimensionality and limited memory space. The existing methods either assume sparsity, ignoring any possible common factor among the variables, or obtain poor performance in recovering the covariance matrix directly from sketched data. To address these issues, we propose a novel method - KEEF: Knowledge-based Time and Memory Efficient Covariance Estimator in Factor Model. Our method leverages historical data to train a knowledge-based sketch matrix, which is used to accelerate the factor analysis of streaming data and directly estimates the covariance matrix from the sketched data. We provide theoretical guarantees, showing the advantages of our method in terms of time and space complexity, as well as accuracy. We conduct extensive experiments on synthetic and real-world data, comparing KEEF with several state-of-the-art methods, demonstrating the superior performance of our method.

关键词： Covariance Matrix Streaming Data sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

Factor Model-Based Large Covariance Estimation from Streaming Data Using a Knowledge-Based Sketch Matrix 24

Factor Model-Based Large Covariance Estimation from Streamin...

引用

33rd ACM International Conference on Information and Knowledge Management (CIKM)

作者： Tan, Xiao Wang, Zhaoyang Qian, Hao Zhou, Jun Duan, Peibo Shen, Dian Wang, Meng Wang, Beilun Southeast Univ Nanjing Peoples R China Ant Grp Hangzhou Peoples R China Monash Univ Melbourne Vic Australia Tongji Univ Shanghai Peoples R China

ISBN: (纸本)9798400704369

Covariance matrix estimation is an important problem in statistics, with wide applications in finance, neuroscience, meteorology, oceanography, and other fields. However, when the data are high-dimensional and constantly generated and updated in a streaming fashion, the covariance matrix estimation faces huge challenges, including the curse of dimensionality and limited memory space. The existing methods either assume sparsity, ignoring any possible common factor among the variables, or obtain poor performance in recovering the covariance matrix directly from sketched data. To address these issues, we propose a novel method - KEEF: Knowledge-based Time and Memory Efficient Covariance Estimator in Factor Model and its extended variation. Our method leverages historical data to train a knowledge-based sketch matrix, which is used to accelerate the factor analysis of streaming data and directly estimates the covariance matrix from the sketched data. We provide theoretical guarantees, showing the advantages of our method in terms of time and space complexity, as well as accuracy. We conduct extensive experiments on synthetic and real-world data, comparing KEEF with several state-of-the-art methods, demonstrating the superior performance of our method.

关键词： Covariance Matrix Streaming Data sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast multiplication of random dense matrices with sparse matrices 38

Fast multiplication of random dense matrices with sparse mat...

引用

International Parallel and Distributed Processing Symposium (IPDPS)

作者： Liang, Tianyu Murray, Riley Buluc, Aydin Demmel, James Univ Calif Berkeley Elect Engn & Comp Sci Dept Berkeley CA 94720 USA Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA Int Comp Sci Inst Berkeley CA USA Sandia Natl Labs Albuquerque NM USA

ISBN: (纸本)9798350387117;9798350387124

This work focuses on accelerating the multiplication of a dense random matrix with a (fixed) sparse matrix, which is frequently used in sketching algorithms. We develop a novel scheme that takes advantage of blocking and recomputation (on-the-fly random number generation) to accelerate this operation. The techniques we propose decrease memory movement, thereby increasing the algorithm's parallel scalability in shared memory architectures. On the Intel Frontera architecture, our algorithm can achieve 2x speedups over libraries such as Eigen and Intel MKL on some examples. In addition, with 32 threads, we can obtain a parallel efficiency of up to 45%. We also present a theoretical analysis for the memory movement lower bound of our algorithm, showing that under mild assumptions, it's possible to beat the data movement lower bound of general matrix-matrix multiply (GEMM) by a factor of root M, where M is the cache size. Finally, we incorporate our sketching method into a randomized algorithm for overdetermined least squares with sparse data matrices. Our results are competitive with SuiteSparse for highly overdetermined problems;in some cases, we obtain a speedup of 10x over SuiteSparse.

关键词： HPC Numerical Linear Algebra sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

Enabling Practical and Performant Sketch-Based Network Telemetry on Programmable Switches

Enabling Practical and Performant Sketch-Based Network Telem...

引用

作者： Namkung, Hun Carnegie Mellon University

学位级别：Ph.D., Doctor of Philosophy

Network telemetry plays an essential role in managing network systems. Various flow-level traffic measurement results (e.g., identifying heavy flows) are needed by network operators to make the right management decisions. In this thesis, we envision performant and practical flow-level network telemetry that satisfies four requirements: (1) low resource footprint, (2) high measurement accuracy, (3) high packet processing speed, and (4) support for diverse measurement results. State-of-the-art techniques of packet sampling suffer from low measurement accuracy. Instead, an alternative type of technique called sketching algorithms, or sketches, has received considerable attention due to their high measurement accuracy and resource efficiency. With recent advances in programmable network hardware technology, programmable switches have become a promising platform to program and deploy sketches with Tbps scale of high packet processing speed. Although running sketches on a programmable switch is a promising way to achieve the goal of satisfying the four requirements, there is a gap between sketches and programmable switches. While there have been continuous improvements on the theoretical side of sketching algorithms for better resource-accuracy tradeoffs, much less attention has been paid to how to efficiently run sketches on actual hardware switches. Specifically, there are three practical challenges: first, sketch implementations require excessive resources on the hardware switch, making rich sketch-based telemetry often infeasible. Second, it takes a long time for developers to implement sketches on programmable switches because of the complex underlying hardware architecture. Third, while packets update counters in the switch data plane, the switch control plane also reads and resets the counters, causing consistency problems that degrade measurement accuracy significantly. In this thesis, we present techniques that enable performant and practical sketchbased network

关键词： Network monitoring Network telemetry Programmable network hardware Programmable switch sketching algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：