Evolutionary algorithms for the mapping of pipelined applications onto heterogeneous embedded systems

ABSTRACT

In this paper, we compare four algorithms for the mapping of pipelined applications on a heterogeneous multiprocessor platform implemented using Field Programmable Gate Arrays (FPGAs) with customizable processors. Initially, we describe the framework and the model of pipelined application we adopted. Then, we focus on the problem of mapping a set of pipelined applications onto a heterogeneous multiprocessor platform and consider four search algorithms: Tabu Search, Simulated Annealing, Genetic Algorithms, and the Bayesian Optimization Algorithm. We compare the performance of these four algorithms on a set of synthetic problems and on two real-world applications (the JPEG image encoding and the ADPCM sound encoding). Our results show that on our framework the Bayesian Optimization Algorithm outperforms all the other three methods for the mapping of pipelined applications.

REFERENCES

• 1: S. Banerjee, T. Hamada, P.M. Chau, and R.D. Fellman. Macro pipelining based scheduling on high performance heterogeneous multiprocessor systems. IEEE Transactions on Signal Processing, 43(6):1468--1484, June 1995.
• 2: Anne Benoit , Yves Robert, Mapping pipeline skeletons onto heterogeneous platforms, Journal of Parallel and Distributed Computing, v.68 n.6, p.790-808, June, 2008 [doi>10.1016/j.jpdc.2007.11.004]
• 3: Karam S. Chatha , Ranga Vemuri, A tool for partitioning and pipelined scheduling of hardware-software systems, Proceedings of the 11th international symposium on System synthesis, p.145-151, December 02-04, 1998, Hsinchu, Taiwan, China
• 4: William J. Dally , Ujval J. Kapasi , Brucek Khailany , Jung Ho Ahn , Abhishek Das, Stream Processors: Progammability and Efficiency, Queue, v.2 n.1, March 2004 [doi>10.1145/984458.984486]
• 5: P. Eles, Z. Peng, K. Kuchcinski, and A. Doboli. System level hardware/software partitioning based on simulated annealing and tabu search. Design Automation for Embedded Systems, 2:5--32, 1997.
• 6: Christian Gagné , Marc Parizeau, Open BEAGLE: A New C++ Evolutionary Computation Framework, Proceedings of the Genetic and Evolutionary Computation Conference, p.888, July 09-13, 2002
• 7: Fred Glover , Fred Laguna, Tabu Search, Kluwer Academic Publishers, Norwell, MA, 1997
• 8: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 9: Michael I. Gordon , William Thies , Saman Amarasinghe, Exploiting coarse-grained task, data, and pipeline parallelism in stream programs, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: Martin Grajcar, Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system, Proceedings of the 36th annual ACM/IEEE Design Automation Conference, p.280-285, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309931]
• 11: Haris Javaid , Sri Parameswaran, Synthesis of heterogeneous pipelined multiprocessor systems using ILP: jpeg case study, Proceedings of the 6th IEEE/ACM/IFIP international conference on Hardware/Software codesign and system synthesis, October 19-24, 2008, Atlanta, GA, USA [doi>10.1145/1450135.1450137]
• 12: C. T. King , W. H. Chou , L. M. Ni, Pipelined Data Parallel Algorithms-I: Concept and Modeling, IEEE Transactions on Parallel and Distributed Systems, v.1 n.4, p.470-485, October 1990 [doi>10.1109/71.80175]
• 13: S. Kirkpatrick, C. Gelatt, and M. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, 1983. http://www.jstor.org/stable/1690046 Retrieved on 16 January 2009.
• 14: Yuan Lin , Hyunseok Lee , Mark Woh , Yoav Harel , Scott Mahlke , Trevor Mudge , Chaitali Chakrabarti , Krisztian Flautner, SODA: A Low-power Architecture For Software Radio, Proceedings of the 33rd annual international symposium on Computer Architecture, p.89-101, June 17-21, 2006
• 15: David M. Nicol , David R. O'Hallaron, Improved Algorithms for Mapping Pipelined and Parallel Computations, IEEE Transactions on Computers, v.40 n.3, p.295-306, March 1991 [doi>10.1109/12.76406]
• 16: M. Pelikan. Bayesian optimization algorithm with decision graphs in c++, version 1.1, 2000.
• 17: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithm. Springer Verlag, Berlin, 2005.
• 18: Martin Pelikan , David E. Goldberg , Erick E. Cantú-paz, Linkage Problem, Distribution Estimation, and Bayesian Networks, Evolutionary Computation, v.8 n.3, p.311-340, September 2000 [doi>10.1162/106365600750078808]
• 19: Seng Lin Shee , Sri Parameswaran, Design methodology for pipelined heterogeneous multiprocessor system, Proceedings of the 44th annual Design Automation Conference, June 04-08, 2007, San Diego, California [doi>10.1145/1278480.1278682]
• 20: G. Wang, W. Gong, B. DeRenzi, and R. Kastner. Application partitioning on programmable platforms using the ant colony optimization. Journal of Embedded Computing, 1(12):1--18, 2005.
• 21: Ning Weng , Nandeesh Kumar , Satish Dechu , Benfano Soewito, Mapping task graphs onto Network Processors using genetic algorithm, Proceedings of the 2008 IEEE/ACS International Conference on Computer Systems and Applications, p.481-488, March 31-April 04, 2008 [doi>10.1109/AICCSA.2008.4493576]
• 22: Wayne Wolf, The future of multiprocessor systems-on-chips, Proceedings of the 41st annual Design Automation Conference, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996753]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Algorithms

Keywords:
boa, fpga, ga, mapping, pipelining, sa, ts