基于层次式有向超图模型的胚胎硬件功能描述转换方法

当前胚胎硬件的实际工程应用受到限制,原因在于其应用设计自动化程度低,功能分化主要由人工完成,导致大规模电路功能分化难以实现.基于大规模电路功能分化的需要,针对典型多层胚胎硬件结构,提出了胚胎硬件功能的层次式有向超图描述及其存储方式,开发了基于正则匹配的硬件语言描述到层次式有向超图的转换算法,从而有效地将胚胎硬件功能分化问题转换为不同粒度的超图划分问题.为了建立分粒度层次式有向超图模型,进而设计并实现了胚胎硬件的硬件语言描述到有向超图的转换系统(Hypergraph For Embryonics,HGFE).实验及分析表明,该系统适用于几十门至几万门的测试电路,为胚胎硬件功能分化提供了良好的图论模型,并和有向无环图对比,建模时间减少了至少28.7%,存储空间减少了至少30.1%,验证了该方法的优越性.

基于有向超图的资源约束下企业过程结构优化

为了提高企业过程结构优化的实用性、合理性以及计算机支持性,提出了基于有向超图和资源约束的优化方法.根据优化需求,通过对考虑了支持资源的过程进行不同的有向超图建模,利用有向超图的性质以及超图上所附加的过程语义,把过程结构优化转化为有向超图的切割和活动合并问题,并给出具体求解过程.求得的过程为一个结构和支持资源都优化的过程.最后,通过举例验证该方法可行、有效.

一种基于有向超图的规则库冗余及环路检测方法

当规则库的规模随着知识的更新而不断增大,规则库的维护就变得日益重要.其中,规则库的冗余和环路是影响规则库效率的重要问题.针对含有复合规则的产生式规则库,提出了一种基于有向超图的规则库表达方法,定义了其邻接矩阵和可达矩阵并推导出可达矩阵的计算方法.在此基础上给出了基于可达矩阵的冗余和环路检测算法.与已有的基于有向超图的算法相比,新算法图更简洁,矩阵规模更小,从而检测效率得到提高.实例证明该算法是有效可行的.

基于有向超图的工作流资源分配均衡优化方法

为了拓展工作流资源分配均衡优化的深度和广度,提出了一种考虑过程支持资源变化与过程结构变化相互影响的优化方法.通过对过程进行扩展超图建模,利用超图的性质以及活动能力需求集与支持资源能力集之间的耦合,给出了过程结构随支持资源变化而变化的形式化处理规则;给出了由不同结构过程构成的、用于工作流资源分配均衡优化超图模型(DHM-WRAB)的建模规则,使工作流资源分配均衡优化转化为具有权因子的超图最短路径求解问题,并给出求解过程;最后,通过举例证明该方法可行、有效.

基于有向超图的参数代表示模型及其实现

本文提出了一种基于有向超图的参数化图形表示模型．它不仅能够表示图形的尺寸约束和几何约束，而且能够支持图形拓扑结构变化和工程设计约束的表示．在交互绘制图形对象的同时直接建立参数化图形约束模型．由于在图形构造的每一步都保证约束的一致性，因此，不会出现过约束或欠约束的情况．经实践表明，该模型具有实用方便、高效可行的特点，适合于系列化产品的参数化ＣＡＤ系统建模和绘图．

基于赋权有向超图的云计算依赖任务调度研究

如何对依赖任务进行高效合理的调度是云计算急需解决的关键问题之一。对云计算环境下的依赖任务调度系统进行了形式化描述。采用赋权有向无环超图来构造依赖任务调度问题的数学模型,结点对应于依赖任务,有向超边对应于任务之间的执行先后依赖关系。将云计算依赖任务调度问题转换为赋权有向超图的优化划分问题,提出了基于多水平方法和赋权有向超图的依赖任务划分优化算法。设计并实现了基于多水平方法的云计算依赖任务调度原型系统。在Cloud Sim云计算仿真实验平台下,与Min-Min算法、Max-Min算法进行了对比实验,实验数据对比表明该算法在减少依赖任务执行时间的同时,优化了资源负载均衡性能。

