稀疏矩阵在统计文件组织中的应用

本文介绍了在统计文件组织中运用稀疏矩阵的一种数据结构及其上的操作流程,并结合图书流通信息统计实例,辅以适当的矩阵运算,给出了一些有用的统计信息。采用此结构,能以较少的代价来组织大量的数据。若施以有意义的矩阵运算,则可取得尽可能多的统计信息。对于研制事务处理,企业管理和物资管理等统计软件来说,有一定的实用意义。     

基于Coq的分块矩阵运算的形式化

矩阵是工程领域中常用的一种数据结构,在深度学习领域,矩阵乘法是神经网络训练中的核心技术之一,面对大型矩阵的运算问题,分块矩阵技术可将大矩阵运算转换为小矩阵运算以实现并行运算,并且能够大幅度减少矩阵运算步骤并且提高矩阵运算速度.本文首先对目前学术界的矩阵形式化工作进行了系统总结并且分析了矩阵形式化的主要几种方法;其次介绍并完善了基于Coq记录类型的矩阵形式化方法,其中包括提出新的矩阵等价定义、对之前的形式化工作进行了整理和完善,并证明了一组新的引理;在此基础上进一步实现了分块矩阵运算的形式化,讨论了该类型的归纳证明的难点和解决方法;最终实现了矩阵与分块矩阵形式化的不同类型的基础库.     

面向稀疏矩阵访存特性的Cache划分

稀疏矩阵向量乘是许多科学计算的核心,计算中大量的间接和随机访存成为计算的主要瓶颈。本文通过分析稀疏矩阵向量乘运算的数据结构和计算过程,得到计算中不同数据的访存特征,并提出了一种面向数据访存特性的Cache划分方法。对12个稀疏矩阵向量乘的测试表明,本文的Cache划分方法能有效地提高可重用向量的Cache命中率,同时减少计算对Cache空间的需求。     

一种用于规则QC-LDPC码的高效译码方法

针对一类规则QC-LDPC码,提出一种高效的Log-BP译码方法,通过矩阵分裂,将原监督矩阵分裂成多个小矩阵,将原本的校验节点更新运算拆分成多次处理,以降低log-BP迭代运算的复杂度,给出该方法的迭代运算顺序。与现有的log-BP译码方法相比,该方法在相同的码速率下,校验节点运算单元与变量节点运算单元总规模减小了1/3;在相同的硬件资源下,译码速率提高了1/3,且校验节点运算单元与变量节点运算单元结构趋于对称,有利于设置更少的流水线级数、获得更好的时钟性能。     

一种基于MapReduce并行框架的大规模矩阵乘法运算的实现

在机器学习算法中,矩阵乘法运算是一种基本运算.而扩大矩阵乘法的运算规模并降低其运算时间,将有利于满足机器学习算法处理大规模数据的要求.将MapReduee并行框架用于分块矩阵乘法,实现一种用于大规模矩阵乘法运算的方法.理论分析和实验结果表明该方法在处理大规模矩阵乘法上具有极大的潜能,并且随着计算节点的增加从而获得较好的加速比.     

沿次对角线带宽为m的稀疏矩阵压缩存储的通用寻址公式

本文属于数据结构的课题,它将文献[2]与[3]中给出的沿主对角线具有m条非零元素的稀疏矩阵压缩 存储寻址公式推广到沿次对角线分布的类似矩阵上,得到了新的寻址公式,并用例子验证了公式的正确性。     

数据结构实用教程(Java语言描述)

<正>本书是为全国高等院校计算机及相关专业开设数据结构课程而精心编著的一本实用教材。本书按照面向对象的程序设计方法,采用目前广泛使用的Java语言描述各种数据结构和运算方法,使得一种数据结构对应一种操作接口,进而通过     

大数据结构化与数据驱动的复杂系统维修决策

现代大型机电系统组成结构越来越复杂、智能化程度越来越高, 然而系统维修工作却越来越困难; 另外, 尽管快速发展的信息技术使得系统内部的各种流数据得到了有效的保存, 但却缺乏对这类大数据的有效利用、实现复杂系统的维修控制与决策.为此, 提出了大数据结构化与数据驱动的复杂系统维修决策方法.大数据结构化使用了层次分析法(Analytic hierarchy process, AHP)的思想, 依次建立系统维修的各个层级模型; 基于模型抽象出支持系统维修的数据变量、提炼出各层级变量的表达函数; 研究进一步实现了维护决策的数据驱动技术, 在模型和函数之上定义了数据状态块矩阵, 通过设计矩阵的特殊运算算法完成维修决策的数据驱动.最后, 使用一个具体的例子来说明提出方法的可用性, 结果证明提出的方法是可行的, 符合设备维修决策建设目标, 即维修方法经济、高效与实用.     

云环境中支持隐私保护的可计算加密方法

随着云计算的深入发展,隐私安全成为了云安全的一个关键问题.加密是一种常用的保护敏感数据的方法,但是它不支持有效的数据操作.为了提供云计算环境中的隐私保护,设计了一个基于矩阵和向量运算的可计算加密方案CESVMC.通过运用向量和矩阵的各种运算,CESVMC实现了对数据的加密,并支持对加密字符串的模糊检索和对加密数值数据的...     

数据结构实用教程(Java语言描述)

本书是为全国高等院校计算机及相关专业开设数据结构课程而精心编著的一本实用教材。本书按照面向对象的程序设计方法,采用目前广泛使用的Java语言描述各种数据结构和运算方法,使得一种数据结构对应一种操作接口,进而通过不同的存储类型来实现。     

Generalising the array split obfuscation

An obfuscation is a behaviour-preserving program transformation whose aim is to make a program “harder to understand”. Obfuscations are mainly applied to make reverse engineering of object-oriented programs more difficult. In this paper, we propose a fresh approach by obfuscating abstract data-types allowing us to develop structure-dependent obfuscations that would otherwise (traditionally) not be available. We regard obfuscation as data refinement enabling us to produce equations for proving correctness. We model the data-type operations as functional programs making our proofs easy to construct.We show how we can generalise an imperative obfuscation - an array split - so that we can apply it to abstract data-types and we give specific examples for lists and matrices. We develop a theorem which allows us, under certain conditions, to produce obfuscated operations directly. Our approach also allows us to produce random obfuscations and we give an example for our list data-type.     

一种数据结构制导的线程划分方法与执行模型

在对程序进行并行化时,为了保证结果的正确性,并行编译器只能采取一种保守的策略,也就是,如果它不能确定两段代码在并行执行时是否会发生冲突,它就不允许这两段代码并行执行.虽然这种做法保证了正确性,但同时也限制了对并行性的开发.在这种背景下,许多推测多线程方法被提了出来,这些方法通过允许可能冲突的代码段并行执行来把握更多的并行机会,同时,通过从冲突中恢复来保证结果的正确性.然而,传统推测多线程方法所使用的“沿控制流将串行程序划分为多个线程”的做法并不适合不同数据结构上的操作在控制流中相互交错的情况,因为如果沿控制流将程序线性地划分为多个线程,则同一个数据结构上的操作将被分到不同的线程中,从而非常容易发生冲突.为了有效地对这些程序进行并行化,提出了一种基于数据结构的线程划分方法与执行模型.在这种方法中,程序中的对象被划分成多个组,同一组中对象上的操作被分派到同一个线程中去执行,从而降低了在同一个数据结构上发生冲突的可能性.     

Data schemata based on directed graphs

Rooted, labeled, directed graphs (RLDs) are taken as the basis for describing data structures. A constructive formalism is set up to describe RLDs, generate them by means of grammars, and carry out operations such as accessing nodes, inserting and deleting data items, and recognizing graph patterns. It is shown how the formalism can be translated into languages for data definition and data manipulation, of the type associated with data-base systems. The availability of the formalism allows a systematic development of such languages, and provides a method of incorporating consistency preconditions to structural operations and proving the correctness of the data structures that arise in using such languages.     

Inferring functional properties of matrix manipulating programs by abstract interpretation

We present a new static analysis by abstract interpretation to prove automatically the functional correctness of algorithms implementing matrix operations, such as matrix addition, multiplication, general matrix multiplication, inversion, or more generally Basic Linear Algebra Subprograms. In order to do so, we introduce a family of abstract domains parameterized by a set of matrix predicates as well as a numerical domain. We show that our analysis is robust enough to prove the functional correctness of several versions of the same matrix operations, resulting from loop reordering, loop tiling, inverting the iteration order, line swapping, and expression decomposition. We extend our method to enable modular analysis on code fragments manipulating matrices by reference, and show that it results in a significant analysis speedup.     

Verifying abstract data types with SNOBOL4

The presentation of an abstract data type by a series of equational axioms has become an accepted specification mechanism. Verifying the correctness of such specifications has been recognized as a problem troubling their use. A means is presented for experimenting with a directly executable version of the axioms without having to choose representations for the data structures or describe algorithms for the operations.     

基于底层虚拟机的标识符混淆方法

针对现有代码混淆仅限于某一特定编程语言或某一平台,并不具有广泛性和通用性,以及控制流混淆和数据混淆会引入额外开销的问题,提出一种基于底层虚拟机（LLVM）的标识符混淆方法。该方法实现了4种标识符混淆算法,包括随机标识符算法、重载归纳算法、异常标识符算法以及高频词替换算法,同时结合这些算法,设计新的混合混淆算法。所提混淆方法首先在前端编译得到的中间文件中候选出符合混淆条件的函数名,然后使用具体的混淆算法对这些函数名进行处理,最后使用具体的编译后端将混淆后的文件转换为二进制文件。基于LLVM的标识符混淆方法适用于LLVM支持的语言,不影响程序正常功能,且针对不同的编程语言,时间开销在20%内,空间开销几乎无增加;同时程序的平均混淆比率在77.5%,且相较于单一的替换算法和重载算法,提出的混合标识符算法理论分析上可以提供更强的隐蔽性。实验结果表明,所提方法具有性能开销小、隐蔽性强、通用性广的特点。     

一种XML数据并行更新方法*

提出了一种支持在分布式系统中并行地修改XML数据的方法策略,实现了不同的系统客户端可以同时修改同一个XML数据的不同部分或相同部分.支持修改操作的分散式管理,即客户端在不与服务器进行交互的情况下进行正确的修改.支持动态客户端和动态权限控制信息,适用于在更新过程中参与更新的客户端和更新权限都发生变化的情况.     

基于分支混淆算法的隐私数据库自适应加密方法

为有效降低隐私数据库中数据泄露的可能性,进一步提高数据安全性,本文设计一种基于分支混淆算法的隐私数据库自适应加密方法。在收集应用程序对数据库的请求内容的基础上,利用分支混淆算法对隐私数据库内数据的特征进行分类,并选取朴素贝叶斯分类器对数据库内混淆点实施分类,从而确定数据库中数据的字段类型,基于此,针对不同字段类型数据选取相应加密算法。其中,数值类型数据采用保序加密算法,等值比较类型数据采用等值加密算法,文本类型数据采用分词辅助索引加密算法。在加密数值型、时间类型、字符型字段的同时,保留偏序特性和可检索特性。实验结果表明提出的方法可实现对隐私数据库内不同字段类型数据的有效加密,且加密所需的时间开销较小,安全性高。     

分支混淆中的条件异常代码构造研究

当前分支混淆技术通过构造条件异常代码和异常处理替代条件跳转指令,隐藏分支选择指令的地址,提高约束条件获取的难度,从而对抗符号执行。当前方法构造的条件异常代码中,关键数据具有二值性问题,有利于分支混淆的检测、发现和约束条件获取,降低了混淆的隐蔽性和与符号执行的对抗性;基于该缺点,提出一种使关键数据具有多样性特征的条件异常代码构造方法,增加了混淆的隐蔽性和约束条件的获取难度,提高分支混淆对抗符号执行的强度;通过结构化异常处理实现了基于新型条件异常代码构造的分支混淆原型系统,并对混淆进行了测试和分析。     

Verifying atomic data types

Atomic transactions are a widely-accepted technique for organizing computation in fault-tolerant distributed systems. In most languages and systems based on transactions, atomicity is implemented through atomic objects, typed data objects that provide their own synchronization and recovery. Hence, atomicity is the key correctness condition required of a data type implementation. This paper presents a technique for verifying the correctness of implementations of atomic data types. The significant aspect of this technique is the extension of Hoare's abstraction function to map to a set of sequences of abstract operations, not just to a single abstract value. We give an example of a proof for an atomic queue implemented in the programming language Avalon/C++.