RM及其扩展可调度性判定算法性能分析

可调度性判定是实时调度算法的关键问题．单调速率算法RM（rate monotonic）及其扩展是应用广泛的实时调度算法，大量文献讨论了实时任务在这些算法下的可调度性判定，给出了相应的判定算法．但迄今为止，对这些判定算法的性能分析都是理论上的定性分析或者只是少数几种判定算法之间的简单比较，这不利于实时系统的开发．归纳了RM及其扩展的可调度性判定算法，通过测试平台，系统地测试和分析了各算法的性能和适用场合，讨论了各种条件和实现方式对算法性能和可调度性的影响．

Classical two-site fidelity and quantum phase transitions in the Ising model and the extended Hubbard model

In this Letter, the classical two-site-ground-state fidelity (CTGF) is exploited to identify quantum phase transitions (QPTs) for the transverse field Ising model (TFIM) and the one-dimensional extended Hubbard model (EHM). Our results show that the CTGF exhibits an abrupt change around the regions of criticality and can be used to identify QPTs in spin and fermionic systems. The method is especially convenient when it is connected with the density-matrix renormalization group (DMRG) algorithm. (C) 2008 Elsevier B.V. All rights reserved.

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.

Application of the Conjugate Gradient Optimization Algorithm of Neural Network on Laser Machining

在应用激光技术加工复杂曲面时,通常以采样点集为插值点来建立曲面函数,然后实现曲面上任意坐标点的精确定位。人工神经网络的BP算法能实现函数插值,但计算精度偏低,往往达不到插值精确要求,造成较大的加工误差。提出人工神经网络的共轭梯度最优化插值新算法,并通过实例仿真,证明了这种曲面精确定位方法的可行性,从而为激光加工的三维精确定位提供了一种良好解决方案。这种方法已经应用在实际中。

Modification of Bertrand's theorem and extended Runge-Lenz vector

It is shown that for a particle with suitable angular moments in the screened Coulomb potential or isotropic harmonic potential, there still exist closed orbits rather than ellipse, characterized by the conserved aphelion and perihelion vectors, i.e. extended Runge-Lenz vector, which implies a higher dynamical symmetry than the geometrical symmetry O-3. The closeness of a planar orbit implies the radial and angular motional frequencies are commensurable.

Simulating shock to detonation transition: Algorithm and results

An algorithm based on flux-corrected transport and the Lagrangian finite element method is presented for solving the problem of shock dynamics. It is verified through the model problem of one-dimensional strain elastoplastic shock wave propagation that the algorithm leads to stable, non-oscillatory results. Shock initiation and detonation wave propagation is simulated using the algorithm, and some interesting results are obtained. (C) 1999 Academic Press.

Extended self-similar scaling law of multi-scale eddy structure in wall turbulence

The longitudinal fluctuating velocity of a turbulent boundary layer was measured in a water channel at a moderate Reynolds number. The extended self-similar scaling law of structure function proposed by Benzi was verified. The longitudinal fluctuating velocity, in the turbulent boundary layer was decomposed into many multi-scale eddy structures by wavelet transform. The extended self-similar scaling law of structure function for each scale eddy velocity was investigated. The conclusions are I) The statistical properties of turbulence could be self-similar not only at high Reynolds number, but also at moderate and low Reynolds number, and they could be characterized by the same set of scaling exponents xi (1)(n) = n/3 and xi (2)(n) = n/3 of the fully developed regime. 2) The range of scales where the extended self-similarity valid is much larger than the inertial range and extends far deep into the dissipation range,vith the same set of scaling exponents. 3) The extended selfsimilarity is applicable not only for homogeneous turbulence, but also for shear turbulence such as turbulent boundary layers.

Extended Stoney'S Formula For A Film-Substrate Bilayer With The Effect Of Interfacial Slip

The curvature-stress relation is studied for a film-substrate bilayer with the effect of interfacial slip and compared with that of an ideal interface without interfacial slip. The interfacial slip together with the dimensions, elastic and interfacial properties of the film and substrate layers can cause a significant deviation of curvature-stress relation from that with an ideal interface. The interfacial slip also results in the so-called free edge effect that the stress, constraint force, and curvature vary dramatically around the free edges. The constant curvature as predicted by Stoney's formula and the Timoshenko model of an ideal interface is no longer valid for a bilayer with a nonideal interface. The models with the assumption of an ideal interface can also lead to an erroneous evaluation on the true stress state inside a bilayer with a nonideal interface. The extended Stoney's formula incorporating the effects of both the layer dimensions and interfacial slip is presented.

Ancient Chinese algorithm: The Ying Buzu Shu (method of surplus and deficiency) vs Newton iteration method

