基于顶点组重分配的动态增量图划分算法

图划分是分布式图计算中的一项基础工作,其作用是将大规模图进行划分并分配到集群中的不同机器上.图划分的质量对分布式图计算的性能有很大的影响,其目标是降低负载平衡和最小化边割.如今,现实中的图数据通常呈动态增长态势,这就需要一种能够处理动态增量图的划分方法,在图数据动态增长的过程中确保划分的质量不受影响.目前虽然有一些动态图划分算法被提出,但它们不能同时专注于实时处理动态变化和获得高质量的划分结果.提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题.在ED-IDGP算法中,设计实时处理4种不同单元更新类型的动态处理器,并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量.在ED-IDGP的局部优化器中,利用基于改进标签传播算法的顶点组搜索策略搜索顶点组,并利用提出的顶点组移动增益公式衡量最有益的顶点组,将该顶点组移动到目标分区中做优化.在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.

多核处理器中混合关键级任务可调度及半分区划分算法

当前,多数多处理机中混合关键级任务可调度性分析以及半分区调度算法均针对单核利用率展开研究。但由于多核系统任务调度复杂性较高,现有研究结果存在各处理器负载不均衡以及任务可调度性不理想等问题。针对该问题,文中将动态需求边界函数(Dynamic Demand Boundary Function,DDBF)的应用范围扩展至多核处理器系统。根据半分区划分调度算法对DDBF改进,并加入了结转作业和前接作业分析提出了SDDBF(Super Dynamic Demand Boundary Function),可更精确地计算与利用资源。文中基于SDDBF提出了SDA(Stepper Dispatch Algorithm)可调度性分析法与半分区划分算法MCWF(Mixed-Criticality Worist First)。仿真结果表明,相较于AMC(Adaptive Mixed Criticality)、AMC-max以及XU算法,SDA可调度性分析判定提升了5%~10%,相较于WF_MY(Worst First_My)、WF_NEW(Worst First_New)算法,MCWF可使系统在任意关键等级下的CPU(Central Processing Unit)负载具有更良好的均衡性能。

混合关键系统半划分调度算法研究

混合关键系统是现代嵌入式系统发展的主要趋势之一,其中高关键任务代表紧急度高或者重要程度高的实际任务,往往需要优先保证.为了保证高关键级别任务的执行,当前的混合关键任务调度算法中常常存在对低关键级别任务采用丢弃或者调度不及时的现象,造成在关键级别转换时,任务丢失时限率较大且系统利用率较低.为此,本文在具有双重关键级别的混合关键系统中,对EDF-os半划分调度算法进行改进.首先,在划分阶段,将高关键级别的任务作为固定任务,低关键级别的任务按照利用率使用Worst-Fit策略进行划分.其次,在执行阶段,采用job边界迁移形式,并详细讨论了在不同系统关键级别之下,不同关键级别任务优先级确定的策略,根据优先级对任务进行调度执行.最后,模拟具有双关键级别的多处理器混合关键系统,随机产生任务集进行仿真实验,结果表明,该方法使得低关键级别任务的可执行比例平均提升了14.8%,任务丢失时限率降低了19.7%.

基于MrsP协议的任务划分优化算法

多处理器实时系统中,调度和资源共享是核心问题,与之相对应的调度算法和共享资源访问协议将直接影响系统的性能,这就要求调度算法和资源访问协议在保证实时性的基础上尽量发挥硬件平台的计算能力。然而,现有的调度算法多假设任务相互独立,没有考虑任务之间的资源共享,共享资源访问协议也多侧重于规则和最坏响应时间分析。对此,将P-RM算法和MrsP协议相结合,得出了多处理器实时系统的整体可调度性条件。文中根据MrsP协议的特性,提出了一种减小阻塞时间的任务划分算法,通过改进任务利用率的计算方式解决了关键区重复计算的问题,与之前的任务划分算法相比,也解决了关键区重复计算以及任务分类后拆分再分配的问题。实验表明,该算法所需要的处理器数目减少了15%~20%。

一种多核处理器中混合关键级任务半分区调度算法

