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

Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints

OPERATIONS RESEARCH 2022年第6期70卷 3403-3419页

作者： Shafiee, Mehrnoosh Ghaderi, Javad Columbia Univ Dept Elect Engn New York NY 10027 USA

Motivated bymodern parallel computing applications, we consider the problem of scheduling parallel-task jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel;however, the job is considered completed only when all its tasks finish their processing, which we refer to as the synchronization constraint. Furthermore, assignment of tasks to machines is subject to placement constraints, that is, each task can be processed only on a subset of machines, and processing times can also be machine dependent. Once a task is scheduled on a machine, it requires a certain amount of resource from that machine for the duration of its processing. A machine can process (pack) multiple tasks at the same time;however, the cumulative resource requirement of the tasks should not exceed the machine's capacity. Our objective is to minimize the weighted average of the jobs' completion times. The problem, subject to synchronization, packing, and placement constraints, is NP-hard, and prior theoretical results only concern much simpler models. For the case that migration of tasks among the placement-feasible machines is allowed, we propose a preemptive algorithm with an approximation ratio of (6 + epsilon). In the special case that only one machine can process each task, we design an algorithm with an improved approximation ratio of four. Finally, in the case that migrations (and preemptions) are not allowed, we design an algorithm with an approximation ratio of 24. Our algorithms use a combination of linear program relaxation and greedy packing techniques. We present extensive simulation results, using a real traffic trace, that demonstrate that our algorithms yield significant gains over the prior approaches.

关键词： scheduling algorithms approximation algorithms data-parallel computing datacenters

来源：评论

学校读者我要写书评

暂无评论

A Stream Algebra for Performance Optimization of Large Scale Computer Vision Pipelines

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2022年第2期44卷 905-923页

作者： Helala, Mohamed A. Qureshi, Faisal Z. Pu, Ken Q. Ontario Tech Univ Fac Sci Oshawa ON L1G 0C5 Canada

There is a large growth in hardware and software systems capable of producing vast amounts of image and video data. These systems are rich sources of continuous image and video streams. This motivates researchers to build scalable computer vision systems that utilize data-streaming concepts for processing of visual data streams. However, several challenges exist in building large-scale computer vision systems. For example, computer vision algorithms have different accuracy and speed profiles depending on the content, type, and speed of incoming data. Also, it is not clear how to adaptively tune these algorithms in large-scale systems. These challenges exist because we lack formal frameworks for building and optimizing large-scale visual processing. This paper presents formal methods and algorithms that aim to overcome these challenges and improve building and optimizing large-scale computer vision systems. We describe a formal algebra framework for the mathematical description of computer vision pipelines for processing image and video streams. The algebra naturally describes feedback control and provides a formal and abstract method for optimizing computer vision pipelines. We then show that a general optimizer can be used with the feedback-control mechanisms of our stream algebra to provide a common online parameter optimization method for computer vision pipelines.

关键词： Streaming media Computer vision Algebra Pipelines approximation algorithms Optimization Buildings Stream algebra online vision algorithms stream processing large scale computer vision systems parameter tuning performance optimization

来源：评论

学校读者我要写书评

暂无评论

Outlier-Robust Estimation: Hardness, Minimally Tuned algorithms, and Applications

引用

IEEE TRANSACTIONS ON ROBOTICS 2022年第1期38卷 281-301页

作者： Antonante, Pasquale Tzoumas, Vasileios Yang, Heng Carlone, Luca MIT Lab Informat & Decis Syst Cambridge MA 02139 USA Univ Michigan Dept Aerosp Engn Ann Arbor MI 48109 USA

