CC-NUMA系统中Cache一致性协议模拟验证方法研究
|
摘要
Cache一致性协议作为CC-NUMA(Cache Coherency Non-Uniform Memory Access)系统的硬件基础,在系统设计过程中占有举足轻重的地位。大规模的CC-NUMA系统往往采用复杂的多层Cache一致性协议,通常难以对这种复杂协议进行完全形式化验证,因此软件模拟验证仍然在大规模CC-NUMA系统的Cache一致性协议验证中扮演着重要角色。
本文针对某型CC-NUMA系统,重点研究了对其Cache一致性协议进行模拟验证的问题。设计了一套覆盖率驱动的高效Cache一致性协议模拟验证方法,并使用SystemC实现了验证系统。本文的主要工作和贡献如下:
1.在分析目标系统协议表的基础上设计了一套覆盖率驱动的Cache一致性协议伪随机模拟验证方法;
2.使用SystemC语言实现了全系统模拟器。在此基础上,为了加速模拟器执行,针对验证目标系统的特点,提出了一种基于MPI并行函数库的SystemC模拟应用分布式并行化方法,并基于此方法设计实现了一个支持模拟验证系统并行执行的分布式并行系统模拟器;
3.基于朴素贝叶斯方法提出了一种用于测试激励自动生成的有效测试激励分类算法。使用此算法设计并实现了一个有效测试激励分类器,并将其应用到验证系统中。该分类器将随机产生的测试激励中不具有运行价值的无效测试激励滤除,提高了测试激励的产生效率;
4.基于相关分析提出了一种用于测试激励自动生成的验证结果快速扩展算法。使用此算法设计并实现了一个验证结果扩展器,并将其应用到验证系统中。该验证结果扩展器对已运行过的测试激励施加偏置,通过运行带偏置的测试激励,快速覆盖已被覆盖验证目标的相似项目。
基于上述研究成果建立的完整高效率Cache一致性协议验证系统已经成功的应用于某型CC-NUMA系统的Cache一致性协议验证工作中,应用结果表明了本文方法的有效性。
As the hardware foundation of the CC-NUMA (Cache Coherency Non-Uniform Memory Access) system, cache coherence protocol plays a vital role in the system design process. Large-scale CC-NUMA systems are often the use of complex multi-layered Cache coherence protocol; it is difficult to perform formal verification to the cache coherence protocol because of its great complexity, and the traditional pseudo-random simulation verification still play important role in CC-NUMA system verification.
In this paper, we focus on the cache coherence protocol verification methods of a certain type CC-NUMA systems. A high efficient systems simulator based on SystemC simulator has been designed and implemented. The main work and contribution of this paper is as follows:
1. A set of coverage-driven pseudo-random simulation Cache coherence protocol verification method has been designed based on the analysis of the target system protocol table.
2. Using the SystemC language to implement full-system simulator. And based on it, a parallel MPI-based library of SystemC simulation of a distributed parallel application method has been proposed for speed up the execution of the simulator. A verification system which support distributed parallel execution has been designed and implemented Based on this method.
3. A test stimulus automatically generated classification algorithm based on naive Bayesian classifiers has been presented, a test stimulus classifier based on it has been design and implement. The classifier screen out the high value of run incentive from the pseudo-random generated verification stimulus to improve the generate efficiency of them.
4. Based on correlation analysis presents a rapid expansion algorithm for testing results. A test results expander based on it has been design and implement. It applies bias to the run-off verification stimulus; make a fast cover the results of similar projects have been covered by running the biased verification stimulus.
Based on the above research, a high-efficiency verification system has been successfully established and applied to the verification work of a certain type of complex CC-NUMA system; the application results show the effectiveness of this method.
本文针对某型CC-NUMA系统,重点研究了对其Cache一致性协议进行模拟验证的问题。设计了一套覆盖率驱动的高效Cache一致性协议模拟验证方法,并使用SystemC实现了验证系统。本文的主要工作和贡献如下:
1.在分析目标系统协议表的基础上设计了一套覆盖率驱动的Cache一致性协议伪随机模拟验证方法;
2.使用SystemC语言实现了全系统模拟器。在此基础上,为了加速模拟器执行,针对验证目标系统的特点,提出了一种基于MPI并行函数库的SystemC模拟应用分布式并行化方法,并基于此方法设计实现了一个支持模拟验证系统并行执行的分布式并行系统模拟器;
3.基于朴素贝叶斯方法提出了一种用于测试激励自动生成的有效测试激励分类算法。使用此算法设计并实现了一个有效测试激励分类器,并将其应用到验证系统中。该分类器将随机产生的测试激励中不具有运行价值的无效测试激励滤除,提高了测试激励的产生效率;
4.基于相关分析提出了一种用于测试激励自动生成的验证结果快速扩展算法。使用此算法设计并实现了一个验证结果扩展器,并将其应用到验证系统中。该验证结果扩展器对已运行过的测试激励施加偏置,通过运行带偏置的测试激励,快速覆盖已被覆盖验证目标的相似项目。
基于上述研究成果建立的完整高效率Cache一致性协议验证系统已经成功的应用于某型CC-NUMA系统的Cache一致性协议验证工作中,应用结果表明了本文方法的有效性。
As the hardware foundation of the CC-NUMA (Cache Coherency Non-Uniform Memory Access) system, cache coherence protocol plays a vital role in the system design process. Large-scale CC-NUMA systems are often the use of complex multi-layered Cache coherence protocol; it is difficult to perform formal verification to the cache coherence protocol because of its great complexity, and the traditional pseudo-random simulation verification still play important role in CC-NUMA system verification.
In this paper, we focus on the cache coherence protocol verification methods of a certain type CC-NUMA systems. A high efficient systems simulator based on SystemC simulator has been designed and implemented. The main work and contribution of this paper is as follows:
1. A set of coverage-driven pseudo-random simulation Cache coherence protocol verification method has been designed based on the analysis of the target system protocol table.
2. Using the SystemC language to implement full-system simulator. And based on it, a parallel MPI-based library of SystemC simulation of a distributed parallel application method has been proposed for speed up the execution of the simulator. A verification system which support distributed parallel execution has been designed and implemented Based on this method.
3. A test stimulus automatically generated classification algorithm based on naive Bayesian classifiers has been presented, a test stimulus classifier based on it has been design and implement. The classifier screen out the high value of run incentive from the pseudo-random generated verification stimulus to improve the generate efficiency of them.
4. Based on correlation analysis presents a rapid expansion algorithm for testing results. A test results expander based on it has been design and implement. It applies bias to the run-off verification stimulus; make a fast cover the results of similar projects have been covered by running the biased verification stimulus.
Based on the above research, a high-efficiency verification system has been successfully established and applied to the verification work of a certain type of complex CC-NUMA system; the application results show the effectiveness of this method.
引文
[1] Olukotun, K. Chip Multiprocessor Architecture: Techniques to Improve Throughput and Latency. San Rafael, CA: Morgan and Claypool Publishers. 2007. ISBN 1-598-29122-X
[2] Marty, M. R., Bingham, J. D., Hill, M. D., Hu, A. J., Martin, M. M., and Wood, D. A. Improving Multiple-CMP Systems Using Token Coherence. In Proceedings of the 11th international Symposium on High-Performance Computer Architecture (HPCA2005). 2005
[3] Carl Pixley, Noel R. Strader, W. C. Bruce, Jaehong Park, Matt Kaufmann, Kurt Shultz, Michael Burns, Jai Kumar, Jun Yuan, Janet Nguyen. Commercial design verification: methodology and tools. International Test Conference.1996
[4]李暾.VLSI RTL级测试程序自动生成技术研究: [博士学位论文].长沙:国防科技大学计算机学院.2003.9.
[5] Fong Pong and Michel Dubois. Verification Techniques for Cache Coherence Protocols. ACM Computing Surveys, 1997, 29(1):82–126.
[6] Mark Glasser, Adam Rose, Tom Fitzpatrick, Dave Rich, Harry Foster著,王欣,俞俊,罗开杰,秦贤智,钟文枫译.高级验证方法学.成都:电子科技大学出版社.2007
[7] Serdar Tasiran, Kurt Keutzer. Coverage metrics for functional validation of hardware designs. IEEE Design & Test of Computers, 2001, 18(4): 36~45.
[8] SM Plaza, IL Markov, V Bertacco. Random Stimulus Generation using Entropy and XOR Constraints Design. Automation and Test in Europe, 2008.
[9] O'Krafka B, Mandyam S, Kreulen J, Raghavan R., Saha A, Malik N. MPTG: A portable test generator for cache-coherent multiprocessors. In Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference: 38–44. 1995.
[10] Aharon Aharon, Dave Goodman, Moshe Levinger, Yossi Lichtenstein, Yossi Malka, Charlotte Metzger, Moshe Molcho, Gil Shurek. Test Program Generation for Functional Verification of PowerPC Processors in IBM. DAC, 1995.
[11]张振军,毛志刚,基于伪随机的微处理器验证方法及改进.信息技术.2008.32(10)
[12]易江芳,佟冬,程旭.GATEST:使用遗传算法自动生成模拟矢量的验证平台.北京大学学报(自然科学版).2006.42(05)
[13] The Mentor Functional Verification platform. http://www.mentor.com/products/fv/. 2009.7
[14] http://www.cadence.com/products/fv/Pages/default.aspx. 2009. 7
[15] Discovery Verification Platform. http://www.synopsys.com/Solutions/EndSolutions/DiscoveryVerifDiscove/Pages/default.aspx. 2009.7
[16] http://www.obsidiansoft.com/. 2009. 7
[17] J.Bhasker著,夏宇闻,甘伟译.SystemC入门,第2版.北京:北京航空航天大学出版社,2008.9
[18] http://www.systemc.org/. 2009.8
[19] Gr?tker, T., Liao, S., Martin, G., Swan, S. System Design with SystemC. Berlin:Springer. 2002. ISBN: 978-1-4020-7072-3
[20] B. Chopard, P. Combes and J. Zory. A Conservative Approach to SystemC Parallelization. Computational Science– ICCS 2006. 2006.
[21] V. Galiano, H. Migallón, D. Pérez-Caparrós, J. A. Palomino and M. Martínez. Speeding Up in Distributed SystemC Simulations. International Symposium on Distributed Computing and Artificial Intelligence 2008 (DCAI 2008). 2008
[22]蔡自兴,徐光祐.人工智能及其应用,第二版.北京:清华大学出版社.1996
[23] Stuart Russell, Peter Norvig著.姜哲,金奕江,张敏,杨磊等译.人工智能,一种现代方法,第二版.北京:人民邮电出版社.2004
[24] http://en.wikipedia.org/wiki/Functional_verification. 2009. 8
[25]王建国,吴建平.基于扩展有限状态机的协议测试集生成研究.软件学报,2001, 12(8): 1197-1204.
[26] Cheng, K. and Krishnakumar, A. S. Automatic generation of functional vectors using the extended finite state machine model. ACM Trans. Des. Autom. Electron. Syst, 1996, 1(1):57-79.
[27] Andrew Piziali. Functional Verification Coverage Measurement and Analysis. Berlin: Springer. 2004.
[28] S. Tasiran and K. Keutzer. Coverage metrics for functional validation of hardware designs. IEEE Design and Test of Computers, 2001, 18(4):36–45.
[29] Donna Mitchell.Manual and Automatic VHDL/Verilog Test Bench Coding Techniques. Dedicated Systems Magazine, 2001, Q2
[30]都志辉著,李三立审阅,陈渝,刘鹏校对.高性能计算之并行编程技术——MPI并行程序设计.2001.2.
[31] Amdahl, Gene. Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. AFIPS Conference Proceedings (30): 483–485.
[32] Tom M.Mitchell著,曾华军,张银奎等译.机器学习.北京:机械工业出版社.2003
[33] Ta-Chung Chang, Vikram Iyengar and Elizabeth M. Rudnick. A Biased Random Instruction Generation Environment for Architectural Verification of Pipelined Processors. Journal of Electronic Testing, 2006, 16(1-2): 13-27.
[34] Chinnery, David G. A Functional Validation Technique: Biased-Random Simulation Guided by Observability-Based Coverage. ICCD '01: Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, 2001:82.
[2] Marty, M. R., Bingham, J. D., Hill, M. D., Hu, A. J., Martin, M. M., and Wood, D. A. Improving Multiple-CMP Systems Using Token Coherence. In Proceedings of the 11th international Symposium on High-Performance Computer Architecture (HPCA2005). 2005
[3] Carl Pixley, Noel R. Strader, W. C. Bruce, Jaehong Park, Matt Kaufmann, Kurt Shultz, Michael Burns, Jai Kumar, Jun Yuan, Janet Nguyen. Commercial design verification: methodology and tools. International Test Conference.1996
[4]李暾.VLSI RTL级测试程序自动生成技术研究: [博士学位论文].长沙:国防科技大学计算机学院.2003.9.
[5] Fong Pong and Michel Dubois. Verification Techniques for Cache Coherence Protocols. ACM Computing Surveys, 1997, 29(1):82–126.
[6] Mark Glasser, Adam Rose, Tom Fitzpatrick, Dave Rich, Harry Foster著,王欣,俞俊,罗开杰,秦贤智,钟文枫译.高级验证方法学.成都:电子科技大学出版社.2007
[7] Serdar Tasiran, Kurt Keutzer. Coverage metrics for functional validation of hardware designs. IEEE Design & Test of Computers, 2001, 18(4): 36~45.
[8] SM Plaza, IL Markov, V Bertacco. Random Stimulus Generation using Entropy and XOR Constraints Design. Automation and Test in Europe, 2008.
[9] O'Krafka B, Mandyam S, Kreulen J, Raghavan R., Saha A, Malik N. MPTG: A portable test generator for cache-coherent multiprocessors. In Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference: 38–44. 1995.
[10] Aharon Aharon, Dave Goodman, Moshe Levinger, Yossi Lichtenstein, Yossi Malka, Charlotte Metzger, Moshe Molcho, Gil Shurek. Test Program Generation for Functional Verification of PowerPC Processors in IBM. DAC, 1995.
[11]张振军,毛志刚,基于伪随机的微处理器验证方法及改进.信息技术.2008.32(10)
[12]易江芳,佟冬,程旭.GATEST:使用遗传算法自动生成模拟矢量的验证平台.北京大学学报(自然科学版).2006.42(05)
[13] The Mentor Functional Verification platform. http://www.mentor.com/products/fv/. 2009.7
[14] http://www.cadence.com/products/fv/Pages/default.aspx. 2009. 7
[15] Discovery Verification Platform. http://www.synopsys.com/Solutions/EndSolutions/DiscoveryVerifDiscove/Pages/default.aspx. 2009.7
[16] http://www.obsidiansoft.com/. 2009. 7
[17] J.Bhasker著,夏宇闻,甘伟译.SystemC入门,第2版.北京:北京航空航天大学出版社,2008.9
[18] http://www.systemc.org/. 2009.8
[19] Gr?tker, T., Liao, S., Martin, G., Swan, S. System Design with SystemC. Berlin:Springer. 2002. ISBN: 978-1-4020-7072-3
[20] B. Chopard, P. Combes and J. Zory. A Conservative Approach to SystemC Parallelization. Computational Science– ICCS 2006. 2006.
[21] V. Galiano, H. Migallón, D. Pérez-Caparrós, J. A. Palomino and M. Martínez. Speeding Up in Distributed SystemC Simulations. International Symposium on Distributed Computing and Artificial Intelligence 2008 (DCAI 2008). 2008
[22]蔡自兴,徐光祐.人工智能及其应用,第二版.北京:清华大学出版社.1996
[23] Stuart Russell, Peter Norvig著.姜哲,金奕江,张敏,杨磊等译.人工智能,一种现代方法,第二版.北京:人民邮电出版社.2004
[24] http://en.wikipedia.org/wiki/Functional_verification. 2009. 8
[25]王建国,吴建平.基于扩展有限状态机的协议测试集生成研究.软件学报,2001, 12(8): 1197-1204.
[26] Cheng, K. and Krishnakumar, A. S. Automatic generation of functional vectors using the extended finite state machine model. ACM Trans. Des. Autom. Electron. Syst, 1996, 1(1):57-79.
[27] Andrew Piziali. Functional Verification Coverage Measurement and Analysis. Berlin: Springer. 2004.
[28] S. Tasiran and K. Keutzer. Coverage metrics for functional validation of hardware designs. IEEE Design and Test of Computers, 2001, 18(4):36–45.
[29] Donna Mitchell.Manual and Automatic VHDL/Verilog Test Bench Coding Techniques. Dedicated Systems Magazine, 2001, Q2
[30]都志辉著,李三立审阅,陈渝,刘鹏校对.高性能计算之并行编程技术——MPI并行程序设计.2001.2.
[31] Amdahl, Gene. Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. AFIPS Conference Proceedings (30): 483–485.
[32] Tom M.Mitchell著,曾华军,张银奎等译.机器学习.北京:机械工业出版社.2003
[33] Ta-Chung Chang, Vikram Iyengar and Elizabeth M. Rudnick. A Biased Random Instruction Generation Environment for Architectural Verification of Pipelined Processors. Journal of Electronic Testing, 2006, 16(1-2): 13-27.
[34] Chinnery, David G. A Functional Validation Technique: Biased-Random Simulation Guided by Observability-Based Coverage. ICCD '01: Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, 2001:82.