一种基于加法链的快速标量乘算法

给出一种标量的串长加法链算法来提高椭圆曲线标量乘法的效率。新的标量乘算法结合底层域直接计算2Q+P、2^nR+S算法,使用大小窗口法将串长算法和滑动窗口算法结合,加法链长度、存储空间和预计算都减少,其效率比二元法提高53%,比NAF法提高47.5%,比串长算法提高46.2%,比Windows法提高42.2%。     

Homotopy techniques for multiplication modulo triangular sets

We study the cost of multiplication modulo triangular families of polynomials. Following previous work by Li et al. (2007), we propose an algorithm that relies on homotopy and fast evaluation–interpolation techniques. We obtain a quasi-linear time complexity for substantial families of examples, for which no such result was known before. Applications are given notably to additions of algebraic numbers in small characteristic.     

New algorithms for relaxed multiplication

In previous work, we have introduced the technique of relaxed power series computations. With this technique, it is possible to solve implicit equations almost as quickly as doing the operations which occur in the implicit equation. Here “almost as quickly” means that we need to pay a logarithmic overhead. In this paper, we will show how to reduce this logarithmic factor in the case when the constant ring has sufficiently many 2^p$2^p$th roots of unity.     

Automated synthesis of multiple analog circuits using evolutionary computation for redundancy-based fault-tolerance

Analog circuits are one of the most important parts of modern electronic systems and the failure of electronic hardware presents a critical threat to the completion of modern aircraft, spacecraft, and robot missions. Compared to digital circuits, designing fault-tolerant analog circuits is a difficult and knowledge-intensive task. A simple but powerful method for robustness is a redundancy approach to use multiple circuits instead of single one. For example, if component failures occur, other redundant components can replace the functions of broken parts and the system can still work. However, there are several research issues to make the redundant system automatically. In this paper, we used evolutionary computation to generate multiple analog circuits automatically and then we combined the solutions to generate robust outputs. Evolutionary computation is a natural way to produce multiple redundant solutions because it is a population-based search. Experimental results on the evolution of the low-pass, high-pass and band-stop filters show that the combination of multiple evolved analog circuits produces results that are more robust than those of the best single circuit.     

Theoretical comparison between sequential redundancy addition and removal and retiming optimization techniques

This paper attempts to determine the capabilities of existing redundancy addition and removal (SRAR) techniques for logic optimization of sequential circuits. To this purpose, we compare this method with the retiming and resynthesis (RaR) techniques. For the RaR case the set of possible transformations has been established by relating them to STG transformations by other authors. Following these works, we first formally demonstrate that logic transformations provided by RaR are covered by SRAR as well. Then we also show that SRAR is able to identify transformations that cannot be found by RaR. This way we prove that the sequential redundancy addition and removal technique provides more possibilities for logic optimization.     

3D-MMA:基于3D集成电路的矩阵乘加速结构

脉动阵列结构规整、吞吐量大,适合矩阵乘算法,广泛用于设计高性能卷积、矩阵乘加速结构。在深亚微米工艺下,通过增大阵列规模来提升芯片计算性能,会导致频率下降、功耗剧增等问题。因此,结合3D集成电路技术,提出了一种将平面脉动阵列结构映射到3D集成电路上的双精度浮点矩阵乘加速结构3D-MMA。首先,设计了针对该结构的分块映射调度算法,提升矩阵乘计算效率;其次,提出了基于3D-MMA的加速系统,构建了3D-MMA的性能模型,并对其设计空间进行探索;最后,评估了该结构实现代价,并同已有先进加速器进行对比分析。实验结果表明,访存带宽为160GB/s时,采用4层16×16脉动阵列的堆叠结构时,3D-MMA计算峰值性能达3TFLOPS,效率达99%,且实现代价小于二维实现。在相同工艺下,同线性阵列加速器及K40GPU相比,3D-MMA的性能是后者的1.36及1.92倍,而面积远小于后者。探索了3D集成电路在高性能矩阵乘加速器设计中的优势,对未来进一步提升高性能计算平台性能具有一定的参考价值。     

