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

Stochastic spatial routing for reconfigurable networks

MICROPROCESSORS AND MICROSYSTEMS 2006年第6期30卷 301-318页

作者： DeHon, Andre Huang, Randy Wawrzynek, John Univ Calif Berkeley Berkeley CA 94720 USA

FPGA placement and routing is time consuming, often serving as the major obstacle inhibiting a fast edit-compile-test loop in prototyping and development and the major obstacle preventing late-bound hardware and design mapping for reconfigurable systems. We introduce a stochastic search scheme which can achieve comparable route quality to traditional, software-based routers while being amenable to parallel, spatial implementation. We quantify the quality and performance of this route scheme using the Toronto Place-and-Route Challenge benchmarks. We sketch hardware implementations ranging from a minimal hardware-search assistance scheme which provides two orders of magnitude speedup, to FPGA-based schemes which provide greater speedup, to full hardware schemes which provide over three orders of magnitude routing acceleration. For coarse-grained devices with wide-word datapaths, the area overhead for integrating this hardware support into the network can be below 30%;for conventional FPGAs, a collection of hundreds of FPGAs can be configured to route one FPGA rapidly. With parallel path searches, the time required for the spatial solution scales sublinearly in network size for the typical, limited-bisection networks used for practical reconfigurable systems. (C) 2006 Elsevier B.V. All rights reserved.

关键词： FPGA detail routing reconfigurable computing spatial routing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

randomized wait-free consensus using an atomicity assumption

引用

9th International Conference on Principles of Distributed Systems (OPODIS 2005)

作者： Cheung, Ling Univ Nijmegen Dept Comp Sci POB 9010 NL-6500 GL Nijmegen Netherlands

ISBN: (纸本)9783540363217

We present a randomized algorithm for asynchronous wait-free consensus using multi-writer multi-reader shared registers. This algorithm is based on earlier work by Chor, Israeli and Li (CIL) and is correct under the assumption that processes can perform a random choice and a write operation in one atomic step. The expected total work for our algorithm is shown to be O(N log(log N)), compared with O(N-2) for the CIL algorithm, and O(N log N) for the best known weak adversary algorithm. We also model check instances of our algorithm using the probabilistic model checking tool PRISM.

关键词： asynchronous consensus randomized algorithms wait-free termination weak adversary probabilistic model checking.

来源：评论

学校读者我要写书评

暂无评论

Non-independent randomized rounding and coloring

Non-independent randomized rounding and coloring

引用

Workshop on Efficient algorithms (WEA)

作者： Doerr, B Univ Kiel Math Seminar D-24098 Kiel Germany

We propose an advanced randomized coloring algorithm for the problem of balanced colorings of hypergraphs (discrepancy problem). Instead of independently coloring the vertices with a random color, we try to use structural information about the hypergraph in the design of the random experiment by imposing suitable dependencies. This yields colorings having smaller discrepancy. We also obtain more information about the coloring, or, conversely, we may enforce the random coloring to have special properties. There are some algorithmic advantages as well. We apply our approach to hypergraphs of d-dimensional boxes and to finite geometries. Among others results, we gain a factor 2(d/2) decrease in the discrepancy of the boxes, and reduce the number of random bits needed to generate good colorings for the geometries down to O(root n) (from n). The latter also speeds up the corresponding derandomization by a factor of root n. (c) 2005 Elsevier B.V. All rights reserved.

关键词： randomized algorithms hypergraph coloring discrepancy randomized rounding integer linear programming

来源：评论

学校读者我要写书评

暂无评论

An energy efficient ranking protocol for radio networks

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2006年第5期E89A卷 1346-1354页

作者： Nakano, Koji Hiroshima Univ Sch Engn Higashihiroshima 7398527 Japan

A radio network (RN for short) is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations run on batteries and expends power while broadcasting/receiving a data packet. Thus, the most important measure to evaluate protocols on the radio network is the number of awake time slots, in which a station is broadcasting/receiving a data packet. We also assume that the stations are identical and have no unique ID number, and no station knows the number n of the stations. For given n keys one for each station, the ranking problem asks each station to determine the number of keys in the RN smaller than its own key. The main contribution of this paper is to present an optimal randomized ranking protocol on the k-channel RN. Our protocol solves the ranking problem, with high probability, in O(n/k + log n) time slots with every station being awake for at most O(log n) time slots. We also prove that any randomized ranking protocol is required to run in expected Omega(n/k + log n) time slots with at least one station being awake for expected Q(Iog n) time slots. Therefore, our ranking protocol is optimal.

