Task placement heuristic based on 3D-adjacency and look-ahead in reconfigurable systems

ABSTRACT

To get efficient HW management in 2D Reconfigurable Systems, heuristics are needed to select the best place to locate each arriving task. We propose a technique that locates the task next to the borders of the free area for as many cycles as possible, trying to minimize the area fragmentation. Moreover, we combine it with a look-ahead heuristic that allows delaying the scheduling of a task to the next event, increasing the solution search space.

REFERENCES

• 1: Katherine Compton , Scott Hauck, Reconfigurable computing: a survey of systems and software, ACM Computing Surveys (CSUR), v.34 n.2, p.171-210, June 2002 [doi>10.1145/508352.508353]
• 2: O. F. Diessel, G. Wigley, "Opportunities for Operating Systems Research in Reconfigurable Computing", Technical Report ACRC-99-018. Advanced Computing Research Centre, School of Computer and Information Science, University of South Australia, 1999.
• 3: O. F. Diessel, H. Elgindy, "On dynamic task scheduling for FPGA-based systems", International Journal of Foundations of Computer Science, IJFCS'01, Vol. 12, No. 5, 2001.
• 4: Kiarash Bazargan , Ryan Kastner , Majid Sarrafzadeh, Fast Template Placement for Reconfigurable Computing Systems, IEEE Design & Test, v.17 n.1, p.68-83, January 2000 [doi>10.1109/54.825678]
• 5: Herbert Walder , Christoph Steiger , Marco Platzner, Fast Online Task Placement on FPGAs: Free Space Partitioning and 2D-Hashing, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.178.2, April 22-26, 2003
• 6: A. Ahmadinia, C. Bobda, M. Bednara, J. Teich, "A new approach for on-line placement on reconfigurable devices", IPDPS-2004 (RAW'04), vol. 04, no. 4, p. 134a, 2004.
• 7: Manish Handa , Ranga Vemuri, An efficient algorithm for finding empty space for online FPGA placement, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996820]
• 8: J. Tabero J. Septién, H. Mecha, D. Mozos, "A vertex-list approach to 2D HW multitasking management in RTR FPGAs", DCIS 2003, Ciudad Real, Spain, pp. 545--550, Nov 2003.
• 9: J. Tabero J. Septién, H. Mecha, D. Mozos, "A low fragmentation heuristic for task placement in 2D RTR HW management", FPL 2004, Antwerp, Belgium, pp. 241--250, Sep 2004

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

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

General Terms:
Algorithms, Design, Performance