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

Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

作者： Ruchir Puri Andrew Bjorksten Thomas E. Rosser IBM Thomas J. Watson Research Center Yorktown Heights NY IBM Corporation 11400 Burnet Road Austin TX

ISBN: (纸本)9780818675973

Domino logic is one of the most popular dynamic circuit configurations for implementing high-performance logic designs. Since domino logic is inherently noninverting, it presents a fundamental constraint of implementing logic functions without any intermediate inversions. Removal of intermediate inverters requires logic duplication for generating both the negative and positive signal phases, which results in significant area overhead. This area overhead can be substantially reduced by selecting an optimal output phase assignment, which results in a minimum logic duplication penalty for obtaining inverter-free logic. In this paper, we present this previously unaddressed problem of output phase assignment for minimum area duplication in dynamic logic synthesis. We give both optimal and heuristic algorithms for minimizing logic duplication.

关键词： logic optimization logic functions domino logic heuristic algorithms logic duplication area overhead optimal algorithms logic design dynamic logic synthesis minimum logic duplication penalty output phase assignment inverters

来源：评论

学校读者我要写书评

暂无评论

Sorting N items using a p-sorter in optimal time

Sorting N items using a p-sorter in optimal time

引用

8th IEEE Symposium on Parallel and Distributed Processing

作者： Olariu, S Zheng, SQ Old Dominion Univ Norfolk United States

ISBN: (纸本)0818676833

A sorting device capable of sorting p items in constant time is cabled a p-sorter. It is known that the task of sorting N items using a p-sorter requires at least Omega (N log N/p log p) applications of the p-sorter. This bound is tight: there exist algorithms that use O (N log N/p log p) calls to the p-sorter to sort N items. However, there is no known implementable algorithm that can sort N items in O (N log N/p log p) time using a p-sorter. The main contribution of this paper is to propose a simple VLSI architecture and to show that in our architecture N items can be sorted in O (N log N/p log p) calls to the p-sorter, while enforcing conflict-free memory accesses. An important feature of our design is that the total additional VLSI area for hardware, other than the memory for data and the p-sorter, is kept to a minimum.

关键词： special-purpose architectures VLSI sorting p-sorter optimal algorithms parallel algorithms reconfigurable mesh

来源：评论

学校读者我要写书评

暂无评论

Generalized Kraft's inequality and discrete k-modal search

引用

SIAM JOURNAL ON COMPUTING 1996年第2期25卷 420-447页

作者： Mathur, A Reingold, EM Univ of Illinois at Urbana-Champaign Urbana IL USA

A function f : R --> R is k-modal if its kth derivative has a unique zero. We study the problem of finding the smallest possible interval containing the unique zero of the kth derivative of such a function, assuming that the function is evaluated only at integer points. We present optimal algorithms for the case when k is even and for k = 3 and near-optimal algorithms when k greater than or equal to 5 and odd. A novel generalization of Kraft's inequality is used to prove lower bounds on the number of function evaluations required. We show how our algorithms lead to an efficient divide-and-conquer algorithm to determine all turning points or zeros of a k-modal function. Unbounded k-modal search is introduced and some problems in extending previous approaches for unbounded searching to the k-modal case are discussed.

关键词： k-modal search Kraft's inequality k-modal functions optimal algorithms binary search unimodal search bimodal search unbounded search Fibonacci numbers

来源：评论

学校读者我要写书评

暂无评论

AN optimal PATH COVER ALGORITHM FOR COGRAPHS

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 1995年第8期30卷 75-83页

作者： LIN, R OLARIU, S PRUESSE, G OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 UNIV VERMONT DEPT COMP SCI & ELECT ENGNBURLINGTONVT 05405

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. In this paper, we present an optimal algorithm for determining a minimum pat... 详细信息

关键词： COGRAPHS SCHEDULING PATH COVER HAMILTONICITY VLSI GREEDY algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

WORST-CASE optimalITY OF SMOOTHING algorithms FOR PARAMETRIC SYSTEM-IDENTIFICATION

引用

AUTOMATICA 1995年第5期31卷 759-763页

作者： TEMPO, R CENS-CNR Politecnico di Torino 10129 Torino Corso Duca degli Abruzzi 24 Italy

We study parametric identification of uncertain systems in a deterministic setting. We assume that the problem data and the linearly parameterized system model are given, In the presence of a priori information and norm-bounded noise, we design optimal worst-case algorithms. In particular, we study the interplay between identification tools and nonstandard techniques used in approximation theory. The obtained estimators, called smoothing algorithms, as well as the identification errors are computed by means of the singular-value decomposition of the system model. Finally, the proposed algorithms are tested on real data referring to the tuning of A/D converters.

关键词： SYSTEM PARAMETRIC IDENTIFICATION WORST-CASE optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

CODE ASSIGNMENT FOR HIDDEN TERMINAL INTERFERENCE AVOIDANCE IN MULTIHOP PACKET RADIO NETWORKS

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 1995年第4期3卷 441-449页

