Identifying sources of global contention in constraint satisfaction search

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.

Systematic delay-driven power optimisation and power-driven delay optimisation of combinational circuits

With the proliferation of mobile wireless communication and embedded systems, the energy efficiency becomes a major design constraint. The dissipated energy is often referred as the product of power dissipation and the input-output delay. Most of electronic design automation techniques focus on optimising only one of these parameters either power or delay. Industry standard design flows integrate systematic methods of optimising either area or timing while for power consumption optimisation one often employs heuristics which are characteristic to a specific design. In this work we answer three questions in our quest to provide a systematic approach to joint power and delay Optimisation. The first question of our research is: How to build a design flow which incorporates academic and industry standard design flows for power optimisation? To address this question, we use a reference design flow provided by Synopsys and integrate in this flow academic tools and methodologies. The proposed design flow is used as a platform for analysing some novel algorithms and methodologies for optimisation in the context of digital circuits. The second question we answer is: Is possible to apply a systematic approach for power optimisation in the context of combinational digital circuits? The starting point is a selection of a suitable data structure which can easily incorporate information about delay, power, area and which then allows optimisation algorithms to be applied. In particular we address the implications of a systematic power optimisation methodologies and the potential degradation of other (often conflicting) parameters such as area or the delay of implementation. Finally, the third question which this thesis attempts to answer is: Is there a systematic approach for multi-objective optimisation of delay and power? A delay-driven power and power-driven delay optimisation is proposed in order to have balanced delay and power values. This implies that each power optimisation step is not only constrained by the decrease in power but also the increase in delay. Similarly, each delay optimisation step is not only governed with the decrease in delay but also the increase in power. The goal is to obtain multi-objective optimisation of digital circuits where the two conflicting objectives are power and delay. The logic synthesis and optimisation methodology is based on AND-Inverter Graphs (AIGs) which represent the functionality of the circuit. The switching activities and arrival times of circuit nodes are annotated onto an AND-Inverter Graph under the zero and a non-zero-delay model. We introduce then several reordering rules which are applied on the AIG nodes to minimise switching power or longest path delay of the circuit at the pre-technology mapping level. The academic Electronic Design Automation (EDA) tool ABC is used for the manipulation of AND-Inverter Graphs. We have implemented various combinatorial optimisation algorithms often used in Electronic Design Automation such as Simulated Annealing and Uniform Cost Search Algorithm. Simulated Annealing (SMA) is a probabilistic meta heuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. We used SMA to probabilistically decide between moving from one optimised solution to another such that the dynamic power is optimised under given delay constraints and the delay is optimised under given power constraints. A good approximation to the global optimum solution of energy constraint is obtained. Uniform Cost Search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. We have used Uniform Cost Search Algorithm to search within the AIG network, a specific AIG node order for the reordering rules application. After the reordering rules application, the AIG network is mapped to an AIG netlist using specific library cells. Our approach combines network re-structuring, AIG nodes reordering, dynamic power and longest path delay estimation and optimisation and finally technology mapping to an AIG netlist. A set of MCNC Benchmark circuits and large combinational circuits up to 100,000 gates have been used to validate our methodology. Comparisons for power and delay optimisation are made with the best synthesis scripts used in ABC. Reduction of 23% in power and 15% in delay with minimal overhead is achieved, compared to the best known ABC results. Also, our approach is also implemented on a number of processors with combinational and sequential components and significant savings are achieved.

Integrated magnetic components for high-power high-current dc-dc converters

This thesis is focused on the design and development of an integrated magnetic (IM) structure for use in high-power high-current power converters employed in renewable energy applications. These applications require low-cost, high efficiency and high-power density magnetic components and the use of IM structures can help achieve this goal. A novel CCTT-core split-winding integrated magnetic (CCTT IM) is presented in this thesis. This IM is optimized for use in high-power dc-dc converters. The CCTT IM design is an evolution of the traditional EE-core integrated magnetic (EE IM). The CCTT IM structure uses a split-winding configuration allowing for the reduction of external leakage inductance, which is a problem for many traditional IM designs, such as the EE IM. Magnetic poles are incorporated to help shape and contain the leakage flux within the core window. These magnetic poles have the added benefit of minimizing the winding power loss due to the airgap fringing flux as they shape the fringing flux away from the split-windings. A CCTT IM reluctance model is developed which uses fringing equations to accurately predict the most probable regions of fringing flux around the pole and winding sections of the device. This helps in the development of a more accurate model as it predicts the dc and ac inductance of the component. A CCTT IM design algorithm is developed which relies heavily on the reluctance model of the CCTT IM. The design algorithm is implemented using the mathematical software tool Mathematica. This algorithm is modular in structure and allows for the quick and easy design and prototyping of the CCTT IM. The algorithm allows for the investigation of the CCTT IM boxed volume with the variation of input current ripple, for different power ranges, magnetic materials and frequencies. A high-power 72 kW CCTT IM prototype is designed and developed for use in an automotive fuelcell-based drivetrain. The CCTT IM design algorithm is initially used to design the component while 3D and 2D finite element analysis (FEA) software is used to optimize the design. Low-cost and low-power loss ferrite 3C92 is used for its construction, and when combined with a low number of turns results in a very efficient design. A paper analysis is undertaken which compares the performance of the high-power CCTT IM design with that of two discrete inductors used in a two-phase (2L) interleaved converter. The 2L option consists of two discrete inductors constructed from high dc-bias material. Both topologies are designed for the same worst-case phase current ripple conditions and this ensures a like-for-like comparison. The comparison indicates that the total magnetic component boxed volume of both converters is similar while the CCTT IM has significantly lower power loss. Experimental results for the 72 kW, (155 V dc, 465 A dc input, 420 V dc output) prototype validate the CCTT IM concept where the component is shown to be 99.7 % efficient. The high-power experimental testing was conducted at General Motors advanced technology center in Torrence, Los Angeles. Calorific testing was used to determine the power loss in the CCTT IM component. Experimental 3.8 kW results and a 3.8 kW prototype compare and contrast the ferrite CCTT IM and high dc-bias 2L concepts over the typical operating range of a fuelcell under like-for-like conditions. The CCTT IM is shown to perform better than the 2L option over the entire power range. An 8 kW ferrite CCTT IM prototype is developed for use in photovoltaic (PV) applications. The CCTT IM is used in a boost pre-regulator as part of the PV power stage. The CCTT IM is compared with an industry standard 2L converter consisting of two discrete ferrite toroidal inductors. The magnetic components are compared for the same worst-case phase current ripple and the experimental testing is conducted over the operation of a PV panel. The prototype CCTT IM allows for a 50 % reduction in total boxed volume and mass in comparison to the baseline 2L option, while showing increased efficiency.

