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

IEEE International Parallel & Distributed Processing Symposium

作者： A. Benoit H. Larchevêque P. Renaud-Goud LIP Ecole Normale Supérieure de Lyon France LABRI University of Bordeaux I France

ISBN: (纸本)9781467309752

In this paper, we study the problem of replica placement in tree networks subject to server capacity and distance constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The Single policy enforces that all requests of a client are served by a single server in the tree, while in the Multiple policy, the requests of a given client can be processed by multiple servers, thus distributing the processing of requests over the platform. For the Single policy, we prove that all instances of the problem are NP-hard, and we propose approximation algorithms. The problem with the Multiple policy was known to be NP-hard with distance constraints, but we provide a polynomial time optimal algorithm to solve the problem in the particular case of binary trees when no request exceeds the server capacity.

关键词： Replica placement distance constraints optimal algorithms approximation algorithms tree networks binary tree single vs multiple policy

来源：评论

学校读者我要写书评

暂无评论

optimal Functional Unit Assignment and Voltage Selection for Pipelined MPSoC with Guaranteed Probability on Time Performance 2017

Optimal Functional Unit Assignment and Voltage Selection for...

引用

18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)

作者： Jiang, Weiwen Sha, Edwin H. -M. Zhuge, Qingfeng Dong, Hailing Chen, Xianzhang Chongqing Univ Coll Comp Sci Chongqing 400044 Peoples R China

ISBN: (纸本)9781450350303

Pipelined heterogeneous multiprocessor system-on-chip (MPSoC) can provide high throughput for streaming applications. In the design of such systems, time performance and system cost are the most concerning issues. By analyzing runtime behaviors of benchmarks in real-world platforms, we find that execution times of tasks are not fixed but spread with probabilities. In terms of this feature, we model execution times of tasks as random variables. In this paper, we study how to design high-performance and low-cost MPSoC systems to execute a set of such tasks with data dependencies in a pipelined fashion. Our objective is to obtain the optimal functional unit assignment and voltage selection for the pipelined MPSoC systems, such that the system cost is minimized while timing constraints can be met with a given guaranteed probability. For each required probability, our proposed algorithm can efficiently obtain the optimal solution. Experiments show that other existing algorithms cannot find feasible solutions in most cases, but ours can. Even for those solutions that other algorithms can obtain, ours can reach 30% reductions in total cost compared with others.

关键词： Functional unit assignment application-specific system energy efficiency probabilistic execution time optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

From Almost optimal algorithms to Logics for Complexity Classes via Listings and a Halting Problem

引用

JOURNAL OF THE ACM 2012年第4期59卷 17-17页

作者： Chen, Yijia Flum, Joerg Shanghai Jiao Tong Univ Shanghai 200240 Peoples R China Univ Freiburg D-79104 Freiburg Germany

Let C denote one of the complexity classes "polynomial time," "logspace," or "nondeterministic logspace." We introduce a logic L(C)(inv) and show generalizations and variants of the equivalence (L(C)(inv) captures C if and only if there is an almost C-optimal algorithm in C for the set TAUT of tautologies of propositional logic.) These statements are also equivalent to the existence of a listing of subsets in C of TAUT by corresponding Turing machines and equivalent to the fact that a certain parameterized halting problem is in the parameterized complexity class XCuni.

关键词： algorithms Languages Theory optimal algorithms logics for complexity classes listings parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Bridging Supervised Learning and Test-Based Co-optimization

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 1255-1293页

作者： Popovici, Elena Icosyst Corp 222 Third StSuite 0142 Cambridge MA 02142 USA

This paper takes a close look at the important commonalities and subtle differences between the well-established field of supervised learning and the much younger one of cooptimization. It explains the relationships between the problems, algorithms and views on cost and performance of the two fields, all throughout providing a two-way dictionary for the respective terminologies used to describe these concepts. The intent is to facilitate advancement of both fields through transfer and cross-pollination of ideas, techniques and results. As a proof of concept, a theoretical study is presented on the connection between existence / lack of free lunch in the two fields, showcasing a few ideas for improving computational complexity of certain supervised learning approaches.

关键词： supervised learning active learning co-optimization free lunch optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Voting in the Presence of Byzantine Faults 22

Voting in the Presence of Byzantine Faults

引用

IEEE 22nd Pacific Rim International Symposium on Dependable Computing (PRDC)

作者： Tseng, Lewis Univ Illinois Dept Comp Sci Champaign IL 61820 USA

ISBN: (纸本)9781509056521

Voting (or election) algorithms are used widely in many safety-critical systems to mask errors. Most systems only tolerate malicious (or Byzantine) voters - these systems assume the existence of a correct and centralized mechanism to collect the votes and propagate the voting output to each voter. However, in many realistic scenarios, such a centralized voting mechanism is not feasible. Thus, we study the Byzantine voting problem - no centralized mechanism exists in the system, and voters may become Byzantine faulty. We first present impossibility results in both synchronous and asynchronous systems. To circumvent the impossibility results presented in this paper, we propose two relaxed voting properties that are achievable and present optimal voting algorithms that satisfy the relaxed properties. Finally, we show that it is possible to design Byzantine voting algorithms that produce the voting output in one communication step under contention-free scenarios.

关键词： Byzantine Voting optimal algorithms Impossibility Results Distributed algorithms Consensus

来源：评论

学校读者我要写书评

暂无评论

On one-step worst-case optimal trisection in univariate bi-objective Lipschitz optimization

引用

COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION 2016年第Jun.期35卷 123-136页

作者： Zilinskas, Antanas Gimbutiene, Grazina Vilnius State Univ Inst Math & Informat LT-08663 Vilnius Lithuania

