Counting and Topological Order

The counting method is a simple and efficient method for processing linear recursive datalog queries.Its time complexity is bounded by O(n,e)where n and e denote the numbers the numbers of nodes and edges,respectively,in the graph representing the input.relations.In this paper,the concepts of heritage appearance function and heritage selection function are introduced,and an evaluation algorithm based on the computation of such functions in topological order is developed .This new algorithm requires only linear time in the case of non-cyclic data.     

Energy Efficiency of a Multi-Core Processor by Tag Reduction

We consider the energy saving problem for caches on a multi-core processor.In the previous research on low power processors,there are various methods to reduce power dissipation.Tag reduction is one of them.This paper extends the tag reduction technique on a single-core processor to a multi-core processor and investigates the potential of energy saving for multi-core processors.We formulate our approach as an equivalent problem which is to find an assignment of the whole instruction pages in the physical memory to a set of cores such that the tag-reduction conflicts for each core can be mostly avoided or reduced.We then propose three algorithms using different heuristics for this assignment problem.We provide convincing experimental results by collecting experimental data from a real operating system instead of the traditional way using a processor simulator that cannot simulate operating system functions and the full memory hierarchy.Experimental results show that our proposed algorithms can save total energy up to 83.93% on an 8-core processor and 76.16% on a 4-core processor in average compared to the one that the tag-reduction is not used for.They also significantly outperform the tag reduction based algorithm on a single-core processor.     

Parallel solution for finite element linear systems of equations on workstation cluster

With the advances in the high speed computers network technologies, a workstation cluster is becoming the main environment for parallel processing. Finite element linear systems of equations are common throughout structural analysis in Civil Engineering. The preconditioned conjugate gradient method （PCGM） is an iterative method used to solve the finite element systems of equations with symmetric positive definite system matrices. In this paper, the algorithm of PCGM is parallelized and implemented on DELL workstation cluster. Optimization techniques for the sparse matrix vector multiplication are adopted in programming. The storage scheme is analyzed in detail. The experiment result shows that the designed parallel algorithm has high speedup and good efficiency on the high performance workstation cluster. This illustrates the power of parallel computing in solving large problems much faster than on a single processor.     

esign of power controller in CDMA system with power and SIR error minimization

In this paper, an uplink power control problem is considered for code division multiple access （CDMA） systems. A distributed algorithm is proposed based on linear quadratic optimal control theory. The proposed scheme minimizes the sum of the power and the error of signal-to-interference ratio （SIR）. A power controller is designed by constructing an optimization problem of a stochastic linear quadratic type in Krein space and solving a Kalman filter problem.     

Design of power controller in CDMA system with power and SIR error minimization

In this paper, an uplink power control problem is considered for code division multiple access (CDMA) systems. A distributed algorithm is proposed based on linear quadratic optimal control theory. The proposed scheme minimizes the sum of the power and the error of signal-to-interference ratio (SIR). A power controller is designed by constructing an optimization problem of a stochastic linear quadratic type in Krein space and solving a Kalman filter problem.     

Algorithm and Implementation of Parallel Multiplication in a Mixed Number System

This paper presents a high-speed multiplication algorithm for the mixed number system of the ordinarybinary number and the symmetric redundant binary number.It is implemented with the multivalned logictheory,and 3-valued and 2-valued circuits are used.The 3-valued circuit proposed in this paper is anemitter-coupled logic circuit with high speed,simplicity and powerful functions.A 3-valued ECL thresholdgate can simultaneously produce six types of one-variable operations.The array multiplier,designed withthe algorithm and the circuits,is fast and simple,and is suitable for building LSI.It can be used in a high-speed computer just as an ordinary binary multiplier.     

CNB: A critical-network-based timing optimization method for standard cell global routing

A novel method, named critical-network-based (CNB),for timing optimization in global routing is presented in this paper.The essence of this method is different from that of the typical existing ones,named nets-based (NB) and critical-path-based (CPB).The main contribution of this paper is that the CNB delay reduction method is more efficient than the typical existing ones.This new method makes it possible to reduce the delay in an overall survey.Based on CNB,a timing optimization algorithm for global routing is implemented and tested on Microelectronics Center of North Carolina (MCNC) benchmarks in this paper.The experimental results axe compared between this algorithm and the existing ones.The experimental results show that this algorithm is able to control the delay efficiently.     

Sub-optimality analysis of mobile robot rolling path planning

Rolling planning is an efficient method for path planning in uncertain environment. In this paper, the general principle and algorithm of mobile robot path planning based on rolling windows are studied. The sub-optimality of rolling path planning is analyzed in details and explained with a concrete example.     

Pattern Matching Compilation of Functions Defined in Context—Free Languages

LFC is a functional language based on recursive functions defined in context-free languages.In this paper,a new pattern matching algorithm for LFC is presented,which can represent a sequence of patterns as an integer by an encoding method.It is a rather simple method and produces efficient case-expressions for pattern matching definitions of LFC.The algorithm can also be used for other functional languages,but for nested patterns it may become complicated and further studies are needed.     

