摘要:

摘要:如何有效地将海量数据分布到存储节点，是存储系统首要解决的问题.提出的MJHAR（matrix-based jump hash algorithm for replication data）对象分布算法简洁、高效，支持权值和数据冗余机制.该算法创造性地将节点映射到二维矩阵，对象的分布、定位只需从矩阵的行内、行间计算目标节点的行号和列号即可.理论研究表明，该算法满足公平性、自适应性、紧凑性、节点变化对象迁移量较小的特点.实验结果表明，该算法的计算时间比一致性hash算法快40%，比跳跃hash算法快23%，极大地缩短了计算时间，且比一致性hash算法对象分布更加均匀.

摘要:分布式存储系统为了保证可靠性，会采用一定的存储冗余策略，如多副本策略、纠删码策略.纠删码相对于副本具有存储开销小的优点，但节点修复网络开销大.针对修复网络开销优化，业界提出再生码和以简单再生码为代表的局部可修复码，显著降低了修复网络开销.然而，现有的基于编码的分布式容错存储方案大都假设节点处于星型逻辑网络结构中，忽略了实际的物理网络拓扑结构和带宽信息.为了实现拓扑感知的容错存储优化，相关研究在纠删码和再生码修复过程中结合网络链路带宽能力，建立树型修复路径，进一步提高了修复效率.但是，由于编码和修复过程的差异性，上述工作并不适合于简单再生码修复.针对该问题，结合实际物理网络拓扑结构，将链路带宽能力引入到简单再生码的修复过程中，对带宽感知的简单再生码修复优化技术开展研究.建立了带宽感知节点修复时延模型，提出了基于最优瓶颈路径和最优修复树的并行修复树构建算法，并通过实验对算法性能进行了评估.实验结果表明，与星型修复方式相比，该算法有效地降低了节点修复时延，提高了修复效率.

摘要:随着大数据时代的到来，全球信息存储量呈现爆发式的增长，传统的存储系统在存储性能、存储容量、数据可靠性和成本等方面存在诸多不足.近年来，以云计算平台为依托的存储技术得到了飞速发展，成为处理海量数据的重要工具.针对分布式文件系统元数据管理的问题，提出了一种自适应元数据服务负载均衡策略.该策略主要包括以下3点内容：介绍了一种实时的元数据服务器的性能评价模型；提出了一种基于服务器负载变化的检测周期自适应调整机制；提出了一种基于元数据服务器性能指标的自适应负载均衡算法.实验结果证明了该方法的可行性、有效性和稳定性.

摘要:小数据同步写普遍存在于各种计算机环境中，并且可以由计算机系统的不同层次软件产生，从底层操作系统一直到上层应用软件都可以生成小数据同步写请求.然而，操作系统的文件系统是以块作为最小逻辑可寻址单位，小数据写将会导致严重的写放大问题，使得系统的I/O性能大幅度降低.为了解决上述问题，提出了一种I/O调度器，并将其命名为Hitchhike.该调度器可以识别小数据写，并通过对其他数据块中的数据进行压缩，将小数据嵌入到压缩出来的空间中，从而将小数据和该数据块一起写入到磁盘上，以异步回写的方式完成小数据的同步写，不仅有效缓解了磁盘的写放大问题，也极大地提高了小数据同步写的效率.基于Linux 2.6.32的Deadline调度器实现了Hitchhike原型系统，并利用Filebench基准测试来测试调度器在吞吐量、I/O延迟等方面的性能.通过与传统I/O调度器的性能进行比较，可以发现，Hitchhike调度器能够显著地提高小数据同步写的性能高达48.6%.

摘要:以SSD（solid state drive）为代表的新型存储介质在虚拟化环境下得到了广泛的应用，通常作为虚拟机读写缓存，起到优化磁盘I/O性能的作用.已有研究往往关注SSD缓存的容量规划，依据缓存读写命中率评价SSD缓存分配效果，未能充分考虑SSD的服务能力上限，难以适用于典型的分布式应用场景，存在虚拟机抢占SSD缓存资源，导致虚拟机中应用性能违约的可能.实现了虚拟化环境下面向多目标优化的自适应SSD缓存系统，考虑了SSD的服务能力上限.基于自适应闭环实现对虚拟机和应用状态的动态感知.动态检测局部SSD缓存抢占状态，基于聚类方法生成虚拟机的优化放置方案，依据全局SSD缓存供给能力确定虚拟机迁移顺序和时机.实验结果表明，该方法在应对典型分布式应用场景时可以有效缓解SSD缓存资源的争用，同时满足应用对虚拟机放置的需求，提升应用的性能并兼顾应用的可靠性.在Hadoop应用场景下，平均降低了25%的任务执行时间，对I/O密集型应用平均提升39%的吞吐率.在ZooKeeper应用场景下，以不到5%的性能损失为代价，应对了虚拟化主机的单点失效带来的虚拟机宕机问题.

