Many industrial problems in various fields, such as logistics, process management, orproduct design, can be formalized and expressed as optimization problems in order tomake them solvable by optimization algorithms. However, solvers that guarantee thefinding of optimal solutions (complete) can in practice be unacceptably slow. Thisis one of the reasons why approximative (incomplete) algorithms, producing near-optimal solutions under restrictions (most dominant time), are of vital importance. Those approximative algorithms go under the umbrella term metaheuristics, each of which is more or less suitable for particular optimization problems. These algorithmsare flexible solvers that only require a representation for solutions and an evaluation function when searching the solution space for optimality.What all metaheuristics have in common is that their search is guided by certain control parameters. These parameters have to be manually set by the user andare generally problem and interdependent: A setting producing near-optimal resultsfor one problem is likely to perform worse for another. Automating the parameter setting process in a sophisticated, computationally cheap, and statistically reliable way is challenging and a significant amount of attention in the artificial intelligence and operational research communities. This activity has not yet produced any major breakthroughs concerning the utilization of problem instance knowledge or the employment of dynamic algorithm configuration. The thesis promotes automated parameter optimization with reference to the inverse impact of problem instance diversity on the quality of parameter settings with respect to instance-algorithm pairs. It further emphasizes the similarities between static and dynamic algorithm configuration and related problems in order to show how they relate to each other. It further proposes two frameworks for instance-based algorithm configuration and evaluates the experimental results. The first is a recommender system for static configurations, combining experimental design and machine learning. The second framework can be used for static or dynamic configuration,taking advantage of the iterative nature of population-based algorithms, which is a very important sub-class of metaheuristics. A straightforward implementation of framework one did not result in the expected improvements, supposedly because of pre-stabilization issues. The second approach shows competitive results in the scenario when compared to a state-of-the-art model-free configurator, reducing the training time by in excess of two orders of magnitude.

No description available.

A Control Data Flow Graph (CDFG) is a Directed Acyclic Graph (DAG) in which a node can be either an operation node or a control node. The target of this kind of graph is to capture allt he control and data flow information of the original hardware description while preserving the various dependencies. This kind of graph is generated by Novel Generator of Accelerators and Processors (NoGap), a design automation tool for Application Specific Instruction-set Processor (ASIP) and accelerator design developed by Per Karlström from the Department of Electrical Engineering of Linköping University. The aim of this project is to validate the graph, check if it fulfills the requirements of its definition. If it does not, it is considered an error and the running process will be aborted. Moreover, useful information will be extracted from the graph for futute work.

Given the breadth of constraint satisfaction problems (CSPs) and the wide variety of CSP solvers, it is often very difficult to determine a priori which solving method is best suited to a problem. This work explores the use of machine learning to predict which solving method will be most effective for a given problem. We use four different problem sets to determine the CSP attributes that can be used to determine which solving method should be applied. After choosing an appropriate set of attributes, we determine how well j48 decision trees can predict which solving method to apply. Furthermore, we take a cost sensitive approach such that problem instances where there is a great difference in runtime between algorithms are emphasized. We also attempt to use information gained on one class of problems to inform decisions about a second class of problems. Finally, we show that the additional costs of deciding which method to apply are outweighed by the time savings compared to applying the same solving method to all problem instances.

As the field programmable gate array (FPGA) industry grows device capacity with Moore's law and expands its market to high performance computing, scalability of its key CAD algorithms emerges as a new priority to deliver a user experience competitive to parallel processors. Among the many walls to overcome, placement stands out due to its critical impact on both frontend synthesis and backend routing. To construct a scalable placement flow, we present three innovations in detailed placement: a legalizer that works well under low whitespace; a wirelength optimizer based on bipartite matching; and a cache-aware annealer. When applied to the hundred-thousand cell IBM benchmark suite, our detailed placer can achieve 27% better wirelength and 8X faster runtime against FastDP, the fastest academic detailed placer reported, and our full placement flow can achieve 101X faster runtime, with 5% wirelength overhead, against VPR, the de facto standard in FPGA placements.

