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

Fast Multiple-Precision Integer Division Using Intel AVX-512

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTING 2023年第1期11卷 224-236页

作者： Edamatsu, Takuya Takahashi, Daisuke Univ Tsukuba Grad Sch Sci & Technol Tsukuba Ibaraki 3058573 Japan Univ Tsukuba Ctr Computat Sci Tsukuba Ibaraki 3058577 Japan

This paper reports on the implementation of a large integer division method that uses Intel Advanced Vector Extensions 512 (AVX-512), which is a 512-bit Single Instruction Multiple Data (SIMD) instruction set, and proposes a modification to a conventional division algorithm that makes it more SIMD instruction-friendly. More specifically, we use the Integer Fused Multiply-Add AVX-512 (AVX-512IFMA) subset, which is an instruction set that works well with large integer multiplication, to compute large integer divisions via a multiplication-based approach with a reciprocal. For the division process, we apply the most basic algorithm and divide-and-conquer methods and then use several techniques to compute efficiently with SIMD instructions in our implementation. We then combine these techniques and methods to implement our division function so that it can flexibly handle various sizes. To evaluate the performance of our proposed implementation, we executed our division program and the GNU Multiple Precision Arithmetic Library (GMP) on a Cannon Lake microarchitecture processor. A comparison of the execution times for our division program and GMP with various sizes showed that our method resulted in performance improvements of 25% to 35% on average, thus indicating that SIMD instructions are effective for fast arbitrary precision integer divisions.

关键词： Instruction sets Arithmetic Registers approximation algorithms Costs Computer architecture Time measurement AVX-512 divide-and-conquer integer division multi-precision arithmetic SIMD

来源：评论

学校读者我要写书评

暂无评论

Joint Active and Passive Beamforming Design for Reconfigurable Intelligent Surface Enabled Integrated Sensing and Communication

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2023年第4期71卷 2457-2474页

作者： Xing, Zhe Wang, Rui Yuan, Xiaojun Tongji Univ Coll Elect & Informat Engn Shanghai 201804 Peoples R China Tongji Univ Shanghai Inst Intelligent Sci & Technol Shanghai 201804 Peoples R China Univ Elect Sci & Technol China Natl Key Lab Sci & Technol Commun Chengdu 610000 Peoples R China

To exploit the potential of the reconfigurable intelligent surface (RIS) in supporting integrated sensing and communication (ISAC), this paper proposes a novel joint active and passive beamforming design for RIS-enabled ISAC system in consideration of the target size. First, the detection probability for target sensing is derived in closed-form based on the illumination power on an approximated scattering surface area of the target, and a new concept of ultimate detection resolution (UDR) is defined for the first time to measure the target detection capability. Then, an optimization problem is formulated to maximize the signal-to-noise ratio (SNR) at the user-equipment (UE) under a minimum detection probability constraint. To solve this non-convex problem, a novel alternative optimization approach is developed. In this approach, the solutions of the communication and sensing beamformers are obtained by our proposed bisection-search based method. The optimal receive combining vector is derived from an equivalent Rayleigh-quotient problem. To optimize the RIS phase shifts, the Charnes-Cooper transformation is conducted to cope with the fractional objective, and a novel convexification process is proposed to convexify the detection probability constraint with matrix operations and a real-valued first-order Taylor expansion. After the convexification, a successive convex approximation (SCA) based algorithm is designed to yield a suboptimal phase-shift solution. Finally, the overall optimization algorithm is built, followed by detailed analyses on its computational complexity, convergence behavior and problem feasibility condition. Extensive simulations are carried out to testify the analytical properties of the proposed beamforming design, and to reveal two important trade-offs, namely, communication vs. sensing trade-off and UDR vs. sensing-duration trade-off. In comparison with several existing benchmarks, our proposed approach is validated to be superior when detecti

关键词： Sensors Array signal processing Optimization Signal to noise ratio approximation algorithms Radar cross-sections Object detection Reconfigurable intelligent surface (RIS) integrated sensing and communication (ISAC) beamforming optimization detection probability ultimate detection resolution (UDR)

来源：评论

学校读者我要写书评

暂无评论

Online Submodular Coordination With Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination

引用

IEEE ROBOTICS AND AUTOMATION LETTERS 2023年第4期8卷 2261-2268页

