Due to the ever-growing requirements in high performance data computation, multiprocessor systems have been proposed to solve the bottlenecks in uniprocessor systems. Developing efficient multiprocessor systems requires effective exploration of design choices like application scheduling, mapping, and architecture design. Also, fault tolerance in multiprocessors needs to be addressed. With the advent of nanometer-process technology for chip manufacturing, realization of multiprocessors on SoC (MpSoC) is an active field of research. Developing efficient low power, fault-tolerant task scheduling, and mapping techniques for MpSoCs require optimized algorithms that consider the various scenarios inherent in multiprocessor environments. Therefore there exists a need to develop a simulation framework to explore and evaluate new algorithms on multiprocessor systems. This work proposes a modular framework for the exploration and evaluation of various design algorithms for MpSoC system. This work also proposes new multiprocessor task scheduling and mapping algorithms for MpSoCs. These algorithms are evaluated using the developed simulation framework. The paper also proposes a dynamic fault-tolerant (FT) scheduling and mapping algorithm for robust application processing. The proposed algorithms consider optimizing the power as one of the design constraints. The framework for a heterogeneous multiprocessor simulation was developed using SystemC/C++ language. Various design variations were implemented and evaluated using standard task graphs. Performance evaluation metrics are evaluated and discussed for various design scenarios. 1. Introduction Current uniprocessor systems guarantee high processor utilization; however, they fall short in meeting critical real time demands that require (1) high data throughput, (2) fast processing time, (3) low energy and power consumptions, and (4) fault tolerance. Present-day applications that run on embedded or uniprocessor systems, such as multimedia, digital signal processing, image processing, and wireless communication, require an ever-growing amount of resources and speed for data processing and storage, which can no longer be satisfied by uniprocessor systems [1]. The increasing performance demand dictates the need for concurrent task processing on multiprocessor systems. Multiprocessor SoC (MpSoC) systems have emerged as a viable alternate to address the bottlenecks of uniprocessor systems. In an effort to improve the processing performance, multiprocessor systems incorporate a number of processors or processing elements
References
[1]
L. Thiele, I. Bacivarov, W. Haid, and K. Huang, “Mapping applications to tiled multiprocessor embedded systems,” in Proceedings of the 7th International Conference on Application of Concurrency to System Design (ACSD '07), pp. 29–40, July 2007.
[2]
C. Neeb and N. Wehn, “Designing efficient irregular networks for heterogeneous systems-on-chip,” Journal of Systems Architecture, vol. 54, no. 3-4, pp. 384–396, 2008.
[3]
S. Manolache, P. Eles, and Z. Peng, Real-Time Applications with Stochastic Task Execution Times, Analysis and Optimization, Springer, 1st edition, 2007.
[4]
W. Wolf, High-Performance Embedded Computing, Elsevier, 20072007.
[5]
A. A. Jerraya and W. Wolf, Multiprocessor Systems-on-Chips, Morgan Kaufmann Series in Systems on Silicon, 2005.
[6]
J. Nurmi, H. Tenhunen, J. Isoaho, and A. Jantsch, Interconnect-Centric Design for Advanced SoC and NoC, Kluwer Academic, 2004.
[7]
N. D. Thai, “Real-time scheduling in distributed systems,” in Proceedings of the IEEE International Conference on Parallel Computing in Electrical Engineering (PARELEC '02), pp. 165–170, 2002.
[8]
R. Marculescu, U. Y. Ogras, L. S. Peh, N. E. Jerger, and Y. Hoskote, “Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 3–21, 2009.
[9]
G. De Micheli and L. Benini, Networks on Chips: Technology and Tools Systems on Silicon, Academic Press, 2006.
[10]
R. Marculescu and P. Bogdan, “The Chip is the network: toward a science of network-on-chip design,” Foundations and Trends in Electronic Design Automation, vol. 2, no. 4, pp. 371–461, 2007.
[11]
S. Stuijk, T. Basten, M. Geilen, A. H. Ghamarian, and B. Theelen, “Resource-efficient routing and scheduling of time-constrained network-on-chip communication,” in Proceedings of the 9th EUROMICRO Conference on Digital System Design: Architectures, Methods and Tools (DSD '06), pp. 45–52, September 2006.
[12]
J. Hu and R. Marculescu, “Communication and task scheduling of application-specific networks-on-chip,” Proceedings of the IEEE, vol. 152, no. 5, pp. 643–651, 2005.
[13]
G. Varatkar and R. Marculescu, “Communication-aware task scheduling and voltage selection for total systems energy minimization,” in International Conference on Computer Aided Design (ICCAD '03), pp. 510–517, San Jose, Calif, USA, November 2003.
[14]
S. Zhang, K. S. Chatha, and G. Konjevod, “Approximation algorithms for power minimization of earliest deadline first and rate monotonic schedules,” in Proceedings of the International Symposium on Low Power Electronics and Design (ISLPED '07), pp. 225–230, August 2007.
[15]
F. Gruian, “Hard real-time scheduling for low-energy using stochastic data and DVS processors,” in Proceedings of the International Symposium on Low Electronics and Design (ISLPED '01), pp. 46–51, August 2001.
[16]
M. T. Schmitz, B. M. Al-Hashimi, and P. Eles, “Iterative schedule optimization for voltage scalable distributed embedded systems,” Journal ACM Transactions on Embedded Computing Systems, vol. 3, no. 1, pp. 182–217, 2004.
[17]
D. Shin and J. Kim, “Power-aware communication optimization for networks-on-chips with voltage scalable links,” in International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS '04), pp. 170–175, September 2004.
[18]
E. Carvalho, N. Calazans, and F. Moraes, “Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs,” in Proceedings of the 18th IEEE/IFIP International Workshop on Rapid System Prototyping (RSP '07), pp. 34–40, May 2007.
[19]
H. J. Ahn, M. H. Cho, M. J. Jung, Y. H. Kim, J. M. Kim, and C. H. Lee, “UbiFOS; a small real-time operating system for embedded systems,” ETRI Journal, vol. 29, no. 3, pp. 259–269, 2007.
[20]
C. Ostler and K. S. Chatha, “An ILP formulation for system-level application mapping on network processor architectures,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE '07), pp. 99–104, April 2007.
[21]
H. M. Harmanani and R. Farah, “A method for efficient mapping and reliable routing for NoC architectures with minimum bandwidth and area,” in Proceedings of the Joint IEEE North-East Workshop on Circuits and Systems and TAISA Conference (NEWCAS-TAISA '08), pp. 29–32, June 2008.
[22]
J. Hu and R. Marculescu, “Energy- and performance-aware mapping for regular NoC architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 4, pp. 551–562, 2005.
[23]
S. Murali and G. De Micheli, “Bandwidth-constrained mapping of cores onto NoC architectures,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE '04), pp. 896–901, February 2004.
[24]
P. Poplavko, T. Basten, M. Bekooij, J. Van Meerbergen, and B. Mesman, “Task-level timing models for guaranteed performance in multiprocessor networks-on-chip,” in Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '03), pp. 63–72, November 2003.
[25]
G. Ascia, V. Catania, and M. Palesi, “Multi-objective mapping for mesh-based NoC architectures,” in Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS '04), pp. 182–187, September 2004.
[26]
K. Srinivasan and K. S. Chatha, “A technique for low energy mapping and routing in network-on-chip architectures,” in Proceedings of the International Symposium on Low Power Electronics and Design, pp. 387–392, August 2005.
[27]
P. Brucker, Scheduling Algorithms, 5th edition, 2006.
[28]
X. Zhu and W. Qin, “Prototyping a fault-tolerant multiprocessor SoC with run-time fault recovery,” in Proceedings of the 43rd Annual Design Automation Conference (DAC '06), pp. 53–56, 2006.
[29]
R. Holsmark, M. Palesi, and S. Kumar, “Deadlock free routing algorithms for mesh topology NoC systems with regions,” in Proceedings of the 9th EUROMICRO Conference on Digital System Design: Architectures, Methods and Tools (DSD '06), pp. 696–703, September 2006.
[30]
M. Pirretti, G. M. Link, R. R. Brooks, N. Vijaykrishnan, M. Kandemir, and M. J. Irwin, “Fault tolerant algorithms for network-on-chip interconnect,” in Proceedings of the IEEE Computer Society Annual Symposium on VLSI: Emerging Trends in VLSI Systems Design, pp. 46–51, February 2004.
[31]
D. Bertozzi, L. Benini, and G. De Micheli, “Error control schemes for on-chip communication links: the energy-reliability tradeoff,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 24, no. 6, pp. 818–831, 2005.
[32]
F. Angiolini, D. Atienza, S. Murali, L. Benins, and G. De Micheli, “Reliability support for on-chip memories using Networks-on-Chip,” in Proceedings of the 24th International Conference on Computer Design (ICCD '06), pp. 389–396, October 2006.
[33]
V. Puente, J. A. Gregorio, F. Vallejo, and R. Beivide, “Immunet: a cheap and robust fault-tolerant packet routing mechanism,” in Proceedings of the 31st Annual International Symposium on Computer Architecture, pp. 198–209, June 2004.
[34]
A. Pullini, F. Angiolini, D. Bertozzi, and L. Benini, “Fault tolerance overhead in network-on-chip flow control schemes,” in proceedings of the 18th Symposium on Integrated Circuits and Systems Design (SBCCI '05), pp. 224–229, September 2005.
[35]
P. Beerel and M. E. Roncken, “Low power and energy efficient asynchronous design,” Journal of Low Power Electronics, vol. 3, no. 3, pp. 234–253, 2007.
[36]
M. Koibuchi, H. Matsutani, H. Amano, and T. M. Pinkston, “A lightweight fault-tolerant mechanism for network-on-chip,” in Proceedings of the 2nd IEEE International Symposium on Networks-on-Chip (NOCS '08), pp. 13–22, April 2008.
[37]
P. Bogdan, T. Dumitra？, and R. Marculescu, “Stochastic communication: a new paradigm for fault-tolerant Networks-on-chip,” VLSI Design, vol. 2007, Article ID 95348, 17 pages, 2007.
[38]
S. Murali and G. De Micheli, “SUNMAP: a tool for automatic topology selection and generation for NoCs,” in Proceedings of the 41st Design Automation Conference (DAC '04), pp. 914–919, June 2004.
[39]
A. Jalabert, S. Murali, L. Benini, and G. De Micheli, “Xpipescompiler: a tool for instantiating application specific networks on chip,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE '04), pp. 884–889, February 2004.
[40]
Z. Lu, R. Thid, M. Millberg, E. Nilsson, and A. Jantsch, “NNSE: nostrum network-on-chip simulation environment,” in Proceedings of the Swedish System-on-Chip Conference (SSoCC '03), April 2005.
[41]
S. Mahadevan, M. Storgaard, J. Madsen, and K. Virk, “ARTS: a system-level framework for modeling MPSoC components and analysis of their causality,” in Proceedings of the 13th IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunications Systems (MASCOTS '05), pp. 480–483, September 2005.
[42]
P. G. Paulin, C. Pilkington, and E. Bensoudane, “StepNP: a system-level exploration platform for network processors,” IEEE Design and Test of Computers, vol. 19, no. 6, pp. 17–26, 2002.
[43]
N. Genko, D. Atienza, G. De Micheli, J. M. Mendias, R. Hermida, and F. Catthoor, “A complete network-on-chip emulation framework,” in Proceedings of the Design, Automation and Test in Europe (DATE '05), pp. 246–251, March 2005.
[44]
M. Coppola, S. Curaba, M. D. Grammatikakis, G. Maruccia, and F. Papariello, “OCCN: a network-on-chip modeling and simulation framework,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, DATE 04, vol. 3, pp. 174–179, February 2004.
[45]
C. A. Zeferino and A. A. Susin, “SoCIN: a parametric and scalable Network-on-Chip,” in Proceedings of the 16th Symposium on Integrated Circuits and Systems Design, pp. 169–174, 2003.
[46]
H. Orsila, E. Salminen, M. H？nnik？inen, and T. D. H？m？l？inen, “Evaluation of heterogeneous multiprocessor architectures by energy and performance optimization,” in Proceedings of the International Symposium on System-on-Chip (SOC '08), pp. 1–6, November 2008.
[47]
H. Orsila, T. Kangas, E. Salminen, T. D. H？m？l？inen, and M. H？nnik？inen, “Automated memory-aware application distribution for Multi-processor System-on-Chips,” Journal of Systems Architecture, vol. 53, no. 11, pp. 795–815, 2007.
[48]
F. Paterna, L. Benini, A. Acquaviva, F. Papariello, and G. Desoli, “Variability-tolerant workload allocation for MPSoC energy minimization under real-time constraints,” in Proceedings of the IEEE/ACM/IFIP 7th Workshop on Embedded Systems for Real-Time Multimedia (ESTIMedia '09), pp. 134–142, October 2009.
[49]
R. Teodorescu and J. Torrellas, “Variation-aware application scheduling and power management for chip multiprocessors,” ACM SIGARCH Computer Architecture News, vol. 36, no. 3, pp. 363–374, 2008.
[50]
Z. Lide, L. S. Bai, R. P. Dick, S. Li, and R. Joseph, “Process variation characterization of chip-level multiprocessors,” in Proceedings of the 46th ACM/IEEE Design Automation Conference (DAC '09), pp. 694–697, New York, NY, USA, July 2009.
[51]
“Embedded System Synthesis Benchmarks Suite (E3S),” http://ziyang.eecs.umich.edu/~dickrp/e3s/.
[52]
C. Ababei and R. Katti, “Achieving network on chip fault tolerance by adaptive remapping,” in Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS '09), pp. 23–29, May 2009.
[53]
O. Derin, D. Kabakci, and L. Fiorin, “Online task remapping strategies for fault-tolerant network-on-chip multiprocessors,” in Proceedings of the 5th ACM/IEEE International Symposium on Networks-on-Chip (NOCS '11), pp. 129–136, May 2011.
