Constructing H4, a Fast Depth-Size Optimal Parallel Prefix Circuit

Given n values x ₁, x ₂,...,x _n and an associative binary operation , the prefix problem is to compute x ₁x ₂x _i, 1in. Prefix circuits are combinational circuits for solving the prefix problem. For any n-input prefix circuit D with depth d and size s, if d+s=2n–2, then D is depth-size optimal. In general, a prefix circuit with a small depth is faster than one with a large depth. For prefix circuits with the same depth, a prefix circuit with a smaller fan-out occupies less area and is faster in VLSI implementation. This paper is on constructing parallel prefix circuits that are depth-size optimal with small depth and small fan-out. We construct a depth-size optimal prefix circuit H4 with fan-out 4. It has the smallest depth among all known depth-size optimal prefix circuits with a constant fan-out; furthermore, when n136, its depth is less than, or equal to, those of all known depth-size optimal prefix circuits with unlimited fan-out. A size lower bound of prefix circuits is also derived. Some properties related to depth-size optimality and size optimality are introduced; they are used to prove that H4 is depth-size optimal.     

对数字电路扇出的影响和造成困难的分析

提出一种在 Benchmark电路中存在的隐式扇出和描述实际组合电路中扇出的一种方法 .从 D传送、赋值和冗余、难测故障等方面 ,对扇出的影响造成的困难进行了分析 ,并叙述了其影响的范围和程度 .     

并行下载最优机制

建立并行下载模型,并基于这一模型,从下载节点效益的角度出发,分析并提出最优机制.这种最优机制包括最优的选择源节点集合和文件分块方案.理论分析表明,这种机制能够使下载节点代价函数最小.仿真结果说明了这种机制的有效性.     

Faster optimal parallel prefix circuits: New algorithmic construction

Parallel prefix circuits are parallel prefix algorithms on the combinational circuit model. A prefix circuit with n inputs is depth-size optimal if its depth plus size equals 2n-2. Smaller depth implies faster computation, while smaller size implies less power consumption, less VLSI area, and less cost. To be of practical use, the depth and fan-out of a depth-size optimal prefix circuit should be small. A circuit with a smaller fan-out is in general faster and occupies less VLSI area. In this paper, we present a new algorithm to design parallel prefix circuits, and construct a class of depth-size optimal parallel prefix circuits, named SU4, with fan-out 4. When n30, SU4 has the smallest depth among all known depth-size optimal prefix circuits with fan-out 4.     

平面全柔性3-DOF过驱动并联机构的最优综合

以设计全柔性多自由度过驱动并联机构为目标,研究了平面3-DOF 4RRR过驱动并联机构的最优综合问题．从一般四分支3-DOF平面并联机构出发,建立了机构的运动学模型;给出了机构的4种可能拓扑结构分类,对不同拓扑结构类型机构的运动学和力学性能进行了分析比较．建立了并联机构全工作空间操作性改善优化模型,采用遗传算法进行优化设计并给出了实例,根据优化实例的结果设计制造了平面全柔性三自由度过驱动并联机构．以上方法对其它全柔性并联机构的优化设计具有参考价值．     

Observer-Based Optimal Control of Flexible Stewart Parallel Robots

The design and simulation of two optimal control schemes for a parallel flexible link manipulator of the Stewart type is presented. The first control scheme combines a nonlinear rigid model of the flexible manipulator with a linear rigid observer, whereas the second scheme uses a nonlinear flexible manipulator model with a linear flexible observer. The majority of the results available in the literature do not address the optimal control problem through the use of observers, as it is done in this paper, for the control of parallel robots. The simulation results have shown in both cases that indeed optimal state-obscrver-based control is a good candidate for controlling parallel-link manipulators in practice. As expected, the second scheme (flexible model plus flexible observer) gives better results than the first one, achieving faster trajectory tracking. The effects of white noises, applied forces, and zero gravity environment were taken under consideration.     

Parallel Control for Optimal Tracking via Adaptive Dynamic Programming

