The pipeline decomposition tree:: an analysis tool for multiprocessor implementation of image processing applications

ABSTRACT

Modern embedded systems for image processing involve increasingly complex levels of functionality under real-time and resource-related constraints. As this complexity increases, the application of single-chip multiprocessor technology is attractive. To address the challenges of mapping image processing applications onto embedded multiprocessor platforms, this paper presents a novel data structure called the pipeline decomposition tree (PDT), and an associated scheduling framework, which we refer to as PDT scheduling. PDT scheduling exploits both heterogeneous data parallelism and task-level parallelism, which are important considerations for scheduling image processing applications. This paper develops the PDT representation for system synthesis, and presents methods using the PDT to derive customized pipelined architectures that are streamlined for the given implementation constraints.

REFERENCES

• 1: Smita Bakshi , Daniel D. Gajski, Partitioning and pipelining for performance-constrained hardware/software systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.4, p.419-432, Dec. 1999 [doi>10.1109/92.805749 ]
• 2: N. K. Bambha, S. S. Bhattacharyya, J. Teich, and E. Zitzler. Systematic integration of parameterized local search in evolutionary algorithms. IEEE Transactions on Evolutionary Computation,8(2):137--155, April 2004.
• 3: S. Banerjee, T. Hamada, P. M. Chau, and R. D. Fellman, Macropipelining based scheduling on high performance heterogeneous multiprocessor systems. IEEE Trans. Signal Processing, vol. 43, pp.1468--1484, June 1995.
• 4: M. K. Dhodhi, I. Ahmad, and I. Ahmad. "A multiprocessorscheduling scheme using problem-space genetic algorithms". InIEEE Conf. on Evolutionary Computation, pages 214-219, 1994.
• 5: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 6: P. Hoang and J. Rabaey, Scheduling of DSP Programs ontoMultiprocessors for Maximum Throughput. In IEEE Transactionson Signal Processing, vol. 41, no.6, June 1993.
• 7: J. Jonsson, J. Vasell, "Real-Time Scheduling for Pipelined Executionof Data Flow Graphs on a Realistic Multiprocessor Architecture",In Proceedings of IEEE International Conference onAcoustics, Speech and Signal Processing, May 7-10, 1996, Atlanta,Georgia, USA, pp. 3314-3317.
• 8: B. Kernighan and S. Lin. An Efficient Heuristic Procedure forPartitioning Graphs. The Bell System Technical Journal, pages 291--307, February 1970.
• 9: K. Konstantinides, R. T. Kaneshiro, and J. R. Tani, "Task Allocationand Scheduling Models for Multiprocessor Digital Signal Processing," IEEE Trans. on Acoustics, Speech, and Signal Processing, vol. 38, no. 12, pp. 2151--2161, Dec. 1990.
• 10: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 11: A Task Duplication Based Scheduling Algorithm for Heterogeneous Systems, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.445, May 01-05, 2000
• 12: Jim Rehg , Kathleen Knobe , Umakishore Ramachandran , Rishiyur S. Nikhil , Arun Chauhan, Integrated Task and Data Parallel Support for Dynamic Applications, Selected Papers from the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computers, p.167-180, May 28-30, 1998
• 13: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 14: Jaspar Subhlok , Gary Vondran, Optimal latency-throughput tradeoffs for data parallel pipelines, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.62-71, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237508]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Design

Keywords:
design space exploration, multiprocessor scheduling, system-level models