Assignment 3 – sorting networks

 

submission by:

Benbassat Amit       ID - 035967272

Chin Merhavi Liat   ID – 031872500

(Source files)

 

Important Note:

In the exercise we where asked to implement Sorting Networks according to Kosa's paper.

 

For checking fitness, we need to run 2^32 cases. Data set of 65000 for each generation takes minimum ~ 22 minutes, which mean around 3 generation in one hour.

Kosa used 1000 generations. Simple calculation shows that we need minimum 333 hours to run 1000 generation on such data set.(We restricted the tree depth to 5)

 

We choose to decrease the data set, generation number and number of generation as describe below.

 

1. The best fitness for 100 generations:.

 

 

The Genetic algorithm was design according to Kosa's document with changes of parameter as followed:

  Generation size = 500 trees with start depth of 5. –

Data set for fitness purpose was 6000 random numbers.   –

-   Number generation was 100.

-   With all that the algorithm was running for 13 hours.

 

The best fitness was starting from 3550 (50 % from the dataset was hits) and ended with 22.4, whice means that all 6000 data set was fully sorted  and for each "compare_exchange" operation , the fitness increase in 0.1 which mean 0.1*224 = 22.4.

 

With decreasing of all this parameters still the algorithm was run for about 13 hours.

 

2.The sorting tree (phenotype) is as followed:

 

 

************* The phenotype*********************

