Online placement and scheduling algorithms and methodologies for reconfigurable computing systems

An operating system is required for controlling the applications and managing the FPGA resources in a multi-user multi-tasking reconfigurable computing platform. In our research, we examine computer aided design (CAD) issues involved in the design of a reconfigurable operating system (ROS). In our model of the reconfigurable operating system, a host is responsible for managing reconfigurable resources and execution of applications. Main CAD operations performed by the host include temporal partitioning, synthesis, online scheduling and online placement.; We present an efficient algorithm for finding empty area on the FPGA as a list of maximal empty rectangles. In addition to being fast, our algorithm handles dynamic addition and deletion of tasks efficiently while maintaining a high quality placement. We use bin packing heuristics for choosing suitable placement location for a task. We provide detailed characteristics of the online placement system.; We present an integrated online scheduling and placement methodology. We defer scheduling decisions until it is absolutely necessary to accommodate dynamically changing task priorities. We show by experimentation that in-order task execution strategy guarantees the shortest execution time and the out-of-order strategy results in better FPGA area utilization.; We use computational geometry algorithms and data-structures for placement of rectilinear tasks. Our algorithm can be used for placement of mixed rectangular and rectilinear tasks.; We propose a run-time efficient algorithm to quantify the amount of fragmentation of area resources in a given rectangular bounding box area on the FPGA. We demonstrate that fragmentation aware online placement results in better placement quality.; Massive parallelism inherent in a hardware implementation of an algorithm can be explored for its faster execution as compared to its software implementation. We present three different reconfigurable architectures for two dimensional online placement. Each architecture makes different trade-offs between execution time, area usage, memory requirement and reconfiguration overheads.; Shifting of task placement and scheduling responsibility to hardware reduce the time tick processing overhead and result in faster placement and scheduling decisions. We propose a hardware based integrated online placement and scheduling algorithm.