摘要:通过对视频监控数据的特点和传统存储方案进行分析，提出一种高性能分布式存储系统解决方案.不同于传统的基于文件存储的方式，设计了一种逻辑卷结构，将非结构化的视频流数据以此结构进行组织并直接写入RAW磁盘设备，解决了传统存储方案中随机磁盘读写和磁盘碎片导致存储性能下降的问题.该方案将元数据组织为两级索引结构，分别由状态管理器和存储服务器管理，极大地减少了状态管理器需要管理元数据的数量，消除了性能瓶颈，并提供了精确到秒级的检索精度.此外，该方案灵活的存储服务器分组策略和组内互备关系使得存储系统具备容错能力和线性扩展能力.系统测试结果表明，该方案在成本低廉的PC服务器上实现了单台服务器可同时记录400路1080P视频流，写入速度是本地文件系统的2.5倍.

摘要:自20世纪60年代以来，虽然有Floyd-Hoare逻辑的出现，但使用形式化工具对命令式程序的正确性和可靠性进行自动验证，一直被认为是极具挑战性、神圣不可及的工作.20世纪末，由于更多科研的投入，特别是微软、IBM等大型公司研发部门的大量人力、物力的投入，程序验证方面在21世纪初取得了不少进展，例如用于验证空客代码无运行时错误的ASTRÉE工具、用于Windows设备驱动里关于过程调用的协议验证的SLAM工具.但这些工具并没有考虑动态创建的堆（heap）：ASTRÉE工具假设待验证代码没有动态创建的堆，也没有递归；SLAM假设待验证系统已经有了内存安全性.事实上，很多重要的程序，例如Linux内核、Apache、操作系统设备驱动程序等，都涉及到对动态创建堆的操作.如何对这类操作堆的程序（heap-manipulating programs）进行自动验证仍然是一个难题.2001年~2002年，分离逻辑（separation logic）提出后，其分离（separation）思想和相应的框（frame）规则使得局部推理（local reasoning）可以很好地应用到程序验证中.自2004年以来，基于分离逻辑对操作动态创建堆的程序进行自动验证方面的研究有了很大的进展，取得了很多令人瞩目的成果，例如SpaceInvader/Abductor，Slayer，HIP/SLEEK，CSL等工作.着重对这方面的部分重要工作进行阐述.

摘要:在当前的计算机系统架构和软件生态环境下，ROP（return-oriented programming）等基于二进制代码重用的攻击技术被广泛用于内存漏洞利用.近年来，网络空间安全形势愈加严峻，学术界、工业界分别从攻击和防护的角度对二进制代码重用技术开展了大量研究.首先介绍了二进制代码重用技术的基础.然后分析了二进制代码重用攻击技术的演变和典型攻击向量.同时，对基于控制流完整性和随机化的防护方法进行了讨论，对工业界最新的二进制代码重用防护机制CET（control-flow enforcement technology）和CFG（control flow guard）进行了剖析.最后讨论了二进制代码重用技术今后的发展方向，包括潜在的攻击面和防御机制增强的思路.

摘要:SIMD扩展部件是近年来集成到通用处理器中的加速部件，旨在发掘多媒体和科学计算等程序的数据级并行.控制依赖给发掘程序中的数据级并行带来了阻碍，当前，无论基于loop-based还是SLP的控制流向量化方法都需要if转换，而没有考虑循环内蕴含的向量并行度，导致生成的向量代码效率较低.此外，不精确的代价模型指导控制流向量化，同样导致生成的向量代码效率较低.为此，提出了改进的控制流SIMD向量化方法.首先，提出了含有控制依赖的循环分布算法，分离循环的可向量化部分和不可向量化部分，同时考虑分布时数据的局部性；其次，提出了一种直接向量化控制流的方法，该方法考虑了基本块间的向量重用；最后，利用精确的代价模型指导超字选择指令和超字条件分支指令的生成.实验结果表明：与现有的控制流向量化方法相比，改进方法生成的向量代码性能提高了24%.

摘要:动态污点跟踪技术展现了在移动隐私保护方面的强大功能，但存在系统性能较低问题.提出了一种基于即时编译的动态污点传播优化方法.首先，将程序逻辑精确抽象为污点传播逻辑，简化污点传播分析复杂性；然后，提出了一个污点传播框架，并证明了在该框架下污点传播分析的正确性和有效性；最后，采用消除、替换和移动等方法将冗余低效的污点传播代码转化为高效等价的污点传播代码.实验结果表明，经过优化后，单条热路径的污点传播代码节省了38%的内存占用和指令执行时间，系统整体性能平均提升了6.8%.

