The Refinement-Tree Partition for Parallel Solution of Partial Differential Equations

Dynamic load balancing is considered in the context of adaptive multilevel methods for partial differential equations on distributed memory multiprocessors. An approach that periodically repartitions the grid is taken. The important properties of a partitioning algorithm are presented and discussed in this context. A partitioning algorithm based on the refinement tree of the adaptive grid is presented and analyzed in terms of these properties. Theoretical and numerical results are given.     

Optimal Data-Space Partitioning of Spatial Data for Parallel I/O

It is desirable to design partitioning methods that minimize the I/O time incurred during query execution in spatial databases. This paper explores optimal partitioning for two-dimensional data for a class of queries and develops multi-disk allocation techniques that maximize the degree of I/O parallelism obtained in each case. We show that hexagonal partitioning has optimal I/O performance for circular queries among all partitioning methods that use convex non-overlapping regions. An analysis and extension of this result to all possible partitioning techniques is also given. For rectangular queries, we show that hexagonal partitioning has overall better I/O performance for a general class of range queries, except for rectilinear queries, in which case rectangular grid partitioning is superior. By using current algorithms for rectangular grid partitioning, parallel storage and retrieval algorithms for hexagonal partitioning can be constructed. Some of these results carry over to circular partitioning of the data—which is an example of a non-convex region.     

Optimal Data-Space Partitioning of Spatial Data for Parallel I/O

It is desirable to design partitioning methods that minimize the I/O time incurred during query execution in spatial databases. This paper explores optimal partitioning for two-dimensional data for a class of queries and develops multi-disk allocation techniques that maximize the degree of I/O parallelism obtained in each case. We show that hexagonal partitioning has optimal I/O performance for circular queries among all partitioning methods that use convex non-overlapping regions. An analysis and extension of this result to all possible partitioning techniques is also given. For rectangular queries, we show that hexagonal partitioning has overall better I/O performance for a general class of range queries, except for rectilinear queries, in which case rectangular grid partitioning is superior. By using current algorithms for rectangular grid partitioning, parallel storage and retrieval algorithms for hexagonal partitioning can be constructed. Some of these results carry over to circular partitioning of the data—which is an example of a non-convex region.     

Test Vector Optimization Using Pocofan-Poframe Partitioning

This paper presents an automated POCOFAN-POFRAME algorithm that partitions large combinational digital VLSI circuits for pseudo exhaustive testing. In this paper, a simulation framework and partitioning technique are presented to guide VLSI circuits to work under with fewer test vectors in order to reduce testing time and to develop VLSI circuit designs. This framework utilizes two methods of partitioning Primary Output Cone Fanout Partitioning (POCOFAN) and POFRAME partitioning to determine number of test vectors in the circuit. The key role of partitioning is to identify reconvergent fanout branch pairs and the optimal value of primary input node N and fanout F partitioning using I-PIFAN algorithm. The number of reconvergent fanout and its locations are critical for testing of VLSI circuits and design for testability. Hence, their selection is crucial in order to optimize system performance and reliability. In the present work, the design constraints of the partitioned circuit considered for optimization includes critical path delay and test time. POCOFAN-POFRAME algorithm uses the parameters with optimal values of circuits maximum primary input cone size (N) and minimum fan-out value (F) to determine the number of test vectors, number of partitions and its locations. The ISCAS’85 benchmark circuits have been successfully partitioned, the test results of C499 shows 45% reduction in the test vectors and the experimental results are compared with other partitioning methods, our algorithm makes fewer test vectors.     

Experimentelle Bestimmung des ΔKeff für Ermüdungsrißfortschritt

