Rule testing in scheduling applications is a complex and potentially costly business problem. This thesis reports the outcome of research undertaken to develop a system to describe and test scheduling rules against a set of scheduling data. The overall intention of the research was to reduce commercial scheduling costs by minimizing human domain expert interaction within the scheduling process. This thesis reports the outcome of research initiated following a consultancy project to develop a system to test driver schedules against the legal driving rules in force in the UK and the EU. One of the greatest challenges faced was interpreting the driving rules and translating them into the chosen programming language. This part of the project took considerable effort to complete the programming, testing and debugging processes. A potential problem then arises if the Department of Transport or the European Union alter or change the driving rules. Considerable software development is likely to be required to support the new rule set. The approach considered takes into account the need for a modular software component that can be used in not just transport scheduling systems which look at legal driving rules but may also be integrated into other systems that have the need to test temporal rules. The integration of the rule testing component into existing systems is key to making the proposed solution reusable. The research outcome proposes an alternative approach to rule definition, similar to that of RuleML, but with the addition of rule metadata to provide the ability of describing rules of a temporal nature. The rules can be serialised and deserialised between XML (eXtensible Markup Language) and objects within an object oriented environment (in this case .NET with C#), to provide a means of transmission of the rules over a communication infrastructure. The rule objects can then be compiled into an executable software library, allowing the rules to be tested more rapidly than traditional interpreted rules. Additional support functionality is also defined to provide a means of effectively integrating the rule testing engine into existing applications. Following the construction of a rule testing engine that has been designed to meet the given requirements, a series of tests were undertaken to determine the effectiveness of the proposed approach. This lead to the implementation of improvements in the caching of constructed work plans to further improve performance. Tests were also carried out into the application of the proposed solution within alternative scheduling domains and to analyse the difference in computational performance and memory usage across system architectures, software frameworks and operating systems, with the support of Mono. Future work that is expected to follow on from this thesis will likely reside in investigations into the development of graphical design tools for the creation of the rules, improvements in the work plan construction algorithm, parallelisation of elements of the process to take better advantage of multi-core processors and off-loading of the rule testing process onto dedicated or generic computational processors.

Whether software is licensed under terms which ‘close off’ or make accessible the underlying code that comprises software holds profound implications for development due to the centrality of this good to contemporary life. In the 2000s, developing countries adopted policies to promote free and open source software (F/OSS) for reasons of technological autonomy and to reduce spending on royalties for foreign produced proprietary software. However, the adoption of such policies varied across countries. Focusing upon Argentina and Brazil, two countries that reflect contrasting policy outcomes in promoting F/OSS, I explain why and how different policies came to be adopted by analysing the way in which institutions and patterns of association affected the lobbying power of advocates and opponents of F/OSS promotion. Advocates are generally weak actors, yet they might strengthen their lobbying power through embeddedness within political and state institutions which offer opportunities to mobilise resources and forge ties with political decision-makers. Opponents are generally strong, business actors, yet their lobbying power may be attenuated by weak concentration in business association, reducing their capacity to mobilise and coordinate support. In Argentina, where F/OSS advocates’ institutional embeddedness was weak and concentration in business association was strong, the government was prevented from promoting F/OSS, despite signs that it wished to do so. In Brazil, where F/OSS advocates’ institutional embeddedness was strong and concentration in business association was weak, the government promoted F/OSS despite vociferous opposition from amongst the largest firms in the world.

Audio analysis algorithms and frameworks for Music Information Retrieval (MIR) are expanding rapidly, providing new ways to discover non-trivial information from audio sources, beyond that which can be ascertained from unreliable metadata such as ID3 tags. MIR is a broad field and many aspects of the algorithms and analysis components that are used are more accurate given a larger dataset for analysis, and often require extensive computational resources. This thesis investigates if, through the use of modern distributed computing techniques, it is possible to design an MIR system that is scalable as the number of participants increases, which adheres to copyright laws and restrictions, whilst at the same time enabling access to a global database of music for MIR applications and research. A scalable platform for MIR analysis would be of benefit to the MIR and scientific community as a whole. A distributed MIR platform that encompasses the creation of MIR algorithms and workflows, their distribution, results collection and analysis, is presented in this thesis. The framework, called DART - Distributed Audio Retrieval using Triana - is designed to facilitate the submission of MIR algorithms and computational tasks against either remotely held music and audio content, or audio provided and distributed by the MIR researcher. Initially a detailed distributed DART architecture is presented, along with simulations to evaluate the validity and scalability of the architecture. The idea of a parameter sweep experiment to find the optimal parameters of the Sub-Harmonic Summation (SHS) algorithm is presented, in order to test the platform and use it to perform useful and real-world experiments that contribute new knowledge to the field. DART is tested on various pre-existing distributed computing platforms and the feasibility of creating a scalable infrastructure for workflow distribution is investigated throughout the thesis, along with the different workflow distribution platforms that could be integrated into the system. The DART parameter sweep experiments begin on a small scale, working up towards the goal of running experiments on thousands of nodes, in order to truly evaluate the scalability of the DART system. The result of this research is a functional and scalable distributed MIR research platform that is capable of performing real world MIR analysis, as demonstrated by the successful completion of several large scale SHS parameter sweep experiments across a variety of different input data - using various distribution methods - and through finding the optimal parameters of the implemented SHS algorithm. DART is shown to be highly adaptable both in terms of the distributed MIR analysis algorithm, as well as the distribution

The hybrid message passing + shared memory programming model combines two parallel programming styles within the same application in an effort to improve the performance and efficiency of parallel codes on modern multi-core clusters. This thesis presents a performance study of this model as it applies to two Molecular Dynamics (MD) applications. Both a large scale production MD code and a smaller scale example MD code have been adapted from existing message passing versions by adding shared memory parallelism to create hybrid message passing + shared memory applications. The performance of these hybrid applications has been investigated on different multi-core clusters and compared with the original pure message passing codes. This performance analysis reveals that the hybrid message passing + shared memory model provides performance improvements under some conditions, while the pure message passing model provides better performance in others. Typically, when running on small numbers of cores the pure message passing model provides better performance than the hybrid message passing + shared memory model, as hybrid performance suffers due to increased overheads from the use of shared memory constructs. However, when running on large numbers of cores the hybrid model performs better as these shared memory overheads are minimised while the pure message passing code suffers from increased communication overhead. These results depend on the interconnect used. Hybrid message passing + shared memory molecular dynamics codes are shown to exhibit different communication profiles from their pure message passing versions and this is revealed to be a large factor in the performance difference between pure message passing and hybrid message passing + shared memory codes. An extension of this result shows that the choice of interconnection fabric used in a multi-core cluster has a large impact on the performance difference between the pure message passing and the hybrid code. The factors affecting the performance of the applications have been analytically examined in an effort to describe, generalise and predict the performance of both the pure message passing and hybrid message passing + shared memory codes.

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

published_or_final_version / abstract / Computer Science / Doctoral / Doctor of Philosophy

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy

Software testing is the most widely practiced approach to assure the correctness of programs. Despite decades of research progress, software testing is still considered very resource-demanding and time-consuming. In the recent decade, the wide adoption of multithreaded programs and the service-based architecture has further aggravated the problem that we are facing. In this thesis, we study issues in software testing where resource constraints (such as time spent and memory space allocated) are important considerations, and we look for testing techniques that are significantly advanced in effectiveness and efficiency given limited quotas of resources, which we refer to as budget. Our main focus is on two types of systems: concurrent systems and service-based systems. The concurrent system is a class of computing system where programs are designed as collections of interacting and parallel computational processes. Unfortunately, concurrent programs are well known to be difficult to write and test: various concurrency bugs still exist in heavily-tested programs. To make it worse, detecting concurrency bugs is expensive, which is, for example, notorious for dynamic detection techniques that target high precision. This thesis proposes a dynamic sampling framework, CARISMA, to reduce the overhead dramatically while still largely preserving the bug detection capability. To achieve its goal, CARISMA intelligently allocates the limited budget on the computation resource through sampling. The core of CARISMA is a budget estimation and allocation framework whose correctness has been proven mathematically. Another source of cost comes from the nondeterministic nature of concurrent systems. A common practice to test concurrent system is through stress testing where a system is executed with a large number of test cases to achieve a high coverage of the execution space. Stress testing is inherently costly. To this end, it is critical that the bug detection for each execution is effective, which demands a powerful test oracle. This thesis proposes such a test oracle, OLIN, which reports anomalies in the concurrent executions of programs. OLIN finds concurrency bugs that are consistently missed by previous techniques and incurs low overhead. OLIN can achieve a higher effectiveness within given time and computational budgets. Service-based systems are composed of loosely coupled and unassociated units of functional units and are often highly concurrent and distributed. We have witnessed their prosperity in recent decades. Service-based systems are highly dynamic and regression testing techniques are applied to ensure their previously established functionality and correctness are not adversely affected by subsequent evolutions. However, regression testing is expensive and our thesis focuses on the prioritization of regression test cases to improve the effectiveness of testing within predefined constraints. This thesis proposes a family of prioritization metrics for regression testing of location-based services and presents a case study to evaluate their performance. In conclusion, this thesis makes the following contributions to software testing and analysis: (1) a dynamic sampling framework for concurrency bug detection, (2) a test oracle for concurrent testing, and (3) a family of test case prioritization techniques for service-based systems. These contributions significantly improve the effectiveness and efficiency of resource utilization in software testing. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Computer systems play an increasingly crucial and ubiquitous role in human endeavour by carrying out or facilitating tasks and providing information and services. How much work these systems can accomplish, within a certain amount of time, using a certain amount of resources, characterises the systems’ performance, which is a major concern when the systems are planned, designed, implemented, deployed, and evolve. As one of the most popular computer systems, the Web is inevitably scrutinised in terms of performance analysis that deals with its speed, capacity, resource utilisation, and availability. Performance analyses for the Web are normally done from the perspective of the Web servers and the underlying network (the Internet). This research, on the other hand, approaches Web performance analysis from the perspective of Web pages. The performance metric of interest here is response time. Response time is studied as an attribute of Web pages, instead of being considered purely a result of network and server conditions. A framework that consists of measurement, modelling, and monitoring (3Ms) of Web pages that revolves around response time is adopted to support the performance analysis activity. The measurement module enables Web page response time to be measured and is used to support the modelling module, which in turn provides references for the monitoring module. The monitoring module estimates response time. The three modules are used in the software development lifecycle to ensure that developed Web pages deliver at worst satisfactory response time (within a maximum acceptable time), or preferably much better response time, thereby maximising the efficiency of the pages. The framework proposes a systematic way to understand response time as it is related to specific characteristics of Web pages and explains how individual Web page response time can be examined and improved.

The World Health Organization (WHO) estimate that road traffic accidents represent the third leading cause of ‘death and disease’ worldwide. Many countries have, therefore, launched safety campaigns that are intended to reduce road traffic accidents by increasing public awareness. In almost every case, however, a reduction in the total number of fatalities has not been matched by a comparable fall in the total frequency of road traffic accidents. Low severity incidents remain a significant problem. One possible explanation is that these road safety campaigns have had less effect than design changes. Active safety devices such as anti-lock braking, and passive measures, such as side impact protection, serve to mitigate the consequences of those accidents that do occur. A number of psychological phenomena, such as attribution error, explain the mixed success of road safety campaigns. Most drivers believe that they are less likely to be involved in an accident than other motorists. Existing road safety campaigns do little to address this problem; they focus on national and regional statistics that often seem remote from the local experiences of road users. Our argument is that localized road accident information would have better impact on people’s safety awareness. This thesis, therefore, describes the design and development of a software tool to provide the general public with access to information on the location and circumstances of road accidents in a Scottish city. We also present the results of an evaluation to determine whether the information provided by this software has any impact on individual risk perception. A route planing experiment was also carried out. The results from the experiment gives more positive feedback that road users would consider accident information if such information was available for them.