Solution Set 3

Assigned: Feb. 15.
Due: Mar. 1.

Problem 1

The MULTIPROCESSOR PRECEDENCE CONTRAINED SCHEDULING problem is defined as follows: You are given: The object is to give a schedule for T that observes all these constraints. A schedule is an assignment of a processor and a starting time to each task such that each processor is running at most one task at a time; each task runs for the specified length; and the precedence constraints are observed.

For example, suppose M=3, T1 ... T6 have respective lengths 3, 2, 3, 4, 2, and 1, and T2 < T3, T1 < T4, T2 < T4, T3 < T5, and D=8. Then one valid schedule would be the following:

M1: Task T1 from 0 to 3, idle from 3 to 5, task T5 from 5 to 7, idle from 7 to 8
M2: Task T2 from 0 to 2, idle from 2 to 3, task T4 from 3 to 7, idle from 7 to 8
M3: Idle from 0 to 2, Task T3 from 2 to 5, task T6 from 5 to 6.
If l(T), M, and D are all small integers, then the problem can be compiled into propositional satisfiability using propositional atoms of the form T_P_K meaning that task T begins on processor P at time K, where K=0 ... D-1. The number of propositional atoms is thus |T| * M * D. Describe the constraints you need for the general case. Illustrate each category of constraint with a sample constraint from the above example. As a function of M, |T|, and D, how many constraints are there (order of magnitude)?


First category of constraints: Every task is begun on some processor no later than D-l(T). Thus, for each task T,
T_P1_0 V T_P1_2 V ... V T_P0_(D-l(T)) V T_P1_1 V ... V T_P1_(D-l(T)) V ... T_PM_1 V ... V T_PM_(D-l(T)).
In our example, with T=T4, this would be,
T4_P1_0 V T4_P1_1 V T4_P1_2 V T4_P1_3 V T4_P1_4 V
T4_P2_0 V T4_P2_1 V T4_P2_2 V T4_P2_3 V T4_P2_4 V
T4_P3_0 V T4_P3_1 V T4_P3_2 V T4_P3_3 V T4_P3_4.
In general, there are |T| such constraints, each with O(M*D) disjuncts

Second category of constraints: A task begins on only one processor at only one time. For each task T, for each pair of processors P1, P2, for each pair of times I,J, if either P1 != P2 or I != J, then ~(T_P1_I ^ T_P2^J). In our example an instance would be ~(T1_P1_0 ^ T1_P3_2). There are |T|*|M|2*D2 such constraints.

Third category of constraints: A processor runs only one task at one time. Thus, if P is a processor, T1 and T2 are tasks with T1 != T2 , and K1 and K2 are times with K1 <= K2 < K1 + l(T1) then ~(T1_P_K1 ^ T2_P_K2). An instance in our example would be ~(T1_P1_0 ^ T2_P1_0). Number of constraints: |T|2*M*D2. (More precisely, |T|2*M*D * maxT l(T). The difference may be significant if all of the l(T) are much smaller than D.)

Fourth category of constraints: Precedence constraints. Thus, if T1 and T2 are any pair of tasks where T1 < T2, P1 and P2 are two processes (either equal or different), and K1 and K2 are times such that K2 < K1 + l(T1), then ~(T1_P1_K1 ^ T2_P1^K2). An instance in our example would be ~(T1_P1_1 ^ T4_P1_2). The number of such contraints is O(|T|2 * M2 * D2). (More exactly, O(C * M2 * D2), where C is the number of precedence constraints, which is generally much smaller than T2.)

In counting the total number of constraints, the dominating term is either the second or the fourth category, depending whether C or T is larger. O(max(C,T) *M2 * D2)

Problem 2

Consider a first-order language L over a universe of people with the following primitives:
p(X,Y) --- Predicate. X is a parent of Y.
fa(X,Y) --- Predicate. X is a father of Y.
mo(X,Y) --- Predicate. X is a mother of Y.
fe(X) --- Predicate. X is female
a(X) --- Predicate. X is alive.
o(X) --- Predicate. X is an orphan.
s,a,b --- Constant. Sarah, Andy, Bob.
Express the following statements in L.