Air exploratory discussion of an ancient Chinese algorithm, the Ying Buzu Shu, in about 2nd century BC, known as the rule of double false position in the West is given. In addition to pointing out that the rule of double false position is actually a translation version of the ancient Chinese algorithm, a comparison with well-known Newton iteration method is also made. If derivative is introduced, the ancient Chinese algorithm reduces to the Newton method. A modification of the ancient Chinese algorithm is also proposed, and some of applications to nonlinear oscillators are illustrated.

Composite materials dynamic fracture studies by generalized Shmuely difference algorithm

The generalized Shmuely Difference Algorithm (GSDA) is presented here to analyze the dynamic fracture performance of orthogonal-anisotropic composite materials, such as glass fibre reinforced phenolplast. The difference recurrence Formulae and boundary condition difference extrapolation formulae are derived and programmed. The dynamic stress intensity factors (DSIF) of the isotropic and anisotropic centrally cracked plates are computed respectively using GSDA and compared with that published previously. GSDA is proved effective and reliable. Copyright (C) 1996 Elsevier Science Ltd.

An algorithm for coarse particle sedimentation simulation by Stokesian dynamics

Coarse Particle sedimentation is studied by using an algorithm with no adjustable parameters based on stokesian dynamics. Only inter-particle interactions of hydrodynamic force and gravity are considered. The sedimentation of a simple cubic array of spheres is used to verify the computational results. The scaling and parallelism with OpenMP of the method are presented. Random suspension sedimentation is investigated with Mont Carlo simulation. The computational results are shown in good agreement with experimental fitting at the lower computational cost of O(N In N).

Algorithm for simulating fracture processes in concrete by lattice modeling

To simulate fracture behaviors in concrete more realistically, a theoretical analysis on the potential question in the quasi-static method is presented, then a novel algorithm is proposed which takes into account the inertia effect due to unstable crack propagation and meanwhile requests much lower computational efforts than purely dynamic method. The inertia effect due to load increasing becomes less important and can be ignored with the loading rate decreasing, but the inertia effect due to unstable crack propagation remains considerable no matter how low the loading rate is. Therefore, results may become questionable if a fracture process including unstable cracking is simulated by the quasi-static procedure excluding completely inertia effects. However, it requires much higher computational effort to simulate experiments with not very high loading rates by the dynamic method. In this investigation which can be taken as a natural continuation, the potential question of quasi-static method is analyzed based on the dynamic equations of motion. One solution to this question is the new algorithm mentioned above. Numerical examples are provided by the generalized beam (GB) lattice model to show both fracture processes under different loading rates and capability of the new algorithm.

A Hybrid Scheme Based on Finite Element/Volume Methods for Two Immiscible Fluid Flows

We have successfully extended our implicit hybrid finite element/volume (FE/FV) solver to flows involving two immiscible fluids. The solver is based on the segregated pressure correction or projection method on staggered unstructured hybrid meshes. An intermediate velocity field is first obtained by solving the momentum equations with the matrix-free implicit cell-centered FV method. The pressure Poisson equation is solved by the node-based Galerkin FE method for an auxiliary variable. The auxiliary variable is used to update the velocity field and the pressure field. The pressure field is carefully updated by taking into account the velocity divergence field. This updating strategy can be rigorously proven to be able to eliminate the unphysical pressure boundary layer and is crucial for the correct temporal convergence rate. Our current staggered-mesh scheme is distinct from other conventional ones in that we store the velocity components at cell centers and the auxiliary variable at vertices. The fluid interface is captured by solving an advection equation for the volume fraction of one of the fluids. The same matrix-free FV method, as the one used for momentum equations, is used to solve the advection equation. We will focus on the interface sharpening strategy to minimize the smearing of the interface over time. We have developed and implemented a global mass conservation algorithm that enforces the conservation of the mass for each fluid.

An Integrated Evolutionary Algorithm for Expensive Global Optimization

We propose an integrated algorithm named low dimensional simplex evolution extension (LDSEE) for expensive global optimization in which only a very limited number of function evaluations is allowed. The new algorithm accelerates an existing global optimization, low dimensional simplex evolution (LDSE), by using radial basis function (RBF) interpolation and tabu search. Different from other expensive global optimization methods, LDSEE integrates the RBF interpolation and tabu search with the LDSE algorithm rather than just calling existing global optimization algorithms as subroutines. As a result, it can keep a good balance between the model approximation and the global search. Meanwhile it is self-contained. It does not rely on other GO algorithms and is very easy to use. Numerical results show that it is a competitive alternative for expensive global optimization.

A block SPP algorithm for multidimensional tridiagonal equations with optimal message vector length

A parallel strategy for solving multidimensional tridiagonal equations is investigated in this paper. We present in detail an improved version of single parallel partition (SPP) algorithm in conjunction with message vectorization, which aggregates several communication messages into one to reduce the communication cost. We show the resulting block SPP can achieve good speedup for a wide range of message vector length (MVL), especially when the number of grid points in the divided direction is large. Instead of only using the largest possible MVL, we adopt numerical tests and modeling analysis to determine an optimal MVL so that significant improvement in speedup can be obtained.