This paper studies the problem of optimal parallel tracking control for continuous-time general nonlinear systems. Unlike existing optimal state feedback control, the control input of the optimal parallel control is introduced into the feedback system. However, due to the introduction of control input into the feedback system, the optimal state feedback control methods can not be applied directly. To address this problem, an augmented system and an augmented performance index function are proposed firstly. Thus, the general nonlinear system is transformed into an affine nonlinear system. The difference between the optimal parallel control and the optimal state feedback control is analyzed theoretically. It is proven that the optimal parallel control with the augmented performance index function can be seen as the suboptimal state feedback control with the traditional performance index function. Moreover, an adaptive dynamic programming (ADP) technique is utilized to implement the optimal parallel tracking control using a critic neural network (NN) to approximate the value function online. The stability analysis of the closed-loop system is performed using the Lyapunov theory, and the tracking error and NN weights errors are uniformly ultimately bounded (UUB). Also, the optimal parallel controller guarantees the continuity of the control input under the circumstance that there are finite jump discontinuities in the reference signals. Finally, the effectiveness of the developed optimal parallel control method is verified in two cases.      

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

A 485ps 64-Bit Parallel Adder in 0.18$\mu$m CMOS

This paper presents an optimized 64-bit parallel adder. Sparse-tree architecture enables low carry-merge fan-outs and inter-stage wiring complexity. Single-rail and semi-dynamic circuit improves operation speed. Simulation results show that the proposed adder can operate at 485ps with power of 25.6mW in 0.18μm CMOS process. It achieves the goal of higher speed and lower power.     

微分代数方程的一类并行算法

本文提出求解微分代数方程的一类并行算法,进行误差估计。对于一个模型问题进行稳定性分析,画出稳定区域。计算实例表明算法是有效的。     

A Parallel Approach Eliminates Measurement Perturbations in RLC Circuits

An RLC circuit, certain parameters of which are measured sequentially, that is, one after the other, undergoes significant perturbations that affect its dynamical behavior. By contrast, these perturbations could be eliminated when the measurements are performed in parallel, that is, when the parameters are measured simultaneously. This result confirms the existence of physical systems with the property that certain operations on them can be performed successfully in parallel but not sequentially.     

A New Approach to the Architecture Optimization of a General 3-PUU Translational Parallel Manipulator

This paper presents a new approach to the architecture optimization of a general 3-PUU translational parallel manipulator (TPM) based on the performance of a weighted sum of global dexterity index and a new performance index-space utility ratio (SUR). Both the inverse kinematics and forward kinematics solutions are derived in closed form, and the Jacobian matrix is derived analytically. The manipulator workspace is generated by a numerical searching method with the physical constraints taken into consideration. Simulation results illustrate clearly the necessity to introduce a mixed performance index using space utility ratio for architectural optimization of the manipulator, and the optimization procedure is carried out with the goal of reaching a compromise between the two indices. The analytical results are helpful in designing a general 3-PUU TPM, and the proposed design methodology can also be applied to architectural optimization for other types of parallel manipulators.     

Parallel Distance: A New Paradigm of Measurement for Parallel Driving

In this paper, a new paradigm named parallel dis-tance is presented to measure the data information in parallel driving system. As an example, the core variables in the parallel driving system are measured and evaluated in the parallel distance framework. First, the parallel driving 3.0 system included control and management platform, intelligent vehicle platform and remote-control platform is introduced. Then, Markov chain (MC) is utilized to model the transition probability matrix of control commands in these systems. Furthermore, to distinguish the control variables in artificial and physical driving conditions, different distance calculation methods are enumerated to specify the differences between the virtual and real signals. By doing this, the real system can be guided and the virtual system can be im-proved. Finally, simulation results exhibit the merits and multiple applications of the proposed parallel distance framework.      

一种新的并行归并排序算法

