基于对象的隐式并行编程众核体系结构研究

谭 海

(1.北京理工大学计算机学院，北京100081;2.东华理工大学信息工程学院，江西南昌330013;3.东华理工大学核技术应用教育部工程研究中心，江西南昌330013)

0 引言

目前芯片制造工艺已经具备百亿晶体管的整合能力，且每过两年继续翻倍，出现功耗、片上网络延迟和存储带宽等问题，如何利用芯片上集成的海量晶体管资源设计高性能处理器成为研究的热点。采用多核结构在一定程度有效能够减缓了上述问题，但是晶体管规模数变的过大时，出现过多的亚阈值漏电，导致供应电压按比例下降，系统性能达不到按照摩尔定律所昭示的应有提升，反而产生大功耗问题，多核结构随之遇到瓶颈，唯一的方法就是采用更多的较小单核 (众核)来解决瓶颈问题。

当前的软件结构可以在多核结构上得到较好的扩展，但如果超过八个处理器核，当前软件结构的扩展能力将会很差［1］。Berkele认为未来的并行计算必须有利于传统科学计算的并行化［2］，范东睿研究员指出众核的挑战是供数受限于片外带宽、并行系统难以高效率扩展、并行编程困难［3］，提高应用程序开发产能同时获得并行性能收益是多核大众化并行计算研究的核心目标。微软公司在2007年6月25日在美国西雅图召开第一个以Many-Core为主题的Workshop，讨论众核软件设计应如何开展，并于该年11月发表了THE MANYCORE SHIFT:Microsoft Parallel Computing Initiative Ushers Computing into the Next Era宣言，宣布转入对众核系统软件的研究，基于众核的软件设计成为研究的热点之一。

跟现有多核计算强调专门领域、需要专门知识的程序员不同，众核计算关注通用平台，基本涉及到所有应用领域，支持所有普通程序员进行众核编程开发，即大众化通用并行［4］。具体来说，多核计算关注高性能计算和服务计算领域、采用自底向上的硬件驱动方法、追求性能最大化目标;而众核计算关注个人移动计算、采用自顶向下的应用驱动开发方法、追求最大化产能目标。

1 显式并行编程模式及缺陷

国内外对多核的研究主要是面向计算密集型和数据密集型的专用计算领域，对处理器核的基本结构 (包括指令系统、粒度等)、处理器核之间的互连通信和同步机制 (共享内存、消息传递和数据并行等)、片上存储器的组织形式(局部/全局、Cache/可寻址存储器、SRAM/DRAM等)和多线程的基本机制等的研究［5］。由于一个时钟周期内信号可传输的距离非常有限，处理器核不可能在指令执行期间就完成与其它处理器核的数据通信，不同核处理器之间的通信应该尽可能的采用异步机制且能容忍较长的延迟，不同专用并行机底层硬件和系统软件之间差别较大，这些因素造成了目前的并行程序开发与现有的大众化程序开发之间很大的不同，前者需要通晓底层硬件结构，编译器和专用的并行开发语言的“专家级”程序员，程序开发和维护成本高，并行程序开发过程容易出错，且编写出来的程序不通用，只能在固定的计算机上去运行，程序移植性差，这类需要使用诸如MPI、Charm++等专门并行编程工具的模式称之为显式并行编程模式［6］。在显式编程模式下，为了适应众核硬件并行程序设计，得分别在算法、编程模型、编程语言、编译器和操作系统等方面全套重新设计，这样的变革将是巨大的，成本很大，对普通程序员要求太高，将严重影响众核的推广和使用，显式并行编程模式是多核乃至众核将来发展的瓶颈。

如何继续使用而不是抛弃现有的大量程序 (软件)代码，如何并行现有串行代码及提高程序执行效率;如何利用而不是抛弃现有的开发环境和工具等问题是通用众核技术发展必须要解决的问题。

2 隐式并行编程模式

针对现有显式编程模式成本大、容易出错且不能兼容现有开发工具和程序的不足，我们提出了面向对象的基于对象粒度的隐式编程模式，在底层硬件和编译技术的支撑下，兼容现有的串行程序开发模式、开发技术和开发工具，降低并行程序的开发成本和开发风险，并通过反编译技术和软件逆分析手段，实现对现有的串行二进制代码并行化，使将来的众核时代不至于抛弃现有的这些代码成果。

相对于显式并行编程模式，隐式并行编程模式尽量利用现有的开发工具、开发环境和程序开发语言等技术手段和成果，通过在计算机体系结构底层的硬件支撑进行专门设计、编译器优化等技术手段，使在现有的开发环境和开发工具下开发出来的程序 (比如面向对象的程序)能够无缝的运行在多核/众核系统上，这样开发的程序成本低、开发过程不容易出错、程序移植性好，对程序员要求低，并能同时获得较好的应用性能和产能目标。

