×

zbMATH — the first resource for mathematics

Using constraint programming for the design of network-on-chip architectures. (English) Zbl 1401.90184
Summary: NoC technology is composed of packet-based interconnections, where the communication resources are distributed across the network. Therefore, the optimal resource utilization is a crucial consideration for efficient architectural designs. This paper studies the practicality of the Constraint Programming (CP) models for NoC architecture designs that effectively use a regular mesh with wormhole switching and the XY routing. The complexity of the CP models is compared with the earlier Mixed Integer Programming (MIP) models. Practical CP-based mapping and scheduling models are developed and results are reported on the benchmark datasets. Results indicate that mapping and scheduling problems can be solved at near optimality even under relatively shorter run-time limits as compared to those required by the MIP models.
MSC:
90C27 Combinatorial optimization
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
47N10 Applications of operator theory in optimization, convex analysis, mathematical programming, economics
47N70 Applications of operator theory in systems, signals, circuits, and control theory
Software:
TGFF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baptiste P, Laborie P, Pape CL, Nuijten W (2006) Handbook of constraint programming, chap 22. Constraint-based scheduling and planning. Elsevier, Amsterdam, pp 761-799
[2] Benini L, Bertozzi D, Guerri A, Milano M (2005) Allocation and scheduling for mpsocs via decomposition and no-good generation. In: van Beek P (ed) Principles and practice of constraint programming—CP 2005. Lecture notes in computer science, vol 3709. Springer, Berlin, pp 107-121. doi:10.1007/11564751_11
[3] De Micheli G, Seiculescu C, Murali S, Benini L, Angiolini F, Pullini A (2010) Networks on chips: from research to products. In: Sapatnekar SS (ed) DAC. ACM, pp 300-305
[4] Demiriz A, Bagherzadeh N, Alhussein A (2013) Cpnoc: On using constraint programming in design of network-on-chip architecture. In: Parallel, Distributed and Network-Based Processing (PDP), 2013 21st Euromicro International Conference on, pp 486-493. doi:10.1109/PDP.2013.78
[5] Dick RP, Rhodes DL, Wolf W (1998) Tgff: task graphs for free. In: Borriello G, Jerraya AA, Lavagno L (eds) CODES, IEEE Computer Society, pp 97-101
[6] Ghosh P, Sen A (2010) Efficient mapping and voltage islanding technique for energy minimization in noc under design constraints. In: Shin, SY Ossowski, S Schumacher, M Palakal, MJ Hung CC (eds.) SAC. ACM, New York, pp 535-541
[7] He O, Dong S, Jang W, Bian J, Pan DZ (2011) Unism: unified scheduling and mapping for general networks on chip. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, PP(99):1-14. doi:10.1109/TVLSI.2011.2159280 · Zbl 1188.90146
[8] van Hoeve WJ, Katriel I (2006) Handbook of constraint programming, chap 6 Global Constraints. Elsevier, Amsterdam, pp 169-208
[9] Hu, J; Marculescu, R, Energy- and performance-aware mapping for regular noc architectures, IEEE Trans CAD Integr Circuits Syst, 24, 551-562, (2005)
[10] Liu W, Xu J, Wu X, Ye Y, Wang X, Zhang W, Nikdast M, Wang Z (2011) A noc traffic suite based on real applications. In: VLSI (ISVLSI), 2011 IEEE Computer Society Annual Symposium on, pp 66-71. doi:10.1109/ISVLSI.2011.49
[11] Loiola, EM; Abreu, NMM; Netto, POB; Hahn, P; Querido, TM, A survey for the quadratic assignment problem, Eur J Oper Res, 176, 657-690, (2007) · Zbl 1103.90058
[12] Lombardi M, Milano M (2012) Optimal methods for resource allocation and scheduling: a cross-disciplinary survey. Constraints 17(1):51-85. doi:10.1007/s10601-011-9115-6
[13] Marculescu, R; Ogras, ÜY; Peh, LS; Jerger, NDE; Hoskote, YV, Outstanding research problems in noc design: system, microarchitecture, and circuit perspectives, IEEE Trans CAD Integr Circuits Syst, 28, 3-21, (2009)
[14] Michel L, Van Hentenryck P (2010) Wiley encyclopedia of operations research and management science, chap. Basic CP theory: search. Wiley, New York. doi:10.1002/9780470400531.eorms0088
[15] Ogras, ÜY; Marculescu, R; Marculescu, D; Jung, EG, Design and management of voltage-frequency island partitioned networks-on-chip, IEEE Trans VLSI Syst, 17, 330-341, (2009)
[16] Ruggiero M, Guerri A, Bertozzi D, Milano M, Benini L (2008) A fast and accurate technique for mapping parallel applications on stream-oriented mpsoc platforms with communication awareness. Int J Parallel Program 36:3-36. doi:10.1007/s10766-007-0032-7 · Zbl 1138.68335
[17] Shcherbina O. Quadratic assignment test problems. http://www.mat.univie.ac.at/ oleg/TEST/Chapter13/HCP13.5.1.mod. Accessed Apr 2013
[18] Srinivasan, K; Chatha, KS; Konjevod, G, Linear-programming-based techniques for synthesis of network-on-chip architectures, IEEE Trans VLSI Syst, 14, 407-420, (2006)
[19] Zhang, H; Beltran-Royo, C; Constantino, M, Effective formulation reductions for the quadratic assignment problem, Comput OR, 37, 2007-2016, (2010) · Zbl 1188.90146
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.