EMMA Coverage Report (generated Tue Aug 23 05:57:12 CDT 2011)
[all classes][felix.optimizer]

COVERAGE SUMMARY FOR SOURCE FILE [DataCracker1991.java]

nameclass, %method, %block, %line, %
DataCracker1991.java100% (1/1)71%  (5/7)78%  (719/923)81%  (133/165)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class DataCracker1991100% (1/1)71%  (5/7)78%  (719/923)81%  (133/165)
gcd (int []): int 0%   (0/1)0%   (0/50)0%   (0/8)
gcd2 (int, int): int 0%   (0/1)0%   (0/11)0%   (0/2)
getExpressions (FelixClause, Predicate, int, int, boolean): HashSet 100% (1/1)67%  (288/430)73%  (58/79)
decompose (StatOperator): void 100% (1/1)100% (373/374)99%  (67/68)
DataCracker1991 (): void 100% (1/1)100% (26/26)100% (6/6)
toCanonicalFieldName (FelixPredicate, int): String 100% (1/1)100% (16/16)100% (1/1)
toCanonicalFieldName (Predicate, int): String 100% (1/1)100% (16/16)100% (1/1)

1package felix.optimizer;
2 
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.HashSet;
6 
7import tuffy.mln.Literal;
8import tuffy.mln.Predicate;
9import tuffy.ra.Expression;
10import tuffy.ra.Function;
11 
12import org.apache.commons.math.optimization.GoalType;
13import org.apache.commons.math.optimization.RealPointValuePair;
14import org.apache.commons.math.optimization.linear.LinearConstraint;
15import org.apache.commons.math.optimization.linear.LinearObjectiveFunction;
16import org.apache.commons.math.optimization.linear.Relationship;
17import org.apache.commons.math.optimization.linear.SimplexSolver;
18 
19import felix.dstruct.FelixClause;
20import felix.dstruct.FelixPredicate;
21import felix.dstruct.StatOperator;
22 
23//TODO: CURRENTLY SOLVED BY ROUND!!!
24//TODO: MAYBE CHANGE TO HASH!!!!!!
25 
26 
27/**
28 * An object of DataCracker1991 will try its best to discover opportunities
29 * of partitioning the data.
30 */
31public class DataCracker1991 {
32 
33        /**
34         * Map from variable ID to the signature of predicate's field. This ID is used
35         * in the ILP solver.
36         */
37        public HashMap<Integer, String> varID2predField = new HashMap<Integer, String>();
38        
39        /**
40         * Map from variable ID to the predicate. This ID is used
41         * in the ILP solver.
42         */
43        public HashMap<Integer, FelixPredicate> varID2pred = new HashMap<Integer, FelixPredicate>();
44        
45        /**
46         * Map from variable ID to predicate's field ID. This ID is used
47         * in the ILP solver.
48         */
49        public HashMap<Integer, Integer> varID2field = new HashMap<Integer, Integer>();
50        
51        /**
52         * The inverse map of {@link DataCracker1991#varID2predField}.
53         */
54        public HashMap<String, Integer> predField2varID = new HashMap<String, Integer>();
55        
56        /**
57         * The array that saves the solution of the ILP solver.
58         */
59        double[] ss;
60        
61        /**
62         * Whether the recently processed operator is decomposable.
63         */
64        boolean isDecomposable = false;
65        
66        /**
67         * Generate the signature of predicate's field.
68         * @param p
69         * @param fieldNum
70         * @return
71         */
72        public String toCanonicalFieldName(FelixPredicate p, int fieldNum){
73                return p.getName() + ":" + p.getArgs().get(fieldNum);
74        }
75        
76        /**
77         * Generate the signature of predicate's field.
78         * @param p
79         * @param fieldNum
80         * @return
81         */
82        public String toCanonicalFieldName(Predicate p, int fieldNum){
83                return p.getName() + ":" + p.getArgs().get(fieldNum);
84        }
85        
86        /**
87         * Decompose the data used by the given operator.
88         * @param op
89         */
90        public void decompose(StatOperator op){
91                
92                try{
93                        
94                        // get all open predicates can be seperated
95                        HashSet<FelixPredicate> openPredicates = op.outputPredicates;
96                        
97                        int ct = 0;
98                        for(FelixPredicate p : openPredicates){                
99                                for(int i=0;i<p.arity();i++){
100                                        varID2predField.put(ct, toCanonicalFieldName(p, i));
101                                        varID2pred.put(ct, p);
102                                        varID2field.put(ct, i);
103                                        predField2varID.put(toCanonicalFieldName(p, i), ct);
104                                        ct++;
105                                }
106                        }
107                        
108                        
109                        double[] zeros = new double[ct];
110                        double[] ones = new double[ct];
111                        for(int i=0;i<ct;i++){
112                                zeros[i] = 0;
113                                ones[i] = 1;
114                        //        System.out.println(i + "\t" + varID2predField.get(i));
115                        }
116                        
117                        // obj function :- 0x1 + 0x2 + ... + xn = 0
118                        LinearObjectiveFunction f = 
119                                new LinearObjectiveFunction(zeros, 0);
120                        //LinearObjectiveFunction f = 
121                        //        new LinearObjectiveFunction(ones, 0);
122                        
123                        ArrayList<LinearConstraint> constraints = new ArrayList<LinearConstraint>();
124                        
125                        // constraint :- pi_1 + pi_2 + ... + pi_n >= 1
126                        constraints.add(new LinearConstraint(ones, Relationship.GEQ, 1));
127                        
128                        
129                        //TODO: Assume we know there are partitionings to some fields,
130                        // how can we push them back to other operators? (e.g., date -> d
131                        // throught aligned(.,.) relation).
132 
133                        for(FelixClause c : op.allRelevantFelixClause){
134                                                                
135                                // for each clause, generate constraints for the linear system.
136                                ArrayList<Literal> allLiterals = c.getRegLiterals();
137                                
138                                for(Literal l1 : allLiterals){
139                                        for(Literal l2 : allLiterals){
140                                                if(l1.equals(l2)){
141                                                        continue;
142                                                }
143                                                
144                                                if(op.outputPredicates.contains(l1.getPred()) == false ||
145                                                                op.outputPredicates.contains(l2.getPred()) == false){
146                                                        continue;
147                                                }
148                                                
149                                                //System.err.println(l1 + "\t" + l2);
150                                                
151                                                HashSet<String> allVars = new HashSet<String>();
152                                                allVars.addAll(l1.getVars());
153                                                allVars.addAll(l2.getVars());
154                                                
155                                                for(String var : allVars){
156                                                        
157                                                        HashSet<Integer> shouldBeOne = new HashSet<Integer>();
158                                                        HashSet<Integer> shouldBeNegOne = new HashSet<Integer>();
159                                                        
160                                                        for(int i=0;i<l1.getVars().size();i++){
161                                                                if(var.equals(l1.getTerms().get(i).toString())){
162                                                        //                System.out.print("+" + toCanonicalFieldName(l1.getPred(), i) + " ");
163                                                                        shouldBeOne.add(predField2varID.get(toCanonicalFieldName(l1.getPred(), i)));
164                                                                }
165                                                        }
166                                                        
167                                                        for(int i=0;i<l2.getVars().size();i++){
168                                                                if(var.equals(l2.getTerms().get(i).toString())){
169                                                        //                System.out.print("-" + toCanonicalFieldName(l2.getPred(), i) + " ");
170                                                                        shouldBeNegOne.add(predField2varID.get(toCanonicalFieldName(l2.getPred(), i)));
171                                                                }
172                                                        }
173                                                        
174                                                        //System.out.println();
175                                                        
176                                                        if(shouldBeOne.contains(null) || shouldBeNegOne.contains(null)){
177                                                                continue;
178                                                        }
179                                                        
180                                                        double[] cons = new double[ct];
181                                                        int nOfPos = 0;
182                                                        int nOfNeg = 0;
183                                                        for(int i=0;i<ct;i++){
184                                                                cons[i] = 0;
185                                                                if(shouldBeOne.contains(i)){
186                                                                        cons[i] += 1;
187                                                                        nOfPos ++;
188                                                                }
189                                                                if(shouldBeNegOne.contains(i)){
190                                                                        cons[i] += -1;
191                                                                        nOfNeg ++;
192                                                                }
193                                                        }
194                                                        
195                                                        // [# appearance] x_i_in_left * pi = x_i_in_right * pi
196                                                        constraints.add(new LinearConstraint(cons, Relationship.EQ, 0));
197                                                }
198                                                
199                                                
200                                        }
201                                }
202                                //System.out.println(c);
203                        }
204                        
205                        RealPointValuePair solution = new 
206                        //SimplexSolver().optimize(f, constraints, 
207                        //                GoalType.MAXIMIZE, false);
208                        SimplexSolver().optimize(f, constraints, 
209                                        GoalType.MAXIMIZE, false);
210                
211                        // get the solution and translated them into
212                        // integer form
213                        double[] tmpss = solution.getPoint();
214                        ss = new double[tmpss.length];
215                        
216                        double largest = Double.MIN_VALUE;
217                        for(int i=0;i<tmpss.length;i++){
218                                if(tmpss[i] >= largest){
219                                        largest = tmpss[i];
220                                }
221                        }
222 
223                        for(int i=0;i<ss.length;i++){
224                                ss[i] = tmpss[i]/largest;
225                        }
226                        
227                        isDecomposable = true;
228 
229                }catch(Exception e){
230                //        e.printStackTrace();
231                        isDecomposable = false;
232                }
233        }
234        
235        /**
236         * Return the GCD of the given two numbers.
237         * @param a
238         * @param b
239         * @return
240         */
241        int gcd2(int a, int b){
242                 if (b==0) return a;
243                 return gcd2(b,a%b);
244        }
245        
246        /**
247         * Return the GCD of the given multiple numbers.
248         * @param numbers
249         * @return
250         */
251        int gcd(int... numbers){
252                if(numbers.length == 1){
253                        return numbers[0];
254                }
255                int firstTwoGCD = gcd2(numbers[0], numbers[1]);
256                int[] newNumbers = new int[numbers.length - 1];
257                for(int i = 2; i<numbers.length; i++){
258                        newNumbers[i-2] = numbers[i];
259                }
260                newNumbers[newNumbers.length - 1] = firstTwoGCD;
261                return gcd(newNumbers);
262        }
263        
264        /**
265         * Given a clause appearing in the statOperator, return the appended expression
266         * to this clause to partition the data.
267         * @param fc
268         * @param _p if this value is not NULL and fc is NULL, generate a human-readable version for predicate _p
269         * @param base Number of partitions.
270         * @param nThread ID of the current partition.
271         * @param isSignature if this parameter is false, then it can be used as clause's constraints.
272         * @return
273         */
274        public HashSet<Expression> getExpressions(FelixClause fc, Predicate _p, int base, int nThread, boolean isSignature){
275                
276                HashSet<String> processedExpSignature = new HashSet<String>();
277                HashSet<Expression> ret = new HashSet<Expression>();
278                
279                if(fc != null){
280                        for(Literal l : fc.getRegLiterals()){
281                                
282                                Predicate p = l.getPred();
283                        
284                                Expression e = new Expression(Function.Eq);
285                                
286                                Expression emod = new Expression(Function.Modulo);
287                                
288                                Expression currentSumRoot = null;
289                                
290                                for(Integer fieldID : varID2pred.keySet()){
291                                        
292                                        if(ss[fieldID] == 0){
293                                                continue;
294                                        }
295                                        
296                                        if(!varID2pred.get(fieldID).equals(p)){
297                                                continue;
298                                        }
299                                        
300                                        if(currentSumRoot == null){
301                                                Expression etmp = new Expression(Function.Multiply);
302                                                if(isSignature == false){
303                                                        etmp.addArgument(l.getTerms().get(varID2field.get(fieldID)).isVariable() ? 
304                                                                        Expression.exprVariableBinding(l.getTerms().get(varID2field.get(fieldID)).toString()) : 
305                                                                        Expression.exprConstNum(l.getTerms().get(varID2field.get(fieldID)).constant() ));
306                                                }else{
307                                                        etmp.addArgument(Expression.exprVariableBinding(l.getPred().getArgs().get(varID2field.get(fieldID)).toString()));
308                                                }
309                                                etmp.addArgument(Expression.exprConstNum(ss[fieldID]));
310                                                
311                                                currentSumRoot = etmp;
312                                        }else{
313                                                Expression etmp = new Expression(Function.Add);
314                                                etmp.addArgument(currentSumRoot);
315                                                
316                                                Expression etoadd = new Expression(Function.Multiply);
317                                                if(isSignature == false){
318                                                        etoadd.addArgument(l.getTerms().get(varID2field.get(fieldID)).isVariable() ? 
319                                                                        Expression.exprVariableBinding(l.getTerms().get(varID2field.get(fieldID)).toString()) : 
320                                                                                Expression.exprConstNum(l.getTerms().get(varID2field.get(fieldID)).constant() ));
321                                                }else{
322                                                        etoadd.addArgument(Expression.exprVariableBinding(l.getPred().getArgs().get(varID2field.get(fieldID)).toString()));
323                                                }
324                                                        
325                                                etoadd.addArgument(Expression.exprConstNum(ss[fieldID]));
326                                                
327                                                etmp.addArgument(etoadd);
328                                                
329                                                currentSumRoot = etmp;
330                                                
331                                        }
332                                }
333                                
334                                if(currentSumRoot != null){
335                                
336                                        Expression eround = new Expression(Function.Round);
337                                        eround.addArgument(currentSumRoot);
338                                        emod.addArgument(eround);
339                                        emod.addArgument(Expression.exprConstInteger(base));
340                                        e.addArgument(emod);
341                                        e.addArgument(Expression.exprConstInteger(nThread));
342                                        e.changeName = false;
343                                        
344                                        if(processedExpSignature.contains(e.toString())){
345                                                continue;
346                                        }
347                                        
348                                        processedExpSignature.add(e.toString());
349                                        ret.add(e);
350                                        
351                                }
352                        }
353                }else if(_p != null){
354 
355                        Expression e = new Expression(Function.Eq);
356                        
357                        Expression emod = new Expression(Function.Modulo);
358                        
359                        Expression currentSumRoot = null;
360                        
361                        for(Integer fieldID : varID2pred.keySet()){
362                                
363                                if(ss[fieldID] == 0){
364                                        continue;
365                                }
366                                
367                                if(!varID2pred.get(fieldID).equals(_p)){
368                                        continue;
369                                }
370                                
371                                if(currentSumRoot == null){
372                                        Expression etmp = new Expression(Function.Multiply);
373                                        if(isSignature == false){
374                                                
375                                        }else{
376                                                etmp.addArgument(Expression.exprVariableBinding(_p.getArgs().get(varID2field.get(fieldID)).toString()));
377                                        }
378                                        etmp.addArgument(Expression.exprConstNum(ss[fieldID]));
379                                        
380                                        currentSumRoot = etmp;
381                                }else{
382                                        Expression etmp = new Expression(Function.Add);
383                                        etmp.addArgument(currentSumRoot);
384                                        
385                                        Expression etoadd = new Expression(Function.Multiply);
386                                        if(isSignature == false){
387                                                
388                                        }else{
389                                                etoadd.addArgument(Expression.exprVariableBinding(_p.getArgs().get(varID2field.get(fieldID)).toString()));
390                                        }
391                                                
392                                        etoadd.addArgument(Expression.exprConstNum(ss[fieldID]));
393                                        
394                                        etmp.addArgument(etoadd);
395                                        
396                                        currentSumRoot = etmp;
397                                        
398                                }
399                        }
400                        
401                        if(currentSumRoot != null){
402                        
403                                Expression eround = new Expression(Function.Round);
404                                eround.addArgument(currentSumRoot);
405                                emod.addArgument(eround);
406                                emod.addArgument(Expression.exprConstInteger(base));
407                                e.addArgument(emod);
408                                e.addArgument(Expression.exprConstInteger(nThread));
409                                e.changeName = false;
410                                                                
411                                processedExpSignature.add(e.toString());
412                                ret.add(e);
413                                
414                        }
415                }
416                return ret;
417        }
418        
419}
420 
421 
422 
423 
424 
425 

[all classes][felix.optimizer]
EMMA 2.0.5312 EclEmma Fix 2 (C) Vladimir Roubtsov