Zinc finger nuclease gene repair as a treatment for cystinosis

Cystinosis is a multi-system autosomal recessive disorder caused by mutations and/or deletions in both alleles of CTNS, a gene encoding for the low pH dependent lysosomal cystine exporter cystinosin. Cystinosis occurs in approximately 1:200,000 newborns worldwide and is characterised by an accumulation of cystine in the lysosomes. The most severe form of the disorder is nephropathic cystinosis presenting Fanconi syndrome and leads without treatment to an end-stage renal failure before the age of ten. The only treatment available so far is cysteamine therapy, which delays disease progression by five years, but does not provide a cure for cystinosis patients. Current gene and cell based therapeutic approaches have not yet provided a suitable alternative. A potentially approach for a long-term treatment could be to generate autologous gene–modified stem cells by repairing the gene. Zinc Finger Nucleases (ZFNs) serve as a tool to increase HDR up to a 200,000-fold by introducing a double-stranded break (DSB). Thus, simple mutations in the CTNS gene could be corrected by introduction of a double-stranded break using ZFNs to boost the process of HDR with a suitable donor DNA sequence. A permanent repair of the most common lesion CTNS, a 57 kb deletion, could be achieved by ZFN-mediated HDR using a minigene CTNS promoter/cDNA construct. The thesis describes the design and testing of seven zinc finger nuclease pairs for their cleavage activity in vitro and in cellulo.. A highly sensitive assay to detect even low levels of ZFN-mediated HDR was also developed. Finally, to further investigate the role of autophagy in tissue injury in cystinotic cells an assay to monitor autophagy levels in the cells was successfully developed. This assay provides the opportunity to demonstrate functional restoration of CTNS after successful ZFN-HDR in cystinotic cells.

High-current inductors for high-power automotive DC-DC converters

This thesis is focused on the investigation of magnetic materials for high-power dcdc converters in hybrid and fuel cell vehicles and the development of an optimized high-power inductor for a multi-phase converter. The thesis introduces the power system architectures for hybrid and fuel cell vehicles. The requirements for power electronic converters are established and the dc-dc converter topologies of interest are introduced. A compact and efficient inductor is critical to reduce the overall cost, weight and volume of the dc-dc converter and optimize vehicle driving range and traction power. Firstly, materials suitable for a gapped CC-core inductor are analyzed and investigated. A novel inductor-design algorithm is developed and automated in order to compare and contrast the various magnetic materials over a range of frequencies and ripple ratios. The algorithm is developed for foil-wound inductors with gapped CC-cores in the low (10 kHz) to medium (30 kHz) frequency range and investigates the materials in a natural-convection-cooled environment. The practical effects of frequency, ripple, air-gap fringing, and thermal configuration are investigated next for the iron-based amorphous metal and 6.5 % silicon steel materials. A 2.5 kW converter is built to verify the optimum material selection and thermal configuration over the frequency range and ripple ratios of interest. Inductor size can increase in both of these laminated materials due to increased airgap fringing losses. Distributing the airgap is demonstrated to reduce the inductor losses and size but has practical limitations for iron-based amorphous metal cores. The effects of the manufacturing process are shown to degrade the iron-based amorphous metal multi-cut core loss. The experimental results also suggest that gap loss is not a significant consideration in these experiments. The predicted losses by the equation developed by Reuben Lee and cited by Colonel McLyman are significantly higher than the experimental results suggest. Iron-based amorphous metal has better preformance than 6.5 % silicon steel when a single cut core and natural-convection-cooling are used. Conduction cooling, rather than natural convection, can result in the highest power density inductor. The cooling for these laminated materials is very dependent on the direction of the lamination and the component mounting. Experimental results are produced showing the effects of lamination direction on the cooling path. A significant temperature reduction is demonstrated for conduction cooling versus natural-convection cooling. Iron-based amorphous metal and 6.5% silicon steel are competitive materials when conduction cooled. A novel inductor design algorithm is developed for foil-wound inductors with gapped CC-cores for conduction cooling of core and copper. Again, conduction cooling, rather than natural convection, is shown to reduce the size and weight of the inductor. The weight of the 6.5 % silicon steel inductor is reduced by around a factor of ten compared to natural-convection cooling due to the high thermal conductivity of the material. The conduction cooling algorithm is used to develop high-power custom inductors for use in a high power multi-phase boost converter. Finally, a high power digitally-controlled multi-phase boost converter system is designed and constructed to test the high-power inductors. The performance of the inductors is compared to the predictions used in the design process and very good correlation is achieved. The thesis results have been documented at IEEE APEC, PESC and IAS conferences in 2007 and at the IEEE EPE conference in 2008.