PROGN4

     PROGN4

          PROGN3

               NOOP

              

               NOOP

              

               PROGN2

                    COMPARE_EXCHANGE

                         13

                        

                         12

                        

                   

                    PROGN3

                         PROGN3

                              PROGN3

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             10

                                            

                                             7

                                            

                                       

                                        COMPARE_EXCHANGE

                                             6

                                            

                                             2

                                            

                                       

                                  

                                   COMPARE_EXCHANGE

                                        10

                                       

                                        1

                                       

                                  

                                   PROGN4

                                        COMPARE_EXCHANGE

                                             8

                                            

                                             1

                                            

                                       

                                        COMPARE_EXCHANGE

                                             9

                                            

                                             8

                                            

                                       

                                        COMPARE_EXCHANGE

                                             14

                                             

                                             2

                                            

                                       

                                        COMPARE_EXCHANGE

                                             7

                                            

                                             0

                                            

                                       

                                  

                              

                              PROGN3

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             12

                                            

                                             0

                                            

                                       

                                        COMPARE_EXCHANGE

                                             7

                                             

                                             1

                                            

                                       

                                  

                                   PROGN4

                                        COMPARE_EXCHANGE

                                             15

                                            

                                             5

                                            

                                       

                                        COMPARE_EXCHANGE

                                             10

                                            

                                             0

                                            

                                        

                                        COMPARE_EXCHANGE

                                             5

                                            

                                             4

                                             

                                       

                                        COMPARE_EXCHANGE

                                             14

                                            

                                             4

                                             

                                       

                                  

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             9

                                            

                                             1

                                            

                                       

                                        COMPARE_EXCHANGE

                                             1

                                            

                                             0

                                            

                                

                                  

                              

                              PROGN2

                                   NOOP

                                  

                                   NOOP

                                  

                             

                         

                         COMPARE_EXCHANGE

                              4

                             

                              3

                             

                        

                         PROGN4

                              PROGN2

                                   PROGN4

                                        COMPARE_EXCHANGE

                                             13

                                            

                                             8

                                             

                                       

                                        COMPARE_EXCHANGE

                                             8

                                            

                                             5

                                            

                                       

                                        COMPARE_EXCHANGE

                                             15

                                             

                                             14

                                            

                                       

                                        COMPARE_EXCHANGE

                                             6

                                             

                                             5

                                            

                                       

                                  

                                   PROGN4

                                        COMPARE_EXCHANGE

                                             12

                                            

                                             2

                                            

                                        

                                        COMPARE_EXCHANGE

                                             11

                                            

                                             0

                                             

                                       

                                        COMPARE_EXCHANGE

                                             10

                                            

                                             5

                                             

                                       

                                        COMPARE_EXCHANGE

                                             11

                                            

                                             7

                                            

                                       

                                  

                             

                              COMPARE_EXCHANGE

                                   4

                                  

                                   2

                                  

                             

                              PROGN3

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             5

                                            

                                             3

                                            

                                       

                                        COMPARE_EXCHANGE

                                             8

                                            

                                             0

                                            

                                        

                                  

                                   NOOP

                                  

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             12

                                            

                                             9

                                            

                                       

                                        COMPARE_EXCHANGE

                                             11

                                            

                                             8

                                            

                                       

                                   

                             

                              PROGN3

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             6

                                             

                                             3

                                            

                                       

                                        COMPARE_EXCHANGE

                                             12

                                             

                                             4

                                            

                                       

                                  

                                   COMPARE_EXCHANGE

                                        13

                                       

                                        10

                                       

                                  

                                   NOOP

                                  

                             

                        

                   

              

         

          PROGN4

               PROGN4

                    NOOP

                   

                    COMPARE_EXCHANGE

                         15

                        

                         14

                        

                   

                    COMPARE_EXCHANGE

                         14

                        

                         4

                        

                   

                    COMPARE_EXCHANGE

                         11

                        

                         8

                        

                   

              

               PROGN3

                    COMPARE_EXCHANGE

                         10

                        

                         4

                        

                   

                    COMPARE_EXCHANGE

                         12

                        

                         8

                        

                   

                    COMPARE_EXCHANGE

                         14

                        

                         10

                        

                   

              

               COMPARE_EXCHANGE

                    8

                   

                    1

                   

              

               PROGN3

                    COMPARE_EXCHANGE

                         9

                        

                         0

                        

                   

                    COMPARE_EXCHANGE

                         8

                        

                         2

                        

                   

                    COMPARE_EXCHANGE

                         11

                        

                         6

                        

                   

              

         

          PROGN4

               PROGN3

                    COMPARE_EXCHANGE

                         1

                        

                         0

                        

                   

                    COMPARE_EXCHANGE

                         8

                        

                         7

                        

                    

                    COMPARE_EXCHANGE

                         11

                        

                         4

                        

                   

              

               PROGN3

                    COMPARE_EXCHANGE

                         12

                        

                         3

                        

                   

                    COMPARE_EXCHANGE

                         14

                        

                         9

                         

                   

                    COMPARE_EXCHANGE

                         13

                        

                         4

                        

                   

              

               PROGN3

                    COMPARE_EXCHANGE

                         10

                        

                         8

                        

                   

                    PROGN2

                         PROGN2

                              COMPARE_EXCHANGE

                                   15

                                  

                                   9

                                  

                             

                              COMPARE_EXCHANGE

                                   4

                                  

                                   3

                                  

                             

                        

                         PROGN2

                              COMPARE_EXCHANGE

                                   7

                                  

                                   4

                                  

                             

                              COMPARE_EXCHANGE

                                   11

                                  

                                   7

                                  

                             

                        

                   

                    COMPARE_EXCHANGE

                         9

                         

                         8

                        

                   

              

               NOOP

              

         

          PROGN3

               PROGN2

                    COMPARE_EXCHANGE

                         10

                        

                         3

                        

                   

                    COMPARE_EXCHANGE

                         5

                        

                         3

                        

                    

              

               PROGN3

                    COMPARE_EXCHANGE

                         8

                        

                         4

                        

                   

                    COMPARE_EXCHANGE

                         10

                        

                         5

                        

                   

                    COMPARE_EXCHANGE

                         6

                        

                         5

                         

                   

              

               PROGN3

                    COMPARE_EXCHANGE

                         2

                        

                         1

                        

                   

                    COMPARE_EXCHANGE

                         15

                        

                         12

                        

                   

                    COMPARE_EXCHANGE

                         7

                        

                         2

                        

                   

              

         

    

     PROGN2

          NOOP

         

          PROGN2

               PROGN4

                    COMPARE_EXCHANGE

                         3

                        

                         1

                        

                   

                    COMPARE_EXCHANGE

                         9

                        

                         6

                        

                   

                    COMPARE_EXCHANGE

                         10

                        

                         1

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         3

                        

                   

              

               PROGN4

                    COMPARE_EXCHANGE

                         15

                        

                         14

                        

                   

                    COMPARE_EXCHANGE

                         10

                        

                         7

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         8

                        

                   

                    COMPARE_EXCHANGE

                         14

                        

                         4

                        

                   

              

         

    

     PROGN4

          PROGN2

               PROGN3

                    COMPARE_EXCHANGE

                         5

                        

                         0

                        

                   

                    COMPARE_EXCHANGE

                         3

                        

                         1

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         3

                        

                   

              

               PROGN4

                    PROGN3

                         COMPARE_EXCHANGE

                              1

                             

                              0

                              

                        

                         COMPARE_EXCHANGE

                              8

                             

                              7

                             

                        

                         COMPARE_EXCHANGE

                              11

                             

                              4

                             

                        

                   

                    PROGN3

                         COMPARE_EXCHANGE

                              12

                             

                              3

                             

                        

                         COMPARE_EXCHANGE

                              14

                              

                              9

                             

                        

                         COMPARE_EXCHANGE

                              13

                             

                              4

                              

                        

                   

                    PROGN3

                         COMPARE_EXCHANGE

                              10

                             

                              8

                              

                        

                         COMPARE_EXCHANGE

                              14

                             

                              13

                             

                        

                         COMPARE_EXCHANGE

                              9

                             

                              8

                             

                        

                   

                    NOOP

                   

              

          

          PROGN3

               PROGN3

                    COMPARE_EXCHANGE

                         3

                        

                         0

                        

                   

                    COMPARE_EXCHANGE

                         15

                        

                         10

                        

                   

                    COMPARE_EXCHANGE

                         15

                        

                         2

                         

                   

              

               COMPARE_EXCHANGE

                    13

                   

                    1

                   

              

               PROGN4

                    COMPARE_EXCHANGE

                         12

                        

                         6

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         9

                        

                   

                    COMPARE_EXCHANGE

                         6

                        

                         2

                        

                   

                    COMPARE_EXCHANGE

                         9

                         

                         6

                        

                   

              

         

          PROGN4

               PROGN3

                    COMPARE_EXCHANGE

                         12

                        

                         9

                        

                   

                    COMPARE_EXCHANGE

                         11

                        

                         5

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         7

                        

                   

              

               PROGN3

                    COMPARE_EXCHANGE

                         14

                         

                         5

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         0

                        

                   

                    COMPARE_EXCHANGE

                         9

                        

                         4

                        

                   

              

               NOOP

              

               PROGN2

                    COMPARE_EXCHANGE

                         10

                        

                         9

                        

                   

                    COMPARE_EXCHANGE

             

         

                        COMPARE_EXCHANGE

                                   13

                                  

                                   7

                                  

                             

                              NOOP

                             

                         

                         PROGN4

                              PROGN3

                                   COMPARE_EXCHANGE

                                        3

                                       

                                        0

                                        

                                  

                                   COMPARE_EXCHANGE

                                        11

                                       

                                        8

                                        

                                  

                                   COMPARE_EXCHANGE

                                        8

                                       

                                        4

                                        

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        10

                                        

                                        8

                                       

                                  

                                   COMPARE_EXCHANGE

                                        12

                                        

                                        7

                                       

                                  

                                   COMPARE_EXCHANGE

                                        14

                                        

                                        1

                                       

                                  

                             

     PROGN4

          PROGN3

               PROGN4

                    PROGN4

                         NOOP

                        

                         PROGN4

                              NOOP

                             

                              COMPARE_EXCHANGE

                                   12

                                   

                                   7

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        13

                                        

                                        4

                                       

                                  

                                   COMPARE_EXCHANGE

                                        7

                                        

                                        6

                                       

                                  

                                   COMPARE_EXCHANGE

                                        4

                                        

                                        3

                                       

                                  

                             

                              NOOP

                             

                         

                         PROGN4

                              PROGN3

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        7

                                       

                                  

                                   COMPARE_EXCHANGE

                                        10

                                       

                                        7

                                       

                                  

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        13

                                       

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        10

                                        

                                        5

                                       

                                  

                                   COMPARE_EXCHANGE

                                        4

                                        

                                        0

                                       

                                  

                                   COMPARE_EXCHANGE

                                        9

                                        

                                        4

                                       

                                  

                             

                              COMPARE_EXCHANGE

                                   10

                                  

                                   9

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        1

                                       

                                  

                                   COMPARE_EXCHANGE

                                        6

                                       

                                        0

                                       

                                  

                                   COMPARE_EXCHANGE

                                        11

                                       

                                        1

                                       

                                  

                             

                        

                         PROGN4

                              NOOP

                             

                              PROGN4

                                   COMPARE_EXCHANGE

                                        13

                                       

                                        8

                                       

                                  

                                   COMPARE_EXCHANGE

                                        10

                                       

                                        1

                                       

                                  

                                   COMPARE_EXCHANGE

                                        5

                                       

                                        3

                                       

                                  

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        8

                                       

                                  

                             

                              PROGN2

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        10

                                       

                                  

                                   COMPARE_EXCHANGE

                                        12

                                       

                                        11

                                       

                                  

                             

                              PROGN2

                                   COMPARE_EXCHANGE

                                        11

                                       

                                        2

                                       

                                  

                                   COMPARE_EXCHANGE

                                        5

                                       

                                        4

                                       

                                  

                              

                        

                   

                    PROGN2

                         NOOP

                        

                         PROGN2

                              COMPARE_EXCHANGE

                                   10

                                  

                                   6

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        10

                                       

                                        3

                                       

                                  

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        7

                                       

                                  

                                   COMPARE_EXCHANGE

                                        13

                                       

                                        3

                                       

                                  

                             

                        

                    

                    PROGN3

                         COMPARE_EXCHANGE

                              13

                             

                              11

                             

                        

                         PROGN2

                              COMPARE_EXCHANGE

                                   1

                                  

                                   0

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        11

                                       

                                        7

                                       

                                   

                                   COMPARE_EXCHANGE

                                        12

                                       

                                        1

                                       

                                   

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        4

                                       

                                   

                             

                        

                         PROGN4

                              PROGN2

                                   COMPARE_EXCHANGE

                                        11

                                        

                                        9

                                       

                                  

                                   COMPARE_EXCHANGE

                                        10

                                        

                                        8

                                       

                                  

                             

                              COMPARE_EXCHANGE

                                   10

                                   

                                   4

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        2

                                       

                                        1

                                       

                                  

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        14

                                       

                                  

                                   COMPARE_EXCHANGE

                                        7

                                       

                                        4

                                       

                                  

                             

                              PROGN2

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        3

                                       

                                  

                                   COMPARE_EXCHANGE

                                        11

                                       

                                        8

                                       

                                  

                             

                        

                   

                    PROGN4

                         PROGN3

                              PROGN3

                                   COMPARE_EXCHANGE

                                        12

                                        

                                        6

                                       

                                  

                                   COMPARE_EXCHANGE

                                        8

                                        

                                        1

                                       

                                  

                                   COMPARE_EXCHANGE

                                        9

                                        

                                        0

                                       

                                  

                             

                              COMPARE_EXCHANGE

                                   8

                                   

                                   2

                                  

                             

                              NOOP

                             

                        

                         PROGN3

                              PROGN4

                                   COMPARE_EXCHANGE

                                        12

                                       

                                        8

                                        

                                  

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        5

                                        

                                  

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        4

                                        

                                  

                                   COMPARE_EXCHANGE

                                        11

                                       

                                        5

                                        

                                  

                             

                              PROGN4

                                   COMPARE_EXCHANGE

                                        8

                                       

                                        7

                                       

                                  

                                   COMPARE_EXCHANGE

                                        4

                                       

                                        2

                                       

                                  

                                   COMPARE_EXCHANGE

                                        9

                                       

                                        1

                                       

                                  

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        12

                                       

                                  

                             

                              PROGN2

                                   COMPARE_EXCHANGE

                                        9

                                       

                                        6

                                       

                                  

                                   COMPARE_EXCHANGE

                                        5

                                       

                                        1

                                       

                                  

                             

                        

                         PROGN3

                              COMPARE_EXCHANGE

                                   6

                                  

                                   1

                                  

                             

                              PROGN4

                                   COMPARE_EXCHANGE

                                        12

                                       

                                        10

                                       

                                   

                                   COMPARE_EXCHANGE

                                        5

                                       

                                        2

                                       

                                   

                                   COMPARE_EXCHANGE

                                        14

                                       

                                        10

                                       

                                   

                                   COMPARE_EXCHANGE

                                        8

                                       

                                        5

                                       

                                   

                             

                              PROGN2

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        9

                                        

                                  

                                   COMPARE_EXCHANGE

                                        13

                                       

                                        1

                                        

                                  

                             

                        

                         PROGN2

                              PROGN3

                                   COMPARE_EXCHANGE

                                        3

                                       

                                        2

                                       

                                  

                                   COMPARE_EXCHANGE

                                        2

                                       

                                        0

                                       

                                  

                                   COMPARE_EXCHANGE

                                        15

                                       

                                        0

                                       

                                  

                             

                              PROGN3

                                   COMPARE_EXCHANGE

                                        6

                                       

                                        2

                                       

                                  

                                   COMPARE_EXCHANGE

                                        10

                                       

                                        2

                                       

                                  

                                   COMPARE_EXCHANGE

                                        7

                                       

                                        1

                                       

                                  

                              

                        

                   

              

               PROGN4

                    COMPARE_EXCHANGE

                         13

                        

                         10

                         

                   

                    COMPARE_EXCHANGE

                         14

                        

                         8

                        

                   

                    COMPARE_EXCHANGE

                         15

                         

                         5

                        

                   

                    COMPARE_EXCHANGE

                         3

                        

                         2

                        

                    

              

               PROGN4

                    COMPARE_EXCHANGE

                         5

                        

                         4

                        

                   

                    COMPARE_EXCHANGE

                         13

                        

                         6

                        

                   

                    COMPARE_EXCHANGE

                         14

                        

                         12

                         

                   

                    COMPARE_EXCHANGE

                         9

                        

                         5

                        

                   

              

         

          PROGN2

               PROGN2

                    COMPARE_EXCHANGE

                         15

                        

                         9

                        

                   

                    COMPARE_EXCHANGE

                         4

                        

                         3

                        

                   

              

               PROGN2

                    COMPARE_EXCHANGE

                         7

                        

                         4

                        

                    

                    COMPARE_EXCHANGE

                         11

                        

                         7

                        

                   

              

         

          PROGN2

               PROGN4

                    PROGN4

                         PROGN4

                              PROGN3

                                   NOOP

                                  

                                   NOOP

                                  

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             13

                                            

                                             12

                                             

                                       

                                        COMPARE_EXCHANGE

                                             15

                                            

                                             0

                                            

                                       

                                  

                             

                              PROGN4

                                   PROGN4

                                        COMPARE_EXCHANGE

                                             13

                                            

                                             11

                                            

                                        

                                        COMPARE_EXCHANGE

                                             15

                                            

                                             14

                                            

                                        

                                        COMPARE_EXCHANGE

                                             14

                                            

                                             4

                                             

                                       

                                        COMPARE_EXCHANGE

                                             11

                                            

                                             8

                                            

                                       

                                  

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             10

                                            

                                             4

                                            

                                       

                                        COMPARE_EXCHANGE

                                             12

                                            

                                             8

                                            

                                       

                                        COMPARE_EXCHANGE

                                             14

                                            

                                             10

                                            

                                        

                                  

                                   COMPARE_EXCHANGE

                                        8

                                       

                                        1

                                        

                                  

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             9

                                            

                                             0

                                            

                                       

                                        COMPARE_EXCHANGE

                                             8

                                             

                                             2

                                            

                                       

                                        COMPARE_EXCHANGE

                                             11

                                             

                                             6

                                            

                                       

                                  

                             

                              PROGN4

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             1

                                            

                                             0

                                             

                                       

                                        COMPARE_EXCHANGE

                                             8

                                            

                                             7

                                            

                                       

                                        COMPARE_EXCHANGE

                                             11

                                             

                                             4

                                            

                                       

                                  

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             12

                                            

                                             3

                                            

                                       

                                        COMPARE_EXCHANGE

                                             14

                                            

                                             9

                                            

                                        

                                        COMPARE_EXCHANGE

                                             13

                                            

                                             4

                                             

                                       

                                  

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             10

                                             

                                             8

                                            

                                       

                                        COMPARE_EXCHANGE

                                             14

                                            

                                             13

                                            

                                       

                                        COMPARE_EXCHANGE

                                             9

                                            

                                             8

                                            

                                       

                                  

                                   NOOP

                                  

                             

                              PROGN3

                                   PROGN2

                                        COMPARE_EXCHANGE

                                             10

                                            

                                             3

                                            

                                       

                                        COMPARE_EXCHANGE

                                             5

                                            

                                             3

                                            

                                       

                                   

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             8

                                            

                                             4

                                            

                                       

                                        COMPARE_EXCHANGE

                                             10

                                            

                                             5

                                            

                                       

                                        COMPARE_EXCHANGE

                                             6

                                             

                                             5

                                            

                                       

                                  

                                   PROGN3

                                        COMPARE_EXCHANGE

                                             2

                                            

                                             1

                                            

                                       

                                        COMPARE_EXCHANGE

                                             15

                                            

                                             12

                                            

                                        

                                        COMPARE_EXCHANGE

                                             7

                                            

                                             2

                                             

                                       

                                  

                             

                        

                         COMPARE_EXCHANGE

                              10

                             

                              7

                             

                        

                         COMPARE_EXCHANGE

                              13

                             

                              8

                             

                         

                         COMPARE_EXCHANGE

                              10

                             

                              9

                             

                        

                   

                    COMPARE_EXCHANGE

                         11

                        

                         10

                        

                   

                    COMPARE_EXCHANGE

                         6

                        

                         1

                        

                   

                    COMPARE_EXCHANGE

                         10

                        

                         0

                        

                   

              

               NOOP

              

         

          NOOP

         

    

 

3. The numbers of compare exchange was 224 far from Kosa in about 164 extra compare exchange operations. Also the tree was test for only 6000 random cases and it is not tested for all ~64000 cases.

The outcome is better than bubble sort (16 * 15 = 240) but far from the 60 compare_exchange operations that Kosa found.

The reason for that is that we were limited with time and/ Or we don’t have powerful computer(s), and because of that we choose to decrease the value of the runtime as was described before.