Nonlinear estimation in robotics and vision is typically plagued with outliers due to wrong data association or incorrect detections from signal processing and machine learning methods. This article introduces two unifying formulations for outlier-robust estimation, generalized maximum consensus ($\textrm{G}$-$\textrm{MC}$) and generalized truncated least squares ($\textrm{G-TLS}$), and investigates fundamental limits, practical algorithms, and applications. Our first contribution is a proof that outlier-robust estimation is inapproximable: In the worst case, it is impossible to (even approximately) find the set of outliers, even with slower-than-polynomial-time algorithms (particularly, algorithms running in quasi-polynomial time). As a second contribution, we review and extend two general-purpose algorithms. The first, adaptive trimming ($\textrm{ADAPT}$), is combinatorial and is suitable for $\textrm{G}$-$\textrm{MC}$;the second, graduated nonconvexity ($\textrm{GNC}$), is based on homotopy methods and is suitable for $\textrm{G-TLS}$. We extend $\textrm{ADAPT}$ and $\textrm{GNC}$ to the case where the user does not have prior knowledge of the inlier-noise statistics (or the statistics may vary over time) and is unable to guess a reasonable threshold to separate inliers from outliers (as the one commonly used in RANdom SAmple Consensus $(\textrm{RANSAC})$. We propose the first minimally tuned algorithms for outlier rejection, which dynamically decide how to separate inliers from outliers. Our third contribution is an evaluation of the proposed algorithms on robot perception problems: mesh registration, image-based object detection (shape alignment), and pose graph optimization. $\textrm{ADAPT}$ and $\textrm{GNC}$ execute in real time, are deterministic, outperform $\textrm{RANSAC}$, and are robust up to 80-90% outliers. Their minimally tuned versions also compare favorably with the state of the art, even though they do not rely on a noise bound for the inliers.

关键词： Estimation Signal processing algorithms Probabilistic logic approximation algorithms Simultaneous localization and mapping Particle measurements Measurement uncertainty algorithms autonomous systems computational complexity computer vision maximum likelihood estimation resilient perception robust estimation

来源：评论

学校读者我要写书评

暂无评论

Training Deep Neural Network for Optimal Power Allocation in Islanded Microgrid Systems: A Distributed Learning-Based Approach

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2022年第5期33卷 2057-2069页

作者： Guo, Fanghong Xu, Bowen Zhang, Wen-An Wen, Changyun Zhang, Dan Yu, Li Zhejiang Univ Technol Dept Automat Hangzhou 310014 Peoples R China Nanyang Technol Univ Sch Elect & Elect Engn Singapore Singapore

Currently, numerical optimization methods are used to solve distributed optimal power allocation (OPA) problems for islanded microgrid (MG) systems. Most of them are developed based on rigorous mathematical derivation. However, the complexity of such optimization algorithms inevitably creates a gap between theoretical analysis and real-time implementation. In order to bridge such a gap, in this article we provide a new distributed learning-based framework to solve the real-time OPA problem. Specifically, inspired by the human-thinking scheme, distributed deep neural networks (DNNs) together with a dynamic average consensus algorithm are first employed to obtain an approximate OPA solution in a distributed manner. Then a distributed balance generation and demand algorithm is designed to fine-tune it to obtain the final optimal feasible solution. In addition, it is theoretically proved that the proposed DNN can well approximate one existing OPA algorithm (Guo et al. 2018), where quantitative numbers of at most how many hidden layers and neurons are provided. Several experimental case studies show that our proposed distributed learning framework can achieve similar optimal results to those obtained by using typical existing distributed numerical optimization methods while it is superior in terms of simplicity and real-time capability.

关键词： Optimization Real-time systems Heuristic algorithms approximation algorithms Training Resource management Generators Bio-inspired optimization deep neural network (DNN) distributed framework learning to optimize optimal power allocation (OPA)

来源：评论

学校读者我要写书评

暂无评论

A k-Hop Collaborate Game Model: Extended to Community Budgets and Adaptive Nonsubmodularity

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2022年第9期52卷 5567-5578页

作者： Guo, Jianxiong Wu, Weili Beijing Normal Univ Zhuhai BNU UIC Inst Artificial Intelligence & Future Net Zhuhai 519087 Guangdong Peoples R China BNU HKBU United Int Coll Guangdong Key Lab AI & Multimodal Data Proc Zhuhai 519087 Guangdong Peoples R China Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75080 USA

Revenue maximization (RM) is one of the most important problems in social networks, which attempts to find a small subset of users that make the expected revenue maximized. It has been studied in depth before. However, most of the existing literature was based on nonadaptive seeding strategies and simple information diffusion models. It considered the number of influenced users as a measurement unit to quantify the revenue. Until the emergence of the collaborate game model, it considered the activity as a basic object to compute the revenue. An activity initiated by a user can only influence those users whose distances are within k-hop from the initiator. Based on that, we adopt an adaptive seed strategy and formulate an RM under the size budget (RMSB) problem. If taking into account the product's promotion, we extend it to an RM under the community budget problem, where the influence can be distributed over the whole network uniformly. We can prove that our objective function is adaptive monotone and not adaptive submodular, but it is adaptive submodular in some special cases. We study these two problems under both the special submodular cases and general nonsubmodular cases, and propose RMSBSolver and RMCBSolver to solve them with strong theoretical guarantees, respectively. In particular, we give a data-dependent approximation ratio by adaptive primal curvature for the RMSB in general nonsubmodular cases. Finally, we evaluate our proposed algorithms by conducting experiments on real datasets, and show the effectiveness and accuracy of our solutions.

关键词： Adaptation models Games Social networking (online) Companies Adaptive systems approximation algorithms Optimization Adaptive startegy approximation alogrithm collaborate game model nonsubmodularity online social networks (OSNs) stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

An approximation Algorithm for Bounded Task Assignment Problem in Spatial Crowdsourcing

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2021年第8期20卷 2536-2549页

作者： Bhatti, Shahzad Sarwar Fan, Jiahao Wang, Kangrui Gao, Xiaofeng Wu, Fan Chen, Guihai Shanghai Jiao Tong Univ Shanghai Key Lab Scalable Comp & Syst Dept Comp Sci & Engn Shanghai 200240 Peoples R China

Spatial crowdsourcing, a human-centric compelling paradigm in performing spatial tasks, has drawn rising attention. Task assignment is of paramount importance in spatial crowdsourcing. Existing studies often use heuristics of various kinds to solve task assignment problems. These schemes usually only apply some specific cases, once the environment changes, the efficiency of the algorithms is significantly reduced. In this paper, we first introduce a taxonomy of task assignment in spatial crowdsourcing. Next, we design an approximation algorithm and get an efficient solution for the important problem, namely, Bounded and Heterogeneous Task Assignment (BHTA), such that the sum of the rewards of workers is maximized subject to multiple constraints. We prove that the BHTA problem is NP-hard. Subsequently, we propose a constant-ratio approximation algorithm based on partition and shifting method to achieve the assignment solution. To meet with the workers' dynamism, we further devise a greedy algorithm and provide theoretical guarantee. Experiments on synthetic and real datasets demonstrate the efficiency of our strategy over previous methods. So far as we know, this paper is the first attempt to give a constant-ratio approximation for such task assignment problems in spatial crowdsourcing.

关键词： Task analysis Crowdsourcing Dynamic scheduling Processor scheduling approximation algorithms Heuristic algorithms Spatial crowdsourcing task assignment matching and scheduling constant-ratio approximation multi-user dynamism

来源：评论

学校读者我要写书评

暂无评论

Tight approximation for Unconstrained XOS Maximization

引用

MATHEMATICS OF OPERATIONS RESEARCH 2021年第4期46卷 1599-1610页

作者： Filmus, Yuval Kawase, Yasushi Kobayashi, Yusuke Yamaguchi, Yutaro Technion Israel Inst Technol Henry & Marilyn Taub Fac Comp Sci IL-3200003 Haifa Israel Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1138656 Japan Kyoto Univ Res Inst Math Sci Kyoto 6068502 Japan Kyushu Univ Grad Sch Fukuoka 8190395 Japan Kyushu Univ Fac Informat Sci & Elect Engn Fukuoka 8190395 Japan

A set function is called XOS if it can be represented by the maximum of additive functions. When such a representation is fixed, the number of additive functions required to define the XOS function is called the width. In this paper, we study the problem of maximizing XOS functions in the value oracle model. The problem is trivial for the XOS functions of width 1 because they are just additive, but it is already nontrivial even when the width is restricted to 2. We show two types of tight bounds on the polynomial-time approximability for this problem. First, in general, the approximation bound is between O(n) and Omega(n/logn), and exactly theta(n/logn) if randomization is allowed, where n is the ground set size. Second, when the width of the input XOS functions is bounded by a constant k >= 2, the approximation bound is between k - 1 and k - 1 - epsilon for any epsilon > 0. In particular, we give a linear-time algorithm to find an exact maximizer of a given XOS function of width 2, whereas we show that any exact algorithm requires an exponential number of value oracle calls even when the width is restricted to 3.

关键词： XOS functions value oracles approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Projection-Based QLP Algorithm for Efficiently Computing Low-Rank approximation of Matrices

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 2218-2232页

作者： Kaloorazi, Maboud F. Chen, Jie Northwestern Polytech Univ Sch Marine Sci & Technol Xian Peoples R China Xian Shiyou Univ Sch Elect Engn Xian 710000 Peoples R China

Matrices with low numerical rank are omnipresent in many signal processing and data analysis applications. The pivoted QLP (p-QLP) algorithm constructs a highly accurate approximation to an input low-rank matrix. However, it is computationally prohibitive for large matrices. In this paper, we introduce a new algorithm termed Projection-based Partial QLP (PbP-QLP) that efficiently approximates the p-QLP with high accuracy. Fundamental in our work is the exploitation of randomization and in contrast to the p-QLP, PbP-QLP does not use the pivoting strategy. As such, PbP-QLP can harness modern computer architectures, even better than competing randomized algorithms. The efficiency and effectiveness of our proposed PbP-QLP algorithm are investigated through various classes of synthetic and real-world data matrices.

关键词： Matrix decomposition approximation algorithms Signal processing algorithms Sparse matrices Singular value decomposition Signal processing Oceanography Low-rank approximation rank-revealing matrix factorization the pivoted QLP the singular value decomposition randomized numerical linear algebra

来源：评论

学校读者我要写书评

暂无评论

Reducing the Service Function Chain Backup Cost Over the Edge and Cloud by a Self-Adapting Scheme

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2022年第8期21卷 2994-3008页

作者： Shang, Xiaojun Huang, Yaodong Liu, Zhenhua Yang, Yuanyuan SUNY Stony Brook Stony Brook NY 11794 USA

Emerging virtual network functions (VNFs) bring new opportunities to network services on the edge within customers' premises. Network services are realized by chained up VNFs, which are called service function chains (SFCs). These services are deployed on commercial edge servers for higher flexibility and scalability. Despite such promises, it is still unclear how to provide highly available and cost-effective SFCs under edge resource limitations and time-varying VNF failures. In this paper, we propose a novel Reliability-aware Adaptive Deployment scheme named RAD to efficiently place and back up SFCs over both the edge and the cloud. Specifically, RAD first deploys SFCs to fully utilize edge resources. It then uses both static backups and dynamic ones created on the fly to guarantee the availability under the resource limitation of edge networks. RAD does not assume failure rates of VNFs but instead strives to find the sweet spot between the desired availability of SFCs and the backup cost. Theoretical performance bounds, extensive simulations, and small-scale experiments highlight that RAD provides significantly higher availability with lower backup costs compared with existing baselines.

关键词： Dynamic scheduling Cloud computing Servers Heuristic algorithms Reliability Mobile computing approximation algorithms Virtual network functions edge computing service function chain availability

来源：评论

学校读者我要写书评

暂无评论

Design of Majority Logic-Based Approximate Booth Multipliers for Error-Tolerant Applications

引用

IEEE TRANSACTIONS ON NANOTECHNOLOGY 2022年 21卷 81-89页

作者： Zhang, Tingting Jiang, Honglan Mo, Hai Liu, Weiqiang Lombardi, Fabrizio Liu, Leibo Han, Jie Univ Alberta Dept Elect & Comp Engn Edmonton AB T6G 1H9 Canada Shanghai Jiao Tong Univ Dept Micronano Elect Shanghai 200240 Peoples R China Tsinghua Univ Sch Integrated Circuits Beijing 100084 Peoples R China Nanjing Univ Aeronaut & Astronaut Coll Elect & Informat Engn Nanjing 211106 Peoples R China Northeastern Univ Dept Elect & Comp Engn Boston MA 02115 USA

Approximate computing at the nanoscale provides sufficiently accurate and often adaptive results to improve hardware efficiency for error-tolerant applications. Differently from conventional Boolean logic-based designs, many emerging nanotechnologies extensively assemble circuits using the voter-based majority logic (ML). In this letter, we investigate designs of approximate radix-4 Booth multipliers based on ML. Initially, we propose two new radix-4 Booth partial product (PP) generation methods by exploiting the characteristics of ML. Based on these methods, approximate PP generators are designed to produce single-sided or double-sided errors. The PPs are then reduced by using the features of errors to construct approximate multipliers. Specifically, complementary strategies guided by an analysis of error effects are developed to compensate for the accuracy loss and to reduce the hardware overhead during the PP reduction. The reduced PPs are then compressed by using full adders. Four approximate multipliers are proposed to offer various accuracy requirements for different applications. These designs show superior performance in power and area for emerging nanotechnologies. As case studies, image processing, a multiple-layer perceptron and a multi-task convolutional neural network are presented to show the validity and advantages of the proposed designs.

关键词： Logic gates Hardware Image coding Generators approximation algorithms Shape Nanoscale devices Booth encoding partial product generator approximate multiplier majority logic nanotechnologies

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：