Top

International Journal of Parallel Programming

Published in:

01-06-2015

Power Efficiency for Hardware/Software Partitioning with Time and Area Constraints on MPSoC

Authors: Edwin Sha, Li Wang, Qingfeng Zhuge, Jun Zhang, Jing Liu

Published in: International Journal of Parallel Programming | Issue 3/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Hardware/software partitioning is a crucial step in hardware/software co-design for energy-efficient, high-performance systems. Previous research efforts mainly focused on single processor architecture. Their methods can not produce high-quality solutions to the problem of hardware/software partitioning for multiprocessor systems. In this paper, we propose two algorithms for hardware/software partitioning problem on MPSoC, to minimize power consumption with time and area constraints. The Tree_Partitioning algorithm generates optimal partitioning results for tree-structured control-flow graphs using dynamic programming. For the general partitioning problem, we propose the DAG_Partitioning algorithm to produce near optimal solution efficiently for directed-acyclic graphs. The experimental results show that our proposed algorithms outperform existing techniques for a set of benchmarks with various time and area constraints.

previous article Accelerating Smith-Waterman Alignment of Species-Based Protein Sequences on GPU

next article CCAP: A Cache Contention-Aware Virtual Machine Placement Approach for HPC Cloud

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Arató, P., Juhász, S., Mann, Z.Á., Orbán, A., Papp, D.: Hardware-software partitioning in embedded system design. In: Intelligent Signal Processing, 2003 IEEE International Symposium on, pp. 197–202 (2003)

Arató, P., Mann, Z.Á., Orbán, A.: Algorithmic aspects of hardware/software partitioning. ACM Trans. Des. Autom. Electron. Syst. 10(1), 136–156 (2005)CrossRef

Bakshi, S., Gajski, D.D.: Hardware/software partitioning and pipelining. In: Proceedings of the 34th annual Design Automation Conference, pp. 713–716. ACM (1997)

Bình, N.N., Imai, M., Shiomi, A., Hikichi, N.: A hardware/software partitioning algorithm for designing pipelined asips with least gate counts. In: Design Automation Conference Proceedings 1996, 33rd, pp. 527–532 (1996)

Blickle, T., Teich, J., Thiele, L.: System-level synthesis using evolutionary algorithms. Des. Autom. Embed. Syst. 3(1), 23–58 (1998)CrossRef

Chatha, K.S., Vemuri, R.: An iterative algorithm for hardware-software partitioning, hardware design space exploration and scheduling. Des. Autom. Embed. Syst. 5(3–4), 281–293 (2000)CrossRef

Chatha, K.S., Vemuri, R.: Magellan: multiway hardware-software partitioning and scheduling for latency minimization of hierarchical control-dataflow task graphs. In: Proceedings of the Ninth International Symposium on Hardware/Software, Codesign, pp. 42–47 (2001)

Chatha, K.S., Vemuri, R.: Hardware-software partitioning and pipelined scheduling of transformative applications. IEEE Trans. Very Large Scale Integr. Syst. 10(3), 193–208 (2002)CrossRef

Dick, R.P., Jha, N.K.: Mogac: A multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems. IEEE Trans. Comput. Aid. Des. Integr. Circuits Syst. 17(10), 920–935 (1998)CrossRef

10.

Dick, R.P., Rhodes, D.L., Wolf, W.: Tgff: task graphs for free. In: Proceedings of the 6th International Workshop on Hardware/Software Codesign, pp. 97–101. IEEE Computer Society (1998)

11.

Eles, P., Peng, Z., Kuchcinski, K., Doboli, A.: System level hardware/software partitioning based on simulated annealing and tabu search. Des. Autom. Embed. Syst. 2(1), 5–32 (1997)CrossRef

12.

Gohringer, D., Becker, J.: High performance reconfigurable multi-processor-based computing on fpgas. In: 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, pp. 1–4 (2010)

13.

Goodacre, J., Sloss, A.N.: Parallelism and the arm instruction set architecture. Computer 38(7), 42–50 (2005)CrossRef

14.

Grode, J., Knudsen, P.V., Madsen, J.: Hardware resource allocation for hardware/software partitioning in the lycos system. In: Proceedings of the Design, Automation and Test in Europe, pp. 22–27 (1998)

15.

Henkel, J., Ernst, R.: An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques. IEEE Trans. Very Large Scale Integr. Syst. 9(2), 273–289 (2001)CrossRef

16.

Jiang, Y., Zhang, H., Jiao, X., Song, X., Hung, W.N., Gu, M., Sun, J.: Uncertain model and algorithm for hardware/software partitioning. In: VLSI, 2012 IEEE Computer Society Annual Symposium on, pp. 243–248 (2012)

17.

Jigang, W., Chang, B., Srikanthan, T.: A hybrid branch-and-bound strategy for hardware/software partitioning. In: Computer and Information Science, Eighth IEEE/ACIS International Conference on, pp. 641–644 (2009)

18.