作者： BERTOSSI, AA BONUCCELLI, MA UNIV PISA DIPARTIMENTO INFORMAT I-56100 PISA ITALY

Hidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station, This interference lowers the system throughput and increases the average packet delay, Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol, However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes, In this paper, we investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference, Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. In this paper, we seek for assignments that minimize the number of codes used, We show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, we present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms, The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented.

关键词： Code Division Multiple Access Channel Capacity Network Topology Packet Radio Networks Radiofrequency Interference Delays Minimisation Computational Complexity Interference Suppression Hidden Terminal Interference Avoidance Multihop Packet Radio Networks Code Assignment System Throughput Average Packet Delay Code Division Multiple Access Orthogonal Codes Channel Capacity NP Complete Problem Network Topologies optimal algorithms Distributed Heuristic algorithms Suboptimal Centralized algorithms Network Topology Access Protocols Multiaccess Communication Throughput Delay Interference Elimination Channel Capacity Computer Networks Heuristic algorithms Computational Modeling

来源：评论

学校读者我要写书评

暂无评论

LINEAR-TIME OPTIMIZATION algorithms FOR P-4-SPARSE GRAPHS

引用

DISCRETE APPLIED MATHEMATICS 1995年第2期61卷 155-175页

作者： JAMISON, B OLARIU, S OLD DOMINION UNIV DEPT COMP SCINORFOLKVA 23529 MARYMOUNT UNIV DEPT COMP SCIARLINGTONVA 22347

Quite often, real-life applications suggest the study of graphs that feature some local density properties. In particular, graphs that are unlikely to have more than a few chordless paths of length three appear in a number of contexts. A graph G is P-4-sparse if no set of five vertices in G induces more than one chordless path of length three. P-4-sparse graphs generalize both the class of cographs and the class of P-4-reducible graphs. It has been shown that P-4-sparse graphs can be recognized in time linear in the size of the graph. The main contribution of this paper is to show that once the data structures returned by the recognition algorithm are in place, a number of NP-hard problems on general graphs can be solved in linear time for P-4-sparse graphs. Specifically with an n-vertex P-4-sparse graph as input the problems of finding a maximum size clique, maximum size stable set, a minimum coloring, a minimum covering by clique, and the size of the minimum fill-in can be solved in O(n) time, independent of the number of edges in the graph.

关键词： OPTIMIZATION NP-HARD PROBLEMS RESOURCE ALLOCATION LOCAL DENSITY LINEAR algorithms optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

An improvement on parallel computation of a maximal matching

引用

INFORMATION PROCESSING LETTERS 1995年第6期56卷 343-348页

作者： Han, YJ Electronic Data Systems Inc. 37350 Ecorse Rd. Romulus MI 48174 USA

We present an improved optimal parallel algorithm with time complexity O(log(3) n) for computing a maximal matching in a graph. The improvement is made on the recent result of Kelsen which requires O(log(4) n) time fo... 详细信息

关键词： graph algorithms maximal matching optimal algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal Worst-Case Tuning of Smoothing algorithms

引用

IFAC Proceedings Volumes 1994年第8期27卷 527-532页

作者： Roberto Tempo CENS-CNR Politecnico di Torino Corso Duca degli Abruzzi 24 10129 Torino Italy

In this paper, we study robust parametric identification of uncertain systems in a deterministic setting. We assume that the problem data y and the linearly parametrized system model M(θ) are given. In the presence of apriori information and norm-bounded output noise, we design robust and optimal worst-case algorithms. In particular, we study the interplay between classical identification tools and nonstandard techniques frequently used in approximation theory. Indeed, we combine the robustness of smoothing algorithms (often called constrained least squares) with the optimality of interpolatory algorithms. We demonstrate that the optimal tuning of these algorithms can be easily performed via a singular value decomposition of the matrix M .

关键词： System Parameter Identification Worst-Case Tuning optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

optimal POLYGON PLACEMENT BY TRANSLATION

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1994年第3-4期52卷 139-148页

作者： PAL, SP DASGUPTA, B MADHAVAN, CEV UNIV MINNESOTA DEPT COMP SCIMINNEAPOLISMN 55455 INDIAN INST SCI DEPT COMP SCI & AUTOMATBANGALORE 560012KARNATAKAINDIA

Let M be an m-sided simple polygon and N be an n-sided polygon with holes. In this paper we consider the problem of computing the feasible region, i.e., the set of all placements by translation of M so that M lies inside N without intersecting any hole. First we propose an O (mn(2)) time algorithm for computing the feasible region for the case when M is a monotone polygon. Then we consider the general case when M is a simple polygon and propose an O(m(2)n(2)) time algorithm for computing the feasible region. Both algorithms are optimal upto a constant factor.

关键词： POLYGON PLACEMENT FEASIBLE REGION POLYGON CONTAINMENT optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：