Parallel performance in multi-physics simulation

A comprehensive simulation of solidification/melting processes requires the simultaneous representation of free surface fluid flow, heat transfer, phase change, non-linear solid mechanics and, possibly, electromagnetics together with their interactions in what is now referred to as "multi-physics" simulation. A 3D computational procedure and software tool, PHYSICA, embedding the above multi-physics models using finite volume methods on unstructured meshes (FV-UM) has been developed. Multi-physics simulations are extremely compute intensive and a strategy to parallelise such codes has, therefore, been developed. This strategy has been applied to PHYSICA and evaluated on a range of challenging multi-physics problems drawn from actual industrial cases.

A multilevel approach to the travelling salesman problem

We motivate, derive, and implement a multilevel approach to the travelling salesman problem.The resulting algorithm progressively coarsens the problem, initialises a tour, and then employs either the Lin-Kernighan (LK) or the Chained Lin-Kernighan (CLK) algorithm to refine the solution on each of the coarsened problems in reverse order.In experiments on a well-established test suite of 80 problem instances we found multilevel configurations that either improved the tour quality by over 25% as compared to the standard CLK algorithm using the same amount of execution time, or that achieved approximately the same tour quality over seven times more rapidly. Moreover, the multilevel variants seem to optimise far better the more clustered instances with which the LK and CLK algorithms have the most difficulties.

Preface [Special Issue: International Symposium on Combinatorial Optimisation (CO2000)]