作者： Xu, Zirui Zhou, Hongyu Tzoumas, Vasileios Univ Michigan Dept Aerosp Engn Ann Arbor MI 48109 USA

We enable efficient and effective coordination in unpredictable environments, i.e., in environments whose future evolution is unknown a priori and even adversarial. We are motivated by the future of autonomy that involves multiple robots coordinating in dynamic, unstructured, and adversarial environments to complete complex tasks such as target tracking, environmental mapping, and area monitoring. Such tasks are often modeled as submodular maximization coordination problems. We introduce the first submodular coordination algorithm with bounded tracking regret, i.e., with bounded suboptimality with respect to optimal time-varying actions that know the future a priori. The bound gracefully degrades with the environments' capacity to change adversarially. It also quantifies how often the robots must re-select actions to "learn " to coordinate as if they knew the future a priori. The algorithm requires the robots to select actions sequentially based on the actions selected by the previous robots in the sequence. Particularly, the algorithm generalizes the seminal Sequential Greedy algorithm by Fisher et al. to unpredictable environments, leveraging submodularity and algorithms for the problem of tracking the best expert. We validate our algorithm in simulated scenarios of target tracking.

关键词： Robots Robot kinematics Target tracking Task analysis Optimization Linear programming approximation algorithms Multi-robot systems unknown environments online learning regret optimization submodular optimization

来源：评论

学校读者我要写书评

暂无评论

Vehicular Applications of Koopman Operator Theory-A Survey

引用

IEEE ACCESS 2023年 11卷 25917-25931页

作者： Manzoor, Waqas A. Rawashdeh, Samir Mohammadi, Alireza Ford Motor Co Dept Syst Engn & Validat Dearborn MI 48124 USA Univ Michigan Dept Elect & Comp Engn Dearborn MI 48128 USA

Koopman operator theory has proven to be a promising approach to nonlinear system identification and global linearization. For nearly a century, there had been no efficient means of calculating the Koopman operator for applied engineering purposes. The introduction of a recent computationally efficient method in the context of fluid dynamics, which is based on the system dynamics decomposition to a set of normal modes in descending order, has overcome this long-lasting computational obstacle. The purely data-driven nature of Koopman operators holds the promise of capturing unknown and complex dynamics for reduced-order model generation and system identification, through which the rich machinery of linear control techniques can be utilized. Given the ongoing development of this research area and the many existing open problems in the fields of smart mobility and vehicle engineering, a survey of techniques and open challenges of applying Koopman operator theory to this vibrant area is warranted. This review focuses on the various solutions of the Koopman operator which have emerged in recent years, particularly those focusing on mobility applications, ranging from characterization and component-level control operations to vehicle performance and fleet management. Moreover, this comprehensive review of over 100 research papers highlights the breadth of ways Koopman operator theory has been applied to various vehicular applications with a detailed categorization of the applied Koopman operator-based algorithm type. Furthermore, this review paper discusses theoretical aspects of Koopman operator theory that have been largely neglected by the smart mobility and vehicle engineering community and yet have large potential for contributing to solving open problems in these areas.

关键词： Vehicle dynamics Heuristic algorithms Nonlinear dynamical systems Taxonomy approximation algorithms Trajectory Intelligent robots nonlinear systems system identification vehicles

来源：评论

学校读者我要写书评

暂无评论

Divergence Estimation in Message Passing algorithms

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第11期69卷 7461-7477页

作者： Skuratovs, Nikolajs Davies, Mike E. Univ Edinburgh Sch Engn Edinburgh EH16 5GT Scotland

Many modern imaging applications can be modeled as compressed sensing linear inverse problems. When the measurement operator involved in the inverse problem is sufficiently random, denoising Scalable Message Passing (SMP) algorithms have a potential to demonstrate high efficiency in recovering compressed data. One of the key components enabling SMP to achieve fast convergence, stability and predictable dynamics is the Onsager correction that must be updated at each iteration of the algorithm. This correction involves the denoiser's divergence that is traditionally estimated via the Black-Box Monte Carlo (BB-MC) method. While the BB-MC method demonstrates satisfying accuracy of estimation, it requires heuristic tuning and executing the denoiser additional times at each iteration and might lead to a substantial increase in computational cost of the SMP algorithms. In this work we develop two Large System Limit models of the Onsager correction for denoisers operating within SMP algorithms and use these models to propose practical black-box methods for divergence estimation that require no additional executions of the denoiser and demonstrate similar correction compared to the BB-MC method.

