Many optimisations in modern compilers have been traditionally based around using analysis to examine certain aspects of the code; the compiler heuristics then make a decision based on this information as to what to optimise, where to optimise and to what extent to optimise. The exact contents of these heuristics have been carefully tuned by experts, using their experience, as well as analytical tools, to produce solid performance. This work proposes an alternative approach – that of using proper statistical analysis to drive these optimisation goals instead of human intuition, through the use of machine learning. This work shows how, by using a probabilistic search of the optimisation space, we can achieve a significant speedup over the baseline compiler with the highest optimisation settings, on a number of different processor architectures. Additionally, there follows a further methodology for speeding up this search by being able to transfer our knowledge of one program to another. This thesis shows that, as is the case in many other domains, programs can be successfully represented by program features, which can then be used to gauge their similarity and thus the applicability of previously learned off-line knowledge. Employing this method, we are able to gain the same results in terms of performance, reducing the time taken by an order of magnitude. Finally, it is demonstrated how statistical analysis of programs allows us to learn additional important optimisation information, purely by examining the features alone. By incorporating this additional information into our model, we show how good results can be achieved in just one compilation. This work is tested on real hardware, for both the embedded and general purpose domain, showing its wide applicability.

Parallel computing has long been an area of research interest because exploiting parallelism in difficult problems has promised to deliver orders of magnitude speedups. Processors are now both powerful and cheap, so that systems incorporating tens, hundreds or even thousands of powerful processors need not be prohibitively expensive. The weak link in exploiting parallelism is the means of communication between the processors. Shared memory systems are fundamentally limited in the number of processors they can utilise. To achieve high levels of parallelism it is still necessary to use distributed memory and some form of interconnection network. But interconnection networks can be costly, slow, difficult to build and expand, vulnerable to faults and limited in the range of problems they can be used to solve effectively. As a result there has been extensive research into developing interconnection networks which overcome some or all of these difficulties. In this thesis it is argued that a new interconnection network, Hierarchical Cliques (HiC), and a derivative, FatHiC, possesses many desirable properties and are worthy of consideration for use in building parallel computers. A fundamental element of an interconnection network is its topology. After defining the topology of HiC, expressions are derived for the various parameters which define its underlying limits of performance and fault tolerance. A second element of an interconnection network is an addressing and routing scheme. The addressing scheme and routing algorithms of HiC are described. The flexibility of HiC is demonstrated by developing embeddings of popular, regular interconnection networks. Some embeddings into HiC suffer from high congestion, however the FatHiC network is shown to have low congestion for those embeddings. The performance of some important, regular, data parallel problems on HiC and ++ / FatHiC are determined by analysis and simulation, using the 2D-mesh as a means of comparison. But performance alone does not tell the whole story. Any parallel computer system must be cost effective. In order to analyse the cost effectiveness of HiCs an existing measure was expanded to provide a more realistic model and a more accurate means of comparison. One aim of this thesis is to demonstrate the suitability of HiC for parallel computing systems which execute irregular algorithms requiring dynamic load balancing. A new dynamic load balancing algorithm is proposed which takes advantage of the hierarchical structure of the HiC to reduce communication overheads incurred when distributing work. To demonstrate performance of an irregular problem, a novel parallel algorithm was developed to detect subgraph isomorphism from many model graphs to a single input graph. The use of the new load balancing algorithm in conjunction with the subgraph isomorphism algorithm is discussed.

When a robot performs a task in an unstructured dynamic environment, it has to account for many factors. It should not only keep the track of where it is and how it should move, but also ensure that the kinematic, dynamic and task specific limitations are observed. It is also important that the robot can effectively avoid collisions with static and moving obstacles. In the current thesis we present design and implementation of an algorithm capable to face all these challenges. The system combines principles of dynamic roadmaps and elastic roadmaps frameworks, both of which are the state-of-art approaches to motion planning problem. The suggested solution is presented in the context of a broad overview of the literature in motion planning domain focusing on methodology of sample-based and feedback planning in dynamic environments. The implemented algorithm is applied to a 7-degree-of-freedom manipulator and is demonstrated and analyzed through a variety of simulated test scenarios. The result is an extensible and future-oriented planning system that can plan and execute movement between a starting and target position while preserving task constraints and reacting to environment changes in real time.

