共查询到20条相似文献,搜索用时 78 毫秒
1.
关键路径的稀疏矩阵求解算法 总被引:4,自引:0,他引:4
求解AOE网的关键路径算法一般基于拓扑排序,虽然具有较好的时间复杂度(O(n+e)),但由于必须进行拓扑排序,同时还要进行拓扑逆序扫描,使得算法本身比较复杂。针对这个问题提出了一个算法,算法采用了稀疏矩阵作为数据的存储结构,为防止关键路径丢失,采用队列方式进行操作。同经典算法相比,该算法简单,时间复杂度相近(O(n+e/n))。 相似文献
2.
TTCAN协议静态调度算法研究与仿真 总被引:2,自引:0,他引:2
TTCAN已经被广泛应用于汽车控制系统的实时通讯协议.TTCAN协议的研究目标主要是通过优化周期性通讯任务的调度方法,以便满足系统的实时信号传输的要求.针对TTCAN协议周期性和非周期性通讯任务的特点,采用最优调度法研究和改进了基于状态模型的TTCAN调度算法,并且利用Simulink中的Stateflow工具建立了TTCAN静态调度算法的仿真模型,仿真结果较好地验证了改进算法在通信实时性和带宽利用率方面的优势.仿真模型的建立为TTCAN协议的应用研究提供了重要的参考价值. 相似文献
3.
为了提高学术论文检索的精准性,进而为学术研究提供便利,提出了针对学术论文检索问题的排名策略。首先,介绍了基于网页排名算法面向论文索引排名的启发式方法,其中利用Hash索引技术有效地减少了稀疏矩阵计算对内存的消耗;其次,定义了论文间引用关系图的密集度均衡值,并通过大量实验阐明了不同排名算法的迭代次数与图密集度均衡值之间的关系;最后,将所提出的基于论文索引排名的启发式算法应用于科学引文索引(SCI)数据库中,并与原被引频次降序的排序结果进行比较与分析。实验结果表明:在三种基于网页排名技术的算法中,基于链接结构分析的随机过程算法比较适合于按关键词搜索得到的相关领域学术论文的排名。 相似文献
4.
5.
李长兴 《计算机光盘软件与应用》2013,(5)
在《数据结构》课程中,三元组稀疏矩阵的转置算法通常会作为难点来讲解。通过介绍一般数组的矩阵转置的算法以及稀疏矩阵、稀疏矩阵的三元组表示,引出稀疏矩阵的一般算法。本文介绍的稀疏矩阵的算法是一种用C语言编写的转置算法,并通过对两种算法的涉及到的时间以及空间的复杂度进行分析,突出C语言编写的转置算法的优势。 相似文献
6.
7.
8.
稀疏矩阵的乘法运算可用于解决许多实际的应用问题。提出一种新颖的稀疏矩阵相乘算法,算法实现中将计算单元由单个元素扩展至行向量,避免了矩阵的转置,减少了扫描次数。利用三元组和少量的额外辅助空间实现稀疏矩阵的相乘。实验结果表明了该算法的有效性。 相似文献
10.
11.
超长指令字(Very Long Instruction Word,VLIW)处理器一般采用总线互连的多簇结构,每个簇中的功能单元共享一个本地寄存器堆,簇间采用总线传输数据,以避免功能单元增多时,全连通结构的延时、面积和功耗的快速增长;但簇间数据共享时的拷贝和延时,使得处理器在性能上有所下降.文中提出了一种寄存器堆互连的多簇VLIW结构,采用寄存器堆来连接各个簇,从而可以避免簇间数据传输的延时和额外的数据拷贝操作.同时也提出了针对这种结构的指令调度算法,以提高指令调度的性能.实验结果表明,与全连通的VLIW结构相比,寄存器堆互连结构在性能上仅有13%左右的性能下降,代码长度则基本不变;这都优于总线互连的多簇结构. 相似文献
12.
卷积神经网络(convolutional neural network, CNN)在图像处理、语音识别、自然语言处理等领域实现了很好的性能.大规模的神经网络模型通常遭遇计算、存储等资源限制,稀疏神经网络的出现有效地缓解了对计算和存储的需求.尽管现有的领域专用加速器能够有效处理稀疏网络,它们通过算法和结构的紧耦合实现高能效,却丧失了结构的灵活性.粗粒度数据流架构通过灵活的指令调度可以实现不同的神经网络应用.基于该架构,密集卷积规则的计算特性使不同通道共享相同的一套指令执行,然而稀疏网络中存在权值稀疏,使得这些指令中存在0值相关的无效指令,而现有的指令执行方式无法自动跳过它们从而产生无效计算.同时在执行不规则的稀疏网络时,现有的指令映射方法造成了计算阵列的负载不均衡.这些问题阻碍了稀疏网络性能的提升.基于不同通道共享一套指令的前提下,根据稀疏网络的数据和指令特征增加指令控制单元实现权值数据中0值相关指令的检测和跳过,同时使用负载均衡的指令映射算法解决稀疏网络中指令执行不均衡问题.实验表明:与密集网络相比稀疏网络实现了平均1.55倍的性能提升和63.77%的能耗减少.同时比GPU(cuSparse)和Cambricon-X实现的稀疏网络分别快2.39倍(Alexnet)、2.28倍(VGG16)和1.14倍(Alexnet)、1.23倍(VGG16). 相似文献
13.
Scheduling and Priority Mapping for Static Real-Time Middleware 总被引:3,自引:0,他引:3
Dipippo Lisa Cingiser Wolfe Victor Fay Esibov Levon Bethmangalkar Gregory Cooper Ramachandra Bethmangalkar Ramachandra Johnston Russell Thuraisingham Bhavani Mauer John 《Real-Time Systems》2001,20(2):155-182
This paperpresents a middleware real-time scheduling technique for static,distributed, real-time applications. The technique uses globaldeadline monotonic priority assignment to clients and the DistributedPriority Ceiling protocol to provide concurrency control andpriorities for server execution. The paper presents a new algorithmfor mapping the potentially large number of unique global prioritiesrequired by this scheduling technique to the restricted set ofpriorities provided by commercial real-time operating systems.This algorithm is called Lowest Overlap First Priority Mapping;we prove that it is optimal among direct priority mapping algorithms.This paper also presents the implementation of these real-timemiddleware scheduling techniques in a Scheduling Service thatmeets the interface proposed for such a service in the Real-TimeCORBA 1.0 standard. Our prototype Scheduling Service is integratedwith the commercial PERTS tool that provides schedulability analysisand automated generation of global and local priorities for clientsand servers. 相似文献
14.
求解混合流水车间调度问题的分布估计算法 总被引:9,自引:0,他引:9
针对混合流水车间调度问题(Hybrid flow-shop scheduling problem, HFSP)的特点, 设计了基于排列的编码和解码方法, 建立了描述问题解空间的概率模型, 进而提出了一种有效的分布估计算法(Estimation of distribution algorithm, EDA). 该算法基于概率模型通过采样产生新个体, 并基于优势种群更新概率模型的参数. 同时, 通过实验设计方法对算法参数设置进行了分析并确定了有效的参数组合. 最后, 通过基于实例的数值仿真以及与已有算法的比较验证了所提算法的有效性和鲁棒性. 相似文献
15.
一个基于DAG图的指令调度优化算法 总被引:1,自引:0,他引:1
指令调度是优化编译技术中一项关键技术,对于VLIW体系结构的CPU,指令调度显得尤为重要。指令调度是在保证语义正确的前提下,改变指令的执行顺序,减少流水线中的空闲周期,从而提高CPU性能的一种优化方法。文章着重分析了优化编译中的指令调度问题,提出了一个指令调度算法和DAG图的一种化简方法,证明了算法的正确性,分析了算法的效率,比较了生成的新指令序列和最优的指令序列总的执行时间的差别。同时,针对目前流行的编译器GCC的指令调度算法中存在的问题,提出了一个较好的解决途径。 相似文献
16.
17.
王磊 《自动化技术与应用》2013,32(6)
为消除数据竞争,可通过旁路控制机构或其它技术手段来解决,但仍然不能从根本上消除数据竞争.针对数据相关的不可避免性,采用流水线的动态调度算法来解决数据竞争问题,常用的动态调度算法是Tomasulo算法和记分牌调度算法,分析了Tomasulo算法和记分牌调度算法的基本思想和算法实现,对他们的异同进行了分析说明,实验证明,动态调度算法具有很好的消除数据竞争效果. 相似文献
18.
资源受限的项目调度问题的求解算法 总被引:1,自引:0,他引:1
本文建立了不确定资源环境下的资源受限的项目调度模型,用不确定规划的方法将不确定问题转化为等价的确定性问题,并给出了一个解决该问题的二阶段算法及实例。 相似文献
19.
20.
高效并行扫描问题是调度问题的子集,调度问题是NP完全问题.针对输运问题的特点,如何按特定的计算次序调度本地网格单元,以保证最佳的计算与通信性能是一个难度很大的问题.文中设计了一种基于局部深度优先的优先级(PDFDS)算法,该算法具有局部性、通信量小、优先级队列好等特点.将PDFDS算法应用到求解二维粒子输运方程的程序中,与现有的调度算法相比,新算法具有更好的并行计算效果,对于大规模计算问题,可以扩展到1024个处理器,相对于64个处理器的并行效率达到了96%. 相似文献