Experimental Determination of ΔK_eff for Fatigue Crack Propagation The results of semi-empirical determinations of ΔK_eff, i.e. K_op, are compared with results obtained via COD and ?back face strain”? measurements. A basic discrepancy is noticed between both sets of results. Three experimental methods for determination of the partitioning point ?K_op”? are described. These methods rely solely on the crack propagation behaviour of fatigue crack and do not depend on any preexisting mechanical model concerning the causes for the partitioning point ?K_op”?. The results obtained with these new test methods are in good agreement with the results obtained semi-empirically. Additionally, Elber's hypothesis, that at high R-ratios ΔK_eff ΔK, was experimentally supported. Yet, the essential finding shows that closure mechanisms cannot be the causes for the existence of a partitioning point and therewith the causes for the existence of ΔK_eff.     

Automatic partitioning of unstructured meshes for the parallel solution of problems in computational mechanics

Most of the recently proposed computational methods for solving partial differential equations on multiprocessor architectures stem from the 'divide and conquer' paradigm and involve some form of domain decomposition. For those methods which also require grids of points or patches of elements, it is often necessary to explicitly partition the underlying mesh, especially when working with local memory parallel processors. In this paper, a family of cost-effective algorithms for the automatic partitioning of arbitrary two- and three-dimensional finite element and finite difference meshes is presented and discussed in view of a domain decomposed solution procedure and parallel processing. The influence of the algorithmic aspects of a solution method (implicit/explicit computations), and the architectural specifics of a multiprocessor (SIMD/MIMD, startup/transmission time), on the design of a mesh partitioning algorithm are discussed. The impact of the partitioning strategy on load balancing, operation count, operator conditioning, rate of convergence and processor mapping is also addressed. Finally, the proposed mesh decomposition algorithms are demonstrated with realistic examples of finite element, finite volume, and finite difference meshes associated with the parallel solution of solid and fluid mechanics problems on the iPSC/2 and iPSC/860 multiprocessors.     

Parallel computation of meshless methods for explicit dynamic analysis

A parallel computational implementation of modern meshless methods is presented for explicit dynamic analysis. The procedures are demonstrated by application of the Reproducing Kernel Particle Method (RKPM). Aspects of a coarse grain parallel paradigm are detailed for a Lagrangian formulation using model partitioning. Integration points are uniquely defined on separate processors and particle definitions are duplicated, as necessary, so that all support particles for each point are defined locally on the corresponding processor. Several partitioning schemes are considered and a reduced graph-based procedure is presented. Partitioning issues are discussed and procedures to accommodate essential boundary conditions in parallel are presented. Explicit MPI message passing statements are used for all communications among partitions on different processors. The effectiveness of the procedure is demonstrated by highly deformable inelastic example problems. Copyright © 2000 John Wiley & Sons, Ltd.     

A space partitioning method for facility layout problemswith shape constraints

This paper focuses on facility layout problems with shape constraints. A heuristic algorithm is developed for the problems with the objective of minimizing the sum of rectilinear distances weighted by flow amounts between the facilities. The suggested algorithm is a simulated annealing algorithm in which a solution is encoded as a matrix that has information about relative locations of the facilities on the floor. A block layout is constructed by partitioning the floor into a set of rectangular blocks according to the information while satisfying the areas of the facilities. In this paper, three methods are suggested for the partitioning procedure and they are employed in the simulated annealing algorithm. The results of computational experiments show that the proposed algorithm performs better than two existing algorithms.     

An assessment of three creep–fatigue life prediction methods for nickel‐based superalloy GH4049

High‐temperature low‐cycle fatigue tests with and without a 10‐s strain hold period in a cycle were performed on a nickel base superalloy GH4049 under a fully reversed axial total strain control mode. Three creep–fatigue life prediction methods are chosen to analyse the experimental data. These methods are the linear damage summation method (LDS), the strain range partitioning method (SRP) and the strain energy partitioning method (SEP). Their ability to predict creep‐fatigue lives of GH4049 at 700, 800 and 850 °C has been evaluated. It is found that the SEP method shows an advantage over the SRP method for all the tests under consideration. At 850 °C, the LDS and SEP methods give a more satisfactory prediction for creep–fatigue lives. At the temperatures of 700 and 800 °C, the SRP and SEP methods can correlate the life data better than the LDS method. In addition, the differences in predictive ability of these methods have also been analysed. The scanning electron microscopy (SEM) examination of fracture surfaces reveals that under creep–fatigue test conditions crack initiation mode is transgranular, while crack propagation mode is either intergranular plus transgranular or entirely intergranular, dependent on test temperature.     

