上位机知识篇---关键路径

“关键路径”这个概念之所以能在数据结构图论、FPGA/数字电路设计和工程管理这三个截然不同的领域中都占据核心地位是因为它在本质上解决的是同一个底层问题在一个由依赖关系构成的复杂系统中如何找到决定整体耗时的那条瓶颈链路。下面我们来逐一剖析它在三个领域中的具体内涵。 数据结构/图论中的关键路径在这里关键路径是有向无环图DAG上的一个经典算法问题常用于项目调度建模。是什么在一个表示任务依赖关系的 AOE 网Activity On Edge network边表示活动的网中顶点代表一个事件任务开始或结束的瞬间状态。有向边代表一个活动有持续时间的任务。关键路径是从起点到终点的最长路径其长度决定了整个工程的最早完成时间。为什么因为只有关键路径上的任务被缩短整个工程的工期才会提前。非关键路径上的任务都有“缓冲时间”即使稍微延迟也不影响最终交付。怎样做算法步骤正向遍历求最早时间从源点出发按拓扑序计算每个顶点的最早发生时间 ve。对每个顶点 vv其ve[v] max{ ve[u] w(u,v) }取所有前驱路径中的最大值。反向遍历求最迟时间从汇点出发按逆拓扑序计算每个顶点的最迟发生时间 vl汇点的vl[汇点] ve[汇点]。对每个顶点 uu其vl[u] min{ vl[v] - w(u,v) }取所有后继路径中的最小值。确定关键活动与路径计算每个活动 aiai​ 的总时差松弛时间总时差 vl[后继] - ve[前驱] - 活动持续时间。所有总时差为 0的活动构成一条或多条关键路径。⚡ FPGA/数字电路中的关键路径在这里关键路径定义了一个数字电路能够跑多快的物理极限。是什么在数字电路中信号从源寄存器输出经过一系列组合逻辑与门、或门、加法器等必须在下一个时钟沿到来前稳定地到达目标寄存器输入。关键路径就是所有这样的寄存器到寄存器路径中组合逻辑延迟最大的那一条。为什么决定最高时钟频率系统的时钟周期不能短于关键路径的延迟否则数据来不及稳定就会被下一级寄存器采到错误值即发生建立时间违例。公式为Tclk≥TcoTlogicTsetup​。关键路径就是那个让 Tlogic最大的路径。它是时序收敛的核心FPGA 开发工具的“布局布线”过程90%以上的努力都在与关键路径博弈通过优化布局、插入寄存器、逻辑复刻等手段来缩短它以达到目标频率。怎样做设计优化策略插入流水线寄存器在大段组合逻辑中插入一级寄存器将一个长路径拆成两个短路径这是最直接有效的方法。逻辑重定时利用EDA工具的算法自动在组合逻辑前后移动寄存器平衡各级延迟。布局优化在物理层面将相关逻辑块放的更近减少走线延迟。操作符优化将大而慢的“超前进位加法器”拆成“流水线加法器”或改用面积更小、更快的结构。 工程管理中的关键路径这是关键路径概念最普及的领域源于项目管理知识体系。是什么项目是由一系列活动组成的网络图关键路径是项目中总时差最小的活动序列它直接决定了项目的最短总工期。通常这几乎是总时差为0的活动所组成的路径。为什么进度控制焦点项目经理的最核心职责就是盯紧关键路径上的任务。任何一个关键活动的延误都会直接且无缓冲地延误整个项目。资源调配依据当资源人、钱、设备冲突时应优先保证关键路径上的活动。缩短非关键活动除了可能制造新的关键路径外无法提前项目总工期。风险预警关键路径上的活动是最高风险项需要最多的关注和应急预案。怎样做项目管理实践活动分解WBS列出所有任务及其依赖。绘制网络图用节点AON或箭线AOA表示依赖关系。正向与反向计算使用与图论中完全一致的算法计算每个活动的最早开始/结束、最迟开始/结束时间并计算总时差。动态管理项目进行中关键路径可能会因提前或延误而漂移需要定期重新计算将管理重心动态转移到新的关键路径上。 三者之间的奇妙连接图论提供了数学模型和算法基础DAG 动态规划。项目管理是这个算法的提出动机和直接应用场景。数字电路设计则是在物理世界最精妙、最自动化的实现之一。EDA软件在几亿条路径中用类似的项目管理算法PERT/CPM来找出“最长的那条逻辑链”并自动“赶工”。 Mermaid 总结框图