网格优化有向超图任务调度算法

任务调度是网格计算的一个重要部分.分析网格环境下任务调度的特点以及传统DAG图的优缺点,吸取有向超图的优点,将有向超图理论融合网格环境特征,建立了网格环境下的优化有向超图模型,并在此基础上通过网格优化有向超图的水平构形、标号及带宽计算实现任务对网格资源的映射与调度,提出网格优化有向超图任务调度算法GODHTS.模拟实验结果证明了该模型及其算法的有效性和优越性.

网格任务调度的有向超图划分算法

网格计算是当前一个活跃的研究领域,其中任务调度是一个重要部分。根据网格环境下任务调度及传统DAG图的特点,吸取有向超图的优点,将有向超图理论融合任务调度特征,建立了基于划分的网格任务调度有向超图模型,并在此基础上通过对网格有向超图的划分实现任务对网格资源的映射与调度,提出了一种基于有向超图划分的网格任务调度算法HPGTS。模拟仿真实验结果证明了该模型及其算法的有效性和优越性。

有向超图理论的发展和应用

简要介绍有向超图理论的发展，及其在电网络分析与综合方面应用的一些研究成果。

一种XDL网表电路到有向超图的转换系统

FPGA电路网表的XDL描述文件,不仅能通过解析来抽取FPGA设计的Inst电路单元和Net电路信号,而且能用于构建FPGA电路网表中信号传播的抽象数学模型.本文通过有向超图来构建FPGA电路网表中信号的前向拓扑关系,其中FPGA电路单元的有效管脚表示为超图结点,管脚间的外部连线、管脚内的电路逻辑功能表示为有向超边.进而,本文阐述了XDL网表级电路描述文件到有向超图的转换流程,给出了XDL网表级电路描述文件编译所需的EBNF表达式、XDL网表级电路到有向超图的转换算法.最后,本文基于RapidSmith开源软件和Java语言实现了转换系统,并选用基于Xilinx公司的Virtex-4型号FPGA的测试用例,实现了XDL网表级电路描述文件转换至有向超图,验证了XDL网表级电路描述文件到有向超图转换系统的有效性和正确性.

有向超图的可平面性算法

随着有向超图理论在实际问题中的深入应用,其平面性研究也更加具有意义.本文回顾有向超图的一般理论,给出了有向超图结构图的概念,并在此基础上给出有向超图的可平面性算法.由于有向超图的结构图是简单有向图,故有向超图的可平面性算法建立在对一般图的可平面性判断上,该算法是多项式时间算法,是有效算法.

有向超图的超网络能量及其性质

图能量表述为方阵形式的矩阵特征值绝对值之和.网络能量已在无向图、有向图及混合图中得到较为成功的应用,与传统意义上的图能量之间存在多个相同或相似的上下限.由于图与超图之间的关联,无向图与有向图的网络能量及无向超图的超网络能量之间存在密切联系.将超网络能量由无向超图推广应用到有向超图,提出了有向超图的超网络能量,分析了无向超图与有向超图的超网络能量之间的关联,同时论述了无向图与有向图的网络能量及无向超图与有向超图的超网络能量之间的联系,最后给出了有向超图的超网络能量若干重要性质.

动态有向超图中限制不交B-路算法设计

超图在现实生活中有很重要的应用价值,比如信息传递、货物运输、商品配送等问题都可以归约到超图中建立数学模型并设计优化算法。而网络环境是会随时间发生连续动态变化的,故本文主要研究动态超图中的连通性问题。同时,由于大规模网络中故障的发生是不可避免的,而且是极具破坏性的,所以,提高网络的生存性能,保证网络的容错性有很重要的研究价值。设计不交超路径是提高网络容错性的主要解决方案。由于超路中B-路有很好的结构性质和广泛的应用背景,因此,本文在时变超图网络中考虑满足时间限制的不交B-路构建问题。目前由于动态网络研究的复杂性,连续时间动态网络背景的处理方法大多是采用时间离散化转换为静态网络去求近似解,本文考虑当给定起始时刻时,在时间范围[0,Τ]内每条超弧的延迟函数为连续时间动态函数的情况下,针对不交B-路问题给出最优解的求解算法,并证明算法的正确性及运算复杂度。

