166
A. Bernasconi et al.
Proof Consider each lattice switch s as a unit-time job, and each literal that occurs
at least once in the lattice as a machine. Moreover, let every subset L s of literals
assigned to a switch s represent the subset of machines that can execute job s.
A solution of the restricted PMS problem on this instance, i.e., an assignment of
each job to a machine, corresponds to an assignment of each switch to a single
literal. Since the jobs require one unit of time to complete, an optimal solution
that minimizes the makespan is equivalent to an optimal solution that minimizes
the maximum number of jobs assigned to a machine. This, in turn, is equivalent
to minimize the maximum number of switches assigned to the same literal, i.e., to
minimize the lattice degree.
For example, the top left cell v 1 of the lattice in Fig. 7.2a represents a job that can
be executed by the two machines associated with the literals x 1 and x 2 .
In [27], two exact polynomial time algorithms for the restricted PMS have been
proposed which can be immediately adapted to solving MDA. Let m = NM be
the lattice size, and let be the number of distinct literals occurring in the lattice.
Notice that n ≤ ≤ 2n, where n is the number of input variables of the function f
implemented by the lattice. We denote by K the size of the input instance, that is,
the total number of elements in the collection S of sets L i , 1 ≤ i ≤ m, of literals
that could be assigned to each switch s i of the lattice. Note that K = O(mn).
The first exact algorithm is theoretically more efficient, with a time complexity of
order O(mK) = O(m 2 n). Since m = NM, with N and M given by the number
of products in irredundant SOP representations of f and f D (see Sect. 7.2), the
algorithm can be very time consuming. Indeed, N and M could be exponential in
the number of input variables n. The second algorithm proposed in [27] has a worst
case running time O(m 2 n 2 ) worse than the previous one, but in practice performs
better.
Due to the high cost of these algorithms, we propose a very efficient heuristic
algorithm, called HMDA, for solving the MDA problem, which shows a very high
success rate with respect to an always-optimal algorithm (see Sect. 7.6) and whose
cost in time is linear in the size K of the input instance. To this end we state an
immediate lower bound on the minimal degree d ∗ of the lattice that will be exploited
by the heuristic.
Proposition 7.2 d ∗ ≥ ≥
m
The input to HMDA is the collection S. Each set R in S has an additional
attribute R.pos which holds the position h, 1 ≤ h ≤ m, of the corresponding
switch in the lattice. The sets in S are first sorted by their cardinality in ascending
order to provide more freedom for the choice of literals as the algorithm proceeds.
The selection strategy of the heuristic is the following:
1. Among all literals in the current subset that have not been chosen more than
m
times, choose the one with the lowest number of occurrences across all the
(remaining) subsets.
2. If such a literal does not exist, or in case of ties, select the literal chosen the
lowest number of times so far.
A. Bernasconi et al.
Proof Consider each lattice switch s as a unit-time job, and each literal that occurs
at least once in the lattice as a machine. Moreover, let every subset L s of literals
assigned to a switch s represent the subset of machines that can execute job s.
A solution of the restricted PMS problem on this instance, i.e., an assignment of
each job to a machine, corresponds to an assignment of each switch to a single
literal. Since the jobs require one unit of time to complete, an optimal solution
that minimizes the makespan is equivalent to an optimal solution that minimizes
the maximum number of jobs assigned to a machine. This, in turn, is equivalent
to minimize the maximum number of switches assigned to the same literal, i.e., to
minimize the lattice degree.
For example, the top left cell v 1 of the lattice in Fig. 7.2a represents a job that can
be executed by the two machines associated with the literals x 1 and x 2 .
In [27], two exact polynomial time algorithms for the restricted PMS have been
proposed which can be immediately adapted to solving MDA. Let m = NM be
the lattice size, and let be the number of distinct literals occurring in the lattice.
Notice that n ≤ ≤ 2n, where n is the number of input variables of the function f
implemented by the lattice. We denote by K the size of the input instance, that is,
the total number of elements in the collection S of sets L i , 1 ≤ i ≤ m, of literals
that could be assigned to each switch s i of the lattice. Note that K = O(mn).
The first exact algorithm is theoretically more efficient, with a time complexity of
order O(mK) = O(m 2 n). Since m = NM, with N and M given by the number
of products in irredundant SOP representations of f and f D (see Sect. 7.2), the
algorithm can be very time consuming. Indeed, N and M could be exponential in
the number of input variables n. The second algorithm proposed in [27] has a worst
case running time O(m 2 n 2 ) worse than the previous one, but in practice performs
better.
Due to the high cost of these algorithms, we propose a very efficient heuristic
algorithm, called HMDA, for solving the MDA problem, which shows a very high
success rate with respect to an always-optimal algorithm (see Sect. 7.6) and whose
cost in time is linear in the size K of the input instance. To this end we state an
immediate lower bound on the minimal degree d ∗ of the lattice that will be exploited
by the heuristic.
Proposition 7.2 d ∗ ≥ ≥
m
The input to HMDA is the collection S. Each set R in S has an additional
attribute R.pos which holds the position h, 1 ≤ h ≤ m, of the corresponding
switch in the lattice. The sets in S are first sorted by their cardinality in ascending
order to provide more freedom for the choice of literals as the algorithm proceeds.
The selection strategy of the heuristic is the following:
1. Among all literals in the current subset that have not been chosen more than
m
times, choose the one with the lowest number of occurrences across all the
(remaining) subsets.
2. If such a literal does not exist, or in case of ties, select the literal chosen the
lowest number of times so far.