The challenge of testing SRAM memories consists in providing realistic fault models and test solutions with minimal application time. While classical memory tests cover the static faults, they are not sufficient to cover dynamic faults which have emerged in VDSM technologies. The purpose of this thesis is implementation of a memory BIST that targets static faults as well as dynamic faults while maintaining an acceptable test time and area overhead.At first, and as a semester project, the functional fault models (FFMs) associated with state-of-the-art SRAM technologies have been studied and state-of-the-art memory testing algorithms, targeting these FFMs have been presented.Next, and as part of this master's thesis, a combination of March LR and March AB memory testing algorithms is selected and modified to support testing word-oriented memories. Furthermore, this algorithm is extended to provide support for detecting Data-Retention Faults. This algorithm is then implemented using Verilog HDL in Register-Transfer Level of abstraction.The implemented MemBIST is then evaluated with respect to area, performance and fault coverage. A bit-oriented March LR-based MemBIST, currently in use on Atmel® AVR® micro-controllers, is used as a reference for benchmarking purposes. All target fault primitives (FPs) have been implemented using behavioral Verilog HDL and simulated with both MemBISTs.Our evaluations show that our word-oriented MemBIST can provide a 500% performance advantage (due to the word-oriented execution) for 32-bit memories and at the same time has a better fault coverage compared to the reference MemBIST. The implemented algorithm can detect all static and realistic dynamic inter-word memory faults as well as most static and realistic dynamic intra-word faults. The implemented MemBIST also maintains a very small area overhead due to sharing the required registers with existing system components.Keywords: MemBIST, Built-In Self Test, Memory Testing, March Test, Fault Model, Fault Coverage, Fault Detection

Thesis (M.S. in Modeling, Virtual Environments and Simulation and M.S. in Computer Science)--Naval Postgraduate School, June 2003. / "This thesis is done in cooperation with the MOVES Institute"--Cover. Thesis advisor(s): Eugene Paulo, John Hiles. Includes bibliographical references (p. 49). Also available online.

Many complex natural and man made systems are inherently concurrent in nature, consisting of many autonomous parts that interact with each other. Cellular automata allow the concurrency and interactions of these complex systems to be modelled. Using a reconfigurable a computing platform for running cellular automata models allows the natural concurrency of digital electronics to be directly exploited by the system being modelled. This thesis investigates methods and philosophies for developing cellular automata models on a reconfigurable computing platform, the SPACE machine. Modelling and verification techniques are developed using a process algebra, Circal. These techniques allow the desired behaviour of a system to be specified and simulated. The model is then translated into a digital design, which can be verified as correct against the behavioural model using the Circal system. Three cellular automata system are used to develop the methods and philosophies. The Game of Life is used to investigate how to model and implement CA on the SPACE machine. The Philosophies and techniques that are developed for the Game of Life are used in the following systems. More complex cellular automata models of road traffic are used to further develop the modelling techniques developed in the Game a Life. A user interface, which was created for viewing the outputs from the Game a Life, is extended to allow cellular automata cells to be dynamically placed and moved about on the computing surface, allowing the user to observe and modify experiment in real time. A cellular automata based cryptography system is then used to further enhance the techniques developed, and particularly to explore the area of producing dynamically reconfigured circuits as the inputs to the system change. The thesis concludes that there are many real life complex systems, such as road traffic simulation and cryptography, which require high performs systems to run on. The methods and philosophies developed in this thesis allow CA systems to be modelled using process algebra and run directly in digital hardware, allowing the natural concurrency of the hardware to be fully exploited.

Thesis (Ph. D.)--University of Alabama at Birmingham, 2007. / Additional advisors: Dale W. Callahan, Gary J. Grimes, Ian K. Knowles, B. Earl Wells. Description based on contents viewed Feb. 13, 2009; title from PDF t.p. Includes bibliographical references (p. 139-143).

Thesis (Ph.D.)--Drexel University, 2009. / Includes abstract and vita. Includes bibliographical references (leaves 198-210).

Thesis (Ph. D.)--Electrical and Computer Engineering, Georgia Institute of Technology, 2005. / Panagiotis Manolios, Committee Member ; Douglas M. Blough, Committee Member ; Vincent John Mooney III, Committee Chair ; William D. Hunt, Committee Member ; Sung Kyu Lim, Committee Member. Vita. Includes bibliographical references.

Thesis (M.S.)--Ohio University, June, 2004. / Includes bibliographical references (p. 67-70).