目前软件技术的高度发展，以C++和Java为代表的面向对象高级程序设计语言的产生，遵循人类思维方式，采用适合人类的处理问题的思考模式，以对象作为编程单元来编制程序，对象和对象之间相对独立，对象具有封装、继承和多态性的特点，对象的方法和数据具有私有、公有和保护三种访问模式，程序的代码段主要由对象的方法调用组成，对象和对象之间通过消息机制完成通信。虽然在单核模式下，这些程序是串行执行的，对象的方法调用根据编制的代码序列串行顺序依次调用，显然这些对象及其方法的调用是能够并行进行。这些对象作为一种高度并行化的颗粒，能够直接映射到众核中的不同核去运行，通过处理器核间的通信链路来完成对象间的消息传递。现有的并 行 粒 度 有 循 环［7］、 函 数［8］、 代 码 复 用［9］和 软 件 流水［10-11］，需要程序员进行专门处理，对程序员要求较高，不通用，且不能解决现有代码的并行问题，属于显式编程模式，面向对象的基于对象并行粒度编程模式属于隐式编程模式，易于实现，并行度高，能够较好的解决现有代码的并行问题，是众核发展技术的出路。

3 基于对象的隐式并行编程模式研究

通过编译器和底层硬件支撑，现有的大众化程序员能够利用现有的面向对象开发技术和开发工具轻松开发出对象级粒度的并行程序，达到应用程序开发产能和并行性能收益同步提高的大众化并行计算研究的核心目标，完成对高级语言对象级并行粒度的隐式编程模式的研究;应用反编译技术和软件逆向分析，对现有二进制代码 (面向对象程序所写)中的对象级粒度进行识别和重构。

3.1 研究目标

通过研究，对编译器进行改进，完成在二进制代码中对同一对象的方法和变量的统一存放，并加以标注，片上处理器调度时根据该标注识别对象，完成核间数据通信和参数传递的研究;完成现有二进制代码中对象粒度的识别和重构，实现串行程序并行化;构建硬件支撑模块，根据程序并发度调度二进制代码中标注的对象，并将这些对象调度到不同核上运行;分析并找出对象间所有可能存在的数据共享方式。

3.2 关键问题

为了解决上述关键问题，主要需完成下面几个方面的研究:

(1)通过对现有面向对象编译器的改进，完成将现有面向对象语言中对象间的消息机制改进为核间通信手段的研究，进行不同对象 (核间)方法执行时参数传递及结果返回机制的研究，并在二进制代码中对对象加以标记，同一对象的不同方法放在一起 (正文段)，同一对象的不同变量放置在一起 (数据段);

(2)由于对象存在封装性，完成对象级并行粒度所有可能存在的共享数据及对其冲突类型进行评估;

(3)通过构建合适的底层硬件模块，完成对二进制代码中的对象及其方法的识别 (现在的串行二进制代码，改造后的工具写出来的程序中对象已有标注)，增加处理器对象访存指令，分析程序并发度，每个程序的对象被调度到3-8个核上运行，并实现完成片上计算时间和传输时间的错开、调度管理。

4 体系结构设计

我们采用图1所示的三维众核体系结构，由一层处理核层和多层cache层组成，层间采用3D叠片技术互连，处理核层各核间采用2D Mesh互连，cache层各cache块节点间采用半互连长互连线互连，处理核由L1 T-cache、I/D-cache和路由器组成，其中T-cache是L1级事务内存，该体系结构存储架构采用如图2所示结构，支持对象直接访问。

每个面向对象程序根据程序规模大小，把它的对象分别调度到3-8个核上，完成对象到处理器核的分配，为了利于指令缓存和数据缓存的命中率和实施局部性原理，把该对象的方法存储在离核较近的地址空间段中，由对象所分配的核负责该对象所有方法的运行 (有的对象的方法调用频率高，调度时需要考虑到这些对象在不同核上的负载平衡)，对象实例生成时，变量部分考虑存储在离处理器核较近的内存空间段;程序运行时，先经由硬件支撑机构遍历2-3遍代码，分析其合适的并发度，完成程序中对象的识别后再分配对象于不同核，通过这些核并发执行这些对象。

该体系结构是一种可重构的异构多核系统，结点处理器核可以是异构的，可以由众多的处理器核组成构成众核系统，系统采用二级缓存系统，每个单核有自己的私有一级缓存L1，L1由指令缓存、数据缓存和事务缓存构成，数据缓存和事务缓存采用多端口Cache，且数据缓存和事务缓存之间能够进行数据交换。具体的布局布线策略可采用斜布线和3D布线技术来实现，处理器核和存储器DRAM间数据通信可以采用图3所示的3D通路，处理器和存储的组合示意图如图4所示。

