Extending Force-directed Scheduling with Explicit Parallel and Timed Constructs for High-level Synthesis

This work extends force-directed scheduling (FDS) to support specification constructs that express parallelism and timing behaviours. We select the FDS algorithm because it maximizes the amount of resource sharing, and it naturally supports constructs for parallelism. However, timed constructs are not supported. As a result, we propose timed FDS (TFDS) that optimizes over parallel, timed and untimed constructs. In doing so, we make the following four contributions: 1) we extend the definition of control data flow graphs (CDFGs) to define timed CDFGs (TCDFGs), 2) we define a scheduling algorithm for timed constructs called TIME, 3) we extend the definition of mobility used in FDS, and 4) we present optimizations for a composition of parallel, timed and untimed constructs to better aid FDS. We implement our extensions in a high-level synthesis framework based on the abstract state machine formalism, and we generate synthesizable VHDL. We experiment with several examples such as FIR, edge detector, and a differential equation solver, and target them onto an Altera DE2 FPGA. Some of these experiments show improvements of up to 52% in circuit area when compared to their unoptimized counterparts.