Interactive co-design of high throughput embedded multimedia

ABSTRACT

The idea of Force-Directed Scheduling (FDS) was first introduced by Paulin and Knight to minimize the number of resources required in the high-level synthesis of high-throughput ASICs [3]. In this paper, we reformulate the original FDS algorithm to address the interactive hardware and software design of low-cost but still high-throughput embedded multimedia systems.

REFERENCES

• 1: R.L.Graham, "Bounds on multiprocessor timing anomalies", SIAM J. Appl. Math., 17(2):416-429, 1969.
• 2: B.W.Kernighan and S.Lin, "An Effective Heuristic Procedure For Partitioning Graphs ", The Bell System Technical Journal pp. 291-308, February 1970.
• 3: Pierre G. Paulin , John P. Knight, Algorithms for High-Level Synthesis, IEEE Design & Test, v.6 n.6, p.18-31, November 1989 [doi>10.1109/54.41671]
• 4: Y.Therasse & al, "VLSI architecture of a SMDS/ATM router", An. T616coms, Vol.48, No.3-4, pp. 166-180, 1993.
• 5: L. Nachtergaele , F. Catthoor , F. Balasa , F. Franssen , E. De Greef , H. Samsom , H. De Man, Optimization of memory organization and hierarchy for decreased size and power in video and image processing systems, Proceedings of the 1995 IEEE International Workshop on Memory Technology, Design and Testing, p.82, August 07-08, 1995
• 6: W.F.J. Verhaegh & al, "Improved Force-Directed Scheduling (IFDS) in high-throughput digital signal processing", IEEE Trans. CAD, VoI. i4, p. 945-960, 1995.
• 7: A.Gerasoulis & al, "A multistage approach to scheduling task graphs", DIMACS Series Discrete Math Th. Comp. Sc., 22:81-103, 1995.
• 8: Anshul Gupta, Fast and effective algorithms for graph partitioning and sparse-matrix ordering, IBM Journal of Research and Development, v.41 n.1-2, p.171-183, Jan./March 1997
• 9: Zhen Liu, Worst-case analysis of scheduling heuristics of parallel systems, Parallel Computing, v.24 n.5-6, p.863-891, June 1998 [doi>10.1016/S0167-8191(98)00037-4]
• 10: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 11: D.Eppstein & al, "Dynamic graph algorithms", CRC Handbook of Algorithms and Theory of Computation, Chapter 8, 1999.
• 12: Arnout Vandecappelle , Miguel Miranda , Erik Brockmeyer , Francky Catthoor , Diederik Verkest, Global multimedia system design exploration using accurate memory organization feedback, Proceedings of the 36th ACM/IEEE conference on Design automation, p.327-332, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309945]
• 13: Sven Wuytack , Francky Catthoor , Gjalt de Jong , Hugo J. De Man, Minimizing the required memory bandwidth in VLSI system realizations, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.4, p.433-441, Dec. 1999 [doi>10.1109/92.805750]
• 14: T.J-EOmn~s & aI, "Dynamic algorithms for minimizing memory bandwidth in high throughput telecom and multimedia" in Techniques de paralI61isation automatique, TSI, I~ditions Hermes, 1999.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Advanced technologies
  B.8 Performance and Reliability

  C. Computer Systems Organization

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

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)

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

General Terms:
Design, Performance, Theory