关键词： Switched mode power supplies Heuristic algorithms Estimation Noise reduction approximation algorithms Message passing Prediction algorithms divergence estimation denoiser Onsager correction expectation propagation

来源：评论

学校读者我要写书评

暂无评论

Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 786-801页

作者： Guo, Luyao Shi, Xinli Cao, Jinde Wang, Zihao Southeast Univ Sch Math Nanjing 210096 Peoples R China Southeast Univ Frontiers Sci Ctr Mobile Informat Commun & Secur Nanjing 210096 Peoples R China Southeast Univ Sch Cyber Sci & Engn Nanjing 210096 Peoples R China Southeast Univ Frontiers Sci Ctr Mobile Informat Commun & Secur Sch Math Nanjing 210096 Peoples R China Southeast Univ Purple Mt Labs Nanjing 211111 Peoples R China Yonsei Univ Yonsei Frontier Lab Seoul 03722 South Korea

This paper proposes a novel CTA (Combine-ThenAdapt)-based decentralized algorithm for solving convex composite optimization problems over undirected and connected networks. The local loss function in these problems contains both smooth and nonsmooth terms. The proposed algorithm uses uncoordinated network-independent constant stepsizes and only needs to approximately solve a sequence of proximal mappings, which is advantageous for solving decentralized composite optimization problems where the proximalmappings of the nonsmooth loss functionsmay not have analytical solutions. For the general convex case, we prove an O(1/k) convergence rate of the proposed algorithm, which can be improved to o(1/k) if the proximal mappings are solved exactly. Furthermore, with metric subregularity, we establish a linear convergence rate for the proposed algorithm. Numerical experiments demonstrate the efficiency of the algorithm.

关键词： Convergence Signal processing algorithms Optimization approximation algorithms Gradient methods Network topology Measurement Decentralized optimization inexact proximal gradient method linear convergence network independent

来源：评论

学校读者我要写书评

暂无评论

Multi-Tenant In-Memory Key-Value Cache Partitioning Using Efficient Random Sampling-Based LRU Model

引用

IEEE TRANSACTIONS ON CLOUD COMPUTING 2023年第4期11卷 3601-3618页

作者： Wang, Yuchen Yang, Junyao Wang, Zhenlin Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA

In-memory key-value caches are widely used as a performance-critical layer in web applications, disk-based storage, and distributed systems. The Least Recently Used (LRU) replacement policy has become the de facto standard in those systems since it exploits workload locality well. However, the LRU implementation can be costly due to the rigid data structure in maintaining object priority, as well as the locks for object order updating. Redis as one of the most effective and prevalent deployed commercial systems adopts an approximated LRU policy, where the least recently used item from a small, randomly sampled set of items is chosen to evict. This random sampling-based policy is lightweight and shows its flexibility. We observe that there can exist a significant miss ratio gap between exact LRU and random sampling-based LRU under different sampling size $K$Ks. Therefore existing LRU miss ratio curve (MRC) construction techniques cannot be directly applied without loss of accuracy. In this article, we introduce a new probabilistic stack algorithm named KRR to accurately model random sampling based-LRU, and extend it to handle both fixed and variable objects in key-value caches. We present an efficient stack update algorithm that reduces the expected running time of KRR significantly. To improve the performance of the in-memory multi-tenant key-value cache that utilizes random sampling-based replacement, we propose kRedis, a reference locality- and latency-aware memory partitioning scheme. kRedis guides the memory allocation among the tenants and dynamically customizes $K$K to better exploit the locality of each individual tenant. Evaluation results over diverse workloads show that our model generates accurate miss ratio curves for both fixed and variable object size workloads, and enables practical, low-overhead online MRC prediction. Equipped with KRR, kRedis delivers up to a 50.2% average access latency reduction, and up to a 262.8% throughput improvement compared

关键词： Partitioning algorithms Resource management Memory management Cloud computing approximation algorithms Throughput Heuristic algorithms Application servers multi-tenant LRU modeling methodologies memory allocation

来源：评论

学校读者我要写书评

暂无评论

Improved Bounds for Metric Capacitated Covering Problems

引用

ALGORITHMICA 2023年第7期85卷 1825-1849页

作者： Bandyapadhyay, Sayan Univ Bergen Dept Informat Bergen Norway

