Genetic Programming for Low-Resource Systems

Embedded systems dominate the computing landscape. This dominance is increasing with the advent of ubiquitous computing whereby lightweight, low-resource systems are being deployed on a vast scale. These systems present new engineering challenges: high-volume production places a stronger emphasis on absolute cost, resources available to executing software are highly constrained, and physical manufacturing capabilities approach hard limits. Add to this the sensitive nature of many of these systems, such as smartcards used for financial transactions, and the development of these systems becomes a formidable engineering challenge. For the software engineer, the incentive to produce efficient and resource-aware software for these platforms is great, yet existing tools do not support them well in this task. It is difficult to assess the impact of decisions made at the source code level in terms of how they change a system's resource consumption. Existing toolchains, together with the very complex interactions of software and their host processors, can produce unforeseen implications at run-time of even small changes. We could describe such a situation as an instance of programming the unprogrammable, and Genetic Programming is one solution method used for such problems. Genetic Programming, inspired by nature's ability to solve problems involving complex interactions and strong pressures on resource consumption, is a clear candidate for attacking the challenges presented in these systems. Genetic Programming facilitates the creation and manipulation of source code in a way that grants us fine control over its measurable characteristics. In this thesis, I investigate the potential of Genetic Programming as a tool in controlling the non-functional properties of software, as a new method of designing code for low-resource systems. I demonstrate the feasibility of this approach, and investigate some of the ways Genetic Programming could be utilised by a practitioner. In doing so, I also identify key components that any application of Genetic Programming to such a domain will require. I review current low-resource system optimisation, Genetic Programming and methods for simultaneously handling multiple requirements. I present a series of empirical investigations designed to provide evidence for and against a set of hypotheses regarding the success of Genetic Programming in solving problems within the low-resource systems domain. These experiments include the creation of new software, the improvement of existing software and the fine-grained control of resource usage in general. Thus I will address a range of non-functional requirements related to the resource-consumption of a program, and demonstrate how we can apply techniques inspired by natural evolution in combination with conventional optimisation methods to address some of the problems that the plethora of low-resource systems present. To conclude, I review the progress made, reassess my hypotheses, and outline how these new methods can be carried forward to a wide range of applications