В настоящее время я реализую Swing Modulo Scheduling в среде с открытым исходным кодом и борюсь с этим.
Сначала я вычисляю свойства узла графа, включая Высоту, Глубину, ASAP, ALAP и MOV. После этого вычисляются SCC для частичного порядка и учитываются вершины между наборами частичного порядка. Затем выполняется упорядочение узлов, игнорируя задние края графа. В конце концов график заполнен.
График (https://drive.google.com/file/d/1rdiATd1O5xO7p1GAXh15zklhqve_6z4E/view?usp=sharing), который, я думаю, может быть запланирован с помощью SMS, не запланирован, потому что перед ним запланированы два предшественника и один предшественник. Один (node_1118) из предшественников ограничивает время планирования node_1117, так что EarlyStart> LateStart и не может быть найден подходящий для него слот. Я также рассмотрел ребра между операциями с задержкой 0, чтобы выбрать вершину с наибольшей глубиной или высотой.
Vertex: node_1002 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 7 Zero Depth: 0
Vertex: node_1003 ASAP: 6 ALAP: 6 MOV: 0 Height: 0 Depth: 6 Zero Height: 0 Zero Depth: 7
Vertex: node_1104 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 1 Zero Depth: 1
Vertex: node_1105 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 1 Zero Depth: 3
Vertex: node_1106 ASAP: 4 ALAP: 4 MOV: 0 Height: 2 Depth: 4 Zero Height: 0 Zero Depth: 7
Vertex: node_1107 ASAP: 4 ALAP: 4 MOV: 0 Height: 2 Depth: 4 Zero Height: 1 Zero Depth: 6
Vertex: node_1108 ASAP: 4 ALAP: 4 MOV: 0 Height: 2 Depth: 4 Zero Height: 2 Zero Depth: 0
Vertex: node_1109 ASAP: 2 ALAP: 2 MOV: 0 Height: 4 Depth: 2 Zero Height: 3 Zero Depth: 0
Vertex: node_1110 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 1 Zero Depth: 3
Vertex: node_1112 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 1 Zero Depth: 1
Vertex: node_1113 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 0 Zero Depth: 4
Vertex: node_1114 ASAP: 1 ALAP: 5 MOV: 4 Height: 1 Depth: 1 Zero Height: 1 Zero Depth: 0
Vertex: node_1115 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1117 ASAP: 0 ALAP: 6 MOV: 6 Height: 0 Depth: 0 Zero Height: 2 Zero Depth: 5
Vertex: node_1118 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 3 Zero Depth: 4
Vertex: node_1119 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 4 Zero Depth: 3
Vertex: node_1120 ASAP: 1 ALAP: 5 MOV: 4 Height: 1 Depth: 1 Zero Height: 1 Zero Depth: 0
Vertex: node_1121 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 6 Zero Depth: 1
Vertex: node_1122 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 5 Zero Depth: 2
Vertex: node_1126 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 6 Zero Depth: 1
Vertex: node_1128 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 6 Zero Depth: 1
Vertex: node_1127 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 5 Zero Depth: 2
Vertex: node_1129 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 4 Zero Depth: 1
Vertex: node_1130 ASAP: 0 ALAP: 6 MOV: 6 Height: 0 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1116 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 2 Zero Depth: 2
Vertex: node_1134 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1136 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1135 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 2 Zero Depth: 2
Vertex: node_1137 ASAP: 0 ALAP: 1 MOV: 1 Height: 5 Depth: 0 Zero Height: 0 Zero Depth: 2
Vertex: node_1138 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 3 Zero Depth: 4
Vertex: node_1139 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 4 Zero Depth: 1
Vertex: node_1140 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 2 Zero Depth: 5
Vertex: node_1141 ASAP: 5 ALAP: 5 MOV: 0 Height: 1 Depth: 5 Zero Height: 1 Zero Depth: 0
Vertex: node_1142 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1143 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 2 Zero Depth: 2
Vertex: node_1147 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1149 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_1148 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 2 Zero Depth: 2
Vertex: node_1150 ASAP: 1 ALAP: 1 MOV: 0 Height: 5 Depth: 1 Zero Height: 1 Zero Depth: 0
Vertex: node_1153 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 0 Zero Depth: 1
Vertex: node_1154 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 0 Zero Depth: 2
Vertex: node_1155 ASAP: 5 ALAP: 5 MOV: 0 Height: 1 Depth: 5 Zero Height: 1 Zero Depth: 0
Vertex: node_1158 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 0 Zero Depth: 1
Vertex: node_1159 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 0 Zero Depth: 2
Vertex: node_6002 ASAP: 0 ALAP: 6 MOV: 6 Height: 0 Depth: 0 Zero Height: 1 Zero Depth: 6
Vertex: node_6155 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_6156 ASAP: 0 ALAP: 0 MOV: 0 Height: 6 Depth: 0 Zero Height: 3 Zero Depth: 1
Vertex: node_6157 ASAP: 0 ALAP: 4 MOV: 4 Height: 2 Depth: 0 Zero Height: 6 Zero Depth: 1
MinII равен 4, и порядок, который я вычислил, следующий:
Order: {node_1141 node_1106 node_1107 node_1108 node_1109 node_1150 node_1105 node_1143 node_1142 node_1155 node_1113 node_1110 node_1116 node_1115 node_1114 node_1140 node_1138 node_1119 node_1135 node_1154 node_1137 node_1122 node_1127 node_1148 node_1159 node_1104 node_1112 node_1134 node_1136 node_1153 node_6156 node_1121 node_1126 node_1128 node_1139 node_1147 node_1149 node_1158 node_6155 node_6157 node_1002 node_1129 node_1118 node_1120 node_1130 node_1117 node_6002 node_1003 }
Частичный заказ:
Set1: node_1105 node_1106 node_1107 node_1108 node_1109 node_1141 node_1142 node_1143 node_1150 node_1155 (RecMII = 4)
Set2: node_1110 node_1113 node_1114 node_1115 node_1116 (RecMII = 2)
Set3: node_1002 node_1104 node_1112 node_1117 node_1118 node_1119 node_1120 node_1121 node_1122 node_1126 node_1128 node_1127 node_1129 node_1130 node_1134 node_1136 node_1135 node_1137 node_1138 node_1139 node_1140 node_1147 node_1149 node_1148 node_1153 node_1154 node_1158 node_1159 node_6155 node_6156 node_6157 (RecMII = 2)
Set4: node_1003 node_6002 (Remaining Vertices)
Не найдено подходящего графика для этого графика. Может быть, кто-то может найти проблему. Я думаю, что это сочетание проблемы, связанной с анализом и упорядочением узлов.
Также термин «повторение» является проблемой. Я думаю, что они имеют в виду SCC.