Changeset 623 for trunk/user/sort


Ignore:
Timestamp:
Mar 6, 2019, 4:37:15 PM (6 years ago)
Author:
alain
Message:

Introduce three new types of vsegs (KCODE,KDATA,KDEV)
to map the kernel vsegs in the process VSL and GPT.
This now used by both the TSAR and the I86 architectures.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/user/sort/sort.c

    r619 r623  
    2929#include <hal_macros.h>
    3030
    31 #define ARRAY_LENGTH        256        // number of values
     31#define ARRAY_LENGTH        1024       // number of items
    3232#define MAX_THREADS         1024       // 16 * 16 * 4
    33 #define USE_DQT_BARRIER     1
    34 #define DISPLAY_ARRAY       0
    35 #define INTERACTIVE_MODE    0
     33
     34#define USE_DQT_BARRIER     1          // use DQT barrier if non zero
     35#define DISPLAY_ARRAY       0          // display items values before and after
     36#define VERBOSE             0          // for debug
     37#define INTERACTIVE_MODE    0          // for debug
     38#define CHECK_RESULT        0          // for debug
     39#define INSTRUMENTATION     1          // register computation times on file
    3640
    3741/////////////////////////////////////////////////////////////
    … …  
    8488
    8589///////////////////////////////////
    86 static void merge( const int * src,
    87                    int       * dst,
    88                    int         length,
    89                    int         init_pos_src_a,
    90                    int         init_pos_src_b,
    91                    int         init_pos_dst )
     90static void merge( const int * src,               // source array
     91                   int       * dst,               // destination array
     92                   int         length,            // number of items in a subset
     93                   int         init_pos_src_a,    // index first item in src subset A
     94                   int         init_pos_src_b,    // index first item in src subset B
     95                   int         init_pos_dst )     // index first item in destination
    9296{
    9397    int i;
    … …  
    135139    unsigned int       lid;
    136140
    137     int         * src_array  = NULL;
    138     int         * dst_array  = NULL;
     141    int              * src_array  = NULL;
     142    int              * dst_array  = NULL;
    139143
    140144    // get core coordinates an date
    … …  
    146150    unsigned int  main_uid   = ptr->main_uid;
    147151
     152#if DISPLAY_ARRAY
     153unsigned int n;
     154if( thread_uid == main_uid )
     155{
     156    printf("\n*** array before sort\n");
     157    for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , array0[n] );
     158}
     159#endif
     160
     161    /////////////////////////////////
     162    pthread_barrier_wait( &barrier );
     163
     164#if VERBOSE
     165printf("\n[sort] thread[%d] exit barrier 0\n", thread_uid );
     166#endif
     167
    148168    unsigned int  items      = ARRAY_LENGTH / threads;
    149169    unsigned int  stages     = __builtin_ctz( threads ) + 1;
    150170
    151     printf("\n[SORT] thread[%d] : start\n", thread_uid );
     171#if VERBOSE
     172printf("\n[sort] thread[%d] : start\n", thread_uid );
     173#endif
    152174
    153175    bubbleSort( array0, items, items * thread_uid );
    154176
    155     printf("\n[SORT] thread[%d] : stage 0 completed\n", thread_uid );
     177#if VERBOSE
     178printf("\n[sort] thread[%d] : stage 0 completed\n", thread_uid );
     179#endif
    156180
    157181    /////////////////////////////////
    158182    pthread_barrier_wait( &barrier );
    159     printf("\n[SORT] thread[%d] exit barrier 0\n", thread_uid );
    160 
    161     // the number of threads contributing to sort
    162     // is divided by 2 at each next stage
     183
     184#if VERBOSE
     185printf("\n[sort] thread[%d] exit barrier 0\n", thread_uid );
     186#endif
     187
     188#if DISPLAY_ARRAY
     189if( thread_uid == main_uid )
     190{
     191    printf("\n*** array after bubble sort\n");
     192    for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , array0[n] );
     193}
     194#endif
     195
     196    // the number of threads contributing to sort is divided by 2
     197    // and the number of items is multiplied by 2 at each next stage
    163198    for ( i = 1 ; i < stages ; i++ )
    164199    {
    165         pthread_barrier_wait( &barrier );
     200        if((i % 2) == 1)               // odd stage
     201        {
     202            src_array = array0;
     203            dst_array = array1;
     204        }
     205        else                           // even stage
     206        {
     207            src_array = array1;
     208            dst_array = array0;
     209        }
    166210
    167211        if( (thread_uid & ((1<<i)-1)) == 0 )
    168212        {
    169             printf("\n[SORT] thread[%d] : stage %d start\n", thread_uid , i );
    170 
    171             if((i % 2) == 1)               // odd stage
    172             {
    173                 src_array = array0;
    174                 dst_array = array1;
    175             }
    176             else                           // even stage
    177             {
    178                 src_array = array1;
    179                 dst_array = array0;
    180             }
    181 
     213
     214#if VERBOSE
     215printf("\n[sort] thread[%d] : stage %d start\n", thread_uid , i );
     216#endif
    182217            merge( src_array,
    183218                   dst_array,
    184                    items << i,
     219                   items << (i-1),
    185220                   items * thread_uid,
    186221                   items * (thread_uid + (1 << (i-1))),
    187222                   items * thread_uid );
    188223
    189             printf("\n[SORT] thread[%d] : stage %d completed\n", thread_uid , i );
     224#if VERBOSE
     225printf("\n[sort] thread[%d] : stage %d completed\n", thread_uid , i );
     226#endif
    190227        }
    191228
    192229        /////////////////////////////////
    193230        pthread_barrier_wait( &barrier );
    194         printf("\n[SORT] thread[%d] exit barrier %d\n", thread_uid , i );
    195 
    196     }
     231
     232#if VERBOSE
     233printf("\n[sort] thread[%d] exit barrier %d\n", thread_uid , i );
     234#endif
     235
     236#if DISPLAY_ARRAY
     237if( thread_uid == main_uid )
     238{
     239    printf("\n*** array after merge %d\n", i );
     240    for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , dst_array[n] );
     241}
     242#endif
     243
     244    }  // en for stages
    197245
    198246    // all threads but the main thread exit
    … …  
    220268    unsigned int           lid;                // core local index for a thread
    221269    unsigned int           n;                  // index in array to sort
    222     unsigned long long     cycle;              // current date for log
    223270    pthread_t              trdid;              // kernel allocated thread index (unused)
    224271    pthread_barrierattr_t  barrier_attr;       // barrier attributes
    225272
     273    unsigned long long     start_cycle;
     274    unsigned long long     seq_end_cycle;
     275    unsigned long long     para_end_cycle;
     276
     277    /////////////////////////
     278    get_cycle( &start_cycle );
     279 
    226280    // compute number of threads (one thread per core)
    227281    get_config( &x_size , &y_size , &ncores );
    … …  
    240294         (total_threads != 512) && (total_threads != 1024) )
    241295    {
    242         printf("\n[SORT ERROR] number of cores must be power of 2\n");
     296        printf("\n[sort error] number of cores must be power of 2\n");
    243297        exit( 0 );
    244298    }
    … …  
    247301    if ( ARRAY_LENGTH % total_threads)
    248302    {
    249         printf("\n[SORT ERROR] array size must be multiple of number of threads\n");
     303        printf("\n[sort error] array size must be multiple of number of threads\n");
    250304        exit( 0 );
    251305    }
    252306
    253     printf("\n\n[SORT] main starts on core[%x,%d] / %d threads / %d values / PID %x\n",
    254     main_cxy, main_lid, total_threads, ARRAY_LENGTH, getpid() );
     307    printf("\n\n[sort] main starts / %d threads / %d items / pid %x / cycle %d\n",
     308    total_threads, ARRAY_LENGTH, getpid(), (unsigned int)start_cycle );
    255309
    256310    // initialize barrier
    … …  
    269323    if( error )
    270324    {
    271         printf("\n[SORT ERROR] cannot initialise barrier\n" );
     325        printf("\n[sort error] cannot initialise barrier\n" );
    272326        exit( 0 );
    273327    }
    274328
    275     printf("\n[SORT] main completes barrier init\n");
     329#if VERBOSE
     330printf("\n[sort] main completes barrier init\n");
     331#endif
    276332
    277333    // Array to sort initialization
    … …  
    281337    }
    282338
    283 #if DISPLAY_ARRAY
    284 printf("\n*** array before sort\n");
    285 for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , array0[n] );
    286 #endif
    287 
    288     printf("\n[SORT] main completes array init\n");
     339#if VERBOSE
     340printf("\n[sort] main completes array init\n");
     341#endif
    289342
    290343    // launch other threads to execute sort() function
    … …  
    317370                                         &arg[thread_uid] ) ) // sort arguments
    318371                    {
    319                         printf("\n[SORT ERROR] main cannot create thread %x \n", thread_uid );
     372                        printf("\n[sort error] main cannot create thread %x \n", thread_uid );
    320373                        exit( 0 );
    321374                    }
    322375                    else
    323376                    {
    324                         printf("\n[SORT] main created thread %x \n", thread_uid );
     377#if VERBOSE
     378printf("\n[sort] main created thread %x \n", thread_uid );
     379#endif
    325380                    }
    326381                }
    … …  
    329384    }
    330385   
    331     get_cycle( &cycle );
    332     printf("\n[SORT] main completes threads create at cycle %d\n", (unsigned int)cycle );
     386    ///////////////////////////
     387    get_cycle( &seq_end_cycle );
     388
     389#if VERBOSE
     390printf("\n[sort] main completes sequencial init at cycle %d\n",
     391(unsigned int)seq_end_cycle );
     392#endif
    333393
    334394#if INTERACTIVE_MODE
    … …  
    339399    sort( &arg[main_uid] );
    340400
     401    ////////////////////////////
     402    get_cycle( &para_end_cycle );
     403
     404    printf("\n[sort] main completes parallel sort at cycle %d\n",
     405    (unsigned int)para_end_cycle );
     406
     407    // destroy barrier
     408    pthread_barrier_destroy( &barrier );
     409
    341410#if INTERACTIVE_MODE
    342411idbg();
    343412#endif
    344413
    345     // destroy barrier
    346     pthread_barrier_destroy( &barrier );
    347 
    348 #if INTERACTIVE_MODE
    349 idbg();
    350 #endif
    351 
    352     // Check result
    353     int    success = 1;
    354     int*   res_array = ( (total_threads ==   2) ||
    355                          (total_threads ==   8) ||
    356                          (total_threads ==  32) ||
    357                          (total_threads == 128) ||
    358                          (total_threads == 512) ) ? array1 : array0;
    359    
    360     for( n=0 ; n<(ARRAY_LENGTH-2) ; n++ )
    361     {
    362         if ( res_array[n] > res_array[n+1] )
    363         {
    364             printf("\n[SORT] array[%d] = %d > array[%d] = %d\n",
    365             n , res_array[n] , n+1 , res_array[n+1] );
    366             success = 0;
    367             break;
    368         }
    369     }
    370 
    371 #if DISPLAY_ARRAY
    372 printf("\n*** array after sort\n");
    373 for( n=0; n<ARRAY_LENGTH; n++) printf("array[%d] = %d\n", n , res_array[n] );
    374 #endif
    375 
    376     get_cycle( &cycle );
    377 
    378     if ( success )
    379     {
    380         printf("\n[SORT] success at cycle %d\n", (unsigned int)cycle );
    381     }
    382     else
    383     {
    384         printf("\n[SORT] failure at cycle %d\n", (unsigned int)cycle );
    385     }
    386 
    387 #if INTERACTIVE_MODE
    388 idbg();
     414#if CHECK_RESULT   
     415int    success = 1;
     416int*   res_array = ( (total_threads ==   2) ||
     417                     (total_threads ==   8) ||
     418                     (total_threads ==  32) ||
     419                     (total_threads == 128) ||
     420                     (total_threads == 512) ) ? array1 : array0;
     421
     422for( n=0 ; n<(ARRAY_LENGTH-2) ; n++ )
     423{
     424    if ( res_array[n] > res_array[n+1] )
     425    {
     426        printf("\n[sort] array[%d] = %d > array[%d] = %d\n",
     427        n , res_array[n] , n+1 , res_array[n+1] );
     428        success = 0;
     429        break;
     430    }
     431}
     432
     433if ( success ) printf("\n[sort] success\n");
     434else           printf("\n[sort] failure\n");
     435#endif
     436
     437#if INSTRUMENTATION
     438char   name[64];
     439char   path[128];
     440
     441// build a file name from n_items / n_clusters / n_cores
     442if( USE_DQT_BARRIER ) snprintf( name , 64 , "sort_dqt_%d_%d_%d",
     443                      ARRAY_LENGTH, x_size * y_size, ncores );
     444else                  snprintf( name , 64 , "sort_smp_%d_%d_%d",
     445                      ARRAY_LENGTH, x_size * y_size, ncores );
     446
     447// build file pathname
     448snprintf( path , 128 , "home/%s" , name );
     449
     450// compute results
     451unsigned int sequencial = (unsigned int)(seq_end_cycle - start_cycle);
     452unsigned int parallel   = (unsigned int)(para_end_cycle - seq_end_cycle);
     453
     454// display results on process terminal
     455printf("\n----- %s -----\n"
     456       " - sequencial : %d cycles\n"
     457       " - parallel   : %d cycles\n",
     458       name, sequencial, parallel );
     459
     460// open file
     461FILE * stream = fopen( path , NULL );
     462if( stream == NULL )
     463{
     464    printf("\n[sort error] cannot open instrumentation file <%s>\n", name );
     465    exit(0);
     466}
     467
     468// register results to file
     469fprintf( stream , "\n----- %s -----\n"
     470                  " - sequencial : %d cycles\n"
     471                  " - parallel   : %d cycles\n",
     472         name, sequencial, parallel );
     473
     474// close instrumentation file
     475if( fclose( stream ) )
     476{
     477    printf("\n[sort error] cannot close instrumentation file <%s>\n", name );
     478    exit(0);
     479}
    389480#endif
    390481
    … …  
    392483
    393484}  // end main()
    394 
    395485
    396486/*
Note: See TracChangeset for help on using the changeset viewer.