7 Literal Selection in Switching Lattice Design
165
diagonal cells, we could obtain lattices for the same target function with a lower
degree or with a smaller number of areas. For instance, the lattice in Fig. 7.2c has
degree 3, and the lattice in Fig. 7.2d has only four areas, one for x 1 , one for x 3 , and
two disjoint areas for x 2 .
Motivated by the previous considerations, we pose the following two optimization problems:
Minimal Degree Assignment (MDA) Problem Find a literal assignment that
minimizes the degree of the lattice.
Minimal Partition Assignment (MPA) Problem Find a literal assignment that
minimizes the number of areas in the lattice.
7.4 The MDA Problem
The MDA problem is motivated by the need of avoiding an excessive load to any
single circuit generating an input variable. For this reason, our first optimization
problem focuses on minimizing the lattice degree, i.e., minimizing the maximum
number of lattice cells assigned to the same literal.
Although this problem has not been directly studied in the past, we have found
some interesting connections to many different and known problems such as graph
orientation problems [6], network flow problems [28], and a variant of bipartite
maximum matching called semi-matching used to solve a particular type of the
offline scheduling problem [27]. These problems are all solvable in polynomial time,
making our problem polynomially solvable too, thanks to simple and immediate
reductions. Interestingly enough, the weighted versions of all these problems are
NP-hard, thus making the MDA problem NP-hard as well whenever an integer
weight is assigned to each switch and the degree is computed taking into account
the weights.
The area of scheduling problems is the one that provided the most useful
reductions. In particular MDA is equivalent to a restricted version of the offline
parallel machine scheduling problem, or PMS, which has received great attention
in the literature (e.g., see [25, 30]). PMS consists of assigning m jobs to n identical,
unrelated, machines, with the goal of minimizing one or more objective functions,
for instance, the makespan 2 of the scheduling. The restricted version of PMS
equivalent to MDA is the version where each job requires one unit of time to
complete, and can be executed only on a specific subset of the available machines.
Proposition 7.1 MDA problem on an N × M lattice with different literals is
equivalent to the restricted PMS with NM unit-time jobs and machines.
2 The makespan of a schedule is the difference in time between its start and its end. With unitlength jobs, as we assume below, makespan represents the maximum number of jobs assigned to a
machine.
165
diagonal cells, we could obtain lattices for the same target function with a lower
degree or with a smaller number of areas. For instance, the lattice in Fig. 7.2c has
degree 3, and the lattice in Fig. 7.2d has only four areas, one for x 1 , one for x 3 , and
two disjoint areas for x 2 .
Motivated by the previous considerations, we pose the following two optimization problems:
Minimal Degree Assignment (MDA) Problem Find a literal assignment that
minimizes the degree of the lattice.
Minimal Partition Assignment (MPA) Problem Find a literal assignment that
minimizes the number of areas in the lattice.
7.4 The MDA Problem
The MDA problem is motivated by the need of avoiding an excessive load to any
single circuit generating an input variable. For this reason, our first optimization
problem focuses on minimizing the lattice degree, i.e., minimizing the maximum
number of lattice cells assigned to the same literal.
Although this problem has not been directly studied in the past, we have found
some interesting connections to many different and known problems such as graph
orientation problems [6], network flow problems [28], and a variant of bipartite
maximum matching called semi-matching used to solve a particular type of the
offline scheduling problem [27]. These problems are all solvable in polynomial time,
making our problem polynomially solvable too, thanks to simple and immediate
reductions. Interestingly enough, the weighted versions of all these problems are
NP-hard, thus making the MDA problem NP-hard as well whenever an integer
weight is assigned to each switch and the degree is computed taking into account
the weights.
The area of scheduling problems is the one that provided the most useful
reductions. In particular MDA is equivalent to a restricted version of the offline
parallel machine scheduling problem, or PMS, which has received great attention
in the literature (e.g., see [25, 30]). PMS consists of assigning m jobs to n identical,
unrelated, machines, with the goal of minimizing one or more objective functions,
for instance, the makespan 2 of the scheduling. The restricted version of PMS
equivalent to MDA is the version where each job requires one unit of time to
complete, and can be executed only on a specific subset of the available machines.
Proposition 7.1 MDA problem on an N × M lattice with different literals is
equivalent to the restricted PMS with NM unit-time jobs and machines.
2 The makespan of a schedule is the difference in time between its start and its end. With unitlength jobs, as we assume below, makespan represents the maximum number of jobs assigned to a
machine.