Parallel methods for optimality criteria-based topology optimization

Topology optimization problems require the repeated solution of finite element problems that are often extremely ill-conditioned due to highly heterogeneous material distributions. This makes the use of iterative linear solvers inefficient unless appropriate preconditioning is used. Even then, the solution time for topology optimization problems is typically very high. These problems are addressed by considering the use of non-overlapping domain decomposition-based parallel methods for the solution of topology optimization problems. The parallel algorithms presented here are based on the solid isotropic material with penalization (SIMP) formulation of the topology optimization problem and use the optimality criteria method for iterative optimization. We consider three parallel linear solvers to solve the equilibrium problem at each step of the iterative optimization procedure. These include two preconditioned conjugate gradient (PCG) methods: one using a diagonal preconditioner and one using an incomplete LU factorization preconditioner with a drop tolerance. A third substructuring solver that employs a hybrid of direct and iterative (PCG) techniques is also studied. This solver is found to be the most effective of the three solvers studied, both in terms of parallel efficiency and in terms of its ability to mitigate the effects of ill-conditioning. In addition to examining parallel linear solvers, we consider the parallelization of the iterative optimality criteria method. To tackle checkerboarding and mesh dependence, we propose a multi-pass filtering technique that limits the number of “ghost” elements that need to be exchanged across interprocessor boundaries.     

Multi-physics bi-directional evolutionary topology optimization on GPU-architecture

Topology optimization has proven to be viable for use in the preliminary phases of real world design problems. Ultimately, the restricting factor is the computational expense since a multitude of designs need to be considered. This is especially imperative in such fields as aerospace, automotive and biomedical, where the problems involve multiple physical models, typically fluids and structures, requiring excessive computational calculations. One possible solution to this is to implement codes on massively parallel computer architectures, such as graphics processing units (GPUs). The present work investigates the feasibility of a GPU-implemented lattice Boltzmann method for multi-physics topology optimization for the first time. Noticeable differences between the GPU implementation and a central processing unit (CPU) version of the code are observed and the challenges associated with finding feasible solutions in a computational efficient manner are discussed and solved here, for the first time on a multi-physics topology optimization problem. The main goal of this paper is to speed up the topology optimization process for multi-physics problems without restricting the design domain, or sacrificing considerable performance in the objectives. Examples are compared with both standard CPU and various levels of numerical precision GPU codes to better illustrate the advantages and disadvantages of this implementation. A structural and fluid objective topology optimization problem is solved to vary the dependence of the algorithm on the GPU, extending on the previous literature that has only considered structural objectives of non-design dependent load problems. The results of this work indicate some discrepancies between GPU and CPU implementations that have not been seen before in the literature and are imperative to the speed-up of multi-physics topology optimization algorithms using GPUs.

     

多种群并行协作的粒子群算法

针对高维复杂优化问题在求解时容易产生维数灾难导致算法极易陷入局部最优的问题,提出一种能够综合考虑高维复杂优化问题的特性,动态调整进化策略的多种群并行协作的粒子群算法。该算法在分析高维复杂问题求解过程中的粒子特点的基础上,建立融合环形拓扑、全连接形拓扑和冯诺依曼拓扑结构的粒子群算法的多种群并行协作的网络模型。该模型结合3种拓扑结构的粒子群算法在解决高维复杂优化问题时的优点,设计一种基于多群落粒子广播-反馈的动态进化策略及其进化算法,实现高维复杂优化环境中拓扑的动态适应,使算法在求解高维单峰函数和多峰函数时均具有较强的搜索能力。仿真结果表明,该算法在求解高维复杂优化问题的寻优精度和收敛速度方面均有良好的性能。     

PolyTop: a Matlab implementation of a general topology optimization framework using unstructured polygonal finite element meshes

We present an efficient Matlab code for structural topology optimization that includes a general finite element routine based on isoparametric polygonal elements which can be viewed as the extension of linear triangles and bilinear quads. The code also features a modular structure in which the analysis routine and the optimization algorithm are separated from the specific choice of topology optimization formulation. Within this framework, the finite element and sensitivity analysis routines contain no information related to the formulation and thus can be extended, developed and modified independently. We address issues pertaining to the use of unstructured meshes and arbitrary design domains in topology optimization that have received little attention in the literature. Also, as part of our examination of the topology optimization problem, we review the various steps taken in casting the optimal shape problem as a sizing optimization problem. This endeavor allows us to isolate the finite element and geometric analysis parameters and how they are related to the design variables of the discrete optimization problem. The Matlab code is explained in detail and numerical examples are presented to illustrate the capabilities of the code.     

Large-scale convex optimal control problems: time decomposition,incentive coordination, and parallel algorithm