ABSTRACT Due to the rapid progress in the field of VLSI, improvements in speed, power and area are quite evident. Research and development in this field are motivated by growing markets of portable mobile devices such as personal multimedia players, cellular phones, digital camcorders and digital cameras. Among the recently popular logic families, pass transistor logic is promising for low power applications as compared to conventional static CMOS because of lower transistor count. This thesis proposes four novel designs for Booth encoder and selector logic using pass logic principles. These new designs are implemented and used to build a 64 x 64-bit multiplier. The proposed Booth encoder and selector logic are competitive with the existing and shows substantial reduction in transistor count. It also shows improvements in delay when compared to two of the three published works.

As the field programmable gate array (FPGA) industry grows device capacity with Moore's law and expands its market to high performance computing, scalability of its key CAD algorithms emerges as a new priority to deliver a user experience competitive to parallel processors. Among the many walls to overcome, placement stands out due to its critical impact on both frontend synthesis and backend routing. To construct a scalable placement flow, we present three innovations in detailed placement: a legalizer that works well under low whitespace; a wirelength optimizer based on bipartite matching; and a cache-aware annealer. When applied to the hundred-thousand cell IBM benchmark suite, our detailed placer can achieve 27% better wirelength and 8X faster runtime against FastDP, the fastest academic detailed placer reported, and our full placement flow can achieve 101X faster runtime, with 5% wirelength overhead, against VPR, the de facto standard in FPGA placements.

Tandem mass spectrometry, also known as MS/MS, is an analytical technique to measure the mass-to-charge ratio of charged ions and widely used in genomics, proteomics and metabolomics areas. There are two types of automatic ways to interpret tandem mass spectra: de novo methods and database searching methods. Both of them need to use massive computational resources and complicated comparison algorithms. The real-time peptide-spectrum matching (RT-PSM) algorithm is a database searching method to interpret tandem mass spectra with strict time constraints. Restricted by the hardware and architecture of an individual workstation the RT-PSM algorithm has to sacrifice the level of accuracy in order to provide prerequisite processing speed. The peptide-spectrum similarity scoring module is the most time-consuming part out of four modules in the RT-PSM algorithm, which is also the core of the algorithm. In this study, a multi-core computing algorithm is developed for individual workstations. Moreover, a distributed computing algorithm is designed for a cluster. The improved algorithms can achieve the speed requirement of RT-PSM without sacrificing the accuracy. With some expansion, this distributed computing algorithm can also support different PSM algorithms. Simulation results show that compared with the original RT-PSM, the parallelization version achieves 25 to 34 times speed-up based on different individual workstations. A cluster with 240 CPU cores could accelerate the similarity score module 210 times compare with the single-thread similarity score module and the whole peptide identification process 85 times compare with the single-thread peptide identification process.

The Genetic Algorithm (GA) is a popular global search algorithm. Although it has been used successfully in many fields, there are still performance challenges that prevent GA’s further success. The performance challenges include: difficult to reach optimal solutions for complex problems and take a very long time to solve difficult problems. This dissertation is to research new ways to improve GA’s performance on solution quality and convergence speed. The main focus is to present the concept of shadow price and propose a two-measurement GA. The new algorithm uses the fitness value to measure solutions and shadow price to evaluate components. New shadow price Guided operators are used to achieve good measurable evolutions. Simulation results have shown that the new shadow price Guided genetic algorithm (SGA) is effective in terms of performance and efficient in terms of speed.

This project presents the development of a collision avoidance active system for cars.There is a large interest in developing avoidance system in the automotive industry since the accidents are of such nature that can be avoided if the system works as desirable e.g., in animal crossing or having the car in front stopping without the driver noticing. A control system is designed to avoid collisions by acting on the steer and brakes of a car. An algorithm is developed to optimize a fuzzy logic controller which actuates on the steer and brakes of the car. The algorithm optimizes the inputs of the car, i.e. steer and brake, to avoid the collision with the object. The optimization of the trajectory implies that the car returns to the original lane and it is the minimum time possible inthe other lane. The object is situated at different distances and the initial speed of the car also varies depending on the situations. The results are obtained by using a car model that is developed in this project in conjunction with the tyre model, [1]. Simulations show that it performs collision avoidance manoeuvres in different conditions. Furthermore, improvements of the present work are suggested that are believed to further enhance the presented algorithm.