The purpose of this dissertation is to further previous work on coalgebras as infinite statebased transition systems and their logical characterisation with particular focus on infinite regular behaviour and branching. Finite trace semantics is well understood [DR95] for nondeterministic labelled transition systems, and has recently [Jac04, HJS06] been generalised to a coalgebraic level where monads act as branching types for instance, of nondeterministic choice. Finite trace semantics then arises through an inductive construction in the Kleisli-category of the monad. We provide a more comprehensive definition of finite trace semantics, allowing for finitary branching types in Chapter 5. In Chapter 6 we carry over the ideas behind our definition of finite trace semantics to define infinite trace semantics. Coalgebraic logics [Mos99] provide one approach to characterising states in coalgebras up to bisimilarity. Coalgebraic logics are Boolean logics with the modality r. We define the Boolean dual of r in the negation-free fragment of finitary coalgebraic logics in Chapter 7, showing that finitary coalgebraic logics are essentially negation free. Our proof is largely based on the previously established completeness of finitary coalgebraic logics [KKV08]. Finite trace semantics induces the notion of finite trace equivalence. In Chapter 8 we define coalgebraic logics for many relevant branching and transition types characterising states of coalgebras with branching up to finite trace equivalence. Under further assumptions we show that these logics are expressive. Coalgebra automata allow us to state finitary properties over infinite structures essentially by a fix-point style construction. We use the dualisation of r from Chapter 7 to prove that coalgebra automata are closed under complementation in Chapter 10. This result completes a Rabin style [Rab69] correspondence between finitary coalgebraic logics and coalgebra automata for finitary transition types, begun in [Ven04, KV05]. The semantics of coalgebra automata is given in terms of parity graph games [GTW02]. In Chapter 9 we show how to structure parity graph games into rounds using the notion of players power [vB02] and how to normalise the interaction pattern between the players per round. From the latter we obtain the coinductive principle of game bisimulation. Languages accepted by coalgebra automata are called regular. Regularity is commonly [Sip96, HMU03] disproved using the pumping lemma for regular languages. We define regular languages of coalgebras and prove a pumping lemma for these languages in Chapter 11.

Recently CMOS sensors have been greatly improved, and various smart sensors, which include processing units inside the chip, have been reported. Although a number of methods for motion detection are reported in the literature, little attention has been paid to tracking sensors. Many motion detection sensors have been reported, and sometimes motion detection and motion object tracking are regarded as equivalent, since they typically use the same algorithm at the front end. However they are not the same. Tracking means tracing the progress of objects as they move about in a visual scene. The target must be followed continuously for a long time. On the other hand motion detectors only output instantaneous target movement. There are two main problems in the existing design of tracking sensors. Firstly they cannot handle complex target images, therefore simple features are used as the target for some sensors, even though the target does not always have those features in the real-world. Usually those sensors only track simple features such as edges or bright points. Secondly the precision of tracking is quite poor due to their circuit techniques. So although they perform well on synthetic data, performance is poor on real-world images. This thesis investigates how to realize a single chip tracking sensor which can deal with complex real-world object. A survey of existing tracking algorithms, which can be implemented on silicon is presented. A computation directed algorithm, which is known as BMA (Block Matching Algorithm) has been adopted and modified. This algorithm can deal not only with edges but also with more ambiguous features, and a performance of the algorithm is tested with real-world images. Hybrid circuits consisting sensors, analogue and digital circuits have been developed, and high precision tracking circuits are presented. The circuits, which incorporate <i>64x64 </i>Active Pixel Sensors, parallel analogue memory and a Switched Capacitor parallel processing unit, are implemented on a single chip and fabricated. The circuits have been tested electrically, and total chip performance has been examined with test bed for tracking. Finally ideas for future improvements are presented. These are actually possible with current CMOS technology.

