×

A GRASP metaheuristic for the robust mapping and routing of dataflow process networks on manycore architectures. (English) Zbl 1327.90157

Summary: In this paper, we study the problem of joint placement and routing, both in the deterministic and stochastic cases, arising in the field of compilation of dataflow applications for manycore architectures. A GRASP algorithm is first proposed for solving the deterministic version and extended afterwards to treat the chance-constrained program with uncertainty affecting the weights of a dataflow process network. Extensive computational results, on representative synthetic benchmark and real data, illustrate the practical relevance of the approach, as well as the robustness of the obtained stochastic solutions.

MSC:

90C15 Stochastic programming
90C59 Approximation methods and heuristics in mathematical programming
68N20 Theory of compilers and interpreters
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aubry P, Beaucamps PE, Blanc F, Bodin B, Carpov S, Cudennec L, David V, Dore P, Dubrulle P, Dupont BdD, Galea F, Goubier T, Harrand M, Jones S, Lesage J, Louise S, Chaisemartin N, Nguyen T, Raynaud H, Sirdey R (2013) Extended cyclostatic dataflow program compilation and execution for an integrated manycore processor. In: Proceedings of the first international workshop on architecture, languages, compilation and hardware support for emerging manycore systems (ALCHEMY 2013), Barcelona, Spain, pp 1624-1633
[2] Bonfietti A, Benini L, Lombardi M, Milano M (2010) An efficient and complete approach for throughput-maximal sdf allocation and scheduling on multi-core platforms. In: Proceedings of the conference on design, automation and test in Europe, DATE ’10. European Design and Automation Association, pp 897-902
[3] Calafiore G, Campi M (2006) The scenario approach to robust control design. IEEE Trans Autom Control 51(5):742-753 · Zbl 1366.93457 · doi:10.1109/TAC.2006.875041
[4] Carpov S, Cudennec L, Sirdey R (2013) Throughput constrained parallelism reduction in cyclo-static dataflow applications. Procedia Comput Sci 18:30-39 · doi:10.1016/j.procs.2013.05.166
[5] Castrillon J, Tretter A, Leupers R, Ascheid G (2012) Communication-aware mapping of KPN applications onto heterogeneous mpsocs. In: Proceedings of the 49th annual design automation conference, DAC ’12. ACM, New York, NY, pp 1266-1271
[6] Choi J, Oh H, Kim S, Ha S (2012) Executing synchronous dataflow graphs on a SPM-based multicore architecture. In: Proceedings of the 49th annual design automation conference, DAC ’12. ACM, New York, NY, pp 664-671
[7] Dupont de Dinechin B, Guironnet de Massas G, Lager G, Léger C, Orgogozo B, Reybert J, Strudel T (2013) A distributed run-time environment for the Kalray MPPA-256 integrated manycore processor. Procedia Comput Sci 18(0):1654-1663 · doi:10.1016/j.procs.2013.05.333
[8] Feo T, Resende M (1995) Greedy randomized adaptive search procedures (GRASP). J Glob Optim 6:109-133 · Zbl 0822.90110
[9] Galea F, Sirdey R (2012) A parallel simulated annealing approach for the mapping of large process networks. In: IPDPS Workshop, pp 1787-1792
[10] Garey M, Johnson D, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theor Comput Sci 1(3):237-267 · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[11] Goubier T, Sirdey R, Louise S, David \[V (2011) \Sigma\] ΣC: a programming model and langage for embedded manycores. In: Lecture Notes in Computer Science, vol 7016, pp 385-394 · Zbl 0338.05120
[12] Hu J, Marculescu R (2005) Energy- and performance-aware mapping for regular NoC architectures. IEEE Trans Comput Aided Des Integr Circuits Syst 24(4):551-562 · doi:10.1109/TCAD.2005.844106
[13] Korte B, Vygen J (2006) Combinatorial optimization: theory and algorithms, 3rd edn. Springer, Berlin · Zbl 1099.90054
[14] Lee E, Parks T (1995) Dataflow process networks. Proc IEEE 83(5):773-801 · doi:10.1109/5.381846
[15] Lo VM (1988) Heuristic algorithms for task assignment in distributed systems. IEEE Trans Comput 37(11):1384-1397 · doi:10.1109/12.8704
[16] Lombardi M, Milano M, Ruggiero M, Benini L (2010) Stochastic allocation and scheduling for conditional task graphs in multiprocessor systems-on-chip. J Sched 13:315-345 · Zbl 1232.68017 · doi:10.1007/s10951-010-0184-y
[17] Manolache S, Eles P, Peng Z (2008) Task mapping and priority assignment for soft real-time applications under deadline miss ratio constraints. ACM Trans Embed Comput Syst 7(2):19:1-19:35 · doi:10.1145/1331331.1331343
[18] Marcon C, Borin A, Susin A, Carro L, Wagner F (2005) Time and energy efficient mapping of embedded applications onto NoCs. In: ASP-DAC 2005, vol 1, pp 33-38
[19] Marculescu R, Ogras U, Peh LS, Jerger N, Hoskote Y (2009) Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives. IEEE Trans Comput Aided Des Integr Circuits Syst 28(1):3-21 · doi:10.1109/TCAD.2008.2010691
[20] Marwedel P, Teich J, Kouveli G, Bacivarov I, Thiele L, Ha S, Lee C, Xu Q, Huang L (2011) Mapping of applications to MPSoCs. In: Proceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, CODES+ISSS ’11. ACM, New York, NY, pp 109-118
[21] Murali S, Benini L, De Micheli G (2006) A methodology for mapping multiple use-cases onto networks on Chips. In: DATE. IEEE, pp 118-123
[22] Orsila H, Salminen E, Hämäläinen TD (2009) Parameterizing simulated annealing for distributing Kahn process networks on multiprocessor SoCs. In: Proceedings of the 11th international conference on System-on-chip, SOC’09, pp 19-26
[23] Prékopa A (1995) Stochastic programming. Kluwer Academic Publishers, Dordrecht · Zbl 0863.90116 · doi:10.1007/978-94-017-3087-7
[24] Shestak V, Smith J, Uml R, Hale J, Moranville P, Maciejewski AA, Siegel HJ (2006) Greedy approaches to static stochastic robust resource allocation for periodic sensor driven distributed systems. In: Proceedings of the 2006 international conference on parallel and distributed processing techniques and applications (PDPTA06), pp 3-9 · Zbl 0355.68042
[25] Singh AK, Shafique M, Kumar A, Henkel J (2013) Mapping on multi/many-core systems: survey of current and emerging trends. In: Proceedings of the 50th annual design automation conference, DAC ’13. ACM, New York, NY, pp 1:1-1:10
[26] Sirdey R (2011) Contributions á l’optimisation combinatoire pour l’embarqué: des autocommutateurs cellulaires aux microprocesseurs massivement paralléles. HDR, UTC, France
[27] Srinivasan K, Chatha K (2005) A technique for low energy mapping and routing in Network-on-Chip architectures. In: ISLPED ’05, pp 387-392
[28] Stan O, Sirdey R, Carlier J, Nace D (2012) A heuristic algorithm for stochastic partitioning of process networks. In: Proceedings of the 16th IEEE international conference on system theory, control and computing (ICSTCC), pp 1-6
[29] Stan O, Sirdey R, Carlier J, Nace D (2013) A GRASP for placement and routing of dataflow process networks on manycore architectures. In: Eight international conference on P2P, parallel, grid, cloud and internet computing (3PGCIC) · Zbl 1327.90157
[30] Stone H (1977) Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans Softw Eng 3(1):85-93 · Zbl 0355.68042 · doi:10.1109/TSE.1977.233840
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.