Grant Wallace
CS597d
 
Observation 12:
The Program Decision Logic Approach to Predicated Execution [1]
 
Strengths:
    Reduces control flow height by doing boolean minimization on the decision network represented by the predicate define instructions. This gives a simpler control flow graph, which can significantly improve performance in applications with a lot of decision logic.
    Factorization is performed on the BDD which reduces the number of pred defines necessary in two-level synthesis. It can also allow parts of the decision logic to be calculated early (depending on condition availability), possibly utilizing previously empty resource slots. Four new predicated define types are introduced to efficiently support this. Essentially these new predicated define types also consider the predicate guarding the define instruction as a condition.
    The minimized BDD is re-expressed into predicate defines. If an architecture doesn’t support predication, complete reverse if-conversion can be performed to create branch control flow.
    Shows a speedup of 1.13 over predicated code not using BDD minimization.
 
Weaknesses:
    Increases the number of predicated defines compared to predicated code which in not BDD minimized. On lower issue processors this can become a resource constraint, potentially reducing the performance gains achieved from control flow minimization.
 
Questions:
    I’m curious what type of performance improvement this technique yields on non-predicated architectures (i.e. complete reverse if-conversion after BDD minimization).
 
    I’m confused by the \/F and /\F type, I would think it would be…
psrc comp  \/F    /\F
0       0       1      -
0       1       -       -
1       0       -       -
1       1       -       0
 
 
[1] David I. August, ... "The Program Decision Logic Approach to Predicated Execution" Proceedings of the 26th International Symposium on Computer Architecture, May, 1999.