AbstractsComputer Science

This thesis considers how to speed up the execution of functional programs using parallel execution, load distribution, and speculative evaluation. This is an important challenge given the increasing complexity of software systems, the decreasing cost of individual processors, and the appropriateness of the functional paradigm for parallelisation. Processor speeds are continuing to climb â�� but the magnitudes of increase are overridden by both the increasing complexity of software and the escalating expectation of users. Future gains in speed are likely to occur through the combination of todayâ��s conventional uni-processors to form loosely-coupled multicomputers. Parallel program execution can theoretically provide linear speed-ups, but for this theoretical benefit to be realised two main hurdles must be overcome. The first of these is the identification and extraction of parallelism within the program to be executed. The second hurdle is the runtime management and scheduling of the parallel components to achieve the speed-up without slowing the execution of the program. Clearly a lot of work can be done by the programmer to â��paralleliseâ�� the algorithm. There is often, however, much parallelism available without significant effort on the part of the programmer. Functional programming languages and compilers have received much attention in the last decade for the contributions possible in parallel executions. Since the semantics of languages from the functional programming paradigm manifest the Church-Rosser property (that the order of evaluation of sub-expressions does not affect the result), sub-expressions may be executed in parallel. The absence of side-effects and the lack of state facilitate the availability of expressions suitable for concurrent evaluation. Unfortunately, such expressions may involve varying amounts of computation or require high amounts of data â�� both of which complicate the management of parallel execution. If the future of computation is through the formation of multicomputers, we are faced with the high probability that the number of available processing units will quickly outweigh the known parallelism of an algorithm at any given moment during execution. Intuitively this spare processing power should be utilised if possible. The premise of speculative evaluation is that it employs otherwise idle tasks on work that may prove beneficial. The more program components available for execution the greater the opportunity for speculation and potentially the quicker the programâ��s result may be obtained. The second impediment for the parallel execution of programs is the scheduling of program components for evaluation. Multicomputer execution of a program involves the allocation of program components among the available tasks to maximise throughput. We present a decentralised, speculation-cognate, load distribution algorithm that allocates and manages the distribution of program components among the tasks with the co-aim of minimising the impact on tasks…