This thesis investigates the use of System-On-Chip technology as the basis for a low cost Automatic Optical Inspection system. Novel object recognition and image registration algorithms are developed and targeted for a System-On-Chip platform. Execution time analysis of the novel algorithms is performed. This analysis shows that the application's performance criteria can be met through enhancing the platform using a Digital Signal Processor. Fast and accurate object recognition is an important class of algorithms for inspection systems. This thesis shows that techniques based on the Hough Transform are too computationally expensive for the recognition of Integrated Circuits. The thesis presents a novel low complexity technique based on Region Growing which is robust and efficient for complex images. Effective and efficient image registration is a fundamental task in inspection systems. This thesis presents a new approach to detecting placement errors of Integrated Circuits. The approach is based on the use of a Genetic Algorithm to derive transformations for matching a captured image to a reference image. This thesis presents execution time studies of the novel algorithms on an enhanced target platform. The image registration system is partitioned across the enhanced platform. The Digital Signal Processor executes the fitness function of the Genetic Algorithm. The rest of the algorithm runs on the System-On-Chip platform. The techniques developed in this work can be used to detect further types of faults on test samples such as placement errors of resistors and capacitors. The work therefore forms the basis of a high functionality low cost Automatic Optical Inspection system.

We investigate whether the Pi-calculus is able to serve as a good foundation for the design and implementation of a strongly-typed concurrent programming language. The first half of the dissertation examines whether the Pi-calculus supports a simple type system which is flexible enough to provide a suitable foundation for the type system of a concurrent programming language. The second half of the dissertation considers how to implement the Pi-calculus efficiently, starting with an abstract machine for Pi-calculus and finally presenting a compilation of Pi-calculus to C. We start the dissertation by presenting a simple, structural type system for Pi-calculus, and then, after proving the soundness of our type system, show how to infer principal types for Pi-terms. This simple type system can be extended to include useful type-theoretic constructions such as recursive types and higher-order polymorphism. Higher-order polymorphism is important, since it gives us the ability to implement abstract datatypes in a type-safe manner, thereby providing a greater degree of modularity for Pi-calculus programs. The functional computational paradigm plays an important part in many programming languages. It is well-known that the Pi-calculus can encode functional computation. We go further and show that the type structure of lambda-terms is preserved by such encodings, in the sense that we can relate the type of a lambda-term to the type of its encoding in the Pi-calculus. This means that a Pi-calculus programming language can genuinely support typed functional programming as a special case. An efficient implementation of Pi-calculus is necessary if we wish to consider Pi-calculus as an operational foundation for concurrent programming. We first give a simple abstract machine for Pi-calculus and prove it correct. We then show how this abstract machine inspires a simple, but efficient, compilation of Pi-calculus to C (which now forms the basis of the Pict programming language implementation).

Virtual hardware exploits the dynamic reconfigurability of Field Programmable Gate Arrays (FPGAs), but is currently limited by the delay properties of synchronous FPGA architectures. Synchronous circuits are difficult to manipulate dynamically, since this alters their internal delays. The speed-independent properties of self-timed circuits overcome this problem, thus allowing the full benefits of dynamic reconfiguration to be exploited. The general properties of self-timed systems, such as modularity, low-power and data-dependent delays also provide benefits to less dynamic FPGA systems as well. This thesis introduces a model for self-timed FPGA architectures called STACC (Self-timed Array of Configurable Cells). STACC architectures replace the global clock of an FPGA with an array of timing cells that provide local self-timed control to a region of logic blocks. STACC differs from previous self-timed FPGA architectures in that it does not disrupt the structure of the logic blocks. The STACC model is used to produced a self-timed version of the Xilinx XC6200. Example circuits for the self-timed XC6200 demonstrate the benefits of self-timing for implementing virtual hardware systems. Evaluation of the architecture shows that the implementation overhead of the timing array is reasonable, and that the self-timed XC6200 has the potential to out-perform the synchronous XC6200 through the use of data dependent delays.

This thesis sets out to realize an embedded synthesisable domain specific reconfigurable core for DWT algorithms and investigates whether optimizing at both algorithmic and architecture level will yield a high performance hardware. A novel implementation scheme for the realization of a low power JPEG-2000 lifting based DWT is proposed and presented in this thesis. The scheme targets to reduce the switched capacitance by reducing the number of computational steps and data-path/arithmetic hardware through the manipulation of configurable logic blocks and interconnects. These resulted in a novel DWT specific reconfigurable architecture that is more efficient than a generic reconfigurable core. The thesis also investigates single event effects on the proposed reconfigurable core. The research resulted in a number of single event upset (SEU) mitigation schemes for the proposed core. The thesis introduces a novel approach to eradicate single event disruptions in sequential and configurable bit storage circuits. Two novel SEU mitigation schemes for combinational circuits are proposed through this thesis. These are based on partial triple modular redundancy and on dual hardware redundancy with comparisons. The proposed schemes are implemented n the proposed reconfigurable core and evaluated in terms of performance overheads and the results proved the efficacy of the proposed approaches over already in use mitigation schemes.

