2015年 第52卷 第6期
摘要：
不断扩展的计算机应用领域和日益更新的计算需求对计算机体系结构提出新的要求和挑战，应用需求和工艺技术持续地对计算机体系结构的变革提供挑战性的需求和发展的机会。本专辑希望通过分析重要应用领域的应用特征对计算机体系结构提出的需求，论述体系结构研究和设计中的重要的科学问题和关键技术，报导体系结构研究和开发中的新技术、新方法、新系统，交流思想和成果，促进计算机体系结构的研究与发展。专辑的组织获得研究工作者的广泛响应与支持。本期专题共计收录了11篇论文，重点关注多核处理器的调度、存储、能耗控制、文件系统、模拟器等研究内容，同时也关注了云计算平台体系结构研究问题，在一定程度上反映了当前国内研究单位在计算机体系结构领域的主要研究方向。
不断扩展的计算机应用领域和日益更新的计算需求对计算机体系结构提出新的要求和挑战，应用需求和工艺技术持续地对计算机体系结构的变革提供挑战性的需求和发展的机会。本专辑希望通过分析重要应用领域的应用特征对计算机体系结构提出的需求，论述体系结构研究和设计中的重要的科学问题和关键技术，报导体系结构研究和开发中的新技术、新方法、新系统，交流思想和成果，促进计算机体系结构的研究与发展。专辑的组织获得研究工作者的广泛响应与支持。本期专题共计收录了11篇论文，重点关注多核处理器的调度、存储、能耗控制、文件系统、模拟器等研究内容，同时也关注了云计算平台体系结构研究问题，在一定程度上反映了当前国内研究单位在计算机体系结构领域的主要研究方向。
2015, 52(6): 1225-1241.
DOI: 10.7544/issn1000-1239.2015.20150104
摘要：
随着半导体工艺的发展，处理器集成的片上缓存越来越大，传统存储器件的漏电功耗问题日益严峻，如何设计高能效的片上存储架构已成为重要挑战.为解决这些问题，国内外研究者讨论了大量的新型非易失性存储技术，它们具有非易失性、低功耗和高存储密度等优良特性.为探索spin-transfer torque RAM(STT-RAM)，phase change memory(PCM)，resistive RAM(RRAM)和domain-wall memory(DWM)四种新型非易失性存储器(non-volatile memory, NVM)架构缓存的方法，对比了其与传统存储器件的物理特性，讨论了其架构缓存的优缺点和适用性，重点分类并总结了其架构缓存的优化方法和策略，分析了其中针对新型非易失性存储器写功耗高、写寿命有限和写延迟长等缺点所作出的关键优化技术，最后探讨了新型非易失性存储器件在未来缓存优化中可能的研究方向.
随着半导体工艺的发展，处理器集成的片上缓存越来越大，传统存储器件的漏电功耗问题日益严峻，如何设计高能效的片上存储架构已成为重要挑战.为解决这些问题，国内外研究者讨论了大量的新型非易失性存储技术，它们具有非易失性、低功耗和高存储密度等优良特性.为探索spin-transfer torque RAM(STT-RAM)，phase change memory(PCM)，resistive RAM(RRAM)和domain-wall memory(DWM)四种新型非易失性存储器(non-volatile memory, NVM)架构缓存的方法，对比了其与传统存储器件的物理特性，讨论了其架构缓存的优缺点和适用性，重点分类并总结了其架构缓存的优化方法和策略，分析了其中针对新型非易失性存储器写功耗高、写寿命有限和写延迟长等缺点所作出的关键优化技术，最后探讨了新型非易失性存储器件在未来缓存优化中可能的研究方向.
2015, 52(6): 1242-1253.
DOI: 10.7544/issn1000-1239.2015.20150140
摘要：
随着物联网、云计算与网络舆情分析等应用的快速发展，大数据处理的应用已经成为数据中心的核心负载.数据中心服务器普遍采用多核处理器，而目录缓存作为多核处理器结构中维护缓存一致性的关键部件，对其结构研究(如稀疏目录)更多地关注于目录缓存的容量与可扩展性，更适合处理高性能计算等计算密集型应用.然而，当多核处理器执行延迟敏感的大数据应用程序时，目录缓存的高访存延迟严重制约了数据中心的服务质量.针对该问题，新型主从目录缓存结构优化了数据访问过程中的一致性协议通路，其中主目录区分共享与私有数据，管理私有数据的访存操作，降低私有数据的访存延迟，提高了从目录的容量利用率；从目录维护共享数据的缓存一致性，采用有限位标签结构，提高了从目录的存储效率.实验在Simics+GEMS模拟平台上对大数据程序测试集Cloudsuite-v1.0进行评估.结果表明在以大数据应用程序为主的运行环境下，与2倍容量的稀疏目录相比，主从目录缓存结构降低了24.39%的硬件开销，降低了28.45%的缓存缺失延时，提升了3.5%的处理器IPC；与缓存内目录相比，主从目录结构虽然损失了5.14%的缓存缺失延时与1.1%的处理器IPC，但是降低了42.59%的硬件开销.
随着物联网、云计算与网络舆情分析等应用的快速发展，大数据处理的应用已经成为数据中心的核心负载.数据中心服务器普遍采用多核处理器，而目录缓存作为多核处理器结构中维护缓存一致性的关键部件，对其结构研究(如稀疏目录)更多地关注于目录缓存的容量与可扩展性，更适合处理高性能计算等计算密集型应用.然而，当多核处理器执行延迟敏感的大数据应用程序时，目录缓存的高访存延迟严重制约了数据中心的服务质量.针对该问题，新型主从目录缓存结构优化了数据访问过程中的一致性协议通路，其中主目录区分共享与私有数据，管理私有数据的访存操作，降低私有数据的访存延迟，提高了从目录的容量利用率；从目录维护共享数据的缓存一致性，采用有限位标签结构，提高了从目录的存储效率.实验在Simics+GEMS模拟平台上对大数据程序测试集Cloudsuite-v1.0进行评估.结果表明在以大数据应用程序为主的运行环境下，与2倍容量的稀疏目录相比，主从目录缓存结构降低了24.39%的硬件开销，降低了28.45%的缓存缺失延时，提升了3.5%的处理器IPC；与缓存内目录相比，主从目录结构虽然损失了5.14%的缓存缺失延时与1.1%的处理器IPC，但是降低了42.59%的硬件开销.
2015, 52(6): 1254-1265.
DOI: 10.7544/issn1000-1239.2015.20150154
摘要：
网络服务等新型高通量应用的迅速兴起给传统处理器设计带来了巨大的挑战.高通量众核处理器作为面向此类应用的新型处理器结构成为研究热点.然而，随着片上处理核数量的剧增，加之高通量应用的数据密集型特点,“存储墙”问题进一步加剧.通过分析高通量应用访存行为，发现此类应用存在着大量的细粒度访存，降低了访存带宽的有效利用率.基于此分析，在高通量处理器设计中通过添加访存请求收集表(memory access collection table, MACT) 硬件机制，结合消息式内存机制，用于收集离散的访存请求并进行批量处理.MACT硬件机制的实现，提高了访存带宽的有效利用率，同时也提高了执行效率;并通过时间窗口机制，确保访存请求在最晚期限之前发送出去，保证任务的实时性.实验以典型高通量应用WordCount，TeraSort，Search为基准测试程序.添加MACT硬件机制后，访存数量减少约49%，访存带宽提高约24%，平均执行速度提高约89%.
网络服务等新型高通量应用的迅速兴起给传统处理器设计带来了巨大的挑战.高通量众核处理器作为面向此类应用的新型处理器结构成为研究热点.然而，随着片上处理核数量的剧增，加之高通量应用的数据密集型特点,“存储墙”问题进一步加剧.通过分析高通量应用访存行为，发现此类应用存在着大量的细粒度访存，降低了访存带宽的有效利用率.基于此分析，在高通量处理器设计中通过添加访存请求收集表(memory access collection table, MACT) 硬件机制，结合消息式内存机制，用于收集离散的访存请求并进行批量处理.MACT硬件机制的实现，提高了访存带宽的有效利用率，同时也提高了执行效率;并通过时间窗口机制，确保访存请求在最晚期限之前发送出去，保证任务的实时性.实验以典型高通量应用WordCount，TeraSort，Search为基准测试程序.添加MACT硬件机制后，访存数量减少约49%，访存带宽提高约24%，平均执行速度提高约89%.
2015, 52(6): 1266-1277.
DOI: 10.7544/issn1000-1239.2015.20150160
摘要：
伴随大数据计算时代的到来，片上多核处理器为提高多线程程序服务器吞吐率发挥巨大作用，同时其内存系统的访问延迟越来越影响系统性能.目前，路径驱动(trace-driven)仿真方法比执行驱动(execution-driven)运行速度快，被内存系统研究者广泛采用.但是路径驱动在仿真并发线程时，会同时导致宏观和微观的访存错位.而实际多线程程序运行过程中，不会发生这种访存错位行为.通过理论分析和计算，访存错位引起路径驱动的仿真结果存在明显偏差.针对上述问题，提出了一种方法来避免路径驱动仿真发生宏观和微观访存错位，精确回放采集阶段的多线程程序行为.实验数据显示，在避免宏观访存trace错位后，多线程程序的多个仿真指标出现最高10.22%的变化；对于部分访存密集型的多线程程序，避免微观访存trace错位可以使算数平均IPC出现大于50%的变化.为研究交互线程的内存系统行为提供一种更加准确的路径驱动方法.
伴随大数据计算时代的到来，片上多核处理器为提高多线程程序服务器吞吐率发挥巨大作用，同时其内存系统的访问延迟越来越影响系统性能.目前，路径驱动(trace-driven)仿真方法比执行驱动(execution-driven)运行速度快，被内存系统研究者广泛采用.但是路径驱动在仿真并发线程时，会同时导致宏观和微观的访存错位.而实际多线程程序运行过程中，不会发生这种访存错位行为.通过理论分析和计算，访存错位引起路径驱动的仿真结果存在明显偏差.针对上述问题，提出了一种方法来避免路径驱动仿真发生宏观和微观访存错位，精确回放采集阶段的多线程程序行为.实验数据显示，在避免宏观访存trace错位后，多线程程序的多个仿真指标出现最高10.22%的变化；对于部分访存密集型的多线程程序，避免微观访存trace错位可以使算数平均IPC出现大于50%的变化.为研究交互线程的内存系统行为提供一种更加准确的路径驱动方法.
2015, 52(6): 1278-1287.
DOI: 10.7544/issn1000-1239.2015.20150139
摘要：
随着云存储技术的快速发展和应用，越来越多的企业和用户都开始将数据从本地转移到云存储服务提供商进行存储.但是，在享受云存储高质量服务的同时，将数据仅仅存储于单个云存储服务商中会带来一定的风险，例如云存储服务提供商的垄断、数据可用性和安全性等问题.为了解决这个问题，提出了一种基于重复数据删除技术的云中云存储系统架构，首先消除云存储系统中的冗余数据量，然后基于重复数据删除集中的数据块引用率将数据块以复制和纠删码2种数据布局方式存储在多个云存储服务提供商中.基于复制的数据布局方式易于实现部署，但是存储开销大；基于纠删码的数据布局方式存储开销小，但是需要编码和解码，计算开销大.为了充分挖掘复制和纠删码数据布局的优点并结合重复数据删除技术中数据引用的特点，新方法用复制方式存储高引用数据块，用纠删码方式存储其他数据块，从而使系统整体性能和成本达到较优.通过原型系统的实现和测试验证了相比现有云中云存储策略，新方法在性能和成本上都有大幅度提高.
随着云存储技术的快速发展和应用，越来越多的企业和用户都开始将数据从本地转移到云存储服务提供商进行存储.但是，在享受云存储高质量服务的同时，将数据仅仅存储于单个云存储服务商中会带来一定的风险，例如云存储服务提供商的垄断、数据可用性和安全性等问题.为了解决这个问题，提出了一种基于重复数据删除技术的云中云存储系统架构，首先消除云存储系统中的冗余数据量，然后基于重复数据删除集中的数据块引用率将数据块以复制和纠删码2种数据布局方式存储在多个云存储服务提供商中.基于复制的数据布局方式易于实现部署，但是存储开销大；基于纠删码的数据布局方式存储开销小，但是需要编码和解码，计算开销大.为了充分挖掘复制和纠删码数据布局的优点并结合重复数据删除技术中数据引用的特点，新方法用复制方式存储高引用数据块，用纠删码方式存储其他数据块，从而使系统整体性能和成本达到较优.通过原型系统的实现和测试验证了相比现有云中云存储策略，新方法在性能和成本上都有大幅度提高.
2015, 52(6): 1288-1302.
DOI: 10.7544/issn1000-1239.2015.20150168
摘要：
资源分配策略是当前云计算研究领域中的一个重要研究热点，异构云计算体系结构下的复杂应用问题研究中，最基本的问题在于如何将总体有限的资源分配给多个租户或应用，以达到效率或收效最大化.但是，在经典的资源分配问题中，任务或者用户往往是“贪婪”的；因此，在总体资源有限的前提下，资源分配的公平性就显得尤为重要.为了满足不同的任务需求，达到多种资源分配的公平性，设计了一个虚拟化的异构云计算体系结构，提出了该体系结构下基于占优资源的多资源联合公平分配算法(maximizing multi-resource fairness based on dominant resource, MDRF)，并且证明了算法的帕累托等相关属性；给出了占优资源熵(dominant resource entropy, DRE)和占优资源权重(dominant resource weight, DRW)的定义，占优资源熵更加精确地刻画了用户资源请求与任务所调度到的服务器资源之间的适应程度，使系统的自适应能力更强同时提高了资源利用率.占优资源权重保障了用户优先获取资源的优先次序，协同所采用保障公平性的Max-Min Fairness策略，使资源的分配更加有序.实验表明，我们的策略有更高的系统资源利用率，并且使需求与供给更加匹配，进而使用户的占优资源获取更多，提高了服务质量.
资源分配策略是当前云计算研究领域中的一个重要研究热点，异构云计算体系结构下的复杂应用问题研究中，最基本的问题在于如何将总体有限的资源分配给多个租户或应用，以达到效率或收效最大化.但是，在经典的资源分配问题中，任务或者用户往往是“贪婪”的；因此，在总体资源有限的前提下，资源分配的公平性就显得尤为重要.为了满足不同的任务需求，达到多种资源分配的公平性，设计了一个虚拟化的异构云计算体系结构，提出了该体系结构下基于占优资源的多资源联合公平分配算法(maximizing multi-resource fairness based on dominant resource, MDRF)，并且证明了算法的帕累托等相关属性；给出了占优资源熵(dominant resource entropy, DRE)和占优资源权重(dominant resource weight, DRW)的定义，占优资源熵更加精确地刻画了用户资源请求与任务所调度到的服务器资源之间的适应程度，使系统的自适应能力更强同时提高了资源利用率.占优资源权重保障了用户优先获取资源的优先次序，协同所采用保障公平性的Max-Min Fairness策略，使资源的分配更加有序.实验表明，我们的策略有更高的系统资源利用率，并且使需求与供给更加匹配，进而使用户的占优资源获取更多，提高了服务质量.
2015, 52(6): 1303-1315.
DOI: 10.7544/issn1000-1239.2015.20150153
摘要：
面向能耗优化的面积(核数)-功率(频率)分配问题是当前众核处理器研究热点之一.通过性能-功耗模型了解其在核数-频率空间的分布规律，然后在核数和频率级别这2个维度上通过实测执行逐步搜索，可以获取“核数-频率”配置的最优解，从而达到能耗优化的目的;然而本领域现有方法在核数-频率空间内实测搜索最低能耗时收敛速度慢、搜索开销大、可扩展性差.针对此问题,提出了一种基于求解最优化问题的经典数学方法——可行方向法的最低能耗搜索方法(energy-efficient optimization based on feasible direction method, EOFDM)，每次执行都能从核数和频率2个维度上同时减小搜索空间，在迭代执行中快速收敛至最低能耗点.该方法与现有研究中最优的启发式爬山法(hill-climbing heuristic, HCH)进行了对比实验，平均执行次数、执行时间和能耗分别降低39.5%，46.8%，48.3%，提高了收敛速度，降低了搜索开销；当核数增加一倍时,平均执行次数、执行时间和能耗分别降低48.8%，51.6%，50.9%；当频率级数增加一倍时,平均执行次数、执行时间和能耗分别降低45.5%，49.8%，54.4%，在收敛速度、搜索开销和可扩展性方面均有提高.
面向能耗优化的面积(核数)-功率(频率)分配问题是当前众核处理器研究热点之一.通过性能-功耗模型了解其在核数-频率空间的分布规律，然后在核数和频率级别这2个维度上通过实测执行逐步搜索，可以获取“核数-频率”配置的最优解，从而达到能耗优化的目的;然而本领域现有方法在核数-频率空间内实测搜索最低能耗时收敛速度慢、搜索开销大、可扩展性差.针对此问题,提出了一种基于求解最优化问题的经典数学方法——可行方向法的最低能耗搜索方法(energy-efficient optimization based on feasible direction method, EOFDM)，每次执行都能从核数和频率2个维度上同时减小搜索空间，在迭代执行中快速收敛至最低能耗点.该方法与现有研究中最优的启发式爬山法(hill-climbing heuristic, HCH)进行了对比实验，平均执行次数、执行时间和能耗分别降低39.5%，46.8%，48.3%，提高了收敛速度，降低了搜索开销；当核数增加一倍时,平均执行次数、执行时间和能耗分别降低48.8%，51.6%，50.9%；当频率级数增加一倍时,平均执行次数、执行时间和能耗分别降低45.5%，49.8%，54.4%，在收敛速度、搜索开销和可扩展性方面均有提高.
2015, 52(6): 1316-1328.
DOI: 10.7544/issn1000-1239.2015.20150119
摘要：
随着半导体技术进步,单个芯片上集成大量核心的众核处理器已经广泛应用于高性能计算领域.相比多核处理器,众核处理器能提供更好的计算密度和能效比,但同时也面临越来越严重的可靠性挑战.需要设计高效的处理器容错机制,有效保证课题运行效率的同时不带来较大的芯片功耗和面积开销.在一款自主众核处理器DFMC(deeply fused and heterogeneous many-core)原型基础上,根据核心上运行的应用程序是否具有关联性特征,提出并实现了面向众核处理器的独立和协同2种轻量级错误恢复技术.其中,协同恢复技术由集中部件进行管理,通过协同恢复总线互连,出错时将与错误相关联的多个核心快速回卷到正确状态.2种错误恢复技术中,保留和恢复过程均通过定制的指令实现,恢复所需要的信息保留在运算核心内部,以保证对课题性能的影响最小化.实验表明,通过上述技术只增加了1.257%的芯片面积,可解决自主众核处理器约80%的瞬时错误,且对课题性能、芯片时序和功耗影响很小,可有效地提高众核处理器的容错能力.
随着半导体技术进步,单个芯片上集成大量核心的众核处理器已经广泛应用于高性能计算领域.相比多核处理器,众核处理器能提供更好的计算密度和能效比,但同时也面临越来越严重的可靠性挑战.需要设计高效的处理器容错机制,有效保证课题运行效率的同时不带来较大的芯片功耗和面积开销.在一款自主众核处理器DFMC(deeply fused and heterogeneous many-core)原型基础上,根据核心上运行的应用程序是否具有关联性特征,提出并实现了面向众核处理器的独立和协同2种轻量级错误恢复技术.其中,协同恢复技术由集中部件进行管理,通过协同恢复总线互连,出错时将与错误相关联的多个核心快速回卷到正确状态.2种错误恢复技术中,保留和恢复过程均通过定制的指令实现,恢复所需要的信息保留在运算核心内部,以保证对课题性能的影响最小化.实验表明,通过上述技术只增加了1.257%的芯片面积,可解决自主众核处理器约80%的瞬时错误,且对课题性能、芯片时序和功耗影响很小,可有效地提高众核处理器的容错能力.
2015, 52(6): 1329-1340.
DOI: 10.7544/issn1000-1239.2015.20150162
摘要：
高速互连网络是高性能计算系统的重要组成部分.随着网络规模需求的扩大，如何搭建更大规模的网络是高速互连网络拓扑结构设计的关键.因此，提出一种新型层次化的拓扑结构Paleyfly(PF)，其结合了Paley图强正则的特性和Random Regular(RR)图支持任意规模大小的特点.相比其他新型高速互连网络拓扑结构，Paleyfly能够有效解决在路由芯片端口数受限的背景下，Dragonfly(DF)可扩展性受限、Fat tree(Ft)物理成本高、RR结构物理布局难、路由表规模大等问题.同时，根据强正则属性在路由策略上负载均衡的优势，提出了4种路由策略来解决网络的拥塞问题.最后，通过模拟器实验比较分析PF结构与其他拓扑结构及PF结构不同路由策略的性能，验证了PF结构在不同规模以及不同通信模式配置下网络延迟优于RR结构.
高速互连网络是高性能计算系统的重要组成部分.随着网络规模需求的扩大，如何搭建更大规模的网络是高速互连网络拓扑结构设计的关键.因此，提出一种新型层次化的拓扑结构Paleyfly(PF)，其结合了Paley图强正则的特性和Random Regular(RR)图支持任意规模大小的特点.相比其他新型高速互连网络拓扑结构，Paleyfly能够有效解决在路由芯片端口数受限的背景下，Dragonfly(DF)可扩展性受限、Fat tree(Ft)物理成本高、RR结构物理布局难、路由表规模大等问题.同时，根据强正则属性在路由策略上负载均衡的优势，提出了4种路由策略来解决网络的拥塞问题.最后，通过模拟器实验比较分析PF结构与其他拓扑结构及PF结构不同路由策略的性能，验证了PF结构在不同规模以及不同通信模式配置下网络延迟优于RR结构.
2015, 52(6): 1341-1350.
DOI: 10.7544/issn1000-1239.2015.20150201
摘要：
在科学计算和大数据处理应用需求的推动下，高性能计算机的性能不断提升、系统规模日益扩大，系统功耗越来越成为制约能力提升的重要瓶颈.在深入分析现有4类高性能计算机的基础上探讨了2项关键技术：1)可重构微服务器(reconfigurable micro server， RMS)技术.解决单个计算节点在领域应用加速能力、系统功耗和体积间的平衡兼顾问题.2)自治与分治相结合的集群构造技术.解决基于微小型化计算节点的大规模计算平台构造与扩展性问题.在此基础上，提出了一种新型的高效多用计算平台架构——“蚁群”，构建了包含2 048个低功耗、微小型化RMS计算节点的蚁群平台原型系统，并实现了大规模指纹实时比对和多RMS节点协同排序2个典型应用.测试表明，单个RMS节点的指纹比对性能是Xeon单核的34倍，功耗仅5W，整个原型系统可实现千万量级指纹库的数百并发实时查询；蚁群平台的数据排序性能功耗比是GPU平台的10倍以上，有效提升数据排序的效率.
在科学计算和大数据处理应用需求的推动下，高性能计算机的性能不断提升、系统规模日益扩大，系统功耗越来越成为制约能力提升的重要瓶颈.在深入分析现有4类高性能计算机的基础上探讨了2项关键技术：1)可重构微服务器(reconfigurable micro server， RMS)技术.解决单个计算节点在领域应用加速能力、系统功耗和体积间的平衡兼顾问题.2)自治与分治相结合的集群构造技术.解决基于微小型化计算节点的大规模计算平台构造与扩展性问题.在此基础上，提出了一种新型的高效多用计算平台架构——“蚁群”，构建了包含2 048个低功耗、微小型化RMS计算节点的蚁群平台原型系统，并实现了大规模指纹实时比对和多RMS节点协同排序2个典型应用.测试表明，单个RMS节点的指纹比对性能是Xeon单核的34倍，功耗仅5W，整个原型系统可实现千万量级指纹库的数百并发实时查询；蚁群平台的数据排序性能功耗比是GPU平台的10倍以上，有效提升数据排序的效率.
2015, 52(6): 1351-1361.
DOI: 10.7544/issn1000-1239.2015.20150171
摘要：
在文件系统进行用户数据和元数据的持久化过程中，如果出现异常掉电或系统崩溃，可能导致文件系统出现数据的不一致性问题.现有的Ext4文件系统通过写前日志(write-ahead logging, WAL)技术结合事务机制来保证持久化操作的一致性.写前日志技术将文件系统元数据写入磁盘2次，元数据的粒度小、数量大、重复度高，影响了程序的性能，也缩短了Flash存储介质的使用寿命.针对这一问题，提出了使用新型非易失存储(non-volatile memory, NVM)作为存放日志的独立外部设备，并通过存取指令(load/store)接口直接访问；同时使用倒序扫描(reverse scan)技术对检查点(checkpoint)流程进行优化，减少同一数据块的重复写操作.实验结果表明，使用NVM作为外部日志分区，对于写操作比重较大的程序，在HDD上带宽提升接近50%;在SSD上带宽提升达到23%;在checkpoint时使用倒序扫描之后，写入次数降低明显，带宽提升接近20%.
在文件系统进行用户数据和元数据的持久化过程中，如果出现异常掉电或系统崩溃，可能导致文件系统出现数据的不一致性问题.现有的Ext4文件系统通过写前日志(write-ahead logging, WAL)技术结合事务机制来保证持久化操作的一致性.写前日志技术将文件系统元数据写入磁盘2次，元数据的粒度小、数量大、重复度高，影响了程序的性能，也缩短了Flash存储介质的使用寿命.针对这一问题，提出了使用新型非易失存储(non-volatile memory, NVM)作为存放日志的独立外部设备，并通过存取指令(load/store)接口直接访问；同时使用倒序扫描(reverse scan)技术对检查点(checkpoint)流程进行优化，减少同一数据块的重复写操作.实验结果表明，使用NVM作为外部日志分区，对于写操作比重较大的程序，在HDD上带宽提升接近50%;在SSD上带宽提升达到23%;在checkpoint时使用倒序扫描之后，写入次数降低明显，带宽提升接近20%.
2015, 52(6): 1362-1377.
DOI: 10.7544/issn1000-1239.2015.20140227
摘要：
弹性移动云计算(elastic mobile cloud computing, EMCC)中，移动设备按照实时需求将部分任务迁移到云端执行，无缝透明的利用云资源增强自身功能.将现有EMCC方案分为雇佣云端完成部分计算密集任务的计算迁移型移动云计算(computing migration-mobile cloud computing， CM-MCC)和通过云端的虚拟移动设备来辅助或代替移动设备完成多种任务的云端代理型移动云计算(cloud agent-mobile cloud computing， CA-MCC)两类，分别对CM-MCC,CA-MCC的适用场景、实现流程、关键技术、存在问题及相应解决方法进行研究并指出其发展方向.对EMCC所面临的主要安全威胁，包括用户的错误操作或恶意行为、恶意代码、通信安全以及虚拟系统漏洞、多租户、不安全资源等云安全问题进行分析并研究相应防御方法,指出安全问题将是EMCC研究的重点和难点.
弹性移动云计算(elastic mobile cloud computing, EMCC)中，移动设备按照实时需求将部分任务迁移到云端执行，无缝透明的利用云资源增强自身功能.将现有EMCC方案分为雇佣云端完成部分计算密集任务的计算迁移型移动云计算(computing migration-mobile cloud computing， CM-MCC)和通过云端的虚拟移动设备来辅助或代替移动设备完成多种任务的云端代理型移动云计算(cloud agent-mobile cloud computing， CA-MCC)两类，分别对CM-MCC,CA-MCC的适用场景、实现流程、关键技术、存在问题及相应解决方法进行研究并指出其发展方向.对EMCC所面临的主要安全威胁，包括用户的错误操作或恶意行为、恶意代码、通信安全以及虚拟系统漏洞、多租户、不安全资源等云安全问题进行分析并研究相应防御方法,指出安全问题将是EMCC研究的重点和难点.
2015, 52(6): 1378-1388.
DOI: 10.7544/issn1000-1239.2015.20131494
摘要：
云服务模式具有巨大的经济技术优势和广阔的应用前景，普及云服务技术对我国的信息化建设和社会发展具有重要的意义.云服务推广与应用中面临的最大挑战是安全问题.同态加密，尤其是全同态加密是解决云服务安全问题极为关键的技术，也是近年来国际密码学界研究的热点问题.对同态加密的研究现状进行了综述，介绍了同态加密在云计算机密性保护及其他方面的应用，重点介绍了各种代数部分同态加密方案和电路全同态加密方案的优缺点.对同态加密未来的研究问题进行了分析，同时简单介绍了云安全中的明文保密计算概念、相对于密文计算的优势以及需要进一步研究的问题等.
云服务模式具有巨大的经济技术优势和广阔的应用前景，普及云服务技术对我国的信息化建设和社会发展具有重要的意义.云服务推广与应用中面临的最大挑战是安全问题.同态加密，尤其是全同态加密是解决云服务安全问题极为关键的技术，也是近年来国际密码学界研究的热点问题.对同态加密的研究现状进行了综述，介绍了同态加密在云计算机密性保护及其他方面的应用，重点介绍了各种代数部分同态加密方案和电路全同态加密方案的优缺点.对同态加密未来的研究问题进行了分析，同时简单介绍了云安全中的明文保密计算概念、相对于密文计算的优势以及需要进一步研究的问题等.
2015, 52(6): 1389-1393.
DOI: 10.7544/issn1000-1239.2015.20131952
摘要：
同态加密在云计算等领域具有重要的应用价值，针对现有同态加密方案中私钥个数多和需要预设乘法同态次数的缺陷，基于一个具有特殊b的误差学习问题(learning with errors problem, LWE)变种bLWE(the “special b” variant of the learning with errors problem)，得到具有循环安全性的重线性化过程，据此构造了一个较高效的同态加密方案.与Brakerski等人的方案相比，方案的构造者不需要事先知道服务器中乘法同态次数，且私钥个数由原来的L+1个大幅度地缩小为1个.最后，在标准模型下对重线性化过程的循环安全性和方案的CPA安全性进行了严格证明.
同态加密在云计算等领域具有重要的应用价值，针对现有同态加密方案中私钥个数多和需要预设乘法同态次数的缺陷，基于一个具有特殊b的误差学习问题(learning with errors problem, LWE)变种bLWE(the “special b” variant of the learning with errors problem)，得到具有循环安全性的重线性化过程，据此构造了一个较高效的同态加密方案.与Brakerski等人的方案相比，方案的构造者不需要事先知道服务器中乘法同态次数，且私钥个数由原来的L+1个大幅度地缩小为1个.最后，在标准模型下对重线性化过程的循环安全性和方案的CPA安全性进行了严格证明.
2015, 52(6): 1394-1399.
DOI: 10.7544/issn1000-1239.2015.20131954
摘要：
伪随机数发生器(pseudorandom number generator, PRNG)是重要的密码学概念.基于单向函数的伪随机数发生器起始于1982年的BMY发生器，将单向函数反复迭代，周期性地输出伪随机序列.单向函数的性质和种子长度关系到发生器的可实现性和安全性，是此类发生器的2个重要参数.在分析现有工作的基础上，改进了单向函数的随机化迭代方式，基于不可逆性证明了迭代过程的安全性.迭代方式的改进消除了单向函数的长度保持性质，采用一般的压缩规范单向函数和通用散列函数构建伪随机数发生器.输出级与BMY发生器结构类似，以迭代函数的核心断言作为伪随机序列.基于与真随机序列的不可区分性，证明了伪随机数发生器的安全性.所构建的伪随机数发生器与现有同类发生器结构类似，但放松了对单向函数性质的要求，增强了可实现性，减小了种子长度，提高了效率.
伪随机数发生器(pseudorandom number generator, PRNG)是重要的密码学概念.基于单向函数的伪随机数发生器起始于1982年的BMY发生器，将单向函数反复迭代，周期性地输出伪随机序列.单向函数的性质和种子长度关系到发生器的可实现性和安全性，是此类发生器的2个重要参数.在分析现有工作的基础上，改进了单向函数的随机化迭代方式，基于不可逆性证明了迭代过程的安全性.迭代方式的改进消除了单向函数的长度保持性质，采用一般的压缩规范单向函数和通用散列函数构建伪随机数发生器.输出级与BMY发生器结构类似，以迭代函数的核心断言作为伪随机序列.基于与真随机序列的不可区分性，证明了伪随机数发生器的安全性.所构建的伪随机数发生器与现有同类发生器结构类似，但放松了对单向函数性质的要求，增强了可实现性，减小了种子长度，提高了效率.
2015, 52(6): 1400-1408.
DOI: 10.7544/issn1000-1239.2015.20140205
摘要：
通信开销在云环境中无法忽略，但现有DAG(directed acyclic graph)工作流费用优化模型大都未考虑任务之间的通信开销，难以在实际云环境中应用.为此，提出带通信开销的工作流费用优化模型CA-DAG(communication aware-DAG)，并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communication aware cost optimization).CACO使用前向一致规则(forward consistent， FC)求解工作流的最小完工时间；根据逆向分层策略将任务分层，使费用优化问题从全局转化到局部；采用动态规划方法收集任务在选择服务时产生的零散“时间碎片”，增加任务的费用优化空间，改善费用优化效果.仿真实验结果表明，在考虑通信开销时，CACO费用优化效果较DTL(deadline top level)，DBL(deadline bottom level)，TCDBL(temporal consistency deadline bottom level)都有显著提高.
通信开销在云环境中无法忽略，但现有DAG(directed acyclic graph)工作流费用优化模型大都未考虑任务之间的通信开销，难以在实际云环境中应用.为此，提出带通信开销的工作流费用优化模型CA-DAG(communication aware-DAG)，并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communication aware cost optimization).CACO使用前向一致规则(forward consistent， FC)求解工作流的最小完工时间；根据逆向分层策略将任务分层，使费用优化问题从全局转化到局部；采用动态规划方法收集任务在选择服务时产生的零散“时间碎片”，增加任务的费用优化空间，改善费用优化效果.仿真实验结果表明，在考虑通信开销时，CACO费用优化效果较DTL(deadline top level)，DBL(deadline bottom level)，TCDBL(temporal consistency deadline bottom level)都有显著提高.
2015, 52(6): 1409-1423.
DOI: 10.7544/issn1000-1239.2015.20131422
摘要：
鉴于剖面识别骨架特征提取方法(profile recognition and polygon breaking algorithm, PPA)准确性差、不能提取特殊地形等问题，提出了一种结合形态学的剖面识别骨架特征提取方法(profile recognition and polygon breaking algorithm based on morphology erosion, MEPPA).通过剖面识别提取原始的骨架特征候选点，根据方向系数连接成多边形条带，在此基础上提出了生成标量特征域的填充算法；引入形态学区域细化思想，提出了形态编码和骨架特征形态简化算法，将特征域简化为骨架特征线；为了满足各领域对矢量骨架特征的需求，提出了标量特征线复原、检测与优化剔除等策略，准确地复原了矢量骨架特征模型；提出了保留外分支和环路特征的解决方案，解决了传统骨架特征提取方法不能保留较长的主干线以及不能提取环路地形特征的问题.在真实数据上进行了实验研究，结果表明提取的骨架特征形态的整体效果优于传统方法.
鉴于剖面识别骨架特征提取方法(profile recognition and polygon breaking algorithm, PPA)准确性差、不能提取特殊地形等问题，提出了一种结合形态学的剖面识别骨架特征提取方法(profile recognition and polygon breaking algorithm based on morphology erosion, MEPPA).通过剖面识别提取原始的骨架特征候选点，根据方向系数连接成多边形条带，在此基础上提出了生成标量特征域的填充算法；引入形态学区域细化思想，提出了形态编码和骨架特征形态简化算法，将特征域简化为骨架特征线；为了满足各领域对矢量骨架特征的需求，提出了标量特征线复原、检测与优化剔除等策略，准确地复原了矢量骨架特征模型；提出了保留外分支和环路特征的解决方案，解决了传统骨架特征提取方法不能保留较长的主干线以及不能提取环路地形特征的问题.在真实数据上进行了实验研究，结果表明提取的骨架特征形态的整体效果优于传统方法.
2015, 52(6): 1424-1430.
DOI: 10.7544/issn1000-1239.2015.20140067
摘要：
夜间图像由于照明不足，存在图像对比度、亮度偏低，细节不可见，导致图像质量下降.大多夜间彩色图像增强算法往往在高对比度边缘区域存在“光晕伪影”现象，针对这些问题提出了一种基于目的性优化及改进直方图均衡化的图像增强算法.该算法通过目的性优化增强原图像对比度，最大程度地保留细节；然后采用改进的保留细节的直方图均衡化增强图像；最后采用改进的Gamma校正对图像进行增强.算法结果通过主观视觉效果以及客观质量评价2方面验证，实验结果表明该算法能够有效地增强图像对比度、亮度，恢复图像细节，并消除了“光晕伪影”.
夜间图像由于照明不足，存在图像对比度、亮度偏低，细节不可见，导致图像质量下降.大多夜间彩色图像增强算法往往在高对比度边缘区域存在“光晕伪影”现象，针对这些问题提出了一种基于目的性优化及改进直方图均衡化的图像增强算法.该算法通过目的性优化增强原图像对比度，最大程度地保留细节；然后采用改进的保留细节的直方图均衡化增强图像；最后采用改进的Gamma校正对图像进行增强.算法结果通过主观视觉效果以及客观质量评价2方面验证，实验结果表明该算法能够有效地增强图像对比度、亮度，恢复图像细节，并消除了“光晕伪影”.
2015, 52(6): 1431-1442.
DOI: 10.7544/issn1000-1239.2015.20140356
摘要：
空间数据的应用领域正在不断扩大.数据插值可以有效重建空间未知数据.数据插值就是一个数据再生的过程,即由原始数据再生出具有更高分辨率的数据.插值方法分为“确定”性插值和“不确定”性插值方法.不确定性插值方法的不确定性一方面表现在选用的插值方式具有随机性,另一方面表现在插值参数的选取和确定需要依赖于概率统计原则.多点随机模拟法(multiple-point simulation, MPS)是实现空间数据不确定插值重建的重要手段.单一标准方程模拟(single normal equation simulation, SNESIM)作为一种常用的MPS方法,目前已经用于多个领域的离散型空间数据三维重建.但是由于SNESIM给CPU和内存带来的负荷较大,大大限制了其实际应用.为了克服这种局限性,基于统一计算设备架构(compute unified device architecture, CUDA)实现SNESIM的并行化,并在计算训练图像(training image, TI)熵的基础上选择合适的数据模板尺寸；同时,通过整合软硬数据提高重建质量.与以往基于CPU的重建方法相比,基于CUDA的SNESIM并行算法显示出更好的空间数据重建效率.
空间数据的应用领域正在不断扩大.数据插值可以有效重建空间未知数据.数据插值就是一个数据再生的过程,即由原始数据再生出具有更高分辨率的数据.插值方法分为“确定”性插值和“不确定”性插值方法.不确定性插值方法的不确定性一方面表现在选用的插值方式具有随机性,另一方面表现在插值参数的选取和确定需要依赖于概率统计原则.多点随机模拟法(multiple-point simulation, MPS)是实现空间数据不确定插值重建的重要手段.单一标准方程模拟(single normal equation simulation, SNESIM)作为一种常用的MPS方法,目前已经用于多个领域的离散型空间数据三维重建.但是由于SNESIM给CPU和内存带来的负荷较大,大大限制了其实际应用.为了克服这种局限性,基于统一计算设备架构(compute unified device architecture, CUDA)实现SNESIM的并行化,并在计算训练图像(training image, TI)熵的基础上选择合适的数据模板尺寸；同时,通过整合软硬数据提高重建质量.与以往基于CPU的重建方法相比,基于CUDA的SNESIM并行算法显示出更好的空间数据重建效率.
2015, 52(6): 1443-1451.
DOI: 10.7544/issn1000-1239.2015.20131904
摘要：
在普适计算中，上下文持续快速变化，上下文感知应用根据上下文变化自动调整自身的行为以作出适应.然而，由于不可预测和控制的环境噪声以及环境动态变化等诸多因素的影响，环境上下文会发生一致性错误，从而导致应用表现异常甚至失效.为了解决这些问题，上下文一致性错误需要被自动并正确地修复，现基于已有工作提出了一项新的修复技术hybrid-fixing，它结合了对一致性约束的静态分析和修复动作的动态产生，即使一致性约束内部存在复杂依赖关系，也能确保所生成的修复用例必然正确.实验结果表明，这项修复技术大幅提高了一致性约束内部存在复杂依赖关系下一致性错误修复的成功率，并只花费了很小的时间开销.
在普适计算中，上下文持续快速变化，上下文感知应用根据上下文变化自动调整自身的行为以作出适应.然而，由于不可预测和控制的环境噪声以及环境动态变化等诸多因素的影响，环境上下文会发生一致性错误，从而导致应用表现异常甚至失效.为了解决这些问题，上下文一致性错误需要被自动并正确地修复，现基于已有工作提出了一项新的修复技术hybrid-fixing，它结合了对一致性约束的静态分析和修复动作的动态产生，即使一致性约束内部存在复杂依赖关系，也能确保所生成的修复用例必然正确.实验结果表明，这项修复技术大幅提高了一致性约束内部存在复杂依赖关系下一致性错误修复的成功率，并只花费了很小的时间开销.
2015, 52(6): 1452-1462.
DOI: 10.7544/issn1000-1239.2015.20140403
摘要：
Map/Reduce是海量离线数据分析中广泛应用的并行编程模型.Hive数据仓库基于Map/Reduce实现了查询处理引擎,然而Map/Reduce框架在处理偏斜数据时会出现工作负载分布不均的问题.均衡计算模型(computation balanced model, CBM)，其核心思想是通过数据分布特征指导查询计划优化.相应研究贡献包括2部分，首先针对应用极广的GroupBy查询和Join查询建立了运行估价模型，确定了不同场景下查询计划的优化选择分支；其次基于Hive ETL机制设计了一种统计信息收集方法，解决了统计海量数据分布特征的问题.实验数据表明，通过CBM优化的 GroupBy查询耗时节省了8%～45%，Join查询耗时节省了12%～46%；集群CPU负载均衡指标优化了60%～80%，I/O负载均衡指标优化了60%～90%.实验结果证实了基于CBM模型优化的查询计划生成器能显著均衡化Hive查询运行时的集群负载，并优化了查询处理效率.
Map/Reduce是海量离线数据分析中广泛应用的并行编程模型.Hive数据仓库基于Map/Reduce实现了查询处理引擎,然而Map/Reduce框架在处理偏斜数据时会出现工作负载分布不均的问题.均衡计算模型(computation balanced model, CBM)，其核心思想是通过数据分布特征指导查询计划优化.相应研究贡献包括2部分，首先针对应用极广的GroupBy查询和Join查询建立了运行估价模型，确定了不同场景下查询计划的优化选择分支；其次基于Hive ETL机制设计了一种统计信息收集方法，解决了统计海量数据分布特征的问题.实验数据表明，通过CBM优化的 GroupBy查询耗时节省了8%～45%，Join查询耗时节省了12%～46%；集群CPU负载均衡指标优化了60%～80%，I/O负载均衡指标优化了60%～90%.实验结果证实了基于CBM模型优化的查询计划生成器能显著均衡化Hive查询运行时的集群负载，并优化了查询处理效率.
本刊虚拟专辑J-CRAD Transactions on系列更新，欢迎阅读！
