CIRCUIT ELEMENTS PROPAGATION DELAY DETECTION BY MAXIMUM FLOW

CIRCUIT ELEMENTS PROPAGATION DELAY DETECTION BY MAXIMUM FLOW

Narek Asatryan

Masters Student, National Polytechnic University of Armenia,

Armenia, Yerevan

ABSTRACT

Maximum flow detection is one of the many solutions for application problems. For any connected and directed graph, we have certain material flow, and by considering them as a graph system we can analyze source point and the consumption point. We can review such an example with a gas Pipeline transport, through which gas flows, and by analyzing similar system we can found maximum amount of gas that can pass through the source point until the point of consumption.

In this article, integrated circuit is considered as a graph system, propagation delay chosen as material, and thus we need to find ways to find the maximum propagation delay flow that can occur in our circuit.

Keywords: maximum flow, propagation delay, Edmonds–Karp algorithm, Depth-first search algorithm. 

Introduction

The maximum flow represents the number of dimensions or quantity of material that can flow through our graph. For example, maximum gas that can flow in gas pipeline from source point until the point of consumption. Finding the maximum flow is the solution for many applied problems. Let’s observe scheme in which flowing material. Scheme is considered as connected and directed graph, and thus a maximal flow in it the search result shows how much material is possible to pass from the circuit source to the circuit consumption point.

Figure 1. Graph representation

In integrated circuit, there are various application problems that can be solved by considering integrated circuit as a graph. And by considering them as graph, circuits can be implemented in the search for maximum flows. For this case as a maximum flow material, we can review circuit propagation delay parameter.

Propagation delay of a circuit is defined as the time that takes for the effect of change in input to be visible at the output. So, propagation delay is the time required for the input to be propagated to the output. In other words, it is the difference between the times when the transitioning input reaches 50% of its final value to the time when the output reaches 50% of the final value showing the effect of input change.

Propagation delay dependent upon two factors:

• Transition time of the input effects on transition of the output: So how more is the transition time at the input, then more will be the propagation delay of the cell
• The output load have effect on the circuit elements: how bigger is the capacitive load sitting at the output of the cell, then more will be the effort put (time taken) to charge it. Hence, greater is the propagation delay.

Figure 2. propagation delay

Design process

There are many algorithms for finding the maximum flow in graph. But the most used is Edman Karp's algorithm, which is an implementation of Ford-Fulkerson's method and Dinica's algorithm. They both implemented by considering the given scheme as a connected and directed graph, but their implementation complexities differ. In the theoretical relations, we will consider each of them in more detail and choose the one most suitable for the solution of the problem.

Figure 3. maximum flow in the above graph is 23

So as vertices of the graph will be the elements present in integrated circuit at the connecting chains, and the sides characterizing the elements present in the circuit propagation delay values. With those graphs, by using maximum flow system we will get circuit element that contains maximum propagation delay.

Let’s consider a time-dependent graphs.it defined as G = (V, E), where V contains finite set of vertices and E contains set of edges which is a subset of the unordered pairs of the set of vertices. So, since the graph is weighted, each of its edges is assigned a certain value, which represents the corresponding vertices of the edge to the value of the propagation delay between.

Figure 4. Circuit example

Figure 5. Circuit representation as a graph

Software can be implemented by using two possible algorithms

• Edmonds–Karp algorithm: At each step of the algorithm, a shortest path is selected from unobserved vertices in the network, and the search for this shortest path is performed using a breadth-first search algorithm
• Depth-first search algorithm: In this case data structure takes the form of a tree or graph. The algorithm starts his work from the root vertex (given either to chance in principle, a vertex is selected from the graph from which the algorithm starts work) and is executed for each vertex until it it's possible:

For the development of the software, let's consider the following process block diagram of the algorithm.

Figure 6. Block diagram

Conclusion

The algorithm of the software consists of four steps sequence, each of which the precise operation leads to expected result.

1. Choose one of the “Maximum flow” algorithms: For example, Edmonds–Karp algorithm or Depth-first search algorithm.
2. Getting a description from scheme: Verilog description or Netlist of circuit.
3. Data processing and graph construction: represent the graph as a matrix
4. Algorithm implementation․

References:

1. Thomas H. Cormen Introduction to Algorithms, Third Edition, The MIT press, London, England,2009:708-769
2. Razavi B. Design of Analog CMOS Integrated Circuits. - Mc Graw Hill India, 2nd edition, 2017. – 782p.