Polynomial-time inference of all valid implications for Horn and related formulae

This paper investigates the complexity of a general inference problem: given a propositional formula in conjunctive normal form, find all prime implications of the formula. Here, a prime implication means a minimal clause whose validity is implied by the validity of the formula. We show that, under some reasonable assumptions, this problem can be solved in time polynomially bounded in the size of the input and in the number of prime implications. In the case of Horn formulae, the result specializes to yield an algorithm whose complexity grows only linearly with the number of prime implications. The result also applies to a class of formulae generalizing both Horn and quadratic formulae.To the memory of Robert G. Jeroslow     

Top-down lower bounds for depth-three circuits

We present a top-down lower bound method for depth-three , , ¬-circuits which is simpler than the previous methods and in some cases gives better lower bounds. In particular, we prove that depth-three , , ¬-circuits that compute parity (or majority) require size at least , respectively). This is the first simple proof of a strong lower bound by a top-down argument for non-monotone circuits.     

Computational methods for database repair by signed formulae*

We introduce a simple and practical method for repairing inconsistent databases. Given a possibly inconsistent database, the idea is to properly represent the underlying problem, i.e., to describe the possible ways of restoring its consistency. We do so by what we call signed formulae, and show how the ‘signed theory’ that is obtained can be used by a variety of off-the-shelf computational models in order to compute the corresponding solutions, i.e., consistent repairs of the database. *This paper is a revised and extended version of [9].     

Empirical design formulae for series‐fed substrate integrated waveguides power divider

In this article, empirical design formulae for a unit cell of series‐fed substrate integrated waveguide power divider for a wide range of power division ratio from 1:1 to 1:40 are presented. These formulae are determined through extensive simulations carried out in Ansys HFSS. The physical dimensions of the power divider for any given power division ratio can be directly determined through the design formulae presented in the article. A simple design procedure is discussed and verified with the help of experimental and simulation results. For experimental verification, a power divider is designed to operate in X band, and its prototype is developed on RT Duroid 5880, the measured results for this power divider are in close agreement with simulated as well as predicted results. Also, for validating the design procedure over a wide range of frequencies, many power dividers are designed with different power division ratios, different operating frequencies and different cut‐off frequencies of TE₁₀ mode. The cut‐off frequency (f_c) of TE₁₀ mode is varied from 15 to 25 GHz, and the operating frequency is adjusted in between 1.2f_c and 1.8f_c. That is, 18–40 GHz, which is suitable for many microwave and millimeter wave applications. The obtained results are very close to the desired power division ratios.     

Signal transition graph constraints for synthesis of hazard-free asynchronous circuits with unbounded-gate delays

A synthesis procedure for asynchronous control circuits from a high level specification, signal transition graph (STG), is described. In this paper, we propose some syntactic constraints on STG to guarantee speed-independent implementation. We have introduced a global persistency concept in order to establish the relationship between the persistency concept introduced by Chu [2] (which we call local persistency) and the consistent state coding (CSC). The STG syntactic constraints required to compute theinput set of a signal are identified. This paper also describes an algorithm to ascertain whether a given STG has the CSC property. The algorithm identifies the non-persistent signals associated with the CSC violations. The algorithm has the advantage of operating directly on the STG rather than on the state graph.     

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle

We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho–Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM Journal of Applied Mathematics 49 (1989) 906–931] given by Tao [T. Tao, An uncertainty principle for cyclic groups of prime order, Mathematical Research Letters 12 (2005) 121–127], and a combinatorial lemma by Raz and Shpilka [R. Raz, A. Shpilka, Lower bounds for matrix product, in arbitrary circuits with bounded gates, SIAM Journal of Computing 32 (2003) 488–513]. This combination and an observation on ranks of circulant matrices, which we use to give a much shorter proof of the Donoho–Stark principle, may have other applications.     

A methodology for design of multilayer microwave circuits