The bi-objective Lipschitz optimization with univariate objectives is considered. The concept of the tolerance of the lower Lipschitz bound over an interval is generalized to arbitrary subintervals of the search region. The one-step worst-case optimality of trisecting an interval with respect to the resulting tolerance is established. The theoretical investigation supports the previous usage of trisection in other algorithms. The trisection-based algorithm is introduced. Some numerical examples illustrating the performance of the algorithm are provided. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Bi-objective optimization optimal algorithms Lipschitz optimization Trisection

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for Global Optimization and adaptive covering

引用

JOURNAL OF GLOBAL OPTIMIZATION 2016年第3期66卷 535-572页

作者： Shishkin, Serge L. Finn, Alan M. United Technol Res Ctr 411 Silver LaneMS 129-15 E Hartford CT 06447 USA

The general class of zero-order Global Optimization problems is split into subclasses according to a proposed "Complexity measure" and the computational complexity of each subclass is rigorously estimated. Then, the laboriousness (computational demand) of general Branch-and-Bound (BnB) methods is estimated for each subclass. For conventional "Cubic" BnB based on splitting an n-dimensional cube into sub-cubes, both upper and lower laboriousness estimates are obtained. The value of the Complexity measure for a problem subclass enters linearly into all complexity and laboriousness estimates for that subclass. A new BnB method based on the lattice is presented with upper laboriousness bound that is, though conservative, smaller by a factor of than the lower bound of the conventional method. The optimality of the new method is discussed. All results are extended to the class of Adaptive Covering problems-that is, covering of a large n-dimensional set by balls of different size, where the size of each ball is defined by a locally computed criterion.

关键词： Global Optimization Branch and Bound Adaptive covering Complexity optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal MULTISTAGE ALGORITHM FOR ADJOINT COMPUTATION

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2016年第3期38卷 C232-C255页

作者： Aupy, Guillaume Herrmann, Julien Hovland, Paul Robert, Yves ENS Lyon INRIA LIP F-69364 Lyon 07 France Vanderbilt Univ 221 Kirkland Hall Nashville TN 37235 USA Argonne Natl Lab 9700 S Cass Ave Argonne IL 60439 USA Univ Tennessee Knoxville TN 37996 USA

We reexamine the work of Stumm and Walther on multistage algorithms for adjoint computation. We provide an optimal algorithm for this problem when there are two levels of checkpoints, in memory and on disk. Previously, optimal algorithms for adjoint computations were known only for a single level of checkpoints with no writing and reading costs;a well-known example is the binomial checkpointing algorithm of Griewank and Walther. Stumm and Walther extended that binomial checkpointing algorithm to the case of two levels of checkpoints, but they did not provide any optimality results. We bridge the gap by designing the first optimal algorithm in this context. We experimentally compare our optimal algorithm with that of Stumm and Walther to assess the difference in performance.

关键词： optimal algorithms checkpointing adjoint computation program reversal automatic differentiation

来源：评论

学校读者我要写书评

暂无评论

optimal Functional-Unit Assignment and Buffer Placement for Probabilistic Pipelines 16

Optimal Functional-Unit Assignment and Buffer Placement for ...

引用

International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS)

作者： Jiang, Weiwen Sha, Edwin H. -M. Zhuge, Qingfeng Chen, Xianzhang Chongqing Univ Coll Comp Sci Chongqing Peoples R China

ISBN: (纸本)9781450344838

Applications, such as streaming applications, modeled by task graphs can be efficiently executed in a pipelined fashion. In synthesizing application-specific heterogeneous pipelined systems, where to place buffers (called buffer placement) and what type of functional units to execute each task (called functional assignment) are two critical problems. In reality, the execution time of each task may not be fixed, which makes the above two problems much more challenging. In this paper, we model the execution time of each task on different types of functional units as a random variable. Our objective is to obtain the optimal functional assignment and buffer placement, such that the resultant pipeline can satisfy the timing requirement with the minimum cost under the guaranteed confidence probability. This paper presents efficient algorithms to achieve the objective. Experiments show that other techniques cannot find any feasible solutions in many cases while ours can. Even for the cases where they can find feasible solutions, our algorithms achieve the minimum cost which gives a significant reduction on the total cost, compared with existing techniques.

关键词： High-level synthesis application-specific system optimal algorithms probabilistic scenario

来源：评论

学校读者我要写书评

暂无评论

Scheduling for electricity cost in a smart grid

引用

JOURNAL OF SCHEDULING 2016年第6期19卷 687-699页

作者： Burcea, Mihai Hon, Wing-Kai Liu, Hsiang-Hsuan Wong, Prudence W. H. Yau, David K. Y. Univ Liverpool Dept Comp Sci Liverpool Merseyside England Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan Singapore Univ Technol & Design Informat Syst Technol & Design Singapore Singapore

We study an offline scheduling problem arising in demand response management in a smart grid. Consumers send in power requests with a flexible set of timeslots during which their requests can be served. For example, a consumer may request the dishwasher to operate for 1 h during the periods 8am to 11am or 2pm to 4pm. The grid controller, upon receiving power requests, schedules each request within the specified duration. The electricity cost is measured by a convex function of the load in each timeslot. The objective of the problem is to schedule all requests with the minimum total electricity cost. As a first attempt, we consider a special case in which the power requirement and the duration a for which a request needs service are both unit-size. For this problem, we present a polynomial time offline algorithm that gives an optimal solution and shows that the time complexity can be further improved if the given set of timeslots forms a contiguous interval.

关键词： Optimization Convex power cost optimal algorithms Time complexity Feasible graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：