16538539
Optimal jumper insertion for antenna avoidance under ratio upper-bound
Antenna effect may damage gate oxides during plasma-based fabrication process. The antenna ratio of total exposed antenna area to total gate oxide area is directly related to the amount of damage. Jumper insertion is a common technique applied at routing and post-layout stages to avoid and to fix the problems caused by the antenna effect. This paper presents an optimal algorithm for jumper insertion under the ratio upper-bound. It handles Steiner trees with obstacles. The algorithm us based on dynamic programming while works on free trees. The time complexity is O(alpha|V|2 ) and the space complexity is O(|V|2), where |V| is the number of nodes in the routing tree and a is a factor depending on how to find a non-blocked position on a wire for a jumper
3185763
Address generation for nanowire decoders
Nanoscale crossbars built from nanowires can form high density memories and programmable logic devices. To integrate such nanoscale devices with CMOS circuits, nanowire decoders were invented. Due to the stochastic nature of the nanoscale fabrication, the decoder addresses that address the nanowires selectively must be generated after fabrication. In this paper, we develop a mathematical model of the nanowire decoders for the generation of the proper addresses. Assuming a simple testing approach calledon-off measurement, we prove that the maximum number of the proper addresses can be generated in finite time. We design the algorithms to generate the required number of the proper addresses. Experimental results confirm the efficiency of our algorithms.
2271365
Minimal period retiming under process variations
With aggressive scaling down of feature sizes in VLSI fabrication, process variations have become a critical issue in designs. With process variations, timing optimization should consider the randomness introduced in delays. This paper considers how to retime a circuit under process variations. A statistical retiming problem is defined on the concept of a disutility function. Based on a new minimal period retiming algorithm, two algorithms are presented for the statistical retiming problem. Both theoretical and experimental results are given.
16977232
Incremental exploration of the combined physical and behavioral design space
Achieving design closure is one of the biggest headaches for modern VLSI designers. This problem is exacerbated by high-level design automation tools that ignore increasingly important factors such as the impact of interconnect on the area and power consumption of integrated circuits. Bringing physical information up into the logic level or even behavioral-level stages of system design is essential to solve this problem. In this paper, we present an incremental floorplanning high-level synthesis system. This system integrates high-level and physical design algorithms to concurrently improve a system's schedule, resource binding, and floor-plan, thereby allowing the incremental exploration of the combined behavioral-level and physical-level design space. Compared with previous approaches that repeatedly call loosely coupled floorplanners for physical estimation, this approach has the benefit of efficiency, stability, and better quality of results. For designs containing functional units with non-unity aspect ratios, the average CPU time improved by 369 %, the area improved by 14.24 %, and power improved by 4 %.
6804856
Processing rate optimization by sequential system floorplanning
The performance of a sequential system is usually measured by its frequency. However, with the appearance of global interconnects that require multiple clock periods to communicate the throughput is usually traded-off for higher frequency (for example, through wire pipelining or latency insensitive design). Therefore, we propose to use the processing rate, defined as the amount of processed inputs per unit time, as the performance measure. We show that the minimal ratio of the flip-flop number over the delay on any cycle is an upper bound of the processing rate. Since the processing rate of a sequential system is mainly decided by its floorplan when interconnect delays are dominant, the problem of floorplanning for processing rate optimization is formulated and solved. We optimize the processing rate bound directly in a floorplanner by applying Howard's algorithm incrementally. Experimental results confirm the effectiveness of our approach
7128221
TAPHS: thermal-aware unified physical-level and high-level synthesis
Thermal effects are becoming increasingly important during integrated circuit design. Thermal characteristics influence reliability, power consumption, cooling costs, and performance. It is necessary to consider thermal effects during all levels of the design process, from the architectural level to the physical level. However, design-time temperature prediction requires access to block placement, wire models, power profile, and a chip-package thermal model. Thermal-aware design and synthesis necessarily couple architectural-level design decisions (e.g., scheduling) with physical design (e.g., floorplanning) and modeling (e.g., wire and thermal modeling). This article proposes an efficient and accurate thermal-aware floor-planning high-level synthesis system that makes use of integrated high-level and physical-level thermal optimization techniques. Voltage islands are automatically generated via novel slack distribution and voltage partitioning algorithms in order to reduce the design's power consumption and peak temperature. A new thermal-aware floorplanning technique is proposed to balance chip thermal profile, thereby further reducing peak temperature. The proposed system was used to synthesize a number of benchmarks, yielding numerous designs that trade off peak temperature, integrated circuit area, and power consumption. The proposed techniques reduces peak temperature by 12.5degC on average. When used to minimize peak temperature with a fixed area, peak temperature reductions are common. Under a constraint on peak temperature, integrated circuit area is reduced by 9.9% on average
2694561
Identifying Approximately Common Substructures in Trees Based on a Restricted Edit Distance
In this paper we present a dynamic programming algorithm for identifying the largest approximately common substructures (LACSs) of two ordered labeled trees. We consider a substructure of a tree T to be a connected subgraph of T. Given two trees T1,T2 and an integer d, the LACS problem is to find a substructure U1 of T1 and a substructure U2 of T2 such that U1 is within distance d of U2 and where there does not exist any other substructure V1 of T1 and V2 of T2 such that V1 and V2 satisfy the distance restriction and the sum of the sizes of V1 and V2 is greater than the sum of the sizes of U1 and U2. The distance measure considered in the paper is a restricted edit distance originated from Selkow. The LACS problem is motivated by the studies of program and document comparison. The proposed algorithm solves the problem in time O(d2×|T1|×|T2|), which is as fast as the best known algorithm for calculating Selkow's distance of two trees when the distance allowed in the common substructures is a constant independent of the input trees.
15784976
A New Algorithm to Solve Synchronous Consensus for Dependent Failures
Fault tolerant algorithms are often designed under the t-out-of-n assumption, which is based on the assumption that all processes or components fail independently with equal probability. However, real systems may exhibit dependent failures. Cores and survivor sets are used to build an abstraction model for dependent process failures. Using this abstraction, we design an algorithm to solve consensus problem crash failures. Our algorithm uses the processes in all cores to broadcast messages. Each core reaches agreement separately and even simultaneously in some round with no failure in the core. In the worst-case, the decision can be made in the round that is equal to the size of the minimal core. Our algorithm guarantees that all processes eventually decide on the same value regardless the initial values. We prove the correctness of our algorithm and give the lower bound of the number of rounds to solve consensus problem.
11589863
Identifying consensus of trees through alignment
Abstract In this paper we present a dynamic programming algorithm for identifying the similar consensus (SC) (or the largest approximately common substructures) of two ordered labeled trees based on the alignment distance. We consider a substructure of a tree T to be a connected subgraph of T . Given two trees T 1 , T 2 and an integer d , the SC problem is to find a substructure U 1 of T 1 and a substructure U 2 of T 2 such that U 1 is within distance d of U 2 and where there does not exist any other substructure V 1 of T 1 and V 2 of T 2 such that V 1 and V 2 satisfy the distance constraint and the sum of the sizes of V 1 and V 2 is greater than the sum of the sizes of U 1 and U 2 . The proposed algorithm solves the SC problem in time O( d 2 ×| T 1 |×| T 2 |×( G 1 + G 2 ) 2 ), where | T i |, i =1,2, is the size of tree T i and G i is the maximum degree of T i . This is as fast as the best known algorithm for aligning two ordered labeled trees when the distance allowed in the common substructures is a constant independent of the input trees. To demonstrate the utility of our algorithm, we discuss its application to characterizing the conformation space of RNA sequences pertaining to the poliovirus, human rhinovirus and coxsackievirus, where the RNA structures are represented by ordered labeled trees.
41575427
Ranking Web News Via Homepage Visual Layout and Cross-Site Voting
Reading news is one of the most popular activities when people surf the internet. As too many news sources provide independent news information and each has its own preference, detecting unbiased important news might be very useful for users to keep up to date with what are happening in the world. In this paper we present a novel method to identify important news in web environment which consists of diversified online news sites. We observe that a piece of important news generally occupies visually significant place in some homepage of a news site and import news event will be reported by many news sites. To explore these two properties, we model the relationship between homepages, news and latent events by a tripartite graph, and present an algorithm to identify important news in this model. Based on this algorithm, we implement a system TOPSTORY to dynamically generate homepages for users to browse important news reports. Our experimental study indicates the effectiveness of proposed approach.
29234559
Quasi-abelian cayley graphs and parsons graphs
LetGbe a finite group, andSa subset ofGwith 1?SandS-1=S.IfSis a union of conjugacy classes ofG,then the Cayley graphX=Cay(G, S)onGwith respect toSis calledquasi-abelian.In this paper we prove that any connected quasi-abelian Cayley graph is hamiltonian (Theorem 2). As a consequence, we prove that Zaks' three conjectures on Parsons graphs are true, with one exception.