A generic strategy for dynamic load balancing of distributed memory parallel computational mechanics using unstructured meshes

A large class of computational problems are characterised by frequent synchronisation, and computational requirements which change as a function of time. When such a problem is solved on a message passing multiprocessor machine [5], the combination of these characteristics leads to system performance which deteriorate in time. As the communication performance of parallel hardware steadily improves so load balance becomes a dominant factor in obtaining high parallel efficiency. Performance can be improved with periodic redistribution of computational load; however, redistribution can sometimes be very costly. We study the issue of deciding when to invoke a global load re-balancing mechanism. Such a decision policy must actively weigh the costs of remapping against the performance benefits, and should be general enough to apply automatically to a wide range of computations. This paper discusses a generic strategy for Dynamic Load Balancing (DLB) in unstructured mesh computational mechanics applications. The strategy is intended to handle varying levels of load changes throughout the run. The major issues involved in a generic dynamic load balancing scheme will be investigated together with techniques to automate the implementation of a dynamic load balancing mechanism within the Computer Aided Parallelisation Tools (CAPTools) environment, which is a semi-automatic tool for parallelisation of mesh based FORTRAN codes.

Modelling continuum mechanics phenomena using three dimensional unstructured meshes on massively parallel processors

The difficulties encountered in implementing large scale CM codes on multiprocessor systems are now fairly well understood. Despite the claims of shared memory architecture manufacturers to provide effective parallelizing compilers, these have not proved to be adequate for large or complex programs. Significant programmer effort is usually required to achieve reasonable parallel efficiencies on significant numbers of processors. The paradigm of Single Program Multi Data (SPMD) domain decomposition with message passing, where each processor runs the same code on a subdomain of the problem, communicating through exchange of messages, has for some time been demonstrated to provide the required level of efficiency, scalability, and portability across both shared and distributed memory systems, without the need to re-author the code into a new language or even to support differing message passing implementations. Extension of the methods into three dimensions has been enabled through the engineering of PHYSICA, a framework for supporting 3D, unstructured mesh and continuum mechanics modeling. In PHYSICA, six inspectors are used. Part of the challenge for automation of parallelization is being able to prove the equivalence of inspectors so that they can be merged into as few as possible.

Parallel dynamic load-balancing for adaptive unstructured meshes

This chapter describes a parallel optimization technique that incorporates a distributed load-balancing algorithm and provides an extremely fast solution to the problem of load-balancing adaptive unstructured meshes. Moreover, a parallel graph contraction technique can be employed to enhance the partition quality and the resulting strategy outperforms or matches results from existing state-of-the-art static mesh partitioning algorithms. The strategy can also be applied to static partitioning problems. Dynamic procedures have been found to be much faster than static techniques, to provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data. The method employs a new iterative optimization technique that balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. The dynamic evolution of load has three major influences on possible partitioning techniques; cost, reuse, and parallelism. The unstructured mesh may be modified every few time-steps and so the load-balancing must have a low cost relative to that of the solution algorithm in between remeshing.

Dynamic load-balancing for parallel adaptive unstructured meshes

A parallel method for dynamic partitioning of unstructured meshes is described. The method employs a new iterative optimisation technique which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more quickly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Parallel partitioning of unstructured meshes

A method is outlined for optimising graph partitions which arise in mapping un- structured mesh calculations to parallel computers. The method employs a combination of iterative techniques to both evenly balance the workload and minimise the number and volume of interprocessor communications. They are designed to work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. The algorithms can also be used for dynamic load-balancing and a clustering technique can additionally be employed to speed up the whole process. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds.

DRAMA: Dynamic re-allocation of meshes for parallel finite element applications

In many areas of simulation, a crucial component for efficient numerical computations is the use of solution-driven adaptive features: locally adapted meshing or re-meshing; dynamically changing computational tasks. The full advantages of high performance computing (HPC) technology will thus only be able to be exploited when efficient parallel adaptive solvers can be realised. The resulting requirement for HPC software is for dynamic load balancing, which for many mesh-based applications means dynamic mesh re-partitioning. The DRAMA project has been initiated to address this issue, with a particular focus being the requirements of industrial Finite Element codes, but codes using Finite Volume formulations will also be able to make use of the project results.

Dynamic load balancing of distributed memory parallel computational mechanics using unstructured meshes for multi-physical modelling

