Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Heinrich Schuchardt
On 08/06/2017 09:40 PM, Andrew Makhorin wrote:
>>   FORMULA *op1;
>>   FORMULA *op2;
>> ...
>>  case O_ADD:
>> /* addition */
>> op1 = eval_formula(mpl, code->arg.arg.x);
>> op2 = eval_formula(mpl, code->arg.arg.y);
>> value = linear_comb(mpl,
>>+1.0, op1,
>>+1.0, op2);
>> break;
>>
>> gives same result on both arm64 and x86-64.
>>
>> I suggest you change all binary operands.
>>
> 
> This is a normal behavior. Besides, in general case this wouldn't help
> (for example, round-off errors may affect the model generation process).
> 
> If you need to avoid the difference in your case, just don't use random
> numbers as well as other functions having side effects.
> 
> 
> 

You decided to use a constant starting value for initializing the random
function to have reproduceable runs where we use random functions.

I think in the coding we should avoid situations where the result
depends on the choice of the compiler. This may result in different
results on the same architecture when compiling with different compiler
versions.

It would better to prescribe the evaluation sequence in the coding.

I must admit that this would imply some work for you.

Best regards

Heinrich Schuchardt

___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Andrew Makhorin
>   FORMULA *op1;
>   FORMULA *op2;
> ...
>  case O_ADD:
> /* addition */
> op1 = eval_formula(mpl, code->arg.arg.x);
> op2 = eval_formula(mpl, code->arg.arg.y);
> value = linear_comb(mpl,
>+1.0, op1,
>+1.0, op2);
> break;
> 
> gives same result on both arm64 and x86-64.
> 
> I suggest you change all binary operands.
> 

This is a normal behavior. Besides, in general case this wouldn't help
(for example, round-off errors may affect the model generation process).

If you need to avoid the difference in your case, just don't use random
numbers as well as other functions having side effects.



