题目分析在数字集成电路设计中同步设计是保证芯片正确性的关键。一个电路要满足同步设计需要满足两个条件无异步节点构成的环如果电路中存在完全由异步节点如AND、OR等逻辑门组成的环实际电路中可能产生振荡导致行为不可预测。最大延迟不超过时钟周期任意两个同步节点触发器之间的路径延迟必须小于等于给定的时钟周期否则信号无法在下一个时钟边沿前稳定。题目给定电路的节点信息类型和延迟、连接关系以及时钟周期要求判断电路是否满足同步设计并输出相应的结果。节点类型类型代码说明输入i外部输入延迟为000输出o外部输出延迟为000同步节点s触发器延迟为000异步节点a逻辑门有正延迟解题思路第一步检测异步节点环要检测一个有向图中是否存在由异步节点构成的环可以使用拓扑排序。只考虑异步节点计算每个异步节点的入度只统计来自异步节点的边重复删除入度为000的异步节点及其出边如果最后还有异步节点未被删除说明存在异步节点环第二步计算最大路径延迟如果没有异步环则计算所有从“输入或同步节点”出发到“同步或输出节点”结束的路径的最大延迟和。由于图已无环可以使用DFS\texttt{DFS}DFS回溯搜索从每个输入节点或同步节点开始沿边遍历累加节点延迟遇到同步或输出节点时更新最大延迟第三步比较与输出若存在异步环 →Circuit contains cycle.否则若最大延迟时钟周期 →Clock period exceeded.否则 →Synchronous design. Maximum delay: ss.代码实现// Synchronous Design// UVa ID: 192// Verdict: Accepted// Submission Date: 2016-03-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 节点类型常量constintINPUT0,OUTPUT1,SYN2,ASYN3;conststring typeTextiosa;// 节点结构体structvertex{intindex;// 节点编号intdelay;// 节点延迟异步节点有效inttype;// 节点类型};vectorvertexverties;// 所有节点vectorintpath;// DFS 路径缓存vectorvectorintedges;// 邻接表intmaximumDelay;// 最大路径延迟// 拓扑排序检测是否存在异步节点构成的环boolfindCycle(){vectorintconnections;connections.resize(verties.size());fill(connections.begin(),connections.end(),0);// 计算每个异步节点的入度仅考虑异步节点之间的边for(inti0;iedges.size();i)for(intj0;jedges[i].size();j)if(verties[edges[i][j]].typeASYN)connections[edges[i][j]];vectorboolremoved;removed.resize(verties.size());fill(removed.begin(),removed.end(),false);boolnodeRemovedtrue;intnumberRemovedNodes0;// 反复删除入度为 0 的异步节点while(nodeRemoved){nodeRemovedfalse;for(inti0;iremoved.size();i)if(removed[i]falseconnections[i]0){nodeRemovedtrue;numberRemovedNodes;removed[i]true;// 删除该节点的所有出边更新后继节点的入度for(intj0;jedges[i].size();j)if(verties[edges[i][j]].typeASYN)connections[edges[i][j]]--;}}// 若还有异步节点未删除说明存在环returnnumberRemovedNodes!verties.size();}// DFS 回溯搜索所有路径计算最大延迟voidforward(intv,intindex){path[index]v;// 当前路径终点是同步节点或输出节点时计算路径总延迟if(index1verties[path[index]].type!ASYN){inttempMax0;for(inti0;iindex;i)tempMaxverties[path[i]].delay;maximumDelaymax(tempMax,maximumDelay);}else{// 否则继续 DFSfor(inti0;iedges[v].size();i)forward(edges[v][i],index1);}}// 从所有输入节点和同步节点开始搜索最长路径voidfindMaximumDelay(){path.resize(verties.size());maximumDelay0;for(inti0;iverties.size();i)if(verties[i].typeINPUT||verties[i].typeSYN)forward(i,0);}intmain(){intclock,circuits,delay,nodes,start,end,typeIndex;string type;cincircuits;// 读取电路数量while(circuits--){cinclocknodes;// 时钟周期和节点数verties.clear();edges.clear();edges.resize(nodes);// 读取每个节点信息for(inti0;inodes;i){cintypedelay;typeIndex(int)typeText.find(type);// 输入、输出、同步节点的延迟均为 0if(typeIndexINPUT||typeIndexOUTPUT||typeIndexSYN)delay0;verties.push_back((vertex){i,delay,typeIndex});}// 读取连接关系intm;cinm;for(inti1;im;i){cinstartend;edges[start].push_back(end);}// 判断异步环if(findCycle())coutCircuit contains cycle.endl;else{// 计算最大路径延迟findMaximumDelay();if(maximumDelayclock)coutClock period exceeded.endl;elsecoutSynchronous design. Maximum delay: maximumDelay.endl;}}return0;}总结本题核心是图的环检测与路径搜索环检测使用拓扑排序只关注异步节点判断是否存在异步环。最大延迟计算在无环图中通过DFS\texttt{DFS}DFS枚举所有从输入/同步节点出发的路径累加延迟并更新最大值。算法时间复杂度为O(N2)O(N^2)O(N2)最坏情况对于题目给定的数据规模足够高效。