Minimal Set of Essential Resource Disjoint Pairs for Exploring Feasible 3D Schedules

In many synthesis approaches, scheduling is completed before resource binding. Binding centric approaches and simultaneous scheduling/binding approaches such as 3D scheduling are alternative approaches to the high level synthesis. In those approaches, binding is often performed before completion of scheduling. The objective of this paper is to identify and characterize a "feasible" resource binding which guarantees schedulability. The paper introduces the concept of "essential resource disjointness" which is an unavoidable resource disjointness for a valid schedule. It also introduces the concept of "minimal set" of essential resource disjoint pairs (MinERD), and show that MinERD can be characterized by a single processor schedule. By only taking care of MinERD, a schedulable resource binding is always guaranteed