关键路径法

关键路径法，关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。优化关键路径是一种提高设计工作速度的有效方法。一般地，从输入到输出的延时取决于信号所经过的延时最大路径，而与其他延时小的路径无关。在优化设计过程中关键路径法可以反复使用，直到不可能减少关键路径延时为止。EDA工具中综合器及设计分析器通常都提供关键路径的信息以便设计者改进设计，提高速度。关键路径法（CPM）最早出现于1956年，当时美国杜邦（Du Pont）公司的主要负责人Morgan Walker和雷明顿兰德（Remington Rand）公司的数学家James E. Kelly研究如何能够采取正确的措施，在减少工期的情况下能尽可能少的增加费用。1957年5月7日，Kelly借用了线性规划的概念来解决项目计划自动计算的问题，简单的说就是确定了每个活动的工期和活动间的逻辑关系，输入电脑后就能自动计算项目的工期，为了电脑的计算，Kelly在活动间使用了i，j这样的节点来表示活动间的前后逻辑关系。同时Kelly绘制了图形来解释电脑所作的工作，图形以箭线表示活动，以节点表示活动间的逻辑关系，这就是最早的箭线图（ADM）。