Preface [Special Issue containing a selection of papers presented at the International Symposium on Combinatorial Optimisation (CO2000) held at the University of Greenwich, London, from 12-14 July 2000.

Modelling the effect of temperature on product reliability

Reliability of electronic parts is a major concern for many manufacturers, since early failures in the field can cost an enormous amount to repair - in many cases far more than the original cost of the product. A great deal of effort is expended by manufacturers to determine the failure rates for a process or the fraction of parts that will fail in a period of time. It is widely recognized that the traditional approach to reliability predictions for electronic systems are not suitable for today's products. This approach, based on statistical methods only, does not address the physics governing the failure mechanisms in electronic systems. This paper discusses virtual prototyping technologies which can predict the physics taking place and relate this to appropriate failure mechanisms. Simulation results illustrate the effect of temperature on the assembly process of an electronic package and the lifetime of a flip-chip package.

Modelling the performance of lead-Free solder interconnects for copper bumped flip-chip devices

Traditionally, before flip chips can be assembled the dies have to be attached with solder bumps. This process involves the deposition of metal layers on the Al pads on the dies and this is called the under bump metallurgy (UBM). In an alternative process, however, Copper (Cu) columns can be used to replace solder bumps and the UBM process may be omitted altogether. After the bumping process, the bumped dies can be assembled on to the printed circuit board (PCB) by using either solder or conductive adhesives. In this work, the reliability issues of flip chips with Cu column bumped dies have been studied. The flip chip lifetime associated with the solder fatigue failure has been modeled for a range of geometric parameters. The relative importance of these parameters is given and solder volume has been identified as the most important design parameter for long-term reliability. Another important problem that has been studied in this work is the dissolution of protection metals on the pad and Cu column in the reflow process. For small solder joints the amount of Cu which dissolves into the molten solder after the protection layers have worn out may significantly affect solder joint properties.

Multi-physics-multi-scale simulation and optimisation: the next generation

FEA and CFD analysis is becoming ever more complex with an emerging demand for simulation software technologies that can address ranges of problems that involve combinations of interactions amongst varying physical phenomena over a variety of time and length scales. Computation modelling of such problems requires software technologies that enable the representation of these complex suites of 'physical' interactions. This functionality requires the structuring of simulation modules for specific physical phemonmena so that the coupling can be effectiely represented. These 'multi-physics' and 'multi-scale' computations are very compute intensive and so the simulation software must operate effectively in parallel if it is to be used in this context. Of course the objective of 'multi-physics' and 'multi-scale' simulation is the optimal design of engineered systems so optimistation is an important feature of such classes of simulation. In this presentation, a multi-disciplinary approach to simulation based optimisation is described with some key examples of application to challenging engineering problems.

A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Numerical simulation of vacuum dezincing of lead alloy

Removing zinc by distillation can leave the lead bullion virtually free of zinc and also produces pure zinc crystals. Batch distillation is considered in a hemispherical kettle with water-cooled lid, under high vacuum (50 Pa or less). Sufficient zinc concentration at the evaporating surface is achieved by means of a mechanical stirrer. The numerical model is based on the multiphysics simulation package PHYSICA. The fluid flow module of the code is used to simulate the action of the stirring impeller and to determine the temperature and concentration fields throughout the liquid volume including the evaporating surface. The rate of zinc evaporation and condensation is then modelled using Langmuir’s equations. Diffusion of the zinc vapour through the residual air in the vacuum gap is also taken into account. Computed results show that the mixing is sufficient and the rate-limiting step of the process is the surface evaporation driven by the difference of the equilibrium vapour pressure and the actual partial pressure of zinc vapour. However, at higher zinc concentrations, the heat transfer through the growing zinc crystal crust towards the cold steel lid may become the limiting factor because the crystallization front may reach the melting point. The computational model can be very useful in optimising the process within its safe limits.

Scheduling three-operation jobs in a two-machine flow shop to minimize makespan

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.

An integrated approach to flow, thermal and mechanical modeling of electronics devices

The future success of many electronics companies will depend to a large extent on their ability to initiate techniques that bring schedules, performance, tests, support, production, life-cycle-costs, reliability prediction and quality control into the earliest stages of the product creation process. Earlier papers have discussed the benefits of an integrated analysis environment for system-level thermal, stress and EMC prediction. This paper focuses on developments made to the stress analysis module and presents results obtained for an SMT resistor. Lifetime predictions are made using the Coffin-Manson equation. Comparison with the creep strain energy based models of Darveaux (1997) shows the shear strain based method to underestimate the solder joint life. Conclusions are also made about the capabilities of both approaches to predict the qualitative and quantitative impact of design changes.

Finite element modelling of crack detection tests

Four non-destructive tests for determining the length of fatigue cracks within the solder joints of a 2512 surface mount resistor are investigated. The sensitivity of the tests is obtained using finite element analysis with some experimental validation. Three of the tests are mechanically based and one is thermally based. The mechanical tests all operate by applying different loads to the PCB and monitoring the strain response at the top of the resistor. The thermal test operates by applying a heat source underneath the PCB, and monitoring the temperature response at the top of the resistor. From the modelling work done, two of these tests have shown to be sensitive to cracks. Some experimental results are presented but further work is required to fully validate the simulation results.

Turbulence modelling and its impact on CFD predictions for cooling of electronic components

This paper will discuss Computational Fluid Dynamics (CFD) results from an investigation into the accuracy of several turbulence models to predict air cooling for electronic packages and systems. Also new transitional turbulence models will be proposed with emphasis on hybrid techniques that use the k-ε model at an appropriate distance away from the wall and suitable models, with wall functions, near wall regions. A major proportion of heat emitted from electronic packages can be extracted by air cooling. This flow of air throughout an electronic system and the heat extracted is highly dependent on the nature of turbulence present in the flow. The use of CFD for such investigations is fast becoming a powerful and almost essential tool for the design, development and optimization of engineering applications. However turbulence models remain a key issue when tackling such flow phenomena. The reliability of CFD analysis depends heavily on the turbulence model employed together with the wall functions implemented. In order to resolve the abrupt fluctuations experienced by the turbulent energy and other parameters located at near wall regions and shear layers a particularly fine computational mesh is necessary which inevitably increases the computer storage and run-time requirements. The PHYSICA Finite Volume code was used for this investigation. With the exception of the k-ε and k-ω models which are available as standard within PHYSICA, all other turbulence models mentioned were implemented via the source code by the authors. The LVEL, LVEL CAP, Wolfshtein, k-ε, k-ω, SST and kε/kl models are described and compared with experimental data.

Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

The effect of thermal cycle profiles on solder joint damage

The relationship between the damage caused at different thermal cycles is very important. The whole of accelerated thermal cycle testing is based on the premise that damage at one cycle is representative of damage at a different cycle. In this paper, the relative damage caused by six thermal cycle profiles are predicted using Finite Element (FE) modelling and the results validated against experiments. Both creep strain and strain energy density were used as damage indicators and creep strain was found to correlate better with experiment. The validated FE model is then used to investigate the effect of altering each of the thermal profile parameters (ramp and swell times, hot and cold temperatures). The components used for testing are surface mount resistors - 1206, 0805 and 0603. The solders investigated are eutectic SnAgCu and eutectic SnAg.

Intermetallic phase detection in lead-free solders using synchrotron X-ray diffraction

The high-intensity, high-resolution x-ray source at the European Synchrotron Radiation Facility (ESRF) has been used in x-ray diffraction (XRD) experiments to detect intermetallic compounds (IMCs) in lead-free solder bumps. The IMCs found in 95.5Sn3.8Ag0.7Cu solder bumps on Cu pads with electroplated-nickel immersion-gold (ENIG) surface finish are consistent with results based on traditional destructive methods. Moreover, after positive identification of the IMCs from the diffraction data, spatial distribution plots over the entire bump were obtained. These spatial distributions for selected intermetallic phases display the layer thickness and confirm the locations of the IMCs. For isothermally aged solder samples, results have shown that much thicker layers of IMCs have grown from the pad interface into the bulk of the solder. Additionally, the XRD technique has also been used in a temperature-resolved mode to observe the formation of IMCs, in situ, during the solidification of the solder joint. The results demonstrate that the XRD technique is very attractive as it allows for nondestructive investigations to be performed on expensive state-of-the-art electronic components, thereby allowing new, lead-free materials to be fully characterized.