___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Heinrich Schuchardt
On 08/06/2017 08:20 PM, Andrew Makhorin wrote:
> 
>> In the first two cases evaluation of pt precedes evaluation of xt while
>> in the last three cases xt is evaluated before pt. At the moment I
>> cannot say why this happens...
> 
> I'm sure that this happens, because in the first two cases arguments
> passed to a function (I mean C code, not MathProg) are evaluated in one
> order while in the last three cases in some different order. For
> example, to add two linear forms the following statement is used in
> mpl3.c (see line 4754):
> 
> value = linear_comb(mpl,
>+1.0, eval_formula(mpl, code->arg.arg.x,
>+1.0, eval_formula(mpl, code->arg.arg.y);
> 
> where the order in which eval_formula is called depends on the platform.
> 
> 

  FORMULA *op1;
  FORMULA *op2;
...
 case O_ADD:
/* addition */
op1 = eval_formula(mpl, code->arg.arg.x);
op2 = eval_formula(mpl, code->arg.arg.y);
value = linear_comb(mpl,
   +1.0, op1,
   +1.0, op2);
break;

gives same result on both arm64 and x86-64.

I suggest you change all binary operands.

Best regards

Heinrich Schuchardt

___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Andrew Makhorin

> In the first two cases evaluation of pt precedes evaluation of xt while
> in the last three cases xt is evaluated before pt. At the moment I
> cannot say why this happens...

I'm sure that this happens, because in the first two cases arguments
passed to a function (I mean C code, not MathProg) are evaluated in one
order while in the last three cases in some different order. For
example, to add two linear forms the following statement is used in
mpl3.c (see line 4754):

value = linear_comb(mpl,
   +1.0, eval_formula(mpl, code->arg.arg.x,
   +1.0, eval_formula(mpl, code->arg.arg.y);

where the order in which eval_formula is called depends on the platform.


___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Andrew Makhorin
Hi Heinrich,

Thank you for your help.

> The following model is sufficient to demonstrate it:
> 
> param xt := Uniform01();
> param pt := Uniform01();
> 
> var y, >= 0;
> minimize obj : y + pt + xt;
> 
> solve;
> 
> printf "%f ", pt;
> printf "%f\n", xt;
> end;
> 
> 
> 
> x86: (32-bit LSB executable, i686, gcc 4.9.2)
> 0.009597 0.128312
> 
> x86-64: (64-bit LSB, x86-64, gcc 6.3.0)
> 0.009597 0.128312
> 
> armv7 (32-bit LSB, ARM, gcc 6.3.0)
> 0.128312 0.009597
> 
> armv8 (64-bit LSB, ARM aarch64, gcc 6.4.0)
> 0.128312 0.009597
> 
> mips (ELF 32-bit MSB, gcc 4.9.2)
> 0.128312 0.009597
> 
> Random numbers are generated in this sequence on all architectures:
> 
> printf {1..2} "%16.15f\n", Uniform01();
> 
> 0.128311804030091
> 0.009596675168723
> 

Good news: there is no bug.

In the first two cases evaluation of pt precedes evaluation of xt while
in the last three cases xt is evaluated before pt. At the moment I
cannot say why this happens, however, this is obviously not a bug,
because the order of evaluation of subexpressions is not defined (like
in C). Thus, if evaluation of a subexpression has a side effect (as in
case of using Uniform01), the result is indeterminate.


Best regards,

Andrew Makhorin


___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Heinrich Schuchardt
On 08/06/2017 05:52 PM, Andrew Makhorin wrote:
> 
>> The important thing is that I observed a difference for model parameters.
>>
>> ./glpsol --wlp test.lp -m test.mod --check
>>
>> yields totally different files test.lp and different objective values.
>> So this is a problem in model generation.
>>
>> If I take one of the lp files as input I get the same objective value on
>> both platforms. There is no problem in the solver.
>>
>> Replacing Uniform01() by round(Uniform01(), 5) does not change the
>> output for parameter pt[50] on both platforms.
>>
>> By rounding you cannot explain the difference between 334 and 472 of
>> model parameter pt[50]. This could only be explained by the sequence of
>> generation steps and hence Uniform01() values assigned to different
>> parameters on the different platforms.
>>
>> This should be fixed.
> 
> Could you please isolate the possible bug? That is, reduce your model
> file to a minimum minimorum where the bug still appears.
> 

The problem already exists in GLPK 4.53.

The following model is sufficient to demonstrate it:

param xt := Uniform01();
param pt := Uniform01();

var y, >= 0;
minimize obj : y + pt + xt;

solve;

printf "%f ", pt;
printf "%f\n", xt;
end;



x86: (32-bit LSB executable, i686, gcc 4.9.2)
0.009597 0.128312

x86-64: (64-bit LSB, x86-64, gcc 6.3.0)
0.009597 0.128312

armv7 (32-bit LSB, ARM, gcc 6.3.0)
0.128312 0.009597

armv8 (64-bit LSB, ARM aarch64, gcc 6.4.0)
0.128312 0.009597

mips (ELF 32-bit MSB, gcc 4.9.2)
0.128312 0.009597

Random numbers are generated in this sequence on all architectures:

printf {1..2} "%16.15f\n", Uniform01();

0.128311804030091
0.009596675168723

Best regards

Heinrich Schuchardt

___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Andrew Makhorin
Heinrich,

To see which parameters members are evaluated and in which order please
add a print stmt into the routine take_member_num, file src/mpl/mpl3.c,
as follows (it is marked by #if 1/#endif):

double take_member_num
( MPL *mpl,
  PARAMETER *par, /* not changed */
  TUPLE *tuple/* not changed */
)
{ MEMBER *memb;
  double value;
  /* find member in the parameter array */
  memb = find_member(mpl, par->array, tuple);
  if (memb != NULL)
  {  /* member exists, so just take its value */
 value = memb->value.num;
  }
  else if (par->assign != NULL)
  {  /* compute value using assignment expression */
 value = eval_numeric(mpl, par->assign);
add: /* check that the value satisfies to all restrictions, assign
it to new member, and add the member to the array */
 check_value_num(mpl, par, tuple, value);
 memb = add_member(mpl, par->array, copy_tuple(mpl, tuple));
 memb->value.num = value;
#if 1
xprintf("$$$ %s%s = %g\n",
par->name, format_tuple(mpl, '[', memb->tuple), memb->value.num);
#endif
  }
  else if (par->option != NULL)
  {  /* compute default value */
...

Hope this will shed a light on what really happens.


Best,

Andrew Makhorin


___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Andrew Makhorin

> The important thing is that I observed a difference for model parameters.
> 
> ./glpsol --wlp test.lp -m test.mod --check
> 
> yields totally different files test.lp and different objective values.
> So this is a problem in model generation.
> 
> If I take one of the lp files as input I get the same objective value on
> both platforms. There is no problem in the solver.
> 
> Replacing Uniform01() by round(Uniform01(), 5) does not change the
> output for parameter pt[50] on both platforms.
> 
> By rounding you cannot explain the difference between 334 and 472 of
> model parameter pt[50]. This could only be explained by the sequence of
> generation steps and hence Uniform01() values assigned to different
> parameters on the different platforms.
> 
> This should be fixed.

Could you please isolate the possible bug? That is, reduce your model
file to a minimum minimorum where the bug still appears.

Please note that the MathProg translator does not evaluate all members
of model parameters at once; instead that it evaluates only those
members which are actually used in other expressions. For example,

param pt{T} := ceil(1000 * Uniform01());

is not evaluated for all t in T at once; pt[t] is evaluated for a
particular t only if it is actually used in other expressions. So, in
some circumstances pt[t] might be evaluated in different orders and
simultaneously with evaluation of xt and yt members that might affect
the order in which Uniform01() is evaluated.

> 
> With the appended rnd.mod no difference occurs between x86-64 and armv7.

Thus, I think there is no bug in the model generation.


Best regards,

Andrew Makhorin

> 
> > Please conduct the following experiment: move the statement
> >
> > printf {t in T} "%d -> %d\n", t,  pt[t];
> 
> In this case I get the same results on both platforms but different to
> the original values. This is expected because we changed the sequence in
> which Uniform01() is called for the different parameters.
> 
> So the error must be in the code generating the constraints and the
> objective.
> 
> Best regards
> 
> Heinrich Schuchardt



___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk


Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Heinrich Schuchardt
On 08/06/2017 01:51 PM, Andrew Makhorin wrote:
> Hi Heinrich,
> 
>> the appended file test.mod is examples/threads/clustering.mod with
>> appended line
>>
>> printf {t in T} "%d -> %d\n", t,  pt[t];
>>
>> Essentially the line prints out part of the generated problem.
>>
>> The output on x86-64 ends with:
>>
>> 49 -> 608
>> 50 -> 334
>> Model has been successfully processed
>>
>> The output on ARMv7 ends with:
>>
>> 49 -> 852
>> 50 -> 472
>> Model has been successfully processed
>>
>> How can it be that the generated model differs depending on the CPU
>> architecture?
> 
> I think this is due to round-off errors, because you are using
> floating-point computations in your model.

The important thing is that I observed a difference for model parameters.

./glpsol --wlp test.lp -m test.mod --check

yields totally different files test.lp and different objective values.
So this is a problem in model generation.

If I take one of the lp files as input I get the same objective value on
both platforms. There is no problem in the solver.

Replacing Uniform01() by round(Uniform01(), 5) does not change the
output for parameter pt[50] on both platforms.

By rounding you cannot explain the difference between 334 and 472 of
model parameter pt[50]. This could only be explained by the sequence of
generation steps and hence Uniform01() values assigned to different
parameters on the different platforms.

This should be fixed.

With the appended rnd.mod no difference occurs between x86-64 and armv7.

> Please conduct the following experiment: move the statement
>
> printf {t in T} "%d -> %d\n", t,  pt[t];

In this case I get the same results on both platforms but different to
the original values. This is expected because we changed the sequence in
which Uniform01() is called for the different parameters.

So the error must be in the code generating the constraints and the
objective.

Best regards

Heinrich Schuchardt
i,r
1,0.1283118040300906
2,0.0095966751687229
3,0.0296868691220880
4,0.5537919262424111
5,0.8182639055885375
6,0.294472214580
7,0.4122264189645648
8,0.4117954890243709
9,0.9262405140325427
10,0.9006356885656714
11,0.2921296940185130
12,0.5396903096698225
13,0.0966075621545315
14,0.2887144996784627
15,0.2510403958149254
16,0.9628592282533646
17,0.4821618809364736
18,0.0251924195326865
19,0.7129793898202479
20,0.6491678943857551
21,0.3921313951723278
22,0.5375207834877074
23,0.3429719866253436
24,0.7938511283136904
25,0.2059222082607448
26,0.1402976275421679
27,0.8419359494000673
28,0.1841345182619989
29,0.2093450678512454
30,0.3467838228680193
31,0.8280209200456738
32,0.0841145943850279
33,0.5216898573562503
34,0.4337504184804857
35,0.3556738244369626
36,0.540540042049
37,0.6723811845295131
38,0.9386785053648055
39,0.4563398407772183
40,0.8116365587338805
41,0.9145371220074594
42,0.4956066468730569
43,0.1909179259091616
44,0.0471117007546127
45,0.3927211072295904
46,0.9989088969305158
47,0.2465867609716952
48,0.4570853183977306
49,0.8424617522396147
50,0.5246065454557538
51,0.9202133091166615
52,0.2170099485665560
53,0.5642138123512268
54,0.9994520368054509
55,0.7895979653112590
56,0.7396589284762740
57,0.6809262032620609
58,0.4587963344529271
59,0.1945359613746405
60,0.6356118666008115
61,0.5652556745335460
62,0.1927311550825834
63,0.4559926986694336
64,0.4141473318450153
65,0.4965721392072737
66,0.4902477958239615
67,0.8174141729250550
68,0.6797858248464763
69,0.7622624132782221
70,0.2064960440620780
71,0.0774631835520267
72,0.4682604474946856
73,0.8217154666781425
74,0.0617517735809088
75,0.6986637557856739
76,0.2881247876212001
77,0.7896522823721170
78,0.0592444539070129
79,0.8189276908524334
80,0.3886528755538166
81,0.3286704719066620
82,0.5708905346691608
83,0.3592559648677707
84,0.1826520389877260
85,0.6903037726879120
86,0.2194952638819814
87,0.9558027903549373
88,0.5120931821875274
89,0.4040635493583977
90,0.8018818981945515
91,0.7222761367447674
92,0.4168217373080552
93,0.5264520864002407
94,0.0445443517528474
95,0.8853960447013378
96,0.0139014334417880
97,0.2034769528545439
98,0.6512276162393391
99,0.9505041386000812
100,0.1040066075511277
101,0.7478685011155903
102,0.2837275327183306
103,0.9749234374612570
104,0.8172693327069283
105,0.8116271556355059
106,0.2710454147309065
107,0.8248785533942282
108,0.0266930288635194
109,0.6564800501801074
110,0.4773332644253969
111,0.3465599189512432
112,0.1021311134099960
113,0.4602874587289989
114,0.3720337622798979
115,0.695741044879
116,0.4721874981187284
117,0.7628338565118611
118,0.2398488367907703
119,0.5829803529195487
120,0.5513049243018031
121,0.8829018590040505
122,0.7307499027810991
123,0.8282197620719671
124,0.4285414819605649
125,0.6179443909786642
126,0.6062144706957042
127,0.9509311532601714
128,0.1084863096475601
129,0.2279383302666247
130,0.4279454420320690
131,0.9463805933482945
132,0.2482798253186047
133,0.8529801047407091
134,0.3122647008858621
135,0.3930990095250309
136,0.5787950898520648
137,0.9985088757239282

Re: [Bug-glpk] Different generated model on ARMv7 and x86-64

2017-08-06 Thread Andrew Makhorin
Hi Heinrich,

> the appended file test.mod is examples/threads/clustering.mod with
> appended line
> 
> printf {t in T} "%d -> %d\n", t,  pt[t];
> 
> Essentially the line prints out part of the generated problem.
> 
> The output on x86-64 ends with:
> 
> 49 -> 608
> 50 -> 334
> Model has been successfully processed
> 
> The output on ARMv7 ends with:
> 
> 49 -> 852
> 50 -> 472
> Model has been successfully processed
> 
> How can it be that the generated model differs depending on the CPU
> architecture?

I think this is due to round-off errors, because you are using
floating-point computations in your model.

Please conduct the following experiment: move the statement

printf {t in T} "%d -> %d\n", t,  pt[t];

immediately before 'minimize', i.e. make it the very first one.
And then compare the output for both platforms. 

BTW, does ARMv7 use the same floating-point representation (including
long double) as x86-64?

> 
> If I run
> printf {1..1} "%16.15f\n", Uniform01();
> I get the same result on both architectures:
> 
> 0.443241402972490
> Model has been successfully generated
> 
> So it is not a problem in the random number generation.
> 
> If I remove all variables and constraints from appended test.mod I also
> get the same result on both architectures.
> 

Best,

Andrew Makhorin


___
Bug-glpk mailing list
Bug-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/bug-glpk