摘要:分析了触控交互技术在移动手持设备及可穿戴设备的应用现状及存在的问题.基于交互动作的时间连续性及空间连续性，提出了将触控交互动作的接触面轨迹与空间轨迹相结合，同时具有空中手势及触控手势的特性及优点的混合手势输入方法.基于连续交互空间的概念，将混合交互手势、空中手势、表面触控手势进行统一，建立了包括空中层、表面层、混合层的连续交互空间分层处理模型.给出了统一的信息数据定义及数转换流程.构建了通用性的手势识别框架，并对轨迹切分方法及手势分类识别方法进行了阐述.最后设计了应用实例，通过实验，对混合交互手势的可用性及连续空间分层处理模型的可行性进行了验证.实验结果表明，混合手势输入方式同时兼具了表面触控输入及空中手势输入的优点，在兼顾识别效率的同时，具有较好的空间自由度.

摘要:超扩展规则是对扩展规则的扩充，基于超扩展规则能够求得任意两个非互补且不相互蕴含的子句所能扩展出极大项集的交集、差集和并集，并将所得结果以EPCCL（each pair of clauses contains complementary literals）理论的形式保存.基于超扩展规则的性质，提出一种EPCCL理论编译算法：求交知识编译算法IKCHER（intersection approach to knowledge compilation based on hyper extension rule）.该算法适合难解类SAT问题的知识编译，也是一种可并行的知识编译算法.研究了如何实现多个EPCCL理论的求交操作，证明了EPCCL理论的求交过程是可并行执行的，并设计了相应的并行求交算法PIAE（parellel intersection of any number of EPCCL）.通过对输入EPCCL理论对应普通子句集的利用，设计了一种高效的并行求交算法imp-PIAE（improvement of PIAE）.基于上述算法，还设计了两种并行知识编译算法P-IKCHER（IKCHER with PIAE）和impP-IKCHER（IKCHER with imp-PIAE），分别采用PIAE并行合并算法和imp-PUAE并行合并算法.最后，通过实验验证了，大部分情况下，IKCHER算法的编译质量是目前为止所有EPCCL理论编译器中最优的，P-IKCHER算法所使用的合并策略并没有起到加速的效果，反而使得编译效率和编译质量有所下降；impP-IKCHER算法提高了IKCHER算法的编译效率，CPU四核环境下最高可提高2倍.

摘要:随着视频采集和网络传输技术的快速发展以及个人移动终端设备的广泛使用，大量图像数据以集合形式存在.集合内在结构的复杂性使得如何度量集合间距离成为图像集分类的一个关键问题.为了解决这一问题，提出了一种基于双稀疏正则的图像集距离学习框架（double sparse regularizations for image set distance learning，简称DSRID）.在该框架中，两集合间距离被建模成其对应的内部典型子结构间的距离，从而保证了度量的鲁棒性和判别性.根据不同的集合表示方法，给出了其在传统的欧式空间以及两个常见的流形空间，即对称正定矩阵流形（symmetric positive definite matrices manifold，简称SPD manifold）和格林斯曼流形（Grassmann manifold）上的实现.在一系列的基于集合的人脸识别、动作识别和物体分类任务中验证了该框架的有效性.

摘要:大数据蕴含着巨大的价值.分析类查询是获取数据价值的一种重要手段.为及时把握分析结果的变化，查询需要周期性地重复.为此，将不可避免地引入对旧数据的重复分析.目前，以重用历史数据的中间结果、优化冗余计算为核心思路的增量分析技术，存在用户透明性不佳、对历史结果存储位置的选择不够智能化等问题，对周期性增量查询的优化效果有限.从兼顾用户透明性和优化收益的角度出发，设计了一种以语义规则为指导的增量优化方法.该方法扩展了增量描述语法，以查询操作符的操作语义和输出语义指导对历史数据存储、合并位置的选择，再根据代价模型和物理查询任务的划分位置对选择结果进行调整，生成优化后可以在分布式计算框架（如MapReduce）周期性调度执行的物理查询任务.以Apache Hive为基础，实现了上述方法的原型HiveInc.实验结果表明：对于扩展了增量语法描述的TPC-H测试集，HiveInc相对于优化前可以获得平均2.93倍、最高5.78倍的加速；与经典的优化技术IncMR、DryadInc相比，分别可以获得1.69倍和1.61倍的加速.