目前用于混合关键级系统的任务调度算法存在资源分配不合理、中低关键级任务的运行受限等情况,造成系统整体服务质量被降低.本文提出了有效改进系统服务质量的半分区调度算法,该调度算法将用于多核处理器的空闲资源回收计算,能够在触发了高关键级模式的情况下,为被抛弃的低关键级任务分配空闲时间片.此外,该算法还可以利用系统中的空闲时间片推迟系统关键等级的提升,并提出系统关键等级平稳回落策略,两者可以确保系统关键等级不会过于频繁变化.最后,通过算法仿真和实验证明了本文所提方法在混合关键级任务调度问题上的有效性和优越性.

基于改进Newman快速划分算法的城市动态交通子区划分方法

城市交通网络紧密联系,交叉口、干线和交通子区存在复杂关联性。从复杂系统角度提出一种基于Newman快速划分算法(Fast Newman,FN)的控制子区划分方法。首先,考虑城市道路网络拓扑结构复杂性,根据相邻交叉口的交叉口间距、路段交通流量、车流离散特性、交通流速度、车流密度等分析交叉口关联性,建立综合关联度计算模型;其次,将交叉口关联性引入到FN算法中,基于改进的Newman快速划分算法对路网控制子区进行划分;最后,通过实际路网,进行模型验证。结果表明:该子区动态划分方法有效考虑路网拓扑结构复杂性,更符合实际交通流特性,对城市区域路网子区划分更加合理。

算法的相关性变换与划分带个数的关系

使用相关性变换法，划分并映射循环算法到具有固定尺寸的Ｓｙｓｔｏｌｉｃ阵列．下标集合被划分成若干条带，划分带的条数与变换后的Ｓｙｓｔｏｌｉｃ阵列算法的执行时间成正比．指出了Ｍｏｌｄｏｖａｎ给出的计算划分带条数的公式有很大局限性，给出了由空间变换计算划分带条数的方法．

无线传感器网络中的组划分算法

以增加网络生命期为目的设计组划分算法,考虑了传感器网络中各个组长节点的组合理性、平均组能耗和组间负载平衡等因素,对初始的组划分进行了分析和优化处理而得到一个平均组能耗小并且组间负载平衡的组划分,有效地延长了网络生命期.

基于映射法和Delaunay方法的曲面三角网格划分算法

提出一种曲面三角网格划分算法 ,该算法在曲面参数域中生成 Delaunay类型的网格 ,然后将其映射到空间曲面 .为了抵消映射过程中变形的影响 ,采用空椭圆准则代替传统的空间准则 ,并给出椭圆的构造算法以及椭圆圆心的定位方法 .这些方法充分考虑到了映射变形和求解速度 .实验结果表明 ,该算法能生成满意的曲面网格 。

多连通曲面离散点集的3D三角划分算法研究

在对非封闭曲面、简单封闭曲面和多连通封闭曲面的特点进行分析之后,提出了一种多连通封闭曲面离散点集的3D三角划分算法.该算法无须对离散点集所对应的自由曲面进行分片,直接在3D空间根据曲面的形态变化向前逐层推进生成三角网格.算法同时还适用于非封闭曲面和简单封闭曲面两种情形.实验结果表明,该算法的划分效果优良,能够满足曲面重构的需要.

基于曲面偏置的六面体有限元网格再划分算法

根据曲面偏置理论 ,提出一种有效的六面体网格再划分方法 ,并研究了具体实现中的若干关键技术和特殊问题的处理方法 .该方法由表及里 ,逐层生成六面体单元 ,所生成的表层单元质量明显优于内部的单元 .基于提出的算法建立了六面体网格再划分原型系统 ,并给出了几个算例 .结果表明 ,所提出的算法是可靠的 ,适用于任何形状复杂的金属塑性成形过程数值模拟中的六面体网格再划分 .

基于优化合并准则的团划分算法

