0
\$\begingroup\$

I've been trying to improve my understanding of optimization of digital circuit. With such goal in mind I've been studying from this book. I've been trying to understand mathematically the meanings of the definitions given, however there's some point I'm probably missing.

Below all the defintions that I don't understand.

A data-flow graph \$G_d(V,E)\$ is a directed graph whose vertex set \$V={vi;i=1,2,...,n_{ops}}\$ is in one-to-one correspondence with the set of tasks.

Later the following definition is given

A sequencing graph \$G_s(V,E)\$ is a hierarchy of directed graphs. A generic element in the hierarchy is called sequencing graph entity It then specifies

A sequencing graph is an extended data-flow graph that has two kinds of vertices: operations and links, the latter linking other sequencing graph entities in the hierarchy. An example is provided

Let us consider first a sequencing graph entity that has only operation vertices, e.g., a non-hierarchical model or an entity that is a leaf of the hierarchi. The vertx set VV is in one-to-one correspondence with the operations. The edge set EE models the dependencies due to data flow or serialization. The graph has two major properties. First, it is acyclic...

Basically I don't understand why it infers the graph in such example is acyclic, I've tried to review some of the background in chapter two in order to spot how the property is inferred. I can't spot why it should be acyclic. I was wondering if you could help me in understanding why we have the acyclic property or maybe pointing me out some further reference where I can solve my doubt. Mostly of the definitions I've seen so far for dataflow graph are actually the same of the one given in the book I'm mentioning.

\$\endgroup\$
0
\$\begingroup\$

Being acyclic is inferred because it has leaves, which by definition do not cycle or loop back to a previous node. Think of the data flow as being like the transport of water through a tree. It starts at the root, goes up through the branches (which may grow into each other) and finally to the leaves where it evaporates into the atmosphere. Once it gets to the leaves it's done, and cannot loop back to form cycles.

Page 38:

"A graph with no cycles is called an acyclic graph. A tree is a connected acyclic graph. A rooted tree is a tree with a distinguished vertex, called a root. Vertices of a tree are also called nodes. In addition, they are called leaves when they are adjacent to only one vertex each".

Page 122:

"Let us consider first a sequencing graph entity that has only operation vertices, e.g., a non-hierarchical model or an entity that is a leaf of the hierarchy. The vertex set V is in one-to-one correspondence with the operations. The edge set E models the dependencies due to data flow or serialization. The graph has two major properties. First, it is acyclic..."

Directed Acyclic Graph

\$\endgroup\$
  • \$\begingroup\$ I still think that the book I'm using is a bit ambiguous in terms of terminology. For example I struggle to understand some examples the book propose. Can you point out some better reference for sequencing graphs? \$\endgroup\$ – user8469759 Sep 27 '16 at 12:18
  • \$\begingroup\$ Sorry I can't give a better reference. Until yesterday I had no idea what a directed acyclic graph was. So I googled it... \$\endgroup\$ – Bruce Abbott Sep 27 '16 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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