关键词： power-aware computing adhoc networks sorting distributed algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficiently pricing European-Asian options - ultimate implementation and analysis of the AMO algorithm

引用

INFORMATION PROCESSING LETTERS 2006年第6期100卷 213-219页

作者： Shioura, Akiyoshi Tokuyama, Takeshi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

Options are popular and important financial instruments in world financial markets. One of the simplest options is European call option, which is a contract giving its holder the right, but not the obligation, to buy a stock or other financial asset at some point in the future (called the expiration date) for a specified price X (called the strike price). The payoff of an option is the amount of money its holder makes on the contract. Suppose that we have a European option on a stock, and the stock price S is more than the strike price X on the expiration date. Then, we can make some money by exercising the option to buy the stock and selling the stock immediately at the market price. Hence, the payoff of a European option is given by (S — X)~+ = max{S — X, 0}. The price of the option is usually much less than the actual price of the underlying stock. Therefore, options hedge risk more cheaply than stocks only, and provide a chance to get large profit with a small amount of money if one's speculation is good.

关键词： analysis of algorithms approximation algorithms European-Asian option option pricing randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast distributed algorithm for convergecast in ad hoc geometric radio networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2006年第4期66卷 578-585页

作者： Kesselman, A Kowalski, DR Max Planck Inst Informat Saarbrucken Germany Univ Liverpool Dept Comp Sci Liverpool L69 3BX Merseyside England

Wireless ad hoc radio networks have gained a lot of attention in recent years. We consider geometric networks, where nodes are located in a Euclidean plane. We assume that each node has a variable transmission range and can learn the distance to the closest active neighbor at any time. We also assume that nodes have a special collision detection (CD) capability so that a transmitting node can detect a collision within its transmission range. We study the basic communication problem of collecting data from all nodes called convergecast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent delay requirements on the convergecast time. We measure the latency of convergecast, that is the number of time steps needed to collect the data in any n-node network. We propose a very simple randomized distributed algorithm that has the expected running time O(log n). We also show that this bound is tight and any algorithm needs Omega(log n) time steps while performing convergecast in an arbitrary network. One of the most important problems in wireless ad hoc networks is to minimize the energy consumption, which maximizes the network lifetime. We study the trade-off between the energy and the latency of convergecast. We show that our algorithm consumes at most O(n log n) times the minimum energy. We also demonstrate that for a line topology, the minimum energy convergecast takes n time steps while any algorithm performing convergecast within O(log n) time steps requires Omega(n/log n) times the minimum energy. (c) 2006 Elsevier Inc. All rights reserved.

关键词： radio networks convergecast randomized algorithms energy/latency trade-off

来源：评论

学校读者我要写书评

暂无评论

An approximation scheme for stochastic linear programming and its application to stochastic integer programs

引用

JOURNAL OF THE ACM 2006年第6期53卷 978-1012页

作者： Shmoys, David B. Swamy, Chaitanya Cornell Univ Sch ORIE Ithaca NY 14853 USA Cornell Univ Dept Comp Sci Ithaca NY 14853 USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

Stochastic optimization problems attempt to model uncertainty in the data by assuming that the input is specified by a probability distribution. We consider the well-studied paradigm of 2-stage models with recourse: first, given only distributional information about (some of) the data one commits on initial actions, and then once the actual data is realized (according to the distribution), further (recourse) actions can be taken. We show that for a broad class of 2-stage linear models with recourse, one can, for any is an element of > 0, in time polynomial in 1/is an element of and the size of the input, compute a solution of value within a factor (1 + is an element of) of the optimum, in spite of the fact that exponentially many second-stage scenarios may occur. In conjunction with a suitable rounding scheme, this yields the first approximation algorithms for 2-stage stochastic integer optimization problems where the underlying random data is given by a "black box" and no restrictions are placed on the costs in the two stages. Our rounding approach for stochastic integer programs shows that an approximation algorithm for a deterministic analogue yields, with a small constant-factor loss, provably near-optimal solutions for the stochastic generalization. Among the range of applications, we consider are stochastic versions of the multicommodity flow, set cover, vertex cover, and facility location problems.

