一种基于GPU加速的细粒度并行蚁群算法

为改善蚁群算法对大规模旅行商问题的求解性能,提出一种基于图形处理器(GPU)加速的细粒度并行蚁群算法.将并行蚁群算法求解过程转化为统一计算设备架构的线程块并行执行过程,使得蚁群算法在GPU中加速执行.实验结果表明,该算法能提高全局搜索能力,增大细粒度并行蚁群算法的蚂蚁规模,从而提高了算法的运算速度.     

一种基于粗糙集理论的快速并行属性约简算法

将并行计算的思想融入基于粗糙集理论的快速属性约简中,提出了一种基于粗糙集理论的快速并行属性约简算法.该算法在保证约简结果是Pawlak约简的情况下,将属性约简任务划分到多个处理器中同时处理,从而大大提高了属性约简的效率.仿真实验结果说明了该算法的高效性.     

基于MPI的FDTD并行算法及其优化策略

由高性能PC机通过网络互联构成的集群(COW)并行计算系统上应用基于消息传递(Message Passing)的方式实现FDTD的并行算法,获得了足够的加速比,有效地解决了传统的FDTD方法计算电大尺寸目标电磁散射问题时的不足.通过区域分割,各个子区域在边界处与其相邻的子区域进行场值的数据传递,从而实现了FDTD算法的并行化.利用并行FDTD方法研究了电磁波的介质层的散射,结果表明并行算法和串行计算结果的一致性,并有效提高计算效率.最后还给出了对算法进行通信隐藏的优化方法,进一步提高了并行计算的效率.     

Real-time inverse dynamics control of parallel manipulators using general-purpose multibody software

This work deals with the problem of computing the inverse dynamics of complex constrained mechanical systems for real-time control applications. The main goal is the control of robotic systems using model-based schemes in which the inverse model itself is obtained using a general purpose multibody software, exploiting the redundant coordinate formalism. The resulting control scheme is essentially equivalent to a classical computed torque control, commonly used in robotics applications. This work proposes to use modern general-purpose multibody software to compute the inverse dynamics of complex rigid mechanisms in an efficient way, so that it suits the requirements of realistic real-time applications as well. This task can be very difficult, since it involves a higher number of equations than the relative coordinates approach. The latter is believed to be less general, and may suffer from topology limitations. The use of specialized linear algebra solvers makes this kind of control algorithms usable in real-time for mechanism models of realistic complexity. Numerical results from the simulation of practical applications are presented, consisting in a “delta” robot and a bio-mimetic 11 degrees of freedom manipulator controlled using the same software and the same algorithm.     

Measuring robustness of computing systems

System builders are becoming increasingly interested in robust design. We believe that a methodology for generating robustness metrics will help the robust design research efforts and, in general, is an important step in the efforts to create robust computing systems. The purpose of the research in this paper is to quantify the robustness of a resource allocation, with the eventual objective of setting a standard that could easily be instantiated for a particular computing system to generate a robustness metric. The paper exposes how not considering the uncertainties can result in gross overestimation of the system capacity, and shows a method for reducing the impact of uncertainty, and even use it to our advantage if the uncertainties are correlated. We present our theoretical foundation for a robustness metric and give its instantiation for a particular system.     

Optimum design of long-span suspension bridges considering aeroelastic and kinematic constraints

Cable supported bridges are wind prone structures. Therefore, their aerodynamic behaviour must be studied in depth in order to guarantee their safe performance. In the last decades important achievements have been reached in the study of bridges under wind-induced actions. On the other hand, non-conventional design techniques such as sensitivity analysis or optimum design have not been applied although they have proved their feasibility in the automobile or aeronautic industries. The aim of this research work is to demonstrate how non-conventional design techniques can help designers when dealing with long span bridges considering their aeroelastic behaviour. In that respect, the comprehensive analytical optimum design problem formulation is presented. In the application example the optimum design of the challenging Messina Strait Bridge is carried out. The chosen initial design has been the year 2002 design proposal. Up to a 33% deck material saving has been obtained after finishing the optimization process.     

Adaptive robust posture control of a parallel manipulator driven by pneumatic muscles