顾及多重分类与粒度划分的国土空间数据模型研究与应用

国土空间数据在分类分级、过程演化等方面都存在着分类、互依赖、组合构成和前后次序等高阶关系,现有的图层、面向对象、数据立方体等数据模型难以完全刻画全部关系.本文提出了基于有向超图的顾及多重分类与颗粒体系的国土空间数据模型,运用关联矩阵进行逻辑描述,基于超级图形数据库进行物理模型实现和国土空间演化过程的时空分析,解决了全域、全要素、全空间国土空间数据多重分类与颗粒体系表达的难题.相关成果在南京市国土空间基础信息平台得到了应用验证,增强了平台对复杂关系的运营效能,实现了多维关系数据的聚合,为平台实现数据资源自动分类和信息智能定向推送奠定了基础.

事件超图模型及类型识别

为避免向量空间模型的独立性假设影响事件类型识别,该文提出了一种基于超图的事件类型识别方法。该方法首先用事件超图描写事件元素间的多元有序关系;然后用事件超图模型(由事件超图添加类型组件和层面组件后构成)描述某个(某类)事件在不同观测层面的属性及其结构;最后根据事件的属性及其结构计算其相似度,并借此完成事件类型识别。实验结果显示,此方法识别效率的平均F值达到83.0%,与基于向量空间模型的支持向量机方法和最大熵方法相比,此方法也具有一定优势。

基于超图的BCNF的判定算法

利用超图来表示关系模式．定义了直接决定因素、推导．讨论了直接决定因素的性质．在此基础上给出了利用超图判定给定的关系模式是否属于ＢＣＮＦ的新算法．

基于超图的社交网络中的预算影响力最大化

影响力最大化问题是在线社交网络中的热点问题,然而社交网络的结构错综复杂,传统的影响力最大化问题并没有考虑社交网络中的群体影响.针对以上不足,利用有向超图刻画社交用户之间的群体影响,提出一种基于有向超图的预算影响力最大化问题.该问题是在有向超图的社交网络中,在给定预算下,寻找高影响力用户作为种子节点集,使得其最终的传播范围最大化.分析了该问题是NP-hard的且目标函数是非次模函数,提出了改进的贪婪算法和交换启发式算法进行求解,并分析了改进贪婪算法的近似比.通过将所提的算法应用到三个在线社交网络数据集中进行实验,验证了算法的正确性和良好性能.结果表明,改进贪婪算法基础上的交换启发式算法具有明显的性能优势.

云环境下面向负载均衡的数据密集型工作流的数据约简策略

如何对数据密集型工作流应用进行高效合理地调度成为云计算领域亟待解决的关键问题之一。针对此问题,构造数据密集型工作流的有向超图模型,提出了数据支持能力概念,通过基于数据支持能力的合并操作对模型进行约简。最后优化超图多层剖分算法,提出数据约简的数据密集型工作流调度策略HEFT-P。研究结果表明,HEFT-P相比典型的工作流调度策略HEFT、CPOP、MCP,能够很好地对数据密集型工作流进行约简优化,获得较少的调度时间。

支持个性化优化的业务过程建模

为支持根据企业具体的资源环境和目标进行相应的业务过程优化,给出一种基于有向超图的业务过程建模方法。该方法给出了考虑可能支持资源、资源所属企业及可用状态的业务过程的有向超图模型。基于该模型,应用超图理论和模型所附加的过程语义讨论了该模型如何支持个性化的、动态的业务过程优化,并给出具体的优化过程。通过具体实例说明了该方法的特点。该建模方法既是超图理论应用范围的一个扩展,又丰富了超图理论。