Download Algorithms for Mapping and Scheduling Real-Time

Transcript
24
CHAPTER 5. LAZY CONSTRAINTS
by freezing one row (row1 ) of d matrix and compares the values with the other row
(row2 ). It is comparing two columns of these rows (col1 and col2 ). If all those values in
the selected rows and columns match, the information that processors have the same
WCET for those actors is recorded to symmetry matrix Sym at index Symrow1 ,row2
and also diagonally symmetrical Symrow2 ,row1 . While we read the symmetrical matrix
and Symi1 ,i2 6= ; to mean there are symmetries between actors i1 and i2 on the
processors listed in values recorded to the matrix Sym at index i1 , i2 .
[1] Input: di,j
[2] Output: Set of Symmetries S
[3] i1 = 0;
[4] for i1 < d.length do
[5]
row1 = d[i1 ];
[6]
i2 = i1 + 1;
[7]
for i2 < d.length do
[8]
row2 = d[i2 ];
[9]
j1 = 0;
[10]
for j1 < row1 .length do
[11]
col1 = {row1 [j1 ], row2 [j1 ]}
[12]
if col1 [0] == 0 OR col1 [1]
[13]
continue;
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
== 0 then
end
j2 = j1 + 1;
for j2 < row1 .length do
col2 = {row1 [j2 ], row2 [j2 ]}
if col1 [0] == 0 OR col1 [1] == 0 then
continue;
end
if col1 [0] == col2 [0] == col1 [1] == col2 [1] then
Sym[i1 ][i2 ].add({j1 , j2 });
Sym[i2 ][i1 ].add({j1 , j2 });
end
j2 ++;
end
j1 ++;
end
i2 ++;
end
i1 ++;
end
return Symmetries
Algorithm 1: Finding symmetries
We propose an algorithm which is able to find all symmetries based on the input
containing WCET of each actor on each processor. As mentioned before the input