Improved task-allocation algorithms to maximize reliability ofredundant distributed computing systems

This paper considers the problem of finding an optimal and sub-optimal task-allocation (assign the processing node for each module of a task or program) in redundant distributed computing systems, with the goal of maximizing system-reliability (probability that the system completes the entire task successfully). Finding an optimal task-allocation is NP-hard in the strong sense. An efficient algorithm is presented for optimal task-allocation in a distributed computing system with level-2 redundancy. The algorithm, (a) uses branch and bound with underestimates for reducing the average time complexity of optimal task-allocation computations, and (b) reorders the list of modules to allow a subset of modules that does not intra-communicate to be assigned last, for further reduction in the computations of optimal task-allocation for maximizing reliability. An efficient heuristics algorithm is given which obtains sub-optimal solutions in a reasonable computation time. The performance of our algorithms is given over a wide range of parameters such as number of modules, number of processing nodes, ratio of average execution cost to average communication cost, and connectivity of modules. The effectiveness of the optimal task-allocation algorithm is demonstrated by comparing it to a competing optimal task-allocation algorithm, for maximizing reliability. The performance of our algorithm improves very much when the difference between the number of modules and the connectivity increases     

Multidimensional chirp algorithms for computing Fourier transforms

Continuous versions of the multidimensional chirp algorithms compute the function G(y)=F(My), where F(y) is the Fourier transform of a function f(x) of a vector variable x and M is an invertible matrix. Discrete versions of the algorithms compute values of F over the lattice L(2)=ML(1 ) from values of f over a lattice L(1), where L(2) need not contain the lattice reciprocal to L(1). If M is symmetric, the algorithms are multidimensional versions of the Bluestein chirp algorithm, which employs two pointwise multiplication operations (PMOs) and one convolution operation (CO). The discrete version may be efficiently implemented using fast algorithms to compute the convolutions. If M is not symmetric, three modifications are required. First, the Fourier transform is factored as the product of two Fresnel transforms. Second, the matrix M is factored as M=AB, where A and B are symmetric matrices. Third, the Fresnel transforms are modified by the matrices A and B and each modified transform is factored into a product of two PMOs and one CO.     

Improved fairness algorithms for rings with spatial reuse

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In this paper, we concentrate on a class of such policies that achieves fairness by allocating transmission quotas to nodes. For such policies, we provide mechanisms for improving delays and increasing overall throughput without compromising fairness     

Distributed algorithms for computing shortest pairs of disjointpaths

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied     

Efficient algorithms for computing the 2-D hexagonal Fouriertransforms

In this paper, representations of the two-dimensional (2-D) signals are presented that reduce the computation of 2-D discrete hexagonal Fourier transforms (2-D DHFTs). The representations are based on the concept of the covering that reveals the mathematical structure of the transforms. Specifically, a set of unitary paired transforms is derived that splits the 2-D DHFT into a number of smaller one-dimensional (1-D) DFTs. Examples for the 8×4 and 16×8 hexagonal lattices are described in detail. The number of multiplications required for computing the 8×4- and 16×8-point DHFTs are equal 20 and 136, respectively. In the general N⩾8 case, the number of multiplications required to compute the 2N×N-point DHFT by the paired transforms equals N² (log N-1)+N     

改进的参考独立分量分析算法

针对参考独立分量分析收敛速度较慢的问题,提出了两种基于改进的快速收敛牛顿迭代方法的参考独立分量分析方法。该方法首先对观测信号进行白化预处理,避免观测信号矩阵求逆运算,减少了算法的计算量;然后采用修正的具有三阶收敛速度的牛顿迭代方法对参考独立分量分析的代价函数进行优化,推导出快速收敛的参考独立分量分析算法。仿真实验结果表明,改进后的算法是有效的,算法收敛速度相对原算法提高了1.7倍,相对现有算法提高了1倍,而且误差更小。     

Fault simulation on massively parallel SIMD machines algorithms,implementations and results

