User Tools

Site Tools


gams:parallel_versus_sequential_assignments_-_or_beware_of_loop_-statements

Parallel versus sequential assignments - or beware of "Loop"-Statements

Indexed assignments within GAMS are done using simultaneous or parallel assignments. In most cases you don’t need explicit loops, an assignment is an implicit loop. The loop statement is necessary when parallel assignments are not sufficient - an example is provide below. However, a loop statement is not executed in parallel, but sequentially. This may slow down the execution of your code tremendously. Below are some examples:

A simple example

set i / i1 * i100000 /;
parameter u(i);
* bad!
loop(i,
        u(i) = uniform(0,2);
     );
* good
u(i) = uniform(0,2);

If you run this fragment with the profile option set to one, you'll get something like:

----      4 Loop                    61.172    61.172 SECS     11 Mb 
----      8 Assignment u             0.031    61.203 SECS     11 Mb  100000

The execution of the loop statement was approximately 2000 times slower than the parallel assignment! Thus parallel assignments should be used wherever possible.

Note: The order in which a “parallel” assignment is executed is not defined. To force an order one must use a loop statement. Here is an example, which illustrates this:

set j      /j1*j4/
parameters a(j);
a('j1')=1;
* wrong!
a(j)$(ord(j)>1)=a(j-1)+1;
display 'Wrong:',a;
* correct!
loop(j$(ord(j)>1),  a(j)=a(j-1)+1;   );
display 'Correct:',a;
----      6 Wrong:
----      6 PARAMETER a  
j1 1.000,    j2 2.000,    j3 1.000,    j4 1.000

----      9 Correct:
----      9 PARAMETER a  
j1 1.000,    j2 2.000,    j3 3.000,    j4 4.000

Another example

Q: Let's define three sets, stores, products, and weeks. How does the following iteration work exactly?

found =0;
 loop((stores, products, weeks) $ (condition1(weeks)
                                   and condition2(stores)
                                   and condition3(products)),
       found =1;
     );

Assuming that we have 6000 stores, 20 products, and 100 weeks. And only one week, week1, satisfies condition1; only one store, store1, satisfies condition2; only one product, product1, satisfies condition3. Will the iteration go through ALL the stores, products, and weeks even though only one element satisfies all the conditions. Given the conditional control, will the dimensions of the sets have a big impact on run time?

GAMS tries to be efficient when it comes to restricting the domains it needs to search. There is some optimization in place, but with a general construct as you have it there, GAMS will go through all the tuples of the loop. You have a better chance when you do:

set w(weeks), s(stores), p(products);
w(weeks) = condition1(weeks);
s(stores) = condition2(stores);
p(products) = condition3(products);
found = sum((w,s,p), 1); // or card(w)*card(s)*card(p)

Even if GAMS can't be smart about the individual conditions, it only walks them once (card(weeks)+card(stores)+card(products) in the original loop you probably get * instead of +). If the conditions are simple and can be optimized by the GAMS compiler you get constant time. It is a little like code optimization in other language compilers (C, Fortran, etc).

A third example

Here we have an example, where we have to match elements from two different sets. We show different formulation, which are much faster than using a loop statement.

$eolcom //
set k /k1*k9000/;
set t /t1*t1000/;

parameter a(k), b(t);

a(k)=normal(0,1);

// expansive loop
loop(k,
    b(t)$(ord(t) eq ord(k)-card(t))=a(k);
    );
option clear=b;

// better, but not yet optimal
b(t) = sum(k$(ord(k)=ord(t)), a(k+card(t)));
option clear=b;

// much faster using element matching introduced in distribution 227
$version 227
set sk(k) 'shifted k',
    kt(k,t);
sk(k+card(t)) =  yes;
option kt(sk:t); // or  set kt(k,t) / #k:#t /
b(t)=sum(k$kt(k,t),a(k));
option clear=b, clear=kt;

// this formulation is more compact
option kt(k:t);
b(t)=sum(kt(k,t), a(k+card(t)));

Running the code using the GAMS profiler (profile 1) yields:

----      1 ExecInit                 0.000     0.000 SECS      3 Mb 
----      7 Assignment a             0.000     0.000 SECS      5 Mb   9000
----     10 Loop                     1.388     1.388 SECS      5 Mb 
----     13 Clear      b             0.000     1.388 SECS      5 Mb 
----     16 Assignment b             0.796     2.184 SECS      5 Mb   1000
----     17 Clear      b             0.000     2.184 SECS      5 Mb 
----     23 Assignment sk            0.000     2.184 SECS      5 Mb   8000
----     24 Other                    0.000     2.184 SECS      5 Mb 
----     25 Assignment b             0.000     2.184 SECS      5 Mb   1000
----     26 Clear      kt            0.000     2.184 SECS      5 Mb 
----     29 Other                    0.000     2.184 SECS      5 Mb 
----     30 Assignment b             0.015     2.199 SECS      5 Mb   1000
gams/parallel_versus_sequential_assignments_-_or_beware_of_loop_-statements.txt · Last modified: 2009/05/08 13:45 by support