As the complexity of parallel applications increase, the performance limitations resulting from computational load imbalance become dominant. Mapping the problem space to the processors in a parallel machine in a manner that balances the workload of each processors will typically reduce the run-time. In many cases the computation time required for a given calculation cannot be predetermined even at run-time and so static partition of the problem returns poor performance. For problems in which the computational load across the discretisation is dynamic and inhomogeneous, for example multi-physics problems involving fluid and solid mechanics with phase changes, the workload for a static subdomain will change over the course of a computation and cannot be estimated beforehand. For such applications the mapping of loads to process is required to change dynamically, at run-time in order to maintain reasonable efficiency. The issue of dynamic load balancing are examined in the context of PHYSICA, a three dimensional unstructured mesh multi-physics continuum mechanics computational modelling code.

Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimisation technique known as relative gain optimisation which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Relating Innovative 2D Ideas into 3D Garments in Terms of Structure, Using ‘Sculptural Form Giving’ as an Intermediate Step in Creation.

This research focuses on finding a fashion design methodology to reliably translate innovative two-dimensional ideas on paper, via a structural design sculpture, into an intermediate model. The author, both as a fashion designer and a researcher, has witnessed the issues which arise, regarding the loss of some of the initial ideas and distortion during the two-dimensional creative sketch to three-dimensional garment transfer process. Therefore, this research is concerned with fashion designers engaged in transferring a two-dimensional sketch through the method ‘sculptural form giving’. This research method applies the ideal model of conceptual sculpture, in the fashion design process, akin to those used in the disciplines of architecture. These parallel design disciplines share similar processes for realizing design ideas. Moreover, this research investigates and formalizes the processes that utilize the measurable space between the garment and the body, to help transfer garment variation and scale. In summation, this research proposition focuses on helping fashion designers to produce a creative method that helps the designer transfer their imaginative concept through intermediate modeling.

Functional alkali tantalate 2D structures for microelectronics and related applications