A parallel algorithm based on time decomposition and incentive coordination is developed for long-horizon optimal control problems. This is done by first decomposing the original problem into subproblems with shorter time horizon, and then using the incentive coordination scheme to coordinate the interaction of subproblems. For strictly convex problems it is proved that the decomposed problem with linear incentive coordination is equivalent to the original problem, in the sense that each optimal solution of the decomposed problem produces one global optimal solution of the original problem and vice versa. In other words, linear incentive terms are sufficient in this case and impose no additional computation burden on the subproblems. The high-level parameter optimization problem is shown to be nonconvex, despite the uniqueness of the optimal solution and the convexity of the original problem. Nevertheless, the high-level problem has no local minimum, even though it is nonconvex. A parallel algorithm based on a prediction method is developed, and a numerical example is used to demonstrate the feasibility of the approach     

Optimal control of weakly coupled bilinear systems

The optimization of the time-invariant bilinear weakly coupled system with a quadratic performance criterion is considered. A sequence of linear state and costate equations is constructed such that the open-loop solution of the optimization problem is obtained in terms of the reduced-order subsystems. This leads to a reduction in the size of the required computations and allows parallel processing of information. The near-optimal closed-loop control is obtained in the form of a linear feedback law, with the feedback gains calculated from two reduced-order independent time-varying linear-quadratic optimal control problems.     

High resolution topology optimization using graphics processing units (GPUs)

We present a Graphics Processing Unit (GPU) implementation of the level set method for topology optimization. The solution of three-dimensional topology optimization problems with millions of elements becomes computationally tractable with this GPU implementation and NVIDIA supercomputer-grade GPUs. We demonstrate this by solving the inverse homogenization problem for the design of isotropic materials with maximized bulk modulus. We trace the maximum bulk modulus optimization results to very high porosities to demonstrate the detail achievable with a high computational resolution. By utilizing a parallel GPU implementation rather than a sequential CPU implementation, similar increases in tractable computational resolution would be expected for other topology optimization problems.     

A level-set-based topology and shape optimization method for continuum structure under geometric constraints

Recent advances in level-set-based shape and topology optimization rely on free-form implicit representations to support boundary deformations and topological changes. In practice, a continuum structure is usually designed to meet parametric shape optimization, which is formulated directly in terms of meaningful geometric design variables, but usually does not support free-form boundary and topological changes. In order to solve the disadvantage of traditional step-type structural optimization, a unified optimization method which can fulfill the structural topology, shape, and sizing optimization at the same time is presented. The unified structural optimization model is described by a parameterized level set function that applies compactly supported radial basis functions (CS-RBFs) with favorable smoothness and accuracy for interpolation. The expansion coefficients of the interpolation function are treated as the design variables, which reflect the structural performance impacts of the topology, shape, and geometric constraints. Accordingly, the original topological shape optimization problem under geometric constraint is fully transformed into a simple parameter optimization problem; in other words, the optimization contains the expansion coefficients of the interpolation function in terms of limited design variables. This parameterization transforms the difficult shape and topology optimization problems with geometric constraints into a relatively straightforward parameterized problem to which many gradient-based optimization techniques can be applied. More specifically, the extended finite element method (XFEM) is adopted to improve the accuracy of boundary resolution. At last, combined with the optimality criteria method, several numerical examples are presented to demonstrate the applicability and potential of the presented method.     

Parallel Implementations of the Selection Problem: A Case Study

The selection problem has been studied extensively on sequential machines. A linear average time solution and a linear worst-case solution are considered as the standard by most researchers. Theoretical work is also available on parallel models, but it has not been widely implemented on parallel machines. This paper presents an in-depth analysis of the implementation of the standard algorithms, on a number of multiprocessors and supercomputers from the entire spectrum of Flynn's classification, using both an imperative (C based languages with vendor specific parallel extensions) and a functional (SISAL) language. Very interesting results were obtained for all of the experiments performed, leading us to the conclusion that the selection problem has very efficient parallel implementations. Hand-tuned C programs with parallel extensions provided good efficiency but were time-consuming in terms of development. On the other hand, the SISAL code is fully portable and the same program was used on all the machines. The performances of SISAL implementations were comparable to the ones of the hand-tuned C implementations. On all the tests, the routines were able to sustain good speed-up and reasonable efficiency, even with a large number of processors. In two cases (one machine using SISAL, and one using a C-based language), we were able to obtain an efficiency higher than 80% with a configuration close or equal to the maximum number of processors.     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

Sequential integer programming methods for stress constrained topology optimization

This paper deals with topology optimization of load carrying structures defined on a discretized design domain where binary design variables are used to indicate material or void in the various finite elements. The main contribution is the development of two iterative methods which are guaranteed to find a local optimum with respect to a 1-neighbourhood. Each new iteration point is obtained as the optimal solution to an integer linear programming problem which is an approximation of the original problem at the previous iteration point. The proposed methods are quite general and can be applied to a variety of topology optimization problems defined by 0-1 design variables. Most of the presented numerical examples are devoted to problems involving stresses which can be handled in a natural way since the design variables are kept binary in the subproblems.     

Minimizing Communication Penalty of Triangular Solvers by Runtime Mesh Configuration and Workload Redistribution

