6 Local instruction scheduling problem Given a labeled dependency DAG G = (N, E) for a basic block, find a schedule S that specifies a start time S( i ) for each instruction such that S( i ) S( j ), i, j N, i j, and S( j ) S( i ) + latency( i, j ), ( i, j ) E, and max{ S( i ) | i N } is minimized.
{}