A generational scheme for partitioning graphs

Graph partitioning divides a graph into several pieces by cutting edges. Very effective heuristic partitioning algorithms have been developed which run in real-time, but it is unknown how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. Distinctive features are the transmission and modification of whole subdomains (the partitioned units) that act as genes, and the use of a multilevel heuristic algorithm to effect the crossover and mutations. Its effectiveness is demonstrated by improvements on previously established benchmarks.

A combined evolutionary search and multilevel optimisation approach to graph-partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.

Effects of thermal cycling profiles on the performance of chip-on-flex assembly using anisotropic conductive films

Anisotropic conductive films (ACFs) are widely used in the electronic packaging industries because of their fine pitch potential and the assembly process is simpler compared to the soldering process. However, there are still unsolved issues in the volume productions using ACFs. The main reason is that the effects of many factors on the interconnects are not well understood. This work focuses on the performance of ACF-bonded chip-on-flex assemblies subjected to a range of thermal cycling test conditions. Both experimental and three-dimensional finite element computer modelling methods are used. It has been revealed that greater temperature ranges and longer dwell-times give rise to higher stresses in the ACF interconnects. Higher stresses are concentrated along the edges of the chip-ACF interfaces. In the experiments, the results show that higher temperature ranges and prolonged dwell times increase contact resistance values. Close examination of the microstructures along the bond-line through the scanning electron microscope (SEM) indicates that cyclic thermal loads disjoint the conductive particles from the bump of the chip and/or pad of the substrate and this is thought to be related to the increase of the contact resistance value and the failure of the ACF joints.

Failure mechanisms of ACF joints under isothermal ageing

The possible failure mechanisms of anisotropic conductive film (ACF) joints under isothermal ageing conditions have been identified through experiments. It has been found that ACF joints formed at higher bonding temperatures can prevent increases in the contact resistance for any ageing temperature. The higher the ageing temperature the higher the electrical failure rate is. The formation of conduction gaps between the conductive particles and the pads and damages to the metal coatings of the particle have been identified as the reasons behind the electrical failures during ageing. In order to understand the mechanism for the formation of the conduction gap and damages in metal coatings during the isothermal ageing, computer modelling has been carried out and the results are discussed extensively. The computer analysis shows that stresses concentrate at the edges of the particle–pad interface, where the adhesive matrix meets the particle. This could lead to subsequent damages and reductions in the adhesion strength in that region and it is possible for the conductive particle to be detached from the pad and the adhesive matrix. It is believed that because of this a conduction gap appears. Furthermore, under thermal loading the thermal expansion of the adhesive matrix squeezes the conductive particle and damages the metal coatings. Experimental evidences support this computational finding. It is, therefore, postulated that if an ACF-based electronic component operates in a high temperature aging condition, its electrical and mechanical functionalities will be at risk.

Evaluating the process of borosilicate glass capillaries used for fabrication of in-vitro fertilization (IVF) micro-pipettes

In this paper we investigate a number of gas flames for fire polishing borosilicate glass capillaries used in the manufacturing of IVF micro-pipettes. Hydrofluoric acid (HF) was also used as an alternative to finish the pipette end. Glass micro tools in the IVF industry are drawn from hollow glass capillaries of diameter 1 mm. These capillaries are cut manually to a length of 100 mm from hollow glass rods resulting in sharp and chipped edges. These capillaries are held in a customised holder having padding of soft silicone or rubber. Sharp and uneven edges of these capillaries pick up particles of rubber or soft silicone shavings, rendering them ineffective for IVF treatments. The working range of borosilicate glass is 800-1,200 degrees C. The experiments involved analysis of fire polishing process for borosilicate glass capillaries using candle, butane, propane, 2350 butane propane, oxyacetylene gas flames, finding the optimum distance of the capillary relative to the flame, optimum time for which the capillary should be held in the flame and optimum region of the flame which gives the required temperature range. The results show that 2350 butane propane gas mix is optimum for fire polishing of borosilicate glass capillaries. The paper is concluded by comparing the results of fire polishing with the results of acid polishing, in which HF of 1.6% concentration is used to etch the ends of the borosilicate glass pipettes.