In this article, we study the effects of network topology and load balancing on the performance of a new parallel algorithm for solving triangular systems of linear equations on distributed-memory message-passing multiprocessors. The proposed algorithm employs novel runtime data mapping and workload redistribution methods on a communication network which is configured as a toroidal mesh. A fully parameterized theoretical model is used to predict communication behaviors of the proposed algorithm relevant to load balancing, and the analytical performance results correctly determine the optimal dimensions of the toroidal mesh, which vary with the problem size, the number of available processors, and the hardware parameters of the machine. Further enhancement to the proposed algorithm is then achieved through redistributing the arithmetic workload at runtime. Our FORTRAN implementation of the proposed algorithm as well as its enhanced version has been tested on an Intel iPSC/2 hypercube, and the same code is also suitable for executing the algorithm on the iPSC/860 hypercube and the Intel Paragon mesh multiprocessor. The actual timing results support our theoretical findings, and they both confirm the very significant impact a network topology chosen at runtime can have on the computational load distribution, the communication behaviors and the overall performance of parallel algorithms.     

Parallel solution of contact shape optimization problems based on Total FETI domain decomposition method

An application of a variant of the parallel domain decomposition method that we call Total FETI or TFETI (Total Finite Element Tearing and Interconnecting) for the solution of contact problems of elasticity to the parallel solution of contact shape optimization problems is described. A unique feature of the TFETI algorithm is its capability to solve large contact problems with optimal, i.e., asymptotically linear complexity. We show that the algorithm is even more efficient for the solution of the contact shape optimization problems as it can exploit effectively a specific structure of the auxiliary problems arising in the semi-analytic sensitivity analysis. Thus the triangular factorizations of the stiffness matrices of the subdomains are carried out in parallel only once for each design step, the evaluation of the components of the gradient of the cost function can be carried out in parallel, and even the evaluation of each component of the gradient itself can be further parallelized using the standard TFETI scheme. Theoretical results which prove asymptotically linear complexity of the solution are reported and documented by numerical experiments. The results of numerical solution of a 3D contact shape optimization problem confirm the high degree of parallelism of the algorithm.     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。     

Interactive topology optimization on hand-held devices

This paper presents an interactive topology optimization application designed for hand-held devices running iOS or Android. The TopOpt app solves the 2D minimum compliance problem with interactive control of load and support positions as well as volume fraction. Thus, it is possible to change the problem settings on the fly and watch the design evolve to a new optimum in real time. The use of an interactive app makes it extremely simple to learn and understand the influence of load-directions, support conditions and volume fraction. The topology optimization kernel is written in C# and the graphical user interface is developed using the game engine Unity3D. The underlying code is inspired by the publicly available 88 and 99 line Matlab codes for topology optimization but does not utilize any low-level linear algebra routines such as BLAS or LAPACK. The TopOpt App can be downloaded on iOS devices from the Apple App Store, at Google Play for the Android platform, and a web-version can be run from www.topopt.dtu.dk.     

Multibody Analysis of Controlled Aeroelastic Systems on Parallel Computers

The paper describes the application of parallel techniques to amultibody multidisciplinary formulation. The problem is stated interms of a system of nonlinear Differential-Algebraic Equations(DAE). The parallel solution is obtained using a sub-structuringdomain decomposition method, that is able to exploit thecharacteristic quasi-monodimensional topology that multibodymodels usually present. The presence of explicit constraints inform of algebraic equations requires particular care in thetreatment of the related unknowns, to avoid local singularityproblems. The code has been successfully tested on differentcomputer architectures. Special attention has been dedicated toproduce a code that will efficiently work on a cluster of PCs.Results of three test problems, regarding the simulation of anonlinear beam bending and of complex aeroservomechanical systemsas an helicopter rotor and a tiltrotor aircraft, are presented.     

A parallel algorithm with enhancements via partial objective value cuts for cluster-based wireless sensor network design

In this paper, we develop a parallel algorithm for the solution of an integrated topology control and routing problem in Wireless Sensor Networks (WSNs). After presenting a mixed-integer linear optimization formulation for the problem, for its solution, we develop an effective parallel algorithm in a Master–Worker model that incorporates three parallelization strategies, namely low-level parallelism, domain decomposition, and multiple search (both cooperative and independent) in a single Master–Worker framework.     

Topology optimization of trusses with stress and local constraints on nodal stability and member intersection

A truss topology optimization problem under stress constraints is formulated as a Mixed Integer Programming (MIP) problem with variables indicating the existence of nodes and members. The local constraints on nodal stability and intersection of members are considered, and a moderately large lower bound is given for the cross-sectional area of an existing member. A lower-bound objective value is found by neglecting the compatibility conditions, where linear programming problems are successively solved based on a branch-and-bound method. An upper-bound solution is obtained as a solution of a Nonlinear Programming (NLP) problem for the topology satisfying the local constraints. It is shown in the examples that upper- and lower-bound solutions with a small gap in the objective value can be found by the branch-and-bound method, and the computational cost can be reduced by using the local constraints.     

Parallel custom instruction identification for extensible processors

With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint.