一种寄存器分配算法

研究高级综合中一种新的寄存器分配算法,算法通过对冲突图的着色得到最小的寄存器数目,算法分为两步,第一步是变量的均等化,扩展每个变量的生存期使变量在各个分支结构中的生存期相同,即一个变量只有一个生存期;第二步对均等化的变量在每个分支块和分支块的第三个路径中搜索,提出一个近似算法,实验证明该算法能够得到优化的解。     

一种基于可测性的寄存器分配算法

提出了一种在高层次综合的寄存器分配过程中考虑可测性的算法，该算法在将一个调度好的CDFG（Control Data Flow Graph)的变量分配到相应的寄存器的过程中，通过对未能分配复用到输入、输出寄存器的变量进行可测性处理，达到提高设计可测性的目的，同时在进行可测性处理的时候，定义了CDFG的节点的可测性测度方法。     

多寄存器组网络处理器上的寄存器分配技术

针对传统的图着色寄存器分配算法不能直接处理网络处理器的操作问题,提出了一种多寄存器组网络处理上的寄存器分配技术．在依次分析了一个符号寄存器可能位于哪些寄存器组？如果没有候选组,该如何解决这种冲突？如果有多个候选组,该选用哪个组等问题的基础上,通过将这些方法与图着色寄存器分配算法相融合,在IXP上实现了这种多寄存器组的寄存器分配,提高了它的可编程性．这种方法也可运用到其它具有类似寄存器结构的处理器上．     

降低寄存器软错误的静态寄存器重分配方法

针对寄存器交换方法在降低寄存器软错误率过程中,未考虑寄存器分配过程对软错误所带来影响的问题,提出一种基于活跃变量对于软错误影响的静态寄存器重分配方法。首先,引入活跃变量权值来评估其对寄存器软错误的影响;然后,提出两条规则,在进行寄存器交换后对活跃变量进行寄存器的重新分配。该方法在更小粒度的活跃变量层次,进一步降低了寄存器软错误率。实验和分析表明,相对于寄存器交换方法,该策略能进一步降低30%的寄存器软错误率,增强了寄存器的可靠性。     

基于存储资源迭代重用的低成本寄存器重命名方法

针对超标量深流水线中物理寄存器资源冲突造成的流水线阻塞问题,提出了一种多指令共享同一物理寄存器资源的非阻塞指令发射方法。该方法可在物理寄存器资源冲突下继续分配物理寄存器,利用发射缓冲队列临时缓冲冲突的指令,增加发射流水级实际可分配的物理寄存器数量,释放发射窗口,提高物理寄存器使用的并行性。实验结果表明:相对于传统重命名方法,该方法可减少27.3%的物理寄存器资源实现传统方法相同的性能。     

一种应用加权相容图的可测性寄存器分配算法

提出一种基于加权相容图的可测性寄存器分配模型,给出一个基于可测寄存器分配准则的相容图边的权值公式,并运用改进的加权团划分算法对加权相容图进行处理,从而实现了在寄存器分配过程中同时考虑4个可测性准则,达到提高设计可测性的目的.实验结果表明了算法在可测性方面的有效性.     

基础数学库中的MCET寄存器分配方法

针对基础数学库中的寄存器分配特点,利用最常用情况执行时间MCET(Most-Case Execution Time)模型对经典的线性扫描寄存器分配算法进行了扩展。该算法能够很大程度上减少数学库中的最常用路径上的变量溢出过程,将变量溢出过程分配到非常用路径上,从而减少全局的寄存器溢出开销,提高数学库的性能。对基础数学库中函数的应用此分配算法之后,最常用路径执行时间、平均路径执行时间都得到了不同程度的提高。     

含有效冲突的恒定连续Petri网演变图及构造算法

最大速度恒定的连续Petri网(CCPN)是由David首先提出的一类时延连续Petri网模型,构造其演变图是对其性质进行分析的一种有效方法。而对于含有效冲突的最大速度恒定的连续Petri网,由于有效冲突所引起的变迁激发的不确定性,使得构造演变图变得较为困难。基于有效冲突的两种解决方式——确定优先级或按比例分配流量,给出了计算各变迁瞬发速度的算法2;进而对含有效冲突且有界的CCPN,提出了演变图构造算法3,利用其演变图,可以对含有效冲突的CCPN进行性能分析。     

一种基于谓词执行优化技术的寄存器分配算法

对采用谓词执行优化技术后的编译代码,为了更高效地进行寄存器分配,首先介绍了Sias等人提出的一种基于二进制决策图（BDD）的谓词分析系统;然后在其基础上,对传统寄存器分配算法进行改进,给出了一种建立精化干涉图的新算法;最后将算法在学院研制的YHFT—DSP／700芯片的编译器上实现,实验结果表明,减少了所需寄存器数目,缩短了代码执行时间,获得了较好的性能提高．     

微码自动生成系统中的寄存器分配策略

七十年代以来,人们越来越重视对微程序设计和固件工程的研完,尤其是对高级微码自动生成系统的研究。在一个高级微码自动生成系统中,为了将高级微语言中出现的形式变量映射到目标机的物理资源上,不可避免地要遇到寄存器再分配问题。一个寄存器器分配策略的优劣,将直接影响到所产生微码的效率。本文给出的是一种利用给寄存器加特征值的方法来进行寄存器再分配。     

一种基于WatiJ的Deep Web蜘蛛研究

Deep Web中相当一部分内容因为动态网页存在而不能进行有效抓取。为此,设计并实现一种基于Web自动化测试工具——WatiJ的Deep Web网络蜘蛛。阐述利用WatiJ实现用户提交查询表单、循环点击翻页按钮等拟人交互方式的原理,通过实例给出动态网页抓取的关键步骤。实验结果表明,该蜘蛛是针对授权数据源进行动态网页抓取的一种有效解决方案。     

一种网页分类中基于图的半指导学习算法

提出一种基于图的半指导学习算法用于网页分类.采用k近邻算法构建一个带权图,图中节点为已标志或未标志的网页,连接边的权重表示类的传播概率,将网页分类问题形式化为图中类的概率传播.为有效利用图中未标志节点辅助分类,结合网页的内容信息和链接信息计算网页间的链接权重,通过已标志节点,类别信息以一定概率从已标志节点推向未标志节点.实验表明,本文提出的算法能有效改进网页分类结果.     

All Structured Programs Have Small Tree Width and Good Register Allocation

The register allocation problem for an imperative program is often modeled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a flow graphGis the intersection graph of some connected subgraphs ofG. These connected subgraphs represent the lives, or life times, of variables, so the coloring problem models that two variables with overlapping life times should be in different registers. For general programs with unrestricted gotos, the interference graph can be any graph, and hence we cannot in general color within a factorO(n) from optimality unless NP=P. It is shown that if a graph has tree widthk, we can efficiently color any intersection graph of connected subgraphs within a factor (k/2+1) from optimality. Moreover, it is shown that structured (≡goto-free) programs, including, for example, short circuit evaluations and multiple exits from loops, have tree width at most 6. Thus, for every structured program, we can do register allocation efficiently within a factor 4 from optimality, regardless of how many registers are needed. The bounded tree decomposition may be derived directly from the parsing of a structured program, and it implies that the many techniques for bounded tree width may now be applied in compiler optimization, solving problems in linear time that are NP-hard, or even P-space hard, for general graphs.     

基于权限验证图的Web应用访问控制漏洞检测

针对Web应用中的访问控制漏洞缺乏有效检测手段的问题，提出了一种基于权限验证图的检测算法。首先，在程序控制流图（CFG）的基础上，识别权限验证节点和资源节点，通过T和F边将节点连成权限验证图。然后，遍历资源节点对应的所有权限验证路径，计算路径验证权限，与资源节点访问权限比较，检测是否存在访问控制漏洞。实验结果表明，在7个Web应用中，发现了8个已知和未知漏洞，相比较于已有的访问控制漏洞检测算法，该算法可以有效检测4种访问控制漏洞，扩大了漏洞检测范围。     

基于搜索的物联网设备识别框架

越来越多的物联网设备接入到互联网中,但由于设计上的缺陷或者缺乏安全防护手段,这些暴露在公网上的物联网设备极容易受到黑客的攻击与利用。研究表明,具有相似产品属性的物联网设备很有可能存在相同漏洞,因此有效的识别网络空间中的物联网设备,对其产品属性,如设备品牌、型号等相关信息进行细粒度识别和标定,对把握网络空间实体设备的安全态势具有重要意义。本文提出一种基于搜索的物联网设备识别框架,利用物联网设备协议标语中富含的产品属性信息,通过自动化网络搜索技术构建物联网设备信息库,进而实现对未知新设备细粒度地自动分级识别和标定。通过公网实验,该框架能够很好识别视频监控和工控设备的产品属性,型号识别准确率均超过90%。     

Solving the Register Allocation Problem for Embedded Systems Using a Hybrid Evolutionary Algorithm

Embedded systems are unique in the challenges they present to application programmers, such as power and memory space constraints. These characteristics make it imperative to design customized compiler passes. One of the important factors that shape runtime performance of a given embedded code is the register allocation phase of compilation. It is crucial to provide aggressive and sophisticated register allocators for embedded devices, where the excessive compilation time can be tolerated due to high demand on code quality. Failing to do a good job on allocating variables to registers (i.e., determining the set of variables to be stored in the limited number of registers) can have serious power, performance, and code size consequences. This paper explores the possibility of employing a hybrid evolutionary algorithm for register allocation problem in embedded systems. The proposed solution combines genetic algorithms with a local search technique. The algorithm exploits a novel, highly specialized crossover operator that takes into account domain-specific information. The results from our implementation based on synthetic benchmarks and routines that are extracted from well-known benchmark suites clearly show that the proposed approach is very successful in allocating registers to variables. In addition, our experimental evaluation also indicates that it outperforms a state-of-the-art register allocation heuristic based on graph coloring for most of the cases experimented.     

Compact representation of Web graphs with extended functionality

The representation of large subsets of the World Wide Web in the form of a directed graph has been extensively used to analyze structure, behavior, and evolution of those so-called Web graphs. However, interesting Web graphs are very large and their classical representations do not fit into the main memory of typical computers, whereas the required graph algorithms perform inefficiently on secondary memory. Compressed graph representations drastically reduce their space requirements while allowing their efficient navigation in compressed form. While the most basic navigation operation is to retrieve the successors of a node, several important Web graph algorithms require support for extended queries, such as finding the predecessors of a node, checking the presence of a link, or retrieving links between ranges of nodes. Those are seldom supported by compressed graph representations.This paper presents the k²-tree, a novel Web graph representation based on a compact tree structure that takes advantage of large empty areas of the adjacency matrix of the graph. The representation not only retrieves successors and predecessors in symmetric fashion, but also it is particularly efficient to check for specific links between nodes, or between ranges of nodes, or to list the links between ranges. Compared to the best representations in the literature supporting successor and predecessor queries, our technique offers the least space usage (1–3 bits per link) while supporting fast navigation to predecessors and successors ($2–8\mathrm{\mu }\mathrm{s}$ per neighbor retrieved) and sharply outperforming the others on the extended queries. The representation is also of general interest and can be used to compress other kinds of graphs and data structures.     

无线Mesh网络中混合信道分配算法研究

根据多射频多信道无线Mesh网络的特点,提出一种基于节点干扰的混合信道分配算法。将节点间的链路分为正向链路和反向链路,通过概率模型分析链路干扰,计算节点间链路的权重,建立带权重的有向网络连接图。根据链路权重为节点固定接口分配信道,减小可切换接口在信道改变过程中引起的网络干扰。扩展的NS2仿真结果表明,该算法能有效降低链路干扰,提高网络吞吐量。     

基于蜜罐在线恶意网页检测系统研究与设计

针对网页安全威胁的动态性、广泛性等特点,设计了一个基于蜜罐在线恶意网页检测系统。该系统使用URL数据表来记录网页地址,同时结合蜜罐技术对URL数据表不存在或存在但还需进行检测的网页进行综合检测,实时检测出用户需要浏览的网页的安全状态,避免恶意网页的攻击,从而提高人们网络活动的安全性。