Advanced VLSI/ULSI technologies have made it possible to realise parallelism and pipelining processing principles at affordable cost. One of the consequences is that more and more algorithms are now directly implemented in hardware. The configurable hardware algorithm approach has the potential to combine the performance of hardware algorithms and the flexibility of software algorithms at the user level. On the other hand, system timing design problems become one of the determining factors on design complexity, correct system function and high performance. This timing problem plays an even more important role in configurable systems. There are two typical system timing control design approaches, the synchronous timing design and the asynchronous timing design. This thesis investigates and demonstrates the idea and feasibility of applying asynchronous timing control at the system level and synchronous timing control to system composition modules, namely a Globally Asynchronous Locally Synchronous (GALS) design approach, for very large scale configurable hardware algorithms. A systematic approach has been adopted in this thesis to develop a configurable GALS array architecture. With the analysis of general algorithmic properties, a novel multiple threads computation model consisting of an architecture with a pool of programmable hardware operators having configurable interconnections and a GALS system timing control structure is first established. The multiple threads computation model bridges algorithms and the architecture for efficient algorithm embeddings. The GALS timing control makes this threads model practical. A novel and fast event-driven GALS data transfer interface is developed upon which a bit-serial configurable GALS array system for algorithm embeddings is designed. Some good average performance results are obtained with a polynomial evaluation algorithm embedded as a frame buffer. The work on the GALS system timing design principle can be easily extended to the design of general GALS systems.

No description available.

In order for parallel architectures to be of significant use in providing superior performance to uniprocessors, the benefits of splitting the workload among several processing elements must outweigh the overheads associated with this "divide and conquer" strategy. Whether or not this is the case depends on the nature of the algorithm and on the cost:performance functions associated with the real computer hardware available at a given time. This thesis is an investigation into the tradeoff of <I>grain</I> of hardware versus <I>speed</I> of hardware, in an attempt to show how the optimal hardware parallelism can be assessed. A model is developed of the execution time <I>T</I> of an algorithm on a machine as a function of the number of nodes, <I>N.</I> The model is used to examine the degree to which it is possible to obtain an optimal value of <I>N</I>, corresponding to minimum execution time. Specifically, the optimization is investigated assuming a particular base architecture, an algorithm or class thereof and an overall hardware cost. Two base architectures and algorithm types are considered, corresponding to two common classes of parallel architectures: a shared memory multi-processor and a message-passing multi-computer. The former is represented by a simple shared-bus multi-processor in which each processing element performs operations on data stored in a global shared store. The second type is represented by a two-dimensional mesh-connected multi-connected multi-computer. In this type of system all memory is considered private and data sharing is carried out using "messages" explicitly passed among the processing elements.

The Radial Basis Function (RBF) neural network architecture is a powerful computing paradigm that can solve complex classification, recognition and prediction problems. Although the RBF is similar in structure to the ubiquitous Multilayer Perceptron (MLP) neural architecture, it operates in a different way. This thesis discusses the issues addressed, and the findings from, a project that involved implementing a Radial Basis Function neural network in analogue CMOS VLSI. The developed hardware exploits the pulse width modulation (PWM) neural method, which allows compact, low power hardware to be realised through a combination of analogue and digital VLSI techniques. Novel pulsed circuits were designed and developed, fabricated and tested in pursuit of a fully functioning RBF demonstrator chip. The theory underpinning the designs is discussed and measured hardware results from two test chips are presented along with an assessment of circuit performance. Although the circuits generally functioned as required, discrepancies between the actual and theoretical operation were observed. Thus suggested improvements to the original designs are made and the circuit and system level considerations for the final demonstrator chip are discussed. Measured results are presented from the final demonstrator chip, confirming the correct operation of its constituent circuits, along with results from experiments showing that, when modelled in software, the developed circuitry is capable of performing as well as an identically trained RBF with Gaussian non-linearities. However, further results indicated that the expected network performance would degrade when the neural parameters are quantised. Hardware experiments with the demonstrator chip indicated that it could be used as an RBF classifier, but its performance degraded for more complex problems. A summary of the probable reasons for the performance degradation is provided.