University of Twente Student Theses


Scheduling the sequential hardware-in-the-loop simulator

Roodenburg, S.B. (2009) Scheduling the sequential hardware-in-the-loop simulator.

[img] PDF
Abstract:Rutgers [17] developed a hardware simulation environment, which incorporates time multiplexing to allow large hardware designs to be run completely in a FPGA. One of the subjects that required future work was the scheduler: the implemented round robin arbiter does not take any dependencies between cells into account. It was expected that a proper scheduler could drastically improve performance. In this thesis we developed a new scheduler for the seq hils. The duv is partitioned by the developer into different cells. Similar cells are mapped onto a small set of hypercells. Since the cells are considered to be Mealy machines, each cells output depends on its inputs and its current state. Dependencies between cells consist of interconnections between cells and combinational paths through cells. An algorithm for deducting a complete dependency graph from a duv was proposed. The dependency graph will contain all possible data paths through the duv. If all deducted data dependencies are taken into consideration for scheduling, we can construct a schedule offine which can guarantee stabilization of the system. For the scheduling of the seq hils we have implemented an hybrid online/offline scheduling approach. We chose for a computational intensive initial scheduling ofline. This schedule will be optimized during simulation by a simple (low overhead) online scheduler. We introduced two heuristical approaches for offline scheduling based on the dependency paths, which both have a low-order polynomial time and space complexity. This allows us to apply both heuristical approaches on large designs, and choose the schedule with the best makespan, within tenths of seconds. We showed that a worst-case schedule (i.e. a schedule constrained by all data dependencies) would require 3 to 10% less delta cycles to stabilize a system cycle than the round robin arbiter would require. As an online optimization approach, we suggest to start with the worst-case offine schedule, and use runtime information about which cells are unstable, to skip over parts of the schedule if cells are already stable. Tests show that this approach can do another 5 to 10% percent performance increase on average. Based on these results we expected the final performance increase to be about 12 to 15%. After implementing the new algorithms, two realistic designs were simulated with both the round robin and the new scheduler. The actual performance increase matches the expected performance increase based on the results. From this, we expect the 12 to 15% speed increase to hold for a large range of designs.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science MSc (60300)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page