Hardware/software codesign is a design methodology for embedded systems that seeks to satisfy system-level constraints by exploiting the synergy between hardware and software through their concurrent design [71]. During partitioning, design components are assigned to hardware and software implementation targets. The output of the partitioner has a significant impact on the subsequent scheduling of software. This dissertation is a study of the relationship between the partitioning and scheduling of concurrent systems as it pertains to hardware/software codesign. It is structured as three related studies.

The first study is on the Earliest Deadline First (EDF) scheduling policy. This is an optimal policy that yields high processor utilization. An algorithm for the off-line feasibility analysis of systems scheduled by EDF is extended in this study to accommodate tasks that employ coprocessors during their execution. This is relevant to software systems that have been partitioned by moving part of the application functionality into hardware coprocessors.

The second study is a case study of a real-time kernel that implements the EDF scheduling policy and an automotive application executing on a System on Programmable Chip (SoPC). The application is partitioned by creating a hardware coprocessor. The kernel is also partitioned. The impact on the schedule feasibility of the system is examined for both coprocessors. A metric is also proposed that facilitates comparison of coprocessors, whether for the application or the kernel.

The third study is of automated partitioners. The hardware/software partitioning problem is defined such that it includes schedule feasibility and the joint partitioning of application and kernel. A non-linear programming model is created to capture the problem definition and a heuristic is developed based on the Fiduccia/Mattheyses heuristic. Results confirm that the scheduling problem is hard enough that it is not likely to be satisfied unless directly addressed by the partitioner. The results also show that including the kernel in partitioning helps to produce solutions with feasible schedules.

The inter-related nature of hardware/software partitioning, and scheduling of concurrent systems is demonstrated through the three studies described above. In the process, scheduling by the preemptive Earliest Deadline First policy is explored in its relation to hardware/software codesign. It is shown that scheduling of concurrent systems needs to be integrated into hardware/software partitioning in order to meet demanding system constraints. Since all three studies focused on single-processor systems, an avenue for further exploration is to consider multi-processor systems.