Alkali tantalates and niobates, including K(Ta / Nb)O3, Li(Ta / Nb)O3 and Na(Ta / Nb)O3, are a very promising ferroic family of lead-free compounds with perovskite-like structures. Their versatile properties make them potentially interesting for current and future application in microelectronics, photocatalysis, energy and biomedics. Among them potassium tantalate, KTaO3 (KTO), has been raising interest as an alternative for the well-known strontium titanate, SrTiO3 (STO). KTO is a perovskite oxide with a quantum paraelectric behaviour when electrically stimulated and a highly polarizable lattice, giving opportunity to tailor its properties via external or internal stimuli. However problems related with the fabrication of either bulk or 2D nanostructures makes KTO not yet a viable alternative to STO. Within this context and to contribute scientifically to the leverage tantalate based compounds applications, the main goals of this thesis are: i) to produce and characterise thin films of alkali tantalates by chemical solution deposition on rigid Si based substrates, at reduced temperatures to be compatible with Si technology, ii) to fulfil scientific knowledge gaps in these relevant functional materials related to their energetics and ii) to exploit alternative applications for alkali tantalates, as photocatalysis. In what concerns the synthesis attention was given to the understanding of the phase formation in potassium tantalate synthesized via distinct routes, to control the crystallization of desired perovskite structure and to avoid low temperature pyrochlore or K-deficient phases. The phase formation process in alkali tantalates is far from being deeply analysed, as in the case of Pb-containing perovskites, therefore the work was initially focused on the process-phase relationship to identify the driving forces responsible to regulate the synthesis. Comparison of phase formation paths in conventional solid-state reaction and sol-gel method was conducted. The structural analyses revealed that intermediate pyrochlore K2Ta2O6 structure is not formed at any stage of the reaction using conventional solid-state reaction. On the other hand in the solution based processes, as alkoxide-based route, the crystallization of the perovskite occurs through the intermediate pyrochlore phase; at low temperatures pyrochlore is dominant and it is transformed to perovskite at >800 °C. The kinetic analysis carried out by using Johnson-MehlAvrami-Kolmogorow model and quantitative X-ray diffraction (XRD) demonstrated that in sol-gel derived powders the crystallization occurs in two stages: i) at early stage of the reaction dominated by primary nucleation, the mechanism is phase-boundary controlled, and ii) at the second stage the low value of Avrami exponent, n ~ 0.3, does not follow any reported category, thus not permitting an easy identification of the mechanism. Then, in collaboration with Prof. Alexandra Navrotsky group from the University of California at Davis (USA), thermodynamic studies were conducted, using high temperature oxide melt solution calorimetry. The enthalpies of formation of three structures: pyrochlore, perovskite and tetragonal tungsten bronze K6Ta10.8O30 (TTB) were calculated. The enthalpies of formation from corresponding oxides, ∆Hfox, for KTaO3, KTa2.2O6 and K6Ta10.8O30 are -203.63 ± 2.84 kJ/mol, - 358.02 ± 3.74 kJ/mol, and -1252.34 ± 10.10 kJ/mol, respectively, whereas from elements, ∆Hfel, for KTaO3, KTa2.2O6 and K6Ta10.8O30 are -1408.96 ± 3.73 kJ/mol, -2790.82 ± 6.06 kJ/mol, and -13393.04 ± 31.15 kJ/mol, respectively. The possible decomposition reactions of K-deficient KTa2.2O6 pyrochlore to KTaO3 perovskite and Ta2O5 (reaction 1) or to TTB K6Ta10.8O30 and Ta2O5 (reaction 2) were proposed, and the enthalpies were calculated to be 308.79 ± 4.41 kJ/mol and 895.79 ± 8.64 kJ/mol for reaction 1 and reaction 2, respectively. The reactions are strongly endothermic, indicating that these decompositions are energetically unfavourable, since it is unlikely that any entropy term could override such a large positive enthalpy. The energetic studies prove that pyrochlore is energetically more stable phase than perovskite at low temperature. Thus, the local order of the amorphous precipitates drives the crystallization into the most favourable structure that is the pyrochlore one with similar local organization; the distance between nearest neighbours in the amorphous or short-range ordered phase is very close to that in pyrochlore. Taking into account the stoichiometric deviation in KTO system, the selection of the most appropriate fabrication / deposition technique in thin films technology is a key issue, especially concerning complex ferroelectric oxides. Chemical solution deposition has been widely reported as a processing method to growth KTO thin films, but classical alkoxide route allows to crystallize perovskite phase at temperatures >800 °C, while the temperature endurance of platinized Si wafers is ~700 °C. Therefore, alternative diol-based routes, with distinct potassium carboxylate precursors, was developed aiming to stabilize the precursor solution, to avoid using toxic solvents and to decrease the crystallization temperature of the perovskite phase. Studies on powders revealed that in the case of KTOac (solution based on potassium acetate), a mixture of perovskite and pyrochlore phases is detected at temperature as low as 450 °C, and gradual transformation into monophasic perovskite structure occurs as temperature increases up to 750 °C, however the desired monophasic KTaO3 perovskite phase is not achieved. In the case of KTOacac (solution with potassium acetylacetonate), a broad peak is detected at temperatures <650 °C, characteristic of amorphous structures, while at higher temperatures diffraction lines from pyrochlore and perovskite phases are visible and a monophasic perovskite KTaO3 is formed at >700 °C. Infrared analysis indicated that the differences are due to a strong deformation of the carbonate-based structures upon heating. A series of thin films of alkali tantalates were spin-coated onto Si-based substrates using diol-based routes. Interestingly, monophasic perovskite KTaO3 films deposited using KTOacac solution were obtained at temperature as low as 650 °C; films were annealed in rapid thermal furnace in oxygen atmosphere for 5 min with heating rate 30 °C/sec. Other compositions of the tantalum based system as LiTaO3 (LTO) and NaTaO3 (NTO), were successfully derived as well, onto Si substrates at 650 °C as well. The ferroelectric character of LTO at room temperature was proved. Some of dielectric properties of KTO could not be measured in parallel capacitor configuration due to either substrate-film or filmelectrode interfaces. Thus, further studies have to be conducted to overcome this issue. Application-oriented studies have also been conducted; two case studies: i) photocatalytic activity of alkali tantalates and niobates for decomposition of pollutant, and ii) bioactivity of alkali tantalate ferroelectric films as functional coatings for bone regeneration. Much attention has been recently paid to develop new type of photocatalytic materials, and tantalum and niobium oxide based compositions have demonstrated to be active photocatalysts for water splitting due to high potential of the conduction bands. Thus, various powders of alkali tantalates and niobates families were tested as catalysts for methylene blue degradation. Results showed promising activities for some of the tested compounds, and KNbO3 is the most active among them, reaching over 50 % degradation of the dye after 7 h under UVA exposure. However further modifications of powders can improve the performance. In the context of bone regeneration, it is important to have platforms that with appropriate stimuli can support the attachment and direct the growth, proliferation and differentiation of the cells. In lieu of this here we exploited an alternative strategy for bone implants or repairs, based on charged mediating signals for bone regeneration. This strategy includes coating metallic 316L-type stainless steel (316L-SST) substrates with charged, functionalized via electrical charging or UV-light irradiation, ferroelectric LiTaO3 layers. It was demonstrated that the formation of surface calcium phosphates and protein adsorption is considerably enhanced for 316L-SST functionalized ferroelectric coatings. Our approach can be viewed as a set of guidelines for the development of platforms electrically functionalized that can stimulate tissue regeneration promoting direct integration of the implant in the host tissue by bone ingrowth and, hence contributing ultimately to reduce implant failure.

