No description available.

The topic for this dissertation is the optimisation of computer programs, as they are being compiled, using discrete optimisation techniques. The techniques introduced aim to optimise the runtime performance of programs executing on certain types of processors. A very important component of this dissertation is the movement of complexity from the processor to the compiler. Therefore both computer architecture and compilers are important supporting topics. The data output of the compiler is processed using information about the processor to produce execution information which is the goal of this dissertation. Concepts related to instruction level parallelism are covered in two parts. The first part discusses implicit parallelism, where parallel instruction scheduling is performed by the processor. The second part discusses explicit parallelism, where the compiler schedules the instructions. Explicit parallelism is attractive because it allows processor design to be simplified resulting in multiple benefits. Scheduling the instructions to execute while adhering to resource limitations is the area of focus for the rest of the dissertation. In order to find optimal schedules the problem is modelled as a mathematical program. Expressing instructions, instruction dependencies and resource limitations as a mathematical program are discussed in detail with several algorithms being introduced. Several aspects prevent the mathematical programs from being solved in their initial state, therefore additional techniques are introduced. A heuristic algorithm is introduced for scheduling instructions in a resource limited environment. The primary use of this heuristic is to reduce the computational complexity of the problem. However, this heuristic algorithm can be used to generate good schedules on its own. Finally information regarding a practical implementation of a compiler that implements the introduced techniques is introduced as well as experimental results. The experimental results are generated from a series of test programs illustrating the complete process and the computational complexity of the algorithms employed. / Smith, T.H.C., Prof.

No description available.

Traditionally, algorithms have been evaluated through worst-case analysis, where the input is presumed to take its worst possible configuration. However, in many real-world settings, the data is not adversarially constructed and, on the contrary, exhibits some recognizable patterns. This often leads worst-case guarantees to be poor indicators of algorithms' performance. To overcome this limitation, a growing body of work on Beyond Worst-Case analysis has recently emerged. In this thesis, we are concerned with sequential decision-making problems, where an agent must take successive decisions over multiple time steps without knowing in advance the forthcoming input. Examples of such settings include ride-sharing, online retail or job scheduling. Motivated by the unprecedented surge of data in these domains, which may help to overcome worst-case barriers by allowing to predict at least partially the future, we explore three distinct frameworks for Beyond Worst-Case analysis of sequential decision-making: (i) semi-random models, (ii) parametric models, and (iii) algorithms with predictions. While they all pursue the same objective — using previously collected data to provide stronger theoretical guarantees —, these frameworks mainly differ in the way the data is utilized. We examine each of them separately and present novel results for five different online optimization problems: minimum cost matching, assortment optimization (with and without inventory constraints), pricing and scheduling.