关键词： algorithms theory approximation algorithms convex optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fair service for mice in the presence of elephants

引用

INFORMATION PROCESSING LETTERS 2006年第3期99卷 96-101页

作者： Voorhies, Seth Lee, Hyunyoung Klappenecker, Andreas Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Univ Denver Dept Comp Sci Denver CO 80208 USA

We show how randomized caches can be used in resource-poor partial-state routers to provide a fair share of bandwidth to short-lived flows that are known as mice when long-lived flows known as elephants are present. (... 详细信息

关键词： algorithms randomized algorithms caching probabilistic queues

来源：评论

学校读者我要写书评

暂无评论

Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition

引用

SIAM JOURNAL ON COMPUTING 2006年第1期36卷 184-206页

作者： Drineas, Petros Kannan, Ravi Mahoney, Michael W. Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA Yale Univ Dept Math New Haven CT 06520 USA

In many applications, the data consist of ( or may be naturally formulated as) an m x n matrix A which may be stored on disk but which is too large to be read into random access memory ( RAM) or to practically perform superlinear polynomial time computations on it. Two algorithms are presented which, when given an m x n matrix A, compute approximations to A which are the product of three smaller matrices, C, U, and R, each of which may be computed rapidly. Let A' = CUR be the computed approximate decomposition;both algorithms have provable bounds for the error matrix A - A'. In the first algorithm, c columns of A and r rows of A are randomly chosen. If the m x c matrix C consists of those c columns of A ( after appropriate rescaling) and the r x n matrix R consists of those r rows of A ( also after appropriate rescaling), then the c x r matrix U may be calculated from C and R. For any matrix X, let parallel to X parallel to(F) and parallel to X parallel to(2) denote its Frobenius norm and its spectral norm, respectively. It is proven that parallel to A - A'parallel to(xi) <= min (D: rank( D) <= k) parallel to A - D parallel to(xi) + poly(k, 1/c)parallel to A parallel to(F) holds in expectation and with high probability for both xi = 2, F and for all k = 1,..., rank(A);thus by appropriate choice of k parallel to A - A'parallel to(2) <=epsilon parallel to A parallel to(F) also holds in expectation and with high probability. This algorithm may be implemented without storing the matrix A in RAM, provided it can make two passes over the matrix stored in external memory and use O( m + n) additional RAM ( assuming that c and r are constants, independent of the size of the input). The second algorithm is similar except that it approximates the matrix C by randomly sampling a constant number of rows of C. Thus, it has additional error but it can be implemented in three passes over the matrix using only constant additional RAM. To achieve an additional error ( beyond the best

关键词： randomized algorithms Monte Carlo methods massive data sets CUR matrix decomposition

来源：评论

学校读者我要写书评

暂无评论

Variationally universal hashing

引用

INFORMATION PROCESSING LETTERS 2006年第1期100卷 36-39页

作者： Krovetz, Ted Rogaway, Phillip Calif State Univ Sacramento Dept Comp Sci Sacramento CA 95819 USA Univ Calif Davis Dept Comp Sci Davis CA 95616 USA Chiang Mai Univ Fac Sci Dept Comp Sci Chiang Mai 50200 Thailand

The strongest well-known measure for the quality of a universal hash-function family H is its being E-strongly universal, which measures, for randomly chosen h is an element of H, one's inability to guess h(m') even if h(m) is known for some m not equal m'. We give example applications in which this measure is too weak, and we introduce a stronger measure for the quality of a hash-function family, E-variationally universal, which measures one's inability to distinguish h(m') from a random value even if h(m) is known for some m not equal m'. We explain the utility of this notion and,provide an approach for constructing efficiently computable epsilon-VU hash-function families. (c) 2006 Elsevier B.V. All rights reserved.

关键词： randomized algorithms cryptography hashing universal hashing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：