高精度图像测量与对准系统的算法研究

In this paper a new high accuracy image measurement and registration system design is proposed, in which edges of image in pixel are detected by improved Canny operator, edge points are recorded by an auto-tracing algorithm, edges in sub-pixel are located by spatial moment-based operator. The object parameters are calculated by means of Least Squares and the accuracy is improved by a proposed algorithm. Finally an automatic detection,recognition and measurement algorithm is proposed. The simulation experiment on a standard circle shows the properties of validity, feasibility about the design and algorithm proposed.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.

     

基于整体退火遗传算法的低功耗最佳极性搜索

针对n变量逻辑函数在不同极性下所对应的XNOR/OR电路功耗和面积不同的特点,首先用信号概率传递算法和多输入XNOR/OR(同或/或)门的低功耗分解算法建立了XNOR/OR电路的功耗估计模型.在此基础上,将基于列表技术的极性转换算法和整体退火遗传算法相结合,提出了一种针对大规模XNOR/OR电路的低功耗最佳极性搜索算法.对8个较大规模MCNC Benchmark电路测试表明,该算法搜索到的最佳极性所对应的XNOR/OR电路与极性0时的XNOR/OR电路相比,平均节省功耗和面积分别达到了84.4%和65.2%.     

An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs

In this paper, to find all maximal cliques of a trapezoid graph a set of intervals have been constructed by projecting the geometrical representation of the graph on the bottom line. The proposed algorithm for this purpose takes O(n ² + yn) time, where n is the number of vertices of the graph and y is the output size.     

Finding least-weight subsequences with fewer processors

By restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takesO(log² n) time on a CREW PRAM with n³/logn processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log² n log logn) time withn/log logn processors, or in O(log² n) time withn logn processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12].     

基于MODCPSO算法的三值FPRM电路面积与延时优化

针对三值固定RM(fixed polarity reed-muller,FPRM)逻辑电路面积与延时综合优化问题进行了研究,提出了一种基于竞争行为多目标离散粒子群算法(Multi-Objective Discrete Competitive Particle Swarm Optimization,MODCPSO)的极性搜索方案。首先在MODCPSO算法中,引入竞争行为机制,将种群划分为不同的团队,从各个团队中随机抽取两个粒子进行比较,令较差的粒子向着较好的粒子进行速度和位置的更新。同时引入变异机制,令种群粒子能够跳出局部最优解,继续更新进化。然后,结合三值FPRM极性转换技术和MODCPSO算法搜索电路面积与延时的最佳极性。最后,利用PLA格式的MCNC Benchmark电路实现算法测试,并与DPSO算法、MODPSO算法进行了性能对比。实验结果验证了MODCPSO算法的有效性。     

Sull’ordinamento secondo un criterio di ottimalità decrescente delle politiche ammissibili,in un problema non lineare di ripartizione

In this Paper an algorithm is given, for a problem of allocation of resources, which allows to individnate directly the firstk policies (among those which invest on the whole the same quantity of resource as the optimal ones), policies being ordered suiving the rule of decreasing optimality. The algorithm is referred to the particular case of a discrete allocation problem, in which functions of the profit acquirable in productive processes, are given in a discrete set.

---

---

Lavoro eseguito nell’ambito dell’attività del Gruppo di Ricerca Matematica n^o 38 (Università Ca’ Foscari, Venezia) del C.N.R. per l’anno accademico 1967–68.     

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

A more efficient algorithm for the min-plus multiplication

The (min, + ) product C of two n × n matrices A and B is defined as C _ij = min_1≦k≦n A _ik + B _kj . This paper presents an algorithm to compute the (min, +) product of two n × n matrices. The algorithm follows the approach described by Fredman, but is faster than Fredman's own algorithm: its time complexity is either O(n ³/√log₂ n) or even O(n ^2.5√log₂ n), if one adheres to the uniform-cost RAM model faithfully.

This result implies the existence of O(n ³/√log₂ n) algorithms for the problems that (min, +) matrix multiplication is equivalent to, such as the all-pairs shortest paths problem.

As the presented algorithm uses operations on sets, the formal analysis of its time complexity raises a few interesting questions about the applicability of the standard RAM complexity model.     

Construction of 1-resilient Boolean functions with optimum algebraic immunity

In this paper, for an integer n≥10, two classes of n-variable Boolean functions with optimum algebraic immunity (AI) are constructed, and their nonlinearities are also determined. Based on non-degenerate linear transforms to the proposed functions, we can obtain 1-resilient n-variable Boolean functions with optimum AI and high nonlinearity if n?1 is never equal to any power of 2.     

Solving Connected Dominating Set Faster than 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 ⁿ ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 ⁿ barrier, by presenting a simple O(1.9407 ⁿ ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique. An extended abstract of this paper appeared in the proceedings of FSTTCS’06. Fedor V. Fomin was additionally supported by the Research Council of Norway.