Abstract
The overall performance of single-ISA heterogeneous multi-core processors (HMPs) heavily relies on the efficiency of scheduling algorithm. However, traditional scheduling algorithms either treat all cores equally, or assume all cores complying with a strict order in the amount of microarchitecture resources, thus it is unsuitable for increasingly diverse HMPs, where different cores may have different advantages and preferences.
To efficiently schedule single-ISA HMPs, we propose a novel stable matching scheduler based on the matching game theory. The proposed scheduler can always lead to a stable matching between applications and cores, where there does not exist an alternative application-core pair in which both the application and the core prefer each other rather than their current partners. Experimental results demonstrate that the stable matching scheduler beats previous schedules. For example, the stable matching scheduler improves, on average, the performance against the random scheduler by 19.86 % (4-core), 18.78 % (6-core), 22.78 % (8-core).
Supported by the National Sci&Tech Major Project (No.2009ZX01028-002-003, 2009ZX01029-001-003, 2010ZX01036-001-002, 2012ZX01029-001-002-002, 2014ZX01020201, 2014ZX01030101), National Natural Science Foundation of China (No.61221062, 61133004, 61173001, 61232009, 61222204, 61432016), the National High Technology Development 863 Program of China (2012AA010901, 2013AA014301)
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
A time interval contains unfixed number of instructions, which is different with definition of sampling phase in the ANN training stage. Scheduling by time interval promises us to schedule different phases with the sample in the offline training.
- 2.
Since all Processors in the HMPs system may have different microarchitectures, we need N different sets of weights.
- 3.
The linea interpolation units are leveraged to approximately calculate the outputs of active function (e.g. sigmoid or tanh).
References
Sherwood, T., Sair, S., Calder, B.: Phase tracking and prediction. In: the 30th Annual International Symposium on Computer Architecture (ISCA2003), pp. 336–347. ACM, New York (2003)
big.LITTLE processing with ARM Cortex-A15 & Cortex-A7: Improving energy efficiency in high-performance mobile paltform. http://www.arm.com/files/downloads/big_LITTLE_Final_Final.pdf
Variable SMP a multi-core CPU architecture for low power and high performance. http://www.nvidia.com/content/PDF/tegra_white_papers/Variable-SMP-A-Multi-Core-CPU-Architecture-for-Low-Power-and-High-Performance-v1.1.pdf
The future is fusion: The industry-changing impact of accelerated computing. http://sites.amd.com/us/Documents/AMD_fusion_Whitepaper.pdf
Kahle, J.A., Day, M.N., Hofstee, H.P., Johns, C.R., Maeurer, T.R., Shippy, D.: Introduction to the cell multiprocessor. IBM J. Res. Dev. - POWER5 Packag. Arch. 49(4), 589–604 (2005). IBM Corp, Riverton
Marco, C., Faniel, P.B.: Understanding the Linux Kernel. O’Reilly Media, Sebastopol (2002)
Kumar, R., Tullsen, D.M., Ranganathan, P., Jouppi, N.P., Farkas, K.I.: Single-ISA heterogeneous multi-core architectures for multithreaded workload performance. In: the 31th Annual International Symposium on Computer Architecture (ISCA2004), pp. 64–75. ACM, New York (2004)
Ghiasi, S., Keller, T., Rawson, F.: Scheduling for heterogeneous processors in server systems. In: the 2nd Conference on Computing Frontiers (CF2005), pp.199–210. ACM, New York (2005)
Becchi, M., Crowley, P.: Dynamic thread assignment on heterogeneous multiprocessor architectures. In: The 3rd Conference on Computing Frontiers (CF2006), pp. 29–40. ACM, New York (2006)
Kumar, R., Tullsen, D.M., Jouppi, N.P.: Core architecture optimization for heterogeneous chip multiprocessors. In: The 15th International Conference on Parallel Architectures and Compilation Techniques (PACT2006), pp. 23–32. ACM, New York (2006)
Rangan, K., Powell, M.D., Wei, G., Brooks, D.: Achieving uniform performance and maximizing throughput in the presence of heterogeneity. In: The 17th International Symposium on High-Performance Computer Architecture (HPCA2011), pp. 3–14. IEEE, San Antonio (2011)
Teodorescu, R., Torrellas, J.: Variation-aware application scheduling and power management for chip multiprocessors. In: The 35th Annual International Symposium on Computer Architecture (ISCA2008), pp. 363–374. IEEE, Beijing (2008)
Koufaty, D., Reddy, D., Hahn, S.: Bias scheduling in heterogeneous multi-core architectures. In: The 5th European Conference on Computer Systems, pp. 125–138. ACM, New York (2010)
Winter, J.A., Albonesi, D.H., Shoemaker, C.A.: Scalable thread scheduling and global power management for heterogeneous many-core architectures. In: the 19th International Conference on Parallel Architectures and Compilation Techniques (PACT2010), pp. 29–40. ACM, New York (2010)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9–15 (1962)
Stable matching: theory, evidence, and practical design. http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/popular-economicsciences2012.pdf
Henning, J.L.: SPEC CPU2006 benchmark descriptions. ACM SIGARCH Comput. Archit. News 34(4), 1–17 (2006). ACM, New York
Weidan, W., Benjamin, C.L.: Inferred models for dynamic and sparse hardware-software spaces. In: The 45th Annual IEEE/ACM International Symposium on Microarchitecture (Micro2012), pp. 413–424. IEEE, Washington (2012)
Shelepov, D., Saez Alcaide, J.C., Jeffery, S., Fedorova, A., Perez, N., Huang, Z.F., Blagodurov, S., Kumar, V.: HASS: a scheduler for heterogeneous multicore systems. ACM SIGOPS Operating Syst. Rev. 43(2), 66–75 (2009). ACM, New York
Shouqing, H., Qi, L., Longbing, Z., Jian, W.: Processes scheduling on heterogeneous multicore architecture with hardware support. In: The 6th International Conference on Networking, Architecture and Storage (NAS2011), pp. 236–241. IEEE, Dalian (2011)
Van, C.K., Jaleel, A., Eeckhout, L., Narvaez, P., Emer, J.: Scheduling heterogeneous multicores through performance impact estimation (PIE). In: the 39th Annual International Symposium on Computer Architecture (ISCA2012), pp. 213–224. IEEE, Portland (2012)
Kenneth, H., Lieven, E.: Microarchitecture-independent workload characterization. IEEE Micro Hot Tutirials 27(3), 63–72 (2007). IEEE
Eranian, S.: Perfmon2: a flexible performance monitoring interface for Linux. In: Ottawa Linux Symposium Proceedings, pp.269–288 (2006)
Suh, G.E., Devadas, S., Rudolph, L.: A new memory monitoring scheme for memory-aware scheduling and partitioning. In: the 18th International Symposium on High-Performance Computer Architecture (HPCA2002), pp. 117–128. IEEE, Boston (2002)
Mericas, A.: Performance monitoring on the POWER5 microprocessor. In: John, L.K., Eeckhout, L. (eds.) Performance Evaluation and Benchmarking, pp.247–266. CRC Press, Boca Raton (2005)
Binkert, N., Beckmann, B., Black, G., et al.: The gem5 simulator. ACM SIGARCH Comput. Archit. News 39(2), 1–7 (2011). ACM, New York
Li, S., Ahn, J.H., Strong, R.D., Brockman, J.B., Tullsen, D.M., Jouppi, N.P.: McPAT: an integrated power, area, and timing modeling framework for multicore and manycore architectures. In: the 42th Annual IEEE/ACM International Symposium on Microarchitecture (Micro2009), pp. 469–480. IEEE, New York (2009)
Powell, M.D., Biswas, A., Gupta, S., Mukherjee, S.: Architectural core salvaging in a multicore processor for hard-error tolerance. ACM SIGARCH Computer Architecture News 37(3), 93–104 (2009). ACM, New York
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Wang , L., Liu, S., Lu, C., Zhang, L., Xiao, J., Wang, J. (2015). Stable Matching Scheduler for Single-ISA Heterogeneous Multi-core Processors. In: Chen, Y., Ienne, P., Ji, Q. (eds) Advanced Parallel Processing Technologies. APPT 2015. Lecture Notes in Computer Science(), vol 9231. Springer, Cham. https://doi.org/10.1007/978-3-319-23216-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-23216-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23215-7
Online ISBN: 978-3-319-23216-4
eBook Packages: Computer ScienceComputer Science (R0)