Hardware Scheduling for Dynamic Adaptability using External Profiling and Hardware Threading

ABSTRACT

While performance, area, and power constraints have been thedriving force in designing current communication-enabled embeddedsystems, post-fabrication and run-time adaptability is now required.Two dominant configurable hardware platforms are processorsand FPGAs. However, for compute-intensive applications,neither platform delivers the needed performance at the desiredlow power. The need thus arises for custom, application-specificconfigurable (ASC) hardware.This paper addresses the optimization of ASC hardware. Ourtarget application areas are multimedia and communication wherean incoming packet (task) is processed independently of otherpackets. We innovatively utilize two concepts: external profilingand hardware threading. We utilize an M/M/c queueing model toprofile task arrival patterns and show how profiling guides designdecisions. We introduce the novel concept of hardware threadingwhich allows on-the-fly borrowing of unutilized hardware, thusmaximizing task-level parallelism, to either boost performance orto lower power consumption. We present a scheduling algorithmthat synthesizes a hardware-threaded architecture, and discuss experimentalresults that illustrate adaptability to different workloads,and performance/power trade-offs.

REFERENCES

• 1: Arnold O. Allen, Probability, statistics, and queueing theory with computer science applications, Academic Press Professional, Inc., San Diego, CA, 1990
• 2: [2] ARM. "http://www.arm.com/armtech/ARM11Microarchitecture".
• 3: Luca Benini , Alessandro Bogliolo , Giovanni De Micheli, A survey of design techniques for system-level dynamic power management, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.3, p.299-316, June 2000 [doi>10.1109/92.845896]
• 4: [4] R. Camposano. "Path-Based Scheduling for Synthesis". IEEE Transactions on Computer-Aided Design, 10(1):85-93, January 1990.
• 5: Andre DeHon, Reconfigurable Architectures for General-Purpose Computing, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 6: André DeHon, The Density Advantage of Configurable Computing, Computer, v.33 n.4, p.41-49, April 2000 [doi>10.1109/2.839320]
• 7: Carl Ebeling , Darren C. Cronquist , Paul Franklin, RaPiD - Reconfigurable Pipelined Datapath, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.126-135, September 23-25, 1996
• 8: Varghese George , Hui Zhang , Jan Rabaey, The design of a low energy FPGA, Proceedings of the 1999 international symposium on Low power electronics and design, p.188-193, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313920]
• 9: J. R. Hauser , J. Wawrzynek, Garp: a MIPS processor with a reconfigurable coprocessor, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.12, April 16-18, 1997
• 10: Zhining Huang , Sharad Malik, Exploiting operation level parallelism through dynamically reconfigurable datapaths, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514006]
• 11: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 12: Bill Salefski , Levent Caglar, Re-configurable computing in wireless, Proceedings of the 38th conference on Design automation, p.178-183, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378459]
• 13: [13] Tensilica, Inc. "http://www.tensilica.com/".
• 14: [14] Texas Instruments, Inc. "http://www.ti.com/".
• 15: Marlene Wan , Hui Zhang , Varghese George , Martin Benes , Arthur Abnous , Vandana Prabhu , Jan Rabaey, Design Methodology of a Low-Energy Reconfigurable Single-Chip DSP System, Journal of VLSI Signal Processing Systems, v.28 n.1-2, p.47-61, May-June 2001 [doi>10.1023/A:1008159121620]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.2 Design Aids
          Subjects: Optimization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms, Design, Performance