Predicate-aware scheduling: A technique for reducing resource constraints

Predicated execution enables the removal of branches wherein seg-ments of branching code are converted into straight-line segments of conditional operations. An important, but generally ignored side effect of this transformation is that he compiler must assign distinct resources to all the predicated operations at a given time to ensure that those r sources are available at run-time. However, a resource is only put to productive use when the predicates associated with its operations evaluate to True. We propose predicate-aware schedul-ing to reduce the superfluous commitment of resources to opera-tions whose predicates evaluate to False at run-time. The central idea is to assign multiple operations to the same resource at the same time, thereby oversubscribing itsuse. This assignment is in-telligently performed to ensure that no two operations simultane-ously assigned to the same resource will have both of their predi-cates evaluate to True. Thus, no resource is dynamically oversub-scribed. The overall effect of predicate aware scheduling is to use resources more efficiently, thereby increasing performance when resource constraints are a bottleneck