Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Nearest neighbor affinity scheduling in heterogeneous multi-core architectures
Keywords:
asymmetric multiprocessors, multi-core architectures, thread schedulingAbstract
Asymmetric or heterogeneous multi-core (AMC) architectures have definite performance, performance per watt and fault tolerance advantages for a wide range of workloads. We propose a 16 core AMC architecture mixing simple and complex cores, and single and multiple thread cores of various power envelopes. A priority-based thread scheduling algorithm is also proposed for this AMC architecture. Fairness of this scheduling algorithm vis-a-vis lower priority thread starvation, and hardware and software requirements needed to implement this algorithm are addressed. We illustrate how this algorithm operates by a thread scheduling example. The produced schedule maximizes throughput (but is priority-based) and the core utilization given the available resources, the states and contents of the starting queues, and the threads' core requirement constraints. A simulation model simulates 6 scheduling algorithms which vary in their support of core affinity and thread migration. The simulation results that both core affinity and thread migration positively effect the completion time and that the nearest neighbor scheduling algorithm outperforms or is competitive with the other algorithms in all considered scenarios
Downloads
Download data is not yet available.
References
[1] P., Dubey, CMP Challenges, ICCD Panel, IEEE Int. Conf. on Computer Design, 2005.
[2] S. Balakrishnan et al., The Impact of Performance Asymmetry in Emerging Multicore Architectures, Proc. of 32nd ISCA, 2005.
[3] R. Kumar et al., Heterogeneous Chip Multiprocessors, IEEE Computer, 2005.
[4] F. N. Sibai, Dissecting the PC Mark05 Benchmarkand Assessing Performance Scaling, Proc. of 3rd IEEE Conf. on Innovations in Info. Tech., 2006.
[5] L. Hammond et al., A Single-Chip Multiprocessor, IEEE Computer, Volume 30, No. 9, 1997.
[6] R. Kalla et al., IBM POWER5 Chip: A Dual-Core Multithreaded Processor, IEEE Micro, 2004.
[7] P. Kongetira et al., Niagara: A 32-way Multithreaded SPARC Processor, IEEE Micro, 2005.
[8] C. McNairy and R. Bhatia, Montecito: A Dual-Core, Dual-Thread Itanium Processor, IEEE Micro, 2005.
[9] T. Constantinou et al., Performance Implications of Single Thread Migration on a Chip Multi-Core,ACM Comp. Architecture News, Vol. 33 (4), 2005.
[10] K. Shaw et al., Migration in Single Chip Multiprocessors, Comp. Arch. Letters.Vol. 1, No. 3, 2002.
[11] H. Abdel-Shafi et al. Efficient User-Level Checkpointing and Thread Migration in Windows NT Clusters, 3rd Usenix Windows NT Symp., 1999.
[12] R. Avnur et al, Thread Migration in the River Dataflow Environment, University of California Berkeley CS Dept. Technical Report.
[13] S. Hily et al., Contention on 2nd Level Cache May Limit The Effectiveness of Simultaneous Multithreading, INRIA Report # 1086, 1997.
[14] S. Kim et al., Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proc of the 13th IEEE PACT04, 2004.
[15] D. Chandra, et al., Predicting Inter-thread Cache Contention on a Chip Multi-Processor Architecture, Proc of the IEEE HPCA-11, 2005.
[16] A. Fedorova et al., Cache-Fair Thread Scheduling for Multicore Processors, Technical Report TR-17-06, Harvard University, 2006.
[17] A. Silberschatz et al, Operating Systems Concepts, John Wiley and Sons, 2004.
[2] S. Balakrishnan et al., The Impact of Performance Asymmetry in Emerging Multicore Architectures, Proc. of 32nd ISCA, 2005.
[3] R. Kumar et al., Heterogeneous Chip Multiprocessors, IEEE Computer, 2005.
[4] F. N. Sibai, Dissecting the PC Mark05 Benchmarkand Assessing Performance Scaling, Proc. of 3rd IEEE Conf. on Innovations in Info. Tech., 2006.
[5] L. Hammond et al., A Single-Chip Multiprocessor, IEEE Computer, Volume 30, No. 9, 1997.
[6] R. Kalla et al., IBM POWER5 Chip: A Dual-Core Multithreaded Processor, IEEE Micro, 2004.
[7] P. Kongetira et al., Niagara: A 32-way Multithreaded SPARC Processor, IEEE Micro, 2005.
[8] C. McNairy and R. Bhatia, Montecito: A Dual-Core, Dual-Thread Itanium Processor, IEEE Micro, 2005.
[9] T. Constantinou et al., Performance Implications of Single Thread Migration on a Chip Multi-Core,ACM Comp. Architecture News, Vol. 33 (4), 2005.
[10] K. Shaw et al., Migration in Single Chip Multiprocessors, Comp. Arch. Letters.Vol. 1, No. 3, 2002.
[11] H. Abdel-Shafi et al. Efficient User-Level Checkpointing and Thread Migration in Windows NT Clusters, 3rd Usenix Windows NT Symp., 1999.
[12] R. Avnur et al, Thread Migration in the River Dataflow Environment, University of California Berkeley CS Dept. Technical Report.
[13] S. Hily et al., Contention on 2nd Level Cache May Limit The Effectiveness of Simultaneous Multithreading, INRIA Report # 1086, 1997.
[14] S. Kim et al., Fair Cache Sharing and Partitioning in a Chip Multiprocessor Architecture, Proc of the 13th IEEE PACT04, 2004.
[15] D. Chandra, et al., Predicting Inter-thread Cache Contention on a Chip Multi-Processor Architecture, Proc of the IEEE HPCA-11, 2005.
[16] A. Fedorova et al., Cache-Fair Thread Scheduling for Multicore Processors, Technical Report TR-17-06, Harvard University, 2006.
[17] A. Silberschatz et al, Operating Systems Concepts, John Wiley and Sons, 2004.
Downloads
Published
2008-10-01
How to Cite
Sibai, F. N. (2008). Nearest neighbor affinity scheduling in heterogeneous multi-core architectures. Journal of Computer Science and Technology, 8(03), p. 144–150. Retrieved from https://journal.info.unlp.edu.ar/JCST/article/view/756
Issue
Section
Original Articles
