This program has 10 instructions. What is (1) the maximum ILP in this sequence? What is the minimum amount of time it can complete in, assuming that you had a superscalar processor that could perform an infinite number of independent instructions per clock?

The minimum execution time, assuming infinite resources, is called the span of a program. In other words, it's the depth of the DAG. See more about span here: https://smlhelp.github.io/book/concepts/workspan.html

In this example, the most ILP we can get is 3 (executing instructions 02, 04, 05 in 1 clock cycle)? How would a jump instruction fit in this DAG? For example, lets say "else" instruction 10 was instead jump to instruction 2 for a while loop then this wont be a DAG right and cyclicality is possible. Just wanted to clarify if this ILP graph always must be a DAG?

I understand that maximum ILP (just like "span") would be characterized by the depth of the dependency graph. Maximum ILP would be 5 in this case, and so is the minimum number of cycles required to execute, given we can execute at least 3 instructions per clock cycle.

I see that unlike my comment above, shivalgo's used the correct definiton of ILP, as discussed in Slide 41. I agree with his answer, in that case

@pranil - looks like span is 5 (cannot go below this depth. no matter how many compute units we throw at it) and max ILP = 3. But I still think conditional and unconditional branching complicate the situation and the graph is no longer a DAG. How does loops then affect max ILP and span numbers?

conditional and unconditional branching complicate the situation and the graph is no longer a DAG

Not sure if I'm understanding this correctly but it seems like branching is part of the instruction dependency graph. You can see that node "09" and "10" both depends on the node "08", which is the branch instruction. So I think it doesn't affect the span but I'm not 100% sure about ILP (since executing "09" and "10" together wouldn't affect the performance of the program anyways).

I believe that ILP won't be affected by executing "09" and "10" together (which already happens in the instruction dependency graph) because we can't paralelize either of these instructions with any other instruction placed above in the graph (i.e. in span 4 or below). Also, to impact ILP, we would need to paralelize 2 of the instructions in the graph (since the current ILP is 3 and to do better we would need to get to at least 4). I cannot find two instructions that can be further paralelized in the graph.

If you think scheduling instructions is an interesting problem, you may want to take CS243 which covers this topic. You can also take a look at the List Scheduling algorithm which uses a greedy approach - (https://suif.stanford.edu/~courses/cs243/lectures/l7.pdf) and (http://www.cs.cmu.edu/afs/cs/academic/class/15745-f03/public/lectures/L16_handouts.pdf)