Mapping and islanding problems in small scale on-chip networks and large scale power grid networks

In recent years design of computing systems has been extremely challenging due to the advances in processor architectures and semiconductor technologies. With increasing complexity of embedded system products directed towards consumer market and emerging multimedia standards, future Multi Processor System-on-Chips (MPSoCs) are predicted to contain hundreds of Processing Elements (PEs). In this dissertation, complex task of mapping and scheduling of applications to the PEs and resource contention issues have been studied.;The techniques applied to solve the above problems are useful in islanding and partitioning problems in electrical power grid networks as well. Islanding technique is widely used in power distribution networks to avoid cascading power failures. The problem is modeled as a graph partitioning problem with an objective of solving a modified version of the traditional min-cut problem. It has been shown that with slight modification of the objective function, the complexity of the problem changes significantly.;Techniques to find optimal solutions to the problems are developed utilizing mathematical programming. Heuristics solutions are developed using greedy strategy, LP relaxation and randomization techniques. Benchmark and real applications are used to evaluate the proposed methodologies.;Due to performance requirements and scalability issues, Network-on-Chip (NoC) has been widely accepted as the alternative to shared bus and point-to-point architecture for on-chip communication. Minimization of energy consumption has become one of the most important objectives. Communication energy consumption in NoC constitutes a major factor of the overall energy consumption. Energy consumption can be reduced using efficient mapping of tasks to PEs, mapping PEs to NoC routers and routing over the NoC links. A significant amount of additional saving of computation energy can be achieved by scaling down the voltage levels of non-critical PEs. This additional saving, however, comes at the expense of increased complexity of power delivery network and the energy consumption on level shifters. A unified approach to solve all the subproblems of the mapping and scheduling problem is presented. This unified approach outperforms the traditional approach that solves the subproblems sequentially In addition, algorithms have been developed to incorporate these problems during the floorplanning and placement of the PEs on the chip.