This paper reviews and extends the design procedures developed recently for a broad class of multilayer microwave circuits such as couplers, filters, and baluns. Multilayer configurations are now becoming increasingly popular at microwave frequencies due to the several advantages over single-layer configurations. However, systematic design procedures for implementing multilayer circuits have not been available. Examples of multilayer circuits are presented for verifying the extended design procedures. The design procedure reported earlier for coupled line multilayer filters in a homogeneous dielectric substrate environment has been extended to inhomogeneous multilayered microstriplike configurations. Modified procedure is verified by comparing the results with a full-wave electromagnetic simulation. © 1998 John Wiley & Sons, Inc. Int J RF and Microwave CAE 8: 455–473, 1998     

Exponential lower bounds for depth three Boolean circuits

We consider the class of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has gates (for k = O(n ^1/2)) for some , and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC ¹ that require size depth 3 circuits. The main tool is a theorem that shows that any circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form x _i = 0, x _i = 1, x _i = x _j or x _i = ) of dimension at least log(a/s)log n. Received: April 1, 1997.     

A model for synchronous switching circuits and its theory of correctness

Following Bryant [2], an algorithm is given for translating a switching circuit design into a program that simulates its dynamic behavior. A theory of assertions based on Dijkstra [5] and UNITY [4] is then developed to formalize specifications of hardware circuit designs and to establish their correctness. Both combinational and sequential circuits are taken into account both in N-mos and C-mos; the latter turns out to be much simpler.Chaochen Zhou in on leave from the Software Institute, Academia Sinica     

Analysis and identification of speed-independent circuits on an event model

The object of this article is the analysis of asynchronous circuits for speed independence or delay insensitivity. The circuits are specified as a netlist of logic functions describing the components. The analysis is based on a derivation of an event specification of the circuit behavior in a form of a signal graph. Signal graphs can be viewed either as a formalization of timing diagrams, or as a signal interpreted version of marked graphs (a subclass of Petri nets). The main advantage of this method is that a state explosion is avoided. A restoration of an event specification of a circuit also helps to solve the behavior identification problem, i.e., to compare the obtained specification with the desired specification. We illustrate the method by means of some examples.     

基于Multisim的电路仿真分析与设计

Multisim是知名的EDA软件之一,内含数万种元器件和13种常用的虚拟仪嚣仪表。用它可以方便地搭接各种电工电子电路,准确地对电路进行仿真分析。通过几个电路设计实例的仿真分析,说明使用Multisim软件进行电路设计,不仅可以提高设计效率,而且可以保证设计质量。     

Min-rank conjecture for log-depth circuits

A completion of an m-by-n matrix A with entries in {0,1,?} is obtained by setting all ?-entries to constants 0 and 1. A system of semi-linear equations over GF₂ has the form Mx=f(x), where M is a completion of A and f:n{0,1}→m{0,1} is an operator, the ith coordinate of which can only depend on variables corresponding to ?-entries in the ith row of A. We conjecture that no such system can have more than ²n−?⋅mr(A) solutions, where ?>0 is an absolute constant and mr(A) is the smallest rank over GF₂ of a completion of A. The conjecture is related to an old problem of proving super-linear lower bounds on the size of log-depth boolean circuits computing linear operators x?Mx. The conjecture is also a generalization of a classical question about how much larger can non-linear codes be than linear ones. We prove some special cases of the conjecture and establish some structural properties of solution sets.     

Design of coplanar waveguide multilayer square spiral inductors for monolithic microwave integrated circuits

A square indicator using multilayer coplanar waveguide transmission lines on a GaAs fabricated by using monolithic microwave integrated circuits (MMIC) technology is presented. The polyimide layer formation, curing and dry etching processes are used in an attempt to obtain high quality dielectric layers suitable for MMIC applications. The experimental fabrication progress provides two metal layers with two polyimide spacer dielectric layers. A brief overview of the electromagnetic design process is included. The performance of the proposed spiral inductor is investigated experimentally and with electromagnetic simulations (Sonnet em) up to 20 GHz using RF‐on‐water measurements. A very good agreement is achieved, despite the highly three‐dimensional nature of the structure. ©1999 John Wiley & Sons, Inc. Int J RF and Microwave CAE 9: 86–92, 1999