Scalable and Systolic Architecture for Computing Double Exponentiation Over GF(2 m )

Double-exponentiation is a crucial arithmetic operation for many cryptographic protocols. Several efficient double-exponentiation algorithms based on systolic architecture have been proposed. However, systolic architectures require large circuit space, thus increasing the cost of the protocol. This would be a drawback when designing circuits in systems requiring low cost and low power consumption. However, some cost savings can be attained by compromising speed, as in portable devices and many embedded systems. This study proposes a scalable and systolic AB ² and a scalable and systolic A × B, which are the core circuit modules of double-exponentiation. A scalable and systolic double-exponentiation can thus be obtained based on the proposed scalable AB ² and A × B architecture. Embedded system engineers may specify a target double-exponentiation with appropriate scaling systolic circuits. The proposed circuit has lower circuit space/cost and low time/propagation than other circuits.     

An algebraic multigrid-based algorithm for circuit clustering

Digital circuits have grown exponentially in their sizes over the past decades. To be able to automate the design of these circuits, efficient algorithms are needed. One of the challenging stages of circuit design is the physical design where the physical locations of the components of a circuit are determined. Coarsening or clustering algorithms have become popular with physical designers due to their ability to reduce circuit sizes in the intermediate design steps such that the design can be performed faster and with higher quality. In this paper, a new clustering algorithm based on the algebraic multigrid (AMG) technique is presented. In the proposed algorithm, AMG is used to assign weights to connections between cells of a circuit and find cells that are best suited to become the initial cells for clusters, seed cells. The seed cells and the weights between them and the other cells are then used to cluster the cells of a circuit. The analysis of the proposed algorithm proves linear-time complexity, O(N), where N is the number of pins in a circuit. The numerical experiments demonstrate that AMG-based clustering can achieve high quality clusters and improve circuit placement designs with low computational cost.     

超大规模集成电路布局的优化模型与算法

布局确定集成电路单元在芯片中的具体位置,在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题,是超大规模集成电路物理设计的核心问题之一,对集成电路的性能指标,如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中,布局问题通常包含数百万个集成电路单元,以及大小相异的异质性模块,和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展,综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法,并展望进一步的研究方向。     

An ILP based hierarchical global routing approach for VLSI ASIC design

The use of integrated circuits in high-performance computing, telecommunications, and consumer electronics has been growing at a very fast pace. The level of integration as measured by the number of logic gates in a chip has been steadily rising due to the rapid progress in processing and interconnect technology. The interconnect delay in VLSI circuits has become a critical determiner of circuit performance. As a result, circuit layout is starting to play a more important role in today’s chip designs. Global routing is one of the key sub-problems of circuit layout which involves finding an approximate path for the wires connecting the elements of the circuit without violating resource constraints. In this paper, several integer programming (ILP) based global routing models are fully investigated and explored. The resulting ILP problem is relaxed and solved as a linear programming (LP) problem followed by a rounding heuristic to obtain an integer solution. Experimental results obtained show that the proposed combined WVEM (wirelength, via, edge capacity) model can optimize several global routing objectives simultaneously and effectively. In addition, several hierarchical methods are combined with the proposed flat ILP based global router to reduce the CPU time by about 66% on average for edge capacity model (ECM).     

The tractability index of memristive circuits: branch‐oriented and tree‐based models

The memory‐resistor or memristor is a new electrical element characterized by a nonlinear charge‐flux relation. This device poses many challenging problems, in particular from the circuit modeling point of view. In this paper, we address the index analysis of certain differential‐algebraic models of memristive circuits; specifically, our attention is focused on so‐called branch‐oriented models, which include in particular tree‐based formulations of the circuit equations. Our approach combines results coming from differential‐algebraic equation theory, matrix analysis and theory of digraphs. This framework should be useful in future studies of dynamical aspects of memristive circuits. Copyright © 2012 John Wiley & Sons, Ltd.     

The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg (In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.B. (Eds.), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985). The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints (Miller et al., Journal of ACM 7 (1960) 326–329). The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called D_k^← and D_k^→ inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. (Operations Research 2 (1954) 393–410). The new models motivate a new classification of formulations for the ATSP.     