两相分配生物反应器——浊点系统在生物转化中的应用

利用两相分配生物反应器可以控制底物由非水相向水相释放，增加底物的溶解度和解除底物对微生物的抑制，保护产物降解，降低下游分离费用；论述了两相分配生物反应器的基本原理和发展概况，并以胆固醇边链切除生物转化为例，介绍了新开发的浊点系统两相分配生物反应器的巨大潜力。     

DECOMPOSITION ANALYSIS AND OPTIMIZATION OF AN AUTOMOTIVE POWERTRAIN DESIGN MODEL

Decomposition methods in mathematical programming typically apply a coordination strategy based on an identifiable structure in the problem. Decomposition analysis is a rigorous method for discovering how to (i) partition an original model so that the resulting problem structure matches the one required by a general coordination strategy, and (ii) implement the most suitable such strategy. Automated partitioning has received significant attention recently but implementation of coordination strategies based on decomposition analysis is still scarce. This article presents a complete analysis for partitioning and coordinated solution of an automotive powertrain design problem. The model offers a practical approach for accommodating control and geometry variables simultaneously. A variable complexity coordination strategy is proposed and implemented.     

Multilevel Green's function interpolation method for scattering from composite metallic and dielectric objects

A multilevel Green's function interpolation method based on two kinds of multilevel partitioning schemes--the quasi-2D and the hybrid partitioning scheme--is proposed for analyzing electromagnetic scattering from objects comprising both conducting and dielectric parts. The problem is formulated using the surface integral equation for homogeneous dielectric and conducting bodies. A quasi-2D multilevel partitioning scheme is devised to improve the efficiency of the Green's function interpolation. In contrast to previous multilevel partitioning schemes, noncubic groups are introduced to discretize the whole EM structure in this quasi-2D multilevel partitioning scheme. Based on the detailed analysis of the dimension of the group in this partitioning scheme, a hybrid quasi-2D/3D multilevel partitioning scheme is proposed to effectively handle objects with fine local structures. Selection criteria for some key parameters relating to the interpolation technique are given. The proposed algorithm is ideal for the solution of problems involving objects such as missiles, microstrip antenna arrays, photonic bandgap structures, etc. Numerical examples are presented to show that CPU time is between O(N) and O(N log N) while the computer memory requirement is O(N).     

Numerical methods for analyzing the effects of uncertainties on the dynamics of periodic structures

Various approaches are proposed and compared for analysing the effects of structural irregularities and parameter uncertainties on the dynamics of finitely long, one-dimensional, mono-coupled, nearly periodic assemblies with and without structural damping. Computational concerns are raised in regard to the classical method of modal analysis, and alternative methods are formulated which allow for the numerically efficient determination of the exponential decay constant. While modal analysis and Cramer's rule require the solution of an eigenvalue problem, the matrix inversion and matrix partitioning approaches avoid costly eigenvalue computations and require only cost-effective algebraic manipulations. Therefore, implementation of either the direct inversion technique or matrix partitioning both simplifies the analysis and cuts computational costs substantially. © 1997 John Wiley & Sons, Ltd.     

Design considerations and algorithms for partitioning optoelectronic multichip modules