摘要:随着社交网络的不断发展，朋友推荐已成为各大社交网络青睐的对象，在能够帮助用户拓宽社交圈的同时，可以通过新朋友获取大量信息.由此，朋友推荐应该着眼于拓宽社交圈和获取信息.然而，传统的朋友推荐算法几乎没有考虑从获取信息的角度为用户推荐潜在好友，大多是依赖于用户在线的个人资料和共同的物理空间中的签到信息.而由于人们的活动具有空间局部性，被推荐的好友分布在用户了解的地理空间，并不能满足用户通过推荐的朋友获取更多理信息的需求.采用用户在物理世界中的签到行为代替虚拟社交网络中的用户资料，挖掘真实世界中用户之间签到行为的相似性，为用户推荐具有相似的签到行为且地理位置分布更广泛的陌生人，能够增加用户接受被推荐的陌生人成为朋友的可能性，在保证一定的推荐精度的基础上，增加用户的信息获取量.采用核密度估计估算用户签到行为的概率分布，用时间熵度量签到行为在时间上的集中程度，选择可以为用户带来更多新的地理信息的陌生人作为推荐的对象，通过大规模Foursquare的用户签到数据集，验证了该算法能够在精度上保证与目前已有的LBSN上陌生人推荐算法的相似性，在信息扩大程度上高于上述已有算法.

摘要:影响最大化旨在从给定的社会网络中寻找出一组影响力最大的子集.现有工作大都在假设实体点（个人或博客等）影响关系已知的情况下，关注于分析单个实体点的影响力.然而在一些实际场景中，人们往往更关注区域或人群等这类团体的组合影响力，如户外广告、电视营销、疫情防控等.研究了影响力团体的选择问题：（1）基于团体的关联发现，建立了团体传播模型GIC（group independent cascade）；（2）根据GIC模型，给出了贪心算法CGIM（cascade group influence maximization），搜索最具影响力的top-k团组合.在人工数据和真实数据上，实验验证了该方法的效果和效率.

摘要:目前，基因芯片技术飞速发展，促使生物学家积累了大量的不同实验条件下的基因表达数据.事实证明，基因芯片数据分析在理解基因功能、基因调控和分子生命过程中发挥着重要作用.保序子矩阵（order-preserving submatrix，简称OPSM）是基因芯片数据分析技术中的一种有效模型，其可以发现在部分基因和不同实验条件下具有相同表达趋势的聚类.在分析基因表达机理的过程中，OPSM的检索无疑节省了生物学家的时间与精力.目前，OPSM的查询主要是基于关键词的检索方法，但是分析者对结果具有微弱的控制力.通常，分析者所能决定的临时的参数设置往往偏离其领域知识，致使检索结果与真实想要的结果相去甚远.为了解决上述问题，提出两类基于数字签名与Trie的OPSM索引与约束查询方法.在真实数据上进行了大量的实验，实验结果表明，所提出的方法具有良好的有效性与可扩展性.

摘要:模块化数据中心网络的模块间互联结构和路由负责模块的有效组织以及不同模块服务器间的高效通信，使得如何设计具有高带宽、高容错和高可扩展能力的互联结构以支持大规模、超大规模数据中心的构建，成为模块化数据中心网络需要解决的首要问题.提出了一种构建超大规模模块化数据中心的模块间互联结构MDKautz.该结构通过模块内大量未被使用的交换机预留高速端口将模块以Kautz图互连，在无需额外增加任何高端交换设备的前提下，构造出具有高带宽、高容错和灵活可持续扩展性的超大规模数据中心网络.对MDKautz的构建方法、路由策略以及扩展方法进行了分析.数学分析和模拟实验结果证明了该新型网络结构具有良好的拓扑特性和通信性能，可有效支持数据中心高带宽、高容错的典型应用.

摘要:现有的视频编码方法单独针对不同的编码技术进行优化，虽然简化了算法的实现，但却忽略了这些技术之间的内在关系而局限了性能的进一步提升.尝试针对HEVC中的分像素插值和分像素运动估计，建立一种整合的优化算法，同时提升两者的计算速度.首先，通过细分不同分像素的插值方法，把每个分像素的插值代价融合在分像素运动估计的搜索中，并构建一种性价比优先的分像素运动估计方法.该运动估计方法的每一步搜索都按照最小化计算代价和最大化率失真收益的原则进行，保证以最小的计算消耗获得最优的性能.其次，为了配合该方法，针对HEVC的特性构建了一种分区域分像素集的分像素插值算法.该插值算法在分像素运动估计过程中仅动态地计算所用到的分像素，解决了现有插值算法无法同时降低重复计算和冗余计算的问题.实验结果表明，该整合算法可以在几乎不产生率失真性能损失的情况下，大幅度地加快分像素运动估计和插值的速度.