Rather severe parametric uncertainties and uncertain nonlinearities exist in the dynamic modeling of a parallel manipulator driven by pneumatic muscles. Those uncertainties not only come from the time-varying friction forces and the static force modeling errors of pneumatic muscles but also from the inherent complex nonlinearities and unknown disturbances of the parallel manipulator. In this paper, a discontinuous projection-based adaptive robust control strategy is adopted to compensate for both the parametric uncertainties and uncertain nonlinearities of a three-pneumatic-muscles-driven parallel manipulator to achieve precise posture trajectory tracking control. The resulting controller effectively handles the effects of various parameter variations and the hard-to-model nonlinearities such as the friction forces of the pneumatic muscles. Simulation and experimental results are obtained to illustrate the effectiveness of the proposed adaptive robust controller.     

Parallel hyper heuristic algorithm based on reinforcement learning for the corridor allocation problem and parallel row ordering problem

Hyper heuristics is a relatively new optimisation algorithm. Numerous studies have reported that hyper heuristics are well applied in combinatorial optimisation problems. As a classic combinatorial optimisation problem, the row layout problem has not been publicly reported on applying hyper heuristics to its various sub-problems. To fill this gap, this study proposes a parallel hyper-heuristic approach based on reinforcement learning for corridor allocation problems and parallel row ordering problems. For the proposed algorithm, an outer layer parallel computing framework was constructed based on the encoding of the problem. The simulated annealing, tabu search, and variable neighbourhood algorithms were used in the algorithm as low-level heuristic operations, and Q-learning in reinforcement learning was used as a high-level strategy. A state space containing sequences and fitness values was designed. The algorithm performance was then evaluated for benchmark instances of the corridor allocation problem (37 groups) and parallel row ordering problem (80 groups). The results showed that, in most cases, the proposed algorithm provided a better solution than the best-known solutions in the literature. Finally, the meta-heuristic algorithm applied to three low-level heuristic operations is taken as three independent algorithms and compared with the proposed hyper-heuristic algorithm on four groups of parallel row ordering problem instances. The effectiveness of Q-learning in selection is illustrated by analysing the comparison results of the four algorithms and the number of calls of the three low-level heuristic operations in the proposed method.     

The optimal control approach to generalized multiprocessor scheduling

In this paper we present several new results in the theory of homogeneous multiprocessor scheduling. We start with some assumptions about the behavior of tasks, with associated precedence constraints, as processor power is applied. We assume that as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization, and task scheduling overhead, this speedup increases less than linearly with the number of processors applied. We also assume that the number of processors which can be assigned to a task is a continuous variable, with a view to exploiting continuous mathematics. The optimal scheduling problem is to determine the number of processors assigned to each task, and task sequencing, to minimize the finishing time.These assumptions allow us to recast the optimal scheduling problem in a form which can be addressed by optimal control theory. Various theorems can be proven which characterize the optimal scheduling solution. Most importantly, for the special case where the speedup function of each task isp , wherep is the amount of processing power applied to the task, we can directly solve our equations for the optimal solution. In this case, for task graphs formed from parallel and series connections, the solution can be derived by inspection. The solution can also be shown to be shortest path from the initial to the final state, as measured by anl _1/ distance metric, subject to obstacle constraints imposed by the precedence constraints.This research has been funded in part by the Advanced Research Project Agency monitored by ONR under Grant No. N00014-89-J-1489, in part by Draper Laboratory, in part by DARPA Contract No. N00014-87-K-0825, and in part by NSF Grant No. MIP-9012773. The first author is now with AT&T Bell Laboratories and the second author is with BBN Incorporated.     

Parallel algorithms for image enhancement and segmentation by region growing, with an experimental study

This paper presents efficient and portable implementations of a powerful image enhancement process, the Symmetric Neighborhood Filter (SNF), and an image segmentation technique that makes use of the SNF and a variant of the conventional connected components algorithm which we call -Connected Components. We use efficient techniques for distributing and coalescing data as well as efficient combinations of task and data parallelism. The image segmentation algorithm makes use of an efficient connected components algorithm based on a novel approach for parallel merging. The algorithms have been coded in Split-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Cray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results are consistent with the theoretical analysis (and provide the best known execution times for segmentation, even when compared with machine-specific implementations). Our test data include difficult images from the Landsat Thematic Mapper (TM) satellite data.Also affiliated with the Department of Electrical Engineering.Also affiliated with the Department of Computer Science and the Center for Automation Research.