No description available.

No description available.

No description available.

Many computer graphics applications remain in the domain of the specialist. They are typically characterized by complex user-directed tasks, often requiring proficiency in design, colour spaces, computer interaction and file management. Furthermore, the demands of this skill set are often exacerbated by an equally complex collection of image or object manipulation commands embedded in a variety of interface components. The complexity of these graphic editing tools often requires that the user possess a correspondingly high level of expertise. Concise Texture Editing is aimed at addressing the over-complexity of modern graphics tools and is based on the intuitive notion that the human user is skilled at high level decision making while the computer is proficient at rapid computation. This thesis has focused on the development of interactive editing tools for 2D texture images and has led to the development of a novel texture manipulation system that allows: •   the concise painting of a texture; •   the concise cloning of textures; •   the concise alteration of-texture element size; The system allows complex operations to be performed on images with minimal user interaction. When applied to the domain of image editing, this implies that the user can instruct the system to perform complex changes to digital images without having to specify copious amounts of detail. In order to reduce the user's workload, the inherent self-similarity of textures is assessed using wavelets and is exploited to interactively replicate editing operations globally over an image. This unique image system thereby reduces the user's workload through semi-automation, resulting in an acutely concise user interface.

The performance of a recursive data structure (RDS) increasingly depends on good data cache behaviour, which may be improved by software/hardware prefetching or by ensuring that the RDS has a good data layout. The latter is harder but more effective, and requires solving two separate problems: firstly ensuring that new RDS nodes are allocated in a good location in memory, and secondly preventing a degradation in layout when the RDS changes shape due to pointer updates. In this thesis we investigate the insertion of code into a program which attempts to move RDS nodes at runtime to prevent or reduce layout degradation. Such code affects only the performance of a program not its semantics. The body of this thesis is a thorough and systematic evaluation of three different forms of data movement. The first method adapts existing work on static RDS data layout, performing ad-hoc single node movements at a program’s pointer-update sites, which is simple to apply and effective in practice, but the performance gain may be hard to predict. The second method performs infrequent movement of larger groups of nodes, borrowing techniques from garbage collection but also embedding data movement in existing traversals of the RDS; the benefit of performing additional data movement to compact the heap is also demonstrated. The third method restores a pre-chosen layout after each RDS pointer update, a complex but effective method, which may be viewed both as an optimisation and as a method of synthesising new cache-aware RDSs. Concentrating on both maximising performance while minimising latency and extra memory usage, two fundamental RDSs are used for the investigation, representative of two common data access patterns (linear and branching).

Control of pervasive computing environments is a well-known problem. Such environments, or domains, are rich in different types of hardware and software that need to somehow interoperate almost invisibly. Realizing this harmony requires an intelligent application of domain management techniques. Our system, AutoHAN, is one such prototype system that aims to enable automation with respect to applications and resources and has used the home domain as a reference framework without loss of generality. Applications are allowed to enter a domain only after their behaviour has been formally verified not to conflict with that of other applications or to violate the pre-defined rules shaping domain behaviour. My research focuses on modelling domains and the accompanying rules in an ontology substrate. The ontology is itself expressed in first-order logic and hence enjoys classification and reasoning support. A salient feature of this system is what we call rehydration: transforming generic applications into domain-specific ones. Overall, this design allows reliable control of the domain free from unintended interactions.

Virtual machines (VMs) have enjoyed a resurgence as a way of allowing the same application program to be used across a range of computer systems. This flexibility comes from the abstraction that the VM provides over the native interface of a particular computer. However, this also means that the application is prevented from taking the features of particular physical machines into account in its implementation. This dissertation addresses the question of why, where and how it is useful, possible and practicable to provide an application with access to lower-level interfaces. It argues that many aspects of VM implementation can be devolved safely to untrusted applications and demonstrates this through a prototype which allows control over run-time compilation, object placement within the heap and thread scheduling. The proposed architecture separates these application-specific policy implementations from the application itself. This allows one application to be used with different policies on different systems and also allows naïve or premature optimizations to be removed.

Much work has been done on real time scheduling algorithms, but prototypes have made assumptions preventing their adoption in production desktop systems. In particular, they are generally incompatible with common monolithic kernel design and ubiquitous client-server architectures. Acceptance has also been poor because little attention is given to automatically managing quality of service parameters. This dissertation explores the use of soft real time scheduling on a conventionally structured platform. The approach taken is to extend an existing system, thus preserving a large, realistic application software base. The modified system is called <I>Linux-SRT.</I> Results show that soft real time scheduling is effective even on desktop systems which lack fine-grained preemptivity and response times. A basic design premise is that scheduling is separated from functionality, and this allows quality of service to be associated with any unmodified Linux application. End to end quality of service is viewed as a middleware service. Servers and IPC: Our solution makes important servers aware of their clients' Quality of Service, without needing to restructure them. Real time multi-threaded servers are supported with reserves allocated to sets of threads. Single-threaded servers such as the X window system are also addressed with a retrospective accounting mechanism. An asynchronous kernel events system ties the components together and allows servers to synchronise with other activities. Sockets between resource controlled processes provide integral peer authentication for admission control and priority inheritance. Quality of Service Management: Quality of service parameters are applied automatically to real time applications. The user may override this, but care has been taken to streamline the interface. Control and status indicators are tightly integrated with window management functions, hence avoiding cumbersome control programs.

The increasing prevalence of multicore, multiprocessor commodity hardware calls for server software architectures that are cycle-efficient on individual cores and can maximise concurrency across an entire machine. In order to achieve both ends this dissertation advocates stage architectures that put software concurrency foremost and aggressive CPU scheduling that exploits the common structure and runtime behaviour of CPU-intensive servers. For these servers user-level scheduling policies that multiplex one kernel thread per physical core can outperform those that utilise pools of worker threads per stage on CPU-intensive workloads. Boosting the hardware efficiency of severs in userspace means a single machine can handle more users without tuning, operating system modifications, or better hardware.

This dissertation introduces two novel techniques. Firstly, code in the virtualization layer, a <i>software debug assist,</i> provides hooks for debugging, such as extended breakpoint-like facilities. Secondly, the embedded code can modify the characteristics of the virtual resources provided to guests. This can be used to place additional constraints on the behaviour of the target beyond what is specified by the underlying architecture and to ensure correct operation. To demonstrate the feasibility and usefulness of these techniques, this dissertation presents the design and implementation of two prototype tools on commodity x86 machines. The first is a <i>pervasive debugger</i>, which places the debugger in the virtualization layer beneath the target application. The position of the debugger enables <i>horizontal</i> <i>debugging</i>, controlling multiple targets concurrently, and <i>vertical debugging</i>, examining the entire virtual hardware and software hierarchy. The second prototype illustrates <i>demand emulation</i>, which efficiently implements resource modifications that are only used “part-time” – the target dynamically switches between virtualization and emulation whenever the new feature is used. This is demonstrated with a system that protects against hostile network traffic using tainting. In-coming packets are untrusted, and the propagation of the data throughout the system is tracked using demand emulation. Any unsafe use of tainted data is prohibited. Demand emulation combines the speed of hardware with the flexibility of software.