Analysis of quasi-static scheduling techniques in a virtualized reconfigurable machine

ABSTRACT

The SCORE compute model uses fixed-size, virtual compute and memory pages connected by stream links to capture the definition of a computation abstracted from the detailed size of the physical hardware. When the number of physical compute pages is smaller than the number of virtual compute pages in the abstract computation graph, the design is time-multiplexed onto the available physical hardware. A key component of this strategy is an automatic scheduler that selects the temporal sequencing of virtual resources onto the physical device. We describe a quasi-static scheduling strategy that retains the full semantic power of the dynamic SCORE flow graph while taking advantage of static scheduling techniques at program load time to hoist most of the computational work out of the inner scheduling loops. This strategy reduces online scheduling work per reconfiguration epoch by an order of magnitude. In addition, a more global perspective available from offline-scheduling improves schedule quality, resulting in a net reduction of total execution time by 46--81%.

REFERENCES

• 1: Shuvra S. Battacharyya , Edward A. Lee , Praveen K. Murthy, Software Synthesis from Dataflow Graphs, Kluwer Academic Publishers, Norwell, MA, 1996
• 2: Joseph Tobin Buck , Edward A. Lee, Scheduling dynamic dataflow graphs with bounded memory using the token flow model, 1993
• 3: J.T.Buck.Static scheduling and code generation from dynamic dataflow graphs with integer-valued control streams.In Conferenc on Signals,Systems, and Computers ,November 1 1994.
• 4: Eylon Caspi , Michael Chu , Randy Huang , Joseph Yeh , John Wawrzynek , André DeHon, Stream Computations Organized for Reconfigurable Execution (SCORE), Proceedings of the The Roadmap to Reconfigurable Computing, 10th International Workshop on Field-Programmable Logic and Applications, p.605-614, August 27-30, 2000
• 5: M.M.Chu.Dynamic runtime scheduler support for score.Master 's thesis,UC Berkeley,2000.
• 6: Andre Maurice Dehon , Thomas Knight, Jr., Reconfigurable architectures for general-purpose computing, 1996
• 7: Soonhoi Ha, Compile-time scheduling of dataflow program graphs with dynamic constructs, University of California at Berkeley, Berkeley, CA, 1992
• 8: S.Ha and E.A.Lee.Quasi-static scheduling for multiprocessor dsp.In IEEE International Symposium on Circuits and Systems,Singapore.Conferenc on Signals,Systems,and Computers ,June 1991.
• 9: Soonhoi Ha , Edward A. Lee, Compile-Time Scheduling of Dynamic Constructs in Dataflow Program Graphs, IEEE Transactions on Computers, v.46 n.7, p.768-778, July 1997 [doi>10.1109/12.599897 ]
• 10: E.Lee.Advanc d Topics in Data-Flow Computing , chapter Static Scheduling ofData-Flow Programs for DSP,pages 501 -527.Prentice-Hall,Inc.,1991.
• 11: H.Liu and D.F.Wong.Network-flow-based multiway partitioning with area and pin constraints.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems ,17(1):50 -59,January 1998.
• 12: Thomas Martyn Parks, Bounded scheduling of process networks, University of California at Berkeley, Berkeley, CA, 1996