Scheduling

• Basic block scheduling techniques: the basic list scheduling approach [Gibbons and Muchnick, 1986] (cycle based or operation based; chapter 3 of [Hoogerbrugge, 1996]), and a number of alternatives, like:
  • Force directed scheduling [Paulin and Knight, 1989, Stok, 1994].
  • Genetic based [Beaty, 1991].
  • Percolation scheduling [Nicolau, 1985].
• Heuristics: heuristics for list scheduling [Smotherman et al., 1991]; general computing heuristics [Pearl, 1984].
• Inter basic block scheduling with different scheduling scope:
  • Overview of scheduling scopes: see chapter 4 of [Hoogerbrugge, 1996].
  • Trace [Fisher, 1981, Lowney et al., 1993]; Bulldog compiler [Ellis, 1986].
  • Superblock [Hwu et al., 1993, Chekuri et al., 1996].
  • Decision tree [Hsu and Davidson, 1986].
  • Hyperblock (i.e. a region if-converted to a superblock) [Mahlke et al., 1992b].
  • Region [Bernstein and Rodeh, 1991, Mahadevan and Ramakrishnan, 1994]; chapter 4 of [Hoogerbrugge, 1996] describes region scheduling applied to TTAs.
• Software pipelining:
  • Modulo scheduling:
    • Principles [Rau and Glaeser, 1981];
      Lam's software pipelining algorithm [Lam, 1988];
      DESP (Decomposed Software Pipelining) [Wang and Eisenbeis, 1993].
    • Iterative modulo scheduling [Rau, 1994] (an extensive overview is given in [Rau, 1996]).
    • Slack-scheduling [Huff, 1993].
    • Scheduling loops with control-flow [Lavery and Hwu, 1996]
    • Used in commercial compilers [Dehnert and Towle, 1993, Ramakrishnan, 1992].
    • Cache sensitive modulo scheduling [Sánchez and González, 1997].
  • Enhanced pipeline scheduling [Ebcioğlu, 1987, Ebcioğlu and Nakatani, 1989, Moon and Ebcioğlu, 1992].
  • Kernel recognition techniques: perfect pipelining [Aiken and Nicolau, 1988], and URPR [Su and Wang, 1991].
• General papers on scheduling for superscalar and VLIW processors: PA-8000 [Holler, 1996, Dunn and Hsu, 1996, Ebcioğlu et al., 1994, Brownhil et al., 1997, Novack et al., 1995b]; using profiling information [Chen et al., 1994].