Discontinuous Galerkin Computation of the Maxwell Eigenvalues on Simplicial Meshes

This paper is concerned with the discontinuous Galerkin approximation of the Maxwell eigenproblem. After reviewing the theory developed in [5], we present a set of numerical experiments which both validate the theory, and provide further insight regarding the practical performance of discontinuous Galerkin methods, particularly in the case when non-conforming meshes, characterized by the presence of hanging nodes, are employed.

T-duality without isometry via extended gauge symmetries of 2D sigma models

Target space duality is one of the most profound properties of string theory. However it customarily requires that the background fields satisfy certain invariance conditions in order to perform it consistently; for instance the vector fields along the directions that T-duality is performed have to generate isometries. In the present paper we examine in detail the possibility to perform T-duality along non-isometric directions. In particular, based on a recent work of Kotov and Strobl, we study gauged 2D sigma models where gauge invariance for an extended set of gauge transformations imposes weaker constraints than in the standard case, notably the corresponding vector fields are not Killing. This formulation enables us to follow a procedure analogous to the derivation of the Buscher rules and obtain two dual models, by integrating out once the Lagrange multipliers and once the gauge fields. We show that this construction indeed works in non-trivial cases by examining an explicit class of examples based on step 2 nilmanifolds.

Hierarchically grouped 2D local features applied to edge contour localisation

One of the most significant research topics in computer vision is object detection. Most of the reported object detection results localise the detected object within a bounding box, but do not explicitly label the edge contours of the object. Since object contours provide a fundamental diagnostic of object shape, some researchers have initiated work on linear contour feature representations for object detection and localisation. However, linear contour feature-based localisation is highly dependent on the performance of linear contour detection within natural images, and this can be perturbed significantly by a cluttered background. In addition, the conventional approach to achieving rotation-invariant features is to rotate the feature receptive field to align with the local dominant orientation before computing the feature representation. Grid resampling after rotation adds extra computational cost and increases the total time consumption for computing the feature descriptor. Though it is not an expensive process if using current computers, it is appreciated that if each step of the implementation is faster to compute especially when the number of local features is increasing and the application is implemented on resource limited ”smart devices”, such as mobile phones, in real-time. Motivated by the above issues, a 2D object localisation system is proposed in this thesis that matches features of edge contour points, which is an alternative method that takes advantage of the shape information for object localisation. This is inspired by edge contour points comprising the basic components of shape contours. In addition, edge point detection is usually simpler to achieve than linear edge contour detection. Therefore, the proposed localization system could avoid the need for linear contour detection and reduce the pathological disruption from the image background. Moreover, since natural images usually comprise many more edge contour points than interest points (i.e. corner points), we also propose new methods to generate rotation-invariant local feature descriptors without pre-rotating the feature receptive field to improve the computational efficiency of the whole system. In detail, the 2D object localisation system is achieved by matching edge contour points features in a constrained search area based on the initial pose-estimate produced by a prior object detection process. The local feature descriptor obtains rotation invariance by making use of rotational symmetry of the hexagonal structure. Therefore, a set of local feature descriptors is proposed based on the hierarchically hexagonal grouping structure. Ultimately, the 2D object localisation system achieves a very promising performance based on matching the proposed features of edge contour points with the mean correct labelling rate of the edge contour points 0.8654 and the mean false labelling rate 0.0314 applied on the data from Amsterdam Library of Object Images (ALOI). Furthermore, the proposed descriptors are evaluated by comparing to the state-of-the-art descriptors and achieve competitive performances in terms of pose estimate with around half-pixel pose error.