Two algorithms for fault simulation of combinational networks on massively parallel SIMD machines are presented. One algorithm uses a variant of the PPSFP [1] approach, while the other uses a mixture of parallel fault simulation [2] and PPSFP [1]. The algorithms have been implemented on the [Thinking Machines Corporation's] Connection Machine [3]. The second algorithm compares very favorably with published results for well known serial algorithms on the ISCAS benchmark circuits [4]. The results indicate that parallel processing could be a valuable tool for accelerating VLSI CAD applications.     

基于改进CS算法的侧斜视SAR成像

针对SAR的斜视工作模式,该文建立了雷达信号的回波模型,详细分析了回波信号的瞬时方位频率和瞬时多普勒频率及距离Chirp斜视对方位频率的影响,结合经典的 CS算法,提出了一种基于斜视的改进CS算法,并利用该方法进行了仿真试验,理论分析和仿真结果表明,该方法更符合斜视SAR的几何关系,能有效的进行距离压缩、距离徙动校正和方位聚焦,改善成像质量。     

Improved approximation algorithms for connected sensor cover

Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and it is infeasible to replenish energy via replacing batteries. An effective approach for energy conservation is scheduling sleep intervals for some sensors, while the remaining sensors stay active providing continuous service. In this paper we consider the problem of selecting a set of active sensors of minimum cardinality so that sensing coverage and network connectivity are maintained. We show that the greedy algorithm that provides complete coverage has an approximation factor no better than Ω(log n), where n is the number of sensor nodes. Then we present algorithms that provide approximate coverage while the number of nodes selected is a constant factor far from the optimal solution. Finally, we show how to connect a set of sensors that already provides coverage.     

Improved algorithms for synchronizing computer network clocks

The Network Time Protocol (NTP) is widely deployed in the Internet to synchronize computer clocks to each other and to international standards via telephone modem, radio and satellite. The protocols and algorithms have evolved over more than a decade to produce the present NTP Version 3 specification and implementations. Most of the estimated deployment of 100000 NTP servers and clients enjoy synchronization to within a few tens of milliseconds in the Internet of today. This paper describes specific improvements developed for NTP Version 3 which have resulted in increased accuracy, stability and reliability in both local-area and wide-area networks. These include engineered refinements of several algorithms used to measure time differences between a local clock and a number of peer clocks in the network, as well as to select the best subset from among an ensemble of peer clocks and combine their differences to produce a local dock accuracy better than any in the ensemble. This paper also describes engineered refinements of the algorithms used to adjust the time and frequency of the local clock, which functions as a disciplined oscillator. The refinements provide automatic adjustment of algorithm parameters in response to prevailing network conditions, in order to minimize network traffic between clients and busy servers while maintaining the best accuracy. Finally, this paper describes certain enhancements to the Unix operating system kernel software in order to realize submillisecond accuracies with fast workstations and networks     

Improved approximate QR-LS algorithms for adaptive filtering

This paper studies a class of O(N) approximate QR-based least squares (A-QR-LS) algorithm recently proposed by Liu in 1995. It is shown that the A-QR-LS algorithm is equivalent to a normalized LMS algorithm with time-varying stepsizes and element-wise normalization of the input signal vector. It reduces to the QR-LMS algorithm proposed by Liu et al. in 1998, when all the normalization constants are chosen as the Euclidean norm of the input signal vector. An improved transform-domain approximate QR-LS (TA-QR-LS) algorithm, where the input signal vector is first approximately decorrelated by some unitary transformations before the normalization, is proposed to improve its convergence for highly correlated signals. The mean weight vectors of the algorithms are shown to converge to the optimal Wiener solution if the weighting factor w of the algorithm is chosen between 0 and 1. New Givens rotations-based algorithms for the A-QR-LS, TA-QR-LS, and the QR-LMS algorithms are proposed to reduce their arithmetic complexities. This reduces the arithmetic complexity by a factor of 2, and allows square root-free versions of the algorithms be developed. The performances of the various algorithms are evaluated through computer simulation of a system identification problem and an acoustic echo canceller.     

Recursive and iterative algorithms for computing eigenvalues ofHermitian Toeplitz matrices

The numerical solution of the complete eigenspectrum for Hermitian Toeplitz matrices is presented. Trench's algorithm (1989), which employs bisection on contiguous intervals, and the Pegasus method are used to achieve estimates of distinct eigenvalues. Several modifications of Trench's algorithm are examined; the goals are an increase in the rate of convergence, even at some reduction in estimate accuracy, and an accommodation of eigenvalue multiplicity or clustering. A promising approach that contains three key ingredients is found. They are: a modification of Trench's procedure to employ noncontiguous intervals, a procedure for multiplicity identification, and a replacement of the Pegasus method by the modified Rayleigh quotient iteration. The result is the basis for a novel eigenspectrum solver with a cubic convergence rate and good estimation accuracy. Simulation results for high-order Hermitian Toeplitz matrices are provided     

基于CSP的能耗高效云计算资源调度模型与算法

利用约束满足问题对异构云数据中心的能耗优化资源调度问题建模,通过求解建立的约束模型可以获得能耗最优的资源分配方式,并在此基础上提出了能耗优化的资源分配算法dynamicpower (DY)。与已有的算法MinPM、FFD、BFD相比,算法DY考虑了资源的异构性,能够降低云数据中心物理服务器的能耗。最后,利用Choco实现了提出的算法DY,并将DY与MinPM、FFD、BFD进行实验比较,实验结果表明,提出的算法在能耗上有明显优势。     

Improved genetic algorithm for channel allocation with channel borrowing in mobile computing

This paper exploits the potential of the Genetic Algorithm to solve the cellular resource allocation problem. When a blocked host is to be allocated to a borrowable channel, a crucial decision is which neighboring cell to choose to borrow a channel. It is an optimization problem and the genetic algorithm is efficiently applied to handle this. The Genetic Algorithm, for this particular problem, is improved by introducing a new genetic operator, named pluck, that incorporates a problem-specific knowledge in population generation and leads to a better channel utilization by reducing the average blocked hosts. The pluck operator makes the crucial decision of when and which cell to borrow with the future consideration that the borrowing should not lead the network to chaos. It makes a channel borrowing decision that minimizes the number of blocked hosts and improves the long-term performance of the network. Efficacy of the proposed method has been evaluated by experimentation.     

Two fast algorithms for computing point scalar multiplications on elliptic curves

The key operation in Elliptic Curve Cryptosystems(ECC) is point scalar multiplication. Making use of Frobenius endomorphism, Mfiller and Smart proposed two efficient algorithms for point scalar multiplications over even or odd finite fields respectively. This paper reduces thec orresponding multiplier by modulo τ^k-1 … τ 1 and improves the above algorithms. Implementation of our Algorithm 1 in Maple for a given elliptic curve shows that it is at least as twice fast as binary method. By setting up a precomputation table, Algorithm 2, an improved version of Algorithm 1, is proposed. Since the time for the precomputation table can be considered free, Algorithm 2 is about (3/2) log2 q - 1 times faster than binary method for an elliptic curve over Fq.     

Improved dithering algorithms and circuit implementing for STN-LCD

This article proposes a creative brightness average method to improve the traditional dithering algorithm for super twisted nematic-liquid crystal display (STN-LCD).This method restrains the flicker and crosstalk phenomena by avoiding the simultaneous turning on or turning off between adjacent pixels in the same frame. It costs little hardware to realize the brightness average circuit in the liquid crystal display (LCD) controller, without increasing the complexity of STN-LCD driver circuit. The experimental results show that when the frame frequency is 60 Hz, the monochrome image adds up to 64 gray levels, while the multicolor image adds up to 643= 262 144 colors. Meanwhile, the power consumption of the prototype is only 3 317 mW. In short, the brightness average circuit can restrain the phenomena of flicker in high efficiency, and can remarkedly improve the gray and multicolor effect for STN-LCD without increasing the frame frequency, which leads to an apparent decrease in the power consumption.     

基于多维变换的传感器网络节点改进定位算法

提出了两种基于多维变换的无线传感器网络节点的改进定位算法,改进算法一以相合分解代替特征值分解,能简化算法步骤并提高定位精度,时间复杂度为O（n3）,可以应用于对定位精度要求高的场合;改进算法二采用强迫正定Cholesky分解,虽然定位精度比前者稍差,但时间复杂度降为O（n2）,更适合于对实时性要求高的应用环境。仿真结果表明,两种改进算法都能实现高精度节点定位。     

改进的移动计算平台直接匿名证明方案

分析了Ge等人提出的直接匿名证明方案的安全缺陷,指出该方案的认证协议在用于远程证明时不能抵抗重放攻击和平台伪装攻击。提出一种改进的直接匿名证明的认证协议,引入会话密钥协商机制,增强互认证功能。分析表明,改进方案在正确进行直接匿名证明的前提下,满足不可伪造性和匿名性,能够抵抗重放攻击和平台伪装攻击,协议性能满足移动计算平台的可信验证需求。     

Comparison-based diagnosis with faulty comparators

The letter deals with a new approach to diagnosis by comparison. A new class of diagnosable systems is introduced: in these systems, units and comparators used in the diagnostic process may fail. Failure of comparators introduces a new condition of test invalidation for comparison. Characterisation theorems and fault identification similarities between different comparison models are presented.     

Two recursive algorithms for computing the weight distribution ofcertain irreducible cyclic codes

Two recursive algorithms for computing the weight distributions of certain binary irreducible cyclic codes of length n in the so-called index 2 case are presented. The running times of these algorithms are smaller than O(log²r) where r=2^m and n is a factor of r-1