Jigang, W., Srikanthan, T.: Algorithmic aspects of area-efficient hardware/software partitioning. J. Supercomput. 38(3), 223–235 (2006)CrossRef

19.

Jigang, W., Srikanthan, T., Chen, G.: Algorithmic aspects of hardware/software partitioning: 1D search algorithms. IEEE Trans. Comput. 59(4), 532–544 (2010)CrossRefMathSciNet

20.

Jigang, W., Srikanthan, T., Jiao, T.: Algorithmic aspects for functional partitioning and scheduling in hardware/software co-design. Des. Autom. Embed. Syst. 12(4), 345–375 (2008)CrossRef

21.

Kalavade, A., Subrahmanyam, P.: Hardware/software partitioning for multifunction systems. IEEE Trans. Comput. Aid. Des. Integr. Circuits Syst. 17(9), 819–837 (1998)CrossRef

22.

Lee, T.Y., Fan, Y.H., Tsai, C.C.: Adaptive multi-constraints in hardware-software partitioning for embedded multiprocessor fpga systems. WSEAS Trans. Comput. 8(2), 334–343 (2009)

23.

Lin, T.Y., Hung, Y.T., Chang, R.G.: Efficient hardware/software partitioning approach for embedded multiprocessor systems. In: VLSI Design, Automation and Test, 2006 International Symposium on, pp. 1–4 (2006)

24.

López-Vallejo, M., López, J.C.: On the hardware-software partitioning problem: System modeling and partitioning techniques. ACM Trans. Des. Autom. Electron. Syst. 8(3), 269–297 (2003)CrossRef

25.

Madsen, J., Grode, J., Knudsen, P.V., Petersen, M.E., Haxthausen, A.: Lycos: The lyngby co-synthesis system. Des. Autom. Embed. Syst. 2(2), 195–235 (1997)CrossRef

26.

Niemann, R., Marwedel, P.: Hardware/software partitioning using integer programming. In: Proceedings of the 1996 European Conference on Design and Test, p. 473. IEEE Computer Society (1996)

27.

Niemann, R., Marwedel, P.: An algorithm for hardware/software partitioning using mixed integer linear programming. Des. Autom. Embed. Syst. 2(2), 165–193 (1997)CrossRef

28.

Srinivasan, V., Radhakrishnan, S., Vemuri, R.: Hardware software partitioning with integrated hardware design space exploration. In: Design, Automation and Test in Europe, 1998, Proceedings, pp. 28–35 (1998)

29.

Vahid, F.: Partitioning sequential programs for cad using a three-step approach. ACM Trans. Des. Autom. Electron. Syst. 7(3), 413–429 (2002)CrossRef

30.

Vahid, F., Gajski, D.D.: Clustering for improved system-level functional partitioning. In: System Synthesis, 1995, Proceedings of the Eighth International Symposium on, pp. 28–33 (1995)

31.

Vertex, Xilinx Inc., http://www.xilinx.com

32.

Wiangtong, T., Cheung, P.Y., Luk, W.: Comparing three heuristic search methods for functional partitioning in hardware-software codesign. Des. Autom. Embed. Syst. 6(4), 425–449 (2002)CrossRef

33.

Wiangtong, T., Cheung, P.Y., Luk, W.: Hardware/software codesign: A systematic approach targeting data-intensive applications. IEEE Signal Process. Mag. 22(3), 14–22 (2005)CrossRef

34.

Wolf, W., Jerraya, A.A., Martin, G.: Multiprocessor system-on-chip (mpsoc) technology. IEEE Trans. Comput. Aid. Des. Integr. Circuits Syst. 27(10), 1701–1713 (2008)CrossRef

35.

Wu, J., Srikanthan, T.: Low-complex dynamic programming algorithm for hardware/software partitioning. Inf. Process. Lett. 98(2), 41–46 (2006)CrossRefMATH

36.

Wu, J., Srikanthan, T., Yan, C.: Algorithmic aspects for power-efficient hardware/software partitioning. Math. Comput. Simul. 79(4), 1204–1215 (2008)CrossRefMATHMathSciNet

37.

Zivojnovic, V., Velarde, J.M., Schlager, C., Meyr, H.: Dspstone: A dsp-oriented benchmarking methodology. Signal Process. Appl. Technol. 94 (1994)

Title: Power Efficiency for Hardware/Software Partitioning with Time and Area Constraints on MPSoC
Authors: Edwin Sha
Li Wang
Qingfeng Zhuge
Jun Zhang
Jing Liu
Publication date: 01-06-2015
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 3/2015
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-013-0283-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 3/2015

Efficiently Restoring Virtual Machines

An Adaptive and Memory Efficient Sampling Mechanism for Partitioning in MapReduce

Accelerating Smith-Waterman Alignment of Species-Based Protein Sequences on GPU

A Virtualization Based Monitoring System for Mini-intrusive Live Forensics

A Parallel Job Execution Time Estimation Approach Based on User Submission Patterns within Computational Grids

Network and Parallel Computing

Premium Partner