Mapping pipelined applications onto heterogeneous embedded systems: a bayesian optimization algorithm based approach

ABSTRACT

In this paper we propose a flow based on the Bayesian Optimization Algorithm (BOA) for mapping pipelined applications on a heterogeneous multiprocessor platform on Field Programmable Gate Array (FPGA) with customizable processors. BOA is a Probabilistic Model Building Genetic Algorithm (PMBGA) that, substituting the classical mutation and crossover operators with the construction and the sampling of a Bayesian network, is able to identify correlated sub-structures within the problem to be maintained while generating new solutions.

The paper introduces the model adopted for pipelined applications and then shows why BOA fits the problem better than other search algorithms, like Genetic Algorithm (GA), Simulated Annealing (SA) and Tabu Search (TS). We also show that our algorithm is able to cope with data parallel pipelined algorithms. We finally validate our flow on realistic applications like JPEG and ADPCM coding by executing the resulting mapping on our platform.

REFERENCES

• 1: S. Banerjee, T. Hamada, P. M. Chau, and R. D. Macro pipelining based scheduling on high performance heterogeneous multiprocessor systems. IEEE Transactions on Signal Processing, 43(6):1468--1484, June 1995.
• 2: A. Benoit and Y. Robert. Mapping pipeline skeletons onto heterogeneous platforms. J. Parallel Distrib. Comput., Table 4: JPEG performance as predicted by BOA compared to the 68(6):790--808, 2008.
• 3: K. S. Chatha and R. Vemuri. A tool for partitioning and pipelined scheduling of hardware-software systems. In ISSS '98: the 11th international symposium on System synthesis, pages 145--151, 1998.
• 4: W. J. Dally, U. J. Kapasi, B. Khailany, J. H. Ahn, and A. Das. Stream Processors: Progammability and Efficiency. Queue, 2(1):52--62, 2004.
• 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: D. E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison--Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.
• 7: D. E. Goldberg. The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Norwell, MA, USA, 2002.
• 8: M. I. Gordon, W. Thies, and S. Amarasinghe. Exploiting coarse-grained task, data, and pipeline parallelism in stream programs. In ASPLOS-XII: the 2th international conference on Architectural support for programming languages and operating systems, pages 151--162, October 2006.
• 9: M. Grajcar. Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system. In DAC '99: the 36th annual conference on Design automation, pages 280--285, 1999.
• 10: H. Javaid and S. Parameswaran. Synthesis of heterogeneous pipelined multiprocessor systems using ILP: jpeg case study. In CODES/ISSS '08: the 6th international conference on Hardware/Software codesign and system synthesis, pages 1--6, 2008.
• 11: C. T. King, W. H. Chou, and L. M. Ni. Pipelined data parallel algorithms-i: Concept and modeling. IEEE Trans. Parallel Distrib. Syst., 1(4):470--485, 1990.
• 12: M. Kudlur and S. Mahlke. Orchestrating the execution of stream programs on multicore platforms. In PLDI '08: the ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 114--124, 2008.
• 13: Y. Lin, H. Lee, M. Woh, Y. Harel, S. Mahlke, T. Mudge, C. Chakrabarti, and K. Flautner. SODA: A low-power architecture for software radio. In ISCA '06: the 33rd International Symposium on Computer Architecture, pages 89--101, 2006.
• 14: D. M. Nicol and D. R. O'Hallaron. Improved Algorithms for Mapping Pipelined and Parallel Computations. IEEE Trans. Comput., 40(3):295--306, 1991.
• 15: C. Ostler, K. S. Chatha, V. Ramamurthi, and K. Srinivasan. Ilp and heuristic techniques for system-level design on network processor architectures. ACM Trans. Des. Autom. Electron. Syst., 12(4):48, 2007.
• 16: J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
• 17: M. Pelikan, D. E. Goldberg, and E. E. Cantú-paz. Linkage problem, distribution estimation, and bayesian networks. Evol. Comput., 8(3):311--340, 2000.
• 18: M. Pelikan, K. Sastry, and D. E. Goldberg. Sporadic model building for efficiency enhancement of hierarchical boa. In GECCO '06: the 8th annual conference on Genetic and evolutionary computation, pages 405--412, 2006.
• 19: S. L. Shee and S. Parameswaran. Design methodology for pipelined heterogeneous multiprocessor system. In DAC '07: the 44th annual conference on Design automation, pages 811--816, 2007.
• 20: A. Tumeo, M. Branca, L. Camerini, M. Ceriani, M. Monchiero, G. Palermo, F. Ferrandi, and D. Sciuto. Prototyping pipelined applications on a heterogeneous fpga multiprocessor virtual platform. In ASP--DAC '09: Asia and South Pacific Design Automation Conference, pages 317--322, 2009.
• 21: 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.
• 22: N. Weng, N. Kumar, S. Dechu, and B. Soewito. Mapping task graphs onto network processors using genetic algorithm. In AICCSA 2008: the IEEE/ACS International Conference on Computer Systems and Applications, pages 481--488, Mar./Apr. 2008.
• 23: T. Wiangtong, P. Cheung, and W. Luk. Comparing three heuristic search methods for functional partitioning in hardware-software codesign. Design Automation for Embedded Systems, 6(4):425--449, July 2002.
• 24: W. Wolf. The future of multiprocessor systems-on-chips. In DAC '04: the 41st annual conference on Design Automation, pages 681--685, 2004.
• 25: H. Yang and S. Ha. Pipelined data parallel task mapping/scheduling technique for mpsoc. In DATE '09: Design, Automation and Test in Europe, pages 69--75, 2009.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Performance

Keywords:
BOA, FPGA, heterogeneous embedded systems, pipelining