0
\$\begingroup\$

In Retiming synchronous circuitry , why put a negative sign to d(u) in step 1 ? Why there is no subtraction operation for W(u, v) in step 3?

Note:

  1. The quantity W(u, v) is the minimum number of registers on any path from vertex u to vertex v
  2. The quantity D(u, v) is the maximum total propagation delay on any critical path from u to v

algorithm_WD

\$\endgroup\$
1
  • \$\begingroup\$ Please edit the question to make it self explanatory. The link may go dead in the future and current version of the question will then be incomplete. Please add enough details from the source directly into the question. Relevant images, description of symbols etc. \$\endgroup\$
    – AJN
    Jul 27, 2021 at 13:00

1 Answer 1

Reset to default
1
\$\begingroup\$

As a disclaimer, this is the first time I'm reading about retiming, but I do have some academic learning of optimization.

why put a negative sign to d(u) in step 1 ?

"Applying negative sign" (i.e. multiply by -1) is commonly used in optimization to swap problems between "max" and "min". As a crude example, visualize a cost function with a known minima, such as a quadratic function. If you multiply it by -1, that minima has now become a maxima, but the solution ("where is that optimal point located?") remains the same.

As per the definitions of W and D: enter image description here

and the description of the algorithm says it will "compute both W and D". I can only deduce the \$-d\$ is with the intention of transforming the combined "min-max" problem into a single "min-min" problem.

Why there is no subtraction operation for W(u, v) in step 3?

Because \$w\$ are edge weights (\$W(u,v)=w(e)\$) and \$d\$ are vertex weights (\$D(u,v)=d(v)+d(u)\$). From the first step of setting up the algorithm, \$x\$ corresponds to \$w(e)\$ and \$y\$ corresponds to \$-d(u)\$. This means \$W(u,v)=x\$, but you still need to calculate \$D(u,v)\ = d(v)-y\$.

\$\endgroup\$
6
  • \$\begingroup\$ I do not understand why you said transforming the combined "min-max" problem into a single "min-min" problem. \$\endgroup\$
    – kevin998x
    Jul 29, 2021 at 8:44
  • \$\begingroup\$ Why W(u, v) equals x instead of y ? \$\endgroup\$
    – kevin998x
    Jul 29, 2021 at 12:15
  • 1
    \$\begingroup\$ @kevin998x Instead of solving two optimization problems (one for min \$w(p)\$ and another for max \$d(p)\$), which I worded as "combined min-max problem", the text is proposing to optimize both values simultaneously (min \$w(p)\$ and min \$-d(p)\$), that I worded as "single min-min problem". \$\endgroup\$
    – Vicente Cunha
    Jul 29, 2021 at 20:54
  • 1
    \$\begingroup\$ @kevin998x \$W(u,v)\$ will equal to \$x\$ due to the setup in the first step: "weight each edge in E with the ordered pair \$(w(e),-d(u))\$". The second step says that weights should be added using componentwise addition, if I understand proper this means "w sums with w, d sums with d", so there are no mix-sums "w+d" in the solution. Finally the third step says "for each shortest path weight \$(x,y)\$. If you setup the weights as described in the first step, and perform componentwise additions in the second step, then \$x\$ can only be (a sum of) \$w(e)\$ and \$y\$ is (a sum of) \$-d(u)\$. \$\endgroup\$
    – Vicente Cunha
    Jul 29, 2021 at 21:03
  • \$\begingroup\$ y = -d(u) , so D(u, v) = d(v) - y = d(v) + d(u) \$\endgroup\$
    – kevin998x
    Jul 30, 2021 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.