图论中的团划分算法 ,对于高级综合中的分配有重要意义 ,目前高级综合中广泛采用的是C .J.Tseng等提出的近似算法 .文中通过分析完全点和二分点的情况 ,提出了两个合并准则 ,指导改进了目前的团划分算法 .经模拟测试表明 。

超图划分问题的元胞自动机模型及算法研究

对超图划分问题运用元胞自动机理论进行分析建模,提出一种元胞自动机模型以及基于该模型的赋权超图划分优化算法。在该模型中,元胞对应于赋权超图中的结点,邻接元胞对应于邻接超边所包含的结点,元胞的状态对应于所在的划分子集。引入二维辅助数组存储每条超边在划分子集中的结点个数,给出快速的元胞收益值和划分割切值的计算方法,从而避免遍历超边中的结点。实验结果表明,与赋权图划分算法和迁移方法相比,该算法可以取得更优的划分,且时间复杂度和空间复杂度较低。

一种新的大规模配电网络重构的图论算法——图的谱划分算法

建立了配电网络重构的图的多划分模型 ,提出了基于图的谱划分的算法 ,用于求解大规模配电网络的馈线间重构问题。针对规模巨大的实际配电系统 ,应用图的多级划分思想 ,提出了图的压缩算法以提高计算效率。算法避免了目前各种配电网络重构算法迭代过程中大量的潮流计算负担 ,且不依赖于系统的初始拓扑。其寻优能力不逊于常见的重构算法 ,且能高效地求取全局或近全局最优解 。

基于遗传算法的VLSI电路划分方法

电路划分是降低超大规模集成电路设计复杂性的有效方法。提出了一种基于遗传算法的电路划分算法,该算法不仅适用于电路的二划分和划分问题,而且可以满足划分对子集的大小和面积等多约束的要求。

一种启发式并行逻辑模拟划分算法

随着并行计算机应用的日趋广泛，在大型数字系统设计验证中，并行逻辑模拟已成为提高模拟验证效率的重要技术途径。并行逻辑模拟算法性能受多种因素影响，其中电路划分算法是直接影响并行逻辑模拟性能的主要因素。提出了一种利用预模拟信息的启发式划分算法，可以明显改善多 Ｃ Ｐ Ｕ 的负载平衡效果，减少处理器间通讯量，有效提高并行逻辑模拟效率。

基于点网模型的变网格划分算法

通过对分层实体制造 (LOM )中废料与制件之间可剥离性的研究 ,提出一种新的变网格划分算法 ,它根据实体层面轮廓几何特征及层间轮廓差异程度 ,使用点网模型来描述实体截面废料可剥离性的离散场 ,由此确定最终的变网格划分 ,在制件薄壁、凹洞、z方向突变层等位置附近的废料部分依据实体形状划分了多级变网格 ,从而在满足废料可剥离性的前提下使用尽可能少的网格 。

电网络图主划分算法改进

分析比较网络图主划分的已有算法，提出改进算法ＧＰＰＩＡ，使主划分算法通用性提高，运算量和存贮量减少．该算法用Ｃ语言编程，计算机实验证明可行．

应用改进的区域划分算法提高虚拟加工的可视化仿真速度

将显示平面分成多个区域,对组成场景模型的三角面片按区域进行重组,仿真时仅对图形发生变化的区域进行重绘.着重探讨了三角面片区域判定、虚拟场景部件遍历及重绘区域判定三个方面的问题,并给出了详细的改进算法.此外,文中还就区域粒度对算法性能的影响作了实验分析.该算法已应用于虚拟加工原型系统VMS中,显著地提高了加工仿真的速度.

通路时延可控的时序驱动多级划分算法

提出一种可以控制关键通路时延的时序驱动多级划分算法.首先通过聚类保护降低关键通路被分割的几率,减小后续操作对最小割目标的影响;然后使用划分保护控制通路被分割的次数,将关键通路时延限定在指定时钟周期之内.该算法只对最底层网表进行一次时序分析,克服了现有基于通路的时序驱动多级划分算法无法完全控制关键通路时延,需要对所有层次的网表进行时序分析的缺点.实验结果表明,该算法可得到较小的超边割值和通路时延值.