There is considerable interest in the development of optical interconnects for multichip modules (MCM's) to improve their performance. For effective utilization of the optical and electronic technologies, a methodology for partitioning the system is required. The key question to be answered is which technology should be used for each interconnect in a given netlist: optical or electronic. We introduce the computer-aided design approach for partitioning optoelectronic systems into optoelectronic MCM's. We first discuss the design trade-off issues in an optoelectronic system design, including speed, power dissipation, area, and diffraction limits for free-space optics. We then define a formulation for optoelectronic MCM partitioning and describe new algorithms for optimizing this partitioning based on the minimization of the power dissipation. The models for the algorithms are discussed in detail, and an example of a multistage interconnect network is given. Different results, with the number and size of chips being variable, are presented in which improvement for the system packaging has been observed when the partitioning algorithms are applied.     

A domain decomposition tool for boundary element methods

Domain decomposition boundary element methods have become increasingly popular over the last several years for a variety of reasons. In particular, these methods reduce the storage and CPU requirements, can result in sparse linear systems, are easy to parallelize, and, when used in conjunction with a dual reciprocity method, can significantly improve the conditioning of the associated linear system. Nevertheless, for complex geometries, determining an appropriate decomposition of the domain can be extremely difficult. A domain decomposition tool based on a graph partitioning algorithm is presented to automate the process and provide quality decompositions.     

蜂窝纸板结构平压性能有限元分析

研究了蜂窝纸板结构的实体建模、单元属性、网格划分等有限元建模方法,并基于该有限元模型分析了蜂窝纸板结构的平压性能,有限元分析结果与试验结果吻合良好.     

Graph partitioning strategy for the topology design of industrial network

Network topology design problem in industrial network is formulated, which is shown to be equivalent to a multi-constraint optimisation problem: the network design should minimise the amount of inter-network communication, and simultaneously balance the communication load and network size evenly over the resultant sub-networks. To solve this optimisation problem, a graph partitioning strategy is proposed, which can give a good network design by partitioning a graph- based representation of the network optimisation problem. Then, the network optimisation procedures using the graph partitioning strategy are detailed and two experimental, examples are studied. In the experiments, the network designs obtained by the graph partitioning strategy are compared with those obtained by a random partitioning method. The experimental results demonstrate the network designs obtained by the graph partitioning strategy are significantly better than those obtained by the random partitioning method.     

Exploiting semantics of temporal multi‐scale methods to optimize multi‐level mesh partitioning

Multi‐scale problems are often solved by decomposing the problem domain into multiple subdomains, solving them independently using different levels of spatial and temporal refinement, and coupling the subdomain solutions back to obtain the global solution. Most commonly, finite elements are used for spatial discretization, and finite difference time stepping is used for time integration. Given a finite element mesh for the global problem domain, the number of possible decompositions into subdomains and the possible choices for associated time steps is exponentially large, and the computational costs associated with different decompositions can vary by orders of magnitude. The problem of finding an optimal decomposition and the associated time discretization that minimizes computational costs while maintaining accuracy is nontrivial. Existing mesh partitioning tools, such as METIS, overlook the constraints posed by multi‐scale methods and lead to suboptimal partitions with a high performance penalty. We present a multi‐level mesh partitioning approach that exploits domain‐specific knowledge of multi‐scale methods to produce nearly optimal mesh partitions and associated time steps automatically. Results show that for multi‐scale problems, our approach produces decompositions that outperform those produced by state‐of‐the‐art partitioners like METIS and even those that are manually constructed by domain experts. Copyright © 2017 John Wiley & Sons, Ltd.     

Matrix partitioning methods for interior point algorithms

We consider here a linear programming problem whose rows of the constraint matrix can be partitioned into two parts. Such natural partitions exist in several special linear programs, including the assignment problem, the transportation problem, the generalized upper-bounded variable problem, the block diagonal linear program; and can also be used to induce sparsity patterns in Cholesky factorizations. In this paper, we propose a matrix partitioning method for interior point algorithms. The proposed method independently generates Cholesky factorizations of each part, and reduces the complexity to that of solving generally, a dense linear system involving several rank one updates of the identity matrix. Here, we propose solving this linear system by an inductive use of the Sherman-Morrison-Woodbury formula. The proposed method is easily implemented on a vector, parallel machine as well as on a distributed system. Such partitioning methods have been popular in the context of the simplex method, where the special structure of the basis matrix is exploited.