文章提出了一种新的并行归并排序算法。算法充分利用并行系统中各个处理机中数据排序后序列长度相等的特点,计算出归并段对中的一个元素和最后一个元素的位置,然后再从相应的位置进行归并排序。该算法可使排序后的数据分布完全达到平衡,具有较高的负载平衡性、可扩展性和排序稳定性。文章最后给出了基于PC集群的实验结果,并把该结果与PSRS算法作了比较。     

K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations

1IntroductionAlgorithmshavebeenproposedtosolvelinearrecurrencesinparallell1-13].Someofthemsupposeunlimitednumberofprocessorsbeingusedwhileothersuselimitednumberofprocessors.P-M.KoggeandH.S.Stoneproposedarecursivedou-blingalgorithmforthesolutionofageneraJclassofrecuxrenceequationsl1].Itisthefastestalgorithm(thetimeisO(log,N))whenthenumberofprocessingelemelltspiseqllaltoN.Howeveritisnotoptimalintermsofefficiency:itsspeedupisO(de),whileitsefficiencyisO(wt).TherecursivedoublingapproachcanPro…     

一种带数据整数规划的新型并行自平衡PSO算法

为有效解决标准粒子群(PSO)算法在进化后期缺乏多样性且精度不高的问题,利用多核系统及实际高校地理数据,给出一种高校数据的整数规划方法及并行自平衡PSO算法模型来并行求解高校路网问题,同时体现算法性能。将自平衡机制采用多核系统并行处理方式生成相互独立的子群体,每个子群体间并行求解,最终生成主群体最优路径即高校路网。在Visual Studio2005.NET环境下用C++编程实现仿真。实验结果表明,此算法从求解精度及计算时间两个重要方面综合改善了算法性能。     

The Optimal Design of a Planar Parallel Platform for Prescribed Machining Tasks

In this paper a general methodology is presented for determining theoptimum design of a planar parallel platform to be used in machining.The method, based on a mathematical optimization approach, is used tofind a platform design and placement such that firstly, the execution ofa prescribed task path is feasible, and secondly, the actuator forcesrequired to execute the prescribed task are minimized. The applicationof the method is illustrated for two prescribed tasks, five designvariables and a number of geometrical inequality constraints such asactuator length limits. The method succeeds in finding locally optimumand feasible platform designs for which the required task lies insidethe workspace. Two optimization algorithms are implemented and theirrespective results are compared. The first algorithm is a robust andreliable trajectory algorithm, LFOPC, which is however expensive interms of the number of required function evaluations. As the simulationsperformed here in evaluating the objective and constraint functions maybe computationally intensive, an approximation method, Dynamic-Q, isalso used to find the optimum design with greater efficiency. Theeffectiveness of this approximation approach is evaluated.     

一种求解线性方程组的SOR并行算法

逐次松弛迭代算法(SOR)是求解线性方程组的一种常用迭代算法,当系数矩阵正定时,它具有较快的收敛速度。但是,由于每个迭代步内存在数据相关,它难以实现并行计算。目前的SOR并行算法采用数据分解的方法,但由于该法并行区域过小,同步通讯代价大,并行效率低。本文提出了SOR的一种新型并行算法,该算法与传统SOR方法等价,具有相同的收敛性和迭代结果。该并行算法通过矩阵分块增大了可并行计算的区域,并引入流水线技术,利用各处理器间通讯与计算时间的重叠,获得较理想的并行加速效率。通过多核微机以及小规模集群上的数值实验证明,本文提出的SOR并行算法在求解大型稠密线性方程组时具有较好的并行效率。     

A New Approach for the Dynamic Analysis of Parallel Manipulators

A new approach for the dynamic analysis of parallel manipulators is presented in this paper. This approach is based on the principle of virtual work. The approach is firstly illustrated using a simple example, namely, a planar four-bar linkage. Then, the dynamic analysis of a spatial six-degree-of-freedom parallel manipulator with prismatic actuators (Gough–Stewart platform) is performed. Finally, a numerical example is given in order to illustrate the results. The approach proposed here can be applied to any type of planar and spatial parallel mechanism and leads to faster computational algorithms than the classical Newton–Euler approach when applied to these mechanisms.