A scalable method to measure similarity between two EDA-generated timing graphs

摘要

This is a case study of the use of graph similarity to correlate the timing models obtained from two electronic design automation (EDA) static timing analysis tools (Altera's Quartus II software versus Synopsys PrimeTime). Timing models are data modelled from the post-layout netlist and parasitics extraction. The field programmable gate array's (FPGA) timing model is used by customers to optimize their designs. As mask designs are constantly revisioned, new timing models are generated and thus the Quartus II software must constantly be updated with the new models. A verification needs to be carried out at every new iteration of timing models to ensure the regression testing of timing models is stable and reliable. This case study discusses one such verification methodology. A timing graph consists of nodes and edges. Edges have weights attached to them that can denote some characteristic, such as timing arc delays in this case. Out of the many graph similarity algorithms in the field, the most cited are edit distance similarity, neighbourhood matching, spectral matching and belief propagation. Neighbourhood matching, which was used in this study, is a point-to-point matching of a node's similarity score based on its neighbourhood's similarity score. The timing graph from the Quartus II software was generated with an in-house Tcl scripting language applications programming interface. The timing graph from PrimeTime was generated from its timing reports. An algorithm was postulated to calculate graph similarity based on edge weights of the graphs. The algorithm compared both graphs and produced a matrix of graph similarity scores for all paired nodes. The algorithm was tested on five data paths taken from the two EDA tools under evaluation. Our results showed good correlation between intuitive similarity measure and our algorithmic calculation.