Hierarchical topological sorting of apparent loops via partitioning

摘要

Topological sorting (rank ordering) is a highly useful technique for ordering a set of objects according to a precedence relation, producing an ordered list suitable for processing. Applications for topological sorting include compiled logic simulation and timing analysis. While topological sorting is easily accomplished for flat combinational logic networks, hierarchical logic can be difficult to order because feedback may appear in the hierarchical representation even though it is not present in an equivalent flattened representation. This paper presents a new general solution to this problem and describes an efficient algorithm for topological sorting even in the presence of such apparent loops. Its application to hierarchical functional simulation of combinational and synchronous sequential logic is also discussed.