5 众核系统性能评价

并行程序在多个处理核执行时需要在不同核间交互数据和信息，多个程序在多个核同时并行执行时可以通过错开片上计算时间和片上网络通信时间，减少核间通信数据堵塞。由于众核系统往往承载多个程序的运行，当处理器核数变多时，众核系统的整体系统性能就能得到提升，具有同样缓存和功耗，不同核数规模组成的系统性能比较如图5所示 (左图是大、中、小三个单核性能和规模的比较，右图是在同晶体管数规模情况下，分别由少量大核、中量中核和多量小核组成的系统在单个、多个程序运行系统整体性能的对比)，从图中可以看出虽然小核晶体管规模只有大核的1/12，但是它的性能却是大核的1/3，多个小核组成的系统整体吞吐量比少量大核组成的系统吞吐量要大得多，衡量众核系统的性能不能只考虑某个应用程序的并行度，而应该考虑任务及应用程序级别的并行性。

图5 不同核数的系统性能比较

6 结论和展望

提出的基于对象的隐式并行编程众核体系结构，解决众核时代继续使用现有的二进制代码、现有的开发技术和开发工具，减少并行程序开发成本和风险，提出的对象级并行粒度众核软件技术的研究，对众核时代的程序并行化具有借鉴意义。

7 结束语

本文首先通过分析得出面向通用程序大众化并行计算是将来众核发展的方向，接着对其片上网络、并行编程模式和存储架构等关键技术进行深入研究，针对现有的显式编程模式编程成本大、容易出错且不能兼容现有开发工具和程序的不足，提出了面向对象的基于对象粒度的隐式编程模式，在底层硬件和编译技术支撑下，兼容现有的串行程序开发模式、开发技术和开发工具，降低并行程序开发成本和开发风险，并通过反编译和软件逆分析技术手段，实现对现有的串行二进制代码并行化，使将来的众核时代不至于抛弃现有的这些代码成果;并提出了相应的体系结构实现，这些关键技术解决了众核技术发展的瓶颈。

［1］CAOYangjie，YANGHaibing，QIAN Depei，et al.On Adaptability of the runtime environment for emerging Multi-Core programming models［J］.Journal of Xi'an Jiaotong University，2011，45(6):130-134(in Chinese).［曹仰杰，杨海兵，钱德沛，等.多核编程模型运行时环境的自适应性研究［J］.西安交通大学学报，2011，45(6):130-134.］

［2］Kasanovic.The parallel computing laboratory at U.C.Berkeley:A research agenda based on the berkeley view［R］.Berkeley:UCB，2008:1-25.

［3］LIU Duo， SHAO Zili， WANG Meng， et al.Optimal loop parallelization for maximizing iteration-level parallelism ［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23(3):564-572.

［4］YANG Jixiang，TAN Guozhen，WANG Rongsheng.Some key issues and their research progress in multicore software［J］.Acta Electronica Sinica，2010，38(9):2140-2146(in Chinese).［杨际祥，谭国真，王荣生.多核软件的几个关键问题及其研究进展 ［J］.电子学报，2010，38(9):2140-2146.］

［5］Hill M D，Marty M R.Amdahl＇s law in the multicore era ［J］.Computer，2008，41(7):33-38.

［6］W Hwu，S Ryoo，SZ Ueng，et al.Implicitly parallel programming models for thousand-core microprocessors［C］//Design Automation Conference.San Diego，CA，USA:ACM，2007:754-759.

［7］ZHANG Wangyuan，FU Xin，LI Tao，et al.An analysis of microarchitecture vulnerability to soft errors on simultaneous multithreaded architectures［C］//IEEE International Symposium on Performance Analysis of Systems ＆ Software.San Jose，CA，USA:IEEE，2007:169-178.

［8］Balakrishnan S，Sohi G S.Program demultiplexing:Data-flow based speculative parallelization of methods in sequential programs［C］//Int＇l Symp.Computer Architecture.Boston，MA，USA:IEEE，2006:302-313.

［9］Ben Lee.Performance evaluation of dynamic speculative multithreading with the cascadia architecture［J］.IEEE Transactions on Parallel and Distributed Systems，2010，21(1):47-59.

［10］Bridges M J，Vachharajani N，ZHANGY，et al.Revisiting the sequential programming model for multi-core［C］//Proc 40th IEEE/ACM Int'l Symp.Microarchitecture.Chicago，IL，USA:IEEE，2007:69-84.

［11］Tian C，Feng M，Nagarajan V.Copy or discard execution model for speculative parallelization on multicores ［C］//Proc 41st Int＇l IEEE/ACM Symp.Microarchitecture.Lake Como，Italy:IEEE，2008:300-341.