In the Metric Capacitated Covering (MCC) problem, given a set of balls B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {B}}$$\end{document} in a metric space P with metric d and a capacity parameter U, the goal is to find a minimum sized subset B & PRIME;& SUBE;B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {B}}}'\subseteq {\mathcal {B}}$$\end{document} and an assignment of the points in P to the balls in B & PRIME;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {B}}'$$\end{document} such that each point is assigned to a ball that contains it and each ball is assigned with at most U points. MCC achieves an O(log|P|)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log |P|)$$\end{document}-approximation using a greedy algorithm. On the other hand, it is hard to approximate within a factor of o(log|P|)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$o(\log |P|)$$\end{document} even with beta < 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mat

关键词： Capacitated covering approximation algorithms Bicriteria approximation LP rounding

来源：评论

学校读者我要写书评

暂无评论

A Distributed Integrated Feature Selection Scheme for Column Subset Selection

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第3期35卷 2193-2205页

作者： Xiao, Zheng Wei, PengCheng Chronopoulos, Anthony Theodore Elster, Anne C. C. Hunan Univ Coll Informat Sci & Engn Changsha 410082 Hunan Peoples R China Univ Texas San Antonio Dept Comp Sci San Antonio TX 78249 USA Univ Patras Dept Comp Engn & Informat Rion 26500 Greece Norwegian Univ Sci & Technol Dept Comp Sci N-7491 Trondheim Norway

The emergence of computer applications often encounter huge volumes of data which need to be stored and processed in a distributed way. Most of the existing distributed feature selection schemes neglect how good the subsets are that are mapped to the computational nodes, which causes a waste of time and hardware resources. In this paper, we propose a distributed integrated feature selection scheme (DIFS) with Subset Quality Evaluation (SQE). SQE studies the relevance between the quality of a subset and the number of selected features from this subset, which helps shorten the feature selection time efficiently. Feature selection algorithms used in our method and the evaluation metric used in SQE are integrable. Then, we have given the implementation of our scheme for the Column Subset Selection (CSS) problem. More specifically, we integrate a CSS algorithm in DIFS and information entropy as the SQE metric. Theoretically, we prove that the speedup of DIFS can reach m3 compared to the centralized algorithm in ideal situations where $m$m is the number of computational nodes, and give a well bounded approximation guarantee of the solution generated by scheme for CSS problem. Extensive experiments on eight data sets are used to verify the performance of scheme. Experiments results demonstrate the effectiveness of SQE and the impressive speedup DIFS can achieve. Although there is a slight increase of the reconstruction error value in some situations. Additional experiments of classification tasks reveal that the performance of DIFS is better than existing state-of-the-art distributed algorithms.

关键词： Feature extraction Distributed databases Measurement approximation algorithms Optimized production technology Information filters Filtering algorithms Feature selection distributed integrated scheme subset quality evaluation column subset selection

来源：评论

学校读者我要写书评

暂无评论

Non-Linear Reconstruction for ERT Inverse Problem Based on Homotopy Algorithm

引用

IEEE SENSORS JOURNAL 2023年第10期23卷 10404-10412页

作者： Zhang, Wei Tan, Chao Dong, Feng Hebei Univ Technol Sch Artificial Intelligent & Data Sci Tianjin 300130 Peoples R China Tianjin Univ Sch Elect & Informat Engn Tianjin Key Lab Proc Measurement & Control Tianjin 300072 Peoples R China

Due to the non-linear and non-convex properties, classical electrical resistance tomography (ERT) image reconstruction algorithms are less effective and less accurate. In this article, a non-linear and non-convex image reconstruction algorithm based on the homotopy method was proposed. The proposed algorithm converted the ERT inverse problem to a multi-object non-convex optimization which promoted the reconstruction accuracy and avoid the local optimal. Experimental validations were conducted. The optimization process is studied which demonstrates its effectiveness. Moreover, the proposed algorithm is compared with six other representative algorithms (linear/non-linear and convex/non-convex) at the condition of different distributions and the number of objects. The image quality parameters of the proposed algorithms are studied which show that the homotopy algorithm can provide image reconstruction result with higher quality and better stability than the other conventional algorithms.

关键词： Matching pursuit algorithms Image reconstruction Inverse problems Optimization Mathematical models approximation algorithms Convergence Compressed sensing electrical resistance tomography (ERT) homotopy algorithm inverse problem non-convex optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：