Instruction scheduling for a tiled dataflow architecture

ABSTRACT

This paper explores hierarchical instruction scheduling for a tiled processor. Our results show that at the top level of the hierarchy, a simple profile-driven algorithm effectively minimizes operand latency. After this schedule has been partitioned into large sections, the bottom-level algorithm must more carefully analyze program structure when producing the final schedule.Our analysis reveals that at this bottom level, good scheduling depends upon carefully balancing instruction contention for processing elements and operand latency between producer and consumer instructions. We develop a parameterizable instruction scheduler that more effectively optimizes this trade-off. We use this scheduler to determine the contention-latency sweet spot that generates the best instruction schedule for each application. To avoid this application-specific tuning, we also determine the parameters that produce the best performance across all applications. The result is a contention-latency setting that generates instruction schedules for all applications in our workload that come within 17% of the best schedule for each.

REFERENCES

• 1: Saman P. Amarasinghe , Monica S. Lam, Communication optimization and code generation for distributed memory machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.126-138, June 21-25, 1993, Albuquerque, New Mexico, United States
• 2: Jennifer M. Anderson , Monica S. Lam, Global optimizations for parallelism and locality on scalable parallel machines, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.112-125, June 21-25, 1993, Albuquerque, New Mexico, United States
• 3: K. Arvind , Rishiyur S. Nikhil, Executing a Program on the MIT Tagged-Token Dataflow Architecture, IEEE Transactions on Computers, v.39 n.3, p.300-318, March 1990 [doi>10.1109/12.48862]
• 4: D. Buell et al. Splash 2: FPGAs in a Custom Computing Machine. IEEE Computer Society, 1996.
• 5: Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.1-12, May 01-04, 1999, Atlanta, Georgia, United States
• 6: Katherine E. Coons , Xia Chen , Doug Burger , Kathryn S. McKinley , Sundeep K. Kushwaha, A spatial path scheduling algorithm for EDGE architectures, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 7: David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
• 8: A. L. Davis, The architecture and system method of DDM1: A recursively structured Data Driven Machine, Proceedings of the 5th annual symposium on Computer architecture, p.210-215, April 03-05, 1978 [doi>10.1145/800094.803050]
• 9: Jack B. Dennis , David P. Misunas, A preliminary architecture for a basic data-flow processor, Proceedings of the 2nd annual symposium on Computer architecture, p.126-132, January 20-22, 1975
• 10: G. Desoli. Instruction assignment for clustered VLIW DSP compilers: A new approach. Technical Report HPL-98-13, Hewlett-Packard Laboratories, January 1998.
• 11: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 12: John R. Ellis, Bulldog: a compiler for vliw architectures (parallel computing, reduced-instruction-set, trace scheduling, scientific), 1985
• 13: Paolo Faraboschi , Geoffrey Brown , Joseph A. Fisher , Giuseppe Desoli , Fred Homewood, Lx: a technology platform for customizable VLIW embedded processing, Proceedings of the 27th annual international symposium on Computer architecture, p.203-213, June 2000, Vancouver, British Columbia, Canada
• 14: V. G. Grafe , G. S. Davidson , J. E. Hoch , V. P. Holmes, The Epsilon dataflow processor, Proceedings of the 16th annual international symposium on Computer architecture, p.36-45, April 1989, Jerusalem, Israel
• 15: J. R Gurd , C. C Kirkham , I. Watson, The Manchester prototype dataflow computer, Communications of the ACM, v.28 n.1, p.34-52, Jan. 1985 [doi>10.1145/2465.2468]
• 16: Daniel R. Kerns , Susan J. Eggers, Balanced scheduling: instruction scheduling when memory latency is uncertain, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.278-289, June 21-25, 1993, Albuquerque, New Mexico, United States
• 17: Masasuke Kishi , Hiroshi Yasuhara , Yasusuke Kawamura, DDDP-a Distributed Data Driven Processor, Proceedings of the 10th annual international symposium on Computer architecture, p.236-242, June 13-17, 1983, Stockholm, Sweden
• 18: Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
• 19: Walter Lee , Rajeev Barua , Matthew Frank , Devabhaktuni Srikrishna , Jonathan Babb , Vivek Sarkar , Saman Amarasinghe, Space-time scheduling of instruction-level parallelism on a raw machine, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.46-57, October 02-07, 1998, San Jose, California, United States
• 20: Walter Lee , Diego Puppin , Shane Swenson , Saman Amarasinghe, Convergent scheduling, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 21: Jack L. Lo , Susan J. Eggers, Improving balanced scheduling with compiler optimizations that increase instruction-level parallelism, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.151-162, June 18-21, 1995, La Jolla, California, United States
• 22: P. Geoffrey Lowney , Stefan M. Freudenberger , Thomas J. Karzes , W. D. Lichtenstein , Robert P. Nix , John S. O'Donnell , John Ruttenberg, The multiflow trace scheduling compiler, The Journal of Supercomputing, v.7 n.1-2, p.51-142, May 1993 [doi>10.1007/BF01205182]
• 23: K. Mai, T. Paaske, N. Jayasena, R. Ho, W. Dally, and M. Horowitz. Smart memories: A modular reconfigurable architecture. In International Symposium on Computer Architecture, 2002.
• 24: Ramadass Nagarajan , Sundeep K. Kushwaha , Doug Burger , Kathryn S. McKinley , Calvin Lin , Stephen W. Keckler, Static Placement, Dynamic Issue (SPDI) Scheduling for EDGE Architectures, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.74-84, September 29-October 03, 2004 [doi>10.1109/PACT.2004.26]
• 25: Ramadass Nagarajan , Karthikeyan Sankaralingam , Doug Burger , Stephen W. Keckler, A design space evaluation of grid processor architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 26: Emre Özer , Sanjeev Banerjia , Thomas M. Conte, Unified assign and schedule: a new approach to scheduling for clustered register file microarchitectures, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.308-315, November 1998, Dallas, Texas, United States
• 27: Gregory M. Papadopoulos , David E. Culler, Monsoon: an explicit token-store architecture, Proceedings of the 17th annual international symposium on Computer Architecture, p.82-91, May 28-31, 1990, Seattle, Washington, United States
• 28: Gregory M. Papadopoulos , Kenneth R. Traub, Multithreading: a revisionist view of dataflow architectures, Proceedings of the 18th annual international symposium on Computer architecture, p.342-351, May 27-30, 1991, Toronto, Ontario, Canada
• 29: Todd A. Proebsting , Charles N. Fischer, Linear-time, optimal code scheduling for delayed-load architectures, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.256-267, June 24-28, 1991, Toronto, Ontario, Canada
• 30: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 31: S. Sakai , y. Yamaguchi , K. Hiraki , Y. Kodama , T. Yuba, An architecture of a dataflow single chip processor, Proceedings of the 16th annual international symposium on Computer architecture, p.46-53, April 1989, Jerusalem, Israel
• 32: Jesús Sánchez , Antonio González, Instruction scheduling for clustered VLIW architectures, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain [doi>10.1145/501790.501801]
• 33: T. Shimada , K. Hiraki , K. Nishida , S. Sekiguchi, Evaluation of a prototype data flow processor of the SIGMA-1 for scientific computations, Proceedings of the 13th annual international symposium on Computer architecture, p.226-234, June 02-05, 1986, Tokyo, Japan
• 34: Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
• 35: SPEC. Spec CPU 2000 benchmark specifications. SPEC2000 Benchmark Release, 2000.
• 36: Steven Swanson , Ken Michelson , Andrew Schwerin , Mark Oskin, WaveScalar, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.291, December 03-05, 2003
• 37: Steven Swanson , Andrew Putnam , Martha Mercaldi , Ken Michelson , Andrew Petersen , Andrew Schwerin , Mark Oskin , Susan J. Eggers, Area-Performance Trade-offs in Tiled Dataflow Architectures, Proceedings of the 33rd annual international symposium on Computer Architecture, p.314-326, June 17-21, 2006
• 38: Reinhard von Hanxleden , Ken Kennedy, GIVE-N-TAKE—a balanced code placement framework, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.107-120, June 20-24, 1994, Orlando, Florida, United States
• 39: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254]
• 40: Kent Wilken , Jack Liu , Mark Heffernan, Optimal instruction scheduling using integer programming, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.121-133, June 18-21, 2000, Vancouver, British Columbia, Canada
• 41: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 42: Tao Yang , Apostolos Gerasoulis, PYRROS: static task scheduling and code generation for message passing multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.428-437, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143446]
• 43: Javier Zalamea , Josep Llosa , Eduard Ayguadé , Mateo Valero, Modulo scheduling with integrated register spilling for clustered VLIW architectures, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
dataflow, instruction scheduling, tiled architectures