闭模糊拟阵模糊圈的算法研究

用闭模糊拟阵的基本序列来研究和描述它的模糊圈,找到了从闭模糊拟阵的模糊相关集或模糊独立集计算模糊圈的方法,并给出了相应的算法.     

Guided Local Search for Final Placement in VLSI Design

The design of a VLSI circuit consists of two main parts: First, the logical functionality of the circuit is described, and then the physical layout of the modules and connections is settled. In the latter process one wishes to place the modules such that the necessary wiring becomes as small as possible in order to minimize area usage and delays on signal paths. The placement problem is the subproblem of the layout problem which considers the geometric locations of the modules. A new heuristic is presented for the general cell placement problem where the objective is to minimize total bounding box netlength. The heuristic is based on the Guided Local Search (GLS) metaheuristic. GLS modifies the objective function in a constructive way to escape local minima. Previous attempts to use local search on final (or detailed) placement problems have often failed as the neighbourhood quickly becomes too excessive for large circuits. Nevertheless, by combining GLS with Fast Local Search it is possible to focus the search on appropriate sub-neighbourhoods, thus reducing the time complexity considerably. Comprehensive computational experiments with the developed algorithm are reported on a broad range of industrial circuits. The experiments demonstrate that the developed algorithm is able to improve the estimated routing length of large-sized layouts with as much as 20 percent when compared to existing algorithms.     

什么是不恢复余数法——阵列除法器的数学分析(Ⅰ)

运算器对于CPU的性能有重要影响,除法器是运算器的一个重要组件.除法器电路常用不恢复余数法,但声称采用了不恢复余数法的各种电路采用的算法却有明显区别.后续文试图对不恢复余数法及不恢复余数阵列除法器电路进行分析.给出了不恢复余数法的一种数学形式及证明.这种形式经过等效变形后才成为电路所用的算法,这一点将在后续文中给出.     

An effective compact formulation of the max cut problem on sparse graphs

We address the Max Cut problem by developing a compact formulation from the model expressing the condition that cuts and circuits have even intersection. This formulation turns out to be effective on sparse graphs especially with respect to the model based on triples of nodes.     

Variational integrators for electric circuits

Variational integrators are symplectic-momentum preserving integrators that are based on a discrete variational formulation of the underlying system. So far, variational integrators have been mainly developed and used for a wide variety of mechanical systems. In this work, we develop a variational integrator for the simulation of electric circuits. An appropriate variational formulation is presented to model the circuit from which the equations of motion are derived. Finally, a corresponding time-discrete variational formulation provides an iteration scheme for the simulation of the electric circuit. In this way, a variational integrator is constructed that gains several advantages. A comparison to standard integration techniques shows that even for simple LCR circuits a better long-time energy behavior and frequency preservation can be obtained. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Graphs having circuits with at least two chords

All 2-connected non-bipartite graphs are characterized which have a minimal valency ≥3 and which have no odd circuit with two or more chords. From this it is derived that in each graph with chromatic number ≥4 containing no complete 4-graph there is an odd circuit with two or more chords. This result was conjectured by P. Erdös. Corresponding results for even circuits and for circuits with a fixed edge are obtained. Some related problems of the Turán type are solved.     

Routing and Admission Control in General Topology Networks with Poisson Arrivals

Emerging high-speed networks will carry traffic for services such as video-on-demand and video teleconferencing that require resource reservation along the path on which the traffic is sent. High bandwidth-delay product of these networks prevents circuit rerouting, i.e., once a circuit is routed on a certain path, the bandwidth taken by this circuit remains unavailable for the duration (holding time) of this circuit. As a result, such networks will need effectiveroutingandadmission controlstrategies. Recently developed on-line routing and admission control strategies have logarithmic competitive ratios with respect to theadmission ratio(the fraction of admitted circuits). Such guarantees on performance are rather weak in the most interesting case where the rejection ratio of the optimum algorithm is very small or even 0. Unfortunately, these guarantees cannot be improved in the context of the considered models, making it impossible to use these models to identify algorithms that are going to perform well in practice. In this paper we develop routing and admission control strategies for a probabilistic model, where the requests for virtual circuits between any two points arrive according to a Poisson process and where the circuit holding times are exponentially distributed. Our model is close to the one that was developed to analyze and tune the (currently used) strategies for managing traffic in long-distance telephone networks. We strengthen this model by assuming that the rates of the Poisson processes (the “traffic matrix”) are unknown to the algorithm and are chosen by the adversary. Our strategy is competitive with respect to the expectedrejection ratio. More precisely, it achieves an expected rejection ratio of at mostR* + ?, whereR* is the optimum expected rejection ratio. The expectations are taken over the distribution of the request sequences, and, whereris the maximum fraction of an edge bandwidth that can be requested by a single circuit. Our result should be viewed in the context of the previous competitive routing and admission control strategies that requirer ≤ 1/log n, but are not able to formally analyze the (intuitively clear) relation betweenrand the performance achievable in realistic situations.     

VLSI Circuit Performance Optimization by Geometric Programming

Delay of VLSI circuit components can be controlled by varying their sizes. In other words, performance of VLSI circuits can be optimized by changing the sizes of the circuit components. In this paper, we define a special type of geometric program called unary geometric program. We show that under the Elmore delay model, several commonly used formulations of the circuit component sizing problem considering delay, chip area and power dissipation can be reduced to unary geometric programs. We present a greedy algorithm to solve unary geometric programs optimally and efficiently. When applied to VLSI circuit component sizing, we prove that the runtime of the greedy algorithm is linear to the number of components in the circuit. In practice, we demonstrate that our unary-geometric-program based approach for circuit sizing is hundreds of times or more faster than other approaches.     

极小圈模对与二元域拟阵的特征

研究极小圈模对与二元域拟阵的特征.首先给出拟阵M的极小圈模对,模对的并的秩与相应的超平面的交的秩三者的等价关系.在两个极小圈不等的条件下,证明了满足极小圈消去公理的极小圈是唯一的并且极小圈模对的对称差包含在其中,结合极小圈的对称差的表示,证明了极小圈与基的差的绝对值大于等于2.后面两个证明都把原来的必要条件推广为充要条件.最后,用M上不相同的极小圈,极小圈模对,极小圈的对称差表示,M上不相等的超平面,超平面的并不等于E及满足的秩等式极简单地刻划了二元域拟阵M的特征.     

Local elimination algorithms for solving sparse discrete problems

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.     

A note on the separation of subtour elimination constraints in elementary shortest path problems

This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.     

Two Algorithms for Solving a Kind of Heat Conduction Equations

In this paper, a strategy is suggested for numerical solution of a kind of parabolic partial differential equations with nonlinear boundary conditions and discontinuous coefficients, which arise from practical engineering problems. First, a difference equation at the discontinuous point is established in which both the stability and the truncation error are consistent with the total difference equations. Then, on account of the fact that the coefficient matrix of the difference equations is tridiagonal and nonlinearity appears only in the first and the last equations, two algorithms are suggested: a mixed method combining the modified Gaussian elimination method with the successive recursion method, and a variant of the modified Gaussian elimination method. These algorithms are shown to be effective.     

Boolean autoencoders and hypercube clustering complexity

We introduce and study the properties of Boolean autoencoder circuits. In particular, we show that the Boolean autoencoder circuit problem is equivalent to a clustering problem on the hypercube. We show that clustering m binary vectors on the n-dimensional hypercube into k clusters is NP-hard, as soon as the number of clusters scales like ${m^\epsilon (\epsilon >0 )}$ , and thus the general Boolean autoencoder problem is also NP-hard. We prove that the linear Boolean autoencoder circuit problem is also NP-hard, and so are several related problems such as: subspace identification over finite fields, linear regression over finite fields, even/odd set intersections, and parity circuits. The emerging picture is that autoencoder optimization is NP-hard in the general case, with a few notable exceptions including the linear cases over infinite fields or the Boolean case with fixed size hidden layer. However learning can be tackled by approximate algorithms, including alternate optimization, suggesting a new class of learning algorithms for deep networks, including deep networks of threshold gates or artificial neurons.